Programowanie liniowe

F(x) = c₁x₁+c₂x₂ + ... + c_nx_n (MAX) - funkcja celu

a₁₁x₁ + a₁₂x₂ + .... + a_1nx_n ≤ b_1,

a₂₁x₁ + a₂₂x₂ + .... + a_2nx_n ≤ b_2,

...............................................

a_m1x₁ + a_m2x₂ + ....+ a_mnx_n ≤ b_m,

x₁ , x₂ , … , x_n ≥ 0

F(x) = c^Tx (max)

Ograniczenia: Ax ≤ b, x ≥ 0

a₁₁x₁ + a₁₂x₂ + .... + a_1nx_n +z₁ = b_1,

a₂₁x₁ + a₂₂x₂ + .... + a_2nx_n + z₂ = b_2,

...............................................

a_m1x₁ + a_m2x₂ + ....+ a_mnx_n + z_m = b_m,

x₁ , x₂ , … , x_n ≥ 0

z₁ , z₂ , … , z_m ≥ 0

I =(na przekątnej 1 a zera pozostałe elementy)

o wymiarze m x m

[A|I]
= b

Rozwiązania bazowe to rozwiązania, w których zmienne swobodne są przyjęte jako 0.

Tych rozwiązań jest maksymalnie

(n+m)!/[(r!(m+n-r)!],

gdzie r = rząd [A|I]=m.

Wśród rozwiązań bazowych wybieramy dopuszczalne (≥ 0),

i dla nich analizujemy wartość funkcji celu aby znaleźć rozwiązanie zapewniające jej wartość maksymalną

Jedno z nich zapewnia optymalną wartość funkcji celu.

Może się zdarzyć, że więcej niż jedno rozwiązanie zapewnia optymalną wartość funkcji celu.

Na przykład n=3, m=2, r=2, liczba rozw.=10.

x1+2x3+3z1-z2 = 10

x2 +3x3+z1+2z2 =5

(10,5,0,0,0)

(0,25,0,0,-10) -niedopuszczalne

ROZWIĄZANIE UKŁADU RÓWNAŃ

METODĄ NAJMNIEJSZYCH KWADRATÓW

Ax = b

Ax - b = 0

Ax - b = MIN ?

|| Ax - b|| = MI N

Minimalizacja długości wektora

A^TAx = A^Tb

A^TA=B, c=A^Tb

Bx = c