Ручной расчет задачи линейного программирования.

Требуется максимизировать функцию

z=4x₁+5x₂

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

-2x₁-x₂+x₃=-2

x₁-x₂£ -1

- x₁ - x₂ £ -2

0x₁+ 1x₂ £ 2

2x₁ + 1x₂ £ 4

x₃ ³ 0

Коэфициенты ограничений, записанных в таком виде, переписываются со своими знаками, в последней строке таблицы записываются коэффициенты целевой функции с противоположными знаками. Сперва следует исключить свободные переменные, перекинув их на бок таблицы:

После этого следует исключить нуль-уравнение:

Мы видим, что свободные члены в непомеченных строках неотрицательны, следовательно опорное решение получено и надо перейти к поиску оптимального решения. Находим непомеченные столбцы с отрицательными коэфициентами целевой функции, исключая последний. У нас таких нет, поэтому оптимальное решение получено и переходим к извлечению результатов. Для этого составим еще одну таблицу, где содержаться переменные прямой и двойственной задач. Для извлечения решений нужны только столбец свободных членов и строка коэффициентов целевой функции. Поэтому внутренняя часть таблицы не преведена.

В итоге получаем следующие результаты:

1. Прямая задача. Переменные прямой задачи, находящиеся сверху таблицы равны в решении 0, а сбоку - соответствующим свободным членам:

x₁=1; x₂=2; x₃=2.

2. Двойственная задача. Переменные двойственной задачи, находящиеся сверху таблицы равны 0, а сбоку - соответствующим коэфициентам целевой функции:

u₁=0; u₂=4; u₃=0; u₄=8; u₅=0.

Значение целевых функций обеих задач z_max= w_min=12.