Programowanie liniowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 xi 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[edytuj]

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:

Zmaksymalizować funkcję celu

przy ograniczeniach

gdzie:

Sprowadzanie do postaci standardowej[edytuj]

Ż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 zamiane 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[edytuj]

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ż[edytuj]

Linki zewnętrzne[edytuj]