Programowanie liniowe

Programowanie liniowe
Polecane artykuły
Optymalizacja przewozów Metoda simpleks Zasada racjonalnego gospodarowania Analiza progowa Zasady rozmieszczenia stanowisk pracy Metoda pomiarowa Modele podejmowania decyzji Regeneracja Rachunek ekonomiczny

Programowanie liniowe - metoda służąca osiągnięciu jak najlepszego rozwiązania w procesie podejmowania decyzji (na przykład maksymalizacja zysku, minimalizacja kosztów). Jest to szczególny przypadek programowania matematycznego. Programowanie liniowe jest najczęściej stosowanym modelem optymalizacji ze względu na sprawny algorytm obliczeń, a także dzięki możliwości efektownego przedstawienia zagadnienia podejmowania decyzji w postaci graficznej. Wadą programowania liniowego jest to, iż nie wszystko można wyrazić za pomocą liczb. W działalności gospodarczej dominuje zasada racjonalnego gospodarowania, która zakłada, że zasoby jakimi dysponujemy powinny być w maksymalnym stopniu wykorzystane do realizacji założonego celu. Jeżeli zasoby te można opisać ilościowo stosujemy model matematyczny.

TL;DR

Programowanie liniowe to metoda optymalizacji, która pozwala osiągnąć najlepsze rozwiązanie w procesie podejmowania decyzji. Opiera się na budowaniu modelu matematycznego z funkcją celu, zmiennymi decyzyjnymi i warunkami ograniczającymi. Rozwiązanie problemu można znaleźć za pomocą metody geometrycznej lub sympleksowej. Programowanie liniowe znajduje zastosowanie w różnych dziedzinach, takich jak problem mieszanek czy problem transportowy.

Budowanie modelu matematycznego

Aby zastosować programowanie liniowe w procesie podejmowania decyzji, należy opracować model matematyczny, który będzie zawierał:

• funkcję celu (inaczej funkcja kryterium) jest to najważniejsza część modelu, gdyż obrazuje cel jaki chcemy osiągnąć. Musi to być funkcja liniowa zależna od wszystkich zmiennych decyzyjnych.
• zmienne decyzyjne opisują narzędzia i zasoby jakie mamy w posiadaniu, aby cel osiągnąć. Przyjmują one wartości nieujemne.
• warunki ograniczające są to przeszkody, jakie mogą się pojawić w trakcie realizacji celu. Zapisujemy je w postaci nierówności, których lewe strony są funkcjami liniowymi.

Tak utworzony model jest zadaniem programowania liniowego.

Rozwiązanie

Ważne jest, aby model miał postać liniową, czyli funkcja celu oraz lewe strony warunków ograniczających były funkcjami liniowymi. Rozwiązując problem otrzymujemy dopuszczalne rozwiązania, które będą spełniać warunki ograniczające. Jeżeli nasz model posiada dwie zmienne, łatwo jest go rozwiązać metodą geometryczną w układzie współrzędnych kartezjańskich. W takim przypadku należy:

• po określeniu zbioru rozwiązań dopuszczalnych narysować go w układzie
• następnie należy znaleźć funkcję celu, która będzie posiadać minimum jeden punkt wspólny z ze zbiorem rozwiązań dopuszczalnych

W ten sposób ustalimy odpowiednią wartość funkcji celu, którą możemy wykorzystać do podjęcia decyzji.

Metoda graficzna nie sprawdzi się, jeśli mamy więcej niż dwie zmienne decyzyjne. W tej sytuacji można skorzystać z innego sposobu. Jest to metoda sympleks, którą George Dantzig przedstawił w roku 1947. Metoda ta polega na:

• sprowadzeniu warunków ograniczających (które występują bardzo często w postaci nierówności) do układu równań liniowych, dzięki zastosowaniu tzw. zmiennych bilansowych
• następnie obliczamy zmienne decyzyjne, które przedstawiają najlepszą decyzję dostosowaną do ustalonego modelu

Jeżeli podjęcie decyzji zależy od wielu zmiennych, do obliczeń wykorzystuje się komputer ze specjalnie przygotowanym oprogramowaniem. Ważnym elementem jest także analiza wrażliwości czyli odpowiedź na pytanie w jaki sposób zmieni się wybrany parametr przy niezmienionych pozostałych, tak aby rozwiązanie optymalne pozostało w równowadze.

Zastosowanie

W działalności gospodarczej dąży się do maksymalnego wykorzystania dostępnych środków w procesie realizacji założonego celu. Zasada ta sprowadza się do zagadnień optymalizacji oraz zasady największej efektywności. Jeżeli z określonych środków osiągany jest maksymalny nakład lub określony cel jest zrealizowany przy jak najmniejszych nakładach, możemy mówić o planie optymalnym. Związane jest to ze znajomością metod programowania matematycznego, do których zalicza się programowanie liniowe. Za jego pomocą można rozwiązać różne modele zadań, których rozwiązanie w inny sposób byłoby mniej efektywne.

Problem mieszanek

Zagadnienia tego typu wymagają znalezienia optymalnej ilości materiałów potrzebnych do stworzenia końcowego produktu.

Problem transportowy

Rozwiązanie tego typu problemów wymaga znalezienia takiej drogi od dostawcy towaru do odbiorcy, aby poniesione koszta były jak najmniejsze. Trzeba brać pod uwagę wiele aspektów związanych z transportem takich jak rozmieszczenie poszczególnych obiektów czy znalezienie najkrótszej drogi między nimi.

Bibliografia

• Borowczyk K. (2011), ExploreLP – tutorial, Instytut Informatyki, Politechnika Poznańska
• Cegielski A. (2002), Programowanie matematyczne, Wydawnictwo Uniwersytetu Zielonogórskiego, Zielona Góra
• Ignasiak E.(2000), Badania operacyjne, Polskie Wydawnictwo Ekonomiczne
• Józefowska J. (2012), Badania operacyjne i teoria optymalizacji, Wydawnictwo Politechniki Poznańskiej, Poznań
• Pająk E. (2006), Zarządzanie produkcją, Wydawnictwo Naukowe PWN, Warszawa
• Roughgarden T. (2016), Linear Programming: Introduction and Applications, Stanford University, USA
• Wojda A. P. (2013), Wykłady z programowania liniowego, Wydział Matematyki Stosowanej AGH, Kraków

Autor: Ewa Wierciak, Arkadiusz Bugajski