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
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)
