Симплекс-метод решения задачи линейного программирования, страница 10

Несоблюдение этих правил лишает смысла все остальные действия.

г) Из заключительной симплексной таблицы необходимо извлечь решение задачи линейного программирования или указать, почему она неразрешима.

3.3 Решение задачи производственного планирования симплекс-методом

Решим симплекс-методом задачу из раздела 1.1. Для этого вначале нужно привести ее к канонической форме. Это было сделано в разделе 1.4.1. В такой задаче есть готовый базис: переменные x₃, x₄ и x₅. Исходная симплексная таблица примет вид таблицы 11 (столбцы J и К предназначены для вспомогательных расчетов).

Таблица 11 – Исходная симплексная таблица для задачи производственного планирования

Критерий оптимальности нарушен в двух столбцах x₁ и x₂. Следовательно, чтобы увеличить значение прибыли, надо увеличить (включить в базис) любую из этих переменных.

Если выбрать переменную x₁, то разрешающим элементом будет а₁₁, так как min {800/0,8; 600/0,2; 120/0,01} = min {1000; 3000; 12000} = 1000. Тогда прибыль возрастет на 1000*108 = 108000. Если выбрать переменную x₂, то разрешающим элементом будет а₃₂, так как min {800/0,5; 600/0,4; 120/0,1} = min {1600; 1500; 1200} = 1200. Тогда прибыль возрастет на 1200*140 = 168000. Так как 168000 > 108000, лучше ввести в базис x₂.

Описанные расчеты нет необходимости осуществлять вручную. Можно, например, ввести в J3 формулу =$D3/E3, а затем скопировать ее на К3 и J4:К5. В результате в диапазоне ячеек J3:К5 будут получены те отношения, из которых выбирается наименьшее. Если бы какой-либо из коэффициентов в столбцах Е и F был неположительным, то в столбцах J и К появилось бы отрицательное число или сообщение о попытке деления на ноль. Выбрать наименьшее из положительных отношений в такой задаче можно вручную. Затем в J6 можно ввести формулу =$D3/E3, а в К6 - =F6*K5. Результаты вычислений приведены в таблице 11. Для вспомогательных расчетов можно использовать любые свободные ячейки.

Итак, в базис войдет x₂, при этом из базиса выходит x₅, и таблица примет вид таблицы 12 (обе части третьего ограничения делят на 0,1; а из остальных трех строк вычитают преобразованное третье ограничение, умноженное соответственно на 0,5; 0,4 и -140).

Таблица 12 – Вторая симплексная таблица для задачи производственного планирования

Здесь критерий оптимальности нарушен только в одном столбце - x₁. Так как min {200/0,75; 120/0,16; 1200/0,1} = min {266 2/3; 750; 12000} =
= 266 2/3, из базиса выйдет x₃. Таблица примет вид таблицы 13 (обе части первого ограничения делят на 0,75; а из остальных трех строк вычитают преобразованное первое ограничение, умноженное соответственно на 0,16; 0,1 и -94).