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

  • 01 сент. 2011 г.
  • 1968 Слова
Лабораторная работа №5

Тема: Транспортная задача
Вариант №17

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
| 1| 2| 3| 4| Запасы|
1| 8| 7| 6| 7| 110|
2| 9| 6| 8| 6| 220|
3| 6| 8| 7| 8| 330|
4| 8| 6| 7| 6| 440|
Потреб.| 340| 270| 160| 750| |
Проверим необходимое и достаточное условие разрешимостизадачи.
∑ a = 110 + 220 + 330 + 440 = 1100
∑ b = 340 + 270 + 160 + 750 = 1520
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равным 420. Тарифы перевозки единицы груза из базы во все магазины, полагаем, равнынулю.
Занесем исходные данные в распределительную таблицу.
| 1| 2| 3| 4| Запасы|
1| 8| 7| 6| 7| 110|
2| 9| 6| 8| 6| 220|
3| 6| 8| 7| 8| 330|
4| 8| 6| 7| 6| 440|
5| 0| 0| 0| 0| 420|
Потреб.| 340| 270| 160| 750| |
1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
| 1| 2| 3| 4| Запасы|
1| 8[110]| 7| 6| 7| 110|
2| 9[220]| 6| 8| 6| 220|3| 6[10]| 8[270]| 7[50]| 8| 330|
4| 8| 6| 7[110]| 6[330]| 440|
5| 0| 0| 0| 0[420]| 420|
Потреб.| 340| 270| 160| 750| |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m +n - 1 = 8. Следовательно, опорный план является невырожденным.
3. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
| v1=8| v2=10| v3=9| v4=8|
u1=0| 8[110]| 7| 6| 7|
u2=1| 9[220]| 6| 8| 6|
u3=-2| 6[10]| 8[270]| 7[50]| 8|
u4=-2| 8| 6| 7[110]| 6[330]|
u5=-8| 0| 0| 0| 0[420]|
Опорный план неявляется оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(1;2): 0 + 10 > 7
(1;3): 0 + 9 > 6
(1;4): 0 + 8 > 7
(2;2): 1 + 10 > 6
(2;3): 1 + 9 > 8
(2;4): 1 + 8 > 6
(4;2): -2 + 10 > 6
(5;2): -8 + 10 > 0
(5;3): -8 + 9 > 0
Выбираем максимальную оценку свободной клетки (2;2): 6
Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинахмногоугольника чередующиеся знаки «-», «+», «-».
| 1| 2| 3| 4| Запасы|
1| 8[110]| 7| 6| 7| 110|
2| 9[220][-]| 6[+]| 8| 6| 220|
3| 6[10][+]| 8[270][-]| 7[50]| 8| 330|
4| 8| 6| 7[110]| 6[330]| 440|
5| 0| 0| 0| 0[420]| 420|
Потреб.| 340| 270| 160| 750| |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 220. Прибавляем 220 к объемам грузов, стоящихв плюсовых клетках и вычитаем 220 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1| 2| 3| 4| Запасы|
1| 8[110]| 7| 6| 7| 110|
2| 9| 6[220]| 8| 6| 220|
3| 6[230]| 8[50]| 7[50]| 8| 330|
4| 8| 6| 7[110]| 6[330]| 440|
5| 0| 0| 0| 0[420]| 420|
Потреб.| 340| 270| 160| 750| |
3. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятымклеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
| v1=8| v2=10| v3=9| v4=8|
u1=0| 8[110]| 7| 6| 7|
u2=-4| 9| 6[220]| 8| 6|
u3=-2| 6[230]| 8[50]| 7[50]| 8|
u4=-2| 8| 6| 7[110]| 6[330]|
u5=-8| 0| 0| 0| 0[420]|
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(1;2): 0 + 10 > 7
(1;3): 0 + 9 > 6
(1;4): 0 + 8 > 7(4;2): -2 + 10 > 6
(5;2): -8 + 10 > 0
(5;3): -8 + 9 > 0
Выбираем максимальную оценку свободной клетки (1;2): 7
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1| 2| 3| 4| Запасы|
1| 8[110][-]| 7[+]| 6| 7| 110|
2| 9| 6[220]| 8| 6| 220|
3| 6[230][+]| 8[50][-]| 7[50]| 8| 330|
4| 8|...
tracking img