Линейное программирование. Симплексный метод. Методы теории игр.

Решение. Пусть изделие данного типа может быть произведено на фабрике В1 в количестве 216ед., на фабрике В2 в количестве 126ед., на фабрике В3 в количестве 146ед., а производственные мощности для изделий обеспечива-ются наличием деталей для изделий на филиалах: в А1 в объёме 80ед; в А2 в объёме 90ед; в А3 в объёме 75ед; в А4 в объёме 100ед; в А5 в объёме 800ед. При заданной матрице стоимостей Сij каждой модификации можно утверж-дать, что мы имеем дело с типовой транспортной задачей по передаче от фи-лиала i на фабрику j изделий в количестве хij, где i=1, 2, 3, а j=1, 2, 3, 4, 5. При этом цель распределения поставок заключается в том, чтобы себестои-мость продукции Z= была минимальной при условиях =216, =126, =146, =80, =90, =75, =100, =800. Cократим записи так =ai, i=1, 2, 3; =bi, j=1, 2, 3, 4, 5.
В виде математической модели задачу запишем так
Перед началом вычислений проверим 80+90+75+100+800=1145 и 216+126+146=488. Так как объём источников не равен объёму потре-бления. То данная задача относится к типу открытой. Оптимизировать можно только закрытую транспортную задачу.
Так как запрос (заказ, потребность) на количество комплектующих меньше мощности филиалов на величину 1105-488=657ед., то введём в задачу фикти-вную фабрику А4, установим себестоимость модификации из филиалов в А4 предельно высокой (сравнительно с остальными модификациями, обычно в три-четыре раза выше максимальной из данных) и тогда задача станет закрытого типа.
Теперь можно формировать начальную расчётную таблицу закрытой транспортной задачи
Фили-
алы
Фаб-
рики
В1 В2 В3 В4
216 126 146 657
А1
80 12 15 21 40
80
А2
90 12 16 13 40
90
А3
75 15 13 12 40
75
А4
100 14 11 17 40
100
А5
800 12
216 10
126 14
146 40
312
Значения себестоимостей в матрице будем располагать в правом верхнем углу клеток, а в левом нижнем углу клеток будем располагать объёмы по-ставок. Если поставка в клетку отсутствует, то в левом нижнем углу НИЧЕ-ГО не записываем (даже символ нуля). Заполнять объёмы поставок будем методом «минимальной стоимости». Его сущность станет понятной при работе:
-ищем матрице наименьшую стоимость – 10 в клетке А5В2 и из запаса А5 направляем фабрике В2 максимально возможную поставку 126ед.; из оста-вшихся 800-126=674ед отправляем максимально возможную поставку 216ед. в следующую клетку А5В1 с наименьшей стоимостью 12; из оставшихся 674-
-216=458ед отправляем максимально возможную поставку 146ед клетку А5В3 с очередной наименьшей стоимостью 14; из оставшихся 458-146=
=312ед отправляем максимально возможную поставку 146ед клетку А5В3 с очередной наименьшей стоимостью 14; из оставшихся 312ед отправляем максимально остаток 312ед клетку А5В4 с очередной наименьшей для строки стоимостью 40; на этом весь ресурс 800ед израсходован;
-ищем в оставшихся клетках минимальную стоимость – это 11 в клетке А4В2; но передавать что-то из ресурса А4 в заказ В2 совершенно нет необ-ходимости, так как этот заказ уже насыщен ранее из ресурса А5; поэтому в строке А2 можно передать что-то в другие клетки; но А4В1 и А4В3 тоже насыщены, а потому весь запас 100ед передаём в клетку А4В4;
-по такой же схеме раздаём и остальные ресурсы – все пойдут в клетки: А3В4 передадим 75ед, в А2В4 передадим 90ед, в А1В4 передадим 80ед.
Все ресурсы распределены. Все заявки насыщены. Проконтролируем прави-льность составления плана поставок 800+100+75+80+90=216+126+146+ 312=
= 1145, значит план поставок верен – таблица составлена правильно.
Получен начальный опорный план поставок. Значение целевой функ-ции Z=40 80+40 90+40 75+40 100+12 216+10 126+14 146+40 312=32176.
Проверим план на вырожденность: число занятых поставками клеток (нену-левых) равно 8, то есть равно сумме строк и столбцов в таблице минус 1, то есть 4+5-1. Следовательно, этот план невырожден и его можно улучшать. Оптимизировать план будем методом потенциалов по алгоритму:
1.Филиалам Аi прикрепляем потенциалы ui, i=1, 2, 3, 4, 5; фабрикам Вj при-крепляем потенциалы vj, j=1, 2, 3, 4; для ui добавляем столбец справа, для vj – строка внизу расчётной таблицы;
2.Для всех, занятых поставками (базисных) клеток составим уравнения потенциалов Так как уравнений 8, а потенциалов 9 (всех), то для решения этой системы можно один потенциал взять равным любому числу. Чаще всего берут равным нулю. Возьмём v4=0, тогда из первых пяти уравнений найдём сразу u1=-40=u2=u3=u4=u5, из 6-го уравнения v3=-26, из 7-го v2=-30 и из 8-го v1=-28. Таблица с потенциалами примет вид
Фили-
алы
Фаб-
рики
В1 В2 В3 В4
u
216 126 146 657
А1
80 12 15 21 40
80 -40

А2
90 12 16 13
40
90
-40
А3
75 15 13 12 40
75 -40
А4
100 14 11 17 40
100 -40
А5
800 12
216 10
126 14
146 40
312 -40
v -28 -30 -26 0
3.Для всех незагруженных (свободных) клеток проверим условие оптималь-ности - вычисляем оценки vj-ui и сравниваем их со стоимостями cij. Если все cij> vj-ui, то план оптимален, в противном случае – не оптимален. Имеем : c11=12>-28-(-40)=12 –выполнено; с12=15>-30-(-40)=10 –выполнено,
с13=21>-26-(-40)=14 –выполнено, с21=12>-28-(-40)=12 выполнено,
с22=16>-30-(-40)=10–выполнено, с23=13<-26-(-40)=14– не выполнено
с31=15>-28-(-40)=12 – выполнено, с32=13>-30-(-40)=10 – выполнено,
с33=12<-26-(-40)=14 – не выполнено, с41=14>-28-(-40)=12 выполнено,
с42=11>-30-(-40)=10 –выполнено, с43=17>-26-(-40)=14 –выполнено.
Имеются неравенства типа “меньше” и потому план не оптимален, и может быть улучшен.
Для клетки А2В3 условие оптимальности не выполнено; строим для неё цикл пересчёта, начиная с клетки А2В3 со знаком +, а затем чередуя знак ходом ладьи вдоль строк и столбцов: А2В3-А5В3+А5В4-А2В4. Цикл изобра-жён штриховой ломаной на таблице выше. Из отрицательных ветвей цикла выбрать мин{90, 146}=90ед – это максимальная поставка для пересчёта плана на предмет оптимизации Это будет клетка А2В4. По этому циклу можно перебросить 90ед ресурса и получить улучшенный план.