<<
>>

Линейное программирование как обобщенный метод

Наш 2-аппроксимирующий алгоритм взвешенной версии задачи о вершинном по- крытии будет основан на линейном программировании. Линейное программиро- вание описывается здесь не для того, чтобы дать общий алгоритм аппроксимации, а чтобы продемонстрировать его мощь и универсальность.

Что же такое линейное программирование? Чтобы ответить на этот вопрос, будет полезно для начала вспомнить из линейной алгебры задачу системы ли- нейных уравнений. B матрично-векторной записи имеется вектор x неизвестных вещественных чисел, заданная матрица A и заданный вектор b; требуется решить уравнение Ax = b. Многим хорошо известен метод исключения Гаусса, позволяющий эффективно решать такие задачи.

Базовая задача линейного программирования может рассматриваться как более сложная версия этой задачи, в которой равенства заменены неравенствами. Говоря конкретнее, рассмотрим задачу определения вектора x, удовлетворяющего неравен- ству Ax > b. Под этой записью мы имеем в виду, что каждая координата вектора Ax должна быть больше либо равна соответствующей координаты вектора b.

Такие системы неравенств определяют области в пространстве. Например, предположим, x = (x1,x2) — двумерный вектор, и имеются четыре неравенства:

xj > 0, x2 > 0

xj + 2x2 > 6 2xj + x2 > 6

В этом случае множество решений определяет область на плоскости, изобра- женную на рис. 11.10. Для заданной области, определяемой уравнением Ax > b, линейное программирование стремится минимизировать линейную комбинацию координат x по всем x, принадлежащим области.

Рис. 11.10. Область допустимых решений простой задачи линейного программирования

Такая линейная комбинация может быть записана в виде ctx, где c — вектор коэффициентов, а c‘x обозначает скалярное произведение двух векторов.

Таким образом, стандартная форма линейного программирования как задачи оптими- зации выглядит следующим образом.

Для заданной матрицы A с размерами m χ n, векторов b Rm и c Rn найти

вектор x e Rn для решения следующей задачи оптимизации:

miп(⅛ для x > 0; Ax > b).

c‘x часто называется целевой функцией линейной программы, а Ax > b называется набором ограничений. Например, в примере на рис. 11.10, допустим, определяет- ся вектор c (1,5, 1); другими словами, мы стремимся минимизировать величину 1,5x1 + x2 по области, определяемой неравенствами.

Задача решается выбором точки x = (2,2), в которой пересекаются две наклон- ные линии; в ней ctx = 5, и вы можете убедиться, что получить меньшее значение невозможно.

Задачу линейного программирования можно сформулировать как задачу при- нятия решения следующим образом:

Для заданной матрицы A, векторов b и c, и границы γ существует ли такое зна- чение x, для которого x > 0, Ax > b, и ctx < γ?

Чтобы избежать проблем, связанных с представлением вещественных чисел, мы будем считать, что координаты в векторах и матрице являются целыми числами.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Линейное программирование как обобщенный метод:

  1. Метод обобщения независимых характеристик.
  2. ИГНОРИРУЙТЕ ЛИНЕЙНЫЕ ПРЕДСКАЗАНИЯ И ИЗБЕГАЙТЕ ЛИНЕЙНЫХ ВЫВОДОВ! ВЕРЬТЕ СВОЕМУ СЕРДЦУ!
  3. ГЛАВА 18 ОБОБЩЕНИЕ МЕТОДА ГИПСОСОЗНАНИЯ И УКАЗАНИЯ ПО ЕГО ПРИМЕНЕНИЮ
  4. Нередко предлагаемое в вопросе действие респонденты оценивают как обобщенное, типичное, т.е. как действие, которое они обычно совершают.
  5. 7. Интересуйтесь тем, как ваш ребенок относится к слабым ученикам, как помогает им, какими методами завоевывает авторитет
  6. ОБОБЩЕНИЕ
  7. Линейно-функциональные структуры.
  8. ОБОБЩЕНИЕ ТЕОРЕТИЧЕСКОЕ
  9. ОБОБЩЕНИЕ ЭМПИРИЧЕСКОЕ
  10. Линейный и нелинейный умы
  11. Линейные структуры.
  12. Линейный ум-эго
  13. Модификации линейной организационной структуры.
  14. Иванова Г.С. Основы программирования, 2002
  15. Линейный и нелинейный ум
  16. Линейное и нелинейное мышление
  17. Линейное и нелинейное мышление
  18. Эстетика программирования
  19. Перефразирование и обобщение.
  20. Перефразирование и обобщение.