Пример 1.3

Минимизировать функцию

при ограничениях

В стандартной форме с неотрицательными дополнительными переменными ограничения и целевая функция принимают вид

(2.11)

Поскольку в этом случае коэффициенты b положительны, а новые переменные имеют коэффициент +1, ясно, что набор образует базисное фундаментальное решение, а уравнения (2.11) имеют соответствующий вид.

Функция z, имеющая нулевое значение, выражена через небазисные переменные, которые также имеют нулевое значение. Как в таком случае можно уменьшить значение функции z? Поскольку x ₁ и x ₂ должны быть неотрицательны, любое изменение их значений является увеличением этих значений. Поскольку коэффициенты при x ₁ и x ₂ в канонической форме функции z отрицательны, любое такое изменение приведет к убыванию функции z. Вместо того чтобы увеличить их значения одновременно, для простоты выберем одну из переменных. Так как коэффициент при x ₂ больше по модулю, выбираем x ₂.

Однако при увеличении x ₂ значения x ₃ и x ₄ будут изменяться, поскольку должны выполняться уравнения (2.11). Все переменные при этом должны оставаться неотрицательными. Таким образом, должен существовать предел увеличения x ₂.

Поскольку , x ₃ обращается в 0 при x ₂ = 1700/4 = 425.

Поскольку , x ₄ обращается в 0 при x ₂ = 1600/5 = 320.

Таким образом, мы не можем увеличивать x ₂ более чем до 320 (минимального из этих значений), не нарушая условие неотрицательности.

Второе ограничение может быть записано в виде

Если вычесть это уравнение, умноженное на 4, из уравнения первого ограничения (2.11) (4 - коэффициент при x ₂ в этом уравнении), а затем вычесть это же уравнение, умноженное на - 4, из выражения для целевой функции (- 4 - коэффициент при x ₂ в целевой функции), то переменная x ₂ будет исключена отовсюду, кроме второго ограничения, куда она входит с коэффициентом 1.

Ограничения и целевая функция принимают вид

что является канонической формой для базиса x ₂, x ₃, представляющего базисное допустимое решение.

Небазисными переменными стали переменные x ₁ и x ₄. В данный момент они равны 0.

Теперь можно уменьшить значение функции z, увеличив только x ₁. Но на сколько можно увеличить x ₁, чтобы x ₂ и x ₃ оставались неотрицательными?

Для уравнения

Таким образом, нельзя увеличивать x ₁, более чем до 300 (минимального из этих значений). После деления на 7/5 (коэффициент при x ₁) первое ограничение принимает вид

Исключим x ₁ из другого ограничения и выражения для целевой функции, вычтя последнее соотношение, умноженное на 2/5 и -2/5, из ограничения и целевой функции. Получим каноническую форму задачи в базисе x ₁, x ₂, тоже являющимся допустимым. Она имеет следующий вид:

Заметим, что увеличение любой из небазисных переменных x ₃, x ₄ (эти переменные входят в выражение для целевой функции z с положительными коэффициентами) приведет к возрастанию функции z. Таким образом, дальнейшее убывание функции z невозможно и достигнуто минимальное значение функции z, равное -1400 при допустимом базисном решении x ₁ = 300, x ₂ = 200, x ₃ = x ₄ = 0. Если вернуться к геометрической интерпретации на рис.. 1.1, то можно убедиться, что последовательность канонических форм привела из точки 0 в точку A и из точки A в точку B - точку минимума. При выборе в уравнениях (2.11) увеличения x ₁ та же процедура привела бы из точки 0 в точку B через точку C.

Этот итерационный процесс удобно проиллюстрировать в так называемых симплекс-таблицах. Они состоят из уравнений (2.11) - (2.13) для ограничений и целевой функции, записанных в виде

ü Табличный симплекс-метод

Ниже приведены обобщенные результаты, сведенные в таблицы.

На итерации 0 звездочкой отмечено значение 5 - коэффициент при переменной, которую мы собираемся обратить в базисную в предельном ограничении. На итерации 1 отмечено число 7/5. Заметим также, что мы ставим точки вместо переменных, обязанных иметь нулевые значения, чтобы отличить их от переменных, обращающихся в 0 случайно.

Результаты, полученные в рассмотренном примере, можно обобщить. Предположим, что начальная каноническая форма задана, и что на k -й итерации получена каноническая форма, заданная уравнениями (2.4) и (2.5), запись которых приведена ниже в таблице.

Итерационный процесс состоит из трех шагов.

1. Найти переменную для включения в базис.

2. Найти переменную для исключения из базиса.

3. Построить новую каноническую форму.

4) Двойственность в линейном программировании

Многие из полученных результатов легче объяснить, введя понятие двойственности. Мы увидим, что каждой задаче линейного программирования соответствует другая (двойственная) задача. Если понять взаимосвязь между этими задачами, то можно получить решение обеих, когда известно решение любой их них. Введем новые понятия.

Прямая задача:

найти такие , что

и функция имеет максимальное значение.

Ей соответствует двойственная задача: найти такие

и функция имеет минимальное значение.

Исходная задача:

найти такие , , что

и функция имеет минимальное значение.

Соответствующая двойственная задача:

найти такие , , , что

и функция имеет максимальное значение.

Прямая задача имеет ограничения в виде неравенства со знаком ≥, а двойственная – со знаком ≤. Матрица коэффициентов ограничений двойственной задачи является транспонированной матрицей коэффициентов прямой задачи. Коэффициенты целевой функции двойственной задачи являются значениями правых частей ограничений прямой задачи, и наоборот.

В матричной записи прямая задача имеет следующий вид:

найти такой x ≥ 0, что

Ax ≥ b