Programowanie liniowe: Różnice pomiędzy wersjami
m (→Bibliografia: Clean up, replaced: ,Pr → , Pr) |
mNie podano opisu zmian |
||
| (Nie pokazano 11 wersji utworzonych przez 2 użytkowników) | |||
| Linia 1: | Linia 1: | ||
'''[[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 | 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)</ref> | ||
==TL;DR== | ==TL;DR== | ||
| Linia 21: | Linia 6: | ||
==Budowanie modelu matematycznego== | ==Budowanie modelu matematycznego== | ||
Aby zastosować programowanie liniowe w procesie podejmowania decyzji, należy opracować model matematyczny, który będzie zawierał: | 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. | * '''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. | ||
| Linia 29: | Linia 13: | ||
Tak utworzony model jest ''zadaniem programowania liniowego''.<ref> Wojda A. P. (2013)</ref> | Tak utworzony model jest ''zadaniem programowania liniowego''.<ref> Wojda A. P. (2013)</ref> | ||
==Rozwiązanie== | ==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: | 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 | * po określeniu zbioru rozwiązań dopuszczalnych narysować go w układzie | ||
| Linia 43: | Linia 25: | ||
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. | ||
<google>n</google> | |||
==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. | ||
=== Problem transportowy=== | ===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 | 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<ref>Zastosowanie programowania liniowego w zagadnieniach wspomagania procesu podejmowania decyzji.</ref> | ||
{{infobox5|list1={{i5link|a=[[Optymalizacja przewozów]]}} — {{i5link|a=[[Metoda simpleks]]}} — {{i5link|a=[[Zasada racjonalnego gospodarowania]]}} — {{i5link|a=[[Analiza progowa]]}} — {{i5link|a=[[Zasady rozmieszczenia stanowisk pracy]]}} — {{i5link|a=[[Metoda pomiarowa]]}} — {{i5link|a=[[Modele podejmowania decyzji]]}} — {{i5link|a=[[Regeneracja]]}} — {{i5link|a=[[Rachunek ekonomiczny]]}} }} | |||
==Przypisy== | ==Przypisy== | ||
| Linia 56: | Linia 44: | ||
==Bibliografia== | ==Bibliografia== | ||
<noautolinks> | <noautolinks> | ||
* Cegielski A. (2002), ''Programowanie matematyczne'', Wydawnictwo Uniwersytetu Zielonogórskiego, Zielona Góra | |||
* Cegielski A. (2002), Programowanie matematyczne, Wydawnictwo Uniwersytetu Zielonogórskiego, Zielona Góra | * Ignasiak E. (2000), ''Badania operacyjne'', Polskie Wydawnictwo Ekonomiczne, Warszawa | ||
* Ignasiak E.(2000), ''Badania operacyjne'', Polskie Wydawnictwo Ekonomiczne | |||
* Józefowska J. (2012), ''Badania operacyjne i teoria optymalizacji'', Wydawnictwo Politechniki Poznańskiej, Poznań | * Józefowska J. (2012), ''Badania operacyjne i teoria optymalizacji'', Wydawnictwo Politechniki Poznańskiej, Poznań | ||
* Pająk E. ( | * Pająk E. (2013), ''Zarządzanie produkcją. Produkt, technologia, organizacja'', Wydawnictwo Naukowe PWN, Warszawa | ||
* Roughgarden T. (2016), [https://theory.stanford.edu/~tim/w16/l/l7.pdf Linear Programming: Introduction and Applications], Stanford University, USA | * Roughgarden T. (2016), ''[https://theory.stanford.edu/~tim/w16/l/l7.pdf Linear Programming: Introduction and Applications]'', Stanford University, USA | ||
* Wojda | * Wojda P. (2013), ''[https://wms.mat.agh.edu.pl/~wojda/Pl3.pdf Wykłady z programowanie liniowego]'', Wydział Matematyki Stosowanej AGH, Kraków | ||
</noautolinks> | </noautolinks> | ||
Aktualna wersja na dzień 09:28, 11 sty 2024
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]
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.[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.
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[3]
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[4]
| Programowanie liniowe — artykuły polecane |
| Optymalizacja przewozów — Metoda simpleks — Zasada racjonalnego gospodarowania — Analiza progowa — Zasady rozmieszczenia stanowisk pracy — Metoda pomiarowa — Modele podejmowania decyzji — Regeneracja — Rachunek ekonomiczny |
Przypisy
- ↑ Pająk E. (2006)
- ↑ Wojda A. P. (2013)
- ↑ Solving Linear Programs
- ↑ Zastosowanie programowania liniowego w zagadnieniach wspomagania procesu podejmowania decyzji.
Bibliografia
- Cegielski A. (2002), Programowanie matematyczne, Wydawnictwo Uniwersytetu Zielonogórskiego, Zielona Góra
- Ignasiak E. (2000), Badania operacyjne, Polskie Wydawnictwo Ekonomiczne, Warszawa
- Józefowska J. (2012), Badania operacyjne i teoria optymalizacji, Wydawnictwo Politechniki Poznańskiej, Poznań
- Pająk E. (2013), Zarządzanie produkcją. Produkt, technologia, organizacja, Wydawnictwo Naukowe PWN, Warszawa
- Roughgarden T. (2016), Linear Programming: Introduction and Applications, Stanford University, USA
- Wojda P. (2013), Wykłady z programowanie liniowego, Wydział Matematyki Stosowanej AGH, Kraków
Autor: Ewa Wierciak, Arkadiusz Bugajski
