Programowanie liniowe


Programowanie liniowe w encyklopedii

Z Wikipedii, wolnej encyklopedii To jest najnowsza wersja przejrzana, która została oznaczona 13 mar 2019. Od tego czasu wykonano 1 zmianę, która oczekuje na przejrzenie. Przejdź do nawigacji Przejdź do wyszukiwania

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}+\cdots +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}+\cdots +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}+\cdots +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}+\cdots +c_{n}x_{n}.}

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

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

x 1 2 , {\displaystyle x_{1}\geqslant 2,} x 1 1. {\displaystyle 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}} przy warunku x 1 10. {\displaystyle 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.

Spis treści

Postać standardowa | edytuj kod

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}+\cdots a_{n}x_{n}\leqslant \alpha }

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

x i 0. {\displaystyle 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}+\cdots a_{1n}x_{n}\leqslant b_{1},\\a_{21}x_{1}+a_{22}x_{2}+\cdots a_{2n}x_{n}\leqslant b_{2},\\\dots \\a_{m1}x_{1}+a_{m2}x_{2}+\cdots a_{mn}x_{n}\leqslant b_{m},\\[.7em]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}}}

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

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

z ( x ) = c T x {\displaystyle 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}}}

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}}}

Sprowadzanie do postaci standardowej | edytuj kod

Ż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}+\cdots 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}+\cdots 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}+\cdots 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}+\cdots 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}-\cdots a_{n}x_{n}\geqslant -\alpha .}

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

Postać równościowa | edytuj kod

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}+\cdots a_{n}x_{n}\geqslant \alpha ,}

wprowadzamy nową zmienną s , {\displaystyle 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}+\cdots 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}+\cdots 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}}

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},} x 4 = 5 + 2 x 2 x 3 , {\displaystyle 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}.}

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}} ). 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ż | edytuj kod

Linki zewnętrzne | edytuj kod

Kontrola autorytatywna (convex optimization):
Na podstawie artykułu: "Programowanie liniowe" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy