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

Содержание

• 
  Слайд 1
  

  Первухин Михаил Александрович Доцент кафедры математики и моделирования Лекция. Линейное программирование. Транспортная задача. Дисциплина:Исследование операций

• 
  Слайд 2

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

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

• 
  Слайд 3

  Математическая модель ТЗ

  Логистическая компания располагает тремя пунктами упаковки косметики расположенными в Твери, Ярославле и Смоленске, откуда сформированные наборы перевозятся на грузовиках к трём оптовым поставщикам, расположенным в Москве, Санкт-Петербургеи Нижнем Новгороде.

• 
  Слайд 4
  

  Недельная производительность по формированию косметических наборов и потребности в наборах в городах приведены на схеме. С.-Петербург Ярославль Тверь Ниж. Новгород Смоленск Москва 30 тысяч 55 тысяч 25 тысяч 25 тысяч 45 тысяч 20 тысяч

• 
  Слайд 5
  

  Стоимость доставки (транспортные тарифы) одного набора (ед.) из пунктов упаковки к каждому оптовому поставщику приведены в таблице.

• 
  Слайд 6
  

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

• 
  Слайд 7

  Составление математической модели

  Обозначим пункты отправления индексом , так что соответствует Твери, — Ярославлю и — Смоленску, а пункты назначения — индексомj,при этомсоответствует Москве,j— Санкт-Петербургу, — Нижнему Новгороду. Переменными математической модели являются объёмы ежедневных перевозок наборов между пунктами отправления () и пунктами назначения  

• 
  Слайд 8

  Математическая модель задачи

  Цель: Минимизировать суммарные затраты на транспортировку.  

• 
  Слайд 9
  

  С условиями:  

• 
  Слайд 10

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

  Рассмотрим задачу.

• 
  Слайд 11

  Алгоритм решения

  Проверяем условие баланса: запасы должны равняться потребностям. Составляем опорный план методом «северо-западного» угла.

• 
  Слайд 12

  Проверка условия баланса

• 
  Слайд 13

  Метод северо-западного угла

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

• 
  Слайд 14

  Поиск опорного плана методом «северо-западного» угла

  ? Северо-западная клетка. В неё записываем наименьшее из чисел 25 и 45. 0 20 Вычеркиваем израсходованные запасы и потребности. 25 ? В клетку (1;1) записали 25 ед., поэтому на первом складе осталось 25-25=0 ед.

• 
  Слайд 15
  

  0 20 25 ед. товара поедет из склада в магазин Тогда на складе больше не останется товара. Этот значит, в магазины поедет с других складов.   В таблице этот факт мы обозначаем при помощи прочерков.

• 
  Слайд 16
  

  0 20 Следующая северо-западная клетка. Записываем в неё наименьшее из чисел 20 и 55. 20

• 
  Слайд 17
  

  0 20 20 Пересчитываем запасы и потребности 35 0 Потребности магазина полностью выполнены. Ставим в клетку (3,1) прочерк.   −

• 
  Слайд 18

  Продолжаем находить опорный план

  5

• 
  Слайд 19
  
• 
  Слайд 20

  Шаг 3

  3. Проверяем, чтобы число заполненных клеток равнялось где – число складов, – число магазинов. В нашем примере, Значит, число заполненных клеток должно равняться  

• 
  Слайд 21

  Проверка невырожденности опорного плана

  У нас 5 заполненных клеток

• 
  Слайд 22

  Шаг 4

  4. По заполненным клеткам находим потенциалы поставщиков и потенциалы потребителей из следующей формулы: где - тарифы на перевозку с -го склада в -й магазин.  

• 
  Слайд 23

  Вычисление потенциалов

    Полагаем и находим значение остальных потенциалов. Из системыполучаем:  

• 
  Слайд 24

  Шаг 5

  5. Для пустых клеток находим оценки по следующей формуле:  

• 
  Слайд 25

  Вычисление оценок

• 
  Слайд 26

  Шаги 6-7

  6. Если среди чисел нет положительных, то получен оптимальный план; если же они имеются, то переходят к новому плану. 7. Среди положительных чисел выбираем максимальное. Пусть максимальная из оценок - Строим для клетки (обозначим ее *)цикл пересчёта.  

• 
  Слайд 27

  Цикл пересчета

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

• 
  Слайд 28

  Построение цикла

• 
  Слайд 29

  Шаг 8

  8. Производят сдвиг по циклу пересчёта. Для этого каждой клетке таблицы, в которой находится вершина цикла пересчёта, приписывают определённый знак, причём свободной клетке (клетке *) приписывают знак плюс, а всем остальным клеткам  поочерёдно знак плюс или минус. В данную свободную клетку переносят меньшее из чисел, стоящих в клетках со знаком минус. Одновременно это число прибавляют к соответствующим числам, стоящим в клетках со знаком плюс, и вычитают из чисел, стоящих в клетках со знаком минус. После пересчета число заполненных клеток должно остаться тем же.

• 
  Слайд 30

  Расстановка знаков

  + + - - В клетках цикла с минусами выбираем наименьшую из загрузок . Теперь в клетках со знаком + нужно прибавить 5, а в клетках со знаком минус отнять 5.  

• 
  Слайд 31

  Сдвиг по циклу пересчета

  9. Повторяем шаги 4-7.

• 
  Слайд 32

  Вновь вычисляем потенциалы

• 
  Слайд 33

  Пересчитываем оценки

• 
  Слайд 34
  

  + + - - В клетках с минусами две одинаковые «загрузки» по 20 ед., когда мы будем отнимать 20, то в этих клетках получатся нули, но число заполненных клеток на протяжении всей задачи должно оставаться тем же. Поэтому в одной из них мы поставим прочерк, а в другой нарисуем ноль и будем считать ее условно заполненной. Ноль лучше нарисовать в той клетке, где тариф меньше.

• 
  Слайд 35

  Пересчет потенциалов и оценок для нового плана

• 
  Слайд 36
  

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

• 
  Слайд 37

  Замечание 1

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

• 
  Слайд 38
  

  Так как мы решаем задачу минимизации, то из двух клеток стоит выбрать ту, где тариф меньше. В нее записываем 0 и считаем эту клетку условно заполненной. 0

• 
  Слайд 39

  Замечание 2

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