Файл: Е.В. Буйная Симплексный метод решения оптимизационных задач.pdf

13

Новая симплексная таблица для Б1=(А5, А4, А7) будет выглядеть следующим образом:

Полученный опорный план не оптимален, следовательно, необхо-

В результате в базис войдут векторы: Б2=(А5, А4, А2). Строим новую симплексную таблицу.

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

новую симплексную таблицу.

14

Из полученной таблицы видно, что найденный опорный план оптимален для данной задачи (все ∆ k ≥ 0), т.е.

Хопт=(1100/79; 2400/79; 0; 4300/79) и Lmax = 31360/79.

Ответ для нашей задачи будет выглядеть следующим образом: для того, чтобы прибыль от производства и реализации продукции трех видов была максимально возможной при данных условиях, необходимо закупить сырье 1-го вида в объеме - ~ 13,92 единицы; сырье 2-го вида - ~ 30,38 единицы; сырье 3-го вида не закупать вовсе; сырье 4-го вида - ~ 54,43 единицы. В результате подобной политики мы получим прибыль в размере ~396,96 у.е.

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

существование ∆ k=0, не соответствующего базисным векторам, можно сделать вывод, что найденный оптимальный план не единст-

венный (можно перейти к другому плану с тем же значением целевой функции).

Пример 2.

Рассмотрим следующую ситуацию, с которой вы сталкиваетесь каждый день. Предположим, что вы собрались в магазин канцелярских товаров. Ваша задача сделать как можно больше покупок при условии, что вы покупаете только 3 разновидности товара, а именно ручки, карандаши и блокноты (если рассматривать весь ассортимент товара, размерность задачи значительно увеличится, при наличии достаточного количества свободного времени можете попытаться ее решить). В кармане у вас 50 у.е. и, кроме всего прочего, вам необходимо купить хотя

15

бы 3 ручки и 2 блокнота. Вполне закономерно, что вам известна цена товаров: 10 - ручка, 5 – карандаш и 20 у.е. – блокнот.

Если вы обладаете достаточными аналитическими способностями, то сразу сможете сделать вывод по поводу решения данной задачи, но, в качестве примера, попытаемся решить ее симплекс-методом.

Решение:

Если обозначить за Х1 – количество приобретаемых в магазине ручек, за Х2 – карандашей, а за Х3 – блокнотов, то исходную задачу можно представить в следующем виде:

Максимизировать

L(X)=X1+X2+X3

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

10 X1+5 X2+20 X3≤ 50,

X1≥ 3,

X3≥ 2,

X1, X2, X3≥ 0.

После приведения к каноническому виду задача примет вид:

максимизировать

L(X)=X1+X2+X3

X1,X2 ,X3 ,X4 ,X5 ,X6 ≥ 0

При определении начального опорного плана сталкиваемся с отсутствием единичной подматрицы и, следовательно, вводим искусст-

16

максимизировать

L(X)=X1+X2+X3-M X7-M X8

X1 , X 2 , X 3 , X 4 , X 5 , X6 , X7 , X 8 ≥ 0

Отыскав таким образом единичный начальный базис Б0=(А4, А7, А8), переходим к построению симплексных таблиц.

Если принять во внимание, что М – это большое положительное число, то из данной таблицы видно, что опорный план не оптимален (не все ∆ k>0 и хотя бы одно из значений Zjk >0).

Рассчитываем

Вводя в базис А1 вместо А7, получаем новую симплексную табли-

цу.

Из таблицы видно, что данный опорный план оптимален. Однако

в базисе находится искусственная переменная и она не равна нулю, от-

сюда заключаем, что в исходной задаче противоречивые ограничения. Если вспомнить о происхождении решенной задачи, то при ука-

занном количестве денег в кармане вам необходимо «умерить свой аппетит».