Линейная производственная задача.

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

(она определяется из условия ), при этом цена игры равна
.
Отметим, что второй игрок, действуя разумно, никогда не будет выбирать третью и четвертую стратегии, поэтому вектор оптимальной смешанной стратегии второго игрока имеет вид:
.
Тогда выигрыш второго игрока равен , если первый игрок выбирает свою первую стратегию, и , если первый игрок выбирает свою вторую стратегию. Значение определяется из условия
, оно равно .
Итак, оптимальная смешанная стратегия второго игрока равна:
.
Найдем оптимальные смешанные стратегии с помощью сведения матричной игры к паре взаимно двойственных задач линейного программирования.
От платежной матрицы П путем добавления положительного числа перейдем к матрице :

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

Оптимальные решения этих задач равны:
и
Оптимальные смешанные стратегии игроков
и
а цена игры


15. Биматричная игра. Каждое из двух конкурирующих предприятий имеет по две стратегии рыночного поведения. Прибыли предприятий (в млн. руб.) при условии, что первое предприятие изберет стратегию i(i = 1, 2), а второе предприятие стратегию j (j = 1, 2), равны соответственно aij и bij. Платежные матрицы П(1) =(aij) и П(2) =(bij):

Требуется найти максиминные стратегии предприятий и равновесие по Нэшу в смешанных стратегиях.
Решение
Смешанные стратегии предприятий можно представить в виде:

(здесь ). При этом, математические ожидания предприятий равны соответственно:

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

Таким образом, максиминные стратегии первого и второго предприятий равны соответственно:

Множество всех возможных пар выигрышей предприятий четырехугольником АBСD (рис.15.1)

Рис.15.1
Очевидно, множество Парето, как и переговорное множество соответствует отрезку ВС.
Прямая, проходящая через точки В(2;1) и С(1;8) задается уравнением
,
поэтому функция Нэша

на отрезке достигает максимума в точке . При этом . Эта точка на рисунке 15.1 обозначена .
Точка является выпуклой комбинацией точек В(2;1) и С(1;8), то есть

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

При этом средний выигрыш первого предприятия равен , а второго -


16. Оптимальный портфель ценных бумаг. Определить, с каким наименьшим риском можно достичь 20%-ной эффективности инвестиций, если есть возможность банковских вложений и заимствований по ставке i, а на рынке ценных бумаг обращаются две акции, их ожидаемые эффективности равны соответственно r1 и r2, риски и, , а коэффициент корреляции доходностей данных акций равен .

Решение
Введем данные в рабочий лист Micrisoft Excel (рис.16.1). Пусть ячейки В9 и В10 соответствуют долям рисковых вложений , в ячейку В8, соответствующую доле безрисковых вложений , введем формулу соответствующую разности всех вложений (единицы) и вложений в акции , в ячейку В12 ведем формулу для ожидаемой эффективности портфеля МЕπ, а в ячейку В13 введем формулу для дисперсии эффективности портфеля DЕπ. Учтем, что .

Рис.16.1
Воспользуемся инструментом «Поиск решения». Для этого выберем в меню «Сервис» пункт «Поиск решения», и в появившемся окне (рис.16.2) укажем, что мы хотим установить целевую ячейку $B$14(в которой рассчитывается дисперсия портфеля) равной минимальному значению, изменяя ячейки $В$10:$B$11 (в которых находятся доли рисковых составляющих портфеля), причем в задаче присутствует ограничение $В$13:$B$7.

СОДЕРЖАНИЕ КУРСОВОГО ПРОЕКТА

1. Линейная производственная задача. 3
2. Задача о расшивке узких мест производства 12
3. Целочисленная задача о расшивке узких мест производства 15
4. Транспортная задача линейного программирования 15
5. Нелинейное программирование 22
9. Задача о кратчайшем пути 48
10. Задача о критическом пути 50
11 Оптимальность по Парето 53
12 Многокритериальная оптимизация 54
13. Принятие решений в условиях неопределенности 57
14. Матричная игра 59
15. Биматричная игра 62
16. Оптимальный портфель ценных бумаг 64
17. Рациональная стоимость опционов 67



1. Линейная производственная задача. Предприятие может выпус¬кать четыре вида продукции, используя для этого три вида ресурсов. Известны технологическая матрица

затрат ресурсов на производство единицы каждого вида продукции [эле¬мент aij этой матрицы равен количеству ресурса i-го вида (i = 1, 2, 3), ко¬торое необходимо затратить в процессе производства единицы продук¬ции j-го вида (j = 1, 2, 3, 4)], вектор

объемов ресурсов и вектор

удельной прибыли на единицу продукции.
Требуется составить производственную программу, обеспечивающую предприятию наибольшую прибыль с учетом ограниченности запасов ре¬сурсов.
Для этого необходимо обсудить экономическое содержание линейной производственной задачи и сформулировать ее математическую модель, преобразовать данную задачу к виду основной задачи линейного про¬граммирования, решить ее симплексным методом, обосновывая каждый шаг вычислительного процесса, найти оптимальную производственную программу, максимальную прибыль, остатки ресурсов различных видов и определить узкие места производства (дефицитные ресурсы).
Затем требуется сформулировать задачу, двойственную линейной производственной задаче, обсудить ее экономическое содержание и запи¬сать математическую модель, после чего найти решение двойственной задачи, пользуясь второй основной теоремой двойственности, обосновав экономический смысл этой теоремы.
Указать оптимальную производственную программу и оценки техноло¬гий, максимальную прибыль и минимальную суммарную оценку всех ре¬сурсов, остатки и двойственные оценки ресурсов и обсудить экономиче¬ский смысл всех этих величин.
После этого необходимо с помощью надстройки «Поиск решения», паке¬та Microsoft Excel, проверить правильность решения задачи и, кроме того, определить границы, в которых могут изменяться коэффициенты целе¬вой функции, в пределах которых не изменяется ассортимент выпускае¬мой продукции, и границы, в которых могут изменяться правые части ог¬раничений, в пределах которых сохраняется устойчивость двойственных оценок.
Решение
Математическая модель задачи такова. Требуется найти про¬изводственную программу

максимизирующую прибыль

при ограничениях по ресурсам

где по смыслу задачи

Получили задачу на условный экстремум. Для ее решения систему не¬равенств при помощи дополнительных неотрицательных неизвестных x5, x6,x7 заменим системой линейных алгебраических уравнений

в которой дополнительные переменные x 5, x 6 и x7 имеют смысл остатков ресурсов (соответственно первого, второго и третьего вида). Среди всех реше¬ний системы уравнений, удовлетворяющих условиям неотрицательности , нужно найти то решение, при котором целевая функция примет наи¬большее значение.
Воспользуемся тем, что правые части всех уравнений системы неотри¬цательны, а сама система имеет предпочитаемый вид дополнительные переменные являются базисными. Поэтому можно применить симплекс¬ный метод. Процесс решения записан в виде последовательности сим¬плексных таблиц (табл. 1).
Таблица 1.1
c Базис h 27 39 18 20 0 0 0
x1 x2 x3 x4 x5 x6 x7
0 x5 140 2 1 6 5 1 0 0
0 x6 90 0 3 0 4 0 1 0
0 x7 198 3 2 4 0 0 0 1
z0-z 0-z -27 -39 -18 -20 0 0 0
0 x5 110 2 0 6 11/3 1 -1/3 0
39 x2 30 0 1 0 4/3 0 1/3 0
0 x7 138 3 0 4 -8/3 0 -2/3 1
z0-z 1170-z -27 0 -18 32 0 13 0
0 x5 18 0 0 10/3 49/9 1 1/9 -2/3
39 x2 30 0 1 0 4/3 0 1/3 0
27 x1 46 1 0 4/3 -8/9 0 -2/9 1/3
z0-z 2412-z 0 0 18 8 0 7 9

Для первой симплекс таблицы

и
.
Для второй симплекс таблицы
и
Как видно из последней симплексной таблицы, оптимальной является производственная программа x1 = 46; x2 = 30; x3 = 0; x4 = 0, обеспечивающая предприятию наибольшую прибыль zmax = 2412; при этом остаток ресурса первого вида x5 = 18, второго вида x6 = 0, третьего вида x7 = 0.
Оценочные коэффициенты ∆1, ∆, ∆3 и ∆4 имеют смысл оценок технологий и показывают, насколько уменьшится прибыль, если произвести единицу соотетствующей продукции. Напри¬мер, коэффициент ∆3 = 18 при переменной x3 показывает, что если произ¬вести одну единицу продукции третьего вида (она не входит в оптималь¬ную производственную программу), то прибыль уменьшится на 18 единиц.
Оставшиеся коэффициенты ∆5, ∆6 и ∆7 имеют смысл двойственных оце-нок ресурсов и показывают, насколько возрастет прибыль, если первона¬чальные запасы соответствующего ресурса увеличить на единицу. Так, увеличение на единицу запаса второго ресурса приведет к увеличению прибыли на ∆ = 7 единиц.
Двойственные оценки представляют собой оптимальное решение зада¬чи, двойственной к исходной задаче планирования производства: это такие внутренние цены y 1, y 2, y 3 , что суммарная внутренняя стоимость всех имеющихся ресурсов минимальна при условии, что внут¬ренняя стоимость ресурсов, из которых можно изготовить единицу про¬дукции каждого вида, не меньше той цены, по которой единицу соответ¬ствующей продукции можно продать на рынке.
Для производства единицы продукции первого вида мы должны затра¬тить, как видно из матрицы A, 2 единицы ресурса первого вида, 0 едини¬ц ресурса второго вида и 3 единицы третьего (элементы первого столбца матрицы). В ценах y1,y2,y3 наши затраты составят 2y 1 +0y2 +3y3. При реа¬лизации единицы первой продукции на рынке мы получили бы прибыль
27 руб. Следовательно, внутренняя оценка стоимости ресурсов, из кото¬рых можно изготовить единицу первого продукта (2y1 +0y2 +3y3), должна составлять не менее 27 руб. Аналогичные условия должны выполняться и для всех остальных видов продукции.
При этом суммарная оценка всех имеющихся ресурсов 140y1 +90y2 +198y3 должна быть минимальной.
Окончательно двойственная задача формулируется так: требуется найти вектор двойственных оценок

минимизирующий общую оценку всех ресурсов

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

при чем оценки ресурсов не могут быть отрицательными:

Запишем вторую основную теорему двойственности для этой задачи:

И подставим в эти уравнения уже известную оптимальную производственную программу x1 = 46; x2 = 30; x3 = 0; x4 = 0:

Первое из этих уравнений означает, что поскольку первый ресурс используется не полностью (при выполнении оптимальной производственной программы расходуется 122 единицы из 140), его двойственная оценка .
Итак,

Решив систему уравнений, получим окончательно, что
Теперь получим решение этой же задачи в пакете Microsoft Excel. Вве¬дем исходные данные в рабочий лист Microsoft Excel. Введем исходные данные (Рис.1.1):

нет