Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 23
Текст из файла (страница 23)
Элементы с,з матрицы С не зависят от первоначального выбора и!, Действительно. Предположим, что вместо первоначального потенциала и, мы бы взяли потенциал й! = я! +1. Тогда 6! = о, — ! и все й; = и; + 1, б. = в — ! при базисных з,у', поскольку нз + ез = сзз при базисных 3,7. Таким образом, сумма йз+й = и, +!+ о — ! = к, + о = с;. 3 '3 не зависит от выбора первоначального потенциала и,. 4. Провести исследование матрицы 35: = С вЂ” С. Если 25 > О, то исследуемый план х является решением задачи (Р), а потенциалы и„е являются решением двойственной задачи.
Если среди элементов матрицы 21 есть отрицательные, то выберем наименьший элемент. Пусть, например, зьз,зт = Ппп 2543 < О. 15 5. Построить новый план перевозок, являющийся крайней точкой мнохсества допустимых элементов. Положим т;'„„= 1, х,' = х, х ! для базисных индексов 3, у, где 1— некоторая положительная величина (не изменяя остальные небазисные компоненты хо равные нулю) так, чтобы х'; по-прежнему были неотрицательны, но олна из базисных компонент обратилась бы в ноль. Вектор матрицы А, соответствующий этой компоненте, выводим из числа базисных, а вектор матрицы А, соответствующий переменной хцзт, вводим в число базисных векторов.
Далее вновь начинаем исслелование полученной крайней точки х', т.е. возвращаемся к и.3. В невырожденной задаче в ноль может обратиться только олна из компонент вектора х. В вырожденной задаче в ноль может обратиться несколько компонент. В этом случае из числа базисных векторов исключается любой вектор с нулевым значением, как правило исключаегся вектор с наибольшей стоимостью перевозок.
129 $5. Транспортная задача 5.5. Примеры транспортных задач Пример 1. 2хн + 2х и + 4хы + 8Х!4 + 4хп + 5хы + 7хм + бхз« + +без!+Зхзз+4хзз+9хз« пнп; х!! + Хз! + хз! < 22, х!2+ х22+ х32 < 2, х!з + хзз + хзз < 17, Х!4+ Х24 + Х34 ч 11~ х!! +хо+ хо + х!4 =!4, Х2! + Х22 + Х23 + Х24 = 18, хз! + хм + хзз + хз! —— 16, ХО >О, 4=1,2,3, 7'=1,2,3,4. Решение. Поскольку суммарные запасы груза на всех пунктах отправления меньше суммарных запросов пунктов назначения, т.е. 3 4 2 о! = 48 < 2 , 'Ь; = 52, то надо привести задачу к замкнутой модели.
3=! 3=.! Введем фиктивный пункт отправления А« с требуемой величиной выво- 4 3 за ૠ— — 2 Ь вЂ” 2'а! = 4 и нулевыми стоимостями перевозок из этого 3=! 3=! пункта. Зададим транспортную задачу в виде платежной матрицы; Построим по метолу «Северо-западного угла» первоначальное распреде- ление: Для краткости в матрице плана перевозок не пишем нулевые значения небазисных перевозок. Значение функционала равно 225. Число ненулевых элементов в первоначальном плане перевозок из+и-1 = 4+4-! = 7.
5 3*«, и! 131 4 5. 'Цаиспертиая задача !ЗО Глава 2. Линейное программирование Это позволяет сразу перейти к исследованию на оптимальность найден- ного плана. Построим матрицу С'. Ь34 — — пнп Ь;3 = -6 < О. Добавляя в первоначальный план распределегд ния на место нулевого небазисного элемента х34 величину 1, получим второй план возможных перевозок Величина ! = 7.
Значение функционала = 183. Построим матрицу С: 4Ъ~3 аа33 — ) 343 — Пцн аа33' = — ! < О. ВО МНОжЕСтВО баЗИСНЫХ ЭЛЕМЕНТОВ °,/ включим элемент хо с наименьшей стоимостью перевозок. Добавляя в первоначальный план распределения на место нулевого небазисного элемента х43 величину 1, получим третий план возможных перевозок: ' В матроне С баанснмс аасмснтм бумм рмаеаать ноауашрнмм шрифтом. 0 — 0 В матрице га = С вЂ” С = 8 0 — 0 В матрице 4з = С вЂ” С = 5 2 — 2 0 0 -6 минимальный элемент 7 5 0 — 1 — 1 4'~ 0 0 0 минимальные элементы 1 — 1 0 Величина ! = 1. Значение функционала = 182.
Построим матрицу С: ~0 — 1 0 4~ — 0 0 1 0 В матрице Ь = С вЂ” С = 4 0 0 5 минимальный элемент 2 1 0 0 Ь13 = ПЦП 43Ч = — 1 < О. Добавляя в первоначальный план распределения ьу на место нулевого небазисного элемента хм величину 1, получим четвертый план возможных перевозок Величина 1 = 2. Значение функционала = 180. Построим матрицу С: 0 0 0 4 Поскольку 43 = с — с = 4 1 0 5 > О, то найденный четвер™й — 0 1 1 0 2 2 0 0 план перевозок является оптимальным и суммарная стоимость 180. !ЗЗ б 5. ТРаяспаргиая задача 132 Глава 2.
Линейное программирование Пример 2. хи + 2хн+ Зхы+4хм+ 4хг~ + Зхп+ 2згг+ 2хгг+ 2хгг+ хга пнп; х~~ + хи + хг~ = 2, хи + я,г+ хц+х1а м 3, + + — 3, х1г + хгг + хгг = хп+хп+хгг+хга =4, + + =4 х~з + хгз + хзг = хг1 + хзг+ хгз+ хга = 5 + +х =3 хм + хга + хм = х; >О, г=1,2,3, г=1,2,3,4. Решение. Поскольку суммарные запасы отправителей равны суммар- г а ным запросам потребителей, т.е. ',г„а; = 2 Ь, = 12, то данная задача ~=! г=! является замкнутой моделью транспортной задачи. Зададим задачу виде платежной матрицы: Построим по метолу «Северо-западного угла* первоначальное распреле- ление: Для краткости в матрице плана перевозок не пишем нулевые значения небазисных перевозок.
Значение функционала равно 21. Число ненулевых элементов в первоначальном плане перевозок гп+и — 1 = 3+4 — 1 = б Это позволяет сразу перейти к исследованию на оптимальность найденного плана. Построим матрицу С: (О 0 2 4~ В матрице г3 = С вЂ” С = ~ 2 0 0 — 1~ минимальный элемент — 2 — 1 0 0 ахи = ппп ггаг = -2 < О. Добавляя в первоначальный план распределения ад на место нулевого небазисного элемента хг~ величину 1, получим второй план возможных перевозок Величина ! = 2. Из трех обнулившнхся базисных элементов в базисе оставили два элемента с наименьшими стоимостями перевозок. Значение функционала равно 17.
Построим матрицу С: /О 0 0 2а! В матрице аз = С вЂ” С = ~ 4 2 0 — 1~ минимальный элемент 0 1 0 0 Ьга = т!и гзгг = — 1 < О. Добавляя в первоначальный план распреде'.г ления на место нулевого небазисного элемента хга величину 1, получим третий план возможных перевозок Величина ! = 3. Значение функционала = 14.
Построим матрицу С: УОООЗ! В матрице аг = С вЂ” С = ~4 2 0 0) все элементы неотрицатель- 0 1 0 1 ны Значит найденный третий план перевозок является оптимальным и суммарная стоимость всех перевозок равняется 14. 1З4 Глава 2. Линейное программирование 135 б 5. Транспортная задача Примпо 3.
5хп + 4хп + 1Зхм + 9хм + 2хн + 7хм + бзю + 8хм + +9хп+ 7хы+11хм+7хз«+х»+бха+х«з+х» — гп!и; иия на место нулевого небазисного элемента хн величину Ф, получим Второй план возможных перевозок хи +хм+хм+хм = 19, хи +хм +хм +х» = 9, хи+ хп+хм+хм= 7, х~г+хп+хм+и»=17, хз~ + хп + хзз + хз« = 11, хюг + хм + хзз + х«э = 15, х» + х«2+ хм +х«« = 15~ х!4 +х24+ хм + хи = 11, хб ) О, 1, т' = 1,2, 3,4.
Решение. Представим задачу замкнутого типа в стандартной форме: Величина ! = 7. Значение функционала = 228. Построим матрицу С: Построим по методу «Северо-западного угла» первоначальный план: Ьм = тш Ьб = — 4 < О, Третий план перевозок Для краткости в матрице плана перевозок не пишем нулевые значения небазисных перевозок. Значение функционала равно 270. Число элементов в базисе гп + и — 1 = 4+ 4 — 1 = 7. Один базисный элемент оказался нулевым. Это означает, что задача является вырожденной.
Перейдем к ис- Величина ! = 11. В этом случае обнуляются сразу два базисных эле- мента. Оставим из них в базисе элемент х,и с наименьшей стоимостью перевозок. Значение функционала равно 184. Построим матрицу С: следованию на оптимальность найденного плана. Построим матрицу С: (О 0 4 0~ М атрица «ь = С вЂ” С = 6 5 4 0 > О. Значит третий план 4 10 0 0 гьн — — ппп 2!чг = -6 < О.
Добавляя в первоначальный план распределе- "еревозок является оптимальным и стоимость всех перевозок равна 184. 0 — — 6 В ыатрнце Ь С С 4 -2 0 10 6 ~~ 0 0 2 4 минимальный элемент 4 0 0 0 — 0 В матрице г."ь = С вЂ” С = 2 4 О 4 О~ 6 0 2 0 4 минимальный элемент !О 0 0 1З7 ф 5. Транспортная звлача (а) (Ь) л! л (а,и) + (Ь,о): = ч! а!и!+~ Ь о.
2=! 2=! + ( у л! л л с» 1 л (с,х) = ~~! ~~! и2хп+~ 2=! = ~У ~и!а! с2, С!2 1 0 ... 0 0 0 О 1 ... 0 1 0 ... О 0 1 ... О 0 1 О с!л сп С22 и! и2 1 ". 0 0 0 ... 1 С2» и о, 32 ~ ! или О, 1,2 Е В, !О = ! =(ю 2 =Яо О, иначе. О О . 1 1 0 ... 0 О О . 1 0 ! ... 0 с С!»2 о о ... ! о о л й =О, 1= 1,...,и!, (ь) 2=! ~ ~ ~!21 = О, 2 = 1,...,и; 136 Глава 2. Линейное программирование 5.6. Задача двойственная к транспортной задаче Рассмотрим транспортную задачу: л л (с,х): лл ~'~ь с, хг- пнп; 2=! 2=! х! >О, л»1,..г,ш, Ут!,...,и, л Х: х! =ан 2=1,...,гп, 2'=! Е х! =Ь,2=1,...,п, г' ы л замкнутого типа ~ 2;а! = 2 Ь; = Ьг . Двойственной к ней будет 2=! '2=! (см п.2.5) задача в которой двойственными переменными являются потенциалы и = (и!,...,и,„), о = (о!,...,ол). В матричном виде ограничения задачи (Р") имеют вид: 1 0 ...
0 ! 0 ... 0 ! 0 ... 0 0 ! ... 0 Матрица ограничений является транспонированной по отношению к ма- трице ограничений исходной транспортной задачи (Р). 5.7. Обоснование метода потенциалов решения транспортной задачи Теорема. Крайняя точка х является решением в невырозкденной транснортной задаче (Р) тогда и только тогда, когда вектор дь > О. Доказательство. Достаточность. Пусть Ь > О.
Это означает, что для точки * найдены потенциалы ин ог такие, что йч2: = с,г — с„= су— (и; + о ) > О, ! = 1,..., гп, 2 = 1,..., и, причем и, + о; = с; для базисных 2, ! (множество базисных индексов обозначим В). Следовательно, и;+о! ( с,г, ! = 1,...,пь, 2 = !,...,п. Таким образом, условие дь > О равносильно тому, что вектор (и, о) является допустимым в двойственной задаче (Р ).
с другой стороны, поскольку х!. = 0 при (2, 2) к В, то С; Х; = ~~! С! Хг = ~~~ (и*'+О!)ХО К'. Л~'.ыг(и!+От) 22' !=! 2=! !дев !дев 2=! 2=! Разбивая последнюю сумму на две и учитывая условия (а) и (Ь), продолжим последнее равенство 'У О;Холл,'~ и,',~ Х22+~О,'~'Х!, 2=! Ф=! 2=! с=! л +,у,ь, =( л)+(ьл). Отсюда по критерию решения п.3.! х — решение в прямой задаче (Р), а (и, о) — решение в двойственной задаче (Р""). Необкоднмогтгл Пусть * — оптимальный план. Докажем, что тогда 22 > О. Проведем доказательство от противного. Допустим, что это условие не выполняется, т.е. существует 222,2, < О. Поскольку гь22 = 0 лла (2,2) е В, то (1в,зо) к В.
Возьмем достаточно малое ! > 0 так, чтобы х + ! > О, где вектор Е = (!О) выбирается по методу потенциалов, Условия (а)-(Ь) допустимости вектора х + ! в задаче (Р) равносильны условиям: 141 9 5. Траисяорпзая задача 140 Глава 2. Линейное программирование 5.9. Задачи 1 2х +Зхц+4х з+хы+Зхм+4хы+2хгз+5Х24+хн+ухзг+ хзз+ ухзз + 5Х4! + 2х«2 + 8хзз + 2хм Х11+ Ха + ХЦ + ХМ Х21+ Х22+ Х23+ Х24 хз1+хзг+хзз+хм = 5 Х4! + ХХ2 + Х43 + ХЫ К а!!+ хг! ха + хгг я!э+ Хгз хм + хгз , >О, 1,«=1,2,3,4.
5.2. Хц + 3, и + Гбхц + бх, 4 ухг! + 2хгг + 5хгз + 8хм + 5хп + 2хзг + 2х + 9хз«+ 2хм + х«2+ Зххо+4хм пнп; -1-хз1+ хм = 14, + ХП + Х42 + хзз+ х«з = «х, +хм= 15, Х11+ ХМ хц+ хгг х!з+ хгэ Х14 + Х24 Х11+ Х,г+ ХЦ Х21 + Х22 + Х23 хз1+ хзг+ хзэ Х41 + Х42 + Х43 ;,« =1,2,3,4. х! >О, 5.3. 4х + За г «-Зх з+бхм+4хп+5хм+ 5хз1+4хзг+6хзз+ ~41+ 9ххг + !Ох«3 — пз1п; +хц+хц( 8, + хм + хгз ~ 11 +хзг+ хзэ 4 + ххг + х43 ~ ~4, х„+ х21+хзз+ха = 5 хц + хгг + хп + Х42 = 15 хц + хгэ + хээ+ Х43 = 1О 3 = 1,2,3. х» ) О, 3,= 1,2,3,4, 5 4 2 + бац «- 2хц + Х1« -1- 2хц + 9хм + 4хм + Зхц + "~гч + хгз 5хз1+ 2хзг + 8хзз + 2хзз + 5хзз -! ппп; хм+ хг, + хз! — — 15, хц + хгг + хзг— х1з + хгз + хзз = 14, хм+ хгз+хм= 9 Х15 + Х25 + Х35 = 6, х!2+ х,з+ х!4+ х!5 — — 13, хи+ Х23+ Х24+ х25 — 11~ хзг+ хзз+ хм + хзз = 22> 3= 1,2,3, г =1,2,3,4,5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
