Быстрый поиск

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

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

(3. )

Требуется в области допустимых решений системы уравнений (3. ) и (3.) найти решение, минимизирующее линейную функцию (3. ).

Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен то среди всех неизвестных выделяется базисных неизвестных, а остальные · неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и · пустых клеток.

На предприятии ОАО «Электросигнал» имеется 4 транзитных склада Аi, на которых хранятся сборочные узлы и 5 цехов Bj, занимающихся сборкой готовой продукции. Ниже, в таблице 3., приведены данные по количеству сборочных узлов на каждом складе, запросы цехов и стоимость перевозки одного агрегата из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок.

Таблица 3. – Исходные данные по количеству сборочных узлов и стоимость перевозки

Цеха Склад	B1 (b1=40)	B2 (b2=50)	B3 (b3=15)	B4 (b4=75)	B5 (b5=40)
А1 (а1=50)	1,0	2,0	3,0	2,5	3,5
А2(а2=20)	0,4	3,0	1,0	2,0	3,0
А3(а3=75)	0,7	1,0	1,0	0,8	1,5
А4(а4=80)	1,2	2,0	2,0	1,5	2,5

В данном случае Σai=225 >Σbj=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного цеха B6 с потребностью b5=225-220=5 и стоимостью перевозок сi6=0.Имеем таблицу 3. :

Таблица 3. -

Цеха Склад	B1 (b1=40)	B2 (b2=50)	B3 (b3=15)	B4 (b4=75)	B5 (b5=40)	B6 (b6=5)
А1 (а1=50)	1,0	2,0	3,0	2,5	3,5	0
А2(а2=20)	0,4	3,0	1,0	2,0	3,0	0
А3(а3=75)	0,7	1,0	1,0	0,8	1,5	0
А4(а4=80)	1,2	2,0	2,0	1,5	2,5	0

Математическая модель: обозначим xij – количество товара, перевозимого из Аi в Bj. Тогда

x11 x12 x13 x14 x15 x16

x21 x22 x23 x24 x25 x26

X = x31 x32 x33 x34 x35 x36 - матрица перевозок.

x41 x42 x43 x44 x45 x46

min(x11+2x12+3x13+2,5x14+3,5x15+0,4x21+3x22+x23+2x24+3x25+0,7x31+x32+x33+0,8x34+1,5x35++1,2x41+2x42+2x43+1,5x44+2,5x45) (3. )

x11+x12+x13+x14+x15+x16=50

x21+x22+x23+x24+x25+x26=20

x31+x32+x33+x34+x35+x36=75

x41+x42+x43+x44+x45+x46=80

(3. )

x11+x21+x31+x41=40

x12+x22+x32+x42=50

x13+x23+x33+x43=15

x14+x24+x34+x44=75

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. )

u2+v1≤0,4

u2+v2≤3

u2+v3≤1

u2+v4≤2

u2+v5≤3

u2+v6≤0

u3+v1≤0,7

u3+v2≤1

u3+v3≤1

u3+v4≤0,8

u3+v5≤1,5

u3+v6≤0

u4+v1≤1,2

u4+v2≤2

u4+v3≤2

u4+v4≤1,5

u4+v5≤2,5

u4+v6≤0

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. – Проведение итераций

Цеха

Склад

(b1=40)

(b2=50)

(b3=15)

(b4=75)

(b5=40)

(b6=5)

А1 (а1=50)

1,0

50

2,0

3,0

2,5

3,5

А2(а2=20)

0,4

3,0

1,0

2,0

3,0

А3(а3=75)

0,7

0

1,0

1,0

55

0,8

1,5

5

15

А4(а4=80)

1,2

2,0

20

1,5

40

2,5

Стоимость 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. - Проведение итераций

Цеха