Решение одной из пары двойственных задач можно найти, зная только ответ к другой задаче и пользуясь 2-й теоремой двойственности: если i-e ограничение одной из пары двойственных задач на компонентах оптимального решения есть строгое неравенство, то оптимальное значение i-й переменной другой задачи равно 0, или, что то же самое - если оптимальное значение j-й переменной одной задачи строго положительно, то j-e ограничение другой из пары двойственных задач на компонентах оптимального решения есть равенство.

Важен экономический смысл двойственных оценок. Двойственная оценка, например, третьего ресурса у3=5 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли на 5 единиц.

Расшивка "узких мест" производства

Таблица N 3

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, тем самым они образуют "узкие места" производства. Будем их заказывать дополнительно. Пусть Т=( t1,t2,t3) - вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие H+Q-lТ≥0, где Н - значения базисных переменных в последней симплексной таблице, а Q-1 - обращенный базис, который образуют столбцы при балансовых переменных в этой таблице. Задача состоит в том, чтобы найти вектор Т, максимизирующий суммарный прирост прибыли W=6t1+5 t3 при условии сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой продукции), предполагая, что можно получить дополнительно не более 1/3 первоначального объема ресурсов каждого вида.

24 2/7 0 -1/7 t1 0

4 + -4/21 1 -5/21 0 ≥ 0

34 -1/21 0 4/21 t3 0

t1 198

0 ≤ 1/3 96

t3 228

t1≥0, t3≥0.

W=6t1+5t3 àmax

-2/7 t1 + 1/7 t3 ≤ 24

4/21 t1 + 5/21 t3 ≤ 4

1/21 t1 - 4/21 t3 ≤ 34

t1≤198/3, t3≤228/3.

t1≥0, t3≥0.

Как видно, после графического решения (График 2) программа расшивки приобретает вид:

t1=21, t2=0, t3=0

С новым количеством ресурсов: 198+21 219

b' = 96+0 = 96

228+0 228

у предприятия будет новая производственная программа.

Найдем h'=Q-1 b'

5/28 0 -1/7 219 30 àx3

-4/7 1 -1/7 96 = 0 àx6

-3/28 0 2/7 228 33 àx1

Теперь новая производственная программа имеет вид: X'оpt=(33;0;30;0). При этом второй ресурс был использован полностью.

219

При наличии ресурсов b' = 96 производство наиболее выгодно, так как

228

достигается max прибыль с использованием всех ресурсов. Также обратим внимание на то, что производство продукции 1–го вида при заказе дополнительных ресурсов необходимо будет уменьшить на 15 единиц, а производство продукции 3–го вида – увеличить на единицу.

ΔLmax=(Y,t)=6·21=126, где Y=(6;0;5); t(21;0;0)

L'max= ΔLmax+ Lmax=126+2328=2454.

Этот результат можно проверить, подставив значения х1 и х3 в первоначальную целевую функцию: L'max=48xl+30x2+29x3+10x4=31·37+41·21=1147+861=2454.

Транспортная задача

Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в т пунктах производства (хранения) в количествах a1, а2, ., аm единиц, необходимо распределить между п пунктами потребления, которым необходимо соответственно b1, b2,,…, bn единиц. Стоимость перевозки единицы продукта из i-ro пункта отправления в j-й пункт назначения равна cij и известна для всех маршрутов. Необходимо составить план перевозок, при кото­ром запросы всех пунктов потребления были бы удовлетворены за счет имею­щихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Обозначим через xij количество груза, планируемого к перевозке от i-ro поставщика j-му потребителю. При наличии баланса производства и потребле­ния

математическая модель транспортной задачи будет выглядеть так:

найти план перевозок

X=(xij), xij³0, iÎNm, jÎNn

минимизирующий общую стоимость всех перевозок

при условии, что из любого пункта производства вывозится весь продукт

, iÎNm

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

, jÎNn

Для решения транспортной задачи чаще всего применяется метод потен­циалов. Пусть исходные данные задачи имеют вид