Транспортная задача линейного программирования
Транспортная задача с избытком заявок.
Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления Am+1 с запасом am+1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.
Задача, двойственная к транспортной.
Построим
задачу, двойственную
к транспортной.
С этой целью
вспомним, что
каждому пункту
отправления
и назначения
отвечает определенное
ограничение
В
то же время
каждому ограничению
из (6.1) сопоставляется
определенная
неизвестная
в двойственной
задаче. Тем
самым устанавливается
соответствие
между всеми
пунктами
и
и всеми неизвестными
двойственной
задачи.
Обозначим
неизвестную
в двойственной
задаче, отвечающую
пункту отправления
,
через
,
а пункту назначения
– через
.
Каждому
неизвестному
в транспортной
задаче соответствует
ограничение,
связывающее
неизвестные
в двойственной
задаче. Неизвестное
входит ровно
в два ограничения
системы (6.1): одно
из них отвечает
пункту
,
а другое – пункту
.
В обоих этих
уравнениях
коэффициент
при
равен 1. Поэтому
соответствующее
ограничение
в двойственной
задаче имеет
вид
.
Правая
часть неравенства
(6.2) равна
, потому
что именно с
этим коэффициентом
неизвестная
входит в минимизируемую
формулу (2.4).
Оптимизируемая форма двойственной задачи имеет вид
Таким
образом, задача
двойственная
к транспортной
формулируется
следующим
образом. При
ограничениях
(6.2) максимизировать
формулу (6.3). Подчеркнем,
что знак значений
неизвестных
и
может быть
произвольным.
Предположим,
что нам известно
некоторое
допустимое
базисное решение
транспортной
задачи, в котором
все базисные
неизвестные
строго положительны.
Это решение
оптимально
лишь в том случае,
когда соответствующая
ей система
оказывается
совместной.
Эта система
возникает из
системы (6.2), если
в ней все неравенства,
отвечающие
базисным неизвестным
заменить
точными равенствами.
В итоге приходим к соотношению:
(для
всех свободных
неизвестных
)
Тем самым мы убеждаемся, что признак оптимальности в работе по методу потенциалов совпадает с необходимым и достаточным условием оптимальности.
7.Пример решения транспортной задачи.
В городе N имеется 4 склада Аi, на которых хранится ткань (в рулонах) и 5 магазинов Bj, занимающихся продажей ткани. Ниже, в таблице, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок.
|
Склад |
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.Имеем таблицу:
|
Склад |
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) (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+40v1+50v2+15v3+75v4+40v5+5v6) (1*)
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) |
|
|
|
|
|
0 |
| А2(а2=20) |
|
3,0 | 1,0 | 2,0 | 3,0 | 0 |
| А3(а3=75) |
|
|
1,0 |
|
1,5 | 0 |
| А4(а4=80) |
1,2 |
2,0 |
|
|
|
|
1,0
2,0
1,0
0,8
2,0
1,5
2,5
0Стоимость 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.Составим таблицу:
|
Склад |
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 |
|
U1=0 |
|
|
|
|
|
0 |
|
U2=-1,3 |
|
|
|
|
|
0 |
|
U3=-1 |
|
|
|
|
|
0 |
|
U4=-0,3 |
|
|
|
|
|
|
А1
(а1=50)
3,5
3,0
1,0
3,0
А4(а4=80)
1,2В верхнем левом углу здесь и далее записываем значение 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. Составим таблицу:
|
Склад |
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 |
|
U1=0 |
|
|
|
|
|
0 |
|
U2=-0,6 |
|
|
|
|
|
0 |
|
U3=-1 |
|
|
|
|
|
0 |
|
U4=-0,3 |
|
|
|
|
|
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: |
2,0
1,0
3,0
А3(а3=75)
А4(а4=80)