Решить транспортную задачу.

       Транспортная таблица имеет вид:

 

					Запасы
	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

 

 

Теперь, произведем его оценку. Общие затраты на доставку всей продукции, для данного решения , составляют

 = 20 70 + 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

 

 

Общие затраты на доставку всей продукции, для данного решения , составляют

 = 8 70 + 15 70 + 19 90 + 13 20 + 0 40  = 3580 единиц.

 

Найдем потенциалы поставщиков  и потребителей . Примем  = 0. Тогда :

=  -  = 19 - 0 = 19

=  -  = 15 - 0 = 15

=  -  = 13 - 0 = 13

=  -  = 0 - 13 = -13

=  -  = 8 - 15 = -7

=  -  = 9 - 19 = -10

=  -  = 15 – ( -10 ) = 25

 

					Запасы	Потенциалы
	20	13	8 70	11	70	-7
	15 70	9	17	18	70	-10
	21	19 90	15	13 20	110	0
	0	0	0	0 40	40	-13
Заявки	70	90	70	60
Потенциалы	25	19	15	13

 

Найдем оценки свободных ячеек следующим образом :

 =  - (  +  ) = 20 - ( -7 + 25 ) = 2

 =  - (  +  ) = 13 - ( -7 + 19 ) = 1

 =  - (  +  ) = 11 - ( -7 + 13 ) = 5

 =  - (  +  ) = 17 - ( -10 + 15 ) = 12

 =  - (  +  ) = 18 - ( -10 + 13 ) = 15

 =  - (  +  ) = 21 - ( 0 + 25 ) = -4

 =  - (  +  ) = 0 - ( -13 + 25 ) = -12

 =  - (  +  ) = 0 - ( -13 + 19 ) = -6

 

Среди оценок есть отрицательные, следовательно, решение не оптимальное.

Из отрицательных оценок выбираем минимальную, она соответствует ячейке , ее оценка  = -12.

Ячейки ,  ,  ,  , ,  образуют цикл для свободной ячейки . Цикл начинается в этой свободной ячейке. Пусть ячейка  имеет порядковый номер 1.

 Среди ячеек цикла  ,  , , номера которых четные , выберем ячейку , как обладающую наименьшим значением 40. От ячеек цикла с четными номерами, мы отнимаем 40. К ячейкам с нечетными номерами мы прибавляем 40.   Ячейка  выйдет из базиса, ячейка  станет базисной.

 

					Запасы
	20	13	8 70	11	70
	15 30	9 40	17	18	70
	21	19 50	15	13 60	110
	0 40	0	0	0	40
Заявки	70	90	70	60

 

 

 

 

Общие затраты на доставку всей продукции, для данного решения , составляют

 = 8 70 + 15 30 + 9 40 + 19 50 + 13 60 + 0 40 = 3100 единиц.

 

Найдем потенциалы поставщиков  и потребителей . Примем  = 0. Тогда :

=  -  = 19 - 0 = 19

=  -  = 15 - 0 = 15

=  -  = 13 - 0 = 13

=  -  = 8 - 15 = -7

=  -  = 9 - 19 = -10

=  -  = 15 – ( -10 ) = 25

=  -  = 0 - 25 = -25

 

 

					Запасы	Потенциалы
	20	13	8 70	11	70	-7
	15 30	9 40	17	18	70	-10
	21	19 50	15	13 60	110	0
	0 40	0	0	0 40	40	-25
Заявки	70	90	70	60
Потенциалы	25	19	15	13

 

Найдем оценки свободных ячеек следующим образом :

 =  - (  +  ) = 20 - ( -7 + 25 ) = 2

 =  - (  +  ) = 13 - ( -7 + 19 ) = 1

 =  - (  +  ) = 11 - ( -7 + 13 ) = 5

 =  - (  +  ) = 17 - ( -10 + 15 ) = 12

 =  - (  +  ) = 18 - ( -10 + 13 ) = 15

 =  - (  +  ) = 21 - ( 0 + 25 ) = -4

 =  - (  +  ) = 0 - ( -25 + 19 ) = 6

 =  - (  +  ) = 0 - ( -25 + 15 ) = 10

 =  - (  +  ) = 0 - ( -25 + 13 ) = 12

 

 

Среди оценок есть отрицательные, следовательно, решение не оптимальное.

Из отрицательных оценок выбираем минимальную, она соответствует ячейке , ее оценка  = -4. Ячейки , , , образуют цикл для свободной ячейки . Цикл начинается в этой свободной ячейке. Пусть ячейка  имеет порядковый номер 1.

Среди ячеек цикла  ,  ,номера которых четные , выберем ячейку , как обладающую наименьшим значением 30. От ячеек цикла с четными номерами, мы отнимаем 30. К ячейкам с нечетными номерами мы прибавляем 30.  Ячейка  выйдет из базиса, ячейка  станет базисной.

 

					Запасы
	20	13	8 70	11	70
	15	9 70	17	18	70
	21 30	19 20	15	13 60	110
	0 40	0	0	0	40
Заявки	70	90	70	60

 

 

Общие затраты на доставку всей продукции, для данного решения , составляют

 = 8 70 + 9 70 + 21 30 + 19 20 + 13 60 + 0 40 = 2980 единиц.

 

Найдем потенциалы поставщиков  и потребителей . Примем  = 0. Тогда :

=  -  = 21 – 0 = 21

=  -  = 19 - 0 = 19

=  -  = 15 - 0 = 15

=  -  = 13 - 0 = 13

=  -  = 0 - 21 = -21