--PAGE_BREAK--
6. Решить транспортную задачу.
Транспортная таблица имеет вид:
Запасы
20
13
8
11
70
15
9
17
18
70
21
19
15
13
110
Заявки
70
90
70
60
Решение.
Найдём общую сумму запасов: = 70 + 70 + 110 = 250.
Найдём общую сумму заявок: =70 + 90 + 70 + 60 = 290.
В нашем случае запасы поставщиков ( 250 единиц продукции ) меньше, чем потребность потребителей ( 290 единиц продукции ) на 40 единиц. Введем в рассмотрение фиктивного поставщика с запасом продукции, равным 40. Стоимость доставки единицы продукции от данного поставщика ко всем потребителям примем равной нулю.
Запасы
20
13
8
11
70
15
9
17
18
70
21
19
15
13
110
0
0
0
0
40
Заявки
70
90
70
60
Решение транспортной задачи начнем с построения допустимого базисного плана, для этого воспользуемся методом северо-западного угла.
Рассмотрим ячейку таблицы. Запасы поставщика составляют 70 единиц продукции, заявки потребителя составляет 70. Разместим в ячейку значение, равное min { 70, 70 } = 70, т.е. мы полностью израсходoвали запасы поставщика. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения. В то же время мы полностью удовлетворили потребность потребителя, но будем считать, что потребность данного потребителя составляют 0 единиц продукции (не будем одновременно вычеркивать строку и столбец).
Рассмотрим ячейку.Запасы поставщика составляют 70 единиц продукции. Потребность потребителя составляет 0. Разместим в ячейку значение, равное min { 70, 0 } = 0, т.е. мы полностью удовлетворили потребность потребителя. Поэтому исключаем 1ый столбец таблицы из дальнейшего рассмотрения.
Рассмотрим ячейку.Запасы поставщика составляют 70 единиц продукции. Потребность потребителя составляет 90. Разместим в ячейку значение, равное min { 70, 90 } = 70, т.е. мы полностью израсходoвали запасы поставщика. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Рассмотрим ячейку.Запасы поставщика составляют 110 единиц продукции. Потребность потребителя составляет 90 – 70 = 20. Разместим в ячейку значение, равное min { 110, 20 } = 20, т.е. мы полностью удовлетворили запросы потребителя. Поэтому исключаем 2ой столбец таблицы из дальнейшего рассмотрения.
Рассмотрим ячейку.Запасы поставщика составляют 110 – 20 = 90 единиц продукции. Потребность потребителя составляет 70. Разместим в ячейку значение, равное min { 90, 70 } = 70, т.е. мы полностью удовлетворили запросы потребителя. Поэтому исключаем 3ий столбец таблицы из дальнейшего рассмотрения.
Рассмотрим ячейку. Запасы поставщика составляют 90 – 70 = 20 единиц продукции. Потребность потребителя составляет 60. Разместим в ячейку значение, равное min { 20, 60 } = 20, т.е. мы полностью израсходoвали запасы поставщика. Поэтому исключаем 3ью строку таблицы из дальнейшего рассмотрения.
Рассмотрим ячейку. Запасы поставщика составляют 40 единиц продукции. Потребность потребителя составляет 60 – 20 = 40. Разместим в ячейку значение, равное min { 40, 40 } = 40, т.е. мы полностью израсходoвали запасы поставщика. Поэтому исключаем 4ую строку таблицы из дальнейшего рассмотрения. В то же время мы полностью удовлетворили запросы потребителя .
Мы нашли начальное опорное решение, т.е. израсходовали все запасы поставщиков и удовлетворили все заявки потребителей. Занесем полученные значения в таблицу:
Запасы
20
70
13
8
11
70
15
0
9
70
17
18
70
21
19
20
15
70
13
20
110
0
0
0
0
40
40
Заявки
70
90
70
60
Теперь, произведем его оценку. Общие затраты на доставку всей продукции, для данного решения, составляют
= 2070 + 15 0 + 9 70 + 19 20 + 15 70 + 13 20 + 0 40 = 3720 единиц.
Найдем потенциалы поставщиков и потребителей. Примем = 0. Тогда :
= — = 19 — 0 = 19
= — = 15 — 0 = 15
= — = 13 — 0 = 13
= — = 0 — 13 = -13
= — = 9 — 19 = -10
= — = 15 – ( -10 ) = 25
= — = 20 — 25 = -5
Запасы
Потенциалы
20
70
13
8
11
70
-5
15
0
9
70
17
18
70
-10
21
19
20
15
70
13
20
110
0
0
0
0
0
40
40
-13
Заявки
70
90
70
60
Потенциалы
25
19
15
13
Найдем оценки свободных ячеек следующим образом :
= — ( + ) = 13 — ( -5 + 19 ) = -1
= — ( + ) = 8 — ( -5 + 15 ) = -2
= — ( + ) = 11 — ( -5 + 13 ) = 3
= — ( + ) = 17 — ( -10 + 15 ) = 12
= — ( + ) = 18 — ( -10 + 13 ) = 15
= — ( + ) = 21 — ( 0 + 25 ) = -4
= — ( + ) = 0 — ( -13 + 25 ) = -12
= — ( + ) = 0 — ( -13 + 19 ) = -6
= — ( + ) = 0 — ( -13 + 15 ) = -2
Среди оценок есть отрицательные, следовательно, решение не оптимальное.
Из отрицательных оценок выбираем минимальную, она соответствует ячейке, ее оценка = -2.
Ячейки , ,,,, образуют цикл для свободной ячейки. Цикл начинается в этой свободной ячейке. Пусть ячейка имеет порядковый номер 1.
Среди ячеек цикла , , , номера которых четные, выберем ячейку, как обладающую наименьшим значением 70. От ячеек цикла с четными номерами, мы отнимаем 70. К ячейкам с нечетными номерами мы прибавляем 70. Ячейка выйдет из базиса, ячейка станет базисной.
Запасы
20
13
8
70
11
70
15
70
9
17
18
70
21
19
90
15
13
20
110
0
0
0
0
40
40
Заявки
70
90
70
60
продолжение
--PAGE_BREAK--