|
|
Стоимость 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 |
||||||||||||||||||
|
U1=0 |
|
|
|
|
|
0 | ||||||||||||||||||
|
U2=-0,6 |
|
|
|
|
|
0 | ||||||||||||||||||
|
U3=-1 |
|
|
|
|
|
0 | ||||||||||||||||||
|
U4=-0,3 |
|
|
|
|
|
|
Стоимость 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 |
||||||||||||||||||
|
U1=0 |
|
|
|
|
|
0 | ||||||||||||||||||
|
U2=-0,6 |
|
|
|
|
|
0 | ||||||||||||||||||
|
U3=-1 |
|
|
|
|
|
0 | ||||||||||||||||||
|
U4=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
Цеха
Цеха
