Введение в теорию исследования операций. Гермейер (1971) (Введение в теорию исследования операций. Гермейер (1971).djvu), страница 8

Примером использования такого соединения является модель Ч1, если в качестве частных критериев выступает не время работы, а само работоспособное или неработоспособное состояние отдельных агрегатов. При этом последовательное соединение агрегатов дает пример конъюнкции (все агрегаты должны работать), а дублирование системы в целом есть пример дизъюнкции конъюнкции (должна работать хоть одна система, в которой должны работать все агрегаты). Наконец, поагрегатное дублирование дает пример конъюнкции дизъюнкций (должен работать хоть один агрегат каждого типа).

Ч. Обобщенное логическое свертывание критериев. Прямым обобщением действий предыдущего пункта являются: вместо (43) антагонистические интересы (Р'„= — йу~; вместо (44) яг,= ппп Ч7~Х~, Х )О; 1</<« (46) б) суммарная цель состоит в выполнении всех частных целей (конъюнкция) « йу. = П )р~. (44) 43 й З) О ЦЕЛЯХ И КРИТЕРИЯХ вместо (45) 1)7,= шах йР~Л~, Л~)0. (47) 1 /<з Эти способы объединения применимы для любых типов целей (критериев). Выражение (46) немедленно превращается в (44), если все Ю' принимают только значения 0; 1, а Л =1. Точно так же в этом случае и (47) эквивалентно (45). Использование операций минимума и максимума видно во многих приведенных выше примерах моделей; особенно ярким является пример Ъ1, где за критерий принимается время работы системы (см., например, (15), (17) и т. д.).

Ч1. Случайное и неопределенное свертывание. Суммарным критерием объявляется тот или иной частный критерий в зависимости от того, какое значение примет неконтролируемый фактор 1, т. е. )у', = )р" 0) = ул В общем случае частные критерии могут определяться непрерывной случайной или неопределенной величиной, и мы получим Ф, = Ю (а) = У„. (48) Несмотря на кажущуюся тавтологию, именно этот случай является одним из путей проникновения случайных и неопределенных факторов в исследование операций и как раз отражает неуверенность оперирующей стороны при выборе критерия операции. В частности, если оперирующая сторона не может точно определить коэффициент веса Л7 частных операций в способах объединения ! и Ч, то эти (Л~) и будут теми неопределенными факторами, о которых идет речь.

С нашей точки зрения, неуверенность оперирующей стороны при выборе критерия увеличивает количество случайных или неопределенных факторов, неконтролируемых оперирующей стороной, что, несомненно, затрудняет выбор стратегий и уменьшает их эффективность. Следует подчеркнуть, что при таком способе объединения критерии В'7 становятся как бы равновесомыми; все равно„увеличивать ли Йгу илн Ж~+„если увеличение одинаково. Если и в этом нет уверенности, то нужно одновременно вводить неопределенные коэффициенты веса 44 о ьогмьлизнцяи нсследовьння опвгкций (гл. ~ частных критериев, т.

е. вместо (48) писать (г', = Л (а) )г'„. Перечисленные методы объединения критериев применимы и к случаю не полностью сформулированной операции. Здесь в роли частных критериев должны выступать функции ю;(х, у). В 4. Полнота системы элементарных действий над критериями (методов свертывания) Покажем, что введенные в предыдущем разделе элементарные действия в состоянии отразить всю широту возможных однозначных зависимостей Ф', от )р~, если использовать всевозможные комбинации этих действий.

Это обстоятельство следует из нескольких результатов, которые сейчас будут приведены. Т е о р е м а 1. Если однозначная функция )Р', = = Р(!Р'„..., )Р',) и каждое из %'~ принимают лишь конечное число конечных возможных значений, то зависимость !Р, от (г' может быть представлена в виде конечного числа действий типа Р1, [т. е.

(43) — (45)] и типа 1 и 11 [(39) и (4!)]. Доказательство. Пусть Ф'~ — возможные дискретные значения 1-го критерия (! =1, ..., 1,.), занумерованные в порядке возрастания. )г', также, очевидно, принимает лишь конечное число значений, которые в порядке роста обозначим через Ф',„(я=1, ..., У). Введем функции а, =О при Ж',( Уь; ы, =1 при Ф,>%',„. Поскольку а,„является функцией Я7„то она является и функцией Ф'.. Имеем, очевидйо, (49) У,=,~~ Ж вЂ” (гы- )ы ь()Р ) где К„=-О. Таким образом, 1Р, образовано из ы,ь по правилу 1 (39).

Ч 4! полнота систвмы элямкнтлгных дняствий 45 Пусть андлогично Ф'ы(%'у) определяются равенствами Ю,,=О' при Ку(Ч7;у, 1=1, ., хр (60) Ж';,.:= 1 при Ф'у~ )(Чг;,, Таким образом, функции %'П образованы нз ЧУ по способу П. В то же время ()т .= ~г (Чг; — Чтг, )ЧУ,,(Ж'у), (51) Таким образом, го,х, являюшиеся функцией (Ч'„могут быть записаны как функции ЧУ, ((Ч'у). Поскольку ьз, „ и В'П являются булевыми переменными (принимают только значения 0 и 1), то по уже упоминавшейся теореме математической логики зависимость <о,а от Ж', может быть представлена *) как последовательность действий типа 1хг.

Но так как сами Уг выражаются через (Чу по способу П, а (Чг,— через ьу„а по (49), т. е. по правилу !, то теорема доказана. Теорема ! исчерпывает здесь результаты, говорящие о точном представлении зависимостей Р (Ч7)) в виде конечного числа элементарных действий. Последующее утверждает только возможность того или иного приближенного представления, ио с любой заданной точностью.

Теорема П. Пусть Чг",=-Р((Что ..., Чг",) принимает конечное число — И значений ЧР,», а Ч() пусть произвольны, но ограничены. Тогда, каково бы ни было е ) О, существуют множество М векторов (ЧУ ) и функция г"'(Ч7„..., (Ч'х), составленная из конечного числа действий 1, П н !Ч, такие, что *) Функция ю,а (Ж; (Пх)) всегда может быть доопределена до Ыеа()ГЫ) дЛя НЕЗаВИСИМЫХ УЫ, ПрИНИМаЮщИХ ЗНаЧЕНИя О; !. ДЛя этого достаточно, например, положить ю,а(гг'; )=О, если хотя бы для одного ! вектор (чг р ..., У-,ч) ие есть вектор (вгы(!ру)). Вектор (%' , ..., %'-, ), очевидно, тогда и только тогда есть вектор ()рту (чту) ... У- (%'у)) для некоторого 1, когда Уы ~ чг у ... .

° . ="- Ф'! р' 46 О ФОРМАЛИЗАЦИИ ИССЛЕДОВАНИЯ ОНЕРАЦ31й (ГЛ. ! 1) Р (гР' ) = Р' (К !), когда (Ж~) б М; 2) Р'(((~,) пробегает все !Ч значений У7,» !)ри (ЯРГ), пробегающем М, не принимая иных значенйй и при любых ()Р ); 3) !Р( образует е-сеть на ограниченпом множестве всех (Ф'~), т. е. для любого ('!Р' ) найдется (УР!') ЕМ, удаленный от (К~) не более чем на е. Доказательство. Пусть М» — множество векторов (Ж~), для которых Р()Р' ) =- )Р',.». Ввиду ограниченности М„в нем всегда можно выделить е-сеть М», составленную из конечного числа векторов ()Р')»!'), где 1= 1, ..., т». Занумеруем все )Р')!»!, для данного 1, в порядке возрастания в виде величин К;, где г = 1, ..., Лу ( ~~,',т».

Введем »=1 1, РУ,)%,.„ р(~)=((, ~ , ( ,„, и образуем новые переменные Ри Ж', = ~(К',„— К,„!) ы,„(К'т). Р=! Очевидно, что ()Р' ) = ('»Р' ), если (%'у) Е М = Х М» Оставим определение Ж'~ тем же, если ым — независимые переменные, принимающие только значенйя 0 и 1. Функцию Р, (Ф~) определим равенством (Р()Р,), ()Р,) б М, ( )Р„, ()Р',.) (М. Функция Р,(ыр)=Р,(У,.), очевидно, удовлетворяет усло- виям теоремы 1 и потому представима в виде конечного числа действий 1, П и 1Ч. То же относится и к функции Р ())Рс) Р» 1"Ъ ()' у)1' т. к.ь!~,(%' ) образованы по способу П. Поскольку Р" (В'~) =- =Р»(Ю'~(У,)) =-Р(Ж'~) при (И'~) ~М и принимает лишь й 41 познать системы элементлгных действий 47 значения Ю',и принимая все эти значения уже на множестве М, и поскольку М образует е-сеть, то теорема доказана. Так как любая равномерно непрерывная функция с любой заданной степенью точности может быть представлена кусочно постоянной функцией, то, видоизменяя несколько доказательство, в основном аналогичное только что приведенному, можно убедиться, что справедлива Теорема П1.

Если В',=Р(!Р') равномерно непрерывна на некотором параллелепипеде возможных значений (!Ь' ), то она с любой степенью точности может быть представлена в виде конечного числа действий типа 1, 1! и 1Ч. Хотя эти теоремы и не полностью исчерпывают вопрос, однако с точки зрения практики они достаточно убедительно говорят о полноте системы операций 1, 1! и !Ч.

Поскольку действия типа Ч, как показано выше, включают в себя 1Ч, то тем самым продемонстрирована и полнота системы действий 1, П и Ч. Однако можно доказать и значительно более сильное утверждение. Теорема 1Ч. Если Ф',=Р(Ф'з) (1<з) непрерывна на области — оо < У!в<В' <У~~ < ьо, то каково бы ни было е, найдется таков конечное число коэффициентов аи„, с,„(1<1,; й<й, <з+2), что в этой области ! / Ю Р(Ф'~) — ш(п шах ( .'У, 'а,ь~Ж'у+с,„<е. ~м(кь ~кькее !=~ Дока за тель ство. Ход доказательства не зависит от величины з, поэтому для простоты ограничимся случаем з=2. Разобьем прямоугольную область точек (Ко Ф',) на столь малые прямоугольники, чтобы разность,"., между максимумом и минимумом Р (К„Ф',) в этих прямоугольниках была меньше е. Затем разобьем каждый из прямоугольников диагональю на два треугольника. Таким образом, область изменения (йУ„Ж',) разбита на треугольники, внутри которых изменение В',, не превышает е.

48 о ььогмллизлцни нсслздовлнин онеглцнй (гл. Проведем через три точки пространства ()Р'„ )Р'„ Ж',.), отвечающие вершинам треугольника, плоскость Ж.=аы Ф"ь+аыьФ'ь+Сы, (52) где Ь вЂ” номер треугольника. Внутри треугольника эта плоскость отличается от Р()Р'„В',) не более чем на е. Пусть теперь )㻠— угол между Ь-й плоскостью и положительной осью 1Р',; через гг обозначим — пни)гь.

Прове- 1 2 дем через каждую пару точек пространства ()р„Ф'„(р,), соответствующих вершинам Ь-го треугольника, плоскости Ж', = аьь, Ф, + аьь,Ф, + сь;, Ь = 2, 3, 4, (53) каждая из которых составляет с положительной осью Ю, угол, равный Й, и острый угол с внешней нормалью в плоскости (Ж'„%',) к стороне Ь-го треугольника, проходящей через соответствующую пару вершин. Тогда плоскость (52) расположена над Ь-м треугольником выше, чем три остальные плоскости, отвечающие Ь=-2; 3; 4; а функция (ОЬЫ)р, + ОЬЬьК'ь+ СЬЬ) = 1Ь (В'„)р,) 1.сь~ь представляет собой трехгранную «чашу», дном которой является часть плоскости (52), лежащая над Ь-м треугольником, а боковые грани — куски плоскостей (53). Далее, по определению Й, 1ь ((ь'„)г',) расположена над треугольником с номером Ь, ~ Ь выше, чем плоскость аьп1%/, + аь „+ сь „а значит, и выше, чем 1ь, ()ь" „'йг",).

Поэтому ш!п1ь(У„Ф',)=пппшах(алые +ОьыУ,+сьь) ь ь ь совпадает над Ь-м треугольником с соответствуощим куском плоскости (52) и потому отличается от г" (Ю'„%',) всюду не более чем на е, что и требовалось доказать. Как видно из доказательства, утверждаемая приближенная запись г(гр'т) есть не что иное, как иная формулировка кусочно линейной аппроксимации. Замечания к теореме гЧ. 1. В формулировке теоремы можно, конечно, с соответствующим изменением коэффициентов линейных форм, 5 41 полнотА системы элементАРных де»стии» 49 брать не мииимакс, а максимин. Чтобы в этом убедиться, достаточно роспользоваться теоремой 1Ч для г',(Ф'у) = = — г'(У'у) н равенством '-1 ппп щах ~ — ~аь»уеду — сь»ь = — пьах ппп ~~~а»»,Фу+с,» ь» ь» ~! 2. В современной математике, в частности в линейном и нелинейном программировании и в теории игр, большое значение приобрели выпуклые (вогнутые) функции 1(х„..., х„), которые определяются как удовлетворяющие неравенству у (Лх, + (1 — Л) у„..., Лк„+ (1 — Л) у„) ( ( Ц (хы ..., х„) + (1 — Л) ) (уы ..., у,) (54) при любых Л из интервала 10, Ц.