Programowanie liniowe

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ć:
 
 
 

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

Zmienne  są liczbami rzeczywistymi.

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

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

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:
 

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

Można więc zapisać:
 

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

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

Zminimalizować funkcję celu 
 

przy ograniczeniach
 

gdzie:

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:
 

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

czyli:
 
 

Jeśli na zmienną  nie ma ograniczenia, że musi przyjmować tylko wartości dodatnie, wprowadzamy 2 nowe zmienne  i  i zamieniamy wszystkie wystąpienia tej zmiennej na  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:
 

wprowadzamy nową zmienną  która może przyjmować tylko wartości nieujemne i przekształcamy równanie do postaci:
 
 

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

Zwykle chcemy przepisać te równania do postaci:
 

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.
 
 
 

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 ). 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ż 
 metoda simpleks
 programowanie całkowitoliczbowe
 programowanie matematyczne
 programowanie nieliniowe

Przypisy

Linki zewnętrzne 
 Skrypt dra Łukasza Kowalika z MIMUW
 

 
Układy równań liniowych