Методы решения задач транспортного типа

 

 Точка  безусловного минимума – (7; 14) 

     Метод золотого сечения.

Используем  свойство непрерывной функции: если точки g и h расположены на отрезке [a,b] и значение функции f(a) ≤ g(a), то на [a,b] есть хотя бы один минимум функции. 

x₃, x₅ – a₀,b₀ – (3;10), (15;22)

Δ₀=b-a= (15-3; 22-10) = (12; 12)

λ =

Δ₁=λ₁∙Δ₀= (12; 12) = (11; 11)

Δ₂=Δ₀-Δ₁= (1; 1)

y₀=a₀+Δ₂= (3; 10) + (1; 1) = (4; 11)

z₀=b₀-Δ₂= (15; 22) - (1; 1) = (14; 21)

φ (y₀)=48

φ (z₀)=66 

a₀ = (4; 11), b₀ = (14; 21)

Δ₀= (10; 10)

λ =

Δ₁ = (10; 10) = (9; 9)

Δ₂= (1; 1)

y₀= (5; 12)

z₀= (13; 20)

φ (y₀)=27

φ (z₀)=75 

φ (y₀)> φ (x(²⁾)

φ (z₀)>φ (x(²⁾)

точка (7;14) – min 

    Метод Ньютона

Для решения  берём частные производные по х, не учитывая λ. 

=2x₁+x₂-31 

=x₁+2x₂-38 

=2 

=2 

=1 

=1 

F(x) = () - матрица коэффициентов.

  ОПРЕДЕЛИТЕЛЬ, или детерминант, – в математике запись чисел в виде квадратной таблицы, в соответствие которой ставится другое число («значение» определителя). Определители позволяют удобно записывать сложные выражения, возникающие, например, при решении линейных уравнений в аналитической геометрии и в математическом анализе. 

Δ₁₁=2 

Δ₁₂=-1 

Δ₂₁=1

Δ₂₂=2 

F⁽¹⁾(x)= 

F׳(x) =() 

x⁽¹⁾ = x(⁰⁾-F^-1(x⁽⁰⁾)f(x⁽⁰⁾) 

f(x⁽⁰⁾)= 

x⁽¹⁾ =(0;7)-)()=(0;7)-(-17/3;-38/3)=(;) - получили точку оптимума, в которой целевая функция равна 0. 

    3.5. Метод Нелдора-Мида.

    Рисунок 5. 

 
 
 
 

 

                                                    
 
 
 
 

1. λ=1            

х₁=9,4

х₂=8,4

L=84+84,6=168,6 => произведём сжатие,  λ=0,5

2. х₁=7,7

х₂=6,2

L=77+55,8=132,8

3. х₁=6,5

х₂=5,2

L=65+46,8=111,8

4. х₁=6

х₂=5

L+60+45=105

5. х₁=5,5

х₂=4,5

L=55+40,5=95,5 => заканчиваем итерации. 
 

Задание № 4.

Динамическое  программирование.

Матричные игры.

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

4.2. Свести  игру в матричной постановке  к задаче линейного программирования. Показать, что прямая и двойственная  задачи линейного программирования  соответствуют смешанным стратегиям.

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

- смешанную  стратегию первого игрока как  решение прямой задачи линейного  программирования;

-   смешанную стратегию второго  игрока как решение двойственной  задачи линейного программирования;

- цену  игры как значение целевой  функции указанных задач линейного  программирования.

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

4.1.

  

             α=8 

        β=8 

α=β => седловой точки нет!

4.2.

x₁+x₂+x₃->max

4x₁+6x₂+7x₃≤1

8x₁+9x₂+8x₃≤1

3x₁+5x₂+4x₃≤1 

y₁+y₂+y₃->min

4y₁+8y₂+3y₃≥1

6y₁+9y₂+5y₃≥1

7y₁+8y₂+4y₃≥1 

4.3.

Таблица 47.

 

Таблица 48.

 

Таблица 49.

 

Таблица 50.

 

Х₁=-

Х₂=

Х₃=-

Y₁=

Y₂=

Y₃=-

L= 
 
 
 

Таблица 51.