Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А
4.5.10 78 x1 |
+ |
52 x2 |
min, 4.5.11 |
5 x1 |
+ 4 x2 |
min, |
|
6 x1 + |
2 x2 |
9, |
x1 + x2 |
6, |
|||
10 x1 + 14 x2 |
13, |
2 x1 |
+ |
x2 |
9, |
||
11 x1 |
|
x2 |
6; |
3 x1 |
+ |
x2 |
11. |
4.6. Задача линейного программирования транспортного цеха
|
|
|
ЗЛП транспортного цеха формулируется следующим |
||||||||
образом: пусть имеется m пунктов отправления |
A1 , A2 ,…, Am , в |
||||||||||
которых сосредоточен однородный груз, и |
n пунктов назначения |
||||||||||
B1 , |
|
B2 ,…, Bn . Заданы количество груза ai , i |
|
|
|
|
|
|
|
||
|
|
1, m в каждом пункте |
|||||||||
Ai |
и размеры спроса каждого пункта bj , j |
|
|
|
|
|
|||||
1, n в одних и тех же |
|||||||||||
|
|
|
|
|
|
||||||
единицах измерения. Известна также матрица C |
(cij ) , i 1, m , |
||||||||||
|
|
|
|
||||||||
j |
1, n расходов cij на перевозку единицы продукции из пункта Ai |
||||||||||
в пункт Bj . Необходимо определить такой план перевозки, который
бы обеспечивал вывоз всех грузов из пунктов отправления, удовлетворение всех потребностей в пунктах назначения и имел бы минимальную стоимость.
В случае, если выполняется равенство
m |
n |
ai |
bj (условие баланса), |
i 1 |
j 1 |
задача называется закрытой транспортной задачей. В противном случае – открытой.
Для разрешимости транспортной задачи необходима и достаточна еѐ закрытость.
Математическая постановка закрытой транспортной задачи имеет следующий вид:
m n
cij xij min |
(4.6.1) |
i 1 j 1
при ограничениях
118
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xij |
|
|
|
ai , |
|
i 1, m ; |
|
|
|
|
(4.6.2) |
|||||||||
|
|
|
|
j 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xij |
|
|
|
bj , |
|
|
j |
1, n ; |
|
|
|
|
(4.6.3) |
|||||||
|
|
|
|
i 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xi |
0 , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
i |
1, m , |
|
j |
1, n , |
|
(4.6.4) |
|||||||||||||
где xij |
- количество продукта, перевозимое из пункта Ai в пункт Bj , |
||||||||||||||||||||||||
ai 0 , |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
i 1, m и bj |
|
0 , |
j |
|
1, n . Любая допустимая точка задачи |
||||||||||||||||||||
может быть записана в виде матрицы |
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
x11 ... |
|
x1n |
|
|
|||||||||
|
|
|
|
X |
(xij ) |
... ... ... . |
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
xm1 |
|
... xmn |
|
|
|||||||||
|
Для приведения открытой задачи к закрытой необходимо |
||||||||||||||||||||||||
выполнить следующие действия: |
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m |
|
n |
|
1) если запасы больше потребностей: |
ai |
bj , |
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i 1 |
|
j 1 |
|
вводится фиктивый n+1 пункт назначения. Его |
||||||||||||||||||||||||
|
потребность bn |
1 |
|
|
|
ai |
|
bj , а тарифы |
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
Ci,n 1 |
0 |
i |
1, m. |
|
|
|
|
|
|
|
|
|
||||||||||||
|
2) Если |
ai |
|
|
|
|
bj |
, то вводится фиктивный (m+1)-й пункт |
|||||||||||||||||
|
отправления, его запас am 1 |
|
|
bj |
ai |
, |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
Сm 1, j |
0 |
i |
|
1, m. |
|
|
|
|
|
|
|
|
|
|||||||||||
Рассмотрим два метода нахождения исходной базисной точки для транспортной задачи: метод "северо-западного угла" и метод минимального элемента.
4.6.1. Метод "северо-западного угла"
Алгоритм построения исходной базисной точки складывается из нескольких шагов, на каждом из которых
119
определяется верхний левый элемент матрицы X. |
|
|
|
|||||||||||||||
|
1. Полагаем i |
1 |
, j |
0 |
1 |
, |
a' |
|
a , |
b' |
|
b |
j |
, i |
1, m , j |
1, n . |
||
|
|
|
0 |
|
|
|
|
i |
|
i |
j |
|
|
|
|
|||
|
2 Полагаем |
x |
|
min(a' |
,b' |
) . Если x |
|
|
a' , то |
|
||||||||
|
|
|
i0 j0 |
|
|
i0 |
j |
0 |
|
|
i0 j0 |
|
i0 |
|
||||
|
переходим к шагу 3, в противном случае к шагу 5. |
|
||||||||||||||||
|
3. Полагаем b' |
|
b' |
|
x |
j0 |
. Индексу i |
присваиваем |
|
|||||||||
|
|
|
j0 |
|
j0 |
|
i0 |
|
|
|
|
0 |
|
|
|
|
|
|
|
значение i0 |
1. Если i0 |
m , то переходим к шагу 4, в |
|
||||||||||||||
|
противном случае к шагу 2. |
|
|
|
|
|
|
|
|
|
||||||||
|
4. Полагаем |
x |
j |
b' |
для всех |
j |
j |
. Решение закончено. |
||||||||||
|
|
|
i0 |
j |
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
5. Полагаем |
a' |
|
a' |
|
x |
j0 |
. Индексу |
j |
присваиваем |
|
|||||||
|
|
|
i0 |
|
i0 |
|
i0 |
|
|
|
|
0 |
|
|
|
|
|
|
|
значение |
j0 |
1. Если |
j0 |
|
n , то переходим к шагу 6, в |
|
|||||||||||
|
противном случае переходим к шагу 2. |
|
|
|
|
|
||||||||||||
|
6. Полагаем |
x |
|
a' |
для всех i |
i |
. Решение закончено. |
|||||||||||
|
|
|
ij0 |
|
i |
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
Рассмотрим пример использования данного алгоритма |
|
||||||||||||||||
Пример 1. Исходные данные: |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
bj |
30 |
|
36 |
|
|
|
36 |
|
|
|
|
22 |
|
|
|
56 |
|
|
ai |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
45 |
3 |
|
|
|
4 |
|
|
|
|
|
2 |
|
|
|
|
4 |
|
5 |
30 |
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
70 |
3 |
|
|
|
1 |
|
|
|
|
|
4 |
|
|
|
|
2 |
|
4 |
|
|
21 |
|
|
|
36 |
|
|
|
|
13 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
15 |
4 |
|
|
|
3 |
|
|
|
|
|
5 |
|
|
|
|
3 |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
50 |
2 |
|
|
|
4 |
|
|
|
|
|
3 |
|
|
|
|
6 |
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
50 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В |
верхнем |
правом |
|
углу |
|
|
в |
каждой |
|
ячейке |
стоят |
|||||||
коэффициенты cij , |
i |
1,4 , |
j 1,5 . Данная задача является закрытой |
|||||||||||||||
транспортной задачей, так как сумма потребностей в продукте равна |
||||||||||||||||||
сумме имеющегося продукта |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
45+70+15+50=30+36+36+22+56. |
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
120 |
|
|
|
|
|
|
|
|
|
||
Результаты работы алгоритма записаны в нижнем левом углу ячейки. Получена исходная базисная точка
|
30 |
15 |
0 |
0 |
0 |
|
X |
0 |
21 |
36 |
13 |
0 |
|
0 |
0 |
0 |
9 |
6 |
||
|
||||||
|
0 |
0 |
0 |
0 |
50 |
со значением целевой функции, равным 804.
Метод "северо-западного угла" может оказаться очень "далеким" от оптимального, так как при построении начальной базисной точки этим методом мы совсем не реагируем на
коэффициенты целевой функции cij . Более близкие к оптимальным точки можно получить с помощью метода минимального элемента.
4.6.2.Алгоритм метода минимального элемента
1.Полагаем ai' ai , b'j bj , (i, j) 
, где
(i, j) : i 1, m, j 1, n .
2. |
Определяем пару индексов (i0 , j0 ) из условия |
min cij ci0 j0 . |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
(i, j ) |
3. |
Полагаем x |
min(a' |
,b' ) . Если |
x |
a' |
, то переходим к |
||||||
|
i0 j0 |
|
|
|
|
i0 |
j0 |
|
|
i0 j0 |
i0 |
|
|
шагу 4, в противном случае - к шагу 7. |
|
|
|||||||||
4. |
Полагаем b' |
b' |
|
|
x . |
|
|
|
|
|
||
|
j0 |
j0 |
|
|
|
i0 j |
0 |
|
|
|
|
|
5. |
(i0 , j) : j 1, n . |
|
|
|
|
|
|
|||||
6. |
Если множество |
|
|
состоит из элементов одной строки ik , то |
||||||||
|
полагаем x |
b' |
для всех (i , j) |
. Решение закончено. В |
||||||||
|
ik j |
j |
|
|
|
|
k |
|
|
|
|
|
|
противном случае переходим к шагу 2. |
|
|
|||||||||
7. |
Полагаем a' |
a' |
|
|
x . |
|
|
|
|
|
||
|
i0 |
i0 |
|
|
i0 j0 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|||
8. |
(i, j0 ) : i 1, m . |
|
|
|
|
|
|
|||||
9. |
Если множество |
|
|
состоит из элементов одного столбца jk , то |
||||||||
|
полагаем x |
a' |
для всех (i, j |
k |
) |
. Решение закончено. В |
||||||
|
ijk |
i |
|
|
|
|
|
|
|
|
|
|
противном случае переходим к шагу 2.
121
Данным методом найдем исходную базисную точку для примера 1.
Пример 2.
bj |
30 |
|
36 |
|
36 |
|
22 |
|
56 |
|
ai |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
45 |
|
3 |
|
4 |
|
2 |
|
4 |
|
5 |
|
|
|
|
36(2) |
|
|
|
9(5) |
|
|
|
|
|
|
|
|
|
|
|
||
70 |
|
3 |
|
1 |
|
4 |
|
2 |
|
4 |
|
|
36(1) |
|
|
|
22(3) |
|
12(5) |
|
|
|
|
|
|
|
|
|
|
|||
15 |
|
4 |
|
3 |
|
5 |
|
3 |
|
6 |
|
|
|
|
|
|
|
|
15(5) |
|
|
|
|
|
|
|
|
|
|
|
|
|
50 |
|
2 |
|
4 |
|
3 |
|
6 |
|
8 |
30(4) |
|
|
|
|
|
|
|
20(5) |
|
|
|
|
|
|
|
|
|
|
|
Для наглядности каждый элемент снабжен индексом, равным номеру итерации, на которой был получен данный элемент. В результате получили следующую базисную точку
0 0 36 0 9
X
0 36 0 22 12
0 0 0 0 15
30 0 0 0 20
со значением целевой функции, равным 545. Данное значение явно меньше, чем значение целевой функции на базисной точке, полученной методом "северо-западного угла".
Замечание 1. Признаком вырожденности транспортной задачи является существование r m , s n , для которых выполняется равенство
r |
s |
a i |
b j . |
|
k |
k 1 |
l 1 |
В этом случае при использовании приведенных алгоритмов может оказаться, что среди n m 1 базисных координат есть нулевые.
122