close

Вход

Забыли?

вход по аккаунту

?

3585 prudovskiy b.d matematicheskoe obespechenie asu v transportnom upravlenii

код для вставкиСкачать
40
ГОСУДАРСТВЕННЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ АВТОМОБИЛЬНОГО ТРАНСЛОРТД
№
МИНИСТЕРСТВО
АВТОМОБИЛЬНОГО
ТРАНСПОРТА
РСФСР
Государственный научно-исследовательский институт
автомобильного транспорта
Ленинградский филиал
Б. Д. ПРУДОВСКИЙ, М. Г. КЕРЗНЕР, Г. И. ТРОФИМОВА
МАТЕМАТИЧЕСКОЕ
ОБЕСПЕЧЕНИЕ АСУ
В ТРАНСПОРТНОМ УПРАВЛЕНИИ
М О СКВА «Т Р А Н С П О Р Т » 1977
осг
ХГ
УДК
656.13
65.011.56
V
М атем атическое
обеспечение А С У
в транспортном
уп р авлен и и . П р у д о в с к и й Б . Д ., К е р з н е р
- •»
Т р о ф и м о в а
Г . И . М . «Т р ан сп о р т», 1977. 88 с.
(Г о с н а у ч -исслед. ин-т авто м о би льн о го тр а н с п о р та ).
'
В книге изложены результаты работ по " р о е ^ а а НИю А С У то ан сп о р тн ы м уп р авлен и ем (Т > ), вы полненны х
Л ен и н гр ад ски м ф илиалом н аучн о-и сслед овательского ин­
с т и т у т а авто м о б и л ьн о го тр ан сп о р та;-п р и во д ятся ал го р и т­
м ы ^ р еш ен и я осн овн ы х за д а ч м а те ^ ^ 0К° ™ аХ
0Ррте
м и р о ван и я, и сп о л ьзуем ы х на а вто м «С ильном т р а н « 1орт е
о п и сы ва е тся р яд ва ж н е й ш и х авто тр ан сп о р тн ы х за д *ч и
и зл а га ю тся м етоды их реш ения; п р и во д ятся некоторы е
н о н ы ^ р е зу л ьта ты ,
п о лучен н ы е
ири
п роекти р ован и и
" ^ ^ К н и г а р ассчи та н а на н а учн ы х и инж енерно-техниче
ск и х
р аб о тн и ко в авто м о б и льн о го тр ан сп о р та, асп и р ан ­
т к и студ ен то в, сп ец и али зи р ую щ и х ся в о б л асти прим е­
нения эко н о м и ко -м атем ати чески х м етод ов на авто м о б и л ь
ном тр ан сп о р те, р аб о тн и ко в И В Ц тр ан сп о р тн ы х управлений, р а зр а б о тчи ко в А С У .
Т аб л . 2
342212
п
31803-306
049(01)-77
306-77
Б И Б Л И О Т Е К А
П азло д ар сн сго
дачгосударственны й иаучно-исследов*
© ге л ь Ж
институт а в то м о б и льн о е.
транспорта. 1977.
-
ПРЕДI И СЛО ВИ Е
Перед автомобильным транспортом нашей страны по­
ставлены большие и важные задачи. Эффективное управ­
ление транспортным процессом в настоящее время уже
невозможно только на базе интуиции, здравого смысла
и прошлого опыта. Необходимо строгое количественное
обоснование принимаемых решений, которое возможно
лишь при использовании экономико-математических ме­
тодов. Большие возможности в использовании резервов
автомобильного транспорта, дальнейшем повышении
эффективности его работы появляются в связи с широ­
ким и повсеместным внедрением автоматизированных
систем управления транспортными управлениями (АСУ
Т У ).
Одно из центральных мест в автоматизированной си­
стеме управления занимает подсистема математического
обеспечения.
И это, конечно, не случайно, так как при помощи этой
подсистемы осуществляется непосредственная разработ­
ка сначала технического, а затем и рабочего проектов
автоматизированной системы управления.
Действительно, трудно представить успешную разра­
ботку постановок задач и з&дфтй^н^ВД программирова; ние без широкого арсеналаЛЛп^ьйс^математических ме­
тодов и, в первую очередь, методов оптимизации принимаемых решений. Точно так же весьма сомнительно
доведение алгоритмов этих задач до рабочих программ
без использования различных видов программного обес­
печения.
Не составляет исключение и автоматизированная- си­
стема управления транспортным управлением.
Подсистема математического (обеспечения АСУ ТУ
включает в себя математические методы, используемые
при решении задач, и все виды программного обеспече­
ния (машинное, общесистемное и специальное).
На автомобильном транспорте из математических ме­
тодов наибольшее применение находят методы матема­
тического программирования, описанию которых и посвя­
щена данная книга.
■",/
:■
Программное обеспечение в данной книге не рассмат­
ривается.
Л- - л
Наличие в книге подробных вычислительных алгорит­
мов решения общих задач оптимизации, большое коли­
чество рассмотренных автотранспортных задач и иллю­
стративных примеров позволяют авторам надеяться, что
книга окажется полезной для специалистов автомобиль­
ного транспорта.
1
Авторы заранее признательны тем читателям, кото­
рые пожелают высказать критические замечания по по­
воду содержания книги.
'ш И Ш
Глава 1 Л И Н ЕЙ Н О Е ПРОГРАМ М ИРОВАНИЕ
1.1. Общая задача
В настоящее время известно много методов решения
задач линейного программирования. Все эти методы
можно подразделить по числу итераций на конечные и
бесконечные.
К первой группе относятся: симплексный метод (ме­
тод последовательного улучшения плана); двойственный
симплексный метод (метод последовательного уточнения
оценок); метод ведущих переменных Била; метод одно­
временного решения прямой и двойственной задач (ме­
тод последовательного сокращения невязок); методы
возможных направлений и др.
Группа бесконечных методов включает все виды ме­
тодов релаксации. Эти методы обладают плохой сходи­
мостью (требуют большого количества итераций). В
связи с этим, несмотря на незначительный объем вычис­
лений на каждой итерации, их способность конкуриро­
вать с конечными методами для задач больших размеров
сомнительна.
В литературе описаны, по крайней мере, четыре раз­
личных вычислительных алгоритма симплексного и двой­
ственного симплексного методов: прямой алгоритм
(предложен Г. Данцигом); алгоритм с обратной матри­
цей (предложен А. Чарнсом); мультипликативный алго­
ритм (предложен Г. Данцигом и В. Оргард-Хейсом) ;
модифицированный мультипликативный алгоритм (пред­
ложен Г. Зойтендейком).
Сравнение перечисленных алгоритмов показывает,
что лучшим для больших вычислительных машин явля­
ется модифицированный мультипликативный алгоритм;
для Э В М средних размеров предпочтительнее алгоритм
с обратной матрицей; для малых вычислительных машин
самым подходящим является прямой алгоритм. Кстати,
и программа этого алгоритма самая простая.
5
В связи с тем что проектирование А О Т> ориенти­
руется на Э В М средних размеров, ниже изложен алго­
ритм симплексного метода с обратной матрицей.
^
Кроме того, приводится прямой алгоритм симплексно­
го метода.
С ф о р м у л и р у е м з а д а ч у линейного программирования
след Vгащи’м о б р а з о м : минимизировать линейную фу НКцию п переменных
1
0)
при условиях
я
V
7-1
т
X) > О* I* * 1» л*
Задача (1) — (3) записана в канонической форме
(ограничения (2) заданы в виде равенств). В общем слу­
чае ограничения задаются в виде неравенств, т. е.
Л
V
7-1
(О
Однако введение вспомогательных переменных
зволяет легко свести условия (4) к виду (2).
Двойственной к задаче (П — <3) является следующая
задача
т
V
т
\
д.-у/-* шах;
Г
Ш I
У
М ежду решениями прямой ( 1) — (3) и двойственной
(5) задач существует тесная связь. В частности, если
6
Х*=|л:у) и V* =\у*\ — оптимальные решения соответст
венно прямой и двойственной задач, то
п
Л**-
т
(б)
1-1
Соотношение (6) имеет огромное значение в теории
программирования, так как позволяет свести задачу
отыскания максимума (минимума) линейной формы при
линейных ограничениях к эквивалентной задаче максиминимизации или минимаксимизации функции Лагран­
жа. Фактически это преобразование связывает прямую
оптимизацию с теорией игр, с ее седловыми точками и
минимаксными методами. Впервые эта замечательная
связь задач линейного программирования с теорией игр
была установлена в 1951 г. Г. Данцигом. Взаимное про­
никновение этих математических дисциплин оказалось
полезным для каждой из них. В частности, оказалось
возможным показать, что каждой матричнои игре двух
лиц с нулевой суммой можно привести в соответствие
задачу линейного программирования и наоборот.
Следовательно, для решения задач линейного про­
граммирования можно применять игровые методы, а для
решения матричных игр — методы линейного программи­
рования.
Все эти .вопросы представляют значительный интерес,
однако дальнейшее их обсуждение выходит за рамки
поставленной в этой работе цели.
Сформулируем задачу линейного программирования
(1) — (3) »в векторной форме:
миним-изировать функцию СХ при условиях АХ = В,
■И^М |И|И И || I.
где С= (с,, с2,
сп)
а иа 12 . . . а\п \
1=11
о
•
•
- а2п
/
|, х = |
х\
I
В
\
и изложим прямой алгоритм ее решения симплексным
методом,
7
I
\
Алгоритм 1
I а и вт.от ~п'
1. Формирование матрицы А
А
Й21^22
&1п
а?АП
1 0.
О 1.
а'т\ат2
ат п
О 0.
.
•
1
•
т
2. Формирование матрицы базиса ()
О
1 о.
о
1
.0
II Яц
^0 0 . . . . . . . 1
3. Формирование вектора С = (с ,), у = 1, т
С — (СI*
...» Сд, М , М
I
т
где М — достаточно большое число.
4. Формирование вектора Г =(/,-), /= 1 , т
Г=. (л + 1, п + 2 ,..., л-Ьш).
5. Вычисление вектора Аг(1): Х (1)= (3 -1Л,
где
Г т (1> 1
( 1)
1
г(1)
Ло
т
I ^/71 )
6. Л ’:= 0 , где
Л'
I «*т+л )
т
7. х 1.\ —х\ , /== 1, т .
8. Вычисление матрицы К"=||
1|от т ья
по
формуле:
9. Вычисление оценок Д^, у = 1, 2 ,..., т-\-п по форШ
-м:' . .
Ийя^'
*'чК&1 яГ® ^ИЕт1И
муле Ду~= 2]
п в
10. Е сл и Д ;< 0 для всех
1, т4-д* то * :
= 1
и перейти к п. 16 алгоритма; если А > 0 хотя бы для
одного Л 1< /<; т -)-# и У п К 0,
1, т для этого
У, то А: =«=2 и перейти к п. 1о алгоритма; в противном
случае продолжить вычисления с п. .11 алгоритма.
11. Определение индекса 5 из условия Дл=*тахДу,
I < / < т-±п.
12. Определение индекса г из условия */г= т т
А
Уи
$г$ > О, где 1 < 1 < т .
13. 4:
14* дкг: —акз, к*=* 1, т .
15. Безуслоаный переход к п. 5 алгоритма.
16. Вычисления закончены. Если *= 1 и
® ^ а « *. то ЛГ =*(.**, х ь . . ^ — опти­
мальное решение задачи. Если *= 1 и хл±х\/ хл^2 V - ••
. . . V -^/1 ьто / 0, то задача не имеет решения из-за
несовместности системы ограничений. Если й = 2, то за­
дача не имеет решения, так как минимизируемая линей­
ная форма не ограничена снизу.
Проиллюстрируем изложенный алгоритм числовым
примером.
Пример 1. Пусть т —3, я =4,
/2 4 0 4
.4 = 1 7 2 2 4 |, В за!
|, С = (3 , 4, 3, 1)
Ц 8 4 3
Формируем матрицу Л:
1 0 р
121 4 |0 4 1
Л = = | 2
7 22 2 44 0 11 0
\5 8 4 3
о 0 0 1
9
Матрица
(} принимает вид:
10
0
О 1 О
О
О О 1
Формируем векторы С н 7
С « < 3 , 4, 3, 1, М , М . М );
Т ~ ( 5 ,6 ,7 ).
Вычисляем вектор X
18 0
Ам1) = | о
10
1 О
<0 0
1
О
О
О
О
О
О
X:
12;
*1
/2 = о =? х&:
8 ;
/3 =
28
7 =ф Х 7 ;
Итак,
I О
О
О
о
АГ
12
8
28
Вычисляем матрицу У = |
0 0\ —I
У
1 О
2
4 0
17 2
О 1
5
2
4 0
8
4
2
4
1 0
4 0
4 3
1 0
0
0'
/ 2 2 4 0 1 0
\5
10
8 4 3 О О
1;
0
1 0
0
1
Вычисляем оценки Д^:
Д! = А?.2 + Л1.7 + М- 5 — 3=* 14Л4 — 3
Д-2= /VI •4 4* .М •2 -|- Л1•8 — 4 == 14М — 4
Аз
М ■0 4- М -2
Ш —3
М -4 — 3
д4= Л1-4 + /И*4 н-М-3 — 1И 11М - 1
Д
А
0.
Поскольку Л.;>0 ДЛЯ /=1, 2, 3, 4 и при этом у ц > 0. то продолжаем вычисления.
Определяем индекс 5:
5 = 1, так как Дг = 14М = шах {1рШ, 14М, 6М, 11М:}
Определяем индекс г:
г = 2, так как
/
8
У21
7
1111П
12
8
28 |
2
7
о
Полагаем (о= I ■Вектор Т принимает вид: Г = (5, 1, 7)
Матрица (2 принимает вид:
Р
<1=
г
\0
2
°\
7 о ).
5 1/
Первая итерация закончена. Проделав аналогично еще несколько
итераций» получим
О
4
(2
°\
7 2
1,
I
\5 8 4/
2
0
3
1
0
0
0
о
и к—1. Поскольку х5=х6=х7—0г то найдено оптимальное решение
задачи:
Х —(0, 3» 1, 0).
Изложим теперь алгоритм симплексного метода с об­
ратной матрицей.
II
Алгоритм 2
1. Введение искусственного базиса
матрицы
1.1. Заполнение
II гц
у'— О, гпА-п.
! ^1^11'^12
Ь^Л21Я22
а,2п
•
•
1, т 4-2,
10 0
0 10
Ш
0
йтп О 0 0 ............ 1
— сп 0 О О
О
•
т
т
/1
ь,
II
►
—
1
^та'тп\атп2
0- С 1 — С2
т
т
Ь 2 «а
/= 1
\т
I
•
2 а<я0 О О
/==1
т
1.2. /,: = /г-4-/, 1=— 1, т .
2. Если существует у (
1
т +л )
то определение индекса р
т +2.у>0,
шах гт+2.) и переход к п. 4.
т-\-2,р
1<7<т7г+я
3. Определение индекса р из условия
О
)
такое, что
из условия
' 1
^т-\-\,р= шах ^/л+Ь/-
1< ] < п
4. Определение индекса щ из условия
1.0
ПИП
я,р
1<I <т Щир
2 'но > 0.
5.
чг
6. Д ля I
пп. 6.1— 6.2.
6. 1.
и
6.2. ЩШ
41
, /= 0,
т4-/г.
чр
1, 2, ..., т + 2 при условии 1ф а выполнить
Ц8
2 ^/, у — 0, т
п.
7. /„: | Л
8. Проверка условий.
8.1. Если / , < л для всех /= 1 , 2 , . . . , т и 2т .и .у< 0
для всех у = 1, 2 ,..., /г, то Л: = 3 и перейти к п. 10.
8.2. Если 2гт+2у< 0 для всех у — 1, 2 , . . . , т + л»
для всех У = 1 , 2 ,..., п и сущ ествует I такое,
что / / > 0 , то к: = 1 и перейти к п. 10.
12
8.3. Если
существует у такое, что
ГП+2,/ О,
„+!,;•> О, 1< /' < Я и ги.< О, для этого у и всех
/= 1, 2 ,..., т , то к: = 2 и перейти к п. 10.
9. Перейти к п. 2.
10. Вычисления окончены.
Если к — 1, то задача не имеет решения, так как система ограничительных условии несовместна.
Если к = 2, то задача не имеет решения, так как ми­
нимизируемая функция не ограничена снизу.
Если к —3, то получено решение, причем
о
если Щ Ш Ш
* * * * I* *0,
а значение
если // Ф у ни для какого /, 1 < / < т ,
минимизируемой
Проиллюстрируем
что и алгоритм 1.
линеинои
формы
равно
алгоритм 2 на том же примере,
П р и м е р 2. т= 3, п—4
4 0
Л
7 2 2 4 I, Л
(3, 4, 3, 1)
5 8 4 3
Заполняем матрицу \\ги
ш »
0
7
4
2
2
4 10 01
4 0 10
5
8
4
3 0 0
0
3
•4
3
■10 0 0
48
14
14
б
11 0 0 0
( 12
2
8
28
В*//В =*
1
Вычисляем вектор /: /=■(5, 6, 7).
Индекс р определяется из условия п. 2 р= 1, при этом гт +2, Р =
25,1 и переходим к п. 4.
Определяем индекс д:
8
28
* 1,0
12
24,0
*3,0
ПУЗ ШМу
2.
5
2 ’ г-2,1 “ 7 ’ *3,1
В п. 5 получаем гдр =:^21= 7
2
4
/
1 2/7
/ 8/7
5
8
И*//11=1 28
\ о -3 — 4
14 14
\ 48
1
2— 1597
2
0
2/7
4
—3
6
4
4/7
3
—1
11
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
13
В результате вычислений в п. 6 получаем
*//11
— 2/7 0 >
1/7 0
-5 /7 1
3/7 0
—2
0,
24/7 — 4/7 20/7 1
0
4/7 0
2/7
2/7
1
18/7
1/7 0
46/7
0
5/7 0
0 --22/7 -- 15/7
2 . 3
0
10
0
/ 68/7
/
8/7
156/7
\ 24/7
V 32
В п. 7 имеем: /г: =1 и теперь /= (5, 1, 7).
Поскольку ни одно из условий п. 8 не выполняется, то из п. 9
переходим к п. 2.
Определяем индекс р: р —2. Переход к п. 4.
Определяем индекс <
7: <
7= 1.
После выполнения пп. 5— 6 получаем
{ 17
6
1
3
11
II *// II
3
37
3
11
3
0
7
6
6
24
12
1
1
12
1
3
1
/ --3
6
11
16
23
3
3
12
1
10
_П
1
1 0
0 0
1
5
1
—
8
0 0 --- лда
3
3
16
■3
11
0 0 —
3
6
12
6
35
7
12
6
О
О
1
О
О
)
Полагаем /1= 2, теперь /= (2, 1, 7).
ъщ
Поскольку условия п. 8 вновь не выполняются, переходим к п. 2
Определяем индекс р: р= 3. Переход к п. 4.
Определяем индекс <
7: <
7= 3.
Вычисляем матрицу |{ 2 $Л
3 0
0
II
II
10
10
0
10 0 1
15 0 0
0
0 0 0 0
14
13
9
1
22
44
И
22
9
1
2
1
11
11
11
11
16
23
1
3
11
44
22
11
6
21
1
^_ _
11
~~ 44
22
11
0
—1
—1
1 }
8
- 1
,
Присваиваем /з * =3, теперь имеем /=(2, 1,3).
Так как выполняется условие п. 8.1, то к: =3 и переходим к
п. 10. Получено оптимальное решение. При этом
Х 2 = гьо 3* 3, так как /1 = 2;
х\ = -г2,о= 0, так как /2= 1;
х3= ^з,о = 1» так как /3= 3;
х\ — 0, так как /4 Ф 4 ни для какого I (/= 1, 2, 3).
.
Итак, решение А' равно: Х= (0, 3, 1, 0), а значение целевой функции равно
У ) с^Х] = -г'4,о== 15.
НШ Ж
/-1
1.2. Транспортная задача
Одной из самых распространенных в линейном про­
граммировании является транспортная задача, которая
формулируется следующим образом.
Имеется т пунктов производства однородного груза
и п пунктов его потребления. На 1-м пункте производства
сосредоточено а,- тони груза, 1 = 1 , т , а в /-Й пункт потреб­
ления требуется доставить ^ тонн, /=1, п. Будем в даль­
нейшем для обозначения поставщиков и потребителей
использовать обозначения А * и
соответственно. Счи­
таются известными расстояния между каждой парой
«поставщик — потребитель» — 1ц (к м ). Необходимо со­
ставить такой план перевозок, при котором обеспечива­
ется полный вывоз груза со всех пунктов производства
и доставка каждому потребителю груза в соответствии
с его запросом, а совершаемая при этом транспортная
работа минимальна. Обозначим далее через хц объем
груза, доставляемый /-м поставщиком /-му потребителю,
и сформулируем задачу математически:
п
______
2 ХЧ =«/.-/—1, т
■,:> -
; Т * . ' —-
1
(73
*ч>:
(из каждого пункта отправления груз должен быть вы­
везен полностью);
(спрос каждого
стью );
потребителя
удовлетворяется
полно­
х ц > 0, / = 1, пг, ) = 1, п
(9)
(перевозки не могут быть отрицательными);
п
т
2
2
/■*»! |Щ|
1цХ I ] -*■ т I п
(10)
.
(транспортная работа должна быть минимальной).
Единственным условием разрешимости задачи (7)
(10) является баланс между суммарными производством
и потреблением, т. е. выполнение условия
|
т
2
п
0-1 = 2
' =■1
У-1
,ЫД
Щ
(1] )
.'„Щ
Сформулируем условия оптимальности
решения
транспортной задачи: решение Х = [|ж^|| задачи (7) — (10)
является оптимальным в том и только в том случае, ес­
ли существуют векторы 11— {и{) и У — {V}} такие, что
и^ + V^\
‘1 Щ
(12)
Д ля решения транспортной задачи разработан ряд
методов. Ниже изложены два из них — метод дифферен­
циальных рент (алгоритм 3) и метод потенциалов (ал­
горитм 4).
.
Алгоритм 3
1. Ьч \ = 0 , 1и : — 1и , /= 1 , пг, у = 1, п.
2. у: = 1 .
;■ 3. Определение индекса к из условия
== годп 11у.
1</<т
Если таких к несколько, выбирается любое одно
них.
4-
--- И
5. у: ==у —
}—1.
16
6. Проверка выполнения условия: / ^ я ? Если да, то
перейти к п. 3, иначе — к п. 7.
7. к: = 1.
8. /: = 1.
9. Если есть лишь одно /=**, для которого- Щ
1, то 8/*у; = к, к: =г=й-(-1.
10. /: =/4-1.
11. Проверка выполнения условия: /г^я? Если да, то
перейти к п. 9, иначе — к п. 12.
12. Ц = 1.
13. Если есть лишь одно /= /*, для которого Ъп*=
= — 1, то 6,)*=к, к: = к + 1.
14. /: = < 4 -1 .
15. Проверка выполнения условия: '(Щ т§ Если да, то
перейти к п. 13, иначе — к п. 16.
16. Если б
0 для всех 4=1, 2, .., т и /=1, 2, ..., я,
то перейти к п. 17, иначе — к п. 8.
17. а ,: аь /=1, т .
18. Ь/: — Ь}, / = 1, п.
19. Обращение к подпрограмме «Модуль 1», после че­
го продолжать с п. 20.
ЙЩ*■
’ =*
21. Щ
— а(
П
Д
(0, если 8//=0;
Ь{р где 8,,—
8у >0.
22. /: -1.
23. Проверка выполнения условия: бо>0? Если да,
то Ъ): =0 и перейти к п. 24, иначе — перейти к п. 24.
24. / :> / + !.
25. Проверка выполнения условия: / ^ я ? Если да, то
перейти к п. 23, иначе — к п. 26.
26. /: =1+1.
27. Проверка выполнения условия: 1 ^ т ? Если да, то
перейти к п. 21, иначе — к п. 28.
28. Если йх—0 для всех *=1, 2,...., т , то перейти к
п. 59, иначе — к п. 29.
29.
5,: = {
1,
если </,>0;
0, если 4 ,- 0 ]
I, если
0,
/=1, 2
БИБЛИОТЕКА
Павлодарского
>
[ 3 4 2 ? 1 ‘
С
'
17
31* /: — 1*
.. с
32. Проверка выполнения условия: 51= 1).-’ Ьсли да,
то перейти к п. 33, иначе — к п. 39.
|
33.'а к: = ак, к = 1, т .
щ И
34. Ь_к. — Ъ_к, к = \ , п.
'
35.
;— а-I 1*
г:
36. Обращение к подпрограмме «Модуль 1», после че­
го продолжать с п. 37.
I: 1
П т
■
ЩД§37. р \ : И Щ Е Ш
33. Если р ! > р , то 8г: = — 1, иначе 5,: = 1 .
| | . 1\ = / —
|—1,ЯВНрнВ
40. Проверка выполнения условия: 1^ т ? Если да,
то перейти к п. 32, иначе — к п. 41.
!|Ш |
41. у: = 1 .
____
42. Если для некоторого 1— 1*, /= 1, т ,
о,,у >
О .Д 5 /*==1 , то гу. = с г , иначе находим любое Л дтя
которого 8,*/^>0, и полагаем г ^ шш 1ц— Л-*/.
щ
43. у: — у —
{—1^яИ ^И
44. Проверка выполнения условия: у ^ л ? . Если да, то
перейти к п. 42, иначе — к п. 45.
'ЩШ
45. г: = гш п г;-.
46. Находим любое к, для которого гь = г.
47. г. = 1 .
_
_
•
- ^Щ Ш
4 \ Если 5 ,-= — 1, то /и : — 1и -\-г, у = 1, п, и пе­
рейти к п. 49, иначе — перейти к п. 49.
^
49. 1’:== 1+1.
I
50. Проверка выполнения условия: г '^ т ? Если да,
то перейти к п. 48, иначе — к п. 51.
51. Определяем индекс | из условия
Я
7 ^ = т » п / {*.
Д
52. || =1; | дк- = — 1.
ЯИШ
53. Если дай некоторого / ? (1 < / ? < т ) и ^ (1 < ^ <
<
т )5
< О А 5? > О Д 8ру > 0 / \ 89/ > 0 , т о 1Ц
54/ / ; « / + !•
18
.
....I Я
= 0,
:-Д
Л-!
55. Проверка выполнения условия: у'^ я? Если да, то
перейти к п. 53, иначе — к п. 56.
О, если Ъц=0;
56. Щ
1
|
— 1, если Ъ{ фО, 1 = 1, т ,
у = 1, я.
57. Переход к п. 7.
58. Вычисление транспортной работы:
п
т
У У / г
59. Конец вычислений.
П о д п р о г р а м м а « М о д у л ь 1»
1. к : = 1, х и = 0 ,
2.
г. = 1.
/ = 1, т ,
у = 1, п.
3. у: = 1.
4. Если Ьц —к, то перейти к п. 5, иначе — к п. 9.
5. Хц‘. ==гЫп [аг, Ь}\г
Щ'* Л} + И^
.‘г ^ •Л ’ *:>>*
7.
= Ь ,—Хц.
8. Л: = А 4 - Ь
9. у: = у + 1.
10. / ^ я ? Если да, то перейти к п. 4, иначе — к п. 11
11. г. =/4-1.
12. 1^ т ? Если да, то перейти к п. 3, иначе — к п. 13
13. &^1тахд|;?
Ч
1< ] < т
«»
1<]<п
Если да, то перейти к п. 2, иначе — к п. 14.
14. Выход из подпрограммы.
Изложим пример решения транспортной задачи с по
мощью алгоритма 3.
П р и м е р 3. Пусть т=4,/г=4.
5 3
II % К
I 3 1
. 5. ,4 4-
.
8 7
2
(5/} = (90, 70, 110, 230),
{*/} = (70, 250, 80, 100).
19
Первая интерация
1. щ = °> 1и : Ц В й 1 ш Ш
2. /: = 1.
’
’
3. Определяем к: к= 1.
4. Ь2д: == — 1-
5. }: И ] + 1= 2.
6. Так как 2= /< л= 4, то переходим к п. 6.
В результате выполнения пп. 3— 5 еще 3 раза получаем
— 1
0
0 — 1
0 —1 —1
Ц | ЦI
0
о о о о
о о о о
и /=5. Поэтому переходим к п. 7.
7. к : Ш
9.' Есть лишь одно 1*=\,
61,1: =1 и к : = & + 1= 2.
для
которого 6^ 1= — 1. Поэтому
11. Так "как 2С/< /г= 4, переходим к п. 9. В результате выполнения пп. 9— 11 еще 3 раза получаем
1 0 О
2 3
II
II
О О
О О
и /=5. Поэтому переходим к п. 12.
_ \%
Ц Нет ни одного /'=/*, для которого би.= — 1, поэтому пере­
ходим к п. 14.
|У!Щ
15 2= 1
'< я = 4, поэтому переходим к п. 13. После выполнения
пп. 13— 15 еще 3 раза матрица ||6^ || не меняется, а I становится
равным 5. Поэтому переходим к п. 16.
16. Переходим к п. 17.
. -,.:Щ
17. {а [} = (90, 70, 110, 230).
|
18. {6 Л = (70 , 250 , 80, 100).
19. Работа подпрограммы «Модуль
1. к: = 1, хц: = 0 ,
2.
= 1.
4-
Первая итерация в «Модуле !>>:
4. бц = 1. Поэтому перейти к п. 5.
5. Щ Ж = т ш (90, 70) = 70.
6. а ц = а \ — 70 = 20.
7.
= Ьх— 70 = 0.
20
-—
1»:
Щ
:'Щя
.
■
|
ЗД
Щ
8. к: = к
+ 1= 2
9 . /: = / + 1 = 2 .
ш
10. Переход к п. 4.
Вторая итерация в «Модуле 1».
4.
Поэтому переходим к п. 9.
*9. /. — / + 1~
^
10. Переход к п. 4.
Дальнейшие итерации в подпрограмме «Модуль 1» аналогичны
В результате получаем
70
0 0 20\
0 70 0
II Х[/ II
0
> 0
0 0
0 0
°1
0
0/
'
щ | я , 0, 1109 230)
{Гу) = (0, 180, 80, 80),^ = 5.
I
Поэтому переходим к п. 20.
20. I : # й
21. <*,: =0—80=—80.
_
22—25. В результате выполнения этих пунктов получаем § Ы =
= (0, 180, 80, 0).
26. *: = 1+ 1=2.
_
_
27. Переход к п. 21. После выполнения пп. 21—27 получаем
{<*,} = (—80, —250, 110, 230).
28. Переходим к п. 29.
29. {5*} : = (— 1, — 1, 1, 1)..
30. р : =70+70+0+20=160.
31—40. В результате выполнения этих пунктов не происходит
никаких вычислений, так как ни разу при этом не выполняется усло­
вие $|=0.
41—44 В результате выполнения этих пунктов получается
{г ; } = (3, 1, I , 2).
45. г : =1.
46. Находим к: к~2.
47—50. В результате выполнения этих пунктов получается
3 6 4
4 4 2
IIII] II
5 4 4
8 7 2
51. Определяем индекс
#=3.
52—55. В результате выполнения этих пунктов никаких арифме­
тических действий не происходит, так как ни разу не выполняются
условия п. 53.
56. бз,а: Й Ш
21
57. Получаем
1
0
II % II
—
0
—
0
0
1
0
1
—
1
0
—
1
0
0
0
0
0
58. Переход к п. 7.
;■V| Щ
Проделав еще пять итераций, к п. 28 приходим со следующими
результатами:
'•
О О
0 о
II ьи ||
о
1 2
'7 10
8
1 б
II 1ц II
7
7
7 2
м у г
= |
.
* - Кж
М / •" ж
70
О
О 20 \
0
0
0 70
о 110
1
0
0
О 140 80
10;
и {с?,} = (0, 0, 0, 0). Поэтому переходим к п. 59.
59. Вычисление транспортной работы:
4
4
2
2
1ч х ц = 1870.
}-\ Щ1
60. Конец вычислений. Получено решение | |х^
Алгоритм 4
• ЩВк
1. Определение первоначального базисного решения
Ж (0-== || х\р ||
любым из известных методов (по пра­
вилу северо-западного угла, минимального элемента в
строке, в столбце, в матрице и т. д.).
Я
2. Составление
системы
уравнений:
и{ + ^] = 1ц,
для хц>0 для определения потенциалов Щ и о,-. От­
метим, что в этой системе всегда ( т + п) переменных и
22
1) уравнений. Для разрешимости системы достаточно одной из переменных придать любое значение
(наприуер, положить и{ = 0).
3. Опоеделение потенциалов
(т +л
1, т , у=1, п.
С/ = {и 1 } и V
4. Проверка найденного решения на оптимальность
по формуле (12). Если И{ + ~0)^1ц, для хц=0> то реше­
ние оптимально, в противном случае вычисления продол­
жаются.
5. Определение индексов к и § из условия
Ъ/га
ггах (и 1
Я
*</)»
•*
где В
0 ].
6. Построение замкнутого контура, все вершины ко­
торого (кроме одной) проходят через элементы матрицы,
для которых а'1;'>0, а одна вершина имеет координаты
й } = §.
«
V
7. Последовательно обходим полученный контур, рас­
ставляя в каждой вершине знаки. Обход начинается с
вершины, имеющей индексы 1 = к и ]= §. Этой вершине
контура присваивается знак « + ». Далее знаки череду­
ются (— , + , —, ..., — ) так, что никакие две соседние
вершины не могут иметь одинаковые знаки.
8. Среди всех х^>0, попавших в контур и отмечен­
ных знаком «—», выбираем минимальный и присваива­
ем его значение величине Д.
9. Для всех Хц%попавших в контур, полагаем:
Х ц .
где 6,^= 1, если вершина с индексами * и / отмечена знаком «+»,
и 6 ^ = 0, если эта вершина отмечена знаком «
Естественно, что 6/1д= 1.
10. Переход к п. 2 алгоритма.
V
V
ст.
о
П р и м е р 4. Пусть т = 5, п=4.
а(=* (75, 30, 70, 35, 30), &;=(70, 60, 50, 60),
18 20 30 29 4
10 75 34 45
30 35 18 20
И 27 34 35
5 31 28
23
Построим первоначальное решение, используя метод северо-за­
падного угла (отметим, что использование в этом примере метода
минимального элемента в матрице сразу приводит к получению опти­
мального решения. Однако не будем использовать здесь этот метод,
чтобы проиллюстрировать вычисления на всех этапах алгоритма):
/70
0
0
0
<0
г
*<0)
хи
5 0 0
30 0 0
25 45 0
0 5 30
0 0 30
Составляем уравнение для определения потенциалов:
#1 + ^1 = 18;
+ 1/3 = 18;
Щ
Ц\
= 20;
+ 1/3==: 34;
^
и2 + 1/2= 75;
1/44-1/4 = 35;
//3+1/2=35.
«5+^4=60.
Положив и1= 0 и разрешив эту систему уравнений, получаем:
Щ = 0;
VI = 18;
й ||
//2 = 55;
1/2= 20;
|§
и3 = 15;
1/3 =
//4=31;
3;
1/4= 4.
"^
«5 = 56;
Проверив решение
на оптимальность, убеждаемся, что его
можно улучшить. Причем ы / + 1/у— ///= шах для / = 5 и у = 1 .
Следовательно, ^54
0 следует ввести в базис. Строим замкнутый
контур. Он проходит через следующие вершины: (/ = 5, /= *!)-►
- > (/ = 1,
у = 2) —►(/ = 3, у = 2)->- (/ = 3,
-> 0* = 4, у = 3) ->-(/== 4, у = 4) -*-(/= 5, У = 4) (/ = 5, у = 1).
Этим вершинам поставим в соответствие следующие знаки: (+ , —,
+ , — , +, —» +, — , +)•
'
Среди элементов хцу отмеченных знаком «—>, ищем минималь­
ный: пип (70, 25, 5, 30) =5.
■.
Полагаем: х$\ = 5, Х ц = 70 — 5, х \2 = 5 + 5, х & = 25 — 5,
лг33 = 45 + 5, х43 = 5 — 5, ^44 = 30 + 5, д:54 = 30 — 5.
Новое решение ,ЛГ(1) = ||
II имеет следующий вид:
•
/65
ЛГ(1) =
24
10
0
0\
I 0 30 О О\
I
О 20 50
0 1.
\ 0
0
0 35 I
\ 5
0
0 25/
Ш
• -Щ
Нетрудно увидеть, что и это решение не оптимально. Продол
жив вычисления по описанной схеме, получим:
60
0
0
0
0 50
0 0
0 0
X
Выпишем для этого решения систему уравнений и определим
потенциалы:
^1 + ^2= 20
и\ -г Щ = 29
ип -ЪЩ = Ю
г?
о
\= 18
Отсюда:
и\ = 0;
и> о;
VI — 5;
20;
9;
а4= 6;
= 27;
у 4= 29.
и5 0.
Проверка на оптимальность показывает, что
хц~0.
+
для всех
Следовательно, решение Л'* оптимально, а транспортная рабо­
та при этом составляет
4370 ткм
Основную трудность при расчетах по методу потен­
циалов представляет поиск контура (немалые затрудне­
ния создаются здесь и при программировании). Ниже
описывается простой способ нахождения таких конту­
ров. Пусть получено очередное базисное решение Ия,.,!!:
а) просматриваем подряд все столбцы матрицы ИйО
и исключаем из рассмотрения те из них, в которых есть
только один базисный элемент;
б) просматриваем
подряд все строки
матрицы
Ия,^|| и исключаем из рассмотрения те, в которых имеет­
ся только один базисный элемент.
Пункты «а» и «б» повторяем пока возможно. Легко
показать, что оставшиеся строки и столбцы
матрицы
25
И^о'И будут содержать ровно по два базисных элемента
(в том числе элемент, включаемый в базис). Эти элемен­
ты и образуют искомый контур, построение которого те­
перь совсем просто (последовательное соединение сосед­
них элементов в строках и столбцах).
щ И
Единственным условием разрешимости задачи (7) —
(10) является выполнение соотношения (11). В практике,
однако, это условие часто не соблюдается. Принято
считать, что если спрос превышает предложение, т. е.
т
п
-
2 я* < 2 Ьц т0 необходимо ввести фиктивного постав/=*1
7=1
*
п
т
щика Лот+1 с объемом производства ат+1 = 2
п
—2 %
т
а если предложение превышает спрос, т. е. 2 Ш В ^ %
;=1
I =1
то надо вводить фиктивного потребителя В п+1 с потребт
п
ностью в грузе: #„-н = 2 я , — 21 Щ?
'“ 1
7=1
Щ
Я!
-111И
Между тем такой подход далеко не всегда правоме­
рен. Действительно, вводя, например, фиктивного постав­
щика, задача лишь формально приводится к сбаланси­
рованной. При этом нельзя забывать о том, что постав­
щик А т + 1 является фиктивным и реально груз от него
потребителям не поступает. Решение сбалансированной
таким способом задачи может привести к выработке
рекомендаций, согласно которым часть потребителей
будет обеспечена грузом от реально существующих по­
ставщиков, а часть вообще не получит груза (поставки
от фиктивного поставщика). Ясно, что с такими рекомен­
дациями можно согласиться лишь в ситуациях, когда
потребители абсолютно равноценны, а резкая разни­
ца в степени удовлетворения заявок на перевозки до­
пустима.
В остальных случаях введение фиктивного поставщи­
ка неправомерно, а баланса в задаче следует добивать­
ся не путем увеличения объема производства (за счет
фиктивного поставщика), а путем снижения суммарной
потребности потребителей.
. Щ НВ
При этом, если, например, потребители равноценны,
то их потребности можно пересчитывать по следующим
формулам:
26
или
т
2
шх
«<
Щ щ Ь ] ------ , у = 1, |
1
1
п
1 %
*
Н §И1
л
т
В обоих случаях 2 ^ / = 2 Д„ и задача оказывается
-У-1
Ш
V
сбалансированной.
Если потребители неравноценны, то хаждому из них
необходимо поставить в соответствие коэффициент от­
носительной важности (ценности) 8), /==1, п, который оз­
начает ущерб, наносимый /-му потребителю при недовозе ему 1 т груза. После введения фиктивного (т-И )-го
поставщика с объемом производства
I
- *
ш*
1= 2
‘.
«
да
задача принимает вид:
п т
п
2 2
У-1/-1
+2
/—1
/
т
\
ьз ~ 2
\
} Р 1111п:
/
/л+1
г:■
*
2 хи ==ь1’ 1= 1>п'
шШ
/=*1
'
л
V .лг/у =
/«■1
^ •у
Л/, / =
1,
т
4- 11
> 0, /— 1, /я -Ь 1, 7 — 1, л .
Целевая функция этой задачи после преобразования
поинимает вид:
л
/я __
/“ 1Ж
где
27
Возможны и другие подходы. Более подробно они бу­
дут описаны ниже при рассмотрении задачи оптималь­
ного распределения транспортных средств.
Аналогично следует поступать и в ситуациях, когда
объем производства превышает объем потребления.
Выше была рассмотрена широко известная на авто­
мобильном транспорте задача оптимального закрепле­
ния потребителей однородного или взаимозаменяемого
груза за поставщиками. Отметим, что в рамках матема­
тической модели (7) — (10) формулируется еще ряд ав­
тотранспортных задач. Например, оптимальное закрепле­
ние клиентуры за АТП , оптимальное закрепление токов
за элеваторами при организации перевозок зерна и мно­
гие другие.
Рассмотрим здесь одну из этих задач — оптимальное
размещение автомобилей по АТП . Введем следующие
обозначения:
^ ЩШ Я
п — число клиентов;
Т ||||И
т — число типов автомобилей;
____
&
тИ
йг — количество автомобилей *-го типа, 1= 1, т\
к_
Ьц — потребность в автомобилях I-го типа у /-го клиента, \—1, т ,
/=1, П\
:
1ьз — сумма первого и второго нулевых пробегов между к-м
АТП и /-м клиентом, км, Ш В Е тл ||§1,
>
— количество автомобилей ь-го типа, представляемых /-му
клиенту к-м АТП, й И , т , кЩ\9 г, /||1, /г;
Угк — количество автомобилей /-го типа, размещаемое в к-м
' АТП;
г% — количество дополнительно приобретаемых автомобилей
I-го типа;
'Ш 0 Щ Ш
8г — затраты, связанные с приобретением дополнительно одного
автомобиля 1-го типа, руб.;
М-а — максимальное количество автомобилей, которое можно
разместить в к-м АТП;
' ^
Ь] — общее количество автомобилей, которое необходимо /-му
клиенту;
С
Хкз — количество автомобилей, представляемых /-му клиенту
к-м АТП.
5^
Математически задача
образом:
формулируется
Г
2
6=1
следующим
I,
Х Щ ~ Ь1Ж * = 1> т . У = 1. п
(13)
.■ШШШ
(потребность каждого клиента в автомобилях каждого
типа должна удовлетворяться полностью);
28
(количество автомобилей г'-го типа в к-м АТП составля­
ет у!к);
|
22 Ут — а1+ *1, I = ТТ~т
(15)
(суммарное количество автомобилей е-го типа составля­
ет !% + % );
‘■
. V - '. ■' "
■
л
т
V -
1-1
У1к < :Й1* * = 1, г
(16)
(количество автомобилей в каждом АТП не может пре­
вышать ц*);
•
х»1 > С Ш > 0, *1 > о ,
•
(17)
/ * 1, я , Л я 1, г , / я 1, л
(переменные не могут быть отрицательными);
т
2
<5
/-1
сод
(затраты на приобретаемые дополнительно автомобили
не превышают заданных).
Принятый критерий минимума суммарных нулевых
пробегов запишется теперь так:
п
т
г
1 2
V
**/*»/-■>-т !п .
(19)
/«1 г-1 Й—1
Сформулированная задача (13) — (19) является за­
дачей линейного программирования. Решение ее можно
получить симплексным методом по изложенным выше
алгоритмам 1 или 2. Если нет возможности дополнитель­
но приобрести автомобили, то в задаче (13)— (19) сле­
дует положить 5=0 и 2^—0, {= 1 , 2, ..., т . Условие (18)
при этом пропадает из ограничений.
Подставляя, кроме того, равенство (14) в (15) и (16),
получим окончательную формулировку задачи:
Я
Т
______
2 2 х1*1ж а 1> /==1» ш>
/-1 ащ
3— 1597
(20)
29
^
^
Х Л) <Н> к ~ 1' г <
(21)
У-1/-1
Х[ к> = Ь ] ,
п
V
т
V
1=1,
т,
г
V
7=1, п;
-> т т .
(22)
(23)
/=1(=1н=1
Необходимым и достаточным условием разрешимости
задачи (20) — (23) являются:
/71
П
/71
2
2 2 ьи
/=1;=1
1=1
«
I
(потребности клиентов в автомобилях действительно мо­
гут быть удовлетворены) и
'*
т
Т
2 а1 < 2 ы
г=1
й=1
д:
щ
(автомобили могут быть размещены).
Задача (20) — (23) легко сводится к транспортной
Имеем
-‘-ШШ
т
V ( Х\Щ
—
к = 1, г, / = 1, л
(24)
/71
2 й 1 */
1=1
С учетом равенств (24) задача принимает следующий
вид:
Г
V
х%] — Ь], ] — 1, 2 ,... л,
Л= 1
п
у
1 Хк]
У=1
п г
V
—
1, 2, . . . , г;
ГП1П,
7= 1*=1
Х&] >0, & = 1, 2 ,..., г, / — I » 2 ,..., п.
30
(25)
Если клиенты не в состоянии указать свои потребно
сти в автомобилях, то задача (25) принимает вид:
п
\
т
г
2 2 2
Ж 1*=1
I
п
т *п;
г
2 2 4М <
;=1*=1
п
т
2
_____
2
х **1
'5 /-1 Я
г
*= 1»
<Щ
* = I, г;
т
_____
2 2 “ //•*«/= Р/. ] = 1’ п>
Л=1 /-1
■*<*>» 0 »*= 1 , т , к = 1 , г , | = 1 , п ,
где 0 ,*— объем перевозок /-го клиента, т;
ш? .7— производительность автомобиля 1-го типа у /-го клиента, т.
Сформулированная задача является задачей линей­
ного программирования, решение которой можно полу­
чить по алгоритмам 1 или 2, изложенным в п. 1.1.
Во многих ситуациях (например, при перевозке ско­
ропортящихся продуктов) необходимо так закрепить
потребителей за поставщиками, чтобы максимальное
время доставки груза было минимальным. Для выработ­
ки рекомендаций в таких случаях можно воспользовать­
ся математической моделью транспортной задачи по
критерию времени, которая формулируется следующим
образом:
п
2 х ц = Д/, / = 1 , т\
/-1
(26)
т
Х { ] Ш в>р
у Щ 1, л;
(27)
/~1
х 1]
> О, / Ц I , т , / = 1 , п;
тах
В®
тт,
(28)
(29)
где
5//
3
0, Х{у = О,
1,
> О,
31
В этой постановке приняты те же обозначения, что и
в задаче (7) — (10), а 1ц — время доставки груза от 1-го
поставщика /-му потребителю. Заметим, что ограничи­
тельные условия сформулированной задачи (26)
(29)
совпадают с ограничительными условиями транспортной
задачи (8) — (10), а целевые функции различны.
Д ля решения задачи (26) — (29) можно предложить
алгоритм 5, суть которого сводится к последовательному
решению транспортных задач вида (7) — (10).
Алгоритм 5
1 Й!
Й:|- '■
= О 0.
.
2. Решение транспортной задачи линейного програмп
т
мирования вида: минимизировать 2 2
Щ 0§
ПРИ
виях (26) — (28).
3. ({2): = шах т а
*
Усло"
ДдЯ
]
где
_
0, Х и ==0,
1,
Щ
> 0.
IЯ р !
4.
Проверка выполнения условия:
перейти к п. 5, иначе — к п. 7.
Если да, то
с/э,
5.
Щ
<
(
2)
I I
* = 1, т ,
6. /(1): р | (?| х \у: —х и,
у = 1, п.
1= 1 , Щ
рейти к п. 2.
____
____
7. х ф = х \ ) \ /— 1, т, у — 1, п.
8. Конец вычислений.
у = 1, |
и пе­
Май!
/О*
ЙД!
П р и м е р 5. В условиях примера 4 решить задачу (26) — (29),
используя алгоритм 5 (считаем, что
Полагаем /<^= 00. Ре­
шение задачи (7) — (10) приведено в примере 4. Оно имеет вид:
0 60 V о
30
о
о
X Щ I О О 50
10 0
0
30
0
0
32
Определяем, что
Поскол ку № <
35.
то полагаем: |[#|Р II:
II хц || ,
1,
— т, } й Ш
И
Ш 35 Ни блокируем
Й 1 Н в матрице Т все вре­
мена, большие или равные 35. Получаем:
Т
18
10
30
11
5
20
М
М
27
31
30
34
18
34
28
29
М
20
М
М
где М — большое число.
Вновь решаем транспортную задачу (7) — (10). Получаем
60
0
0 0
0 25
0 25
0 0
X
Определяем, что /(2) = 34 < /(1). Полагаем:
щ
34, || х \ 1) || :==
= I! ■*//!• /==1» /и, / = 1 , п и, блокируя в матрице Т все
ты, большие или равные 34, получаем:
Т
18
10
30
11
5
20
М
М
27
31
30
М
18
М
28
элемен­
29\
М \
20 |.
М /
м/
Очередное решение транспортной задачи имеет вид:
X
0 35 0 40
30 0 0 0
0 0 50 20
10 25 0 0
30 0 0 0
*<2>*=29< *<!>.
Полагаем: * ^ = 29, НА ? II:
/18
(10
Т
X I ) || и получаем в матрице
= ||
II Х[)\\
20 М
М м
М\
М \
М 18 20 1.
27 М м /
\ 5 М 28 м/
I М
Iй
33
Очередное решение Х = ||* и || включает в себя элементы, кото­
рым соответствует /^=М . Следовательно,
= М > / • Поэто­
му возвращаемся к предыдущему решению и принимаем
,
О 35 О
30
О О
X —Х^) = I о
О 50
10 25 О
30
О О
5
Для этого решения шах
«./
— 29, а
V
/=1
4
1цх а — 4395.
1
|
Для сравнения напомним, что решение примера 4 по ал! оритлу
5
4
4 обеспечило 51 X
^Их й ~ 4370, но при этом т а х
= 35.
Ш /-1
1
Часто встречаются и представляют значительный ин­
терес транспортные задачи в сетевой постановке, напри­
мер задача о моделировании сети и выборе кратчайшего
маршрута. Формулируется она следующим образом:
заданы п пунктов и связывающие их коммуникации.
Обозначим длину коммуникации между Ш и }-м пунктами 1ц.
■ш'
Если пункты не связаны прямой коммуникацией, то
соответствующее
. Возникает вопрос о поиске
кратчайшего маршрута из /-го в /-й пункт.
Опишем алгоритм, позволяющий одновременно опре­
делять кратчайшие маршруты между любыми двумя
пунктами транспортной сети.
^
•г
Алгоритм 6
г
1. 1*§.’= 1 ф
У — 1. л2. Устанавливается порядок перебора всех элемен­
тов матрицы \\1ц\\. (Этот порядок может быть всегда
Одинаковым, например 1=1, п, /==1, п. Однако, если он
различен при каждом обращении к п. 2, то сходимость
ускоряется)
2.1. /*>: = ш1п (/*х-Н*/)>
1< \ < п
где 1$ I
бор*.
34
текущие значения индексов, установленные порядком пере­
Я
3. Если исчерпаны все значения пар индексов /, /, то
перейти к п. 2, иначе — к п. 4.
4. Если матрица || //у II изменилась при последнем
переборе всех ее элементов, то перейти к п. 2, иначе п. 5.
5. Построение маршрута из пункта 1 0 в пункт /о. Если
^о^о —
то такого
пути не существует.
Если же
//о/о <С 60> то поступаем следующим образом.
5.1, к : = 0 .
5.2. Х0: *»*.* \
5.3 Находим индекс Я&+1 такой, что
1у
X
Л+1
“Ь
/
Л/г+Ь
в
ГП1П (/ ^
1<Х<я
х
*’
"Ь
/ ) *
,/о
5.4. Если Л&+1 ф /а, то &= &+1 и перейти к п. 5.3, ина­
че — к п. 6.
6. Решение закончено. Последовательность Хо,
>,л+1 — это номера пунктов, ведущих А,о= т в пункт Хь+ 1 =
— /оПример
6. Пусть я = 5 и матрица /■*$ имеет следующий вид:
И//у II
Матрица
дующий вид:
||
||
0
1
оо
2
1
0
1
оо
оо
1
0
2
2
оо
2
0
2
1
3
1
2\
ч
3
1 /
0/
после выполнения пп. 1—4 приобретает сле-
(
I
1 2
2 2\
1 0 1 2 11
2 1 0 22
.
Все пункты связаны маршрутами
2 2 (//у
2 < 0со).
1 I Найдем оптимальный
1 2 1 0 / пип $12 + Я » ^15 +
маршрут между первым и третьим2 пунктами:
-}- /|3, /14 —
|—^43) й шш (2, 4, 4) = 2, поэтому Хх = 2.
Далее ш ш (/23 +
/25+ /53)= ш т(1 , 3 )= 1, поэтому Х2 = 3.
Итак, кратчайший путь из п. 1 в п. 3 проходит через промежу­
точный п. 2.
35
1.3. Задача о назначениях
Частным случаем транспортной задачи линейного
программирования является задача о назначениях (проб­
лема выбора), которая формулируется следующим обра­
зом: минимизировать функцию
П
П
2л 2 сихи
; - 1/-1
при условиях
_____
п
2 х и ==! » * = Й
1-1
п
^
п>
_____
х I у = 1, I ===1, й ,
х п = 0 или 1, I, У = 1, п.
Д ля решения этой задачи можно использовать все
те методы, которые разработаны для решения транспорт­
ной задачи линейного программирования. Кроме того,
существуют методы, предназначенные непосредственно
для задачи о назначениях. Ниже излагается алгоритм,
реализующий один из таких методов (венгерский метод).
Алгоритм 7
1. с,у
у = 1, п.
2. Хц: = 0 , /, у = 1, п.
3. й ? = 0 , /= 1 , п.
П
4. з,: = 2
/- 1
е
___________________
8г/> ^ 1 .
_
(0, если с^^-0,
^п==\
—
[1, если С ц = 0.
5. Определение индекса р из условия:
50 —
ПИП
$ /.
о
8. у: = 1.
9. Проверка выполнения условия: Ср^=0/\xV^ Ф — 1?
Если условие выполняется, то перейти к п. 10, иначе — к
п. 20.
10. Проверка выполнения условия: к= 0? Если да, то
перейти к п. 11, иначе — к п. 12.
11. хру. — — 1.
12. Проверка выполнения условия: к —1? Если да, то
перейти к п. 13, иначе — к п. 20.
13. х.,\ = 1.
14. к: = 0.
15.
— 1.
16. Проверка выполнения условия: с,р= ОД 1фр^ Ес­
ли условие выполняется, то перейти к п. 17, иначе — к
п. 18.
17. х1р: = — 1.
18. I: = /+ 1 .
19. Проверка выполнения условия: 1^ п ? Если да, то
перейти к п. 16, иначе — к п. 20.
20. у: = у + 1 21. Проверка выполнения условия: / ^ я ? Если да, то
перейти к п. 9, иначе — к п. 22.
22. Если
0 хотя бы для одного I, то перейти к п. 5,
иначе — к п. 23.
23. Проверка выполнения условия:
П П
у У л — г
Ах Ах °и —
где
Если условие выполняется, то перейти к п. 48, иначе
к п. 24.
24. г,: = 0, /==1, п.
25. з*: = 0 , у = 1, п .
26. /: = 1 .
27. Если хцф\ (/=1, 2, ..., п) ни для одного /, то пе­
рейти к п. 28, иначе — к п. 29.
37
28. г с =1: :л У * ^ т
29. 1\ — /-1-1.
,
Щ
30. Проверка выполнения условия: / ^ л ? Если да, то
перейти к п. 27, иначе — к п. 31.
'Щ
31. к: = 1 .
32. у : = 1 .
- Л |
33. Если хотя бы одноТ»/ такое, что ^ /у= 1 Д г /==
= 1 д 5^=0, то перейти к*п. 34, иначе — к п. 36.
34. 8»: 4=1.
* й Я
35. к\ = 0 .
36. у-: =фу + 1.
37. Проверка выполнения условия: / ^ п ? Если да, то
перейти к п. 33, иначе — к п. 38.
Щ
38. I: =1.
39. Если есть хотя бы одно / такое, что хц= \,/\ г{ =
= 0 А 5^= 1, то перейти к п. 40, иначе — к п. 42.
40. гс = 1 .
41. к: = 0 .
Л М И
42. г. =/-(-1.
-*р|
43. Проверка выполнения условия: ё^Сл ? Если да, то
перейти к п. 39, иначе— к п. 44.
44. Проверка выполнения условия: & = 0 ? Если да, то
перейти к п. 31, иначе — к п. 45.
45. а: = шш ппп Сы.
4
||1|И
/: г.=*1 } :
46. Д ля 1=1, 2, ..., п и /=1, 2, ..., п выполнить:
_
(с// + а, г, = 0 Л 5/= 1,
усц —
а , г,- = 1 А 8] = 0.
47. Перейти к п. 2 алгоритма.
48.
(0, X I; ф 1,
хц: = {
--11, хц = 1 , I, у = 1 , п.
\
IЛ Ш Ш
,г4 ш |
49. Вычислить значение целевой функции
П
п
с = 2 2 сцхц.
И Й
- гЩ
50. Конец вычислений.
Проиллюстрируем действие алгоритма 7 следующим
числовым примером.
38
П р и м е р 7. Пусть л=5
4
3
С = Цсц II = I 2 3 5
4
5
4
5
5
4
4
I \
3
5
4
5
Схема вычислений на 1-й итерации по алгоритму 7
1. Зщ.р ===0. ь, у ==1» 2,...» 5.
2. Матрица С = ||с»,|| принимает вид:
1 1 1 0 1
О 0 0 1 О
С= I 0 2 2 1 2
14 10 1
3 2 2 0 2
3.
= 0. / == 1, 2 , . . . , 5.
4. 5/1 я® (1, 4, 1, 1> !)•
5. р: ч=а 1.
. -1
*
6. Щр = 1.
7.
й=
1.
8—21. В результате вычислений в этих пунктах алгоритма полу
чаем: *м = 1, .*ч4= 0, -^54= О, Л—0.
22. Поскольку р1==(1, 0, 0, 0, 0), то переходим к п. 5 алгоритма
Когда попадаем в п. 22 в 5-й раз, то имеем
1
Ш 1Н Н
1 —1
О
1
0
0
0
Щ Ш
—
1
1, 1, 1, 1, 1) и переходим к п. 23 алгоритма.
23. Поскольку
5
5
2
2
/=1У—1
==^ ^ п ~
т0 вычисления еле*
дует продолжить с п. 24.
24. г/.* = 0 , / = 1 , 2 , . . . , 5.
25. 5у: = 0 , |== 1* 2 , . . . , 5.
26—30. В результате вычислений в этих пунктах алгоритма по­
лучаем /4= 1, г5= 1.
31. к : - 1.
32—37. Вычисления в этих пунктах дают: 54= 1,
38— 43. Вычисления в этих пунктах определяют: г1= 1, к= 0.
44. Поскольку 6= 0, то вычисления следует продолжить с п. 31
алгоритма. При этом в пп. 33 и 39 ни разу не выполнятся соответ­
ствующие условия.
Следовательно, в п. 44 попадем со значением к ф 0(я=1) и про­
должим вычисления далее с п. 45.
39
45. а: =1.
_
46. Получаем новую матрицу С = ||с,-; ||:
0 0 0 1
0 0 2 0
2 2 2 2
С
3 0 0 0
1 1 0 1
47.
Переходим к2 п.
алгоритма. Проведя еще одну итерацию, в
п. 23 получим:
5
5
2 2 ьи
1-1 /=»1
5
П
и перейдем к п. 48 алгоритма с матрицей
1 —1
1
1 —1
1
1
0
0
1
0 —1
0
0
0
X
—1
0
0
0
1
\” 1
°\
- Л
о 1.
1/
0/
48. Получаем:
1 0 0
0 1 О
ООО
ООО
О 0 1
X
49. Вычисляем значение
б
5
V
V
1-х /—1
15
50. Конец вычислений.
Изложим еще один алгоритм решения задачи о на­
значениях, который в общем случае может не привести
к получению оптимального решения задачи, однако всег­
да позволяет получать весьма близкие к наилучшему ре­
шения и очень прост для программирования.
Алгоритм 8
I —1
'
7-1
5. Определение индексов I и 5 из условия
шах
1</<л I <у<л
6. л:*5: = 1.
7. т: = т
1.
8. С{3: =0, 1 = 1, 2, ..., п, исключение из дальнейшего
рассмотрения «-го столбца.
9. СкУ- =0, /= 1, 2, ..., п, исключение из дальнейшего
рассмотрения к-й строки.
10. х—п— 1? Если да, то перейти к п. 11, иначе — к
п. 4.
11. Определение индексов к и 5 из условия
и
о
п
X
■у . -' - ■
12. х^: = 1. ,
13. Вычисление
я
4- Щ
—'8*
|1§ г ® ; -
п п
2 2 еихи-
14. Конец вычислений.
П р и м е р 8. Решить пример 7, используя алгоритм 8. Полагаем:
х: в °
3 *2 4 4 5
и
0
(1)
трицы
Вычисляем элементы матрицы
М)
йи
27
25
31
29
27
28
26
28
24
30
31
29
31
33
33
— —
32
26
32
34
|3б|
II <
*(1) 1
«/у
30\
30 \
32 }.
34 /
34/
Определяем, что к = 5 и 5 =. 4, так как тах
Пола гаем: х54= 1, т= 1,
^52=^53=с55“
^54
36.
сн = <
?24= с34 = <44= с54= с51
Поскольку т=*1=т*=п— 1=4, то переходим к п. 4 алгоритма.
Вычисляем элементы матрицы
= ||
Ц;
ач
Определяем, что к = 4 и 5= 5_
__
_
_
_
_
Полагаем: ЛГ45 == 1, т = 2, с 15 = с2з = с35 — с45 — С41 —С42
с4з = 0.
Так как т = 2 ф п — 1=4,
..
то продолжаем вычисления
#
1
,
5
=
1
.
^
^
'
"
-
.................................
Полагаем:
т= 3
О.т = 3 Ф п — 1 = 4.
с 13 =
с 23 =
с 33 — СП Ш с 12
Ш
•*
V
2,5 = 2.
Полагаем: Х 2 2 ~ 1 * т = 4,
С22= с2з = С21 =
Переходим к п. 11 алгоритма.
Определяем
индексы: 6= 3,5= 1.
Полагаем Я =| и определяем сумму
ШШШЯ
= 4
П 1
оптимальное
решение
примера:
Итак, получили
0 0 10
0 1 0
0
о о
Оо о о
о о О 1
Х = [ 1 о
Изложим, наконец, еще один алгоритм решения зада­
чи о назначениях. Этот алгоритм (как и предыдущий) в
общем случае не гарантирует получение оптимального
решения задачи о назначениях. Кроме того, он весьма
сложно формализуем (труден для программирования).
Однако достоинством этого алгоритма является н
новенно простая схема вычислении, что позволяет реко­
мендовать его для ручного счета.
п
няйттено
Идея алгоритма состоит в следующем. Пусть найдено
некоторое допустимое решение задачи о назначениях.
Перебираем попарно в этом решении ненулевые компоНе Если для любых хй*= 1 и х ^ = 1 выполняется соот­
ношение Скз +
< си + с^, то решение задачи найдено.
■
ь
^
“
1
^
хь*:
=
1
1
х?*—
А»
Если же
+
т0
= 0 и вновь продолжается процесс прогерки
решения на окончательное.
П р и м е р 9. Применить описанный алгоритм для решения при­
мера Щ
Решение примера 9 будем осуществлять на матрице С =
Элементам этой матрицы, обведенным рамкой, в матрице X
С° ° ТВь1беремТв*качестве начального следующее решение: ха
да имеем:
о о о
Г
I 2
2
4
4
С(0)
2
Т
2
3
3
5
5
I
3
жш
4
4
х ц \ \
1. Того|
10 0 0
0 10 0
3
0
4
сц\1
0
0
1
0
0
0
0
0
1
)
I
4
Начинаем проверку:
Си +
<?22= С21 +
Следовательно,
с 12 у
необходимо
СП + с 33 > С31 + с 13
положить:
*31
1,
*13 = 1.
Хц щ 0, %з =
43
Имеем:
С (1)
3
2
4
4
5
0 0 1 0
0
2
I
3
5
3
0 1 0 0
0
2
з
5
5
5
1 0 0 0
0
3
5
4
4
4
5
I
3
4
5
* ( 1)
0 0 0 1 0
0
0
0
0
У
1
Проверяем:
С§1 + ^22 < с2\ + ^32» с22+ ^44 < ^42 + ^24»
С31 +
с 13 < С П +
с 33>
с 22 +
с 55 =
С Ь2 +
^25»
С31 + ^44 < СА\ + ^34»
^13 + ^ 4 4 =
С43 + С ц ,
С31 + ^55 < ^51 + ^35»
^13 + ^55 < ^53 + ^15,
с 22 + ^ 1 3 = с 12 + ^23»
с 44 + ^55 > с 54 + ^45«
Последнее неравенство указывает, что решение можно улучшить.
Полагаем: х54= 1, хА5= 1, х44= 0, х55= 0.
Получаем:
С (2>
3
2
7
4
2
I
3
2
3
3
5
1
5
5
3
5
5
5
,
5
4
4
3
5
4|
0 0 1 0
0 1 0 0
1 0 0 0
0
0
711
0 0 0 0
1
5
0 0 0 1
0
лг<2>=
.
Проверяем:
С31 +
^22 < ^21 + С3 2 ,
С 22 +
С54 < С52 + ^24»
^31 + ^13 < С П + ^33»
с 22 +
^45 < с 42 + ^25,
С31 “ Г ^54 < ^51 + с 34»
^13 + ^54 < ^53 + ^14»
С31 + ^45 < С41 +
^35»
^13 + с 45 < ^43 + с 15»
с 22 +
С2 3 ,
С54 + С45 < С44 + С5 5 .
^13 =
С 12 +
Итак, решение примера найдено:
X
44
0
0
1
0
0
о]
0
1
0
0
0
1
0
0
0
0
0
°\
0 0\
0
0
•
0 1/
1 0/
При этом 2
2
/-1 /=1
сихи = *5-
Наличие среди неравенств равенства ^22+^13=^12+^23 указывает,
что ь данном случае существует альтернативный оптимум. Иначе
говоря, есть еще одно решение, которое не уступает найденному
ранее. Это решение имеет вид:
0. 1 О О О
0 0 1 0 0
X = |[ 1 0 0 0 0
О0 0 1
0 0 10
'
\
5
и дает то же значение целевой функции: 2
У-1
Щ
5
2
сихи ==:
В рамках математической модели задачи о назначе­
ниях формулируется ряд автотранспортных задач. Рас­
смотрим в качестве примера задачу оптимального закреп­
ления различных типов автомобилей за погрузочными
устройствами.
Имеются т марок автомобилей и п типов погрузоч­
ных устройств (погрузочных пунктов). Обозначим {ц
( 1= 1, т , /*®1, п) время загрузки автомоблия I-й марки
/-м погрузочным устройством. Необходимо составить та­
кой план закрепления марок автомобилей за погрузоч­
ными устройствами, при котором суммарное время, за­
трачиваемое на погрузку, было бы минимальным.
Сформулируем описываемую задачу математически,
предварительно введя следующие обозначения:
1, если автомобиль 1-й марки загружается у'-м
погрузочным устройством;
хч
0, в противном случае.
о
С учетом введенных обозначений задача формулиру
ется следующим образом;
П
VI
хи Ш 1>/= 1, т
|§§§§§||
.
1*1
(каждый тип автомобиля загружается одним видом по
грузочного устройства);
(каждое погрузочное устройство будет загружать один
определенный тип автомобиля);
''
4
Х [ ] = 0 или 1, / = 1*
■п
(переменные носят булевский характер);
т
п
2 2 1‘)х>]
*-1 1-1
111*п
(суммарное время на погрузку должно быть мини­
мальным)!.
Единственным условием разрешимости этой задачи
является равенство между количеством погрузочных
устройств и количеством марок автомобилей, т. е. т = л.
В практике часто встречаются случаи, когда это ус­
ловие не выполняется. Предположим, что количество
марок автомобилей больше, чем количество погрузоч­
ных устройств, т. е. т > я . Тогда задача формулируется
следующим образом:
■
П
7=1
т
7 = 1» гг\
I =»1
х ^ = 0 или 1, / = 1, т , ] = 1, п\
т. п
г-Н -1
Предположим теперь, что количество марок автомо­
билей меньше числа погрузочных устройств, т. е. т < п .
фор
л
___
____________ «
т
V -*/;= 1» 1 = Ь
/ ч ^
Г \
П
'" I / " V 1 1 4
•
§
/-1
/У
О или 1, / = 1, т % ] = 1» »\
т
л
2
2
* - 1 7-1
46
у
Вт*
Все три описанные выше формулировки задачи мож­
но обобщить следующим образом:
V-п
\
2
Ш ,. Д В
/-г
т
\
* ■ ""
р:
х и ^ Ь / — 1, т\
•
/ = 1, П\
/-1
Щ/ = 0 или 1, / = 1, /га, / = 1, п\
п
'
т
У 5 ШШЙшЁ РШ *
В «я Ш
1.4. Распределительная задача
Наряду с транспортной одной из самых распростра­
ненных оптимизационных линейных задач является распределительная задача линейного программирования
(Я-задача). Сформулируем ее следующим образом: ми­
нимизировать
ШШРр
п т
=
(3°)
ш яж
при условиях
т
о
V ^;/*//==<?/» / = 1, П;
/=1
(31)
п
> 0, /= 1 , /га, / = I , л.
(33)
Для решения задачи (30) — (33) существует ряд ме­
тодов. Ниже излагается алгоритм, позволяющий реали­
зовать обобщенный метод потенциалов решения этой
задачи.
Алгоритм 9
1.
Введение дополнительного столбца переменных с
гем, чтобы в условиях (32) заменить неравенство на ра­
венство (привести задачу к каноническому виду). Зада­
ча (30) — (33) принимает при этом следующий вид:
47
т я-Н
д. ;ХI /
/—1/—1
V
V
V
т
* /=
1п;
1,
т;
/=1
т
} щцхц=<3], 7=1. п + 1:
; —1
Х[] > 0, 4=1, /я, 7= 1. л + 1»
где
<7,7-0;
о>,7= 1;
1, т . 7 = /г + 1,
а значение фп-н пока не определено и меняется на каж ­
дой итерации.
' .\
'у Я
2. Определение начального базисного решения
—
и Л°> и
,
3. Определение потенциалов строк //» и столбцов
из решения системы уравнений:
Отсюда
ди -и>1
а потенциал (п-Ы)-го столбца 1>
п+1—0 .
4. Вычисление характеристик Е ,•,•:
+и)ТОц).
Если Е {^ 0, 1= 1, т , /= 1, л, то найденное решение
оптимально. Если же хотя бы для одного 1= 5 и /*=■«,
Е,а<С.0, то план неоптимален и его можно улучшить пу­
тем введения в базис элемента с индексами 1= 5 и /' = */.
При наличии нескольких элементов с отрицательными
характеристиками Е ц в базис рекомендуется вводить
элемент, у которого отрицательная характеристика мак­
симальна по абсолютной величине.
48
5. Улучшение плана. Обозначим показатель, харак­
теризующий размер изменения поставки Щ при пере­
распределении их по цепи, через Ац. Для строк, входя­
щих. в цепь перераспределения, должно соблюдаться
Л+1
т
2 ^1)к==0» а для столбцов 2
/-1
1=1
Решив систему уравнений относительно Ац, опреде­
ляем их численные значения. Для разрешимости этой
системы необходимо для включаемого в базис элемента
положить Аз(*= 1- Полагаем далее
— пйп —М -, причем
минимум берется лишь среди тех элементов, ;для кото­
рых Ац <^0 (знак минус при этом отбрасывается).
Полагаем х $ = у за и вычисляем
+ ДуУ»»
для всех элементов, входящих в цепь перераспределения.
Далее управление передается в п. 3 алгоритма.
В изложенном выше алгоритме 9 в п. 2 предусматри­
вается определение начального базисного решения. Ни­
же описывается алгоритм, позволяющий получать в ка­
честве начального базисного решение, весьма близкое
к оптимальному.
Алгоритм 10
1. X I,: = 0, Ь= 1, т , у = 1, л + 1.
2. а {: =
а *= 1, т .
3. Щ]: =С1], у = 1, п.
и
4. ги: = --- , 1 — 1 , т , у = 1, га.
Чц
5. гь?.: = шах тахг^.
1<1<т 1<]<п
6. л:**: = ш 1п(аь,
8.
9.
а)
б)
щ =(2р—
Исключение из дальнейшего рассмотрения:
к-й строки, если а*==0 /\(}^ ф 0 ;
|*-го столбца, если ак ф 0
в) к-й строки и р-го столбца, если аА= ( ^ = 0.
49
»
2
У-1
т
10. Если 2 а, > 0 Д
/-1
т
алгоритма, если V #/ =
/-1
> 0,
то
переход
к п. 5
^
Д ^
0 Д 2 <Э/ ]> 0 * то переход к п. 11
1Ш /-1
П
/71
алгоритма, если ^ а 1'^-0 Д
У/ = 0 , то переход к п. 12
/-1
У-1
алгоритма.
/ :т я
11. Переход к этому пункту означает, что либо систе­
ма ограничений в задаче неразрешима, либо она имеет
решения, но определить их при помощи алгоритма 10
нельзя. В обоих вариантах необходимо попытаться най­
ти начальное базисное решение общими методами линей­
ного программирования.
_ '
85
П
12.
1.
'У
х\у, 1=* 1, т .
п ..
Ш Я
На этом вычисления заканчиваются, так как началь­
ное базисное решение А'(0) задачи (30) — (33) найдено.
/-1
П рим ер
10. т = 4, п = 5,
а / » (1 0 , 50, 15, 30),
(60, 175, 400, 100, 100).
/ 1
1
11
I 10
яц "1 10 2
\ 5 4
4
5
2
10
10
5
1
1 30 8
45 20
20
5
20
10
/ 5
®/у
2
5 2
2 4
5 1
5 4 |
15 20ч
10 4
25 5
20 10
Определяем начальное базисное решение, используя алгоритм 10
Х (°) ™ . Г
15 20 10
0 15 0
0
0
0
0
О 10
Находим потенциалы строк и< и столбцов
уравнений: и^+V^и!^^=д^^.
50
из решения системы
^
Получаем:
VI т
1,
«1 == —
и2 == 0 ,
” 2=
#3 == - 1 8 ,
” з =-
1
1
1
1
, V4 =
=~
3
5
1»
^5 =
2
^6 == 0 .
И4 == 0 .
Вычисляем характеристики
Е 11
Я ц — («/ + $0Щ§
1 + Т '5
^13= 4 — ( — 1 + 1*20)
1
3 ’
15.
Продолжив вычисления, обнаруживаем, что самая большая огрицательная характеристика ^ 13= — 15.
Строим цепь перераспределения. Она имеет вид:
2, ] В 3
О
Определяем величины %
из системы уравнении.
^13+ А12= 9»
20*А13 + 5*А*2з 5=5 0»
10•А12 + 5* А22= 0»
А22 + А23 + А26 = 0.
II А23
Полагаем А13= 1. Тогда получаем: А12 =
4; Д22
2; Аге= 2.
Определяем уп
Получаем 723
Д23
ХИ и выбираем у
А
20
= т 'т у ^
5.
4
1*5
Перераспределяем поставки: А12
20; Д^ = 2-5 = 10; А26 2-5
45
-5; А13
1-5 = 5;
10.
51
Определяем новое решение Л ^ = || х \ у ||
по формуле зЩ ! Щ
:||
= х\у + Д/уУ2з*
Получаем:
Й Щ
10 — 1-5 = 5; д:|^ = 0 + 1-5 = 5; х {$ = 15 + 2*5 = 25;
= 2 0 -4 -5 = 0; 4 1 ) = 5 + 2-5= 15.
Новое решение теперь имеет вид:
/0
у(1 ) _ I 0
Щ
10
\4
I
5
25
0
0
5
0
15
0
•,
0 0
10 0
О О
0 10
0\
15 \
ОГ
16/
Й
Проведя еще две итерации, получаем оптимальное решение
Х ^ = X * = | х*у || примера:
О 0
О 35
(
О
4
При этом:
5
4
2
2
0
0
5
0
15
0
О I
10 0
0 1
5
:|
О О О Г
0 0 26 /
’'
^Чх 1 ) ~
Щ Щ
■‘„Н8
Задача (30) — (33) имеет множество различных ин­
терпретаций. Применительно к автомобильному транс­
порту эта задача описывает следующую ситуацию. З а ­
даны п клиентов, каждому из которых требуется пере­
везти объем груза в С}] т, /— 1, п. Перевозки осуществля­
ются автомобилями разных марок, причем количество
имеющихся в наличии автомобилей 1-й марки составляет
Щ единиц, 1= 1, т . Использование одного автомобиля 1-й
марки у /-го клиента позволяет перевезти в планируемый
период времени рЙ т груза. Если обозначить количество
автомобилей /-й марки, распределяемых /'-му клиенту,
через Хг), то условия (31) требуют, чтобы каждому кли­
енту перевозки осуществлялись в соответствии с заплани­
рованным объемом; условия (32) ограничивают использо­
вание на перевозках подвижного состава, имеющегося в
наличии; условия (33) не допускают отрицательности пе­
ременных.
р|
В практике нередко система (31) — (33) оказывается
52
несовместной (имеющихся в наличии автомобилей недо-
статочно Для выполнения заданных объемов перевозок).
Если при этом нет оснований рассчитывать на увеличе­
ние парка автомобилей, то возникает серьезная пробле­
ма количественного обоснования снижения запланиро­
ванных объемов перевозок. При решении этой проблемы
следует различать три вида ситуаций:
все клиенты равноценны. Это означает, что невозмож­
но отдать предпочтение ни одному из клиентов и невы­
полнение запланированного объема перевозок любому
из них связано с одинаковым ущербом;
все клиенты неравноценны и невыполнение заплани­
рованного объема перевозок каждому из них связано с
различным ущербом;
часть клиентов равноценна, а часть неравноценна.
Сформулируем математические модели, описываю­
щие процесс распределения транспортных средств в пе­
речисленных ситуациях.
Первый вид ситуации (равноценные клиенты) ха­
рактеризуется тремя математическими постановками:
1) шах Д. —* га1п
1
1
(34)
при условиях
IX
V
(35)
/-1
лг/;- > 0, / = 1, т у / = 1, п\
2) шах ——
1
(36)
П11П
Я]
при условиях (35);
П
3) 2 Д/-*пип
/—1
(37)
при условиях (35) и
тп
V
^1]ХЦ < Оу* У==
п>
(38)
/-1
где
ш
— ^ ™IIхЦ. /"* 1> п
1=1
(39)
53
Рассмотрим кратко каждую из сформулированных
задач. Величины
(39) определяют объем груза, кото­
рый будет недоставлен /-му клиенту вследствие отсутст­
вия достаточного количества автомобилей. Критерии (34)
задачи ( 34), ( 35) предписывает так распределять транс­
портные средства, чтобы минимизировать самую боль­
шую величину А* /=1, я. Другими словами, критерий
( 34) обязывает распределять транспортные средства
так, чтобы максимальный (по абсолютной величине) недовоз груза среди всех клиентов был минимальным. Е с ­
ли выразить недовоз груза в относительных единицах,
то критерий принимает вид (36) и приходим к задаче
(35)—-(36). И, наконец, если не заботиться о равномер­
ном удовлетворении заявок клиентуры, а поставить цель
максимизировать суммарный объем перевезенного груза
(минимизировать суммарный объем неперевезенного
груза), то приходим к задаче (35), (37), (38).
Второй вид ситуации (клиенты неравноценны) доста­
точно полно описывается следующей математической
моделью: минимизировать
П
V
(40)
ж I сЛ,
при условиях (35), (38), где с,- — коэффициент, характе­
ризующий ущерб, связанный с недовозом 1 т груза /-му
клиенту, /= 1, п. Нетрудно увидеть, что при с=соп§1,
/= 1, п (клиенты равноценны) задача (35), (38), (40)
становится тождественной задаче (35), (37), (38).
Третий вид ситуации (по аналогии с первым) можно
характеризовать тремя математическими постановками:
1) шах А/
У 6 /а
при условиях
Ш1П
(41)
2)
тах ——
/е/«
(43)
шш
при условиях (42);
3)
Щ
(44)
Ду-»-тН1
при уровнях (42) и
т
\
1-1
где /, — множество клиентов /, груз которым должен быть достав­
лен полностью; \
.. .
/0 __ множество оставшихся клиентов (если в /2 входят неравно­
ценные с точки зрения недовоза им груза клиенты, то критерии
принимает вид:
г а *
2
.■
рай
Изучим некоторые свойства оптимальных решений
сформулированных задач.
Упорядочим клиентов по невозрастанию требуемых
объемов перевозок, т. е. перенумеруем их так, чтобы
%
|
О1 > <р > .. I > ()п-
Тогда имеют место две теоремы, приводимые ниже без
доказательства.
_
Теорема 1. Решение Х = IIя у II задачи (34), (35) является оптимальным в том и только в том случае, если
а,
]
_ Л
У= И
__________________
(47)
у*» ] = ^ + 1» Л.
Теорема 2. Решение Х = ||х«II задачи (35), (36) является оптимальным в том и только в том случае, если
Н
4Щ В
'
^ = /= Т7 Т .
яI
(«)
Условия (47), (48) являются конструктивными и по­
зволяют для решения задач (34), (35) и (35), (36) предложить простые итерационные методы.
Для решения задачи (34), (35) можно предложить
следующий алгоритм,
яШ Ш ёШ *
55
Алгоритм 11
1. Упорядочиваем клиентов в соответствии с (46) и
вводим новую нумерацию клиентов.
'
2. Задаемся некоторым значением 6.
;
3. Решаем систему уравнений вида:
т
7= 1,
2 ™ихи = $7 - 1
/-1
(49)
п
X1] —
—
1=
=
=1» /и;
(50)
/—1
>
0 , 1= 1, т
1, п,
,
II
1>
—
-
XI]
где Д
0ъ
/= Л + 1, л,
а индекс к определяется из условий: ЩйЩЬ, (2ь.+\<8.
4. Если система (49), (50) не имеет решений, то б
увеличивается, а если эта система имеет множество ре­
шений, то б уменьшается. В обоих случаях управление
передается в п. 3 алгоритма.
'^
5. Решение продолжается до тех пор, пока не будет
найдено минимальное значение 6, при котором система
(49), (50) разрешима. После этого следует вернуться к
прежней нумерации клиентов.
Алгоритмы решения задач {(3 5 ), (3 6 )}, {(4 1 ), (42)}
и {(4 2 ), (43)} аналогичны алгоритму 11 с той лишь раз­
ницей, что система уравнений (49) в каждой из этих за­
дач заменяется на:
I
для задачи (35), (36)
I
/=1
для задачи (41), (42)
т
2 т 1Iх I /
I =1
для задачи (42), (43)
т
56
—
° ) . Я р ® л;
Задачи {(35), (37), (38)}, {(35), (38), (40)} и {(42),
(44), (45) } являются распределительными задачами ли­
нейного программирования и для их решения можно
воспользоваться алгоритмом 9.
Отметим, что математические модели {(41), (42)},
{(42),ч(43)} и {(42), (44), (45)} являются наиболее об­
щими и из них остальные постановки вытекают как част­
ный случай. Например, если в задаче (41), (42) множе­
ство У ( пусто, то эта задача становится совершенно аде­
кватной задаче (34), (35) и т. д.
Рассмотренные математические модели, описываю­
щие оптимизацию процесса распределения транспортных
средств, находят широкое применение на автомобильном
транспорте. Например, задача закрепления клиентуры
за АТП может рассматриваться как транспортная зада­
ча линейного программирования только в случае, если
все автомобили имеют одинаковую производительность
на тонну грузоподъемности. В остальных случаях клиен­
тура не в состоянии однозначно указать свои потребно­
сти в автомобилях и представляет информацию о требу­
емых объемах и условиях перевозок грузов.
Рассмотрим задачу закрепления клиентуры за АТП,
содержащими автомобили с разной производительностью
на тонну грузоподъемности, введя предварительно сле­
дующие обозначения:
г — число АТП;
п _число клиентов (под клиентами здесь понимаем число ли­
ний перевозок);
С}; — количество груза, которое требуется доставить / му клиен­
ту (/=1. л), т;
т — число типов подвижного состава;
___
а,-* — количество единиц подвижного состава 1-го типа 0 = 1, м)
в к-м АТП (й=1ГгГ;
— грузоподъемность автомобиля 1-го типа т;
— производительность единицы подвижного состава «-го
типа из к-то АТП при работе у /-го клиента, т. Причем
I
V)Ш = 9Яи |
тн
Л01) _ А02) _ л
Г|^
.
„ , ,Р
+
Шш+ Ш + ш
где Г" — время в наряде;
и
время соответственно первого
и второго нулевых пробегов 1-гб автомобиля от /-го клиента в Л-е
АТП; * 1ьш— время пробега по /-й линии перевозки; г/Л/ и
/Д — время погрузки и разгрузки на ]-й линии;
количество
37
автомобилей 1-го типа из к-го АТП, работающих у /-го клиента
(/ = 1 , т , к— 1, г, ] = \ , п ).
Я
В принятых обозначениях математическая постанов­
ка рассматриваемой задачи записывается следующим
образом: составить план использования автомобилей
11* 1*^11 при условиях:
рН
г
т
_
Ф/*
2 2
й=д /=1
I
п
:М
(каждому клиенту груз должен быть доставлен полно­
стью );
П
^
___________________
^ ^
________________
I = 1, тп, к = 1, г
:•
(количество используемых на перевозках автомобилей
каждого типа не может превышать имеющегося в нали­
чии в к-м А Т П );
л-!!
Х щ Щ О, I — 1, т , к = 1, г, у = 1, п
(переменные не могут быть отрицательными).
В качестве показателя эффективности выбирается
минимум суммарных нулевых пробегов:
п
I
т
г
2 2
3
($■>
/= 1 /= 1 А=1
Сформулированная задача легко сводится к двухиндексной распределительной задаче линейного программи­
рования путем свертки индексов 11 к в индекс р — 1, 2,...,
Р, где Р —т г .
Щ
Рассмотрим еще одну нередко возникающую в прак­
тике задачу оптимального распределения транспортных
средств, в которой в качестве показателя работы автомо­
билей выступает время выполнения перевозок. Введем
следующие обозначения:
п — число клиентов;
— количество груза, которое требуется перевезти /-му клиен­
ту, /= 1, п;
т — число групп подвижного состава, используемого на пере­
возках;
____
Й
а, — количество автомобилей в /-й группа, 7=1, п\
т
ищ — объем груза, который может перевезти в единицу времени
один автомобиль 2-й группы у ^-го клиента;
Хц — время работы автомобилей »'-й группы у /-го клиента;
у. — время работы автомобилей »-й группы у всех клиентов.
Считается, что при осуществлении перевозок автомобиличкаждой группы всегда работают вместе, т. е. за­
прещается работа части автомобилей какой-либо группы
у одного клиента, а остальных — у других.
С учетом введенных обозначений условия задачи фор­
мулируются следующим образом:
т
^
_____
2 “ ’//а1хи ^
IД1
щш 1* п
Ир
(каждому клиенту груз должен быть доставлен полно­
стью) ;
№
2
I
= уг, *=!> т
(52)
/-*
(время работы автомобилей 1-й группы у всех клиентов
равно Уг)\
®
Х;^ > 0, / = 1, т , 7 = 1, п
(53)
(переменные не могут быть отрицательными).
Целевую функцию рассматриваемой задачи запишем
следующим образом:
шах уI
ш)п
(54)
г*ш
(максимальное время выполнения перевозок должно
быть минимальным).
Теорема 3. Решение X —||яг;|| задачи (51) — (54) яв­
ляется оптимальным в том и только в том случае, если
р;.
У\ = У2 ~ ••■— У т — У-
(55)
Доказательство теоремы здесь не приводится.
С учетом (55) критерий эффективности рассматрива­
емой задачи (54) принимает вид:
НЩ | ^ 7
’
У -*■ГШП,
а условия (52) заменяются ограничениями
(56)
Метод решения задачи (51), (53), (56), (57) анало­
гичен методу решения задачи (34), (35) (алгоритма 11).
В результате решения задачи (51), (53), (56), (57)
будет получено такое распределение автомобилей, при
котором автомобили всех групп будут заняты на пере­
возках одинаковое время, а время это, в свою очередь,
будет минимальным.
Глава 2. Д И Н А М И Ч ЕС К О Е П РО ГРА М М И РО В А Н И Е
2.1. Функциональное уравнение Р. Веллмана
Сформулируем задачу динамического программиро­
вания следующим образом:
а]
П
Г (А ') = ^
/у (■*/)-*■ т а х >
(58)
п
/=1
Е ( Х ) ) = Х ] > 0 , / = 1, п.
(60)
Решение этой задачи можно получить при помощи ре­
куррентного соотношения Р. Веллмана:
?,(//) =
где /=2, п,
ф о(Л )
шах
0<X^<N
[ /у С*;) + Ту—1
— ■*/)]*
(61)
=0, N=0, 1 ,2 ,...
Ниже приводится алгоритм решения сформулирован­
ной задачи методом динамического программирования.
Алгоритм 12
1. ср0(;У ): = 0 , N = 0 , 1....... N
2. Щ = I
3 . № = 0.
4. р: = — «5.
5. х } \ = 0 .
6 . а: = / ; { х ^-\-<?)- 1№ — х Л .
60
7. а > р ? Если это условие выполняется, то переход к
п. 8 алгоритма, иначе — к п. 9.
8. §: = а : Щ =х^.
9. л'7:
10. Х )> Ю Если условие выполняется, то переход к
п. 11, иваче — к п. 6.
и . ч;(р)'- “ Р; Ь(МУI 12. N1 Щ .Я Щ 1.
13. N > N ? Если условие выполняется, то переход к
п. 14, иначе — к п. 4.
14. Вывод ц>}(М) и
15. Перенос блока: ф_,-_|(/V) : =ф;(Л/^).
16. у: = у + 1, '
17. /> л? Если условие выполняется, то переход к
п. 18 алгоритма, иначе — к п. 3.
18. У: — п.
19. 7\Г: = N .
20- а: =фу(Л^).
21. Печать | и а.
22. И
=
а.
23. у: = у -4- 1.
24. щш0? Если условие выполняется, то переход к
п. 25, иначе — к п. 20.
25. Конец решения.
Проиллюстрируем изложенный алгоритм на примере
следующей задачи динамического программирования:
максимизировать
I
Г(Х)= 2
с ] [1 — (1 — ^/)ДГ-/]
при условиях
(62)
П
2
Ш Ж;
(63)
■Й
^
^
#(Ж /) =
^ 0, /== 1, Л.
(64)
Сформулированная задача часто встречается в раз­
личных экономических приложениях и характеризует
процесс оптимального распределения ресурсов.
Пусть, например, необходимо распределить N одно­
типных автомобилей для выполнения перевозок у п кли61
ентов. Считаются известными вероятности
выполне­
ния требуемых объемов перевозок одним автомобилем у
каждого из клиентов и относительные важности
этих
перевозок. Пусть далее §§ означает количество автомо­
билей, выделяемых /-му клиенту. Тогда вероятность
выполнения всех перевозок у /-го клиента составит:
1— (1 —
а математическое ожидание выполненного объема пере­
возок с учетом их важности у всех клиентов
Требуется распределить автомобили так, чтобы мак­
симизировать это математическое ожидание Р ( Х ) .
П р и м е р 11, Примем для выходных параметров сформулиро­
ванной задачи следующие значения: п = 3, N=9, с; =(0,5, 0,2, 0,3),
^•=(0,4, 0,3, 0,3).
Все промежуточные вычисления этой задачи по описанному выше
алгоритму сведены в табл. 1.
- щи
Т абли ц а 1
N
?! (■*!)
!
<м*1>
Ч>2 (*а)
Фз (-^а)
?»(■**)
Ф* щ Й
•
0
1
2
1
2
з
0
0,20000
0,32000
0,39200
0
0
0
0
0
0,20000
0,32000
| 0,41000
0
0
0
1
0,43520
4
0,45200
1
0,48200
1
5
0,46112
5
0,49520
1
0,54500
2
6
0,47667
6
0,53720
0,59820
2
3
3
3
4
0
0,2000
0,32000
0,39200
о
1
2
7
8
0,48601
0,49160
9
0,49496
7
8
0,56660
0,59252
3
3
0,64910
0,69230
0,61310
4
0,73430
9
Итак, математическое ожидание выполненного объема перевозок
с учетом их важности у всех клиентов будет максимальным, если
распределить автомобили между клиентами следующим образом:
Х опт= (4, 2, 3).
1 Н И
62
При решении задачи (58) — (60) по описанному алго­
ритму необходимо хранить в памяти Э ВМ функции
фМ (Л/) и <рДЛГ) =а такж е функции % (М ) , /=1~, п, фик­
сирующие те значения Ш при которых выражение (61)
достигает максимума. При помощи функций
оп­
ределяется искомое решение задачи (58) — (60) по пра­
вилу : \
Б
хп =
Ш
-*л—1=='Ь*—
-1
Ж
'
(Л/),
-*я) >
..........................................
(65)
*2 = <!$(ЛГ— — хя—I — ... — *з),
Ш
^1 *=
Т“
•- -«З—-*2>. й
Таким образом, в памяти Э В М для решения задачи
(58) — (60) методом динамического программирования
необходимо хранить У 1 = 2 (М + 1 ) + п (Л/+ 1) = (Л/ + 1) X
Х (« - г2 ) чисел. Предположим, что значения величин N
и «достаточно велики, т. е. У\>У, где V — количество
чисел, которое можно одновременно хранить в памяти
Э ВМ . Тогда для решения задачи (58) — (60) методом
динамического программирования можно предложить
следующий способ.
Решаем исходную задачу, запоминая в оперативной
памяти Э В М функции \|эДЛ/) для /= й+ 1, п, где индекс
к определяется из условия 2 (Л/+1) + (п— к) (N + 1) = V.
Используя формулы (65), определяем значения ис­
комых переменных X], ]' —к + 1, я. Размеры исходной за­
дачи теперь сократились и характеризуются величинами
Ш
■ М
АГ'^ЛГ- 2
•
т* ЩШк
Вновь решаем задачу, запоминая в оперативной па­
мяти ЭВМ функции | | р ! для /= 5+1, к , где индекс 5
определяется из условия 2 (ЛГ-)- \
—-5) (АТ-)-\ )= У По формулам (65) определяем х$, /= 5 + 1, к, сокра­
щаем размеры исходной задачи до
■
п
Щ. Щ;-4.
Ий
к
ЛГ = ЛГ- 2 *1 = Ы ' - 2 *1>
} =5+1
/“ 5+1
Н
п п =~ $, ■
решаем эту задачу и т. д
63
Описанный выше способ можно применять не только
в ситуациях, когда при решении задачи не хватает па­
мяти Э В М . Часто лимитирует оперативная память, но
почти всегда имеется возможность обращения к внешним запоминающим устройствам (магнитные барабаны,
диски или ленты). На эти устройства записывают значе­
ния функций г|)ДЛ0 порциями по V чисел. После вычис­
ления этих функций производится расшифровка полу­
ченного решения по формулам (65), для чего значения
этих функций порциями по V чисел считывают с внеш­
них устройств в оперативную память Э В М . При этом
приходится приблизительно
ц = 2 —Л
раз обращаться
к внешним запоминающим устройствам.
Я
Известно, что обращение к внешней памяти Э В М за­
нимает значительное время. Что выгоднее: одноразовое
решение при многократном обращении к внешним уст­
ройствам или многократное решение без обращения к
внешним устройствам? Ответить на этот вопрос одно­
значно, к сожалению, не удается, так как в общем слу­
чае ответ зависит от целого ряда факторов и предстоит
провести исследования для различных классов Э ВМ .
Однако уже можно с уверенностью утверждать, что для
Э В М с высокой скоростью выполнения элементарных
операций по сравнению с временем обращения к внеш­
ним устройствам (например, БЭСМ - 6) описанный спо­
соб решения задач динамического программирования
большой размерности эффективен.
1
Выше был описан алгоритм определения оптималь­
ной политики для процесса распределения, когда в на­
личии имелся лишь один тип ресурсов и на его использо­
вание было наложено только одно ограничение. Такие
процессы получили название одномерных процессов рас­
пределения ресурсов. Значительный интерес представля­
ют многомерные процессы распределения ресурсов. Ос­
новной формальный аппарат динамического программи­
рования переносится на эти случаи без изменения. Все
же при получении стандартных решений приходится
преодолевать значительные трудности, связанные с раз­
мерностью задач. Д ля преодоления этих трудностей ис­
пользуются математические приемы: различные формы
метода последовательных приближений, способ механи­
ческих квадратур, линеаризация, последовательная ап64
проксимация, увеличение шага сетки и др. Однако самым
мощным из них, безусловно, является метод множителей
Лагранжа.
Сформулируем следующую задачу динамического
программирования: максимизировать
П
(66)
Р (* ,П
при условиях
П
\
2
7=1
п
1
/
VI
(67)
7= 1
> О, У] > 0.
)
Решение этой задачи (по аналогии с решением зада­
чи (58) — (60)) можно получить при помощи следующе­
го рекуррентного соотношения.
Ч}№,'жМ)
.
тах
шах
0<х^<N 0<у
-+-<Ру—I(М — x^, М
[/у(дг;-, т~) +
] — 2, 3 ,..., п,
У
(68 )
где <ро(^> М ) — 0, ЛГ==0, 1, 2 ,..., N . М = 0, 1.......М .
Задача ( 66) — (67) характеризуется двумя типами
ресурсов. Процесс распределения однородных ресурсов
с двумя типами ограничений можно описать следующей
математической моделью: максимизировать
П
(69)
Г (Х )
при условиях
п
2
а) (х < А '
п
2
ш
< В'
Е (х/) = X ; > 0, / = 1, п.
Решение задачи (62)— (72)
пользования соотношения:
(70)
(71)
(72)
достигается путем ис­
65
<р,{А, В ) =
шах
тах
[/ ;(* ;) +
,
0<ву(Жу)<Л 0<*у{Х})<В
+ сру_1(А — а } ( х у), В — <^уС*;))]» У = 2» я*
где фп (Л , В ) = 0, <Р1 (Л , В ) =
тах
тах
а.(А-,)<Л й,(х,)<В
/х ( * 1).
Я
(73)
;|
Сравнение рекуррентных соотношений (61) и ( 68)
или (61) и (73) показывает, что качественно метод ре­
шения задач ( 66) — (67) и (69) — (72) абсолютно не от­
личается от описанного выше метода 'решения задачи
(58) — (60). Однако количественные изменения при пере­
ходе от одномерных процессов распределения к много­
мерным существенные. В связи с этим прибегают к раз­
личным
математическим
приемам,
позволяющим
понизить размерность задачи. Опишем здесь метод
множителей Лагранжа применительно к задаче (62) —
(64). Строим функцию Лагранжа для этой задачи:
Р ( X , X) = 2
/у ( * ; ) - * 2
а 1(*.Л
<74)
/=1
7=1
ц
и рассматриваем задачу нахождения максимума (74)
при условиях (71) и (72). Соответствующее рекуррентное соотношение имеет вид:
:^
СР; ( Я ) =
гг а х
[/ у
(х у)
—
\ а (х } )
+ <ру-1
(В — Ь; ( * ; ) ) ] ,
а величина л меняется в пределах, допускаемых ограни­
чением (70). И так, вместо двумерной необходимо решить
несколько одномерных задач. Число этих одномерных
задач определяется поиском оптимального значения мно­
ж и теля Л а гр а н ж а Я.
^
Рассмотрим зад ачу определения оптимального числа
автобусов на маршруте. Введем следующие обозначе­
ния:
п — число маршрутов движения;
— количество пассажиров, которое требуется перевезти по
/’-му маршруту; /= 1, п\
\Щ Щ
т — число типов автобусов;
ах — количество имеющихся в наличии и готовых к выпуску на
линию автобусов /-го типа, /= 1, т \ ____
<
7,-— вместимость автобуса 1-го типа, 1= 1, т\
Хг] — количество автобусов /-го типа, работающих на /-м марш­
руте, /= 1, т , /=1, п\
-М
N ^— минимальное количество автобусов, работающих на /-м
маршруте,/=1, п.
19
66
С учетом введенных обозначении условия рассматри­
ваемой задачи математически записываются следующим
образом: определить потребное количество автобусов
Х**\\хц\\т п при условиях
I
\
т
2 41*1} > К
/
в
7
п
(75)
1
(по каждому маршруту должны быть перевезены все
пассажиры);
I *
п
2 X I] > Щг 1 = 1 , т
(76)
Ш
(количество используемых автобусов не может быть
меньше имеющегося в наличии по каждому типу);
Ц /;
т
_____
^ Х 1 ) > N }, / = I, п
г;; • ■
1-1
1
(77)
(на каждом маршруте количество работающих автобу­
сов не должно быть меньше некоторого заданного числа,
величина которого регулирует интервал движения авто­
бусов на маршруте), где
|*.
х ц > 0 , 1 = 1 , т , ] — 1 , п.
(78)
В качестве показателя эффективности выбран крите­
рий «минимум используемых автобусов». В условиях
(75) — (78) этот критерий математически формулируется
следующим образом:
Н|
/ Я Л .
/7= 2
2
/-1 /-1
х 1 ]~* т *п-
(79)
При использовании этого критерия задача определе­
ния оптимального количества автобусов на маршрутах
формулируется следующим образом: минимизировать
(79) при условиях (75) — (7 8 ).
Сформулируем необходимые условия существования
решения задачи (75) — (79):
т
п
2 я/ > 2 м )'
/-1
/-1
т
(80)
п
2 9Ш > 2
*-1
У-1
67
начинаться
Следовательно, решение задачи ^ должно
с проверки выполнения этих условий.
Если
п
т е
/-1
то необходимо положить
/г
т е
й/г— 01%
/=1
(I
где индекс Л определяется из условии
шах
1</<те
Если после этого условие (80)
необходимо положить
не выполняется, то
т е
V №8
/ =1
ак = а к + Е
Чъ
и равномерно увеличить величины ЛЛ,- так, чтобы выпол
нялось условие
п
т е
гт 1
7=1
После осуществления указанных преобразований за
дача ( 75) — ( 79) сводится к решению следующей систе
мы:
п
х\) =
, /= 1, т\
;=1
т е
V
/ =1
т е
([фЩ] ^ 0
/==1
68
(81)
где
т
2 «Я
п
■У
N г
■—
7»
/-1
(82)
п
т
2
4Р1
М
> 2
/=*1
<?/•
Легко показать, что при выполнении условии (82)
система (81) всегда имеет решение. Значительный интеоес представляют методы получения целочисленного ре­
шения этой системы. Изложим один из алгоритмов цело­
численного решения системы (81). Суть этого алгорит­
ма сводится к следующему.
Разобъем процесс решения системы (81) на
раций, на каждой из которых решается следующая оптимизационная задача:
т
-> Ш Ш
'X
I
2
1= 1
т
2
1 ‘х 11
/■=*!
}
т
•
^
А
II
2
Щ
1-1
(83)
Р-—1
О< х{
< Я/
—
2л ч
1, т\
7=1
)
Решение этой задачи легко получить методом дина­
мического программирования. Реш ая последовательно
задачу (83) для р= 1, 2, ..., п, получим искомое решение
задачи (75)— (79).
Опишем теперь последовательно метод решения за­
дачи (75)— (79).
Алгоритм 13
1. Проверка выполнения условия:
Если условие выполняется, то перейти к п. 2, в против­
ном случае — к п. 4.
:'
2. Определение индекса к из условия
^ъ= гпах
'Щ
1<1 < т
п
т
3. а к:
— Ш а 1'
;~1
1-1
4. Проверка выполнения условия
т
п
2 9№ < 2
1-1
7—1
Если условие выполняется, то перейти к п. 5, в про
тивном случае — к п. 6.
п
т
2 Я ]— 2
5. а к: = а ь+ Е \ - ^ ---- — ---- /+ 1,
Як
где индекс к определяется из условия, сформулированного в п. 2.
6. Проверка выполнения условия:
т
п
V
а1= 2 Щ *
I
Если условие не выполняется, то перейти к п. 7, в
противном случае — к п. 8.
7. Равномерное увеличение величин ЛЛ,- так, чтобы
выполнялось условие, сформулированное в п. 6.
8.
/:
=
■
[И
1.
9. Решение методом динамического программирова­
ния задачи:
•' '. . -V•.
т
2 Ч1Хц-*т\п\
1~1
т
2 4!хи
.з
I —1
т
2
1-1
}-1
:::
О < х Ц < а, — 2 х 1у.< 1= 11 Щ
11.-1
Е(Х[А = XI], I =
70
1, т .
'
г
-
Метод решения этой задачи будет изложен ниже.
! 10. /: = /+ 111.
Проверка выполнения условия / ^ я ? Если усло­
вие выполняется, то перейти к п. 9, в противном слу­
чае;— к п. 12.
ГС. Конец решения.
Задача, сформулированная в п. 9 алгоритма, реша­
ется мьтодом динамического программирования. При
этом можно воспользоваться двумя способами. Первый
из них состоит в решении следующего рекуррентного со­
отношения:
I
№Ц
'
<?•[((?.-, ЛГЛ =
|Ь; ‘
пип
пир ш Ш Ш
ЩЩ}
/Х11$^ $
*== *> т >
— Я1хи*
где <р1 (С);, N у) =
т\п
;
%
пип
При втором способе необходимо, используя множи­
тель Лагранжа, образовать функцию
|р
т
ЙЙ:
ЩШ:-'
\
/ т
х) = 2 41хц - * 2 ч ***/ й
рЩ|
\*«1
)
/
н тем самым свести задачу к одномерной. Далее оптими­
зация ведется для выражения
/ 1 {Х , А )=
V', :
где
Кт
|
/{X ,
*'
Х )=
пип
[ф/Сгу, X) +ф ,- 1 (Л^;-— хц, X)],
^
*”
шш
^ 2I
1
1
• • I»
%
т
^1 ( х / у , X).
хц<**}
2.2. Разностный метод
Рассмотрим матрицу А = IIш II приращений целевой
функции (58) задачи (58) — (60):
д * У = / д * )-/ у (* -1),
/ у (0) = 0 ,
к = Т к , ]= Т~п
7
и предположим, что для всех к= 1, 2,
N и /= 1, 2, ...,п
выполняется Дь-ь }^А кз, т. е. в матрице приращении це­
левой функции (58) элементы в столбцах расположены
в порядке невозрастания
К?
Д 1у > Дз/ ^
^ Адгу,
1» я»
(8^)
71
Теорема 4. Если приращение функции (58) обладает
свойством (84), то разностный метод приводит к ее мак­
симуму в области (59)-(60).
Доказательство. С вводом элементов матрицы А —
= ЦД/^11 функция (58) принимает вид
р
п Х)
2 2 Щ-
'
Это следует из (58), если представить
так:
Ш
/,(Х])р=Щ
у, [//(^)—/д*—он й2-1 1 ■
/= я*
''
—
Преобразуем матрицу А в вектор {А*}, 5 = 1, 2,
5,
5 —пЫ так, чтобы элементы А* образовали ряд по невоз­
растанию
Д] > Д2 > . . . » Ад.
(85)
Элементы ряда (85) обладают тем важным свойст­
вом, вытекающим из (84), что, если Д8=Аад, то найдется
такое К з , когда Дг=Дд_ и . Это свойство позволяет
предложить конструктивный метод построения решения
задачи.
. ..
УЩ Ш ш
Составим сумму первых г элементов вектора
Ш
<?,=2 М
В силу отмеченного выше свойства ряда (85) очех2
.
-V,.
п }
п
видно, что <рг= 2 2 АЛ<= тах , причем V Х )— г,
зна/=1
{х; }
/=1
чения X] определяются числом наибольших элементов
/-го столбца матрицы Д=|!Дь;11, попавших в последова­
тельность {Д ь Дг,
Аг}.
Таким образом, используя разностный метод, т. е.
последовательно двигаясь по наибольшим приращениям
целевой функции (элементам ряда (85), на каждом ша­
ге получаем оптимальное распределение г (г = 1, 2, ...)
ресурсов и в конечном итоге при г—N — оптимальное ре­
шение задачи. Теорема доказана.
Опишем алгоритм решения задачи (62) — (64) раз­
ностным методом.
70
/~
Алгоритм 14
1 Г : = 0, N1 = 0.
2. Х}: = 0, у = 1, 2, . . . , в.
3. г.-: = /у(1), у = 1, 2,..., п.
4. Найти индекс 5 из условия г5= т а х г;-.
5Д Р: = ^ + г „ 77: = N + 1 .
6.
= х л-\-1.
^ 1. г% — / з (хз~\“ 1) —/ Л хзУ
*
I
I
8. Проверка выполнения условия: N<N1* Если это
условие выполняется, то перейти к п. 4 алгоритма, ина­
че— к п. 9.
___
9. Вывод результатов решения (Р и
/= 1. п) на
печать — конец решения.
Из теоремы 4 вытекает ряд следствий.
Следствие 1. Если функции /у(х,) вогнуты, то раз­
ностный метод приводит к получению оптимального ре­
шения задачи (58) — (60).
Следствие 2. Если функции /;(*,) линейны, то струк­
тура оптимального решения задачи (58) — (60) имеет
вид:
где индекс \ определяется из условия
К
'.
Л/ = шах
= шах /у (1).
7 ’
/
Следствие 3. Для того чтобы вектор А' = {х ,} являлся
оптимальным решением задачи (58) — (60) при условии
(84), необходимо и достаточно выполнение условий:
тпI п [/ у (* у )— /у (дгу — 1)] > тах [/у (ху -г 1) — / ;(* / )]»
%,
Щ
К
/€Л
***'
(86)
тах / у (1) < 1П1п [/ у (х у )— /у (дгу — 1)],
■
/€/.
/ел
где
В
/1= {;: X) > 0), /2= {/: */ = 0).
Сформулированное в виде необходимого и достаточ­
ного условия оптимальности предполагаемого решения
Ш
73
следствие 3 носит конструктивный характер и позволяет
модифицировать разностный метод решения задачи
(58)_(60) при условиях (84) при помощи следующего
алгоритма.
а
Алгоритм 15
1 Отыскание
формулам:
начального
е
г(0)
Х1
,
Ш
решения
[ — \ , ] ш* Х ъ
П 2
л
щ
_________(
п
/ Л
— \*1 ) «о
I;
ЛП
Е \ — I + 1, У * 1» п >
■
с -Я
где 5 — N — п с .
п
2. Вычисление приращений функции (58) по форму­
лам:
А; (х}) = /у (* ;) — // (*/ —
^^{x^ + 1)== // Ш? + О
// (х/)*
..Л И
/= П 2 ,..., л.
3. Определение минимальных и максимальных при­
ращений функции (58) по формулам:
■*!
А* (х*) = шш Д;-(ху);
Д / (х / +
1 )=
Д
™ а х Д у ( х ; + 1).
ЧЯ
4. Проверка выполнения условии ( 86 ):
.3
П|1п[/#(Х|)— / у (х у-— 1)] > т а х [ / ; ( х , + 1 ) - / у (х ,)];
/6 Л
1 6 1*
т а х [ / ; (1)] < т т
у е /*
где /1= {у: х ; > 0 ) , /2=
[ / > (х у ) — / у (х у
/ 6л1
1)],
Я
:Д
х; = 0 |.
Если эти условия выполняются, то перейти к п. 6 ал­
горитма, иначе— к п. 5.
,;■«
5 . х к\ = х к— 1, х,: = ЛГ,-{-1, вычислить приращения
д* (■**)• Л/
и перейти к п. 3 алгоритма.
1
6. Вычислить значение целевой функции по формуле
Рт
!
= 2
/у <*!).
1-1
где X* — оптимальное решение задачи.
Конец решения.
Максимальное количество вычислительных итераций
по модифицированному разностному методу
в то время как немодифицированный метод всегда дает
итераций. Сравнение оценок Ямоц, и /? показывает,
что объем вычислений по модифицированному методу
меньше.
При этом эффективность его применения возрастает
®ри Ы-*-оо и я->2.
Проиллюстрируем действие алгоритма 15 на следую­
щем числовом примере.
П р и м е р 12. В условиях примера 11 решить задачу (62) —
(64) модифицированным разностным методом.
Докажем прежде всего, что для решения задачи (62) — (64)
можно применять разностный метод. Очевидно, что для этого доста­
точно убедиться в вогнутости функций
и воспользоваться след­
ствием 3.
Покажем, что Р (Х ) — вогнутая функция. Для этого достаточно
установить вогнутость функции одного переменного <р(Х), определен­
ной следующим образом:
п
<Р(X) = р (2 -ь Х5) = 2 0}(1 - А,В)),
Н
•
/-1
Ш,
где 2 и 5 — произвольные вектора,
'■
—
А ]= е
2 ? »
а
.
—
Щщ е
5
-
л
.
---------------------------
, ау = — 1п (1 — а;у), у == 1, п.
Определяем вторую производную функцию ср(Я):
Ш
И
Ш-
^ ^ -= — V ! С/Л/В) Ы В ) < 0.
дХ2
^
1 ,1
1
Итак, ф(Х) — вогнутая функция. Следовательно, и функция Р(Х)
вогнутая.
Значит для решения задачи (62) — (64) можно применять разност­
ный метод.
ИШ §-.-
.
75
Теорема 5. Вектор Ж- {X}} является оптимальным решением за
(64) тогда и только тогда, когда выполняются соотно
дачи (62)
шения:
хг \
ув Л
С }1&)] (1 — XVу)
где /1 = {у: лгу
> №'&% С /Ш ] (1
ДОу)
/еА
тах С/ДО/ < т т С Зв{1
/ 6А
У€Л
)\ X) 0).
> 0 }, /2
,
(87)
ДОу)
Г 1
Доказательство. Поскольку функция (62) является вогнутой, то
критерий оптимальности решения задачи (62)— (64), записанный в
общем виде совпадает с условиями (86). Приращение, получаемое
функцией (62) при назначении (л^-Н)-й единицы ресурсов, вычис­
ляется так:
) [ 1— (1 — да/) ']
Ь ] ( . Х ] + \ ) = С} [1 — (1 — 10])
X]
= С]Ф] (1 — Йу) •
(88)
Подставив (88) в (86), получим (87). Теорема доказана
Таблица
2
Приращение функции
X
Л, ( х
)
Способ вычисления
функции Р { Х )
Д,(Х)
*•< *)
1
0,20000
0,0600
0,09000
2
0,12000
0,0420
0,06300
С]П>](
3
0,07200
0,0294
0,04410
СуО>у ( 1 —
® у)2
4
0,04320
0,03087
С ] ® / (1
® ;)3
5
0,02592
|
С
1—
—
С / ® 7- ( 1 —
*0у)4
*
Решим теперь пример 12, сведя все промежуточные вычисления
в табл. 2. Итак, оптимальное решение примера: А* = (4, 2, 3), т. е. ре­
шение совпало с полученным ранее решением примера 12. Отметим,
что если для решения этого примера разностным методом требуется
девять итераций (так как Лг= 9), то модифицированный метод (алго­
ритм 15) позволяет получить оптимальное решение уже на первой
итерации.
л-:
Рассмотрим задачу расчета оптимального суточного
запаса агрегатов и узлов автомобилей. К ак известно, од­
ним из необходимых условий успешной эксплуатации
76
подвижного состава автомобильного транспорта являет­
ся своевременное и быстрое устранение неисправностей
и отказов, неизбежных в процессе эксплуатации. Поэто­
му текущий ремонт подвижного состава рекомендуется
осуществлять преимущественно агрегатным методом,
при котором заменяются неисправные или требующие
капитального ремонта агрегаты и узлы на исправные,
взятые из оборотного фонда.
Суточный запас агрегатов и узлов автомобилей в
АТП, как правило, определяется интуитивно. В резуль­
тате такого планирования некоторые агрегаты и узлы
могут оказаться в избытке, других же может не хватать.
Задача формулируется следующим образом. Заданы:
число марок и количество автомобилей по каждой мар­
ке в АТП, количество агрегатов в автомобиле каждой
марки, вероятности безотказной работы за планируемые
с у т к и каждого агрегата в автомобиле и нового агрегата,
сумма средств, выделенных на суточный запас. Требует­
ся определить количество агрегатов, обеспечивающих
наиболее эффективное выполнение сменно-суточного за­
дания на текущий ремонт, не выходя за рамки суммы
средств, выделенных на суточный запас. Введем следую­
щие обозначения:
т — число марок автомобилей в АТП;
йг— количество автомобилей 1-й марки;
т — количество агрегатов в автомобиле г-й марки;
Зц — стоимость /-го агрегата автомобиля Щ марки, руб. 1= 1,
.
■ВС-
V
■
Ш-Л-
ЯР
Ж,
—
т * 1—и ***\
вероятность безотказной работы /-го агрегата к-то авто­
мобиля *-й марки за планируемые сутки при условии,
что к началу суток агрегат исправлен;
рц — вероятность безотказной работы нового /-го агрегата
(с первоначальным нулевым пробегом) автомобиля М
марки, 1= 1, т , /=1, я;
а*. — коэффициент относительной важности работы к-то авто­
мобиля г-й марки. 1= 1, т у к —1, а».
Хгы — признак, показывающий необходимость приобретения
/-го агрегата для к-го автомобиля 1-й марки, причем
(1, если агрегат необходим,
*1Ъу/= {(0,
Л
если агрегат не нужен;
5 — общая сумма средств, выделяемых на приобретение су­
точного запаса агрегатов для всех автомобилей всех
марок, руб.
77
В математической форме условия рассматриваемом
задачи записываются следующим образом: составить
план приобретения новых агрегатов Х = II х 1Ь;\та.п. при
условиях
________________у;о
и ли
1,
1, т , ] =
, л* , к — 1, а/
(89)
х1к]
(если /-й агрегат приобретается для к-то автомобиля
1-й марки, то Хгы=\, в противном случае
Ц
т
М.
а1
1/-1
(общая сумма средств, затраченная на приобретение новых агрегатов, не должна превышать заданную).
В качестве критерия эффективности решения данной
задачи принят максимум среднего количества (матема­
тического ожидания) безотказно работающих в течений
суток автомобилей, взятых с коэффициентами их относам
тельной важности. Д ля математической записи этого
критерия предварительно заметим, что выражение
.•*
Ц'щ
Р щ (1 — -*;&;) + Р ц *Щ Щ р\к) — Х » 1 Щ Щ ~ Р ‘Я
Щ
дает вероятность безотказной работы /-го агрегата к-щ
автомобиля 1-й марки в течение суток с учетом его воз­
можной замены.
Вероятность безотказной работы к -го автомооиля
1-й марки запишется как
, |Ш Ш |
'
Щ
у ^ ';
^.'-1;
т
а-
п;
представляет собой математическое ожидание общег®
числа безотказно работающих автомобилей с учетом их
важности. Отсюда критерий эффективности решения
данной задачи математически записывается следующим
образом:
Я
т
2
а-
п-
2 §к П |Й! |
7=1
78
хЛ] ЩЩРц)\ §§ т а х .
(91)
Если, например, с** — доход за сутки от 6-го автомо­
биля 1-й марки, то выражение (91) означает, что макси­
мизируется математическое ожидание общего дохода за
сутки. Сведем трехиндексную задачу (89) — (91) к двухнндексной путем свертки индексов * и к:
\
,
V
|г
<?
пя
2
^-1
П
/*»1
\
<2 пя
И Г * *'* 8 '
В | ;
.
(92)
2
2
$я*хя/ <
(93)
/-=1
Хд] = 0 или 1, ^ = Т Г О ,
где д= I -Ь л* (&— 1)', 0 = 2
/ = Г, пч%
;
(94)
а 1-
Нетрудно показать, что целевая функция (92) задачи
(92) — (94) вогнутая (выпуклая вверх). Следовательно,
задача имеет один экстремум. Для получения точного
решения задачи (92) — (94) можно применить метод ди­
намического программирования. Однако разработка это­
го метода для Э ВМ нередко связана с определенными
трудностями. В то же время имеется круг задач, опти­
мальное решение которых может быть получено при
помощи частного случая динамического программирова­
ния— разностным методом. Применительно к данной за­
даче разностный метод в общем случае может не привес­
ти к получению оптимального решения из-за условия
(93). Однако ввиду вогнутости функции (92) и булевско­
го вида переменных (94) можно с уверенностью утверж­
дать, что получаемые при помощи разностного метода
решения задачи (4)'— ( 6) будут всегда либо оптимальны­
ми, либо близкими к нему. Опишем алгоритм решения
этой задачи.
ИЩ Ц
Алгоритм 16
1. 5°: = 0; <
7: —
р; -2.
— 0.
===1*
[к — 1), (}: = 2 а1.
Я
Ь С?*
79
3
Рюси
л9/
Р\]5И1
фиксирование
индек­
0.
5. V»"
5°41, 5°:
6. Ху.,:
5?
Если
условие
не
выпол7. Проверка условия: 5
няется, переход к п. 9.
8. Переход к п. 4.
0
5 ° — 5.IX** ^ Р*
9 . 5 °:
я
о
г
П [р
Рд/)1 *
Х*1 (Р
10. Г.
я—1 } =1
11. Переход к индексам / и к:
т , если Е
Я
т
т
I:
Я
Е
Я
т
т , если Е
т
т
т
т
к:
Е
Я_.
Я
ЯП1, если
а Ьг [ 4
т
т
Я
Я
1 1 , если Е
Я
Я
т
т
12. Конец вычислений.
Глава 3 В Ы П У К Л О Е П Р О Г Р А М М И Р О В А Н И Е
3.1. М ето д в о зм о ж н ы х н ап р авл ен и й
Сформулируем общ ую задачу математического про­
граммирования следующ им образом: в области /?, опре­
деляемой ограничениями
/|(АГ) < */,
X >0
и
(9$)
(98)
задана целевая, в общем случае нелинейная функция
ф ( Х ) . Требуется найти такой Х е Я , для которого спра­
ведливо
ЯП
(97)
ю ( Х ) = шах 'р(А ).
ХРЯ
В этой формулировке X — вектор (матрица) с п ком­
понентами; ?/(Х) — функции (линейные или нелинейные)
от X. Предполагается, что функции <р и /ч имеют непре­
рывные первые и вторые частные производные. Вектор
Х ^ Я называется оптимальным, если для _любого друго­
го вьктора з И || выполняется условие ф (Х )^ ф (Х ).
Обычные аналитические методы решения задач на
условАлй экстремум (например, метод множителей Л а­
гранжа) не могут быть использованы для решения зада­
чи ( 95) — ( 97), так как они не учитывают ограничений в
форме неравенств.
Введем следующее определение. Область Я, опреде­
ляемая условиями (95) — (96), удовлетворяет условию
регулярности, если существует внутренняя точка этой об­
ласти, т. е. если для любого 1е=[1, 2, ..., тп\ существует
Х ^ К такой, что [{(X ) <Ь{.
Обобщение метода Лагранжа на случай решения, за­
дач математического программирования (95) — (97) да­
ет основная теорема общей теории математического про­
граммирования, которая формулируется следующим
образом: пусть область Я, определяемая условиями
( 95) — (96), удовлетворяет также условию регулярности.
Тогда для того, чтобы X был оптимальным решением
задачи (95) — (97), необходимо существование вектора
Й = {й г} такого, что
Ф'Х ( Х , Т п < 0 , (Ф'х , Х ) = 0, Х > 0 ;
(98)
и >о,
(99)
Ф ’и ( х , ( 7 ) > о , (ф ц ,
=
Ш
где Ф ( X , I I ) == (X ) + 2 ^ 1 [Ь ’1
// ( А )]»
( 100)
81
Достаточным условием оптимальности X является
существование
удовлетворяющего (98) и (99), при
условии, ЧТО ф ( Ж ) — вогнутая,
выпуклые функдни 1= 1, 2,
ЩСформулированная теорема для вогнутой функции
ф;(ж| и выпуклых функций /г(Х) известна в общей тео­
рии математического программирования как теорема
Куна и Таккера об эквивалентности задачи выпуклого
программирования задаче определения седловой точки
функции Лагранжа (100) при условиях (95), (96) и
1/3*0.
*
-Ш
ш *'
Дадим определение задачи выпуклого программиро­
вания и сформулируем признаки оптимальности ее ре­
шения.
С ’• -йШи
Задача максимизации ср|Й), Х е У ? или т а х (ч>(^) •
называется задачей выпуклого программирова­
ния, если: ф (Х )— вогнутая дифференцируемая функция
с непрерывным градиентом <р'(А’)=(«Рх11
?*„)>
область Я — множество точек, определяемое соотноше­
ниями
Й§ЙЙ 2 , . . . , т , Х ^ - 0 },
где 1г{Х) — выпуклые функции, удовлетворяет условию
регулярности.
У УУЯ
Решение задачи выпуклого программирования можно
получить методом возможных направлений, представля­
ющим собой реализацию метода наискорейшего спуска.
Направление ^/= (« 1, “ 2,
Щ§ в точке Х б Я называ­
ется возможным, если достаточно малое перемещение из
X в направлении V не выводит за пределы области, т. е.
если найдется достаточно малое число Я > 0 такое, что
Х + Х11^Я- Возможное направление I I в точке X назы­
вается подходящим, если
/ду (X + Ш ) \
I
Л
11^ ' (X ) , ^ ) > 0 .
/х=о
■
''у.. * "
Д ля того чтобы направление V в точке X было воз­
можным, необходимо выполнение следующих условий:
(/ ;(* ), 1 Г ) < 0 , 1ЬЦХУ, 1
Ч }> 0, уб Л Х ),
I
где
/ (Х )= {/ :/ 1(Х )= Ь 1);
82
*у = 0}.
(101)
Если /,-(Х)— линейные функции, то условия (101)
являются также и достаточными.
Для того чтобы <р(Х) достигала максимума на /? в
точке Х ^ К , необходимо и достаточно, чтобы выполня­
лось условие (ср'РО, {/ )< 0 для любого V, удовле­
творяющего условиям ( 101).
Течка ЙЯщ! есть точка максимума функции ср(Х) тог­
да и Только тогда, когда градиент ср(Х) в точке X может
быть Представлен в виде линейной комбинации с неот­
рицательными коэффициентами
внешних нормалей
в X, т. е.
< ? '(* )=
I
2
Для любого
шШ
Ш
Ш
2
] едх)
Р ;Х / , а,-> 0 ,
Эу > 0 .
справедливы неравенства:
Ш
шах ©( X ) — «р( X ) < гпах('р/ ( Х ) , X )
хея
(<р' ( X ) , Х)>
шах ф(X ) — *?(Х) < шах (<?' ( X ) , Х ) ~ - ||| ( X ) , X ) ,
где /?' = [X : ( / ; ( X ) , Х ) < { / ] { Х ) , Х ) + * ^ / П Х ) >
(102)
(103)
| Ц I, Щ
х> щ :
'
1 , У•^-М ; : ,* г; ^
По смыслу /?' представляет собой область пересече­
ния полупространств, образованных гиперплоскостями,
касательными к функциям [г(Х ) в точке X . Соотношения
( 102), (103) используются для оценки точности решения
задач выпуклого программирования методами возмож­
ных направлений.
Изложим один из алгоритмов метода возможных на­
правлений применительно к задаче выпуклого програм­
мирования — задаче (95) — (97).
||
Алгоритм 17
1. Пусть
Х {0)€ % — начальное (исходное) решение
задачи выпуклого программирования (95) (97) и е
заданное малое положительное число.
V7,(^)
^^
У V * ^• ЛППАл
2. Предположим, что
Л , л
л
оире
делены.
3. Решаем вспомогательную задачу линеиного про­
граммирования для определения возможного подходя■
II
83
щего направления. Если М Л -линейны е функции, то
формиру
Если же 1г(Х) нелинейны, вспомогательная задача
ставится несколько иначе, а именно.
шах {*„:
хек
(/;
- 1У ( * (Й)). ^) + ^0 < - ('Р '(А (6)). * (й)) ’
х) + 0хо < (/; (
Л
,
Х (й))
+ Ь,-/1 (*< >}.
I
П усть Х (к) — решение вспомогательной задачи. По/ /Х*) — ЛУ ^ — а
ч?!11
ЛОЖИМ и
4. Если 6/(й)= 0 , то X
— оптимальное решение.
Если СГ{к) ф 0, то перейти к п. 5.
5. Определяем Яь из условия
где ХЙ1 = шах {X:
X* = пип {ХЙ1,
|
А'(Ь) + Ш (к) 6 Л } ,
( 104)
а Хй, удовлетворяет условию
= шах { ( ? ( А ^ + Ш ^ ) : Х < Х Й1).
(105)
Если область Я образована линейными ограничения­
ми, то Хь, =1 и задача (105) сводится к отысканию мак­
симума <р(х) на сегменте
[ Х (*\ Х т ].
В противном
случае (104) представляет собой задачу о максимуме X,
удовлетворяющего условиям
/,(Л Г (Й)+ ^ 1 *)
= 1, от.
6. Находим Х (к+1)= Х^к)+ 1ки {к) и значение
функ­
ции ср(а г(А+1)).
'■ ' ' ^ 1 ч ш Я
7. Если ш (^ (йт1)) — <р{ Х ^ )
е»
процесс решения прекращается. В противном случае вы­
числения в пп. 3— 6 повторяются.
Решение задачи выпуклого программирования можно
оценить при помощи формул (102) или (103). Пусть, на­
пример,
— приближенное решение задачи, а X — ее
точное решение. Тогда
хек
84
_
(/?, если // (А*) — линейные функции,
(/?', если / [ ( X ) — не только линейные функции.
Следовательно, решая вспомогательную задачу, получаеы Ц ' " = Х т - Х т , и о (,'0 - » (А '<н)< 4», где
Д„ =е( ? '( * (*’). У т )Если Дй< е, то Х { —оптимальный вектор. В про­
тивной случае Х (к) следует улучшить.
П р и м е р 13. В условиях примера 11 решить задачу (62)— (64)
(без условия целочисленности) методом возможных направлений по
алгоритму 17.
•
Выберем в качестве начального решения Х<°> оптимальное цело­
численное решение этого примера, полученное ранее методом динами­
ческого программирования: Х ^ = (4, 2, 3).
Решаем вспомогательную задачу линейного программирования
для выбора возможного подходящего направления. Поскольку усло­
вие (63) линейно, то задача эта имеет вид:
ВЦ
п
.
ь (X ) = 2
тах
(106)
при условиях (63), (64), где Щ т
= 0 /1 ) 1
3 1
— (1
® /) " |____________
у а/== — 1п (1 — Ш ;).
Произведя вычисления, получаем:
(0,0331, 0,03504, 0,03670).
Задача (63), (64), (106) является линейной задачей с одним
ограничительным условием. Решение ее имеет вид:
х
I — 1'
где индекс / определяется из условия
9).
= тах 4).
Итак, получаем решение вспомогательной задачи:
Т-4'" \
4
_
лг(0)
ДО*
•
* Находим далее по формуле 6/(0)= X — Х т компоненты вектора 0 к
— 2, 6).
Поскольку
ф 0, то Х (0) — неоптималыюерзшение. ^ Опре­
деляем величину шага Хо из условия Х0 = пип {X , /}, где X опре­
деляется из соотношения
Р (*<°> + Х'6г(0)) = шах Г ( ^ (0) + Ш
<0)\
Применительно к решаемому примеру X' определим из решения
следующего трансцендентного уравнения:
■
85
или после преобразовании
л
^
л
ф(Х')«
- * Ж °Л Х
1 у*
1 ) =0'
V
Решив это уравнение относительно Я,, получаем: Ло=0,038.
Определяем следующее приближение по формуле
Х ( 1) = ^(О + Х ^ 0».
Имеем: *
= (3,848; 1,924; 3,228).
Вычисляем
значение функции (62): Г ( Х (-1;) = 0,7345.
Поскольку /Г (АГ<1)) - Р (ЛГ(0)) < е, * = Ю 3, то решение за­
кончено.
I
■
?
3.2. Условия Куна-Таккера
Необходимо отметить, что условия Куна-Таккера, бу­
дучи необходимыми и достаточными для оптимальности
предполагаемого решения, в то же время не дают вычис­
лительного алгоритма для нахождения оптимального ре­
шения. Однако во многих случаях использование усло­
вий Куна-Таккера позволяет установить структуру опти­
мального решения задачи, изучить ее свойства.
Вернемся еще раз к задаче (62) — (64) и изучим струк­
туру ее решения при помощи условий оптимальности
Куна-Таккера.
Составим для задачи (62) — (64) функцию Лагранжа
ф х ( X , X) = У
/=1
су
[1 — (1 — г » ) ) 1]
+ X ( N — У\ х \ .
\
/-1
(107)
/
Основная теорема утверждает, что для оптимально­
сти вектора X необходимо существование числа л тако­
го, что
%
(108)
Ф х(Х , X) = 0.
После дифференцирования (107) условия (108) при­
нимают вид:
'
И Н Н
86
или
-»/** ( < х, х*= о,
еца.]е Щ й
_
I — х, х>> о.
(110)
Поскольку функции С][\ — ( \ — и);)х 1]— с](\ — е “/*/')
в задаче (62) — (64) вогнутые, то (109) являются также
и достаточными условиями для оптимальности вектора X.
Логарифмируя (110) и обозначая
м
- ‘ ~
I
1
8у= 1п(суа; ), у = 1п Х , А } — — ,
а.
где а] = — 1п (1 —
Ка -
получаем
5|— —I—— V , если X ) > 0;
Щ,
(112)
А)
щ
8у < V , если X ] — 0 .
Отсюда находим основное соотношение
./€
И /й*
•^1==1У6}> 12 (/•
Суммируя (112), находим
1
V = --------
Ш
Г
(111)
У
6).
А )Ь ,— Ю .
2 -4; ^ 6/,
) 6л
Искомые значения составляющих оптимального пла­
на определяются из ( 111):
К |^
Ш
—
Ш / (“/— °)> 7 6 ^1-
пн-
Итак, задача свелась к отысканию разбиения множе­
ства Д= {бт}, те /, на подмножества Д1= {д,} /1^/1 и
Д2={д*}, яййрг* где рЙ содержит /1 наибольших, а Д2—/2
наименьших значений бт множества Д.
Перенумеруем переменные так, чтобы 61^ 62^ . . .^ б п
и обозначим
Легко показать, что если В ,- 1< Фз, то и
Все вышесказанное позволяет для решения
(62) — (64) построить простой алгоритм.
задачи
;
Алгоритм 18
1. Вычислить
1п (1 — ) А
О(у
А
1 1
ш
1п (с ;-а_,)
бп И
2. Построить вариационный ряд ® .
перенумеровать переменные в соответствии с расположе­
нием 6] в этом ряду.
3. Рассчитывать величины В ] по формуле
/1
1
В
V А
2 АЛ-ЛГ1.
\т«=1
2,...
до тех пор, пока не выполнится условие В ] х 8/,+ь
Если это условие не выполняется вплоть до ]\ — п 1, то
принять = п (в этом случае в оптимальном решении
все компоненты будут отличны от н у л я ).
Щ
4. Определить значения х] по формуле
Щ,(Ь) — В ]), ]■= | * Щ»
Х1
О,
5. Перейти к прежней нумерации переменных и подсчитать значение целевой функции Р ( Х ) .
6. Конец вычислений.
О ГЛ А ВЛ ЕН И Е
Предисловие
Глава /. Линейное программирование
...........
1.1. Общая зад ача......................
1.2. Транспортная задача
...................
1.3. Задача о назначениях , *
..........................
1.4. Распределительная задача ........................ ' ' ‘
|2
Глава 2. Динамическое программирование
2.1. Функциональное уравнение. Р. Беллмана . .
2.2. Разностный м етод ................
60
М
2!,
,
. =
§
*
Г ,гава 3. Выпуклое программирование...................
3.1. Метод возможных направлений .
3.2. Условия Куна-Таккера
‘
* '
"
О
-5
ол
^
НИИАТ
Борис Д а в и дов ич П р у д о в с к и й
М арк Г р и г о р ь е в и ч К е р з н е р
Г а л и н а И в а н о в н а Трофимов а
М А Т ЕМ А Т И Ч Е С К О Е О Б Е С П Е Ч Е Н И Е А С У В Т РА Н С П О РТ Н О М
УПРАВЛЕНИИ
Редактор В. И. Я б л о к о в
Технический редактор Л. Е. Ш м е л е в а
Корректор С. М. Л о б о в а
И Б Л*е 783
Сдано в набор 25.10 1976 г.
Подписано к печати 4.08.77г.
Формат 84X1087*2 Бум . тип. X* 2 Печ. л. 2.75 (уел. 4.62) Уч.-нзд. л . 3,92
Гера ж 4700 экз.
Т—14528
Изд. № 1 к—4—1/14 Лв 8219
За*, тин. 1579
Цена 60 коп.
11зд-во «Т Р А Н С П О Р Т », М осква, Басманный туп.. 6а
М осковская типография .V? 8 союзполнграфпрома
пр Государственном комитете Совета Министров С С С Р
по делам издательств, полиграфии и кнжном торговли.
*$;-■ ■
:
Хохлове кй пер. 7,
Документ
Категория
Без категории
Просмотров
1
Размер файла
4 182 Кб
Теги
obespechenii, 3585, matematicheskih, upravlenie, asu, transportnom, prudovskiy
1/--страниц
Пожаловаться на содержимое документа