Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 15
Текст из файла (страница 15)
Так, например, неаналитический критерий ~ Х вЂ” У~ (пример модели П) можно заменить на критерий (Х вЂ” Г')О, позволяющий дифференцировать. По существу теорема ЧП утверждает коммутативность операции взятия минимума и любой монотонной функции. Это свойство не сохраняется, если вместо операции минимизации взять элементарное действие 1 (суммирование); поэтому осреднение по (66) монотонно преобразованного критерия отнюдь не равноценно тому же монотонному преобразованию осредненного критерия (66). Так, 1 1 ~О ~ (Х(1) — У(1))Ч1ф ~Х(1) — У (1) ~ 11~. О О Также и минимум неперестановочен с суммированием; именно поэтому преобразование критерия по (66) меняет, вообще говоря, результаты сравнения эффективности 1(58) не эквивалентно (67)).
Примером такой неэквивалентности является следующая задача. Пусть противник может проникать на нашу территорию в пунктах А и Б, причем все его силы будут проходить или только в А или только в Б; пусть известно, что вероятность прохода через А равна 0,75, а через Б — 0,25. Пусть, далее, в распоряжении оперирующей стороны имеется 2п единиц противодействия проходу, каждая из которых может вывести из строя ИГ единиц сил противника. Цель оперирующей стороны — вывести из строя больше единиц противника. Используются две стратегии: а] деление сил оперирующей стороны на две группы по и единиц, располагаемых в А и Б; б) все силы в 2п единиц сосредоточиваются в пункте А.
Если производить оценку и сравнение эффективности стратегий по (58) без осреднения по случайностям, то гарантированная эффективность первой стратегии будет, очевидно, тэ.л; вторая стратегия гарантирует только О, поскольку наихудшим для нее случаем будет проход противника через Б, где сил оперирующей стороны нет. в 10) пРимеРы Оценки эФФектиВнОсти стРАтеГий 87 Если же произвести осреднение критерия по случайностям, т. е.
учесть вероятность прохода противника в пунктах А и Б, то эффективность первой стратегии окажется той же, т. е. равной т и, в то время как вторая дает величину т 2п.0,75 =1,5тп. Итак, при отсутствии осреднения по случайностям более выгодна первая стратегия, а после осреднения выгоднее вторая. В связи со сказанным целесообразно иногда при сравнении стратегий по осредненному критерию (66) говорить о том, что Х,(У) лучше, чем Х,(Г') в среднем, чтобы отличить это сравнение от сравнения по (58). Также можно говорить и об абсолютном превосходстве в среднем.
Однако если вопрос о смене первоначального критерия на осредненный решен, то сравнение стратегий по (67) становится по существу единственно нас интересующим и термин «в среднем» можно опустить. В заключение опять обратим внимание на то, что и (58), и (66) есть не что иное, как действия свертывания критерия эффективности по неопределенным и случайным факторам в соответствии с элементарными действиями типа Ч и 1 из 8 3. Это еще раз подчеркивает, что все исследование операций проводится на основе последовательного использования элементарных действий над критериями, имеющих своей задачей исключение, в том или ином смысле, влияния неконтролируемых факторов.
$ 10. Примеры оценки эффективности стратегий Для иллюстрации приведем несколько оценок эффективности стратегий в моделях в 2, сохранив нумерацию моделей. Модель 1. Если стратегия уже задана в виде (к~) и известно, что она возможна по сырьевым ограниченйям, л то оценка ее эффективности просто равна ВГ' = ~р~Г( к, 1=! поскольку здесь нет ни случайных, ни неопределенных факторов. 88 оценил эееективиости стглтзгий 1гл. и Удобнее, однако, пользоваться таким пониманием стратегии, чтобы сразу определялся максимально возможный для нее объем производства и снимался бы тем самым вопрос о ее возможности. С этой целью в качестве стратегии возьмем вместо вектора (х; » вектор с координатами р; = — „'; тогда и Ц» р!>О, Др! Максимальный объем производства со стратегией (р» л будет, очевидно, определяться величиной й х»~ = ~ х1, представляющей собой максимальную норму вектора (х!» с данным процентным содержанием продукции ( р!».
Из условия (2) получим »»х»» = пп'п 4 ~ с! л! и оценка эффективности стратегии (р!» сведется к определению величины / л л %' (Р!) = ~ Х 1(! Р!» ° ппп Г1 1(1<и лмР! Любопытно появление в оценке минимума, несмотря на отсутствие неопределенных факторов в критерии; тем самым ограничения (2) оказываются в некотором смысле эквивалентом наличия неопределенных факторов.
Задача линейного программирования в новой записи выглядит как максимизация функции Ж'(р!) при условиях р! ~~ О, Д р!.— — 1,т. е. является обычной задачей поиска экл-1 стремума функции переменных р„..., рл, р„=1 — ~ р!!», 1=1 л-1 заданной в простой области Д р!( 1, р!) О; сложность состоит только в недифференцируемости Ф'(р!).
В 101 пРимеРы оцинки зоонктивиости стРАтеГий 89 Модель П, Пусть дан полипом р(1) при критерии (5). Согласно (58) эффективность полинома р(1) будет равна*) пип [ — |1(1) р(1) Ц = о«с«! пип [ — |пах [~(1) — р(1); р(1) — ~(1)]»= о«с«! пип ( ш|п[р(1) — 1(1); [Я вЂ” р(1)Ц =— оепс«! =-щ|п( сп!и [р(1) — 1(!)]; пип [1(1) — р(1)Ц = о«с«! о«с«! =пип [ — щах [~(1) — р(1)]; пип [»'(1) — р(1)Ц. (78) о«с«! о«с«! Таким образом, для оценки эффективности нужно отыскать максимум и минимум разности ~(1) — р(!). Такая трактовка позволяет избегать рассмотрения не всюду дифференцируемой»1(1) — р(1)».
Если 1(1) дифференцируема, то, обозначив через 1! (с=1, ..., 1 — 1) все решения уравнения 1'(1) — р'(!)=0 и добавив !о=0, 1,=1, получим еще одно выражение для эффективности р(!): пи|и [ — »)(1) — р(1)»»= о«с«! =пип [ пип [р(1,) — ~(1;)]; пип [~(1!) — р(1;)Ц= о«с«! о«с«! = ш1п [пи|п[р(1,) — ~(1!); 1(1!) — р(1;)Ц= о«!«! = пип [ — |)" (1!) — р(1!)Ц. о«!«! Для целей сравнения эффективности различных полиномов, как ранее уже отмечалось, можно пользоваться и критерием [1(1) — р(1)]', тогда мерой для сравнения стратегий будет величина пип [1(!) — р(!)]з.
Однако при этом о«с«! увеличится число точек 1и определяемых как корни производной критерия. Модель 111. Пусть х„ ..., хсс †стратег, которая выбирается заранее без использования информации о 1(х!) (неопределенных факторах), появляющейся у оперирующей стороны в процессе поиска экстремума. *) Здесь мы приходим к знаменитой задаче Чебышева, являющейся одним из первых примеров задач с неопределенными факторамн. оцзнкх ээьективности стглтагяй !гл.
и Благодаря условию Липшица, очевидно, имеем ! (х) ) ! (х ) — Й ~ х — х; ~ для любого 1, т. е. 7'(х) ~ >пзах !1(х;) — Й ! х — х !!. 1<1<У (79) Оценку эффективности стратегии (х„..., хщ) проведем для двух крайних случаев критерия (7), т. е. для Л=О и Л= 1. В первом случае критерий имеет вид )г"= — !х;,— х,!, где !(хп)= ппп 7(х;), а 7(х,)= гп(п 1(х). 3 ма<м о<к<~ Согласно (58) оценка эффективности В' = 1п! ( †!хи †,~) = — знр ~хм †,~.
(80) к,; х и Р Какова бы ни была совокупность точек (х„..., хх! с х,~О, хм 4= 1, можно всегда выбрать почти постоян- ные функции, чтобы точки х, и х, (или хх) лежали на разных концах отрезка !О, 1), причем х, или х~ и будут для этик функций величинами х~,. Действительно, если, например, взять функцию 7'(х) = зх+ 1 при х < хя и ~ (х) = — Й, (х — хх) +зхл+ 1 при х ) хм и ехн < Й, (! — хл), то 7(х,) = ппп 1(х;), а т!п 1(х) =1(!). ~<~< ч о<хс ~ Отсюда следует, что при 0 <х, <хм <1 гарантиро- ванная оценка эффективности стратегии (80) даст результат — шах [! — х,; хл) < — 0,5, каковы бы ни были х, и хх и число точек М. Таким образом, можно гарантировать ошибку в опре- делении х„только не меньшую 0,5, если 0 < х, < хх < 1.
Если же, скажем, хм=! и х,=О, то, положив функцию 1(х) = зх+ 1 цри х < 1 — 8; ! (х) = — Й (х — 1 + 8) + е(! — 8) + 1 при 1 — 8 < х < 1 —; е 1(х) — Й (х — 1+- +з(1 — О)+1 — Й вЂ”, 1 — — <х<1, от е. 0 е убедимся, что х, = 1 — —, а х;, = О, что дает верхнюю з 101 пгимегы оценки эффективности стглтзгнй 91 грань ошибки в определении х„ благодаря произвольности 9, равную 1, т. е. всей длйне сегмента, на котором отыскивается экстремум. Из сказанного ясно, что все стратегии весьма малоэффективны для критерия с Х = 0; увеличение количества точек не увеличивает точности поиска места экстремума.
Необходимо, следовательно, еще сузить неопределенность, т. е. класс рассматриваемйх функций, предположив достаточную крутизну их в районе экстремума или, что естественнее, ихч,'унимодальность '(т. е. наличие только одного локального минимума). В последнем случае легко проверить, что ошибка ~хн — х, ~ не превзойдет пшх (х,;х,— х,; ...; хл — хл... 1 — хд„) даже, если не накладывать ограничения (79). Иначе обстоит дело с критерием при Х = 1, т. е. когда Ф' = — ~ Цхь) — 1(х,) ~.
Пусть х лежит где-то между х, и хл, скажем, между х; и х,+,. ')огда в силу (79) имеем ~(х,)) шах (~(х;) — й(х,— х;); ~(х;„) — й(х;,— х,)]. (81) Если Г(х;) и 1(х;,) фиксированы, то наименьшее значение правая часть неравенства имеет, если х расположено в точке пересечения прямых а=ах,) — я(х — х,) и г=~(х;+,) — й(х;,— х), т. е. если х,= ~ '1 ь~~'+'~+ + хж+хг 2 Прн этом правая часть (81) равна 1(хс)+/ (х;.„) а, 2 ~х'+~ хн. Отсюда следует, что всегда ~~ ппп1(х~) — 2 (х;„— х;) =1(хп) — (х;,— х,).
ь а Поскольку, с другой стороны, всегда ппп 1 (х) = 1(х,) ( 1(х;,), то ~ 1(х,) — 1(х;,) ~ < — (х;~, — х;). 0<х<! 92 оценкь эеэзктивиости стгьтвгия (гл, и Точно так же очевидно, что при х, Е [О, х,] [ Цх,) — ~(х;,) [(й(х,— 0), а при х, Е [хм 1] [1(х,) — Цх~,) [ ~ й (1 — х~), и, следовательно, если неизвестно, где находится х„ то [((х,) — ((хн) [ ~ 1 1 ~(йшах ~х — 0; 1 — хч, — (х — х ); — (ху — хх )~ Эта оценка достижима, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
