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

x15+x25+x35+x45=40

x16+x26+x36+x46=5

xij≥0 (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3. )

Двойственная ЗЛП:

max(50u1+20u2+75u3+80u4+40v1+50v2+15v3+75v4+40v5+5v6) (3. )

u1+v1≤1

u1+v2≤2

u1+v3≤3 (3. )

u1+v4≤2,5

u1+v5≤3,5

u1+v6≤0

ui,vj – произвольные (i=1,2,3,4 ; j=1,2,3,4,5,6 )

Будем искать первоначальный план по методу наименьшей стоимости:

1) x21=20 и 2-ую строку исключаем;

2) x31=20 и 1-ый столбец исключаем;

3) x34=55 и 3-ю строку исключаем;

4) x44=20 и 4-ый столбец исключаем;

5) x12=50 и 1-ю строку и 2-ой столбец исключаем и x32=0;

6) x43=150 и 3-ий столбец исключаем;

7) x45=40 и 5-ый столбец исключаем и x46=5.

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

Таблица 3. – Проведение итераций

Стоимость 1-ого плана:

D1=2•50+0,4•20+0,7•20+0,8•55+2•15+1,5•20+2,5•40=326.

Будем улучшать этот план методом потенциалов: ui- потенциал Аi ,vj- потенциал Bj. Тогда u1+v2=2,u2+v1=0,4, u3+v1=0,7, u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5 ,u4+v6=0.Положим u1=0,тогда v2=2,u3=-1,v1=1,7,v4=1,8, u2=-1,3,u4=-0,3, v3=2,3,v5=2,8,v6=0,3.Составим таблицу 3. :

Таблица 3. - Проведение итераций

 Скачать реферат