Programowanie liniowe: Różnice pomiędzy wersjami
m (Infobox update) |
(LinkTitles.) |
||
| Linia 15: | Linia 15: | ||
'''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. | '''[[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.<ref> Pająk E. (2006), ''Zarządzanie produkcją'', Wydawnictwo Naukowe PWN, Warszawa</ref> | 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.<ref> Pająk E. (2006), ''[[Zarządzanie produkcją]]'', Wydawnictwo Naukowe PWN, Warszawa</ref> | ||
==Budowanie modelu matematycznego== | ==Budowanie modelu matematycznego== | ||
| Linia 34: | Linia 34: | ||
* następnie należy znaleźć funkcję celu, która będzie posiadać minimum jeden punkt wspólny z ze zbiorem rozwiązań dopuszczalnych | * 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.<ref>[https://notendur.hi.is/kth93/3.20.pdf Introduction to linear programming] Hillier, Lieberman ''Introduction to operations research''</ref> | W ten sposób ustalimy odpowiednią [[wartość]] funkcji celu, którą możemy wykorzystać do podjęcia decyzji.<ref>[https://notendur.hi.is/kth93/3.20.pdf Introduction to linear programming] Hillier, Lieberman ''Introduction to operations research''</ref> | ||
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: | 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: | ||
| Linia 42: | Linia 42: | ||
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. | 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== | ==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ść|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 [[plan|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. | 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ść|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 [[plan|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 === | === Problem mieszanek === | ||
Zagadnienia tego typu wymagają znalezienia optymalnej ilości materiałów potrzebnych do stworzenia końcowego produktu. | Zagadnienia tego typu wymagają znalezienia optymalnej ilości materiałów potrzebnych do stworzenia końcowego produktu. | ||
Wersja z 05:41, 21 maj 2020
| Programowanie liniowe |
|---|
| Polecane artykuły |
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.[1]
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.[2]
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.[3]
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[4]
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.[5]
Przypisy
- ↑ Pająk E. (2006), Zarządzanie produkcją, Wydawnictwo Naukowe PWN, Warszawa
- ↑ Wojda A. P. (2013), Wykłady z programowania liniowego, Wydział Matematyki Stosowanej AGH, Kraków
- ↑ Introduction to linear programming Hillier, Lieberman Introduction to operations research
- ↑ Solving Linear Programs
- ↑ Zastosowanie programowania liniowego w zagadnieniach wspomagania procesu podejmowania decyzji.
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
