Использование симплекс-метода.

Преобразуем исходную математическую модель к каноническому виду

, (1*)

(2*)

х₁ ³ 0, х₂ ³ 0, х₃ ³ 0, х₄ ³ 0, х₅ ³ 0. (3*)

Здесь х₃, х₄, х₅ – дополнительные балансовые (остаточные) переменные, добавленные в неравенства для преобразования их в равенства.

Допустимое базисное решение имеет вид , 0.

Построим начальную симплекс-таблицу 1.36.

Решение не является оптимальным, так как в - строке таблицы стоят отрицательные элементы.

Таблица 1.36

Столбец x₂ выберем в качестве разрешающего, поскольку в - строке симплекс-таблицы для столбцов свободных переменных именно в нем находится наименьшее отрицательное число (–3).

Строку x₄ определим в качестве разрешающей, так как ей соответствует наименьшее симплекс-отношение симплекс - столбца.

На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент, равный 10.

Делаем один шаг симплексных преобразований.

Таким образом, симплекс-таблица примет вид.

Таблица 1.37

Новое базисное решение , 12, хотя и улучшает значение целевой функции по сравнению с начальным, но не является оптимальным, поскольку в последней - строке симплекс-таблицы имеется отрицательный элемент (значение ( –0,8) в столбце х₁).

Выберем столбец х₁ в качестве разрешающего, как содержащий отрицательный элемент в - строке симплекс-таблицы 1.37.

Строку x₅ определим в качестве разрешающей, так как ей соответствует наименьшее симплексное отношение. Делаем шаг симплексных преобразований. Получаем таблицу 1.38

Таблица 1.38

Оптимальное решение найдено, поскольку в последней строке симплекс-таблицы 1.38 отсутствуют отрицательные элементы. Для небазисных переменных значения элементов последней строки положительны, следовательно, задача имеет единственное оптимальное решение , при этом  15,2.

2.  Построим математическую модель двойственной задачи (1*) - (3*).

, (4*)

(5*)

y₁ ³ , y₂ ³ 0, y₃ ³ 0. (6*)

Оптимальное решение двойственной задачи можно определить на основе оптимального решения прямой задачи

Из теорем двойственности следует:

1) экстремальные значения целевых функций разрешимых прямой и двойственной задач совпадают, следовательно, 15,2;

2) компоненты оптимального плана двойственной задачи находятся в строке целевой функции итоговой симплекс-таблицы прямой задачи.

Значение переменной y_i двойственной задачи соответствует теневой цене i-го ресурса прямой задачи.

При приведении исходной задачи линейного программирования к каноническому виду в первое неравенство, соответствующее ресурсу Р₁, для преобразования его в равенство добавлялась балансовая переменная х₃. Таким образом, значение переменной y₁ следует искать в последней строке итоговой симплекс-таблицы в столбце х₃ и так далее. Исходя из принципа соответствия , находим остальные переменные. Симплексная таблица 1.39 с двойственными решениями будет иметь вид

Т аблица 1.39

Оптимальное решение двойственной задачи будет (0;0,3;0,8;0;0).

3. Определим статус ресурсов.