Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 24
Текст из файла (страница 24)
Построим матрицу С: УОООЗ! В матрице аг = С вЂ” С = ~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=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 > О. Проведем доказательство от противного. Допустим, что это условие не выполняется, т.е. существует гз2, ! < О. Поскольку гь! = 0 лла (2,2) е В, то (1в,зо) к В. Возьмем достаточно малое ! > 0 так, чтобы х + ! > О, где вектор Е = (!О) выбирается по методу потенциалов, Условия (а)-(Ь) допустимости вектора х + ! в задаче (Р) равносильны условиям: 141 9 5.
Траисяорпзая задача 140 Глава 2. Линейное программирование 5.9. Задачи 1 2х +3Хц+4Х З+Хм+ЗХМ+4ХЫ+2хзэ+5Х24+Хп+ухэз+ Хээ+ ухзз + 5Х4! + гх«2 + 8хзз + 2хм Х11+ ХЦ + ХЦ + ХМ Х21+ Х22+ Х23+ Х24 Хз! + хзз + хзз + хм = 5 Х4! + ХХ2 + Х43 + ХЫ К а!!+ х21 ХЦ + Х22 я!э+ Хзз ХМ + Хзх , >о, 1«=1г34. +3 + ГОХ +бам+2 н+гх»+5 +'х" + "и+ гх + 9хз«+ 2хм + х«2 + Зххо + 4хм пнп; -1-х31+ хм = 14, + ХП + Х42 + хзз+ х«з = «х, +хм= 15, Х11+ ХМ Хц+ Хзз Х!З+ Хзз Х14 + Х24 Х11+ Х,з+ ХЦ Х21 + Х22 + Х23 хз1+ хзз+ хзэ Х41 + Х42 + Х43 ;,« =1,г,3,4.
х! >О, 5.3. 4х + За 2 «-Зх з+бхм+4хп+5хм+ 5хз1+4хзз+6хзз+ ~41+ 9ххз + !Ох«3 — пз1п; +хц+хц( 8, + хм + хзз ~ 11 + Хэз+ ХЗЭ 4 + ххз + х43 ~ ~4, хи+ х21+хз!+Ха = 5 х ц + хзз + хп + Х42 = 15 хц+хзз+ хээ+ Х43 =1О у = 1,2,3. х» ) О, 3,= 1,2,3,4, 5 4 2 + бац «- 2хц + Х1« -1- 2хц + 9хм + 4хм + Зхц + "~зч + хзз 5хз1+ 2хзз + 8хзз + гхзз + 5хзз -! ппп; хм+ хз, + хз! — — 15, Хц + Х22 + Хэз— х1з + хзз + хзз = 14, хм+ хзз+хм= 9 Х15 + Х25 + Х35 = 6, х!2+ х,з+ х!4+ х!5 — — 13, хи+ Х23+ Х24+ х25 — 11~ хзз+ хзз+ хм + хзз = 22> 3= 1,2,3, 3 =1,2,3,4,5. на место нулевого небазисного элемента хц величину 1, получим второй план Величина 1 = !.
Из двух обнулившихся базисных элементов в базисе оставили элемент с наименьшей стоимостью. Значение функционала равно — 22. Построим матрицу С: /О 4 Озз В матрице Ь = С вЂ” С = ~ — 2 О 3) минимальный элемент О О 8 Ьз! — — т1п Ь13 = — 2 < О. Добавляя во второй план распределения з,я на место нулевого небазисного элемента хм величину $, получим третий план распределения должностей Величина 1 = 1. Из двух обнулившихся базисных элементов в базисе оставили элемент с наименьшей стоимостью. Значение функционала равно — 24.
Построим матрицу С': УО 4 О1 В матрице 21 = С вЂ” С = ~0 2 5~ асе элементы неатрицательны. О О 8 Значит найденное распределение является оптимальным и значение исходной задачи равняетса 24. я!1 хм Х31 Х41 Х11+ хм+ Х31 + +хм — — 6, + хм = 18, + хм — — 14, = 1О, +хз! =11 +хэз= 2 +хм —— 6, +хм= 7, 142 Глава 2.
Линейное првграммирваавие Ответы к задачам главы 2 !.1. (1, 3, 0) б Агй; Яаак = 4. 1.2. (О, 3, О, 2), (2, 1, О, 0) б Агб Р; Я „= 5. 1.3. (О, 4, О, 0) б Азй; Я,„= 4. 1.4. (2, О, 3, 0) б Агб; Яачк ка 5. 1,5. (5> 3 0>0) б АЗ8" Яа>ак — 8 1.6. (1, 1, 1, О) б Ащ; Я „= 3. 1.7. (5,0,3,4,0) б Азй; Я = 15. 1.8. (1,2,3,0,0,0) б Агй; Я = 2. 1.9. (5,0,4,1,0,1,0) б Агй; Я„„= 10. 4.1.
(5, 2, 0) б Ехгг, (5, 2, 0) б Агб; Я = 13. 4.2. (! 0 2) =+, ((1,— 10,1) г1+ !0112 9 ,(...(,, !)) = 3+ — 1 - +ос прн 1 — +со. 14 ( '6) 1! 1т 4.3, О, —,О, -) б Ехгг, (4,0,2,0) б Агб; Я,„= 10. (55~'3'''3 4.5. (О, 1, 1, 2) б Езцг, (1, 2, О, 3) б Агй; Я>аак ак 6.
4.6. 2З = й «Ь Яа>ак — — — СО. 4Я. ОООО, -) (-- ) 2к ,-) б Ехгг; Ясак =+со> 4.8. (0,0, !0,0,0),(!0,0,0,0,10) б Агб; Я = — 10. 4.9. (0,0,0,1,0,1) б Ех!г, (0,0,0,1,0,1) бАгй; Я 51. хп =4, хм=3, х, -2 я, — 46 ' з~ хы =6, хп =5, х«э=2, хн =4; 52. .2. хи=6, хзз=!1, хм=7, х —, хи=6, хзз=8, х«~=2 вы=8.
5.3. х — я "' хзз = !5 хзз = 2, хн = 5; я . = !!4 5.4. хн = !О, х>з = 3, х = 11, ззаа хз| =5, хзз=7, хм=9, хм=6' >п>а Глава 3 Вариационное исчисление Началу появления вариационного исчисления дала толчок работа И, Бернулли !696 года «Новая задача, к решению которой приглашаются математикиа, в которой поставлена задача о брахистохроне. В вертикальной плоскости даны две точки А и В. Определить путь АМВ, спускаясь по которому под действием собственной твжести тело М, начав двигаться иэ точки А, дойдет до точки В за кратчайшее время. Вводя в плоскости систему координат так, чтобы ось 1 была горизонтальна, а ось х вертикальна, и пользуясь законом Галилея о скорости тела, падаюшего вниз под действием силы тяжести, нетрудно выписать формализованную постановку задачи: >-:-ыв «а: *н=* (>а= «О Здесь и далее точка над функцией (хз(!)) означает производную этой функции по !.
Эта задача была решена самим И. Бернулли, а также Я. Бернулли, Лейбницем, Лопиталем и Ньютоном. Решение Лейбница было основано на аппроксимации кривых ломаными. Развитая затем в работах Эйлера, эта идея заложила основы прямых методов в вариационном исчислении. Выписанная выше задача об экстремуме интегрального функционала при заданных условиях на концах, является простейшей задачей вариационного исчисления, к рассмотрению которых мы сейчас н перейдем.
В третьей главе приволятся также и другие элементарные эалачи вариационного исчисления: задача Больца, изопериметрическая задача. Все они являются частными случаями более обшей задачи Лагранжа. Как частные случаи задачи Лазранжа рассматриваются задача с подвижными концами и задача со старшими производными. Глава 3. Вариационное исчисление 4 1.
Простейшая задача классического Варианнонного исчисления 1.1. Постановка задачи и ется след юшая растейшей задачей классического вари р ацианнаго исчисления называся следуюшая экстремальная задача в пространсг С ([г, ь Х(х(.)) = / Х(х,х($),х(1)) дб — ехгг; 144 х(хй) = хгн х(1~) = хн (р) Здесь Х = Х(Г,х,х) — ф к ия грантом. Отрезок 8ь, Г п п 3 =,, ') — функция трех переменных, называемая инт1о < 1ы Эк м м в [ ь, ~] предполагается фиксированным и коне нтестре у в задаче рассматривается среди непрерывно дн конечным, ференцируемых функций х б С'([1, 8 ] К), у на концах, илн нраевым условиям: х(8ь) = хб, х(8>) = хн такие Введем норму в пространстве С>([гй, 1>]): ЦуПсц>ьл,1>: = п>ах(ПуПсйял,1> ПуПс11ььь1>) где ЦУЦсбг„м>.
— — гпах(!У(х)! ! 1 б [гб Й~]). Для краткости введем следующие обозначения ПуПо: = ПуПс11ь,г,>> ПуП~ = ЦуПс'<1ьньй которыми будем пользоваться в дальнейшем. Оп ределение. Говорим, что допустимая фу й ункция доставляет слабый локальный минимум в задаче (Р), , и пишем х ь ш!осш>п" Р, если сушествует б ) О такое, что Х(х( )) > Х(х(.)) для любой допустимой функции х (х б Р(Р)), для которой Цх(.) — 2( )Ц~ < б. числении Наряду со слабым экстремумом в классическом ва также изучается сильный экстремум. П и э риационном искласс ф кций, с ри этом расширяется мум ишетс фун, среди которых рассматривается задача.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
