15.5. Решение транспортной параметрической задачи.
.
Определить оптимальное решение перевозок, обеспечивающее минимальные транспортные затраты.
¦ В матрицу расходов введем параметр t, где t??0,3?. Получим
Полагая t=0, решим задачу методом потенциалов и определим оптимальное решение перевозок. Транспортная таблица этого решения будет иметь вид:
| bj ai | 80 | 120 | 150 | 50 | ui |
| 100 | 5+2t 30
| 4-t 70
| 8
-3+4t | 3+t
-1+t |
0 |
| 200 | 4 50
| 7
-4-3t | 4+2t 150
| 7-t
-6+t |
-1-2t |
| 100 | 5
-1+3t | 3 50
| 6
-2+5t | 1+3t 50
|
-1+t |
| vj | 5+2t | 4-t | 5+4t | 2+2t |
|
В таблице ui и vj – потенциалы строк и столбцов. Для занятых клеток они определяются из условия
ui+vj=
.
Полагая и1=0, из этой системы уравнений получаем значения остальных потенциалов.
Оценки свободных клеток находим по формуле
?ij=ui+vj-().
Решение, полученное при t=0, является оптимальным для всех значений параметра t, удовлетворяющих условию
?ij?0, или ?ij+?ijt?0.
Имеем
t1=mах(-?ij/?ij)=-?22/?22=-4/3, ?ijlt;0;
t2=min(-?ij/?ij)=min(-?13/?13;-?14/?14;-?24/?24;-?31/?31;-?33/?33)=
=min(3/4;1;6;1/3;2/5)=1/3, ?ijgt;0.
Так как по условию задачи t?0, то оптимальное решение сохраняется при 0?t?1/3. При этом матрица развозок Х* имеет вид
Х*=
,
а минимальная стоимость транспортных расходов составляет
z*=30·(5+2t)+70·(4-t)+50·4+150·(4+2t)+50·3+50·(1+3t)=1430+440t.
Таким образом, при 0?t?1/3 z*=1430+440t и
Х*=.
Чтобы получить оптимальное решение при t?1/3, перераспределим поставки товаров в ячейку (3,1), где t2=1/3. Вновь полученное распределение имеет вид:
| bj ai | 80 | 120 | 150 | 50 | ui |
| 100 | 5+2t
1-3t | 4-t 100
| 8
-2+t | 3+t
-1+t |
0 |
| 200 | 4 50
| 7
-5 | 4+2t 150
| 7-t
-7+4t |
-2+t |
| 100 | 5 30
| 3 20
| 6
-1+2t | 1+3t 50
|
-1+t |
| vj | 6-t | 4-t | 6+t | 2+2t |
|
Определим пределы изменения t:
t1=-?11/?11=1/3, ?ijlt;0;
t2=min(-?13/?13;-?14/?14;-?24/?24;-?33/?33)=
=min(2;1;7/4;1/2)=1/2, ?ijgt;0.
Полученное в таблице оптимальное решение сохраняется при 1/3?t?1/2. При этом z*=1460+350t и
Х*=.
Перераспределим поставки грузов в клетку (3,3), где t2=1/2. Получим новое распределение:
| bj ai | 80 | 120 | 150 | 50 | ui |
| 100 | 5+2t
2-5t | 4-t 100
| 8
-1-t | 3+t
-1+t |
0 |
| 200 | 4 80
| 7
-6+2t | 4+2t 120
| 7-t
-8+6t |
-3+3t |
| 100 | 5
1-2t | 3 20
| 6 30
| 1+3t 50
|
-1+t |
| vj | 7-3t | 4-t | 7-t | 2+2t |
|
Определяем пределы изменения t:
t1=mах(-?11/?11;-?13/?13;-?31/?31)=mах(2/5;-1;1/2)=1/2, ?ijlt;0;
t2=min(-?14/?14;-?22/?22;-?24/?24)=
=min(1;3;4/3)=1, ?ijgt;0.
Оптимальное решение сохраняется при 1/2?t?1. При этом z*=1490+290t и
Х*=
.
Перераспределим поставки грузов в клетку (1,4), где t2=1. Получим новое распределение:
| bj ai | 80 | 120 | 150 | 50 | ui |
| 100 | 5+2t
2-5t | 4-t 50
| 8
-1-t | 3+t 50
|
0 |
| 200 | 4 80
| 7
-6+2t, | 4+2t 120
| 7-t
-7+5t |
-3+3t |
| 100 | 5
1-2t | 3 70
| 6 30
| 1+3t
1-t |
-1+t |
| vj | 7-3t | 4-t | 7-t | 3+t |
|
Пределы изменения t:
t1=mах(-?11/?11;-?13/?13;-?31/?31;-?34/?34)=mах(2/5;-1;1/2;1)=1, ?ijlt;0;
t2=min(-?22/?22;-?24/?24)=min(3;7/5)=7/5, ?ijgt;0.
Полученное оптимальное решение сохраняется при 1?t?7/5. При этом z*=1540+240t и
Х*=
.
Перераспределим поставки грузов в клетку (2,4), где t2=7/5:
| bj ai | 80 | 120 | 150 | 50 | ui |
| 100 | 5+2t
| 4-t 100
| 8
| 3+t
|
0 |
| 200 | 4 80
| 7
| 4+2t 70
| 7-t 50
|
-3+3t |
| 100 | 5
| 3 20 | 6 80 | 1+3t
|
-1+t |
| vj | 7-3t | 4-t | 7-t | 10-4t |
|
Оценки свободных клеток:
?11=2-5t, ?13=-1-t, ?14=7-5t, ?22=-6+2t, ?31=1-2t, ?34=8-6t.
Пределы изменения t:
t1=mах(-?11/?11;-?13/?13; -?14/?14;-?31/?31;-?34/?34)=mах(2/5;-1;7/5;1/2;4/3)=7/5, ?ijlt;0;
t2=min(-?22/?22)=min(3)=3, ?ijgt;0.
Полученное оптимальное решение сохраняется при 7/5?t?3. При этом z*=1890-10t и
Х*=
.
Т.к. t2=3=?, то решение задачи закончено. ?