Черненко В.Д. Высшая математика в примерах и задачах (том 3)
Подождите немного. Документ загружается.
130
гпава 24
У1
У1
У2
Уз
У*
*,
1
3
-5
-1
2
2
1
1
X/
-1
1
-2
2
©,
0
0
-^2
-2
-1
1
3
1
1
-1
-1
^i
1
1
-1
-1
0
0
1
1
Отрицательный свободный член
-5.
Отрицательные чле-
ны в 1-м и 3-м
столбце.
Выбираем любой столбец, пусть с чле-
ном-2,
т. е. 1-й . Одинаковые знаки со свободным членом во
2-й и 3-й строке. Находим отношение: -5/-1 =2,5 и 2/1=2. Сле-
довательно, разрешающий элемент
1
и замена
х^<г^
у^. Разре-
шающий элемент обведем кружком
Я
=
1 •
Новые табличные ко-
эффициенты вычисляем по алгоритму (2°.) и записываем в ниж-
нем левом углу. Заполняем новую таблицу
л
У1
У2
^/
У4
ь.
3
2
-1
1
2
2
1
0
У1
1
3
2
-2
1
1
0
2
•^2
-1
2
3
-3
1
1
-1
2
Xj
1
1
©-,
0
0
1
1
Отрицательные члены
уже
меньше.
Повторяем вычисления.
Отрицательным является последний элемент во второй строке.
Одинаковые знаки со свободными членами в первой и четвер-
той строке. Строка с нулевым членом не учитывается. Для вы-
бора строки составляем отношение 3/1= 3; -1/-1= 1; 1/1 = 1.
Возьмем замену
х^<г^
у^, тогда
Я
= -1 и находим новые
коэффициенты. Таблица будет
ПИНЕЙНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
131
Уг
У1
^5
""l
У4
bi
2
1
2
0
Уз
3
-2
1
+2
^2
+2
3
1
+2
-^j
1
-1
0
1
Все свободные члены неотрицательны yj-2\x^- l;Xj
=
2;
У4
~ 0;
j^3
= 0;
Х2
=
0;
j;^
= 0. Это и будет опорное решение.
4.2.
Даны ограничения:
j^j
= 2 - (xj + ^2 - 2x3);
Уг^ 1
-(A:I-X2
+^з);
;;з = 5-(х2+хз);
;;4 = 2-(2xi-X2).
Найти минимум функции L =
О
- (-
Xj
+ 2л'2 + .^з).
Решение. Опорное решение существует, но оно не оптималь-
ное,
т.к. при увеличении
х^,
х^ функция L убывает. Запишем ре-
шение в виде таблицы
L
Ух
Уг
Уъ
У4
ь.
0-1
2 4
1 1
' 4
2 2
X,
-'-2
1 3
' 1
«-I
2 2
^2
2 3
' -1
-1 -1
' 2
-^1
X,
' -1
-ч
©.
' -1
« 0
Возьмем
^3
разрешающим столбцом. Одинаковые знаки
со свободными членами в строках у2, у^ Отношение в строке
у2
—
1/1
=
1;
3^3
— 5/1=5, следовательно, разрешающий элемент
в строке
>'2
и Я=
1/1
=
1.
Находим остальные коэффициенты и
запишем другую таблицу
132
Гпава 24
L
Ух
X,
Уз
У4
6,
-1
-7
' 6
1 3
4 2
2 4
X,
-2
I
2
3 5
2
1 1
2
-1 1
2
2 3
2
^
3
3
2
-1 .
2
-1 1
2
2
-1 1
2
^^
-1
1
2
2 3
2
1 1
3
-1 1
2
0 ,
2
В верхней строке есть положительный коэффициент Х2. В
этом столбце единственное положительное отношение
с
элемен-
том строки
у^.
Выбираем разрешающий элемент, находим
Я =
-,
вычисляем остальные коэффициенты и получим таблицу
L
Ух
Хз
^
УА
6,
-7
-9
' 4
^ 1
2 4
^ 6
X,
1
2 4
3
5
Y 5
3
1
2 _i
3
1
-2 i
3
3
2 7
3
Уз
3
-2 _5
3
1
2 i
3
1
2 i
3
1
2 2
3
1
^ 2
3
Уг
1
2 _i
3
©}
1
2 _i
3
1
"2 i
3
1
-т 1
3
Так как у^ положительно, то находим отношения
6
/
—
= 4,
1 3 2^
3
/
—
= 6 и разрешающий элемент
—.
Находим
Я
= -
и
запишем
таблицу
ПИНЕИНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
133
L
Уг
h
Ч
УА
6,
-9
4
1
4
6
X,
4
3
5
3
1
3
1
3
7
3
Уз
5
3
1
3
1
3
2
3
2
3
У1
~3
2
3
1
3
1
3
1
3
Поскольку все члены отрицательны, то функция L имеет
min L = -9 при х^=у^=у^=0. Таким образом:
1) Если в строке L нет положительных элементов помимо
свободного члена, а в столбце нет отрицательных членов поми-
мо L, то оптимальное решение достигнуто.
2) Если в строке L есть положительный элемент, а в столб-
це нет ни одного положительного, то линейная функция не огра-
ничена снизу и оптимального решения не существует.
24.5.
Транспортная задача
V. Пусть имеется т пунктов отправления
А-,...,
А^, в кото-
рых сосредоточены запасы однородного груза в количестве со-
ответственно
flfj,
..., <^jn единиц. Кроме того, имеется п пунктов
назначения 5р ..., В^, подавших заявки соответственно на
Ь^,
bj^
...,
fej^
единиц. Предполагается, что сумма всех заявок равна сумме
всех запасов.
(1)
/=1
/=1
Известна стоимость
с.^
перевозки единицы товара от каж-
дого пункта отправления
А-^
до каждого пункта назначения В
(задана матрицей)
134
Гпава 24
'12
'\п
'21
'22
'2л
'ml
'ml
Требуется составить такой план перевозки, при котором все
заявки были бы выполнены, а стоимость была бы минимальна.
Поскольку критерием эффективности является стоимость, то та-
кая задача называется
транспортной задачей по критерию
сто-
имости.
Обозначим за х^^ — количество груза, отправляемого из
/-ГО пункта Л. ву-й пункт В
{г
=
1,
..., т\] =
1,
..., п).
х..^
— не-
отрицательные переменные т х п должны удовлетворять ус-
ловиям:
1.
Суммарное количество груза, направляемое из каждого
пункта отправления во все пункты назначения, должно равнять-
ся запасу груза на данном пункте. Это дает нам т условий ра-
венств:
/=1 /=1 /=1
(2)
2.
Суммарное количество груза, доставляемое в каждый
пункт назначения изо всех пунктов отправления, должно быть
равно заявке, поданной данным пунктом.
Это дает п условий-равенств
т.
т т
/=1 i=\ i=]
3.
Суммарная стоимость всех перевозок, т. е. сумма вели-
чин
Х-J,
умноженная на соответствующие стоимости
c^j,
должна
бьггь минимальна
/=1 /=1
mm.
ПИНЕЙНОЕ И аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
135
2°.
Совокупность переменных
х.^.
называется допустимым
планом перевозок, если удовлетворяются условия (2) и (3). План
х.^.
— называется оптимальным, если среди допустимых он га-
рантирует минимальную стоимость. Для решения транспортной
задачи составим таблицу 5.1, где ПН — пункты назначения;
ПО — пункты отправления; стоимости перевозок
с-^.
располо-
жены в правом верхнем углу, с тем, чтобы в самой ячейке при
составлении плана помещать перевозки
х-^..
Ячейки таблицы, в
которых будем записывать отличные от нуля перевозки х.., бу-
дем называть базисными, остальные — свободными.
Число строк т и сумма запасов в каждой строке должна
быть равна запасу данного ПО. Число столбцов равно п и сум-
ма перевозок должна равняться заявке ПН. Клетку будем опре-
делять номерами
/,
j.
Таблица 5.1
^,
А,
К
Заявки 6.
^1
Сц
^21
Cml
h
В,
^12
Ч\
Cml
Ьг
к
Сщ
':2п
mn
К
Запасы
а-^
а,
«2
'^т
т п
/=1 /=1
3°.
Решение транспортной задачи разбивается на нахожде-
ние опорного плана
и
приближение посредством последователь-
ных итераций к оптимальному решению.
Исходя из чисто физических соображений ясно, что опор-
ное решение всегда существует.
136
Гпава 24
4°.
Выролсденный
план
перевозок. Такой план может встре-
гиться как при построении опорного плана, так и при его улуч-
шении. Действительно, не все т
+ п
уравнений (2), (3) являются
независимыми. Так, складывая все уравнения (2), (3), получим
уравнение
(1),
т- е- независимых уравнений будет т
+
п-Х, Сле-
цовательно, ранг системы (2), (3) и число базисных переменных
будет г =
m
+
/2
-1,
а число свободных переменных k
=
mn-r =
= (т-\)(п-1)
.
Рассмотрим пример 5.2, когда число базисных
переменных меньше г.
5°.
Улучшение плана
перевозок.
Возьмем транспортную таб-
лицу из m = 5 строк и п = 6 столбцов. Циклом в транспортной
таблице мы будет называть несколько клеток, соединенных зам-
кнутой ломаной линией, которая в каждой клетке делает пово-
рот на 90°. В таблице 5.2 показан цикл с вершинами (1,1),
(1,3),(3,3), (3,1) и цикл Cj^, Cj^, С^^, С^^, С^^, С^^, С^^, С^^ .
Стрелками показано направление обхода. Знаком «+» обозна-
чим те вершины, в которых перевозки увеличиваются, а «~» — в
которых перевозки уменьшаются.
Таблица 5,2
А,
^2
^3
^4
As
h
Bi
Си
f
с„|
с^,
Csj
ь,
^2
С,2
С
1
с,,
С42
С52
Ь2
Bs
^^-
1
^23
'С„
С43
Сзз
Ьз
1
^4
Си
i
Т с
^24
i
Cs4
С 44
1
\С54
К
Вз
С,5
С25
^
Сл
Q
С55\
Ьз
Вб
С,б
1 и^!
r~cJ
Сзб\
1
<^^бТ
Сзв
Ьб
«,•
«/
«2
1
"^
1
""
«5
ПИНЕИНОЕ
И
аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
137
При переносе любого числа единиц
по
циклу равновесие
между заявками и запасами не меняется. Ценой
цикла
называет-
ся увеличение стоимости перевозок при перемещении одной еди-
ницы груза по означенному циклу
и
цена равна алгоритмичес-
кой сумме стоимостей
Cjj-
Cj^
+
C^Q
- C^j.
Очевидно, для улучшения плана перевозок перемещать груз
следует только по тем циклам, цена которых отрицательна, т.
е.
стоимость
в
этих случаях уменьшится. Если циклов
с
отрица-
тельной ценой не осталось, то дальнейшее улучшение невозмож-
но.
Знак «+» выбирается в свободной клетке.
5.1.
Пусть задана транспортная таблица
5.3.
Требуется най-
ти
опорный план.
Таблица
5.3
^'
^2
As
^4
Заявки
bj
^1
10
6
8
7
18
^2
8
7
7
5
27
^3
5
8
10
4
42
^4
6
6
8
6
12
^5
9
5
7
8
26
Запасы
а.
48
30
27
20
125
Решение. Воспользуемся правилом северо-западного угла,
т.
е.
будем заполнять таблицу с левого верхнего угла.
Пункт В
J
подал заявку
на
18 единиц груза, поэтому удов-
летворим эту заявку за счет запаса
48,
имеющихся
в
пункте ^
У
,
и запишем перевозку
18 в
клетке (1,1). Заявку В2
в 27
единиц
также удовлетворим за счет запасов пункта ^
У И
запишем пере-
возку
в
27 единиц
в
клетке (1,2); оставшиеся 3 единицы пункта
А J
назначим пункту
В^. В
заявке пункта
В^
осталось
не-
138 Гпава 24
удовлетворенным
39
единиц; из них 30 единиц удовлетворим за
счет пункта
У4^
,
причем его запас будет исчерпан, а
9
возьмем из
пункта
У4^
.
Из оставшихся
18
единиц пункта Л
^ 12
вьщелим пун-
кту В^ , а оставшиеся 6 единиц В^ , что вместе с 20 единицами
пункта А^ покроет заявку пункта В^
Полученное решение (табл.5.4) является не только до-
пустимым, но и опорным. Поскольку при построении ре-
шения стоимость перевозок е.. не учитывали, то план по-
лучился не оптимальным. Стоимость плана равна сумме
произведений перевозок на соответствующую стоимость
18-10+27-8+3-5+30-8+910+12-8+6-7+20-8 = 1039.
Таблица 5.4
\\пн
\по \^
^/
^2
Аз
^4
Заявки Ъ.
в,
18 >«
6
8
7
18
^2
11 '
7
7
5
27
^3
3 '
30 '
9 '0
4
42
^4
6
6
12 '
6
12
^5
9
5
6 '
20 '
26
Запасы а.
48
30
27
20
125
Попробуем улучшить план. Для этого перенесем из клетки
(1,1)
18
единиц в клетку (2,1) и, чтобы не нарушить баланс, пе-
ренесем также 18 единиц из клетки (2,3) в клетку (1,3)- Полу-
чим новый план (табл.5.5). Найдем суммарную стоимость пе-
ревозок нового плана 27-8+21-5+18-6+12-8+9-10+
+
12-8+6-7+20-8 = 913.
На этом способе уменьшения стоимости в дальнейшем бу-
дет основан алгоритм оптимизации плана перевозок.
ПИНЕЙНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
139
\по ^\
^1
^2
As
^4
Заявки Ъ.
^1
10
6
18
8
7
18
^2
8
27
7
7
5
27
^i
5
21
8
12
10
9
4
42
^4
6
6
8
12
6
12
^5
9
5
7
6
20 «
26
Таблица 5.5
Запасы а.
48
30
27
20
125
5.2.
Дана транспортная таблица 5.6. Составить опорный
план перевозок.
Таблица
5.6
\по
^\
А,
^2
As
А4
Заявки Ъ.
«;
5
^2
5
^s
20
^4
35
^.
10
Запасы а.
10
30
25
10
75
Решение. Применяя способ северо-западного угла, получим
табл.5.7.
Особенностью полученного плана является то, что в нем
шесть, а не восемь г = т+п-1=8 базисных перевозок. Это
произошло из-за того, что при распределении запасов по пунк-
там назначения в некоторых случаях остатки оказывались рав-
ными нулю и в соответствующую клетку не попали.