2020-06-08
63Дано: 
Решение:
1) Обозначим через Хij - количество единиц продукции, которое планируется перевезти с завода Аi (i=1,2,3) на склад Вj (j=1,2,3,4), а через f - суммарные затраты на её изготовление и доставку.
Суммарная мощность пунктов производства составляет: 160+140+170=470.
Суммарная пропускная способность складов составляет: 120+150+190+110=570
Замечаем, что суммарная пропускная способность складов выше суммарной мощности пунктов производства: 470<570
Таким образом, условие закрытости модели не выполняется, поэтому надо вводить фиктивный пункт производства А4 с возможным выпуском: 570-470=100 и стоимостью перевозок Сi5=0 (i=1,2,3).
После введения фиктивного склада открытая модель задачи преобразовалась в закрытую.
Составим распределительную таблицу 1.
| Пункты производства Аi и их мощность. | В1 (120) | В2 (150) | В3 (190) | В4 (110) |
| А1(160) | 7+1=8 Х11 | 8+1=9 Х12 | 1+1=2 Х13 | 2+1=3 Х14 |
| А2(140) | 4+5=9 Х21 | 5+5=10 Х22 | 9+5=14 Х23 | 8+5=13 Х24 |
| А3(170) | 9+2=11 Х31 | 2+2=4 Х32 | 3+2=5 Х33 | 6+2=8 Х34 |
| А3(100) | 0 Х41 | 0 Х42 | 0 Х43 | 0 Х44 |
Где:
- стоимость изготовления и доставки единицы продукции с завода Аi (i=1,2,3) на склад Вj(j=1,2,3,4,5).
Экономико-математическая модель задачи примет вид:
- суммарные затраты:
- 
условия полной отгрузки продукции со всех пунктов производства:
- 
условия полной загрузки всех складов:
-Условия неотрицательности переменных:
Таким образом, задача сводится к нахождению решения (Х11*, Х12*,…, Х35*) системы линейных уравнений (2), (3), доставляющих минимум линейной функции (1).
Решим данную задачу транспортного типа методом потенциалов.
Критерием оптимальности задачи минимизации является отсутствие в заключительной таблице свободных клеток с отрицательными оценками.
В таблице 2 построен начальный опорный план методом минимального элемента.
Табл. 2.
| 120 | 150 | 190 | 110 | Ui | |
| 160 | 8 | 9 | 2 160 | 3 | U1 =0 |
| 140 | 9 + 20 | 10 | 14 - 10 | 13 110 | U2 =12 |
| 170 | 11 | 4 150 | 5 20 | 0 | U3 =3 |
| 100 | 0 - 100 | 0 | 0 + | 0 | U4 =3 |
| Vj | V1=-3 | V2=1 | V3=2 | V4=1 |
Число занятых клеток равно 7, совпадает с m+n-1=3+5-1=7 - опорный план - невырожденный.
 |
Для исследования плана на оптимальность необходимо найти оценки свободных клеток. Для этого надо знать потенциалы Ui и Vj, которые определим в результате решения системы уравнений, составленных по заполненным клеткам:
Получаем
Найдём оценки свободных клеток:
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 8 | 9 | 2[160] | 3 | 160 |
| A2 | 9[30] | 10 | 14 | 13[110] | 140 |
| A3 | 11 | 4[150] | 5[20] | 8 | 170 |
| A4 | 0[90] | 0 | 0[10] | 0 | 100 |
| Потребности | 120 | 150 | 190 | 110 |
Продолжаем алгоритм до тех пор, пока все оценки свободных клеток не станут положительными:
Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v3 = 2; 0 + v3 = 2; v3 = 2
u3 + v3 = 5; 2 + u3 = 5; u3 = 3
u3 + v2 = 4; 3 + v2 = 4; v2 = 1
u4 + v3 = 0; 2 + u4 = 0; u4 = -2
u4 + v1 = 0; -2 + v1 = 0; v1 = 2
u2 + v1 = 9; 2 + u2 = 9; u2 = 7
u2 + v4 = 13; 7 + v4 = 13; v4 = 6
| v1=2 | v2=1 | v3=2 | v4=6 | |
| u1=0 | 8 | 9 | 2[160] | 3 |
| u2=7 | 9[30] | 10 | 14 | 13[110] |
| u3=3 | 11 | 4[150] | 5[20] | 8 |
| u4=-2 | 0[90] | 0 | 0[10] | 0 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых Si j < 0
S14 = 3 –(6 + 0) =- 3
S34 = 8-(6+3)=-1
S44 = 0-(6-2)=-4
max(3,1,4) = 4
Выбираем максимальную оценку свободной клетки (4;4): 0
Для этого в перспективную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 8 | 9 | 2[160] | 3 | 160 |
| 2 | 9[30][+] | 10 | 14 | 13[110][-] | 140 |
| 3 | 11 | 4[150] | 5[20] | 8 | 170 |
| 4 | 0[90][-] | 0 | 0[10] | 0[+] | 100 |
| Потребности | 120 | 150 | 190 | 110 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 1) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 8 | 9 | 2[160] | 3 | 160 |
| A2 | 9[120] | 10 | 14 | 13[20] | 140 |
| A3 | 11 | 4[150] | 5[20] | 8 | 170 |
| A4 | 0 | 0 | 0[10] | 0[90] | 100 |
| Потребности | 120 | 150 | 190 | 110 |
u1 + v3 = 2; 0 + v3 = 2; v3 = 2
u3 + v3 = 5; 2 + u3 = 5; u3 = 3
u3 + v2 = 4; 3 + v2 = 4; v2 = 1
u4 + v3 = 0; 2 + u4 = 0; u4 = -2
u4 + v4 = 0; -2 + v4 = 0; v4 = 2
u2 + v4 = 13; 2 + u2 = 13; u2 = 11
u2 + v1 = 9; 11 + v1 = 9; v1 = -2
| v1=-2 | v2=1 | v3=2 | v4=2 | |
| u1=0 | 8 | 9 | 2[160] | 3 |
| u2=11 | 9[120] | 10 | 14 | 13[20] |
| u3=3 | 11 | 4[150] | 5[20] | 8 |
| u4=-2 | 0 | 0 | 0[10] | 0[90] |
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
S22 = 10-(1+11)=-2
Выбираем максимальную оценку свободной клетки (2;2): 10
Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 8 | 9 | 2[160] | 3 | 160 |
| 2 | 9[120] | 10[+] | 14 | 13[20][-] | 140 |
| 3 | 11 | 4[150][-] | 5[20][+] | 8 | 170 |
| 4 | 0 | 0 | 0[10][-] | 0[90][+] | 100 |
| Потребности | 120 | 150 | 190 | 110 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 8 | 9 | 2[160] | 3 | 160 |
| A2 | 9[120] | 10[10] | 14 | 13[10] | 140 |
| A3 | 11 | 4[140] | 5[30] | 8 | 170 |
| A4 | 0 | 0 | 0 | 0[100] | 100 |
| Потребности | 120 | 150 | 190 | 110 |
u1 + v3 = 2; 0 + v3 = 2; v3 = 2
u3 + v3 = 5; 2 + u3 = 5; u3 = 3
u3 + v2 = 4; 3 + v2 = 4; v2 = 1
u2 + v2 = 10; 1 + u2 = 10; u2 = 9
u2 + v1 = 9; 9 + v1 = 9; v1 = 0
u2 + v4 = 13; 9 + v4 = 13; v4 = 4
u4 + v4 = 0; 4 + u4 = 0; u4 = -4
| v1=0 | v2=1 | v3=2 | v4=4 | |
| u1=0 | 8 | 9 | 2[160] | 3 |
| u2=9 | 9[120] | 10[10] | 14 | 13[10] |
| u3=3 | 11 | 4[140] | 5[30] | 8 |
| u4=-4 | 0 | 0 | 0 | 0[100] |
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
S14 =3-(4+0)=-1
Выбираем максимальную оценку свободной клетки (1;4): 3
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 8 | 9 | 2[160][-] | 3[+] | 160 |
| 2 | 9[120] | 10[10][+] | 14 | 13[10][-] | 140 |
| 3 | 11 | 4[140][-] | 5[30][+] | 8 | 170 |
| 4 | 0 | 0 | 0 | 0[100] | 100 |
| Потребности | 120 | 150 | 190 | 110 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 8 | 9 | 2[150] | 3[10] | 160 |
| A2 | 9[120] | 10[20] | 14 | 13 | 140 |
| A3 | 11 | 4[130] | 5[40] | 8 | 170 |
| A4 | 0 | 0 | 0 | 0[100] | 100 |
| Потребности | 120 | 150 | 190 | 110 |
u1 + v3 = 2; 0 + v3 = 2; v3 = 2
u3 + v3 = 5; 2 + u3 = 5; u3 = 3
u3 + v2 = 4; 3 + v2 = 4; v2 = 1
u2 + v2 = 10; 1 + u2 = 10; u2 = 9
u2 + v1 = 9; 9 + v1 = 9; v1 = 0
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
u4 + v4 = 0; 3 + u4 = 0; u4 = -3
| v1=0 | v2=1 | v3=2 | v4=3 | |
| u1=0 | 8 | 9 | 2[150] | 3[10] |
| u2=9 | 9[120] | 10[20] | 14 | 13 |
| u3=3 | 11 | 4[130] | 5[40] | 8 |
| u4=-3 | 0 | 0 | 0 | 0[100] |
Опорный план является оптимальным, так все оценки свободных клеток положительные.
Этому плану соответствуют минимальные суммарные затраты:
F(x) = 2*150 + 3*10 + 9*120 + 10*20 + 4*130 + 5*40 + 0*100 = 2330
По этому плану перевозок завод А1 должен 150 ед. продукции доставить на склад В3 и 10 ед. продукции доставить на склад В4; завод А2 должен 120 ед. продукции доставить на склад В1 и 20 ед. продукции доставить на склад В2; завод А3 должен 130 ед. продукции доставить на склад В2 и 40 ед. продукции доставить на склад В3. При этом суммарные затраты будут минимальными и составят 2330 ден. ед.
Продукция в объёме 100 ед. останется на складе В3.
2) Решим данную задачу транспортного типа методом потенциалов при дополнительном условии, что склад В2 должен быть загружен полностью либо продукция А2 должна быть полностью распределена. Поскольку из последней таблицы видим, что продукция В2 не осталась на складе, то можно сделать вывод о том, что задача решена в полном объёме в пункте 1.
3) Найдём оптимальный план перевозки готовой продукции на склады при дополнительном условии, что из пункта отправления А2 в пункт назначения В3 должно быть перевезено не менее 60 ед. продукции, а из пункта отправления А3 в пункт назначения В4 должно быть перевезено не более 100 ед. продукции.
Условие для пункта отправления А3 выполняется, так как из него в пункт назначения В4 не вывезено ни одной единицы продукции (см. решение задачи в п.1).
Потребуем выполнения условия «из пункта отправления А2 в пункт назначения В3 должно быть перевезено не менее 60 ед. продукции».
В начальном плане уменьшим стоимость доставки из пункта отправления А2 в пункт назначения В3 с 14-ти до 3-х единиц и решим заданную задачу.
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 8 | 9 | 2[160] | 3 | 160 |
| A2 | 9[20] | 10 | 3[30] | 13[90] | 140 |
| A3 | 11 | 4[150] | 5 | 8[20] | 170 |
| A4 | 0[100] | 0 | 0 | 0 | 100 |
| Потребности | 120 | 150 | 190 | 110 |
m + n - 1 = 7. Следовательно, опорный план является невырожденным.
u1 + v3 = 2; 0 + v3 = 2; v3 = 2
u2 + v3 = 3; 2 + u2 = 3; u2 = 1
u2 + v1 = 9; 1 + v1 = 9; v1 = 8
u4 + v1 = 0; 8 + u4 = 0; u4 = -8
u2 + v4 = 13; 1 + v4 = 13; v4 = 12
u3 + v4 = 8; 12 + u3 = 8; u3 = -4
u3 + v2 = 4; -4 + v2 = 4; v2 = 8
| v1=8 | v2=8 | v3=2 | v4=12 | |
| u1=0 | 8 | 9 | 2[160] | 3 |
| u2=1 | 9[20] | 10 | 3[30] | 13[90] |
| u3=-4 | 11 | 4[150] | 5 | 8[20] |
| u4=-8 | 0[100] | 0 | 0 | 0 |
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
S14 = - 9
S44 = - 4
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 8 | 9 | 2[160][-] | 3[+] | 160 |
| 2 | 9[20] | 10 | 3[30][+] | 13[90][-] | 140 |
| 3 | 11 | 4[150] | 5 | 8[20] | 170 |
| 4 | 0[100] | 0 | 0 | 0 | 100 |
| Потребности | 120 | 150 | 190 | 110 |
В результате получим новый опорный план.
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 8 | 9 | 2[70] | 3[90] | 160 |
| A2 | 9[20] | 10 | 3[120] | 13 | 140 |
| A3 | 11 | 4[150] | 5 | 8[20] | 170 |
| A4 | 0[100] | 0 | 0 | 0 | 100 |
| Потребности | 120 | 150 | 190 | 110 |
u1 + v3 = 2; 0 + v3 = 2; v3 = 2
u2 + v3 = 3; 2 + u2 = 3; u2 = 1
u2 + v1 = 9; 1 + v1 = 9; v1 = 8
u4 + v1 = 0; 8 + u4 = 0; u4 = -8
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
u3 + v4 = 8; 3 + u3 = 8; u3 = 5
u3 + v2 = 4; 5 + v2 = 4; v2 = -1
| v1=8 | v2=-1 | v3=2 | v4=3 | |
| u1=0 | 8 | 9 | 2[70] | 3[90] |
| u2=1 | 9[20] | 10 | 3[120] | 13 |
| u3=5 | 11 | 4[150] | 5 | 8[20] |
| u4=-8 | 0[100] | 0 | 0 | 0 |
S31 = - 2
S33 = - 2
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 8 | 9 | 2[70][-] | 3[90][+] | 160 |
| 2 | 9[20][-] | 10 | 3[120][+] | 13 | 140 |
| 3 | 11[+] | 4[150] | 5 | 8[20][-] | 170 |
| 4 | 0[100] | 0 | 0 | 0 | 100 |
| Потребности | 120 | 150 | 190 | 110 |
В результате получим новый опорный план.
| B1 | B2 | B3 | B4 | Запасы | |
| A1 | 8 | 9 | 2[50] | 3[110] | 160 |
| A2 | 9[0] | 10 | 3[140] | 13 | 140 |
| A3 | 11[20] | 4[150] | 5 | 8 | 170 |
| A4 | 0[100] | 0 | 0 | 0 | 100 |
| Потребности | 120 | 150 | 190 | 110 |
u1 + v3 = 2; 0 + v3 = 2; v3 = 2
u2 + v3 = 3; 2 + u2 = 3; u2 = 1
u2 + v1 = 9; 1 + v1 = 9; v1 = 8
u3 + v1 = 11; 8 + u3 = 11; u3 = 3
u3 + v2 = 4; 3 + v2 = 4; v2 = 1
u4 + v1 = 0; 8 + u4 = 0; u4 = -8
u1 + v4 = 3; 0 + v4 = 3; v4 = 3
| v1=8 | v2=1 | v3=2 | v4=3 | |
| u1=0 | 8 | 9 | 2[50] | 3[110] |
| u2=1 | 9[0] | 10 | 3[140] | 13 |
| u3=3 | 11[20] | 4[150] | 5 | 8 |
| u4=-8 | 0[100] | 0 | 0 | 0 |
Опорный план является оптимальным, так все оценки свободных клеток положительные.
Вернувшись к исхдной стоимости доставки в 14 единиц, посчитаем затраты.
F(x) = 2*50 + 3*110 + 14*140 + 11*20 + 4*150 + 0*100 = 3210
