…
…
…
…
…
…
…
…
Если вероятности 
состояний 
природы известны, то пользуются критерием Байеса, в соответствии с которым оптимальной считается чистая стратегия 
, при которой максимизируется средний выигрыш 
игрока А, т. е. обеспечивается
.
Если игроку А представляются в равной мере правдоподобными все состояния природы, то иногда полагают 
и, учитывая "принцип недостаточного основания" Лапласа, оптимальной считают чистую стратегию , обеспечивающую
.
Если вероятности состояний совсем неизвестны и нельзя сделать о них никаких предположений, то пользуются критериями Вальда, Сэвиджа и Гурвица. Оптимальной по критерию Вальда считается чистая стратегия , при которой наименьший выигрыш игрока А будет максимальным, т. е. ему обеспечивается 
. В соответствии с этим критерием игра ведется как с разумным партнером, противодействующим игроку А в достижении успеха. Критерий рекомендует игроку А ожидать наихудшего результата и в этом предположении искать наиболее благоприятный исход (выигрыш), который совпадает с нижней чистой ценой игры. Критерий Вальда выражает позицию крайнего пессимизма, и принимаемое решение носит заведомо перестраховочный характер. Однако этот критерий имеет право на применение в практике вместе с другими критериями, оценивающими исследуемую ситуацию с других точек зрения.
Оптимальной по критерию Сэвиджа считается та чистая стратегия , при которой минимизируется величина 
максимального риска, т. е. обеспечивается 
. Таким образом, критерий Сэвиджа советует ориентироваться не на выигрыш, а на риск. Это тоже критерий крайнего пессимизма, но здесь пессимизм понимается в ином свете: рекомендуется всячески избегать большого риска при принятии решения.
Оптимальной по критерию Гурвица считается чистая стратегия , найденная из условия
,
где 
принадлежит интервалу (0; 1) и выбирается из субъективных соображений. При =1 критерий Гурвица превращается в критерий Вальда, при = 0 — в критерий крайнего оптимизма, когда рекомендуется выбирать стратегию, обеспечивающую самый большой выигрыш. В связи с этим критерий Гурвица называют критерием пессимизма-оптимизма. При
0 < < 1 получается нечто среднее между тем и другим. Чем ответственнее ситуация, чем больше стремление подстраховаться в ней и не рисковать без должных оснований, тем ближе к единице выбирается коэффициент пессимизма .
ВЕНГЕРСКИЙ МЕТОД
Этот метод впервые был предложен венгерским математиком Эгервари в 1931г. Длительное время работа оставалась малоизвестной. В 1953г. Кун перевел эту работу на английский язык, заново открыв её для специалистов, раз вил идеи Эгервари и усовершенствовал метод, который в честь первого автора и был назван венгерским.
Первоначально венгерский метод был применен к задаче выбора.
Постановка задачи. Предположим, что имеется 
различных работ 
и механизмов 
, каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма 
при выполнении работы 
обозначим 
. Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях.
Формально она записывается так. Необходимо выбрать такую последовательность элементов 
из матрицы
чтобы сумма 
была максимальна и при этом из каждой строки и столбца был выбран только один элемент.
Введем следующие понятия.
1. Нулевые элементы 
матрицы 
называются независимыми нулями, если для любого 
строка и столбец, на пересечении которых расположен элемент 
, не содержат другие нули 
(для всех 
).
2. Две прямоугольные матрицы и 
называются эквивалентными ( ~ ), если 
для всех i, j . Задачи выбора, определяемые эквивалентными матрицами, являются эквивалентными (т. е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).
3. Элементы, расположенные в выделенных строках или столбцах, называются выделенными элементами.
Описание алгоритма венгерского метода
Алгоритм состоит из предварительного этапа и не более чем (n-2) последовательно проводимых итераций. Каждая итерация связана с эквивалентными преобразованиями матрицы, полученной в результате проведения предыдущей итерации, и с выбором максимального числа независимых нулей. Окончательным результатом итерации является увеличение числа независимых нулей на единицу.
Как только количество независимых нулей станет равным , проблема выбора оказывается решенной, а оптимальный вариант назначений определяется позициями независимых нулей в последней матрице.
Предварительный этап. Разыскивают максимальный элемент в 
столбце и все элементы этого столбца последовательно вычитают из максимального. Эту операцию проделывают над всеми столбцами матрицы . В результате образуется матрица с неотрицательными элементами, в каждом столбце которой имеется, по крайней мере, один нуль.
Далее рассматривают 
строку полученной матрицы и из каждого её элемента вычитают минимальный элемент этой строки. Эту процедуру повторяют со всеми строками. В результате получим матрицу 
( ~ ), в каждой строке и столбце которой имеется, по крайней мере, один нуль. Описанный процесс преобразования в называется приведением матрицы.
Находим произвольный нуль в первом столбце и отмечаем его звездочкой. Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет нуля со звездочкой, то отмечаем его звездочкой. Аналогично просматриваем один за другим все столбцы матрицы . Очевидно, что нули матрицы , отмеченные звездочкой, являются независимыми. На этом предварительный этап заканчивается.
(k+1)-ая итерация. Допустим, что k-я итерация уже проведена и в результате получена матрица 
. Если в ней имеется ровно нулей со звездочкой, то процесс решения заканчивается. В противном случае переходим к (k+1) - й итерации.
Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз проводиться пара этапов: третий - первый. Перед началом итерации знаком '+' выделяют столбцы матрицы , которые содержат нули со звездочками.
Первый этап. Просматривают невыделенные столбцы матрицы . Если среди них не окажется нулевых элементов, то переходят к третьему этапу.
Если же невыделенный нуль матрицы обнаружен, то возможен один из двух случаев: 1) строка, содержащая невыделенный нуль, содержит также и нуль со звездочкой; 2) эта строка не содержит нуля со звездочкой.
Во втором случае переходим сразу ко второму этапу, отметив этот нуль штрихом.
В первом случае этот невыделенный нуль отмечают штрихом и выделяют строку, в которой он содержится (знаком '+' справа от строки). Просматривают эту строку, находят нуль со звездочкой и уничтожают знак '+' выделения столбца, в котором содержится данный нуль.
Далее просматривают этот столбец (который уже стал невыделенным) и отыскивают в нем невыделенный нуль (или нули), в котором он находится. Этот нуль отмечают штрихом и выделяют строку, содержащую такой нуль (или нули). Затем просматривают эту строку, отыскивая в ней нуль со звездочкой.
Этот процесс за конечное число шагов заканчивается одним из следующих исходов:
1) все нули матрицы выделены, т. е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу;
2) имеется такой невыделенный нуль в строке, где нет нуля со звездочкой. Тогда переходят ко второму этапу, отметив этот нуль штрихом.
Второй этап. На этом этапе строят следующую цепочку из нулей матрицы : исходный нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с первым нулем со штрихом в одной строке с предшествующим нулем со звездочкой и т. д. Итак, цепочка образуется передвижением от 0' к 0* по столбцу, от 0* к 0' по строке и т. д.
Можно доказать, что описанный алгоритм построения цепочки однозначен и конечен, при этом цепочка всегда начинается и заканчивается нулем со штрихом.
Далее над элементами цепочки, стоящими на нечетных местах ( 0' ) -, ставим звездочки, уничтожая их над четными элементами ( 0* ). Затем уничтожаем все штрихи над элементами и знаки выделения '+'. Количество независимых нулей будет увеличено на единицу. На этом (k+1) - я итерация закончена.
Третий этап. К этому этапу переходят после первого, если все нули матрицы выделены, т. е. находятся на выделенных строках или столбцах. В таком случае среди невыделенных элементов матрицы выбирают минимальный и обозначают его h (h>0). Далее вычитают h из всех элементов матрицы , расположенных в невыделенных строках и прибавляют ко всем элементам, расположенным в выделенных столбцах. В результате получают новую матрицу 
, эквивалентную . Заметим, что при таком преобразовании, все нули со звездочкой матрицы остаются нулями и в , кроме того, в ней появляются новые невыделенные нули. Поэтому переходят вновь к первому этапу. Завершив первый этап, в зависимости от его результата либо переходят ко второму этапу, либо вновь возвращаются к третьему этапу.
После конечного числа повторений очередной первый этап обязательно закончится переходом на второй этап. После его выполнения количество независимых нулей увеличится на единицу и (k+1) - я итерация будет закончена.
Венгерский метод является одним из интереснейших и наиболее распространенных методов решения транспортных задач.
Пример. Решить задачу выбора, которая определяется матрицей:
3
4
2
2
1
4
5
3
1
3
4
3
1
1
1
3
1
2
2
2
1
3
1
2
1
Решение. При решении задачи используем следующие обозначения: знак выделения +, подлежащий уничтожению, обводим кружком. Цепочку во втором этапе указываем стрелками.
Предварительный этап
3
4
2
2
1
4
5
3
1
3
4
3
1
1
1
3
1
2
2
2
1
3
1
2
1
max
4
5
3
2
3
+
+
1
1
1
0*
2
0*
0
0
1
0
0
2
2
1
2
1
4
1
0
1
3
2
2
0
2
Первый, второй этапы
Å
+
1
1
1
0*
2
0*
0¢
0
1
0
+
0¢
2
2
1
2
+
1
4
1
0
1
3
2
2
0
2
+
+
+
1
1
1
0*
2
0
0*
0
1
0
0*
2
2
1
2
1
4
1
0
1
3
2
2
0
2
Первый, третий, первый, второй этапы
+
Å
+
1
1
1
0*
2
0
0*
0¢
1
0
+
0*
2
2
1
2
1
4
1
0
1
3
2
2
0
2
+
Å
Å
1
0¢
0
0*
1
+
1
0*
0¢
2
0
+
0*
1
1
1
1
1
3
0
0
0
+
3
1
1
0¢
1
Первый, второй этапы
+
+
+
+
1
0*
0
0
1
1
0
0*
2
0
0*
1
1
1
1
1
3
0
0
0*
3
1
1
0*
1
Искомые элементы матрицы соответствуют позициям независимых нулей матрицы (т. е. нулей со звездочкой).
Целевая функция 
НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Графический метод
Если в задаче
все ограничения или их часть либо функция цели нелинейны, то мы имеем задачу нелинейного программирования. Задачи,- в которых ограничения и функция цели линейны и предполагается целочисленность переменных, также являются нелинейными.
В задачах нелинейного программирования отсутствуют все или некоторые из свойств, характеризующих линейные задачи. Область допустимых решений в задачах линейного программирования выпукла. В задачах нелинейного программирования это свойство не сохраняется, область допустимых решений может состоять из нескольких несвязанных областей.
Таким образом, в общем случае задача нелинейного программирования является чрезвычайно трудной для решения. Если число переменных в задаче не превышает трех, то можно попытаться решить задачу графически.
Графическое решение задачи нелинейного программирования существенно отличается от такого же решения задач линейного программирования. Даже в том случае, если область допустимых решений задачи представлена системой линейных неравенств, оптимальное решение задачи может находиться в любой точке области: на границе или даже внутри области.
Рассмотрим несколько примеров графического решения таких задач.
Пример. Найти оптимальное решение задачи
Решение. Множество допустимых решений задачи — четырехугольник OEDB, представленный на рис. 1. Линии одного уровня функции цели - концентрические окружности с центром в точке А(2, 3) - точка внутри области. В этой же точке достигается минимум функции цели, равный 
. Максимальное значение функции достигается в точке В(9, 0), где 
.
Рис. 1
Пример. Найти оптимальное решение задачи
Решение. Область допустимых решений задачи прежняя — это четырехугольник OEDB (рис. 2). Линиями одного уровня функции цели являются гиперболы, асимптотами которых служат прямые 
. С ростом значения 
гиперболы удаляются от точки пересечения асимптот. Максимальное значение функция достигает в точке О(0, 0), где 
. Наименьшее значение функция достигает в гиперболе, вырождающейся в точку (7, 1), где .
Рис. 2
Метод множителей Лагранжа
Если в задаче требуется найти экстремум функции цели при ограничениях-равенствах, т. е. имеется задача вида
и функции 
дифференцируемы, то для решения такой задачи может быть использован метод множителей Лагранжа.
Сущность этого метода состоит в следующем. Вводят дополнительные переменные 
(по числу ограничений задачи) и составляют функцию, называемую функцией Лагранжа:
Чтобы найти оптимальное решение, определяют необходимые условия существования экстремума — равенство нулю частных производных по 
b 
;
Каждое решение системы определяет стационарную точку, в которой может достигаться экстремум функции 
. Дальнейшее исследование этих точек позволяет найти решение задачи.
Пример
Методом множителей Лагранжа решить задачу:
Приведем задачу к канонической форме:
Систему ограничений запишем в виде
Составим функцию Лагранжа:
и приравняем ее частные производные к нулю:
Отсюда получим 
Исследуем поведение функции 
в стационарной точке (2,3). Найдем
Следовательно, функция в стационарной точке (2, 3) достигает минимума, что совпадает с результатом, полученным при решении задачи графическим методом.
Для полного исследования поведения функции необходимо определить ее значения на границах области допустимых решений. Таких точек четыре: О(0, 0), Е(0, 6),
D(6, 3) и В(9, 0). Сравнивая значения функции в этих точках 
и 
), находим, что в точке B(9, 0) функция достигает наибольшего значения.
Динамическое программирование
Динамическое программирование (планирование) представляет собой математический метод для нахождения оптимальных решений многошаговых (многоэтапных) задач. Некоторые из таких задач естественным образом распадаются на отдельные шаги (этапы), но имеются задачи, в которых разбиение приходится вводить искусственно, для того чтобы их можно было решить методом динамического программирования.
Пусть на некоторый период времени Т, состоящий из т лет, планируется деятельность группы промышленных предприятий. В начале планируемого периода на развитие предприятий выделяются основные средства Q0, которые необходимо распределить между предприятиями. В процессе функционирования предприятий выделенные им средства частично расходуются. Однако каждое из этих предприятий за определенный период времени (хозяйственный год) получает прибыль, зависящую от объема вложенных средств. В начале каждого года имеющиеся средства могут перераспределяться между предприятиями. Требуется определить, сколько средств надо выделить каждому предприятию в начале каждого года, чтобы суммарный доход от всей группы предприятий за весь период времени Т был максимальным.
Процесс решения такой задачи является многошаговым. Шагом управления (планирования) здесь будет хозяйственный год. Управление процессом состоит в распределении (перераспределении) средств в начале каждого хозяйственного года.
Пусть имеется груз, состоящий из неделимых предметов различных типов, который нужно погрузить в самолет грузоподъемностью Р. Стоимость и масса каждого предмета j-го типа известны и составляют соответственно сj, и pj единиц ( ). Требуется определить, сколько предметов каждого типа надо загрузить в самолет, чтобы суммарная стоимость груза была наибольшей, а масса не превышала грузоподъемности самолета.
Математически задача записывается следующим образом: найти такие целые неотрицательные значения ( ), которые бы максимизировали функцию
при ограничении
где — количество груза j-го типа, позволяющее достичь 
.
Процесс решения рассматриваемой задачи не является многоэтапным. Она относится к классу задач целочисленного линейного программирования. Однако ее можно решить методом динамического программирования. Для этого весь процесс решения потребуется разбить на этапы искусственно. На первом этапе рассматривают всевозможные варианты загрузки самолета предметами первого типа и среди них находят оптимальный. На втором этапе определяют вариант загрузки самолета предметами первого и второго типов и т. д. Процесс решения задачи продолжается до тех пор, пока не будет найден оптимальный вариант загрузки самолета предметами n типов.
ПРИНЦИП ОПТИМАЛЬНОСТИ И РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ
Метод динамического программирования позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Процесс решения задачи разбивается на шаги. При этом нумерация шагов, как правило, осуществляется от конца к началу.
Основным принципом, на котором базируются оптимизация многошагового процесса, а также особенности вычислительного метода динамического программирования, является принцип оптимальности Р. Беллмана.
Принцип оптимальности. Оптимальное поведение обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны быть оптимальными относительно состояния, полученного в результате первоначального решения.
Принцип оптимальности имеет конструктивный характер и непосредственно указывает процедуру нахождения оптимального решения. Математически он записывается выражением вида
(1)
где 
— оптимальное значение эффекта, достигаемого за 
шагов; п — количество шагов (этапов); 
— состояние системы на l-м шаге; 
— решение (управление), выбранное на l-м шаге; 
— непосредственный эффект, достигаемый на l-м шаге.
"Optimum" в выражении (1) означает максимум или минимум в зависимости от условия задачи.
Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за п шагов, 
, проводятся по формуле (1), которая носит название основного функционального уравнения Беллмана или рекуррентного соотношения. Действительно, при вычислении очередного значения функции используются значение функции 
, полученное на предыдущем шаге, и непосредственное значение эффекта 
, достигаемого в результате выбора решения 
при заданном состоянии системы 
. Процесс вычисления значений функции 
осуществляется при естественном начальном условии
, которое означает, что за пределами конечного состояния системы эффект равен нулю.
ВЫЧИСЛИТЕЛЬНАЯ СХЕМА
Оптимальное решение задачи методом динамического программирования находится на основе функционального уравнения (1). Чтобы определить его, необходимо:
1) записать функциональное уравнение для последнего состояния процесса (ему соответствует 
):
2) найти 
из дискретного набора его значений при некоторых фиксированных 
и 
из соответствующих допустимых областей (так как , то 
. В результате после первого шага известно решение Un и соответствующее значение функции 
;
3) уменьшить значение l на единицу и записать соответствующее функциональное уравнение. При 
оно имеет вид
(2)
4) найти условно-оптимальное решение на основе выражения (2);
5) проверить, чему равно значение l. Если 
, расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если, перейти к выполнению п. 3;
6) вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.
Пример. Требуется перевезти груз из города А в город В. Сеть дорог, связывающих эти города, изображена на рис. 1. Стоимость перевозки груза из города s ( ) в город j ( ) проставлена над соответствующими дугами сети. Необходимо найти маршрут, связывающий города А и В, для которого суммарные затраты на перевозку груза были бы наименьшими.
Рис. 1
Решение. На рис. 1 вершинам сети поставлены в соответствие города, а дугам — транспортные магистрали. Разобьем все множество вершин (городов) на подмножества. В первое подмножество включим исходную вершину 1, во второе — вершины, в которые входят дуги, выходящие из вершины 1, в третье — вершины, в которые входят дуги, выходящие из вершин второго подмножества. Таким образом, продолжая разбиение, получаем пять подмножеств: {1}, {2, 3, 4}, {5, 6, 7}, {8, 9}, {10}. Очевидно, что любой маршрут из города 1 в город 10 содержит ровно четыре дуги, каждая из которых связывает вершины, принадлежащие соответствующим подмножествам. Следовательно, процесс решения задачи (нахождения оптимального маршрута) разбивается на четыре этапа. На первом этапе принимается решение, через какой город, принадлежащий второму подмножеству, везти груз из города 1. На втором этапе необходимо определить, через какой город третьего подмножества везти груз из некоторого города, принадлежащего второму подмножеству, и т. д.
Перенумеруем этапы от конечной вершины сети к начальной (см. рис - 1) и введем обозначения: n — номер шага (n = 1,2,3,4); 
— минимальные затраты на перевозку груза от города s до конечного города, если до конечного города осталось п шагов; 
— номер города, через который нужно ехать из города s, чтобы достичь ; 
— стоимость перевозки груза из города s в город j. Здесь все обозначения несут важную смысловую нагрузку: f означает целевую функцию, s — состояние системы (номер города), индекс п несет динамическую информацию о том, что из города s до конечного города осталось п шагов.
Предположим, что груз доставлен в город 10, следовательно, число оставшихся шагов равно нулю (n = 0) и 
, так как из города 10 груз везти не надо.
Рассмотрим последний шаг (п = 1) и вычислим для него значение функции. Очевидно, что в город 10 груз может быть доставлен или из города 8, или из города 9. Вычислим затраты на перевозку для этих двух состояний:
Чтобы произвести расчет для п = 2, выдвинем гипотезы о месте нахождения груза: 1-я гипотеза — груз находится в городе 5; 2-я гипотеза — груз находится в городе 6; 3-я гипотеза — груз находится в городе 7.
Из города 5 в город 10 можно провезти груз или через город 8, или через город 9. Поэтому оптимальный маршрут из города 5 найдется из выражения
Здесь s = 5 и 
, т. е. условно-оптимальный маршрут проходит через город 9.
Аналогично находим значения функции для s = 6 и s = 7:
Все вычисления удобно выполнять в таблицах. Расчеты первого (
) и второго (
) этапов помещены в табл. 1 и 2 соответственно.
Таблица 1
Таблица 2
Цифры в столбцах таблиц, находящиеся слева от двойной вертикальной черты, представляют собой сумму стоимости 
доставки груза из города s в город j и стоимости 
доставки груза из города j в город В. В каждой строке выбирается наименьшая из этих сумм. Этим определяются условно-оптимальные затраты на доставку груза из города s в конечный город. Затраты (значение функции) обозначены и записаны в первом столбце справа от вертикальной черты, а город, через который проходит условно-оптимальный маршрут, обозначен .
Рекуррентное соотношение для п = 3 имеет вид
Отметим, что для подсчета условно-оптимальных значений используется значение 
, полученное на предыдущем шаге, из табл. 2.
Вычисления для третьего шага (
) приведены в табл. 3. Здесь две клетки заштрихованы, поскольку из городов 2 и 3 нельзя попасть в город 7.
Таблица 3
Таблица 4
Вычисления для четвертого шага (
) приведены в табл. 4, из которой видно, что минимальные затраты на перевозку груза 
и оптимальный маршрут проходит через второй город, так как, 
. Далее из табл. 3 при s = 2 следует, что оптимальный маршрут проходит через город 6, так как 
. Продолжая рассмотрение таблиц, для п=2 определяем, что оптимальный маршрут проходит через город 9 (
). Наконец, из города 9 груз доставляется в конечный город 10 (место назначения). Таким образом, двигаясь от последней таблицы к первой, мы определили оптимальный маршрут
m = (1 —2 — 6 — 9 — 10), затраты на перевозку груза по которому составляют 
.
Список литературы
1 Сборник задач и упражнений по высшей математике: Математическое программирование: Учеб. пособие/, А, и др.; Под общ. ред. . — Мн.: Выш. шк., 1995. — 382 с.: ил.
2 Высшая математика: Мат. программир.: Учеб. / , , ; Под общ. ред. . – Мн.: Выш. шк., 1994. – 286 с.: ил.
3 Вентцель операций. М., «Советское радио», 1972, 552 с.
4 Экономико-математические методы и модели: Учеб. пособие /, , и др.; Под общ. ред. А. В Кузнецова. 2-е изд. – Мн.: БГЭУ, 2000. – 412 с.
5 Исследование операций. Зайченко объединение «Вища школа», 1975, 320 с.
6 Костевич программирование: Информ. технологии оптимальных решений: Учеб. пособие /. – Мн.: Новое знание, 2003. – 424 с.: ил.
7 Кудрявцев операций в задачах, алгоритмах программах. – М.: Радио и связь, 1984. – 184 с., ил.
8 , Загоруйко операций: Учеб. для вузов. 2-е изд. /Под ред. , . – М.: Изд-во МГТУ им. , 2002. – 436 с.
9 , Рубинштейн программирование. -2-е изд., перераб. и доп. – Новосибирск: Наука, 1987.
10 Математическое программирование. -2-е изд., перераб.- М.: Наука. Главная редакция физико-математической литературы. 1980. . – 256 с.: ил.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
