Основное неравенство теории двойственности

Для любых допустимых планов и пары взаимодвойственных задач справедливо неравенство . – план производства, – вектор оценки ресурсов.

Критерий оптимальности.

Если для некоторых допустимых планов и выполняется условие равенства функций, то и являются оптимальными ).

Для существования оптимального плана любой пары двойственных задач необходимо и достаточно существование допустимого плана для каждой из них.

Если одна задача имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевой функции совпадут.

Экономический смысл: если разрешима одна задача, то разрешима и другая

Теорема о дополняющей нежесткости.

Для того чтобы планы и пары взаимодвойственных задач были оптимальными, необходимо и достаточно:

Из них следует, что если какое-либо неравенство системы не обращается в строгое равенство оптимальным планом, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю.

Если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение двойственной задачи её оптимальным планом должно обращаться в строгое равенство.

Экономический смысл: по некоторому оптимальному плану производства расход ресурса строго меньше его запаса, то в оптимальном плане соответствующая двойственная оценка этого ресурса = 0. Если же в некотором оптимальном плане оценок его компонента строго >0, то в оптимальном плане производства расход соловеющего ресурса равен его запасу.

Двойственные оценки

Двойственные оценки показывают приращения целевой функции, вызванное малым изменением свободного члена соответствующего ограничения.

Заменим .

Двойственная оценка численно равна изменению целевой функции при изменении ресурса на единицу.

Теория матричных игр. Парные игры с нулевой суммой. Решение игр в чистых и смешанных стратегиях.

Игрой называют упрощенную модель конфликтной ситуации. Игра ведется по определенным правилам. Каждый из участников игры принимает такие решения, которые, как он полагает, могут обеспечить ему наилучший результат. Исход игры – значение некоторой функции, называемой функцией выигрыша или платежной. Если сумма выигрыша игроков равна нулю, то игру называют с нулевой суммой.

Парные игры – игры с 2 игроками.

Пусть игроки и располагают конечным числом возможных действий и . Выбирается стратегия . Если игра состоит из личных ходов, то выбор пар стратегий и однозначно определяют результат: – побеждает игрок , – побеждает игрок .

– минимальный выигрыш игрока

– максимальный проигрыш игрока

Если известно , то можно составить матрицу выигрышей (платёжную) игрока .

– нижняя чистая цена игры

– верхняя чистая цена игры

Если , то игра имеет седловую точку. Пара чистых стратегий , соответствующих и , называется седловой точкой матрицы, а элементы – седловыми.

Для игр без седловых точек решение лежит в области смешанных стратегий.

Смешанной стратегией игрока называют вектор , компоненты которого удовлетворяют условию:

Смешанной стратегией игрока называют вектор , компоненты которого удовлетворяют условию:

В выражениях – вероятности, с которыми игроки выбирают свои стратегии.

При использовании смешанной стратегии игра приобретает случайный характер. Случайной становится и величина выигрыша игрока , которая называется платежной функцией.

Смешанные стратегии называют оптимальными, если они образуют седловую точку:

Поиск оптимальной стратегии начинается с упрощения платежной матрицы. Если в матрице элементы строк не меньше советующих элементов строки , то говорят, что стратегия доминирует над стратегией .

Доминируемые стратегии могут быть исключены из матрицы, так как вероятность применения равна нулю. Решение матрицы сводится к решению задач ЛП.

Решение задач (тоже не решали как бы).

Каждый игрок запоминает одно из чисел 1,4,6,9, затем показывают написанное. Если оба числа оказались одинаковой четности, то игрок выигрывает столько очков, сколько сумма этих чисел. Если четность разная, то выигрывает второй игрок.

	1+1=2	-1-4=-5	-7		-7
	-5			-13	-13
	-7			-15	-15
		-13	-15		-15

Игра не имеет седловой точки. Находим области смешанных стратегий.

Пример упрощения матрицы:

Необходимо отметить, что отбрасывая дублируемые и доминируемые стратегии в игре с седловой точкой, мы все равно придем к игре с седловой точкой, т.е. к решению в чистых стратегиях. Но лучше сразу проверить, не обладает ли игра седловой точкой - это проще, чем сравнивать почленно все строки и все столбцы платежной матрицы.

Элементы строчек 4 меньше или равны элементам строчки 5, удаляем, и так далее.

Получаем матрицу – седловую точку:

Пример решения матрицы:

Динамическое программирование. Принцип оптимальности Беллмана. Задача нахождения минимального пути на сети дорог. Задача о распределении капиталовложений. Задача о замене оборудования. Задача оптимального управления поставками ресурсов.

Динамическое программирование – математический аппарат, позволяющий осуществлять оптимальное планирование управляемых процессов.

Имеется некоторая управляемая система S, характеризующаяся определённым набором параметров. В этой системе происходят какие-то процессы, которые можно представить как многошаговые. На каждом шаге процессам в системе соответствуют определённые значения параметров, описывающих состояние системы – параметр . Заданные условия позволяют определять или начальное, или конечное состояние системы.

Управление S осуществляется для достижения конкретной цели, поэтому указывается показатель эффективности управления, который будет называться целевой функцией – численно отражает эффект, получаемый при том или ином управлении.

Принцип относительности Беллмана.

Каково бы ни было состояние системы S в результате i-1 шагов, управление на i-м шаге должно выбираться так, чтобы оно в совокупности с управлениями на всех последующих шагах с (i+1)-го до N-го включительно доставляло экстремум целевой функции.

Введём следующие обозначения:

– множество состояний, в которых система S может находиться перед i-м шагом;

– множество состояний в конце i-го шага;

- множество управлений, которые могут быть выбраны на i-м шаге и под воздействием каждого из которых система S переходит в одно из состояний множества .

- условно-оптимальное значение целевой функции на интервале от i-го до N-го шага включительно при условии, система S находилась в .

- значения целевой функции на i-м шаге, конкретное число.

- условно-оптимальное значение целевой функции на интервале от (i+1)-го до N-го шага.

В принятых обозначениях принцип оптимальности Беллмана можно записать в математической форме следующим образом:

Для последнего (N-го) шага уравнение принимает вид:

Если рассматривается система без последействия, то её состояние в конце i-го шага будет отвечать одному из элементов множества и зависит как от состояния системы S на начало шага , так и от управления, выбранного из множества . Эту зависимость символически можно записать в следующей форме:

На основании данных уравнений строится вычислительная процедура метода динамического программирования, распадающаяся на два этапа: условную и безусловную оптимизацию.

Условная оптимизация осуществляется путём «попятного» движения от последнего шага к первому. С помощью уравнения для каждого состояния из множества находится такое управление из множества , при котором функция достигает экстремума, и система S переходит в заданное конечное состояние. Таким образом, для каждого состояния из множества находится условно-оптимальное значение целевой функции и соответствующее управление.

Далее на основании уравнения и множества состояний системы S перед шагом определяются условно-оптимальные управления на шаге и условно-оптимальные значения целевой функции на двух последних шагах: и .

В результате получается последовательность множеств условно-оптимальных управлений системой S, которая в конкретных задачах может быть представлена последовательностью таблиц.

Для определения безусловно-оптимального при заданном её начальном состоянии анализируем выполненные расчёты от первого шага к последнему. Для начального состояния находим в множестве некоторое таким образом, чтобы система перешла в , и так далее.

Задача

Задача нахождения минимального пути на сети дорог.

На данной сети дорог указаны стоимости доставки единицы груза из пункта в пункт. Найти наиболее экономный маршрут перевозки груза из пункта 1 в пункт 10.

Концепция динамического программирования предполагает, что процессу принятия решения в оптимизационной задаче может быть придан шаговый характер. С этой целью разобьем все пункты сети на группы. К группе I отнесем пункт 1, к группе II — пункты, и так далее. В результате движение транспорта с грузом из пункта 1 в пункт 10 можно рассматривать как четырехшаговый процесс.

В соответствии с вычислительной схемой метода дина­мического программирования фактическое формирова­ние искомого оптимального управления данным процес­сом состоит из двух процедур: условной оптимизации и безусловной оптимизации. Условная оптимизация осу­ществляется в результате «попятного» движения от по­следнего шага исследуемого явления к его первому шагу, в процессе этого движения находятся шаговые условно-оптимальные управления. Безусловная оптимизация осу­ществляется в процессе движения в прямом направлении от первого шага к последнему, при этом из найденных ранее шаговых условно-оптимальных управлений форми­руется безусловное оптимальное управление всем дан­ным процессом.

Условную оптимизацию начнем с анализа четвертого шага. Возможные состояния, в которых транспорт с гру­зом может оказаться перед четвертым шагом, зависят от управлений на предшествующих шагах и соответствуют его местонахождению либо в пункте 7, либо в пункте 8, либо в пункте 9. Эти состояния образуют множество возможных состояний на начало четвертого шага. Это будет множество . Из каждого указанного состояния можно перейти в конечное состояние единственным путем: из пункта 7 в пункт 10груз может быть доставлен только дорогой (7, 10), из 8в 10 — дорогой (8, 10), из 9в 10 — дорогой (9,10). Реше­ния о доставке груза по названным дорогам и являются управлениями на четвертом шаге, соответствующими указанным состояниям.

	7-10
	8-10
	9-10

	4-7			7+3=10
	4-8			5+9=14	-
	5-7
	5-8				-
	5-9				-

Оптимальный путь: 3-5

	1-2			2+10=12	-
	1-3			5+6=11

При безусловной оптимизации остается пройти еще раз весь оптимизируемый процесс, но уже в прямом направлении, начиная с первого и кончая четвертым шагом, и «прочитать» искомое оптимальное управление (наиболее экономный маршрут), которое будет составлено из найденных ранее (при условной оптимизации) шаговых условно-оптимальных управлений (дорог между отдельными пунктами сети).

Задача о распределении капиталовложений.

Предприятиям выдается кредит. Указан возможный прирост, который не зависит от того, сколько денег вложено в другие предприятия. Общий прирост равен сумме от всех предприятий.

Пример задачи:

Состояние системы S будет характеризоваться в каждый данный момент конкретным вариантом распределения кредита между предприятиями.

Состояние системы S перед выбором раз­мера суммы, ассигнуемой i-му предприятию (перед i-м шагом), определяется величиной остатка кредита после выделения средств другим i-1 предприятиям (на предше­ствующих i-1 шагах).

Поскольку возможны различные варианты распределения средств, то и состояния производственного объединения перед i-м шагом могут быть различными, и каждое из них будет характеризоваться соответствующим значением остав­шейся суммы. Совокупность этих значений и составит множество . Этим же символом обозначим и мно­жество состояний системы перед i-м шагом.

Множество управлений зависит от условий задачи, в данном случае:

Целевая функция означает прирост выпуска продукции на предприятии при условии, что оставшийся кредит будет принадлежать множеству .

- означает максимальный суммарный прирост, полученный на всех пред­приятиях, начиная с -гo.

Согласно уравнению Больцмана:

Для предприятия №4:

60	60	52	52

Далее составим таблицы остальных 3 шагов решения, при этом на каждом шаге учитывая предыдущие исходя их формулы:

Остаток на текущий щаг	Сколько будем отдавать текущему предприятию	Сколько будет отдавать предыдущему	Прирост текущего предприятия	Прирост предыдущего предприятия	Сумма приростов	Максимальный суммарный прирост
						-
						-
						-
						-
						-
						-
						-
						-
						-
						-
						-
						-
	40	60	25	52	77	77
						-
						-
						-

						-
						-
						-
						-
						-
						-
						-
						-
						-
						-
	0	100	0	77	77	77
						-
						-
						-
						-
						-
	0	100	0	77	77	77

После завершения условной оптимизации переходим к безусловной оптимизации — поиску наиболее выгодно­го распределения кредита между предприятиями. Обра­щаемся к таблице 5.5, ибо она соответствует первому шагу. Из этой таблицы видно, что при кредите в 100 млн.руб. максимальный прирост выпуска продукции на всех четырех предприятиях составляет 77 млн.руб., если первому предприятию средств не выде­лять. Остаток кредита 100 – 0 = 100 подлежит оптимальному распределению между остальными тремя предприятиями.

Из табл. 5.4 следует, что из 100 млн.руб. третьему предприятию надлежит выделить 0 млн.руб., а остаток 100 – 0 = 100.

Из табл. 5.3 следует, что из 100 млн.руб. второму предприятию надлежит выделить 40 млн.руб., а остаток 100 - 40 = 60.

Из табл. 5.2 следует, что первому предприятию надлежит выделить 60 млн.руб.

Задача о замене оборудования.

Определение наиболее подходящего времени для замены оборудования. В начале планового периода из лет имеется оборудование возраста лет. Для каждого года планового периода известны стоимость производства (с использованием имеющегося оборудования) продукции, затраты связанные с эксплуатацией.

При этом:

- - это множество состояний оборудования перед i-м годом;

- - множество состояний сразу после выбора управления;

- - множество состояний i-го года;

- - множество управлений, которые могут быть приняты в начале i-го года. В нашей задаче могут быть только два управления: «сохранение» или «замена».

В зависимости от выбранного управления по-разному будет вычисляться :

Из данной формулы видно, что в случае замены оборудования каждый раз мы будем получать одно и тоже значение Z.

– остаточная стоимость оборудования, – стоимость нового оборудования, r(t) – стоимость продукции (производимой в течение года на этом оборудовании), u(t) – ежегодные расходы на эксплуатацию.

Также как и в предыдущем задании, мы начинаем решать задачу с последнего шага. Следует также учитывать, что во всех состояниях, кроме , 0 быть не может. Представим теперь все таблицы решения данной задачи.

Пример задачи:

Таблицы решений:

При решении данной задачи в некоторых таблицах при оценке выбора нужного управления мы получали одинаковые значения F для обоих вариантов управления. В этом случае, в соответствии с алгоритмом решения подобных задач необходимо выбирать управление сохранения оборудования.

Теперь составим матрицу максимальных прибылей за N лет. Для этого, двигаясь в обратном порядке, то есть с конечной таблицы, описывающей начальное год планового периода, к первой, описывающей последний год планового периода, выписываем условно-оптимальные значения целевой функции. В результате получаем таблицу 8. В данной таблице указана граница смены политик («сохранения» или «замены»). Определяя возраст оборудования к началу каждого шага и расчетный год смотрим, в какую область в матрице попадает оборудование и выбираем политику.

Матрица максимальных прибылей:

Задача оптимального управления поставками ресурсов.

Данная задача отсутствует, и поэтому желательно предотвратить её попадание на экзамен.

Транспортная задача. Решение методом потенциалов
(составление начального опорного плана методом северо-западного угла и наименьших стоимостей).

Транспортные модели (задачи) относятся к классу задач ЛП. Эти модели описывают перемещение какого-либо товара из пункта отправления в пункт назначения Назначение транспортных задач – определение объёмов перевозок из пунктов отправки в пункт назначения с минимальной суммарной стоимостью. При этом учитываются ограничения: объем груза, имеющийся в пунктах назначения, и потребность.

В пунктах отправления сосредоточено некоторое число продукта , в пункте объем потребления . Расходы из в равны . Необходимо составить план перевозок, при котором вывоз из в составляет наименьшее число издержек. – количество перевозки.

Если баланс не соблюдается, то ограничение будет иметь вид неравенств.

	Потребители
Поставщики			…
			…
			…
…	…	…	…	…
			…

3 этапа решения.

Этап 1. Составление начального распределения.

Используется метод северо-западного угла. Заключается в том, что всегда в первую очередь заполняется верхняя левая клетка таблицы поставок, затем заполнение идет вправо и вниз при обязательном выполнении условия наличия требуемого объема груза.

	30 (60-30=30)	30 (30-30=0; 100-30=60)
		70 (100-70=30; 60-60=0)	30 (30-30=0; 40-30=10)
			10	110

Метод наименьшей стоимости.

Занесем исходные данные в распределительную таблицу.

Отмечаем клетки с наименьшими стоимостями по каждой строке и столбцу. Клетки с ** заполняются в первую очередь.

Этап 2. Строится система потенциалов. На ее основе проверяется составленный план на оптимальность. В случае его не оптимальности переходим к 3 этапу.

Потенциалами являются специальные показатели и :

Потенциалы рассчитываются таким образом, чтобы для заполнения клетки выполнялось равенство . Значения одного из потенциалов задают произвольно. Для оценки оптимальности для всех клеток определяются оценки , и если среди них нет отрицательных – план оптимален.

Этап 3. Улучшение неоптимального плана перевозок путем реализации циклов перераспределения. Выбирается клетка матрицы перевозок с отрицательной оценкой. Если таких клеток несколько, выбирается клетка с максимальным по модулю из отрицательных оценок. Для данной клетки строится замкнутый контур, начальная вершина которого находится в заполненных клетках. При этом направление отдельных отрезков контура может быть строго горизонтальным или вертикальным. Вершинами контура являются клетки, где отрезки образуют прямой угол.

В вершинах контура поочередно расставляются знаки «+» и «-», начиная со знака «+» в выбранной клетке.

Величина перераспределения поставки определяется как наименьшая из величин поставок в вершинах контура со знаком «-». И эту величину прибавляют к величинам поставок в вершинах со знаком «+», и вычитают из величин поставок в вершинах со знаком «-».

Если величины перераспределения поставки равны поставка не в одной, а в нескольких вершинах контура со знаком «-», то освобождается только одна клетка, обычно с наибольшей стоимостью, а все другие такие клетки остаются занятыми нулевой поставкой.

Выберем, что , рассчитаем по формулам остальные значения потенциалов.

						-7
						-11

Рассчитаем :

Поиск по сайту: