Читайте также:
|
|
Пример 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 | ![]() | 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; | ![]() | 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; | ![]() | v1 = 4; v2 = 5; v3 = 2. |
Получаем новый план:
Таблица 15
9 | 5 | 4 | u1 =0 |
7 | 8 | 5 40 | u2 =3 |
3
![]() | 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; | ![]() | 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 единиц.
Дата добавления: 2015-10-13; просмотров: 57 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Закрытая транспортная задача | | | Решение стандартных транспортных задач в Excel |