МИНИСТЕРСТВООБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Реферат
подисциплине: Методы и модели в экономике и менеджменте.
на тему: «Применениеметодов линейного программирования для оптимизации стоимости перевозок»
Воронеж 2010
Под названием“транспортная задача” объединяется широкий круг задач с единой математическоймоделью. Данные задачи относятся к задачам линейного программирования и могутбыть решены симплексным методом. Однако матрица системы ограниченийтранспортной задачи настолько своеобразна, что для ее решения разработаныспециальные методы. Эти методы, как и симплексный метод, позволяют найтиначальное опорное решение, а затем, улучшая его, получить оптимальное решение.
В общей постановкетранспортная задача состоит в отыскании оптимального плана перевозок некоторогооднородного груза с /> баз /> /> потребителям />.
Различают два типатранспортных задач: но критерию стоимости (план перевозок оптимален, еслидостигнут минимум затрат на его реализацию) и по критерию времени (планоптимален, если на его реализацию затрачивается минимум времени).
(3. ) Обозначим количествогруза, имеющегося на каждой из /> баз (запасы), соответственно />, а общее количествоимеющегося в наличии груза–/>:
/>;
(3. ) заказы каждого изпотребителей (потребности) обозначим соответственно/>,а общее количество потребностей – />:
/>,
(3. ) Тогда при условии
/>
(3. ) мы имеем закрытую модель,а при условии
/>
– открытую модельтранспортной задачи.
Очевидно, в случаезакрытой модели весь имеющийся в наличии груз развозится полностью, и всепотребности заказчиков полностью удовлетворены; в случае же открытой моделилибо все заказчики удовлетворены и при этом на некоторых базах остаются излишкигруза />, либо весь груз оказывается израсходованным, хотяпотребности полностью не удовлетворены />.
Так же существуютодноэтапные модели задач, где перевозка осуществляется напрямую от, например,базы или завода изготовителя к потребителю, и двухэтапные, где между нимиимеется “перевалочный пункт”, например – склад.
План перевозок суказанием запасов и потребностей удобно записывать в виде следующей таблицы,называемой таблицей перевозок (Таблица 3. ):
Таблица 3. — План перевозок с указанием запасов ипотребностей
Пункты
Отправления Пункты назначения Запасы
/>
/> …
/>
/>
/>
/> …
/>
/>
/>
/>
/> …
/>
/> … … … … … …
/>
/>
/> …
/>
/> Потребности
/>
/> …
/>
/>
или
/>
Условие /> или /> означает, с какой задачеймы имеем дело, с закрытой моделью или открытой моделью транспортной задачи.Переменное /> означает количество груза,перевозимого с базы /> потребителю />: совокупность этих величинобразует матрицу (матрицу перевозок).
Очевидно, переменные /> должны удовлетворятьусловиям:
/>
(3. ) />
/>
Система (3. ) содержит /> уравнений с /> неизвестными. Еёособенность состоит в том, что коэффициенты при неизвестных всюду равныединице. Кроме того, все уравнения системы (3. ) могут быть разделены на двегруппы: первая группа из т первых уравнений (“горизонтальные” уравнения) ивторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом изгоризонтальных уравнений содержатся неизвестные с одним и тем же первыминдексом (они образуют одну строку матрицы перевозок), в каждом из вертикальныхуравнений содержатся неизвестные с одним и тем же вторым индексом (они образуютодин столбец матрицы перевозок). Таким образом, каждая неизвестная встречаетсяв системе (3. ) дважды: в одном и только одном горизонтальном и в одном и толькоодном вертикальном уравнениях.
Такая структура системы(3. ) позволяет легко установить ее ранг. Действительно, покажем, чтосовокупность неизвестных, образующих первую строку и первый столбец матрицыперевозок, можно принять в качестве базиса. При таком выборе базиса, по крайнеймере, один из двух их индексов равен единице, а, следовательно, свободныенеизвестные определяются условием />, />.Перепишем систему (3. ) в виде
/>
(3. ) />
где символы />и />означают суммирование посоответствующему индексу. Так, например,
/>
При этом легко заметить, что под символамитакого суммирования объединяются только свободные неизвестные (здесь />, />).
В рассматриваемой намисистеме только два уравнения, а именно первое горизонтальное и первоевертикальное, содержат более одного неизвестного из числа выбранных нами дляпостроения базиса. Исключив из первого горизонтального уравнения базисныенеизвестные /> с помощью вертикальных уравнений, мы получаемуравнение
/>
или короче
(3. ) />
где символ /> означает сумму всехсвободных неизвестных. Аналогично, исключив из первого вертикального уравнениябазисные неизвестные /> с помощью горизонтальных уравнений, мы получаемуравнение
(3. ) />
Так как для закрытоймодели транспортной задачи />, тополученные нами уравнения (3. ) и (3. ) одинаковы и, исключив из одного из нихнеизвестное />, мы получимуравнение-тождество 0=0, которое из системы вычеркивается.
Итак, преобразованиесистемы (3. ) свелось к замене двух уравнений (первого горизонтального ипервого вертикального) уравнением (3. ). Остальные уравнения остаютсянеизменными. Система приняла вид
/>
(3. ) />
В системе (3. ) выделенуказанный выше базис: базисные неизвестные из первых т уравнений образуютпервый столбец матрицы перевозок, а базисные неизвестные остальных уравненийобразуют первую строку матрицы перевозок без первого неизвестного /> [она входит в первоеуравнение системы (3. )]. В системе (3. ) имеется /> уравнений,выделенный базис содержит /> неизвестных,а, следовательно, и ранг системы (3. ) />.
Для решения транспортнойзадачи необходимо кроме запасов и потребностей знать также и тарифы />, т. е. стоимость перевозкиединицы груза с базы /> потребителю />.
Совокупность тарифов /> также образует матрицу,которую можно объединить с матрицей перевозок и данными о запасах ипотребностях в одну таблицу 3.:
Таблица 3. — Совокупность тарифов данные о запасахи потребностях
Пункты
Отправления Пункты назначения Запасы
/>
/> …
/>
/>
/>
/> …
/>
/>
/>
/>
/>
/>
/>
/> …
/>
/>
/>
/>
/> … … … … … …
/>
/>
/> …
/>
/>
/>
/>
/> Потребности
/>
/> …
/>
/>
или
/> /> /> /> /> /> /> /> /> /> /> />
Сумма всех затрат, т. е.стоимость реализации данного плана перевозок, является линейной функциейпеременных />:
(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
А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
Математическая модель:обозначим 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
(b1=40)
B2
(b2=50)
B3
(b3=15)
B4
(b4=75)
B5
(b5=40)
B6
(b6=5)
А1 (а1=50)
1,0
/>
50 2,0 3,0 2,5 3,5
А2(а2=20)
/>0,4
20 3,0 1,0 2,0 3,0
А3(а3=75)
/>0,7
20
0 1,0 1,0
55 0,8 1,5
5
15 А4(а4=80) 1,2 2,0 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. — Проведениеитераций
/> Цеха
Склад
B1
(b1=40)
v1=1,7
B2
(b2=50)
v2=2
B3
(b3=15)
v3=2,3
B4
(b4=75)
v4=1,8
B5
(b5=40)
v5=2,8
B6
(b6=5)
v6=0,3
/>
,7 А1 (а1=50)
U1=0
/>/>
0 1,0
/>/>
- 0,7
50 2,0
- 0,7 3,0
- 0,7 2,5
,3 3,5
0 А2(а2=20)
U2=-1,3
- 2,3
20 0,4
0 3,0
- 1,5 1,0
- 1,5 2,0
- 1 3,0
0 А3(а3=75)
U3=-1
/>
0 0,7
/>
20
/>
,3
0 1,0
0 1,0
,3
55 0,8
- 0,7 1,5
,2 А4(а4=80)
U4=-0,3
- 0,3 1,2
0 2,0
0
15 2,0
0
20 1,5
0
40 2,5
5 0
Вверхнем левом углу здесь и далее записываем значение ui+vj-cij.Имеем: u1+v1--c11=0,7>0,u1+v6-c16=0,3>0,u3+v3-c33=0,3>0,u3+v5-c35=0,3>0,
u4+v1-c41 =0,2>0. => По критерию оптимальности, первый план неоптимален. Далее max(0,7;0,3;0,3;0,3;0,2)=0,7.=> Поместим перевозку в клетку А1В1,сместив20=min(20,50) по циклу, указанному втаблице штрихом. Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5, u4+v6=0. Положим u1=0, тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=2,3,v5=2,8,v6=0,3. Составим таблицу 3. :
Таблица 3. — Проведениеитераций
/> Цеха
Склад
B1
(b1=40)
v1=1
B2
(b2=50)
v2=2
B3
(b3=15)
v3=2,3
B4
(b4=75)
v4=1,8
B5
(b5=40)
v5=2,8
B6
(b6=5)
v6=0,3
0 А1 (а1=50)
U1=0
/>/>/>
0 1,0
20
/>/>
- 0,7
30 2,0
- 0,7 3,0
- 0,7 2,5
,3 3,5
0 А2(а2=20)
U2=-0,6
/>
- 1,6
20 0,4
/>
,7 3,0
/>/>
- 0,8 1,0
- 0,8 2,0
- 0,3 3,0
-0,7 А3(а3=75)
U3=-1
0 0,7
/>/>
,3
20 1,0
0 1,0
/>/>
,3
55 0,8
- 0,7 1,5
-0,5 А4(а4=80)
U4=-0,3
- 0,3 1,2
0 2,0
/>/>
0
15 2,0
/>
0
20 1,5
0
40 2,5
5 0
Стоимость 2-ого плана:
D2=1•20+2•30+0,4•20+1•20+0,8•55+2•15+1,5•20+2,5•40=312.
Имеем:u1+v6-c16=0,3>0,u2+v3-c23=0,7>0,u3+v3-c33=0,3>0,u3+v5-c35=0,3>0.=> По критерию оптимальности, второй план не оптимален. Далее max(0,3;0,7;0,3;0,3)=0,7=> Поместим перевозку в клетку А2В3,сместив15=min(20,30,55,15) по циклу, указанномув таблице штрихом. Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1,u3+v4=0,8,u2+v3=1,u4+v4=1,5,u4+v5=2,5, u4+v6=0.Положим u1=0, тогдаv1=1,u2=-0,6,v2=2,v4=1,8,u3=-1,u4=-0,3,v3=1,6,v5=2,8,v6=0,3.Составим таблицу 3.:
Таблица 3. — Проведениеитераций
/> Цеха
Склад
B1
(b1=40)
v1=1
B2
(b2=50)
v2=2
B3
(b3=15)
v3=1,6
B4
(b4=75)
v4=1,8
B5
(b5=40)
v5=2,8
B6
(b6=5)
v6=0,3
0 А1 (а1=50)
U1=0
0 1,0
35
-1,4
15 2,0
- 0,7 3,0
- 0,7 2,5
,3 3,5
0 А2(а2=20)
U2=-0,6
- 1,6
5 0,4
0 3,0
15
- 0,8 1,0
- 0,8 2,0
- 0,3 3,0
-0,7 А3(а3=75)
U3=-1
0 0,7
-0,4
35 1,0
0 1,0
/>/>/>
,3
40 0,8
/>/>
- 0,7 1,5
-0,5 А4(а4=80)
U4=-0,3
- 0,3 1,2
-0,7 2,0
0 2,0
/>/>
0
35 1,5
/>
0
40 2,5
5 0
Стоимость 3-его плана:
D3=1•35+2•15+0,4•5+1•15+0,8•40+1•35+1,5•35+2,5•40=301,5.
Имеем:u1+v6-c16=0,3>0,u3+v5-c35=0,3>0.=> По критерию оптимальности, третий план не оптимален. Далее max(0,3;0,3)=0,3.=> Поместим перевозку в клетку А3В5,сместив40=min(40,40) по циклу, указанному втаблице штрихом. Получим новую таблицу. Чтобы 4-ый план был невырожденным,оставим в клетке А4В5 нулевую перевозку. Найдемпотенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1,u4+v5=2,5,u2+v3=1,u4+v4=1,5,u3+v5=1,5, u4+v6=0.Положим u1=0, тогдаv1=1,u2=-0,6,v2=2,v4=1,5,u3=-1,u4=0,v3=1,6,v5=2,5,v6=0.Составим таблицу 3. :
Таблица 3. — Проведениеитераций
/> Цеха
Склад
B1
(b1=40)
v1=1
B2
(b2=50)
v2=2
B3
(b3=15)
v3=1,6
B4
(b4=75)
v4=1,5
B5
(b5=40)
v5=2,5
B6
(b6=5)
v6=0
0 А1 (а1=50)
U1=0
0 1,0
35
- 1,4
15 2,0
- 1 3,0
- 1 2,5
3,5
0 А2(а2=20)
U2=-0,6
- 1,6
5 0,4
0 3,0
15
- 1,1 1,0
- 1,1 2,0
- 0,6 3,0
-0,7 А3(а3=75)
U3=-1
0 0,7
-0,4
35 1,0
-0,3 1,0
0,8
40
- 1 1,5
-0,2 А4(а4=80)
U4=0
0 1,2
-0,4 2,0
0 2,0
0
75 1,5
0
0 2,5
5 0
Стоимость 4-ого плана:
D4=1•35+2•15+0,4•5+1•15+1•35+1,5•40+1,5•75=289,5.
Для всех клеток последнейтаблицы выполнены условия оптимальности:
1) ui+vj-сij=0 для клеток, занятых перевозками;
2) ui+vj-сij≤0 для свободных клеток.
Несодержательные ответы:
Прямой ЗЛП:
/> 35 15 0 0 0 0
5 0 15 0 0 0
X = 0 35 0 0 40 0
0 0 0 75 0 5
min=289,5.
Двойственной ЗЛП:
U1=0; U2=-0,6; U3=-1; U4=0; V1=1; V2=2; V3=1,6; V4=1,5; V5=2,5; V6=0.
max=289,5.
Так как min=max, то по критерию оптимальности найдены оптимальныерешения прямой и двойственной ЗЛП. Содержательный ответ: Оптимально перевозитьтак:
Из А1 вB1 – 35 сборочных агрегатов;
Из А1 вB2 – 15 сборочных агрегатов;
Из А2 вB1 – 5 сборочных агрегатов;
Из А2 вB3 – 15 сборочных агрегатов;
Из А3 вB2 – 35 сборочных агрегатов;
Из А3 вB5 – 40 сборочных агрегатов;
Из А4 вB4 – 75 сборочных агрегатов.
При этом стоимостьминимальна и составит Dmin=289,5. 5 сборочных агрегатов необходимо оставить на складе А4для их последующей перевозки в другие Цеха.
Список использованнойлитературы
1. Е.Г. Гольштейн, Д.Б. Юдин «Задачилинейного программирования транспортного типа», Москва, 2007.
2. И.Л. Акулич, В.Ф. Стрельчонок«Математические методы и компьютерные технологии решения оптимизационныхзадач», Рига, 2006.
3. Астафуров В.Г., Колодникова Н. — Компьютерное учебное пособие, раздел “Анализ на чувствительность с помощьюдвойственной задачи”, Томск-2004.
4. Алесинская Т.В. — Задачи поисследованию операций с решениями. Москва, 2008.
5. Смородинский С.С., Батин Н.В. — Оптимизация решений на основе методов и моделей математическогопрограммирования: Учебное пособие. Воронеж, 2009