Алгоритм решения задач динамического программирования.

Определяем все состояния системы при переходе из начального состояния в конечное состояние . На каждом шаге целевые функции имеют вид: и определено уравнение состояния: Из уравнения Беллмана для по находим оптимальное управление на ом шаге По и определяем состояние системы после го шага: Из уравнения Беллмана для находим оптимальное управление на ом шаге По и определяем состояние системы после го шага: и так далее. Условно этот процесс можно представить в виде:

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

 

Размер инвестиций	Доходность проектов
1-ый проект	2-ой проект	3-ий проект	4-ый проект

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

Объёмы вложений

С учётом постановки данную задачу динамического программирования можно разбить на 4 этапа. Каждый этап характеризуется выбором инвестиций в какой то конкретный проект при учёте оптимальных вложений на предыдущих шагах. Математически подобная процедура пошагового выбора имеет вид:

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

 

 

Значения функции находим, используя рекуррентное соотношение 2):

1.

2.

3.

4.

5.

6.

7.

Сведём полученные данные для функции в таблицу

Аналогично, используя рекуррентные соотношения 3) и 4) соответственно, находим значения функций . Запишем данные в таблицу

Максимум целевой функции , равный 28, складывается из расчета:

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

млн. руб.; млн. руб.; млн. руб.

Контрольное задание №4

Предприятие планирует открыть филиалы в Михайловке, Урюпинске и Котельниково, для чего выделяются средства в размере 5 млн. руб.

По расчетам экономистов, каждый филиал при инвестировании в него х тыс. руб. приносит прибыль φ _i(х) тыс.руб. Эти данные приведены в таблице.

Необходимо выбрать оптимальное распределение выделенных средств между филиалами, обеспечивающее максимальную прибыльность всего проекта.

Вариант 1

Вложенные средства (x млн.руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ 1(х)	φ 2(х)	φ 3(х)
	1, 10	1, 40	1, 50
	1, 20	1, 45	2, 20
	1, 30	1, 55	2, 50
	1, 40	1, 60	3, 00
	1, 50	1, 65	3, 10

Вариант 2

Вложенные средства (x млн.руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ 1(х)	φ 2(х)	φ 3(х)
	0, 50	0, 40	0, 20
	0, 60	0, 45	0, 40
	0, 80	0, 55	0, 50
	0, 90	0, 60	0, 70
	1, 00	0, 65	0, 90

Вариант 3

Вложенные средства (x млн.руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ 1(х)	φ 2(х)	φ 3(х)
	0, 35	0, 50	0, 20
	0, 45	0, 90	0, 40
	0, 50	1, 00	0, 50
	0, 55	1, 10	0, 70
	0, 60	1, 25	0, 90

Вариант 4

Вложенные средства (x млн.руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ 1(х)	φ 2(х)	φ 3(х)
	0, 15	0, 20	0, 10
	0, 30	0, 40	0, 40
	0, 45	0, 60	0, 70
	0, 60	0, 80	0, 75
	0, 75	1, 00	0, 90

Вариант 5

Вложенные средства (x млн.руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ 1(х)	φ 2(х)	φ 3(х)
	0, 50	0, 40	0, 60
	1, 00	0, 65	0, 80
	1, 50	0, 80	1, 00
	2, 00	0, 90	1, 20
	2, 50	1, 50	1, 30

Вариант 6

Вложенные средства (x млн.руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ 1(х)	φ 2(х)	φ 3(х)
	1, 50	1, 40	2, 00
	3, 00	3, 50	3, 10
	4, 50	4, 50	4, 60
	6, 00	5, 50	6, 20
	6, 50	7, 00	6, 50

Вариант 7

Вложенные средства (x млн.руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ 1(х)	φ 2(х)	φ 3(х)
	1, 40	1, 10	1, 50
	3, 50	2, 10	2, 00
	3, 70	3, 10	2, 50
	4, 00	4, 10	3, 00
	4, 20	5, 10	3, 50

Вариант 8

Вложенные средства (x млн.руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ 1(х)	φ 2(х)	φ 3(х)
	0, 20	0, 20	0, 25
	0, 25	0, 30	0, 35
	0, 45	0, 50	0, 55
	0, 55	0, 65	0, 60
	0, 75	0, 70	0, 65

Вариант 9

Вложенные средства (x млн.руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ 1(х)	φ 2(х)	φ 3(х)
	1, 50	2, 20	2, 10
	2, 50	3, 10	3, 20
	3, 20	3, 90	4, 00
	4, 10	4, 20	4, 50
	4, 90	4, 50	5, 10

Вариант 10

Вложенные средства (x млн.руб.)	Филиал
Михайловка	Урюпинск	Котельниково
φ 1(х)	φ 2(х)	φ 3(х)
	1, 50	2, 00	1, 50
	2, 30	2, 30	2, 90
	2, 50	2, 80	3, 10
	3, 40	3, 50	3, 90
	3, 60	3, 90	4, 50

 

Тема 5. Элементы теории игр

 

На практике часто встречаются ситуации, когда приходится принимать решение в условиях конфликта интересов нескольких участников события. Такие ситуации возникают, например, в карточных играх, шахматах и т.п. В экономике конфликтные ситуации возникают при взаимодействии покупателя и продавца, банка и клиента, поставщика и потребителя и т.д. Особенностью подобных ситуаций является неопределенность, вызванная неизвестным заранее поведением участников конфликта, которые стремятся добиться максимальной реализации своих целей. Математическим описанием конфликтных ситуаций теория игр. Её целью является выработка рекомендаций по разумному поведению участников конфликта.

 

Основные понятия и общая классификация игр

 

Всякая математическая модель социально-экономического явления или конфликта должна выражать присущие ему черты, т.е. по крайней мере, отражать следующие его компоненты:

а) заинтересованность сторон;

б) возможные действия каждой из сторон;

в) интересы сторон.

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

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

Любое возможное для игрока действие называется его стратегией.

Множество всех стратегий игрока обозначим через . В условиях конфликта каждый игрок выбирает некоторую свою стратегию в результате чего складывается набор стратегий называемый ситуацией. Множество всех ситуаций обозначим .

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

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

(1)

Определение Игрой называется действительный или формальный конфликт, в котором имеется, по крайней мере, два игрока, каждый из которых стремится к достижению собственных целей.

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

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

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

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

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

Для сокращения обозначений, множества стратегий игроков 1 и 2 антагонистической игре будем обозначать через и , а функция выигрыша - через

Для антагонистических игр с двумя игроками вводится следующее определение.

Определение Пусть каждой стратегии 1-го игрока взаимнооднозначно поставлена в соответствие строка некоторой матрицы , а каждой стратегии 2-го игрока взаимнооднозначно поставлен в соответствие столбец этой матрицы. Матрицу называют платежной матрицей (или матрицей игры), если её элемент равен выигрышу 1-го игрока (т.е. проигрышу 2-го) при выборе 1-м игроком -й стратегии, а 2-м - -й.

Следовательно, антагонистическая игра полностью описывается единственной платёжной матрицей и в соответствии с этим называется матричной.

Пример. Швейное предприятие планирует к массовому выпуску новую модель одежды. Спрос на эту модель не может быть точно определен. Однако можно предположить, что его величина характеризуется тремя возможными состояниями (I, II, III). С учетом этих состояний анализируются три возможных варианта выпуска данной модели . Каждый из этих вариантов требует своих затрат и обеспечивает в конечном счете различный эффект. Прибыль (тыс. р.), которую получает предприятие при данном объеме выпуска модели и соответствующем состоянии спроса, определяется матрицей

Выбор в том или ином смысле наилучшего варианта выпуска моделей можно понимать как матричную игру.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. E) тело, размерами которого можно пренебречь в условиях данной задачи
2. I. ОСНОВНЫЕ ЗАДАЧИ ВНЕШНЕЙ ПОЛИТИКИ
3. II. Основные цели и задачи Совета
4. II. Цели и задачи выпускной квалификационной работы
5. II. Цели и задачи настоящей Концепции
6. III. Задачи, определяемые возрастом воспитанников
7. III. Решение логических задач с помощью рассуждений
8. PR – отношения с общественностью. Цели, задачи, функции, методы
9. Авторитарно-ориентированный менеджер, который прежде всего концентрирует свое внимание на решении производственных задач.
10. Адлер выделил три основные жизненные цели (задачи): работу, дружбу и любовь.
11. Активное использование речевых средств и средств информационно- коммуникационных технологий (далее – ИКТ) для решения коммуникативных и познавательных задач.
12. Алгоритм введения желудочного зонда через рот