XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 5
Текст из файла (страница 5)
Каждый год в начале сезона садовник проводит химический анализ почвы на своем участке и оценивает продуктивность сада на новый сезон как „хорошая", „удовлетворительная", „плохая", кодируя ее цифрами 1, '2, 3 соответственно. Ведя наблюдения на протяжении многих лет, садовник заметил, что продуктивность сада в текущем году в основном определяется состоянием почвы в предыдущем году. Он составил матрицы вероятностей перехода почвы из 1-го состояния продуктивности в 1'-е как без дополнительной обработки (матрица Р, = (р,',)), так и с дополнительной обработкой (матрица Рз = (рз5)) участка, включающей внесение минеральных удобрений и т.дл 0,2 0,5 0,3 0,3 0,6 0,1 Р, = 0 0,5 0,5 ; Рз = 0,2 0,5 0,3 0 0 1 0,1 0,4 0,5 где номера строк и столбцов соответствуют состояниям продуктивности почвы в текущем и следующем годах соответственно.
Так, вероятность перехода продуктивности почвы 11з хорошего состояния в плохое без дополнительной обработки участка составляет р,'з — — 0,3, а с дополнительной обработкой участка — рз1з = 0,1. Матрицы Р, и Рз являются матрицами переходных вероятностей. С вероятностью перехода почвы из состояния продуктивности 1 = 1,2,3 в текущем году в состояние продуктивности ,1 = 1,2, 3 в следующем году непосредственно связана величина т„, равная доходу (г; ) 0) или потерям (г,, < 0) садовника ЗО ь ОснОВные пОнЯтиЯ исслеДОВАниЯ ОпеРАЦий в следующем году в денежных единицах при наличии (т = 2) или отсутствии (т = 1) дополнительной обработки участка. Поэтому каждой матрице переходных вероятностей Р = (р,,) садовник поставил в соответствие матрицу Й = (г,1), отражающую его доходы (эту матрицу называют матариией дохода).
Пусть Й!= О 5 1; Йэ-— 7 4 О где элементы матрицы Йо учитывают расходы, связанные с дополнительной обработкой участка. Садовник планирует проработать на своем участке еще А! лет и получить максимальную прибыль. Нужно найти оптимальный вариант его действий: в какие годы, если это необходимо, проводить дополнительную обработку участка? Анализируя задачу с садовником, можно заметить, что она является не только задачей принятия решений в условиях риска, на что указывают матрицы вероятностей перехода почвы из одного состояния продуктивности в другое, но и динамической задачей исследования операций.
При этом в отличие от классической навигационной задачи (см. пример 1.3) информационное состояние „лица, принимающего решения", т.е. садовника, изменяется во времени дискретным образом (раз в год после анализа продуктивности почвы), а сама процедура принятия решений является поэтапной. Классификация задач исследования операций по виду критерия оптимальности. Классификация задач исследования операций может быть связана с видом используемого критерия оптимальности, который в принципе может иметь любой, в том числе и неформализуемый, вид. Так, в задаче о составлении пищевого пайка (см. примеры 1.1 и 1.2) в качестве одного из критериев оптимальности может быть и такой: паек должен обладать наилучшими вкусовыми качествами. Ь Ь Постановки эаяач и иэ классификация Критерием оптимальности может быть требование о максимизации или минимизации некоторой скалярной функции 7", определенной на множестве допустимых решений и называемой нелевой функиией. В этом случае задачу исследования операций называют задачей матаемапзическоао проараммирования.
Если же критерием оптимальности является требование о максимизации или минимизации нескольких скалярных функций, то говорят о задаче мновокритаериальной (вектпорной) оптаимизаиии. Таким образом, при построении математических моделей для принятия решений о составе пищевого пайка в примере 1.1 мы имеем дело с задачей многокритериальной оптимизации, а в примере 1.2 — с задачей математического программирования. В математическом программировании чаще других рассматривают задачи, в которых множество С допустимых решений является подмножеством К", удовлетворяющим системе линейных неравенств а,,х1(6,, 1=1, пь Е Такое множество, если оно непустое н ограниченное, называют выпуклым мноеозранником, поскольку этот класс выпуклых множеств отвечает геометрическому представлению о многогранниках в пространстве'. Если множество допустимых решений С С К" представляет собой выпуклый многогранник, а целевая функция 1 линейная, 'то исходную задачу называют задачей линейноао нроирам'мирования.
Если множество С с К" является выпуклым многоогранником, а целевая функция 1 является квадратичной, то исходную задачу называют задачей квадратаинноао проераммирования. Если С с К" — выпуклое множество, а ~— выпуклая функция, то исходную задачу называют задачей вынуклозо прозраммирования. Теория решения стохасти- Смэ Ашмомоо С.А. 32 1. ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ ческих задач линейного программирования является предметом исследований спъокастпического программирования. В других задачах математического программирования множество С допустимых решений может быть конечным множеством.
Такие задачи относятся к дискретпному программированию. В них допустимые решения могут быть точками целочисленной решетки Е" (целочисленное программирование) или векторами, каждая координата которых может принимать лишь два значения (булево программирование). В отдельных задачах элементы множества С допустимых решений могут представлять собой перестановки конечного числа символов и т.д. Множество С допустимых решений может быть подмножеством некоторого функционального пространства.
В этом случае получаем задачу вариационного исчисления или задачу оптимального управления (см. пример 1.3). Особым случаем задач математического программирования являются задачи о нахождении максимина: /У~ шахпйп1'(У,еТ), 1 ( Е С, г и минимакса: /Г'~ ш1п шах Г(У,Я), ~ ~ й С. и 1пь Об одном аспекте ниегокритерпаеьной оптимизации 33 Прежде чем переходить к анализу специфических особенностей решения задач многокритериальной оптимизации, сделаем замечание, относящееся к математическим методам исследования операций. Под математическими методами исследовани,я операций обычно понимают математический аппарат (специально разработанный или адаптированный), предназначенный для решения задач исследования операций.
Разработанность математических методов для различных классов задач исследования операций является далеко не одинаковой. В настоящее время наиболее разработана теория линейного и выпуклого программирования. 1.2. Об одном аспекте решения задач многокритериальной оптимизации При анализе основных понятий исследования операций мы уже сталкивались с примерами задач многвкритериальной оптимизации. В общем случае постановки задач многокритериальной оптимизации являются более корректными, чем, скажем, постановки задач математического программирования. Это связано с тем, что любая операция представляет собой совокупность целенаправленных действий и проведение практически любой операции, как правило, предполагает достижение не одной, а нескольких целей.
В заключение приведенной далеко не полной классификации задач исследования операции отметим, что задачи многокритериальной оптимизации, равно как и задачи с критериями оптимальности, выражаемыми отношениями порядка на множестве С допустимых решений, по существу, относятся к теории игр'.
Поэтому их классификация проводится по теоретико-игровым признакам. 'Смл Гермейер Ю,Б. Пример 1.6. При проектировании нового технического уптройства обычно преследуют несколько целей, среди котоРых могут быть снижение массы конструкции и повышение ее надежности, снижение стоимости изготовления, повышение технологичности и т.д.
В процессе проектирования указанные цели достигаются за счет соответствующего выбора структуры и параметров конструкции, которые кодируются вектором Х. Таким образом, эта задача оптимального проектирова- ~Ь (Х ) — 1 пип . ХеС Хе=Хе, й=1,т, может быть записана так: ЯХ)-+ехФг, й= 1,т. ХеО Л(Х) -~ шах ХЕС и критериями опти миль ности — Л(Х)-» ппп. ХЕС Д(Х) = хь -+ пп'и, /с = 1, 2. ХНС' ЯХ) — +ппп, й=1,т, ХеС х=, х= или в векторной форме; Рис. 1.2 (1.2) Т"(Х) -+ ппп. ХЕО 34 1. ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ ния является типичной задачей многокритериальной оптими- зации. В общем случае математическая формулировка задачи многокритериальной оптимизации с множеством допустимых решений С С К" и векторной целевой 4ункцией Любой скалярный критерий вида можно заменить эквивалентным скалярным критерием Поэтому понятно, что задачу многокритериальвой оптимиза- ции можно сформулировать следующим образом: Задачу исследования операций называют некорректной, если она не имеет решения.
На начальном этапе развития исследования операций некорректными считали задачи многокритериальной оптимизации, а в качестве обоснования приводились следующие соображения. 1.2. 06 одном аспекте многокритернальной оптимиэации 35 Пусть для каждого й = 1, т элемент Хь множества С является решением задачи математического программирования В этом случае, согласно представлению (1.1), если то Хо — решение задачи мвогокритеризльной оптимизации (1.2). Но, как правило, Хь ~ Х при й~ 1. Поэтому в общем случае следует ожидать, что задача многокритериальной опти- мизации (1.2) не имеет решения. Пример 1.7. Рассмотрим простейшую задачу многокритериальной оптимизации с множеством допустимых решений С = ((х1 хз): (х1 — 2)з+ (хз — 2)~ ( 1~ Из геометрических соображеНий очевидно (рис. 1.2), что А так как Х1 ф Хз, то исходная задача не имеет решения. Итак, одновременное достижение минимума по всем скалярным критериям ЯХ) на одном решении Х в общем случае Февозможно.
Выход состоит в поиске некоторого компрогянсса в достижении локальных целей. „Лицо, принимающее 9вшения", должно сформулировать некоторый принцип комяяРолеиссп и придерживаться его при выборе оптимального 36 ь ОснОВные пОнятия исследОВАния ОпеРАциЙ ьг. Оо одном асиенте многокритернальной оитимиэации 37 решения. Принцип компромисса должен определить свойства оптимального решения и дать ответ на главный вопрос: в каком смысле оптимальное решение лучше всех других решений? Кроме того, это оптимальное решение должно принадлежать множеству допустимых решений задачи. Число возможных принципов компромисса очень велико. Поэтому при решении многокритериальных задач возникает ряд проблем, носящих не вычислительный, а концептуальный характер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
