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

Содержание

• 
  Слайд 1

  Транспортные задачи

  Построение исходного опорного плана перевозок

• 
  Слайд 2

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

  определение оптимального планаперевозок груза из m пунктов отправления A1, A2, . . . , Am в n пунктов назначения B1, B2, . . . , Bn. определение минимального значения целевой функции стоимости перевозок Всякое неотрицательное решение систем линейных уравнений, называетсяпланом транспортной задачи. План, при котором целевая функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи. Еслиобщая потребность в грузе в пунктах назначения равназапасу груза в пунктах отправления, то модель такой транспортной задачи называется закрытой, если данное условие не выполняется, то модель транспортной задачи называется открытой.

• 
  Слайд 3

  Транспортная таблица

    Математическая формулировка транспортной задачи сводится к минимизации линейной функции

• 
  Слайд 4
  

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

  Метод северо-западного угла Метод минимального элемента Метод аппроксимации Фогеля

• 
  Слайд 5

  Задача

  Найти тремя методами опорный план транспортной задачи, в которой запасы на трех складах равны 210, 170, 65 ед. продукции, потребности четырёх магазинов равны 125, 90, 130, 100 ед. продукции, тарифы перевозок в рублях за единицу продукции следующие: 5 8 1 2 2 5 4 9 9 2 3 1

• 
  Слайд 6
  

  Транспортная задачаПостроение исходного опорного планаМетод северо-западного угла

  125 /0 85 /5 65 5 130 /85 35 /0 /165 /35 /0 /0 /0 /65 /0 /0 Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет: S1= 125*5+85*8+5*5+130*4+35*9+65*1=2230 (руб.)

• 
  Слайд 7
  

  Транспортная задачаПостроение исходного опорного планаМетод минимального элемента

  130 /0 65 /35 45 35 125 /80 45 /0 /45 /45 /0 /0 /0 /45 /0 /0 Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет: S2= 125*2+45*8+45*5+130*1+35*2+65*1=1100 (руб.)

• 
  Слайд 8
  

  Транспортная задачаПостроение исходного опорного планаМетод аппроксимации Фогеля

  25 /0 65 /110 110 100 125 /25 20 /0 /20 /25 /0 /0 /0 /45 /0 /0 Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет: S3= 125*2+25*5+65*2+ +110*1+20*4+100*2=895 (руб.) 1 1 1 1 2 1 1 1 - 1 7 3 3 7 - - - - - 3 2 1 2 3 3 3 1 3 0 0 - 0 0 1 - - - - - - - -

• 
  Слайд 9
  

  Построение исходного опорного плана3 –мя методами дает следующие значения стоимости перевозок всего груза:

  S1= 125*5+85*8+5*5+130*4+35*9+65*1=2230 (руб.) S2= 125*2+45*8+45*5+130*1+35*2+65*1=1100 (руб.) S3= 125*2+25*5+65*2+110*1+20*4+100*2=895 (руб.)

• 
  Слайд 10

  Транспортные задачи

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

• 
  Слайд 11
  

  Решение транспортной задачи по начальному опорному плану (метод минимального элемента)Проверим оптимальность опорного плана

  130 65 45 35 125 45 Найдем предварительные потенциалы (ui, vi) для занятых клеток полагая, что u1=0 ui+vj=cij u1=0 u2=-3 u3=-1 v1=5 v2=8 v3=1 v4=2 u1=0 u1+v2=8; 0+v2=8;v2=8 u2+v2=5; 8+u2=5;u2=-3 u2+v1=2; -3+v1=2;v1=5 u1+v3=1; 0+v3=1;v3=1 u1+v4=2; 0+v4=2;v4=2 u3+v4=1; 2+u3=1;u3=-1 Опорный план не оптимален, так как существуют отрицательные оценки(E32) E11=c11-u1-v1=5-0-5=0 E23=c23-u2-v3=4-1+3=6 E24=c24-u2-v4=9+3-2=10 E31=c31-u3-v1=9+1-5=5 E32=c32-u3-v2=2+1-8=-5 E33=c33-u3-v3=3+1-1=3 E11=0 E23=6 E24=10 E31=5 E32=-5 E33=3 Посчитаем оценки для свободных клеток(Eij) Eij=cij-ui-vj

• 
  Слайд 12
  

  Решение транспортной задачи по начальному опорному плану (метод минимального элемента)Построение цикла

  130 45 35 125 45 Построим цикл для свободной клетки A3B2так чтобы во всех углах цикла был груз, кроме клетки с минимальной оценкой. 20 Пустой клетке ставим “+” и далее в следующие углы цикла ставим “-”,”+” соответственно, пока углы цикла не заполнены. Из клеток с “-” вычитаем максимально возможный груз. В данном случае вычитаем 45, и добавляем его в клетки с “+”. 45 80 65

• 
  Слайд 13
  

  Решение транспортной задачи по начальному опорному плану (метод минимального элемента)Проверка на оптимальность

  130 125 45 45 80 20 u1=0 u2=2 u3=-1 v1=0 v2=3 v3=1 v4=2 E11=5 E23=1 E24=5 E31=10 E32=5 E33=3 Найдем предварительные потенциалы. u1=0 u2=2 u3=-1 v1=0 v2=3 v3=1 v4=2 Посчитаем оценки. E11=5 E32=5 E23=1 E24=5 E31=6 E33=3 Опорный план оптимален, так как все оценки не отрицательные. Минимальные затраты составят: F(x)=1*130+2*80+2*125+5*45+2*45+20=875