Корн Г.А., Корн Т.М. - Справочник по математике для ученых и инженеров (947387), страница 76
Текст из файла (страница 76)
х,+ -хе=5)0, 2 ' 2 5 23 «в — — хе + — хв = 20) О, 2 2 24г — зхв 7кв + 30. Коэффициент при х, в последнем выражении отрицателен, целевая функция убывает при воэрвстэнин кв. При этом воэрэствнин первой обращается в нуль переменная хэ текам образом, хв заменяет бээнсиую перемевную хь К=4, 1=2 и 20 40 15 — — х, =- —, хв =-хв =О. 25 23 ' 23 ' 2 Новая кэионическэя форме задачи относительно кь хв есть 5 1 15 х — — х + — хв= — )О, 23 ' 23 23 2 5 40 х + — хв хв= )О 23 23 В 12 23г = тх, + 17л, + 205.
В целевой функции коэффициенты прн свобццных перемепиык кь х, положительны: эиэчнт, получено единственное оптимальное ревпевие 205 205 !2 23 275' (й) Использование искусственных переменных длв начала симплекс-процедуры, Симплекс-метод, как описвно, предполагает, что подходящий выбор начальных базисных переменных хы х,, ..., хю образует некоторое базисное дОПуСтИМОЕ рсщсиис С ()1, ()Э, ..., рю>0. Указанный выбор не очевиден. Нижеследующая процедура может быть применена для начала решения; она же позволяет установить существование допустимых решений. Рассмотрим задачу линейного программирования в стандартной форме (2) и будем считать, чта уравнения (2Ь) записаны так, чта все Ь, = О. Введеэ! ш нскУсственных пеРеменных х„,, х„ю ..., хлэю и Решим вспомогательпУ)о задачу о минимизации линейной формы ю = хо.!+ хлев+".
+ хе,ю (11.4-10а) при )слоаиях анх(+а!эхе-(-...+а!лхл+х„.т=Ь! — -О, ав,хт+ аэгх, +... -)- агах„+ хл, 2 = — Ьв О, а !х! — Раюэхэ+ ° ..+Оп!эхо+хл,ю =-Ьлв ха==О (2=1, 2, ..., л+т). 342 ГЛ. П, МАКСИМУМЫ И МИНИМУМЫ 11.4-2. 11,4.4, 1! 4 ЛПНЕПНОЕ ПРОГРАММИРОВ ИГРЫ И СМЕМПЫЕ ВОПРОСЫ 343 Принимая х„х„„., х„за свободные перемеивыс, а х„т, х„,,, ..., х„т— за базисные, получаем базисное допустимое решение вспомогателы!ой задачи; х;=О для 1~1(п и х„=Ь1 для 1 =1~т. Применяя симплекс метод, находим оптимальное решение вспомогательной задачи.
Если это решение таково, что юш;„=О, т. е. все хп.ы, ..., хпьш равны нулю, то оно определяет допустимое решеаие исходной задачи. Если же для оптимального решения юш!а)0, то исходная задача не имеет допустимых решений. 11.4-3. Нелинейное программирование. Теорема Куна — Такера, Если линейная целевая функция и1или одно или более линейных ограничений в задаче линейного программирования (1) заменены нелинейными относительно переменных Лт, то имеет место задача нелинейного программирования. Такая задача возникает, например, если границы множества решений и1или линии уровня г ва рис. 11.4-1, а заменены кривыми. Задачи нелинейного программирования представляют практический интерес, но, за малым исключением, поддаются лишь численным методам решения (п, 20.2-6). 11гобходииог (но н достаточное) условие макси»сума функции г=1(х,, х„..., хп) (1 = О, 1, ..., т), (1 = 1, 2, ..., т), 31==0 дгр,=О д1 де! 1=1 (11,4-12а) (й = 1, 2, „ ., и).
(теорема Ф. Джона; функции 1 и гр! предполага1отся диффереицпруемым1.) В усювиях (12а) 1.4 полозхитгл но и может вчитаться равным единице всякой раз, когда с!ги(гству!от н дгйспгвитгльпых чисгл (ут, уз, „„у„) таких, что длл рассл!атривагмих эпачгиий х„х„..., х„ Х- — ' двг ~ О, если р! — линейная фувꆆция в кекоторой окрестности 4=1 (хт хз ° хл) т (О в остальных случаях (!!.4-12Ь) ( формулировка Эй!бели теоремы Куна — Такера).
11.4-4. Введение в ионечные игры двух партнеров а нулевой суммой. (а) Игры с чистыми стратегнямн. Конечная игра двух партнеров с нулевой суммой есть модель конфликтной ситуации, характеризуемой конечной матрицей выигрышей ат, а,з ... атт (11.4-13) а»1 а», , ал,п где аш — (положительные или отрицательные) выигрыши игрока А у игрока В, если А выбирает 1 ю из п чистых стратегий 5„5,, ..., 5„, удобных для него, а В выбирает й-ю из т чистых стратегий 5,', 52, „., 5', возможных для него, Ни один из игроков не знает выбора другого. при условиях-нгравгпгтвах гр;(х,, хз...„х„) =0 (1=1, 2, .„, т) эаклю!ашлся в сущсс!пвовании т+1 иготрицатгльиых ь!ножитглгй,Пагранлга Аз, Х„..., Аш (см.
п. 11,3-4), не равных одновргмснно нул!о и таких, что За»ют«м, что сумма вьп!грышей обоих игроков равна нулю прп каькдоч хо;1е (отсюда и название — игра с вулево!1 суммой). игра симметрична, когда т=п и аг„=. — а;ь длЯ всех 1, 1!. Для выигрыша макснмизирующий игрок А выбирает 1-ю строку матрицы выигрышей с теч, чтобы максимизировать и!наш, тогда как минимизирующий игрок В до«жсн минньшзсрозать игах а;!гс Длл каждаи задагшой 41атрицы (13) 4 шах ш!и а!ь — ш!и шах аы. ! ь ь (1 1.4-14) Если обе величины в (14) равны для (не обязательно единственной) пары 1=1, А=-((, то говорят, ггто игра имеет седловую точку или решение 1, 1( и (единственную) цену а!к.
Оптпмальвые стратегии для такой игры не имеют смысла, если игрок А знает предстоящий ход В, и обратно. (Ь) Игры со смешанными стратегними. Смешанные стратегии определяются с помощью вгролтност "й (п. 18.2-2) рт, рг... р„, приписываемых игроком А его и возмозкным стратегиям 5м 5, ..., 5, и вероятностей рп рз, ... р'„, приписываемых игроком В его стратегиям 5;, 52, .„, 5' т ( ~Р„Р,= Х р',.=1.
11= — ! !'=1 »»г шах ~ ш!п ~~ ~', аг р,.рь = г 3' "' »(Р!, Р2, ..., Р~» 1=1 !г=1 » т Р1, Р2... Рт ьа1' 3' "" ! л ~ =! !г ==! (11.4-15) (загорела минимакса длл ко!ипной игры двух партнеров с иулгвой сум.иой ю!игрища) Общая велич«па (15) называется ценой о игры. Каждал конечная игра двух партнеров с нулевой суммой имеет по мгньиый л!врв одно решение, опргдглягмог оптимальными стратегиями рт, рз, .„, Р»' 11 Рз )т Возможны и несколько решений, но цена игры необходимо единственна. Безобидная игра двух партнеров с нулевой суммой имеет цену, равную нулю, Г! р и и е р. Известная згрз мьрб-рьшкз» имеет патрику выигрышен В игре со смешанными стратегиями А стремится максимизировать минимум матгмати юского ожидания (п.
18.3-3) » т ш!п ~' ~ ашргрв Р1, Рз...„рт 1=-1 !4=-1 посредсзьом выбора рт, р„..., р„, тогда как В стреыится минимизировать и т шах ~~Р~ ~ а р р„' Ртрз" Р пугем выбора р', р', .„, р,'„. Длл л1абай заданной л!атрицы выигришгй (13) !1 3 НЛРИЛЦ!4ОННОЕ ИСЦИСЛЕНИЕ 345 11.1-2.
11 2-1. ГЛ Н. МЛКСИМУМЫ И МИНИМУМЫ и «отерла стратегия 1 яхя каждого ягрпка есть решка-герб, г стратсгая 2 — герб-рсапка. Игра сяммстрячяая, бехабядяая я ле ямсст ссдллвых тласк. Решение: р =-р'=-112. р, =р'=!12. а ' г г (с) Связь с линейным программированием. Игры сосмешанными стратегиями привели к развитию некоторых приближенных методов, однако наиболее важные приложения сзязаны с линейнын программированием. Решение данной матричной йгры не изменяется от прибавления ко всем ат одной и той же положительной константы а, так что не будет ограничением рассматривать игры с положительной ценой о) О, В этом случае оптимальныг стратегии рм р, ..., рл и р1, рз, ..., р,'„и цена о конечной игры двух лара!играя с нулевой с!Гмлюй с зидаллой митрицгй выигрышей (13) есть рг=оХ; (1=1, 2, ..., и), р,',=оуь (й=1, 2...„т), (11.4-15] ! а — —— хапщ шпаах где г„„!л, ш „, Хр У, определяются как решения деойгтгглкых задич лилейного лрогриммироеаиия (п.
11.4-1): г = Ха + Хг -1-... + Х„= пни с ограничениями аалХа+аглХ2+" +и ЛХ = 1 (й=1, 2 ", т), Хг)0 (а= — 1, 2, ..., л), ш= — 1',+ Уя+...+ 1',=шах с огршшчениямн анУ,+а 2У2+...+аы Уж <1 (1=1, 2, ..., л), Уь)0 (й=1, 2, „т). !1.5. ВАРИАПИОННОЕ ИСЧИСЛЕНИЕ. МАКСИМУМЫ И МИНИМУМЫ ОПРЕДЕЛЕННЫХ ИНТЕГРАЛОВ 11.5-1. Вариации. (а) Вариация би функции у(х) переменного х есть функция от х, определяемая при каждом значении х как разность бу= У (х) — у(х) новой фуакцни У (х) и функции у(х).
Вариацию бу, вызывающую изменение функционального отлошгкик люкса)у у и х, не следует смешивать с приращением Лу значения даняой функпни у(х), вызыиаемьш приращением Лх независимого переменного х (и. 11.2-!). (5] Если дана функция ГПА (х), уг (Х), ..., Ул (Х); Х], то ее пРнРашенне, соответствующее вариациям Ьу,, Ьу, ..., Ьул функций у, (х), уг (х), ..., Ул(х), есть ЛГ=Г(уа+бу,, 11,+Ьу,,, ул+буж х) — Г(уа, д,, ...,Угй х). (11.5-!) Если функции у(х) и бу дифференцнруены, то вариация Ьу' произзодиой у'(х), вызываемая вариапией бу, есть бу' чм б — г = -- (Ьу) = — У' (х) — у' (х]. «г (11.5-2) Если дана функция Г [уа (х), уз(х), ..., Ул (х)! Уа (х), уз (х), ..., у„'(х); х], то ее приращение, соответствующее вариациям буа, 611„..., Ьул, есть (ух+бра уг+Ьуг.
" ул+Ьдл! да+бра уа+буз "" ул+Ьул х) — Г(У1, уз, ..., у„; уг, уз, ..., у'„; х). (11.5-3) (с) Если фуакпия Г имеет в некоторой области непрерывные частные производные второго порядка, то ее приращение, определяемое равенством (3), можао представить в виде л — бу;+ —,Ьу + дР др '(да, д л л .+ ' ~ ~~ '" бу!Ьуа, ] 2 '" бугбу'-! —,",бу,'Ьу,', +о(Р'), (11.5-4) ,, ! [дг1да, дг!дра ' а дг,' дг„' где Р =1Г6У[+ ЬУ!'+ ЬУаг+ Ьдз'+...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
