Презентация на тему "Транспортная задача (продолжение)"

Содержание

• 
  Слайд 1
  

  Кафедра математики и моделирования Старший преподаватель Е.Г. Гусев Курс «Высшая математика» Лекция 19. Тема: Транспортная задача. Цель: Рассмотреть метод «северо-западного угла». Узнать понятие цикла пересчета и его свойства. Метод потенциалов решения транспортной задачи.

• 
  Слайд 2
  

  Метод Северо-западного угла. Метод минимальной стоимости (элемента).

• 
  Слайд 3
  

  ПРИМЕР.В резерве трех железнодорожных станций A, B, C находятся соответственно 60, 80, 100 вагонов. Составить оптимальный план перегона этих вагонов к 4-ем пунктам погрузки хлеба, если пункту №1 необходимо 40 вагонов, №2 – 60, №3 – 80, №4 – 60. Стоимость перегонов одного вагона со станции A в в указанные пункты соответственно равны 1, 2, 3, 4 ден.ед., со станции B – 4, 3, 2, 0 ден.ед. и со станции C – 0, 2, 2, 1 ден.ед..

• 
  Слайд 4
  
• 
  Слайд 5
  

  m = 3; n = 4; m+n –1 = 6 => План опорный

• 
  Слайд 6
  

  Общая стоимость составленного плана: Z=40·1+20·2+40·3+40·2+40·2+60·1= 40+40+120+80+80+60=420 Это не оптимальное решение.

• 
  Слайд 7
  

  Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то очевидно, что план будет ближе к оптимальному.

• 
  Слайд 8
  

  Суть метода минимальной стоимости (элемента) заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ему соответствует, помещают меньшее из чисел и .

• 
  Слайд 9
  

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

• 
  Слайд 10
  

  Итак, опорный план трансформированной задачи построен, теперь надо из него получит оптимальный. Можно было получить оптимальный план используя симплекс-метод, но в нашем случае симплексная таблица будет содержать mn неизвестных, что приведет к громоздким вычислениям.

• 
  Слайд 11
  

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

• 
  Слайд 12
  

  Метод потенциалов.

• 
  Слайд 13
  

  Числа и называют потенциалами поставщиков и потребителей.

• 
  Слайд 14
  

  Для того чтобы план был оптимальным, необходимо выполнение следующих условий: 1.) для каждой занятой клетки сумма потенциалов должна быть равно стоимости единицы перевозки, стоящей в этой клетке; 2.) для каждой незанятой клетки сумма потенциалов должна быть меньше, либо равна стоимости единицы перевозки, стоящей в этой клетке.

• 
  Слайд 15
  

  Если хотя бы одна незанятая клетка удовлетворяет условию (2), то опорный план не является оптимальным, и его улучшают, перемещая в клетку некоторое количество единиц груза).

• 
  Слайд 16
  

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

• 
  Слайд 17
  

  Выбор клетки в которую необходимо послать перевозку: транспортная задача линейного программирования решается на min линейной функции, поэтому алгоритм ее решения тот же, что и алгоритм симплекс-метода. Загрузке подлежит в первую очередь клетка, которой соответствует

• 
  Слайд 18
  

  Построение цикла и определение величины перераспределения груза: отмечаем знаком « + » незанятую клетку, которую надо загрузить (знаки (-;+) чередуются). Затем находим min, где – перевозки, стоящие в вершинах цикла, отмеченных знаком « - ». Величина minопределяет сколько единиц груза надо перераспределить.

• 
  Слайд 19
  

  После перераспределения должно получиться m+n-1 занятых клеток. Если для какой-либо клетки условие оптимальности не выполняется, то можно улучшить решение двойственной задачи, а заодно и исходной задачи, сделав эту клетку занятой и перебросив груз по циклу.

• 
  Слайд 20
  

  Для свободных клеток сумма потенциалов меньше, либо равна стоимости, следовательно в последней таблице должно быть получено оптимальное решение исходной транспортной задачи.

• 
  Слайд 21
  

  Открытая модель транспортной задачи.

• 
  Слайд 22
  
• 
  Слайд 23
  
• 
  Слайд 24
  
• 
  Слайд 25
  
• 
  Слайд 26
  
• 
  Слайд 27
  

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

• 
  Слайд 28
  

  Вопросы: 1)Чем различаются открытая и закрытая модели транспортной задачи? 2)В чем заключается метод потенциалов решения транспортной задачи?