2015-08-21
419
Пример 2. В открытой транспортной задаче запасы поставщиков не равны потребностям потребителей (таблица 13).
Таблица 13
| Поставщики | Потребители | Запасы | ||
| В1 | В2 | В3 | ||
| А1 | 9 х11 | 5 х12 | 4 х13 | |
| А2 | 7 х21 | 8 х22 | 5 х23 | |
| А3 | 3 х31 | 4 х32 | 6 х33 | |
| Спрос |
Построим математическую модель задачи:
,
,
.
Вводим фиктивного поставщика с запасом 10 и нулевыми затратами на перевоз. Опорный план можно составить методом северо-западного угла или методом минимальной стоимости (таблица 14). Заполнение таблицы начинается с ячеек с наименьшей стоимостью перевозки.
Функция стоимости перевозок:
F1 = 4*25+ 8*35+ 5*15+ 3*15+ 4*35 = 640.
Таблица 14
| Потребители | Запасы | |||||
| В1 | В2 | В3 | ||||
| Поставщики | А1 | 9 |  5
+
| 4 -25 | u1 =0 | |
| А2 | 7 | 8 - | + 5 15 | u2 =1 | ||
| А3 | 3 | 4 | 6 | u3 =-3 | ||
| A4 | 0 | 0 | 0 | u4 =-6 | ||
| Спрос | ||||||
| v1 =6 | v2 =7 | v3 =4 |
Для оптимизации плана используем метод потенциалов. Составляем уравнение потенциалов для занятых ячеек
|
|
|
| u1 +v3 = 4; u2 +v2 = 8; u2 +v3 = 5; u3 +v1 = 3; u3 +v2 = 4; u4 +v1 = 0; |  u1 = 0;
u2 = 1;
u3 = -3;
u4 = -6;
| v1 = 6; v2 = 7; v3 = 4. |
Проверяем условие оптимальности для свободных ячеек:
u1 +v1 = 6 < 9;
u1 +v2 = 7 >5;
u2 +v1 = 7 = 7;
u3 +v3 = 1 < 6;
u4 +v2 = 1 >0;
u4 +v3 = -2 < 0.
Для ячеек x12 и x42 условие оптимальности не выполняется. Для ячейки x12, строим цикл [ х12, х13, х23, х22 ]. Находим значения потенциалов.
| u1 +v2 = 5; u2 +v2 = 8; u2 +v3 = 5; u3 +v1 = 3; u3 +v2 = 4; u4 +v1 = 0; |  u1 = 0;
u2 = 3;
u3 = -1;
u4 = -4;
| v1 = 4; v2 = 5; v3 = 2. |
Получаем новый план:
Таблица 15
| 9 | 5 | 4 | u1 =0 |
| 7 | 8 | 5 40 | u2 =3 |
3
 15 +
| 4 -35 | 6 | u3 =-1 |
| 0 - | + 0 | 0 | u4 =-4 |
| v1 =4 | v2 =5 | v3 =2 |
Проверяем условие оптимальности для свободных ячеек:
u1 +v1 = 4 < 9;
u1 +v3 = 2 < 4;
u2 +v1 = 7 = 7;
u3 +v3 = 1 < 6;
u4 +v2 = 1 >0;
u4 +v3 = -2 < 0.
Для ячейки u4,v2 условие оптимальности не выполняется. Для ячейки x42, строим цикл [ х31, х32, х42, х41 ]. Находим значения потенциалов.
| u1 +v2 = 5; u2 +v2 = 8; u2 +v3 = 5; u3 +v1 = 3; u3 +v2 = 4; u4 +v2 = 0; | u1 = 0;
u2 = 3;
u3 = -1;
u4 = -5;
| v1 = 4; v2 = 5; v3 = 2. |
Получаем новый план:
Таблица 16
| 9 | 5 | 4 | u1 =0 |
| 7 | 8 | 5 40 | u2 =3 |
| 3 | 4 | 6 | u3 =-1 |
| 0 | 0 10 | 0 | u4 =-5 |
| v1 =4 | v2 =5 | v3 =2 |
Проверяем условие оптимальности для свободных ячеек:
u1 +v1 = 4 < 9;
u1 +v3 = 2 < 4;
u2 +v1 = 7 = 7;
u3 +v3 = 1 < 6;
u4 +v1 = -1 <0;
u4 +v3 = -3 < 0.
Для всех клеток условие оптимальности выполняется, следовательно, полученный план является оптимальным.
F = 5*25 +8*10 +5*40 +3*25 +4*35 +0*10 = 620.
При реализации оптимального плана потребитель В2 останется недозагруженным на 10 единиц.
