Решить транспортную задачу.
Транспортная таблица имеет вид:
Решение.
Найдём общую сумму запасов: = 70 + 70 + 110 = 250. Найдём общую сумму заявок: =70 + 90 + 70 + 60 = 290. В нашем случае запасы поставщиков ( 250 единиц продукции ) меньше, чем потребность потребителей ( 290 единиц продукции ) на 40 единиц. Введем в рассмотрение фиктивного поставщика с запасом продукции, равным 40. Стоимость доставки единицы продукции от данного поставщика ко всем потребителям примем равной нулю.
Решение транспортной задачи начнем с построения допустимого базисного плана, для этого воспользуемся методом северо-западного угла.
Рассмотрим ячейку таблицы. Запасы поставщика составляют 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 + 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
Найдем оценки свободных ячеек следующим образом :
= - ( + ) = 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. Ячейка выйдет из базиса, ячейка станет базисной.
Общие затраты на доставку всей продукции, для данного решения , составляют = 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 - ( -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. Ячейка выйдет из базиса, ячейка станет базисной.
Общие затраты на доставку всей продукции, для данного решения , составляют = 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 - ( -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. Ячейка выйдет из базиса, ячейка станет базисной.
Общие затраты на доставку всей продукции, для данного решения , составляют = 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
2020-02-03 |
197 |
Обсуждений (0) |
|
5.00
из
|
|
Обсуждение в статье: Решить транспортную задачу. |
Обсуждений еще не было, будьте первым... ↓↓↓ |
Почему 1285321 студент выбрали МегаОбучалку...
Система поиска информации
Мобильная версия сайта
Удобная навигация
Нет шокирующей рекламы