Programowanie liniowe

Wygląd przypnij ukryj

Programowanie liniowe – klasa problemów programowania matematycznego, w której wszystkie warunki ograniczające oraz funkcja celu mają postać liniową. Warunki ograniczające mają postać:

a 1 x 1 + a 2 x 2 + … + a n x n ⩾ α , {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\geqslant \alpha ,}

a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\geqslant \alpha ,

a 1 x 1 + a 2 x 2 + … + a n x n ⩽ α , {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\leqslant \alpha ,}

a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\leqslant \alpha ,

a 1 x 1 + a 2 x 2 + … + a n x n = α . {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}=\alpha .}

a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}=\alpha .

Mamy zmaksymalizować lub zminimalizować funkcję celu, również liniową:

f = α + c 1 x 1 + c 2 x 2 + … + c n x n . {\displaystyle f=\alpha +c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}.}

f=\alpha +c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}.

Zmienne x i {\displaystyle x_{i}} $x_{i}$ są liczbami rzeczywistymi.

Nie zawsze taki problem ma jakiekolwiek rozwiązanie, np.:

x 1 ⩾ 2 , {\displaystyle x_{1}\geqslant 2,}

x_{1}\geqslant 2,

x 1 ⩽ 1. {\displaystyle x_{1}\leqslant 1.}

x_{1}\leqslant 1.

Być może też żadne rozwiązanie nie jest optymalne, ponieważ potrafimy uzyskać dowolnie dużą wartość funkcji celu, np.:

Zmaksymalizuj f = x 1 {\displaystyle f=x_{1}}

f=x_{1}

przy warunku x 1 ⩾ 10. {\displaystyle x_{1}\geqslant 10.}

x_{1}\geqslant 10.

Programowanie liniowe znalazło szerokie zastosowanie w teorii decyzji, np. do optymalizacji planu produkcyjnego. Wiele problemów optymalizacyjnych znajduje rozwiązanie poprzez sprowadzenie ich do postaci problemu programowania liniowego.

Postać standardowa

Postać standardowa to taka, w której funkcja celu ma być minimalizowana. Występują tylko warunki postaci:

a 1 x 1 + a 2 x 2 + … a n x n ⩽ α {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\leqslant \alpha }

a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\leqslant \alpha

oraz na każdą zmienną nałożony jest warunek:

x i ⩾ 0. {\displaystyle x_{i}\geqslant 0.}

x_{i}\geqslant 0.

Można więc zapisać:

a 11 x 1 + a 12 x 2 + … a 1 n x n ⩽ b 1 , a 21 x 1 + a 22 x 2 + … a 2 n x n ⩽ b 2 , … a m 1 x 1 + a m 2 x 2 + … a m n x n ⩽ b m , x 1 , x 2 , … , x n ⩾ 0 , {\displaystyle {\begin{array}{l}a_{11}x_{1}+a_{12}x_{2}+\ldots a_{1n}x_{n}\leqslant b_{1},\\a_{21}x_{1}+a_{22}x_{2}+\ldots a_{2n}x_{n}\leqslant b_{2},\\\ldots \\a_{m1}x_{1}+a_{m2}x_{2}+\ldots a_{mn}x_{n}\leqslant b_{m},\\x_{1},x_{2},\dots ,x_{n}\geqslant 0,\end{array}}}

{\begin{array}{l}a_{11}x_{1}+a_{12}x_{2}+\ldots a_{1n}x_{n}\leqslant b_{1},\\a_{21}x_{1}+a_{22}x_{2}+\ldots a_{2n}x_{n}\leqslant b_{2},\\\ldots \\a_{m1}x_{1}+a_{m2}x_{2}+\ldots a_{mn}x_{n}\leqslant b_{m},\\x_{1},x_{2},\dots ,x_{n}\geqslant 0,\end{array}}

czyli ograniczenia w postaci standardowej można w sposób ogólny zapisać bardziej zwięźle:

∑ j = 1 n a i j x j ⩽ b i dla i = 1 , … , m , x j ⩾ 0 dla j = 1 , … , n . {\displaystyle {\begin{aligned}\sum _{j=1}^{n}a_{ij}x_{j}&\leqslant b_{i}&\quad {\textrm {dla}}\quad i&=1,\dots ,m,\\x_{j}&\geqslant 0&\quad {\textrm {dla}}\quad j&=1,\dots ,n.\end{aligned}}}

{\begin{aligned}\sum _{j=1}^{n}a_{ij}x_{j}&\leqslant b_{i}&\quad {\textrm {dla}}\quad i&=1,\dots ,m,\\x_{j}&\geqslant 0&\quad {\textrm {dla}}\quad j&=1,\dots ,n.\end{aligned}}

Jeszcze zwięźlej ujmuje się to zagadnienie w postaci macierzowej:

Zminimalizować funkcję celu z ( x ) {\displaystyle z(\mathbf {x} )} $z(\mathbf {x} )$

z ( x ) = c T x {\displaystyle z(\mathbf {x} )=\mathbf {c} ^{T}\mathbf {x} }

z(\mathbf {x} )=\mathbf {c} ^{T}\mathbf {x}

przy ograniczeniach

A x ⩽ b , x ⩾ Θ , {\displaystyle {\begin{aligned}\mathbf {A} \mathbf {x} \leqslant \mathbf {b} ,\\\mathbf {x} \geqslant \Theta ,\end{aligned}}}

{\begin{aligned}\mathbf {A} \mathbf {x} \leqslant \mathbf {b} ,\\\mathbf {x} \geqslant \Theta ,\end{aligned}}

gdzie:

c = ( c j ) j = 1 , … , n ∈ R n , b = ( b i ) i = 1 , … , m ∈ R m , x = ( x i ) i = 1 , … , n ∈ R n , Θ = ( 0 , … , 0 ) ∈ R n A = ( a i j ) i = 1 , … , m ; j = 1 , … , n ∈ R m × n . {\displaystyle {\begin{aligned}\mathbf {c} &=(c_{j})_{j=1,\dots ,n}\in \mathbb {R} ^{n},\\\mathbf {b} &=(b_{i})_{i=1,\dots ,m}\in \mathbb {R} ^{m},\\\mathbf {x} &=(x_{i})_{i=1,\dots ,n}\in \mathbb {R} ^{n},\\\Theta &=(0,\dots ,0)\in \mathbb {R} ^{n}\\\mathbf {A} &=(a_{ij})_{i=1,\dots ,m;j=1,\dots ,n}\in \mathbb {R} ^{m\times n}.\end{aligned}}}

{\begin{aligned}\mathbf {c} &=(c_{j})_{j=1,\dots ,n}\in \mathbb {R} ^{n},\\\mathbf {b} &=(b_{i})_{i=1,\dots ,m}\in \mathbb {R} ^{m},\\\mathbf {x} &=(x_{i})_{i=1,\dots ,n}\in \mathbb {R} ^{n},\\\Theta &=(0,\dots ,0)\in \mathbb {R} ^{n}\\\mathbf {A} &=(a_{ij})_{i=1,\dots ,m;j=1,\dots ,n}\in \mathbb {R} ^{m\times n}.\end{aligned}}

Sprowadzanie do postaci standardowej

Żeby przekształcić problem do postaci standardowej, zamiany maksymalizacji na minimalizacje oraz warunków mniejsze-równe na większe-równe, dokonuje się przez zamianę znaków przy współczynnikach. Jeśli mamy warunek:

a 1 x 1 + a 2 x 2 + … a n x n = α , {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}=\alpha ,}

a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}=\alpha ,

to jest on równoważny parze warunków:

a 1 x 1 + a 2 x 2 + … a n x n ⩾ α , {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\geqslant \alpha ,}

a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\geqslant \alpha ,

a 1 x 1 + a 2 x 2 + … a n x n ⩽ α , {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\leqslant \alpha ,}

a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\leqslant \alpha ,

czyli:

a 1 x 1 + a 2 x 2 + … a n x n ⩾ α , {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\geqslant \alpha ,}

a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\geqslant \alpha ,

− a 1 x 1 + − a 2 x 2 − … a n x n ⩾ − α . {\displaystyle -a_{1}x_{1}+-a_{2}x_{2}-\ldots a_{n}x_{n}\geqslant -\alpha .}

-a_{1}x_{1}+-a_{2}x_{2}-\ldots a_{n}x_{n}\geqslant -\alpha .

Jeśli na zmienną x i {\displaystyle x_{i}} $x_{i}$ nie ma ograniczenia, że musi przyjmować tylko wartości dodatnie, wprowadzamy 2 nowe zmienne x i ′ {\displaystyle x_{i}'} $x_{i}'$ i x i ″ {\displaystyle x_{i}''} $x_{i}''$ i zamieniamy wszystkie wystąpienia tej zmiennej na x i ′ − x i ″ . {\displaystyle x_{i}'-x_{i}''.} $x_{i}'-x_{i}''.$ Na obie nowe zmienne możemy już nałożyć ograniczenie, że są one nieujemne.

Postać równościowa

Postać równościowa (kanoniczna) to taka, w której funkcja celu ma być zmaksymalizowana, wszystkie warunki są równościami, a na wszystkie zmienne nakłada się warunek, że są nieujemne.

Żeby pozbyć się nierówności:

a 1 x 1 + a 2 x 2 + … a n x n ⩾ α , {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\geqslant \alpha ,}

a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\geqslant \alpha ,

wprowadzamy nową zmienną s , {\displaystyle s,} $s,$ która może przyjmować tylko wartości nieujemne i przekształcamy równanie do postaci:

a 1 x 1 + a 2 x 2 + … a n x n = α + s , {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}=\alpha +s,}

a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}=\alpha +s,

a 1 x 1 + a 2 x 2 + … a n x n − s = α {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}-s=\alpha }

a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}-s=\alpha

i analogicznie dla mniejsze-równe, z odwróconym znakiem.

Zwykle chcemy przepisać te równania do postaci:

x i = α i + ∑ j = 1 n c i j x j {\displaystyle x_{i}=\alpha _{i}+\sum _{j=1}^{n}c_{ij}x_{j}}

x_{i}=\alpha _{i}+\sum _{j=1}^{n}c_{ij}x_{j}

tak, że zmienne występujące po lewej stronie równań nie występują nigdzie indziej (ani po prawej stronie równań, ani w funkcji celu).

Z układem takim wiąże się rozwiązanie podstawowe – takie, w którym wszystkie zmienne oprócz lewostronnych mają przypisaną wartość zero, natomiast wszystkie lewostronne oraz funkcja celu mają wartość równą wartości odpowiednich stałych.

f = 2 − x 1 + x 2 , {\displaystyle f=2-x_{1}+x_{2},}

f=2-x_{1}+x_{2},

x 4 = 5 + 2 x 2 − x 3 , {\displaystyle x_{4}=5+2x_{2}-x_{3},}

x_{4}=5+2x_{2}-x_{3},

x 5 = − 2 − x 1 + 1 2 x 3 . {\displaystyle x_{5}=-2-x_{1}+{\frac {1}{2}}x_{3}.}

x_{5}=-2-x_{1}+{\frac {1}{2}}x_{3}.

Rozwiązaniem podstawowym tego układu jest (0, 0, 0, 5, −2), i wartością funkcji celu jest 2.

Rozwiązanie podstawowe nie zawsze musi spełniać wszystkie warunki nieujemności (w tym przypadku niespełniony jest warunek na x 5 {\displaystyle x_{5}} $x_{5}$ ). Przekształcenie równania, które zachowuje zbiór prawidłowych rozwiązań może zmieniać nam rozwiązanie podstawowe – taka jest zresztą idea podstawowego algorytmu programowania liniowego, algorytmu sympleksu.

Zobacz też

Przypisy

↑ programowanie liniowe, Encyklopedia PWN .

Linki zewnętrzne

Kontrola autorytatywna (convex optimization):

Encyklopedie internetowe:

Britannica: topic/linear-programming-mathematics, topic/linear-programming-education