Решение матричных игр С помощью линейного программирования в среде Excel

1.Освоить алгоритм перехода от задачи теории игр к задаче линейного программирования;

2. Получить навык решения матричных игр с помощью линейного программирования в среде EXCEL.

Решение матричной игры сведением к задаче линейного программирования в среде Excel

-3
-1

 

 

 

Среди элементов матрицы есть отрицательные

.

 

Введем переменные для игрока , для игрока .

 

 

ПЗЛП для игрока 1:

 

 

ДЗЛП для игрока 2:

 

Таблица - Решение ПЗЛП в среде Excel

 

0,176471		1,235294
	1,31E-17	1,705882
	0,058824
	0,117647
		1,31E-17
		0,058824
		0,117647

 

Таблица – Решение ДЗЛП в среде Excel   0,176471   1,54E-33 0,411765   0,058824 0,823529         0,117647       1,54E-33     0,058824           0,117647

 

 

Переход к решению исходной игры.

Проверка: Произведение двух векторов и матрицы, взятое в заданном порядке, равно цене игры:

 

Ответ:

 

Обоснование распределения финансовых ресурсов между проектами.

На инвестирование трех проектов выделено В млн. руб. Известна эффективность капитальных вложений x_i в каждый j -й проект, заданная таблично значением нелинейной функции f_j (x_i), где , , n – количество проектов, m – количество возможных сумм капитальных вложений.

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

 

Исходные данные варианта 0:

 

Объем капиталовложений xi (тыс. руб.)	Прирост выпуска продукции fj (xi) в зависимости от объема капиталовложений (тыс. руб.)
проект 1	проект 2	проект 3

 

Математическая модель задачи.

Определить х ^* = (, , …, , …, ), обеспечивающий максимум целевой функции

и удовлетворяющий условиям

,

Математическая модель задачи варианта 0:

при ограничениях:

,

.

Условная оптимизация.

Максимально возможный доход, который может быть получен с проектов (с k -го по n -й), определяется с помощью функции Беллмана:

,

где С_k – количество средств, инвестируемых в k -е проект, 0≤ С_k ≤ В.

На первом шаге условной оптимизации при k = n функция Беллмана представляет собой прибыль только с n -го проекта. При этом на его инвестирование может остаться количество средств С_n, 0 ≤ С_n ≤ В. Чтобы получить максимум прибыли с этого проекта, можно вложить в него все эти средства, т.е. F_n (С_n) = f_n (С_n) и х_n = С_n.

Для упрощения расчетов предполагаем, что распределение средств осуществляется в целых числах x_i = {0, 100, 200, 300, 400, 500, 600, 700} тыс. руб.

Решение.

I этап. Условная оптимизация.

1-й шаг: k = 3.

Таблица 1

x 3 C 3									F 3(C 3)

 

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

Предположим, что все средства в количестве x₃ = 700 тыс. руб. отданы третьему проекту. В этом случае максимальный доход составит f ₃(x ₃) = 700 тыс. руб., следовательно: F ₃(C₃) = f ₃(x ₃) и x ₃= C₃.

 

2-й шаг: k = 2. Определяем оптимальную стратегию при распределении денежных средств между вторым и третьим проектами. При этом рекуррентное соотношение Беллмана имеет вид:

.

Представим в таблице расчет функции Беллмана.

Таблица 2

x 2 C 2									F 2(C 2)
	0+0
	0+40	50+0
	0+50	50+40	70+0
	0+80	50+50	70+40	90+0
	0+110	50+80	70+50	90+40	120+0					100/300
	0+150	50+110	70+80	90+50	120+40	160+0				100/400/500
	0+180	50+150	70+110	90+80	120+50	160+40	190+0			100/500
	0+230	50+180	70+150	90+110	120+80	160+50	190+40	220+0		0/600

 

В шапке таблицы отражены варианты значений капиталовложений х₂, которые могут быть предоставлены второму проекту при условии, что часть средств выделяется третьему проекту. В клетках таблицы первое слагаемое – это возможный прирост выпуска продукции при втором проекте f₂ (х₂) в результате освоения капиталовложений х₂; второе слагаемое – значение функции Беллмана, полученной на предыдущем шаге F ₃(C₂ – х₂), т.е. возможный прирост выпуска продукции при третьем проекте, если ему будет выделена оставшаяся часть капиталовложений, определяемая как C₂ – х₂.

Например, рассуждая формально, если при общей величине капиталовложений C₂ = 0 второму проекту выделяется х₂ = 0, то прирост продукции составляет f₂ (0) = 0, а значение функции Беллмана из табл.1 составит: F ₃(0 – 0) = 0. Поэтому в клетке табл. 2 (0, 0) отражается сумма 0+0.

При общей величине капиталовложений C₂ = 100 тыс. руб. возможны уже два варианта распределения средств между вторым и третьим проектами:

1) второму проекту ничего не выделяется, т.е. х₂ = 0 и прирост продукции составляет f₂ (0) = 0. В этом случае значение функции Беллмана из табл. 1 составит F ₃(100 – 0) = F ₃(100) = 40 тыс. руб., т.е. вся сумма C₂ = 100 тыс. руб. выделена третьему проекту, поэтому суммарный прирост продукции составит 0+40, отражаемый в клетке (100, 0).

2) второму проекту может быть выделено х₂ = 100 тыс. руб., прирост продукции при втором проекте составляет f₂ (100) = 50 тыс. руб. В этом случае значение функции Беллмана из табл. 1 составит F ₃(100 – 100) = F ₃(0) = 0, т.е. вся сумма C₂ = 100 тыс. руб. выделена второму проекту, поэтому суммарный прирост продукции составит 50+0, отражаемый в клетке (100, 100).

Рассуждая аналогично, заполняются все строки табл. 2.

Максимальная сумма по каждой строке вносится в колонку F ₂(C ₂), одновременно в колонку вносят соответствующие максимальным суммам значения х₂ из шапки табл. 2.

Например, в строке C₂ = 100 максимальная сумма 160 не единственная, следовательно, F ₂(100) = 50, ему соответствует значение х₂ = 100, следовательно, =100. В строке C₂ = 500 максимальная сумма единственная 50, следовательно, F ₂(500) = 160, ему соответствуют значения х₂ = 100, х₂ = 400, х₂ = 500, следовательно, =100/400/500.

 

3-й шаг: k = 1. Определяем оптимальную стратегию при распределении денежных средств между первым и двумя другими проектами, используя следующую формулу для расчета суммарного дохода:

, на ее основе составлена табл. 3.

В шапке таблицы отражены варианты значений капиталовложений х₁, которые могут быть предоставлены первому проекту при условии, что часть средств выделяется второму и третьему проекту. В клетках таблицы первое слагаемое – это возможный прирост выпуска продукции при первом проекте f₁ (х₁) в результате освоения капиталовложений х₁; второе слагаемое – значение функции Беллмана, полученной на предыдущем шаге F ₂(C₁ – х₁), т.е. возможный прирост выпуска продукции при втором и третьем проектам, если им будет выделена оставшаяся часть капиталовложений, определяемая как C₁ – х₁.

Таблица 3

x 1 C 1									F 1(C 1)
	0+0
	0+50	30+0
	0+90	30+50	50+0
	0+110	30+90	50+50	70+0
	0+130	30+110	50+90	70+50	100+0					100/200
	0+160	30+130	50+110	70+90	100+50	150+0				0/100/200/300
	0+200	30+160	50+130	70+110	100+90	150+50	190+0			100/500
	0+230	30+200	50+160	70+130	100+110	150+90	190+50	210+0		500/600

 

Значение функции Беллмана F ₁(С ₁) представляет собой максимально возможный доход при всех проектах, а значение , на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первый проект.

Значение целевой функции равно максимальному значению функции Беллмана F ₁(С ₁) из табл. 3.

Следовательно, значение целевой функции равно F _max(x^*) = 240 тыс. руб.

II этап. Безусловная оптимизация.

Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина С_k = (С_{k -1} – х_{k -1}) оптимальным управлением на k -м шаге является то значение х_k, которое обеспечивает максимум дохода при соответствующем состоянии системы S_k.

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

Таблица 4.

	F 3(C 3)		F 2(C 2)		F 1(C 1)
				100/300		100/200
				100/400/500		0/100/200/300
				100/500		100/500
				0/600		500/600

 

1-й шаг. По данным из табл. 4 максимальный доход при распределении 700 тыс. руб. между тремя проектами составляет: C ₁ = 700, F ₁(700) = 240 тыс. руб.

При этом возможны следующие варианты.

Первому проекту нужно выделить:

1) = 500 тыс. руб.;

2) = 600 тыс. руб.

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

1) С ₂ = C ₁ – = 700 – 500 = 200 тыс. руб.;

2) С ₂ = C ₁ – = 700 – 600 = 100 тыс. руб.

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

1) 200 тыс. руб. составляет: F ₂(200) = 90 тыс. руб. при выделении второму проекту = 100 тыс. руб.;

2) 100 тыс. руб. составляет: F ₂(100) = 50 тыс. руб. при выделении второму проекту = 100 тыс. руб.

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

1) С ₃ = C ₂ – = 200 – 100 = 100 тыс. руб.;

2) С ₃ = C ₂ – = 200 – 200 = 0.

По данным табл. 4 находим:

1) F ₃(100) = 40 и = 100 тыс. руб.;

2) F ₃(0) = 0 и = 0.

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

1) х ^* = (500, 100, 100), который обеспечит максимальный доход, равный

F (700) = f₁ (500) + f₂ (100) + f₃ (100) = 150 + 50 + 40 = 240 тыс. руб.;

2) х ^** = (600, 100, 0), который обеспечит максимальный доход, равный

F (700) = f₁ (600) + f₂ (100) + f₃ (0) = 190 + 50 + 0 = 240 тыс. руб.

Заключение. Подвести итог о том, что в работе исследовано и что получено.