Programowanie liniowe

0
222
Programowanie liniowe

Dziedzina wiedzy, która się zajmuje optymalizacją wielu danych to tak zwane programowanie liniowe.

Programowanie liniowe

Dlaczego liniowe? Wszak dlatego, że wszystkie warunki, które mamy możemy spisać w postaci równań bądź nierówności liniowych. Zarówno funkcja celu, jak i ograniczenia mają postać liniową. Funkcję celu optymalizujemy, czyli szukamy jej minimum lub maksimum, a ograniczenia wypisujemy w formie równań bądź nierówności.

Programowanie linioweW ekonomii przykładem optymalizacji, gdzie wykorzystuje się programowanie liniowe jest maksymalizacja zysku (bądź minimalizacja kosztów).

Załóżmy, że produkt a kosztuje 10zł, produkt b 20zł, a produkt c 30zł. W magazynie mieści się 700 metrów sześciennych różnych produktów. Możemy jeszcze założyć, że objętość produktu b jest 1,5 raza, a produktu c 3 razy większa niż produktu a. Możemy zdefiniować więc zmienne: objętość produktów a to x, objętość produktów b to y, a objętość produktów c to z (w jednostkach metr sześcienny).

Mamy więc ograniczenia:

x + y + z =< 700, y = 1,5x, z = 3x (znak „=<” oznacza mniejsze bądź równe)
Zysk wynosi 10x + 20y + 30z i ma być jak największy.

Powyższy problem jest trywialny, ale ma tylko zobrazować jak wygląda podstawowy problem programowania liniowego.

Najpopularniejszym algorytmem rozwiązującym tego typu problemy jest algorytm symplex, wprowadzający tak zwane zmienne dodatkowe i iterujący funkcje celu do najbardziej optymalnego rozwiązania. Implementacja odbywa się z wykorzystaniem tabeli. Żeby algorytm się nie zaciął (a tak może się zdarzyć!) konieczne jest stosowanie tak zwanej reguły Blanda, określającej które elementy powinno się wybierać jako zmienne wchodzące, a które jako wychodzące.

To tak pokrótce o tym, że w ogóle istnieje algorytm możliwy do implementacji. Warto wiedzieć ponadto, że w programowaniu liniowym rozwiązanie optymalne zawsze jest tylko jedno.

Reasumując, dowiedzieliśmy się na czym polega programowanie liniowe, kiedy się je stosuje oraz, że istnieje algorytm rozwiązujący takie problemy w formie jedynego możliwego rozwiązania.

[Głosów:1    Średnia:5/5]

ZOSTAW ODPOWIEDŹ

Please enter your comment!
Please enter your name here