- •§1. Постановка задачи.....................................................................46
- •§1. Основные понятия..................................................................61.
- •§1. Основные понятия.................................................................81
- •§1 Основные понятия.
- •§ 2 Классификация моделей
- •§ 3 Классификация решаемых экономических задач.
- •Классификация решаемых экономических задач.
- •Глава 2. Линейное программирование
- •§ 1 Общая постановка задачи
- •§ 2 Двойственность в задачах линейного программирования
- •Правила построения двойственной задачи по имеемой прямой задаче:
- •§ 3 Теоремы двойственности.
- •§4 Решение задач линейного программирования геометрическим методом
- •Алгоритм геометрического метода решения задач лп.
- •Рассмотрим задачу.
- •§ 5 Симплексный метод решения задач лп
- •Глава 3. Транспортная задача
- •§ 1 Постановка задачи.
- •§ 2 Алгоритм решения транспортных задач.
- •Метод наименьшего элемента.
- •Метод потенциалов.
- •§ 3 Примеры решения транспортных задач.
- •1.Проверяем задачу на сбалансированность.
- •Составляем математическую модель прямой и двойственной задач.
- •Решаем задачу по методу максимального элемента.
- •Глава 4 . Целочисленное программирование
- •§ 1 Постановка задачи целочисленного программирования.
- •§ 2 Графический метод решения задач целочисленного программирования.
- •Алгоритм графического решения задачи целочисленного программирования.
- •§ 3 Пример решения задачи целочисленного программирования.
- •Контрольные вопросы.
- •Глава 5 . Динамическое программирование
- •§1. Постановка задачи.
- •§2. Принцип оптимальности Беллмана.
- •§3. Задача распределения средств на 1 год
- •§4. Задача распределения средств на два года
- •Глава 6 . Управление производством.
- •§ 1 Управление производством.
- •§ 2 Управление запасами .Складская задача.
- •Глава 7. Теория игр.
- •§1 Основные понятия.
- •§2 Антагонистические игры.
- •Геометрический способ решения антагонистических игр
- •§3 Игры с « природой».
- •Пример №1
- •2. Критерий Гурвица.
- •3. Критерий Сэвиджа (критерий минимаксного риска).
- •4. Критерий Лапласа. N
- •Пример №2
- •Глава 8. Системы массового обслуживания
- •§I. Формулировка задачи и характеристики смо
- •§2 Смо с отказами
- •2.1 Основные понятия
- •2.2 Формулы для расчета установившегося режима
- •§3 Смо с неограниченным ожиданием
- •3.1 Основные понятия
- •3.2 Формулы для расчета установившегося режима
- •§4 Смо с ожиданием и с ограниченной длиной очереди
- •4.1 Основные понятия
- •4.2Формулы для установившегося режима
- •§5 Примеры решения задач.
- •Глава 9 нелинейное програмирование.
- •§1 Основные понятия.
- •§2 Математическая модель задачи.
- •§3 Безусловный экстремум
- •§4 Условный экстремум
- •Глава 10 . Сетевое планирование.
- •§1 Основные понятия метода сетевого планирования
- •Работа, события, путь.
- •Любая работа соединяет только 2 события.
- •§2 Расчет сетевых графиков
- •Содержание практических занятий
- •Рекомендуемая литература:
§2. Принцип оптимальности Беллмана.
Основным методом динамического программирования является метод рекуррентных соотношений; который основывается на использовании принципа оптимальности, разработанного американским математиком Р.Беллманом.
Суть принципа:
Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться ОПТИМАЛЬНЫМИ относительно состояния, к которому придет система в конце каждого шага.
Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.
Условная оптимизация
Безусловная оптимизация
Si – состояние системы на i-м шаге. Основная рекуррентная формула динамического программирования в случае решения задачи максимизации имеет вид:
, где максимум в данной формуле берется по всем возможным решениям в ситуации, когда система на шаге m находится в состоянии i.
Величина fm(i) – есть максимальная прибыль завершения задачи из состояния i, если предположить, что на шаге m, система находится в состоянии i.
Максимальная прибыль может быть получена максимизацией суммы прибылей самого шага m и максимальной прибыли шага (m+1) и далее, чтобы дойти до конца задачи.
Планируя многошаговую операцию надо выбирать управление на каждом шаге с учетом всех его будущих последствий на ещё предстоящих шагах.
Управление на i-м шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимальным, а так, чтобы была максимальна сумма выигрышей на всех оставшихся шагах плюс данный шаг.
Среди всех шагов последний шаг планируется без оглядки на будущее, т.е. чтобы он сам, как таковой принес наибольшую выгоду.
Задача динамического программирования начинает решаться с конца, т.е. с последнего шага. Решается задача в 2 этапа:
1 этап (от конца к началу по шагам): Проводится условная оптимизация, в результате чего находится условные оптимальные управления и условные оптимальные выигрыши по всем шагам процесса.
2 этап (от начала к концу по шагам): Выбираются (прочитываются) уже готовые рекомендации от 1-го шага до последнего и находится безусловное оптимальное управление х*, равный х*1, х*2, …, х*m.
§3. Задача распределения средств на 1 год
Пример: имеется запас средств, который нужно распределить между предприятиями, чтобы получить наибольшую прибыль. Пусть начальный капитал S0=100 д.ед. Функции дохода предприятий даны в матрице прибылей по каждому предприятию.
Х |
1 предприятие f (х1) |
2 предприятие f (х2) |
3 предприятие f (х3) |
4 предприятие f (х4) |
20 |
3 |
2 |
3 |
3 |
40 |
4 |
5 |
4 |
6 |
60 |
9 |
8 |
9 |
8 |
80 |
11 |
7 |
5 |
7 |
100 |
12 |
15 |
12 |
14 |
Решение: математическая модель прямой задачи:
Задача решается с использованием принципа Беллмана.
Экономический смысл переменных:
xi – количество денег, вкладываемых в i предприятие.
Si – количество денег, оставшихся после вложения в i-предприятие (состояние системы на i-шаге);
F(xi) – прибыль от вложенной суммы денег;
S0 – начальный капитал.
Рассмотрим 4 шаг:
На 4-ом предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 100 д.ед.Тогда прибыль от вложения денег можно получить следующую.
S3 |
Х4 |
f (x4) |
F4 |
0 |
0 |
0 |
0 |
20 |
20 |
3 |
3 |
40 |
40 |
6 |
6 |
60 |
60 |
8 |
8 |
80 |
80 |
7 |
7 |
100 |
100 |
14 |
14 |
Рассмотрим 3-й шаг.
На 3-ем и 4-ем предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 100 д.ед. Рассмотрим первую возможность. Если 3-му предприятию мы выдаем 20 д.ед. то 4-му предприятию ничего не остается, и наоборот. Соответственно 40 д.ед.можно поделить так (0;40), (20;20);
60 д.ед. – (0;60), (20;40), (40;20), (60;0).
Прибыль от вложения денег в 3-е предприятие берется в исходной матрице прибылей, а прибыль от вложений, денег в 4-е предприятие берется из таблицы предыдущего шага
Прибыль на 3-м шаге берется максимальной по каждому вложению.
Вклад |
Проект |
Остаток |
Прибыль из матрицы |
Прибыль за шаг |
|
Прибыль на шаге |
S2 |
Х3 |
S3 |
f (x3) |
F4 |
f+F |
F3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
20 |
0 |
20 |
0 |
3 |
3 |
3 |
20 |
0 |
3 |
0 |
3 |
||
40 |
0 |
40 |
0 |
6 |
6 |
6 |
20 |
20 |
3 |
3 |
6 |
||
40 |
0 |
4 |
0 |
4 |
||
60 |
0 |
60 |
0 |
8 |
8 |
9 |
20 |
40 |
3 |
6 |
9 |
||
40 |
20 |
4 |
3 |
7 |
||
60 |
0 |
9 |
0 |
9 |
||
80 |
0 |
80 |
0 |
7 |
7 |
12 |
20 |
60 |
3 |
8 |
11 |
||
40 |
40 |
4 |
6 |
10 |
||
60 |
20 |
9 |
3 |
12 |
||
80 |
0 |
5 |
0 |
5 |
||
100 |
0 |
100 |
0 |
14 |
14 |
15 |
20 |
80 |
3 |
7 |
10 |
||
40 |
60 |
4 |
8 |
12 |
||
60 |
40 |
9 |
6 |
15 |
||
80 |
20 |
5 |
3 |
8 |
||
100 |
0 |
12 |
0 |
12 |
Рассмотрим 2 шаг.
Вклад |
Проект |
Остаток |
Прибыль из матрицы |
Прибыль за шаг |
|
Прибыль на шаге |
S1 |
Х2 |
S2 |
f (x2) |
F3 |
f+F |
F2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
20 |
0 |
20 |
0 |
3 |
3 |
3 |
20 |
0 |
2 |
0 |
2 |
||
40 |
0 |
40 |
0 |
6 |
6 |
6 |
20 |
20 |
2 |
3 |
5 |
||
40 |
0 |
5 |
0 |
5 |
||
60 |
0 |
60 |
0 |
9 |
9 |
9 |
20 |
40 |
2 |
6 |
8 |
||
40 |
20 |
5 |
3 |
8 |
||
60 |
0 |
8 |
0 |
8 |
||
80 |
0 |
80 |
0 |
12 |
12 |
12 |
20 |
60 |
2 |
9 |
11 |
||
40 |
40 |
5 |
6 |
11 |
||
60 |
20 |
8 |
3 |
11 |
||
80 |
0 |
7 |
0 |
7 |
||
100 |
0 |
100 |
0 |
15 |
15 |
15 |
20 |
80 |
2 |
12 |
14 |
||
40 |
60 |
5 |
9 |
14 |
||
60 |
40 |
8 |
6 |
14 |
||
80 |
20 |
7 |
3 |
10 |
||
100 |
0 |
15 |
0 |
15 |
Рассмотрим 1 шаг.
Вклад |
Проект |
Остаток |
Прибыль из матрицы |
Прибыль за шаг |
|
Прибыль на шаге |
S1 |
Х2 |
S2 |
f (x2) |
F3 |
f+F |
F2 |
100 |
0 |
100 |
0 |
15 |
15 |
15 |
20 |
80 |
3 |
12 |
15 |
||
40 |
60 |
4 |
9 |
13 |
||
60 |
40 |
9 |
6 |
15 |
||
80 |
20 |
11 |
3 |
14 |
||
100 |
0 |
12 |
0 |
12 |
Анализ результатов:
Максимальная прибыль равна 15 д.ед. Расположить денежные средства между проектами можно несколькими способами:
-
1 проект – 0 д.ед., 2 проект – 0 д.ед., 3 проект – 60 д.ед., 4 проект – 40 д.ед.
-
1 проект – 0 д.ед., 2 проект – 100 д.ед., 3 проект – 0 д.ед., 4 проект – 0 д.ед.
-
1 проект – 20 д.ед., 2 проект – 0 д.ед., 3 проект – 60 д.ед., 4 проект – 20 д.ед.
-
1 проект – 60 д.ед., 2 проект – 0 д.ед., 3 проект – 20 д.ед., 4 проект – 20 д.ед.
-
1 проект – 60 д.ед., 2 проект – 0 д.ед., 3 проект – 0 д.ед., 4 проект – 40 д.ед.