Формирование схемы движения

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

Целевая функция:

Где -расстояние между i-м пунктом отправления и j-м пунктом назначения(км);

-объем перевозок между i-м пунктом отправления

Ограничения:

=

Где -объем отправления из i-го пункта

-объем потребления в j-ом пунктеиндекс пункта отправления (i=1,…,m)индекс пункта назначения (j=1,…,n)число пунктов отправлениячисло пунктов назначения

Составление начального плана перевозок

Начальный (опорный) план перевозок будем искать методом северо-западного угла.

По этому методу заполнение клеток начинается с верхней левой клетки. Далее двигаемся вправо и вниз.

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

; ; и т.д.

Для любого опорного плана число свободных клеток равно (m-1)(n-1). Число базисных переменных (заполненных клеток) должно быть равно n+m-1, среди них могут оказаться нулевые значения.=5;m=3заполненных клеток 7, пустых клеток 8

Таблица4.

F=L11x11+ L12x12+ L12x12+ L13x13+ L14x14+ L15x15+ L21x21+ L22x22+ L23x23+ L24x24+L25x25+ L31x31+ L32x32+ L33x33+ L34x34 + L35x35 =150*270+80*190 +20*290+ +0*190+0*180+0*175+0*350+240*200+120*185+90*200+0*230+0*310+0*295+0*200+100*325=182200

а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj

Значения потенциалов определяются из условия, что для базисных (заполненных) клеток сумма потенциалов равна расстоянию Lij, т.е.

+bij=Lij

при этом потенциал первого пункта отправления принимается равным 0 (а1=0)

а1=0=L11-a1=270-0=270=L12-a1=190-0=190=L13-a1=290-0=290=L23-b3=200-290= -90=L24-a2=185-(-90)=275=L25-a2=200-(-90)=290=L35-b5=325-290=35

б) проверяем условия оптимальности плана.

С целью проверки условий оптимальности плана для всех свободных клеток проверяется соотношение

aij+bijLij+b4=275>190!=85+b5=290>180!=110+b1=180>175!=5+b2=100<350+b1=305>230!=75+b2=225<3103+b3=325>295!=30+b4=310>200!=110