Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Решение транспортной задачи с помощью метода потенциалов.






Министерство образования и науки Российской Федерации

(МИНОБРНАУКИ РОССИИ)

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ»

Институт информационных систем управления

Кафедра математических методов в управлении

 

 

по дисциплине: «Методы оптимальных решений»

 

 

ДОМАШНЯЯ РАБОТА №2

Вариант 20

 

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

 

Выполнила студентка очной формы обучения Сергиенко А.В. 2 курса 3 группы     ____________________ (подпись) __________________________ (инициалы, фамилия)
Принял ____________________ (подпись) Е.Ю. Луценко

Москва 2014 год

 

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

Решение транспортной задачи с помощью метода потенциалов.

Составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были бы минимальными.

Таблица 1. Исходные данные

  b =          
  а =             c =
         
         

 

В правом столбце записаны компоненты вектора a. Каждая i – я компонента его равна максимальному количеству единиц продукта (максимальному предложению), которое может отправить i -й поставщик.

В верхней строке находятся компоненты вектора b. Каждая j – я компонента его равна минимальному количеству единиц продукта (максимальному спросу), которое должен получить j -й потребитель.

В остальных местах таблицы 1 находятся элементы матрицы С удельных затрат на транспортировку продукта размера .

 

 

В матричном виде:

 

Общий объем производства больше, чем требуется всем потребителям , т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 116 -104 = 12 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

 

Первое базисное допустимое решение, построенное по правилу «северо-западного угла», которое состоит в том, чтобы на каждом этапе мы максимально загружали «северо-западную клеточку».

 

Таблица 2. Первое базисное допустимое решение

   
         
    18   + 2
    + 10 16 12   -2
7 7 3 4 2  

 

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

Имеем:

 

Затем по формуле вычисляем оценки всех свободных клеток:

Находим наибольшую положительную оценку:

Для найденной свободной клетки (2, 5) строим цикл пересчета – замкнутую ломаную линию. Это будет цикл с вершинами в клетках (2, 5), (2, 3), (3, 3), (3, 5). Ниже, на схеме выделены только вершинные клетки цикла пересчета.

 

 

   
   
 


Таблица 3. Второе базисное допустимое решение

   
  3 +    
  +18 6     2
          -2
7 7 3 4 - 2  

 

Имеем:

Затем по формуле вычисляем оценки всех свободных клеток:

 

Находим наибольшую положительную оценку:

 

Для найденной свободной клетки (1, 3) строим цикл пересчета. Это будет цикл с вершинами в клетках (1, 3), (1, 2), (2, 2), (2, 3).

 

   
  6
 
   
   

 

 

 

 

Таблица 4. Третье базисное допустимое решение

   
39   + 3    
+   3     3
          -1
7 6 2 3 - 3  

 

Следующим шагом является нахождение потенциалов:

 

Оценки для свободных клеток:

 

Наибольшая положительная оценка:

Для найденной свободной клетки (2, 1) строим цикл пересчета. Это будет цикл с вершинами в клетках (2, 1), (2, 3), (1, 3), (1, 1).

 

  3
   
 
   
   

 


 

Таблица 5. Четвертое базисное допустимое решение

   
36 +      
+ 3 21       1
          -1
7 8 2 3 - 1  

 

Находим потенциалы:

 

Далее находим оценки свободных клеток.

Наибольшая положительная оценка:

Для найденной свободной клетки (1, 2) строим цикл пересчета. Это будет цикл с вершинами в клетках (1, 2), (1, 1), (2, 1), (2, 2).

 

 
   
   
   



 

Таблица 6. Пятое базисное допустимое решение

   
  21      
          1
          -1
7 7 2 3 - 1  

 

Имеем:

 

Оценки свободных клеток:

Опорный план является оптимальным, так как все оценки свободных клеток

 

Итак, оптимальное базисное допустимое решение

 

 

2. Решение задачи с помощью инструмента «Поиск решения» программного продукта Microsoft Excel.

 

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.