Ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver

αi = min hij V1 = max αii
-3    
-1

ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru

βj = max hij
V2 = min βii

1≤V(H) ≤3

С помощью доминирования игра свелась к игре размерности [3х2]

Среди элементов матрицы есть отрицательные → t=│min hij│+1

t=│-1│+1=2

Ht = H+t

Ht = ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru

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

min [ f0 (х)=х1+х2+х3]

Х c R

R={Х ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru

X≥0

R=X

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

max [ g0(y)=y1+y2]

Q= ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru

y≥0

    Хб ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru   ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru
Xсв УСВ Уб   -Y1 -Y2 Cj
ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru Y3      
ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru Y4      
ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru Y5      
ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru g0(y)   - 1   - 1  

Обратный переход:

С помощью программы Simplex Solver получено решение

Х= (0;0,09;0,18;0;0),

Y=(0,09;0,18;0;0;0).

g0(y*)=f0(x*)=0,27

V(H)=1/f0(x*)=1/g0(y*)=1/0,27=3,7

V(H)=V(Ht)t-t=3,704-2=1,704

X*=X*V(H)t

Y*=Y*V(Ht)t

X1=0*3,704=0

X2=0,09*3,704=1/3

X3=0,18*3,704=2/3

Y1=0,09*3,704=1/3

Y2=0,18*3,704=2/3

Ответ: X* = (0;0,09;0,18;0;0), Y* = (0,09;0,18;0;0;0),V(H) = 5/3, V(H)=1,7.

Задание №3

Разбор ситуации об инвестировании предприятий и освоение методики обоснования решения об инвестировании предприятия.

Задача:

На развитие трех предприятий выделено 5 млн. руб. Известна эффективность капитальных вложений в каждое предприятие, заданная значением нелинейной функции gi(xi), представленной в табл. 1

Таблица 1

x g1 g2 g3
2,2 2,8
3,2 5,4
4,1 4,8 6,4
5,2 6,2 6,6
5,9 6,4 6,9

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

Для упрощения расчетов предполагаем, что распределение средств осуществляется в целых числах xi = {0, 1, 2, 3, 4, 5} млн. руб.

Решение.

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

1-й шаг: k = 3. Предположим, что все средства в количестве x3 = 5 млн. руб. отданы третьему предприятию. В этом случае максимальный доход, как это видно из табл. 2, составит g3(x3) = 6,9 тыс. руб., следовательно: F3(C3) = g3(x3).

Таблица 2

x3 C3 F3(C3) ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru
         
  2,8         2,8
    5,4       5,4
      6,4     6,4
        6,6   6,6
          6,9 6,9

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

ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru ,

на основе которого составлена табл. 3.

Таблица 3

х2 С2 F2(C2) ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru
0 + 0          
0 + 2,8 2 + 0         2,8
0 + 5,4 2 + 2,8 3,2 + 0       5,4
0 + 6,4 2 + 5,4 3,2 + 2,8 4,8 + 0     7,4
0 + 6,6 2 + 6,4 3,2 + 5,4 4,8 + 2,8 6,2 + 0   8,6
0 + 6,9 2 + 6,6 3,2 + 6,4 4,8 + 5,4 6,2 + 2,8 6,4 + 0 10,2

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

ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru ,

на основе которого составлена табл. 4.

Таблица 4

х1 С1 F1(C1) ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru
0 + 0          
0 + 2,8 2,2 + 0         2,8
0 + 5,4 2,2 + 2,8 3 + 0       5,4
0 + 7,4 2,2 + 5,4 3 + 2,8 4,1 + 0     7,6
0 + 8,6 2,2 + 7,4 3 + 5,4 4,1 + 2,8 5,2 +0   9,6
0 + 10,2 2,2 + 8,6 3 + 7,4 4,1 + 5,4 5,2 + 2,8 5,9 + 0 10,8

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

Определяем компоненты оптимальной стратегии.

1-й шаг. По данным из табл. 4 максимальный доход при распределении 5 млн. руб. между тремя предприятиями составляет: C1 = 5, F1(5) = 10,8.

При этом первому предприятию нужно выделить ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru = 1 млн руб.

2-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего предприятий: С2 = C1ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru = 5 – 1 = 4 млн руб.

По данным табл. 3 находим, что оптимальный вариант распределения денежных средств размером 4 млн. руб. между вторым и третьим предприятиями составляет: F2(4) = 8,6 при выделении второму предприятию ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru = 2 млн руб.

3-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю третьего предприятия: С3 = C2ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru = 4 – 2 = 2 млн руб.

По данным табл. 2 находим: F3(2) = 5,4 и ешение матричной игры сведением к задаче линейного программирования с помощью программы Simplex Solver - student2.ru = 2 млн руб.

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

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

F(5) = g1(l) + g2(2) + g3(2) = 2,2 + 3,2 + 5,4 = 10,8 млн руб.

Наши рекомендации