Автор работы: Пользователь скрыл имя, 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
X = x31 x32 x33 x34 x35 x36 - матрица перевозок.
x41 x42 x43 x44 x45 x46
min(x11+2x12+3x13+2,5x14+
(1)
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
x11+x21+x31+x41=40 (2)
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+
u1+v1≤1
u1+v2≤2
u1+v3≤3 (2*)
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 ) (3*)
Будем искать первоначальный план по методу наименьшей стоимости:
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.Составим таблицу.
Здесь и далее в нижнем правом углу записываем
значение перевозки.
| Магазины
Склад |
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 |
Стоимость 1-ого плана:
D1=2•50+0,4•20+0,7•20+0,8•
Будем улучшать этот план методом потенциалов: 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.Составим таблицу:
| Магазины
Склад |
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 |
| А1 (а1=50)
U1=0 |
1,0 | 2,0 | 3,0 | 2,5 | 3,5 | 0 |
| А2(а2=20)
U2=-1,3 |
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 |
В верхнем левом углу здесь и далее записываем значение 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,