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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ ВЫСШЕГО  ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ 

…

Кафедра «Математика и математическое моделирование» 
 
 
 

Лабораторная  работа

по дисциплине: Экономико-математические модели и методы в землеустройстве 

на тему: Транспортная задача 
 
 

Выполнила: …

                                                                                                   Проверила: …

                                                                                         Оценка:                  
 
 
 
 
 
 
 
 

Пенза 2011

     Задание (m=3, n=3)

     На  трех складах A₁ , A₂ и A₃ хранится a₁ =100, a₂=200 и a₃ = 60 + 10n единиц одного и того же груза. Этот груз требуется доставить трем потребителям B₁, B₂ и B₃, заказы которых составляют b₁ = 190, b₂ = 120 и b₃ = 10m единиц груза соответственно. Стоимость перевозок c_ij единицы груза с i-го склада j-му потребителю указаны в правых верхних углах соответствующих клеток транспортной таблицы:

     1. Сравнивая суммарный запас   и суммарную потребность  в  грузе, установить, является ли  модель транспортной задачи, заданная  этой таблицей, открытой или закрытой. Если модель является открытой, то ее необходимо закрыть, добавив  фиктивный склад A₄’ с запасом a₄’=b-a в случае a < b или фиктивного потребителя B₄’ с потребностью b₄’=a-b в случае a>b и положив соответствующие им тарифы перевозок нулевыми.

     2. Составить первоначальный план  перевозок. (Рекомендуется воспользоваться  методом наименьшей стоимости.)

     3. Проверить, является ли первоначальный  план оптимальным в смысле  суммарной стоимости перевозок,  и если это так, то составить оптимальный план, обеспечивающий минимальную стоимость перевозок. Найти эту стоимость.  
 

     Решение транспортной задачи

     Транспортная  задача — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.

     Требуется найти минимальную стоимость  перевозок.

     Для этого, сверх имеющихся n пунктов назначения b₁, b₂, b₃ введем еще один, фиктивный, пункт назначения b₄, которому припишем фиктивную заявку, равную избытку запасов над заявками. Стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения b₄ будем считать равным нулю. Введением фиктивного пункта назначения B₄ с его заявкой b₄ мы сравняли баланс транспортной задачи и теперь его можно решать как обычную транспортную задачу с правильным балансом.

     Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ "северо-западного угла", способ минимальной стоимости по строке, способ минимальной стоимости по столбцу и способ минимальной стоимости таблицы.

     Полученное  решение является опорным решением транспортной задачи: 

     Проверяем оптимальность полученного плана  методом потенциалов.

     Составленный нами план перевозок является оптимальным по стоимости: S_н= S_к=100*2+100*3+20*5+30*3+50*0+90*1=780.