Содержание
СОДЕРЖАНИЕ КУРСОВОГО ПРОЕКТА
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Базисh27391820000
x1x2x3x4x5x6x7
0x51402165100
0x6900304010
0x71983240001
z0-z0-z-27-39-18-20000
0x511020611/31 -1/30
39×2300104/301/30
0x7138304 -8/30 -2/31
z0-z1170-z-270-18320130
0x5180010/349/911/9-2/3
39×2300104/301/30
27×146104/3-8/90-2/91/3
z0-z2412-z00188079
Для первой симплекс таблицы
и
.
Для второй симплекс таблицы
и
Как видно из последней симплексной таблицы, оптимальной является производственная программа 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):
Выдержка из текста
Иными словами, при второй игрок будет выбирать свою вторую стратегию и первый игрок будет выигрывать , при второй игрок будет выбирать первую стратегию и первый игрок будет выигрывать . Наилучший для первого игрока выбор при этом соответствует . В нашем случае оптимальной смешанной стратегией первого игрока является стратегия:
(она определяется из условия ), при этом цена игры равна
.
Отметим, что второй игрок, действуя разумно, никогда не будет выбирать третью и четвертую стратегии, поэтому вектор оптимальной смешанной стратегии второго игрока имеет вид:
.
Тогда выигрыш второго игрока равен , если первый игрок выбирает свою первую стратегию, и , если первый игрок выбирает свою вторую стратегию. Значение определяется из условия
, оно равно .
Итак, оптимальная смешанная стратегия второго игрока равна:
.
Найдем оптимальные смешанные стратегии с помощью сведения матричной игры к паре взаимно двойственных задач линейного программирования.
От платежной матрицы П путем добавления положительного числа перейдем к матрице :
все элементы которой положительны.
Пара двойственных задач линейного программирования будет такой:
Оптимальные решения этих задач равны:
и
Оптимальные смешанные стратегии игроков
и
а цена игры
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.