Автор работы: Пользователь скрыл имя, 27 Марта 2011 в 14:09, курсовая работа
Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий.
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .3
1 Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Методы составления начального опорного плана . . . . . . . . . . . . .11
3 Методы решения транспортной задачи
3.1Диагональный метод, или метод северо-западного угла . . . . . . 12
3.2 Метод наименьшей стоимости . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Метод потенциалов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14
4. Транспортная задача с избытком заявок . . . . . . . . . . . . . . . . . . . 22
5. Пример решения транспортной задачи . . . . . . . . . . . . . . . . . . . . .24
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31
Список использованных источников . . . . . . . . . . . . . . . . . . . . . . . . .32
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+v
| Магазины
Склад |
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 |
| А1
(а1=50)
U1=0 |
1,0 | 2,0 | 3,0 | 2,5 | 3,5 | 0 |
| А2(а2=20)
U2=-0,6 |
0,4 | 3,0 | 1,0 | 2,0 | 3,0 | 0 |
| А3(а3=75)
U3=-1 |
0,7 | 1,0 | 1,0 | 0,8 | 1,5 | 0 |
| А4(а4=80)
U4=-0,3 |
1,2 | 2,0 | 2,0 | 1,5 | 2,5 | 0 |
Стоимость 2-ого плана:
D2=1•20+2•30+0,4•20+1•20+
Имеем: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+v
| Магазины
Склад |
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 |
| А1 (а1=50)
U1=0 |
1,0 | 2,0 | 3,0 | 2,5 | 3,5 | 0 |
| А2(а2=20)
U2=-0,6 |
0,4 | 3,0 | 1,0 | 2,0 | 3,0 | 0 |
| А3(а3=75)
U3=-1 |
0,7 | 1,0 | 1,0 | 0,8 | 1,5 | 0 |
| А4(а4=80)
U4=-0,3 |
1,2 | 2,0 | 2,0 | 1,5 | 2,5 | 0 |
Стоимость 3-его плана:
D3=1•35+2•15+0,4•5+1•15+0,
Имеем: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+v
| Магазины
Склад |
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 |
| А1 (а1=50)
U1=0 |
1,0 | 2,0 | 3,0 | 2,5 | 3,5 | 0 |
| А2(а2=20)
U2=-0,6 |
0,4 | 3,0 | 1,0 | 2,0 | 3,0 | 0 |
| А3(а3=75)
U3=-1 |
0,7 | 1,0 | 1,0 | 0,8 | 1,5 | 0 |
| А4(а4=80)
U4=0 |
1,2 | 2,0 | 2,0 | 1,5 | 2,5 | 0 |
Стоимость
4-ого плана: D4=1•35+2•15+0,4•5+1•15+1•35+
Для всех клеток последней таблицы выполнены условия оптимальности:
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 ; 2=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 для их последующей
перевозки в другие магазины.