1 Построение допустимого плана транспортной задачи
Составить допустимые планы транспортной задачи, используя следующие методы построения базисного плана:
минимальной стоимости;
минимальной стоимость по строкам (столбцам);
двойного предпочтения;
северо-западного угла;
Мюллера-Мербаха;
Модифицированного метода Мюллера-Мербаха;
Фогеля.
Рассчитать целевые функции каждого базисного плана перевозок.
Построить гистограмму найденные значений целевых функций и проанализировать результаты.
Исходные данные приведены в таблице.
Поставщики Потребители Запасы
B1 B2 B3 B4 B5 B6
A1 5 4 12 9 8 16 120
A2 8 3 5 11 6 8 170
A3 9 10 3 1 12 7 130
A4 12 8 6 2 5 4 130
A5 1 7 11 6 9 9 130
Потребности 140 137 119 37 151 116
Решение:
Проверим баланс задачи:
ai=120+170+130+130+130=680
bj=140+137+119+37+151+116=700
Так как ai<bj, добавляем фиктивного поставщика с запасом 20 единиц и нулевыми стоимостями перевозок.
Поставщики Потребители Запасы
B1 B2 B3 B4 B5 B6
A1 5 4 12 9 8 16 120
A2 8 3 5 11 6 8 170
A3 9 10 3 1 12 7 130
A4 12 8 6 2 5 4 130
A5 1 7 11 6 9 9 130
A6 0 0 0 0 0 0 20
Потребности 140 137 119 37 151 116
Построим план методом минимальной стоимости.
В ячейки минимальной стоимости (A5B1 и A3B4) помещаем максимально возможное перемещение min(130;140)=130 и min(130;37)=37. При этом потребности потребителя B4 удовлетворены полностью, у потребителя B1 остается потребность еще в 10 единицах, у поставщика A3 остается еще 93 единица запаса, а запасы поставщика A5 исчерпаны полностью. Из дальнейшего построения вычеркиваем четвертый столбец и пятую строку.
Из оставшихся в ячейки минимальной стоимости (A2B2 и A3B3) помещаем максимально возможное перемещение min(170;137)=137 и min(93;119)=93. При этом потребности потребителя B2 удовлетворены полностью, у потребителя B3 остается потребность еще в 26 единицах, у поставщика A2 остается еще 33 единица запаса, а запасы поставщика A3 исчерпаны полностью. Из дальнейшего построения вычеркиваем второй столбец и третью строку.
Из оставшихся в ячейку минимальной стоимости (A4B6) помещаем максимально возможное перемещение min(130;116)=116. При этом потребности потребителя B6 удовлетворены полностью, а у поставщика A4 остается еще 14 единиц запаса. Из дальнейшего построения вычеркиваем шестой столбец.
Из оставшихся в ячейки минимальной стоимости (A1B1, A2B3 и A4B5) помещаем максимально возможное перемещение min(120;10)=10, min(33;26)=26 и min(14;151)=14. При этом потребности потребителей B1 и B3 удовлетворены полностью, у потребителя B5 остается потребность еще в 137 единицах, у поставщиков A1 и A2 остается еще 110 и 7 единица запаса соответственно, а запасы поставщика A4 исчерпаны полностью. Из дальнейшего построения вычеркиваем первый и третий столбцы и четвертую строку.
В оставшиеся ячейки (A1B5, A2B5 и A6B5) помещаем оставшиеся ресурсы в размерах 110, 7 и 20 единиц соответственно. Получаем план:
Поставщики Потребители Запасы
B1 B2 B3 B4 B5 B6
A1 5
10 4 12 9 8
110 16 120
A2 8 3
137 5
26 11 6
7 8 170
A3 9 10 3
93 1
37 12 7 130
A4 12 8 6 2 5
14 4
116 130
A5 1
130 7 11 6 9 9 130
A6 0 0 0 0 0
20 0 20
Потребности 140 137 119 37 151 116
Определим стоимость перевозки (значение целевой функции):
F=5∙10+8∙110+3∙137+5∙26+6∙7+3∙93+1∙37+5∙14+4∙116+1∙130+0∙20=2493
Построим план методом минимальной стоимость по строкам.
Рассмотрим поставщика A1. Наименьшую стоимость имеет перемещение в пункт B2, при этом перемещаем максимально возможный груз min(120;137)=120. У потребителя B2 остается потребность в 17 единицах груза.
Рассмотрим поставщика A2. Наименьшую стоимость имеет перемещение в пункт B2, при этом перемещаем максимально возможный груз min(170;17)=17. Убираем из дальнейших расчетов потребителя B2. Следующий по стоимости потребитель B3, которому перемещаем максимально возможный груз min(153;119)=119. Убираем из дальнейших расчетов потребителя B3. Следующий по стоимости потребитель B5, которому перемещаем максимально возможный груз min(34;151)=34. У потребителя B5 остается потребность в 117 единицах груза.
Рассмотрим поставщика A3. Наименьшую стоимость из оставшихся имеет перемещение в пункт B4, при этом перемещаем максимально возможный груз min(120;37)=37. Убираем из дальнейших расчетов потребителя B4. Следующий по стоимости потребитель B6, которому перемещаем оставшиеся запасы в размере 93 единиц. У потребителя B6 остается потребность в 23 единицах груза.
Рассмотрим поставщика A4. Наименьшую стоимость из оставшихся имеет перемещение в пункт B6, при этом перемещаем максимально возможный груз min(130;23)=23. Убираем из дальнейших расчетов потребителя B6. Следующий по стоимости потребитель B5, которому перемещаем максимально возможный груз min(117;107)=107.
Рассмотрим поставщика A5. Наименьшую стоимость из оставшихся имеет перемещение в пункт B1, при этом перемещаем максимально возможный груз min(130;140)=130.
Оставшийся груз распределяем в ячейках A6B1 и A6B5. Получаем план:
Поставщики Потребители Запасы
B1 B2 B3 B4 B5 B6
A1 5
4
120 12 9 8
16 120
A2 8 3
17 5
119 11 6
34 8 170
A3 9 10 3
1
37 12 7
93 130
A4 12 8 6 2 5
107 4
23 130
A5 1
130 7 11 6 9 9 130
A6 0
10 0 0 0 0
10 0 20
Потребности 140 137 119 37 151 116
Определим стоимость перевозки (значение целевой функции):
F = 4∙120+3∙17+5∙119+6∙34+1∙37+7∙93+5∙107+4∙23+1∙130=2775
Рассуждая аналогично, строим план по столбцам:
Поставщики Потребители Запасы
B1 B2 B3 B4 B5 B6
A1 5
10 4 12 9 8
14 16
96 120
A2 8 3
137 5
11 6
33 8 170
A3 9 10 3
119 1
11 12 7 130
A4 12 8 6 2
26 5
104 4
130
A5 1
130 7 11 6 9 9 130
A6 0 0 0 0 0
0
20 20
Потребности 140 137 119 37 151 116
Определим стоимость перевозки (значение целевой функции):
F=5∙10+8∙14+16∙96+3∙137+6∙33+3∙119+1∙11+2∙26+5∙104+1∙130=3377
Построим план методом двойного предпочтения.
Находим минимальные значения по строкам: A1B2, A2B2, A3B4, A4B4, A5B1. Помечаем их знаком «+».
Аналогично находим минимальные значения по столбцам: A5B1, A2B2, A3B3, A3B4, A2B5, A4B6. Помечаем их также знаком «+».
В ячейки A2B2, A3B4, A5B1 с двумя пометками помещаем максимально возможные перемещения min(170;137)=137, min(130;37)=37 и min(130;140)=130.
Далее помещаем в ячейки A3B3, A4B6, A4B6 с одной пометкой помещаем максимально возможные перемещения min(93;119)=93, min(130;116)=116 и min(14;151)=14.
Далее повторяем процедуру для ячеек без пометок из доступных A1B1, A1B3, A1B5, A1B6, A2B1, A2B3, A2B5, A2B6. Получаем две ячейки с двумя пометками A1B1 и A2B3, в которые помещаем максимально возможное перемещение min(120;10)=10 и min(33;26)=26.
В оставшиеся ячейки (A1B3 и A1B6) помещаем оставшиеся ресурсы в размерах 17 и 113 единиц соответственно. Получаем план:
Поставщики Потребители Запасы
B1 B2 B3 B4 B5 B6
A1 ** 5
10 + 4 12 * 9 8
110 16 120
A2 8 ++ 3
137 ** 5
26 11 * 6
7 * 8 170
A3 9 10 + 3
93 ++ 1
37 12 7 130
A4 12 8 6 + 2 + 5
14 + 4
116 130
A5 ++ 1
130 7 11 6 9 9 130
A6 0 0 0 0 0
20 0 20
Потребности 140 137 119 37 151 116
Определим стоимость перевозки (значение целевой функции):
F = 5∙10+8∙110+3∙137+5∙26+6∙7+3∙93+1∙37+5∙14+4∙116+1∙130=2493
Построим план методом северо-западного угла.
В ячейку A1B1 помещаем максимально возможное перемещение min(120;140)=120. Запасы поставщика A1 исчерпаны полностью, а у потребителя B1 остается потребность в 7 единицах. Из дальнейшего построения вычеркиваем первую строку и переходим к ячейке A2B1.
В ячейку A2B1 помещаем максимально возможное перемещение min(120;7)=7. Потребности потребителя A1 исчерпаны полностью, а у потребителя B1 остается потребность в 7 единицах. Из дальнейшего построения вычеркиваем первую строку и переходим к ячейке A2B1.
Поставщики Потребители Запасы
B1 B2 B3 B4 B5 B6
A1 5
4 12 9 8
16 120
A2 8 3
5
11 6
8 170
A3 9 10 3
1
12 7 130
A4 12 8 6 2 5
4
130
A5 1
7 11 6 9 9 130
A6 0 0 0 0 0
0 20
Потребности 140 137 119 37 151 116
Определим стоимость перевозки (значение целевой функции):
F=8∙3+16∙127+3∙119+6∙1+3∙37+1∙133+2∙18+5∙112+9∙13=3513
Мюллера-Мербаха;
Поставщики Потребители Запасы
B1 B2 B3 B4 B5 B6
A1 5
4 12 9 8
16 120
A2 8 3
5
11 6
8 170
A3 9 10 3
1
12 7 130
A4 12 8 6 2 5
4
130
A5 1
7 11 6 9 9 130
A6 0 0 0 0 0
0 20
Потребности 140 137 119 37 151 116
Определим стоимость перевозки (значение целевой функции):
F=8∙3+16∙127+3∙119+6∙1+3∙37+1∙133+2∙18+5∙112+9∙13=3513
Модифицированного метода Мюллера-Мербаха;
Поставщики Потребители Запасы
B1 B2 B3 B4 B5 B6
A1 5
4 12 9 8
16 120
A2 8 3
5
11 6
8 170
A3 9 10 3
1
12 7 130
A4 12 8 6 2 5
4
130
A5 1
7 11 6 9 9 130
A6 0 0 0 0 0
0 20
Потребности 140 137 119 37 151 116
Определим стоимость перевозки (значение целевой функции):
F=8∙3+16∙127+3∙119+6∙1+3∙37+1∙133+2∙18+5∙112+9∙13=3513
Фогеля.
Поставщики Потребители Запасы
B1 B2 B3 B4 B5 B6
A1 5
4 12 9 8
16 120
A2 8 3
5
11 6
8 170
A3 9 10 3
1
12 7 130
A4 12 8 6 2 5
4
130
A5 1
7 11 6 9 9 130
A6 0 0 0 0 0
0 20
Потребности 140 137 119 37 151 116
Определим стоимость перевозки (значение целевой функции):
F=8∙3+16∙127+3∙119+6∙1+3∙37+1∙133+2∙18+5∙112+9∙13=3513
