Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00274 005315 13077619 na godz. na dobę w sumie
Badania operacyjne z wykorzytsaniem WinQSB - ebook/pdf
Badania operacyjne z wykorzytsaniem WinQSB - ebook/pdf
Autor: Liczba stron: 243
Wydawca: C. H. Beck Język publikacji: polski
ISBN: 978-8-3255-6075-1 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> aplikacje biurowe >> excel
Porównaj ceny (książka, ebook, audiobook).

W pracy przedstawiono wybrane zagadnienia badań operacyjnych, dotyczących problemów decyzyjnych w obszarze zarządzania przedsiębiorstwem, ekonomiki i organizacji produkcji. Są to:

- programowanie liniowe,

- zagadnienia transportowe,

- modele gospodarki zapasami,

- gry decyzyjne i analiza decyzji,

- łańcuchy Markowa.

Każde z prezentowanych zagadnień zawiera krótki wykład teoretyczny oraz przynajmniej jeden przykład numeryczny w postaci zadania, które jest rozwiązane z wykorzystaniem dostępnego w trybie open source oprogramowania WinQSB. Poszczególne kroki dochodzenia do rozwiązania zostały zilustrowane licznymi zrzutami z ekranu przygotowanymi przez Autora.

Książka adresowana jest do studentów kierunków ekonomicznych, praktyków zajmujących się zawodowo problematyką zarządzania operacyjnego, a także słuchaczy studiów podyplomowych w zakresie badań operacyjnych oraz metod ilościowych w zarządzaniu i ekonomii.

(...) recenzowana pozycja wyróżnia się w stosunku do podobnych, dostępnych na rynku wydawniczym publikacji tym, że przedstawione w niej zagadnienia z zakresu badań operacyjnych zostały nie tylko opisane i zilustrowane przejrzyście, ale również zaprezentowano sposób ich rozwiązania z wykorzystaniem istniejącego szeroko dostępnego oprogramowania open source - WinQSB. Stanowi to nowość na polskim rynku wydawniczym.

Dr hab. Kazimierz Waćkowski, prof. PW

Wydział Inżynierii Produkcji

Politechnika Warszawska

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

Badania Badania operacyjne operacyjne z wykorzystaniem z wykorzystaniem WinQSB WinQSB Dariusz Siudak WinQSB_str 7/25/14 3:17 PM Page 1 Badania operacyjne z wykorzystaniem WinQSB WinQSB_str 7/25/14 3:17 PM Page 2 WinQSB_str 7/25/14 3:17 PM Page 3 Badania operacyjne z wykorzystaniem WinQSB Dariusz Siudak WYDAWNICTWO C.H.BECK WARSZAWA 2014 Wydawca: Dorota Ostrowska-Furmanek Redakcja merytoryczna: Danuta Kamińska-Hass Recenzent: dr hab. Kazimierz Waćkowski, prof. PW Projekt okładki i stron tytułowych: Maryna Wiśniewska Ilustracja na okładce: c(cid:13) Mark Evans/iStockphoto.com Seria: Metody ilościowe Publikacja dofinansowana przez Zakład Ekonomii Instytutu Nauk Społecznych i Zarządzania Technologiami Politechniki Łódzkiej Złożono programem TEX c(cid:13) Wydawnictwo C.H.Beck 2014 Wydawnictwo C.H.Beck Sp. z o.o. ul. Bonifraterska 17, 00-203 Warszawa Skład i łamanie: Wydawnictwo C.H.Beck Druk i oprawa: Totem, Inowrocław ISBN 978-83-255-6074-4 e-book 978-83-255-6075-1 Spis treści . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wykaz stosowanych skrótów . 7 . . . . . . . . . . . . . . . . . Wstęp . 8 . . . . . . . . . . . . . . . . . . . . . Rozdział 1. Programowanie liniowe . 11 . . . . . . . . . . . 11 1.1. Modelowanie problemów decyzyjnych . . . . . . . . . . . . . . . . . . . 14 1.2. Rozwiązywanie zadań programowania liniowego metodą geometryczną . . . 33 1.3. Rozwiązywanie zadań programowania liniowego metodą simpleks . . . . . 85 1.4. Rozwiązywanie zadań programowania liniowego całkowitoliczbowego . . . Rozdział 2. Zagadnienia transportowe . 98 . . . . . . 2.1. Sformułowanie i własności zadań transportowych . . . . . . . . . . . . . . 98 2.2. Metody wyznaczania rozwiązań wstępnych . . . . . . . . . . . . . . . . . . 101 2.3. Poszukiwanie rozwiązania optymalnego metodą potencjałów . . . . . . . . 101 . . . . . . . . . . . . . . . . . 103 2.4. Zbilansowane zadanie transportowe . . . . . . . . . . . . . . . . . . . 112 2.5. Niezbilansowane zadanie transportowe . 2.6. Zadanie transportowe z trasami niedopuszczalnymi . . . . . . . . . . . . . 118 . . . . . . . . . . . . . . . . . . 124 2.7. Modelowanie sieciowe . . 2.7.1. Zadanie najkrótszej ścieżki . . . . . . . . . . . . . . . . . . 124 2.7.2. Zadanie maksymalnego przepływu . . . . . . . . . . . . . . . . . . 131 Rozdział 3. Modele gospodarowania zapasami . . 140 . . . . . . . . . . . . . . . . . . 140 . 3.1. Uwagi ogólne . . . . . . . . . . . . . . . . . . . . 141 . 3.2. Model Wilsona . . 3.3. Model z uwzględnieniem rabatu . . . . . . . . . . . . . . . . . . . 152 . 3.4. Model przy dopuszczalnym niedoborze zapasu . . . . . . . . . . . . . . . . 157 Rozdział 4. Gry decyzyjne i analiza decyzji . . . . 166 . . . . . . . . . . . . . . . . . . 166 . 4.1. Gry dwuosobowe o sumie zero . . . . . . . . . . . . . . . . . . . . 181 . 4.2. Gry dwuosobowe o sumie niezerowej . . . . . . . . . . . . . . . . . . . 189 . . . 4.3. Gry z naturą . . . 4.4. Drzewa decyzyjne . . . . . . . . . . . . . . . . . . . . . 204 . . . . . . . . . . . . . . . . . . 209 . . 4.5. Wieloetapowe procesy decyzyjne . Rozdział 5. Łańcuchy Markowa . . . . . . . . . . . . . . 217 5.1. Prawdopodobieństwa przejść łańcucha Markowa w poszczególnych okresach 219 5.2. Stałe prawdopodobieństwa przejść łańcucha . . . . . . . . . . . . . . . . . 219 5.3. Oczekiwany czas powrotu łańcucha . . . . . . . . . . . . . . . . . . . 220 . . . . . . . . . . . . . . . . . 220 5.4. Przykłady zastosowań łańcuchów Markowa . Zakończenie . . . . . . . . . . . . . . . . . . 233 . Bibliografia . . . . . . . . . . . . . . . . . . . 235 . Indeks rzeczowy . . . . . . . . . . . . . . . . . . . 237 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Wykaz stosowanych skrótów CM DCD EOQ EVPI EVWOPI EVWPI IRR MCM MIRR MM MNPV MPI MRM NCW NPV OZT PI R.H.S. RAM RM VAM WinQSB ZZT – długość cyklu dostaw, – metoda minimalnego elementu kolumny (Column Minimum), – – wielkość pojedynczego zamówienia (Economic Order Quantity), – wartość oczekiwana doskonałej informacji (Expected Value of Prefect Information), – wartość oczekiwana bez doskonałej informacji (Expected Value without Perfect Information), – wartość oczekiwana z doskonałą informacją (Expected Value with Perfect Information), – wewnętrzna stopa zwrotu (Internal Rate of Return), – zmodyfikowana metoda minimalnego elementu kolumny (Modified Column Minimum), zmodyfikowana wewnętrzna stopa zwrotu (Modified Internal Rate of Return), – – metoda minimalnego elementu macierzy kosztów (Matrix Minimum), – – zmodyfikowana wartość obecna netto (Modified Net Present Value), zmodyfikowany współczynnik rentowności (Modified Profitability Index), zmodyfikowana metoda minimalnego elementu wiersza (Modified Row Minimum), – otwarte zadanie transportowe, – metoda kąta północno-zachodniego (Northwest Corner Method), – wartość obecna netto (Net Present Value), – – współczynnik rentowności (Profitability Index), – – metoda RAM, metoda Rossella (Rossell’s Approximation Method), – metoda minimalnego elementu wiersza (Row Minimum), – metoda VAM, metoda Vogla (Vogel’s Approximation Method), – prawa strona warunków ograniczających (Right Hand Side), program do rozwiązywania zadań z zakresu programowania matematycznego (Windows Quantitative Support for Business), zamknięte zagadnienie transportowe. Wstęp Badania operacyjne są dyscypliną zajmującą się rozwiązywaniem problemów decyzyjnych wówczas, gdy można je przedstawić (modelować) w postaci mate- matycznej. Pojęciem sytuacji decyzyjnej będziemy nazywać ogół czynników, które wyznaczają postępowanie decyzyjne podmiotu podejmującego decyzje zwa- nego krótko decydentem. W każdej sytuacji decyzyjnej pojawiają się: – decydent, – okoliczności przyczynowe wywołujące sytuację decyzyjną, – zbiór decyzji dopuszczalnych, – kryteria wyboru decyzji do realizacji. Ostateczna decyzja nie musi być identyczna z decyzją optymalną uzyskaną w wyniku rozwiązania zadania decyzyjnego. Można wymienić kilka przyczyn zastosowania metod badań operacyjnych do rozwiązania określonej klasy problemów decyzyjnych w przedsiębiorstwie [Anderson, Sweeney, Williams, 2000, s. 6]: – Problem jest skomplikowany i decydent nie może uzyskać zadowalającego rozwiązania bez wspomagania analizami ilościowymi. – Problem jest szczególnie ważny i decydent potrzebuje pełnej analizy przed podjęciem decyzji. – Problem jest nowy i decydent nie posiada wymaganego doświadczenia. – Problem jest powtarzalny i decydent oszczędza czas i wysiłek, przygotowując decyzję na podstawie procedur ilościowych. Podstawą do podjęcia optymalnej decyzji za pomocą metod badań operacyj- nych jest model decyzyjny uprzednio przygotowany w postaci matematycznej. Model ten na poziomie wejścia składa się z niekontrolowanych danych wej- ściowych (wynikają one z określonej sytuacji decyzyjnej w przedsiębiorstwie i określają tzw. warunki ograniczające) oraz kontrolowalnych danych wejściowych (identyfikacja zmiennych decyzyjnych). Model decyzyjny na poziomie wyjścia dostarcza informacji o możliwości rozwiązania optymalnego, a jeśli takie jest osiągalne, to uzyskuje się wartość optymalizowanej funkcji celu, a także wartości zmiennych decyzyjnych (rezultat) oraz czas wykonania obliczeń. Jeżeli niekontrolowane dane wejściowe są znane lub możliwe do oszacowania i jednocześnie nie ulegają zmianie, model decyzyjny jest modelem determini- stycznym. Mówimy wówczas, że warunki działania przedsiębiorstwa w obszarze rozpatrywanego problemu decyzyjnego są zdeterminowane. Jeżeli niekontrolowa- 8 Wstęp ne dane wejściowe nie są znane i jednocześnie nie można ich wielkości dokładnie oszacować bądź znany jest jedynie zakres wartości, jakie mogą przyjmować, to wówczas model decyzyjny jest nazywany modelem stochastycznym lub pro- babilistycznym. Oba rodzaje modeli decyzyjnych będą przedmiotem rozważań w niniejszej pracy. Nie wszystkie problemy decyzyjne dają się przedstawić w postaci matema- tycznej. Rozwiązywanie takich problemów nie może być wspomagane badaniami operacyjnymi. W pracy przedstawiono wybrane zagadnienia badań operacyjnych. Dotyczą one problemów decyzyjnych w obszarze zarządzania przedsiębiorstwem, ekono- miki i organizacji produkcji. Kolejne rozdziały pracy to: 1) programowanie liniowe; 2) zagadnienia transportowe; 3) modele gospodarki zapasami; 4) gry decyzyjne i analiza decyzji; 5) łańcuchy Markowa. Każde z prezentowanych zagadnień zawiera minimalny wykład teoretyczny oraz przynajmniej jeden przykład numeryczny w postaci zadania. Każdy przy- kład jest rozwiązany z wykorzystaniem oprogramowania pod nazwą WinQSB (Windows Quantitative Support for Business). Program ten wspomaga użytkow- nika w realizacji procesu numerycznego (obliczeniowego). Stosowanie programu komputerowego do rozwiązywania określonych problemów decyzyjnych jest wa- runkiem koniecznym, gdyż przeprowadzanie ręcznych obliczeń jest procesem żmudnym, wymagającym dość dużego nakładu pracy, a przez to przygotowanie optymalnej decyzji może być zbyt kosztowne w relacji do możliwych korzyści z jej zastosowania. Ponadto ręczne obliczenia są podatne na błędy rachunkowe, co w takiej sytuacji prowadzi do rekomendacji decyzji nieefektywnej z ekonomiczne- go punktu widzenia, przy jednoczesnym uwzględnieniu kosztu jej przygotowania. Zastosowanie arkusza kalkulacyjnego również może być nieefektywne ze względu na czas i wysiłek przy konstruowaniu arkusza do odpowiedniego modelu decy- zyjnego oraz przy jego ewentualnej przebudowie (np. w przypadku rozszerzenia jego wymiarów). Indywidualne stosowanie arkusza kalkulacyjnego może również prowadzić do błędów na etapie przygotowania i konstrukcji modelu decyzyjnego w arkuszu. Omawiane w pracy przykłady pokazują kolejne etapy wykorzystania progra- mu WinQSB – od wprowadzenia danych wejściowych do uzyskania rozwiązania i poszczególnych raportów wynikowych. Poszczególne kroki dochodzenia do roz- wiązania w programie WinQSB zostały zilustrowane licznymi zrzutami z ekranu przygotowanymi przez Autora. Pakiet oprogramowania WinQSB jest dostępny w trybie open source, na stro- nie internetowej http://winqsb.softonic.pl/. W przypadku pracy na naj- nowszych wersjach systemu operacyjnego Windows, użytkownik może napotkać pewne problemy uniemożliwiające instalację programu WinQSB. Wówczas najle- 9 Wstęp piej jest wyszukać w wyszukiwarce internetowej instrukcję postępowania w celu poprawnej instalacji WinQSB. Warto tu wspomnieć o dwóch cechach WinQSB, o których należy pamiętać, pracując w tym programie, a mianowicie o tym, że w większości modułów programu WinQSB są zamieszczane daty wygenerowania raportów (daty te są zapisywane w standardzie amerykańskim, tj. mm-dd-rrrr) oraz że na oznaczenie liczb dziesiętnych używa się kropki, a nie przecinka. Niniejszy podręcznik umożliwia: – zapoznanie się z określonymi rodzajami zadań decyzyjnych rozwiązywalnych za pomocą metod i modeli badań operacyjnych od strony teoretyczno-meto- dycznej, – poznanie funkcjonalności programu WinQSB, wspomagających samodziel- ne rozwiązywanie określonej klasy problemów decyzyjnych powstających w przedsiębiorstwie. W literaturze odnajdziemy tylko jedną pozycję poruszającą zagadnienia badań operacyjnych z wykorzystaniem programu WinQSB: [Desai, 2003], powstałą na University of Memphis. W publikacji tej brakuje jednak teoretycznej prezentacji problemów z zakresu badań operacyjnych, gdyż ma ona charakter instrukcji do oprogramowania (tzw. manual), choć w niepełnym zakresie funkcjonalności programu. Rozdział 1. Programowanie liniowe 1.1. Modelowanie problemów decyzyjnych Metody programowania liniowego są podstawowym działem zagadnień z zakresu badań operacyjnych. Służą one do budowania liniowych modeli, wspomagających rozwiązywanie problemów (zadań) decyzyjnych. Liniowe zadanie optymalizacyj- ne jest pewną klasą zadania programowania matematycznego, którego funkcja celu oraz zbiór warunków ograniczających są liniowe, czyli można je rozwiązać za pomocą metod optymalizacji liniowej. Ogólna postać liniowego modelu decyzyjnego (zadania programowania linio- wego), będącego wynikiem modelowania sytuacji decyzyjnej, jest następująca: z = c1x1 + c2x2 + . . . + cnxn → max lub min, (1.1) przy warunkach ograniczających  a11x1 + a12x2 + . . . + a1nxn (cid:62) b1 a21x1 + a22x2 + . . . + a2nxn (cid:62) b2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . am1x1 + am2x2 + . . . + amnxn (cid:62) bm . (1.2) Nie ma znaczenia fakt, że w warunkach ograniczających występuje nierówność typu „(cid:62)” (można ją zastąpić równością lub nierównością typu „(cid:54)”). Innymi słowy, zbiór warunków ograniczających może mieć postać układu równań i/lub słabych nierówności liniowych typu „(cid:62)” i „(cid:54)”. Funkcja z jest nazywana funkcją celu lub funkcją kryterium. Wskazuje ona kryterium wyboru decyzji optymalnej. Występujące w modelu współczynni- ki c1, c2, . . . , cn są określane mianem współczynników funkcji celu, natomiast zmienne x1, x2, . . . , xn noszą nazwę zmiennych decyzyjnych. Zmienne te są przedmiotem sterowania w procesie podejmowania decyzji (w sposób formalny opisują podejmowaną decyzję). Podejmowanie decyzji zawsze przebiega w wa- runkach pewnych ograniczeń, co formalnie wyrażają warunki ograniczające, przy 11 Rozdział 1. Programowanie liniowe czym współczynniki ai1, ai2, . . . , ain (dla i = 1, 2, . . . , m) są określane współ- czynnikami warunków ograniczających, zaś b1, b2, . . . , bm są wyrazami wolnymi warunków ograniczających. Zadanie programowania liniowego, zapisane w postaci (1.1)–(1.2), można przedstawić w zapisie wektorowym: z = cTx → max lub min, przy warunkach ograniczających Ax (cid:62) b, ((cid:54)) (=) gdzie c =  ; x =   c1 c2 . . . cn x1 x2 . . . xn  ; A =  a11 a12 . . . a1n a21 a22 . . . a2n . . . . . . . . . . . . am1 am2 . . . amn (1.3) (1.4)  ; b =   . b1 b2 . . . bm Zadania programowania liniowego charakteryzują się dość prostym zapisem matematycznym oraz uniwersalnym i wydajnym algorytmem obliczeniowym. Rozwiązywanie zadań programowania liniowego polega na wyznaczeniu wartości zmiennych decyzyjnych dla ekstremum warunkowego funkcji celu, przyj- mując odpowiednio największą wartość funkcji celu dla zadania na maksimum, bądź najmniejszą – dla zadania na minimum. Rozwiązanie optymalne przy istnieją- cych warunkach ograniczających można znaleźć za pomocą metody geometrycznej lub metody analitycznej. Najczęściej stosowaną metodą analityczną jest procedura iteracyjna opracowana przez G.B. Dantzinga, określana algorytmem simpleks lub metodą simpleks. Metoda geometryczna pozwala w prosty sposób wyznaczyć roz- wiązanie optymalne, ale posiada ograniczenie do dwóch zmiennych decyzyjnych (przestrzeń dwuwymiarowa). Należy zauważyć, że zadanie wyjściowe może po- siadać dowolną postać układu równań i nierówności warunków ograniczających. Rozwiązanie problemu decyzyjnego za pomocą badań operacyjnych jest procedurą składającą się z następujących etapów [Siudak M., 2012, s. 9]: 1) rozpoznanie sytuacji decyzyjnej i wynikającego z niej problemu decyzyjnego; 2) budowa modelu decyzyjnego; 3) rozwiązanie zadania decyzyjnego; 4) ocena poprawności i realności uzyskanych rozwiązań oraz ewentualna weryfi- kacja modelu decyzyjnego; 5) przedstawienie rozwiązań decydentowi i ostateczne przygotowanie decyzji. Zdecydowanie najtrudniejszym etapem jest konstrukcja modelu decyzyjne- go, czyli matematycznej formalizacji rzeczywistego zadania optymalizacyjnego 12 1.1. Modelowanie problemów decyzyjnych (określenie funkcji celu, kryterium wyboru, warunków ograniczających). Nie- właściwie skonstruowany model decyzyjny może prowadzić do podjęcia decyzji nieoptymalnej, przy czym po stronie kosztów należy uwzględnić poniesione nakłady i zasoby do jej przygotowania. Każdy model jest pewnego rodzaju przybliżeniem rzeczywistości w przedsiębiorstwie, aczkolwiek powinien on uwzględniać wszelkie czynniki mające istotny wpływ na podjęcie właściwej (optymalnej) decyzji. Warto pamiętać, że umiejętność budowy modeli decyzyj- nych można nabyć poprzez analizę przykładowych – hipotetycznych – problemów decyzyjnych powstających w przedsiębiorstwach i wyrażanie ich w postaci sformalizowanych matematycznych problemów decyzyjnych, których rozwią- zywanie wspomagają badania operacyjne. Modelowanie sytuacji problemowych, do których można zastosować metody badań operacyjnych, jest przedmiotem pracy [Pidd, 2003]. Budując liniowe modele decyzyjne, zazwyczaj korzysta się z tzw. aksjomatów liniowości. Przykładowo w obszarze funkcjonowania procesów produkcyjnych określa się dwa podstawowe aksjomaty liniowości modelu decyzyjnego (por. [Siudak M., 2012, s.14]): 1) addytywności – zakładający brak dodatkowych strat lub korzyści wystę- pujących na skali produkcji (zarówno w aspekcie technologicznym, jak i ekonomicznym); 2) proporcjonalności – zakładający stałość proporcji pomiędzy poniesionymi nakładami a uzyskanymi rezultatami. W każdym wypadku należy przeprowadzić analizę, czy przyjęcie powyższych aksjomatów jest uzasadnione dla rzeczywistego problemu decyzyjnego. Ze względu na dalsze rozważania, dokonamy klasyfikacji modeli decyzyjnych rozwiązywanych za pomocą programowania matematycznego według kryterium postaci zmiennych decyzyjnych na1: 1) modele decyzyjne, w których wszystkie zmienne są typu ciągłego; 2) modele decyzyjne zawierające co najmniej jedną zmienną dyskretną (czyli skokową). Zmienne ciągłe rozwiązania optymalnego modelu decyzyjnego mogą przyjmo- wać każdą wartość ze zbioru rozwiązań dopuszczalnych (zazwyczaj w modelach decyzyjnych występują tzw. warunki brzegowe w postaci warunku ogranicza- jącego, zakładającego z góry, że zmienne decyzyjne muszą być większe lub równe zeru). Natomiast zmienne dyskretne przyjmują wartości z niespójnego (skokowego) zbioru izolowanych punktów. Szczególnym przypadkiem zmien- nych dyskretnych są zmienne całkowitoliczbowe – model z takimi zmiennymi określa się mianem zadania programowania całkowitoliczbowego, w którym przy- najmniej jedna zmienna musi przyjmować wartość całkowitą. Innego rodzaju zmienną dyskretną jest tzw. zmienna binarna (zero-jedynkowa), która przyjmu- je wartości 0 lub 1. Modele decyzyjne zawierające co najmniej jedną zmienną 1 Nie jest to jedyne kryterium, według którego można dokonać podziału modeli decyzyjnych. 13 Rozdział 1. Programowanie liniowe binarną są określane mianem zadania programowania binarnego. W stosunku do dyskretnych modeli decyzyjnych stosuje się odrębną klasę metod ich rozwią- zywania. W dalszych częściach niniejszego rozdziału zostaną zaprezentowane przy- kładowe zadania programowania liniowego i ich rozwiązania za pomocą metod geometrycznej oraz analitycznej wraz z pełną analizą i interpretacją uzyskanych wyników. Do ich rozwiązania wykorzystano oprogramowanie WinQSB wspoma- gające rozwiązywanie wielu zadań decyzyjnych za pomocą metod i modeli badań operacyjnych. Moduł programowania liniowego WinQSB umożliwia wyznacze- nie rozwiązania optymalnego zarówno metodą geometryczną, jak i analityczną. Czytelnika zainteresowanego aspektami teoretycznymi programowania liniowego, w tym prezentacją algorytmu simpleks, odsyłamy do szeroko dostępnej literatury przedmiotu (np. [Siudak M., 2012]). 1.2. Rozwiązywanie zadań programowania liniowego metodą geometryczną Dowolne rozwiązanie x1, x2, . . . , xn, spełniające układ równań i nierówności (1.2) jest rozwiązaniem dopuszczalnym zadania. Zbiór wszystkich rozwiązań dopusz- czalnych, czyli zbiór rozwiązań układu równań i nierówności (1.2) będziemy dalej oznaczać przez X. Rozwiązania bazowe układu warunków (1.2) będziemy nazywać dopusz- czalnymi rozwiązaniami bazowymi, jeżeli spełniają one dodatkowo warunek brzegowy: x1 (cid:62) 0, x2 (cid:62) 0, . . . , xn (cid:62) 0. Rozwiązania optymalnego należy poszukiwać wśród bazowych rozwiązań dopuszczalnych układu ograniczeń. Ponieważ wektor bazowych rozwiązań dopusz- czalnych jest punktem wierzchołkowym zbioru rozwiązań dopuszczalnych (X), więc rozwiązanie optymalne leży w jednym z wierzchołków zbioru rozwiązań układu równań i nierówności, a w szczególnym przypadku również na całej krawędzi tego zbioru. Rozwiązaniem optymalnym zadania programowania li- niowego na maksimum (minimum) jest to rozwiązanie, które spośród bazowych rozwiązań dopuszczalnych osiąga największą (najmniejszą) wartość funkcji celu. W przypadku, gdy zbiór rozwiązań dopuszczalnych jest pusty (X = ∅), zadanie jest sprzeczne. Klasyfikację możliwych wyników rozwiązania zadania liniowego przedstawiono na rys. 1.1. Rozwiązanie zadania liniowego metodą geometryczną polega na: – graficznym wyznaczeniu zbioru rozwiązań dopuszczalnych (graficzne roz- wiązanie układu równań i nierówności stanowiących układ warunków ograniczających), – graficznym wyznaczeniu punktu (punktów) optymalnego poprzez wyznacze- nie kilku warstwic funkcji celu. 14 1.2. Rozwiązywanie zadań programowania liniowego metodą geometryczną Rysunek 1.1. Klasyfikacja możliwych wyników rozwiązania zadania programowania liniowego Źródło: opracowanie własne. Należy podkreślić, iż moduł programowania liniowego programu WinQSB automatycznie znajduje warstwicę funkcji celu w punkcie (punktach) odpowia- dającym najmniejszej wartości funkcji kryterium dla zadania na minimum lub odpowiadającym największej wartości funkcji kryterium dla zadania na maksi- mum. Za pomocą kolejnych przykładów z zakresu zarządzania i organizacji pro- dukcji przeanalizujemy możliwości uzyskania wyników rozwiązania zadania programowania liniowego. Przykład 1.1. Przedsiębiorstwo produkuje dwa rodzaje produktów (P1 i P2). Zysk ze sprzedaży jednej tony produktu P1 wynosi 1000 złotych, a z jednej tony produktu P2 2000 złotych. Do produkcji są wykorzystywane dwa surowce: SS1 i SS2, których ilość dostępna w ciągu jednej doby wynosi odpowiednio 8 ton i 3 tony. Ilości surowców (w tonach) wykorzy- stywane do produkcji jednej tony produktu P1 i jednej tony produktu P2 zamieszczono w tabeli 1.1. Oba wyroby charakteryzują się wysoką podzielnością. Tabela 1.1. Zapotrzebowanie na surowce do produkcji oraz ich dostępne zasoby Produkt Surowiec S1 [tony] S2 [tony] Źródło: opracowanie własne. P1 P2 Dostępne zasoby 2 0 2 1 8 3 15 Rozdział 1. Programowanie liniowe największy? Rozwiązanie Ile ton dziennie należy produkować produktów P1 i P2, aby zysk ze sprzedaży był Oznaczamy przez x1 (zmienna decyzyjna 1) ilość ton produkcji produktu P1, a przez x2 (zmienna decyzyjna 2) ilość ton produktu P2. Zadanie programowania liniowego przyjmuje postać poniższego modelu z = 1000x1 + 2000x2 → max, przy warunkach ograniczających 2x1 + 2x2 (cid:54) 8 x2 (cid:54) 3 x1, x2 (cid:62) 0. (1.5) (1.6) (1.7) (1.8) Funkcja celu określa poszukiwanie takiej struktury produkcji, aby uzyskać najwięk- szy (maksymalny) zysk ze sprzedaży produktów P1 i P2. Pierwszy warunek ograniczający oznacza, iż nie można wykorzystać więcej niż 8 ton zasobu surowca SS1, który do produkcji 1 tony produktu P1 jest wykorzystywany w ilo- ści 2 ton, a do produkcji 1 tony produktu P2 również w ilości 2 ton. Drugi warunek ograniczający zakłada, iż do produkcji 1 tony produktu P2 jest wykorzystywana 1 tona surowca S2, którego ilość jest limitowana do 3 ton. Trzeci warunek ograniczający został wprowadzony ze względu na to, iż przed- siębiorstwo nie może wyprodukować ujemnej wielkości produktów P1 i P2 (warunek nieujemności zmiennych decyzyjnych). Tego typu warunki ograniczające określa się mianem warunków brzegowych. Do rozwiązania powyższego zadania decyzyjnego zastosujemy moduł programowa- nia liniowego programu WinQSB. W tym celu należy uruchomić program, wybierając z listy dostępnych programów polecenie WinQSB i dalej moduł Linear and Integer Programming (programowanie liniowe i całkowitoliczbowe). Po uruchomieniu progra- mu pojawi się okno jak na rys. 1.2. Rysunek 1.2. Okno startowe modułu Linear and Integer Programming programu WinQSB 16 1.2. Rozwiązywanie zadań programowania liniowego metodą geometryczną Po uruchomieniu programu, użytkownik ma do wyboru dwie opcje: 1) wprowadzić nowy problem decyzyjny (od początku); 2) załadować uprzednio wprowadzony i zapisa- ny problem decyzyjny. Aby wprowadzić od początku nowy problem do programu, należy wybrać z menu polecenie File/New problem. Zostanie wówczas wyświetlone okno (rys. 1.3), w którym dokonuje się specyfikacji problemu. W oknie tym należy określić: – tytuł problemu (Problem Title), – liczbę zmiennych występujących w modelu (Number of Variables), – liczbę warunków ograniczających (Number of Constraints), – ekstremum funkcji celu (Objective Criterion) – kryterium funkcji celu może zostać określone jako maksimum (maximization) lub minimum (minimization), – domyślny typ zmiennych (Default Variable Type) – typ może zostać określony jako zmienna nieujemna ciągła (Nonnegative continuous), zmienna nieujemna całkowitoliczbowa (Nonnegative integer), zmienna binarna (Binary (0, 1)), zmienna nieograniczona ciągła (Unsigned/unrestricted), – format wprowadzania danych (Data Entry Format) – może to być formularz sko- roszytu (Spreadsheet Matrix Form) bądź formularz modelu (Normal Model Form). Rysunek 1.3. Okno specyfikacji nowego problemu decyzyjnego Oczywiście na dalszym etapie pracy z programem można dokonywać zmian specy- fikacji, łącznie ze zmianą ekstremum funkcji celu, dodawaniem/usuwaniem zmiennych, warunków ograniczających czy zmianą typu zmiennych. Model decyzyjny zapisany za pomocą równań (1.5)–(1.8) zawiera dwie zmienne de- cyzyjne oraz dwa warunki ograniczające, a funkcja celu dąży do maksimum. W tym miejscu należy zaznaczyć, że do programu WinQSB nie ma sensu wprowadzać dodat- kowo warunku brzegowego (1.8), ponieważ warunek nieujemności zmiennych jest speł- niony poprzez określenie ich typu jako zmiennych nieujemnych ciągłych (Nonnegative continuous). Zmienne decyzyjne są oczywiście zmiennymi ciągłymi ze względu na założenie ich nieskończonej podzielności2. Każda zmienna typu ciągłego może przyjąć dowolną wartość ze zbioru liczb rzeczywistych. 2 Modele, w których występują zmienne całkowitoliczbowe, będą omawiane w podrozdziale 1.4. 17 Rozdział 1. Programowanie liniowe Preferowanym formatem wprowadzania danych jest zwykły skoroszyt, przypomina- jący arkusz kalkulacyjny MS Excel. Po zatwierdzeniu (przycisk OK) przechodzimy do formularza wprowadzania parametrów zadania decyzyjnego programowania liniowego, co zaprezentowano na rys. 1.4. Rysunek 1.4. Arkusz służący do wprowadzania parametrów zadania programowania liniowego z przykładu 1.1 Arkusz wprowadzania parametrów zadania programowania liniowego jest skonstru- owany w postaci tabeli, której kolumny składają się z kolejnych zmiennych decyzyjnych. Domyślnie są one określane symbolem X z kolejnymi numerami porządkowymi (w tym przypadku mamy X1 i X2). Ostatnie dwie kolumny służą do określania kierunku nierów- ności (ewentualnie określenia równości) warunków ograniczających (Direction) oraz wartości wyrazów wolnych tychże warunków (R. H. S.)3. Pierwszy wiersz dotyczy tylko i wyłącznie funkcji celu, kolejne zaś – poszcze- gólnych warunków ograniczających. Domyślnie są one oznaczone literą C (od słowa constraint) z kolejnymi liczbami porządkowymi (w analizowanym przykładzie są to C1 i C2). Ostatnie trzy wiersze służą do określania typu zmiennych: dolne ograniczenie (LowerBound), górne ograniczenie (UpperBound) i typ zmiennych (Variable Type). Dla górnego ograniczenia oraz symetrycznie dla dolnego ograniczenia mogą pojawić się następujące symbole: M i −M. Symbol M oznacza bardzo dużą liczbę (oznacze- nie zostało wprowadzone w metodzie kar4 wyznaczania początkowego dopuszczalnego rozwiązania bazowego), tak dużą, że w przypadku, gdy parametr a jest liczbą dodatnią, to dla dowolnych liczb a, b ∈ R spełniona będzie nierówność aM − b 0. Przykłado- we nierówności 0,00001M − 1 000 000 000 0 lub −0,00001M + 1 000 000 000 0 są spełnione za względu na liczbę M. 3 Czyli wartości prawych stron układu równań i nierówności, stąd też skrót R. H. S. (Right Head Side). 4 Metoda kar zostanie omówiona w podrozdziale 1.3. 18 1.2. Rozwiązywanie zadań programowania liniowego metodą geometryczną Dla każdej zmiennej decyzyjnej można dokonać zmiany jej typu poprzez dwukrotne kliknięcie w komórkę zawierającą typ zmiennej. Wówczas automatycznie zmianie ule- gają dolne i górne ograniczenie. W podobny sposób można dokonywać zmiany kierunku nierówności (lub zmiany na równość i odwrotnie) poszczególnych warunków ogranicza- jących5. Oczywiście każde nowo wprowadzone zadanie decyzyjne może zostać zapisane lub wydrukowane (opcje z menu File). Do aktualnego zadania można wprowadzać odpo- wiednie modyfikacje za pomocą poleceń z menu Edit: – zmiana tytułu problemu (Problem Name), – zmiana nazw zmiennych decyzyjnych (Variable Names), – zmiana nazw warunków ograniczających (Constraint Names), – zmiana ekstremum funkcji celu (Objective Function Creation), – dołączenie nowej zmiennej decyzyjnej (Insert a Variable), – usunięcie zmiennej decyzyjnej (Delete a Variable), – dołączenie nowego warunku ograniczającego (Insert a Constraint), – usunięcie warunku ograniczającego (Delete a Constraint). Można także przełączyć tryb wprowadzania danych zadania decyzyjnego na formu- larz modelu (co pokazano na rys. 1.5), wybierając z menu Format polecenie Switch to Normal Model Form. Rysunek 1.5. Formularz modelu dla zadania programowania liniowego z przykładu 1.1 Na rysunku 1.5. został przedstawiony model decyzyjny programowania liniowe- go z przykładu 1.1, którego odpowiednikiem jest model na rys. 1.4. Ponieważ zadanie opisane równaniami (1.5)–(1.8) zawiera dwie zmienne decyzyjne, zatem można je roz- wiązać metodą geometryczną w układzie współrzędnych (dwuwymiarowa przestrzeń geometryczna). Niezależnie od rodzaju formularza wprowadzania danych, aby rozwiązać zadanie metodą geometryczną należy wybrać z menu Solve and Analyze polecenie Graphic Method. Wyświetlone zostanie okno dialogowe (rys. 1.6) służące do przy- pisania każdej z dwóch zmiennych decyzyjnych do osi odciętych i osi rzędnych. Po zaakceptowaniu (w większości przypadków można przyjąć domyślny układ osi współ- rzędnych) zostanie wyświetlone rozwiązanie zadania decyzyjnego metodą geometryczną – w tym przypadku jest to rozwiązanie przykładu 1.1, co przedstawiono na rys. 1.7. Obszar zakreskowany stanowi zbiór rozwiązań dopuszczalnych X. Wynika on z dwóch warunków ograniczających (C1 i C2) oraz warunku brzegowego (x1, x2 (cid:62) 0). Prosta oznaczona symbolem C1 wyznacza półpłaszczyznę z warunku ograniczające- 5 Jest to pomocne w przypadku zadań, w których występuje kilkaset lub więcej zmiennych i kil- kaset lub więcej warunków ograniczających. 19
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Badania operacyjne z wykorzytsaniem WinQSB
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: