Wprowadzenie do badań operacyjnych z komputerem

Spis treści

Rozdział 1. Programowanie liniowe
1.1. Wprowadzenie
1.2. Metoda geometryczna
1.2.1. Model matematyczny
1.2.2. Zbiór rozwiązań dopuszczalnych
1.2.3. Warstwice funkcji celu
1.2.4. Gradient funkcji celu
1.3. Metoda simpleks
1.3.1. Postać bazowa
1.3.2. Badanie optymalności rozwiązania
1.3.3. Wybór zmiennej wprowadzanej do bazy
1.3.4. Wybór zmiennej opuszczającej bazę
1.3.5. Przejście do rozwiązania bazowego sąsiedniego
1.3.6. Kolejne iteracje
1.3.7. Interpretacja geometryczna
1.3.8. Macierz odwrotna do macierzy bazowej
1.3.9. Pierwsza dopuszczalna postać bazowa
1.4. Przegląd szczególnych przypadków
1.4.1. Zadanie sprzeczne
1.4.2. Alternatywne rozwiązania optymalne
1.4.3. Nieograniczony zbiór rozwiązań dopuszczalnych
1.4.4. Reguły postępowania w metodzie simpleks
1.5. Analiza wrażliwości
1.5.1. Współczynniki funkcji celu
1.5.2. Współczynniki wektora wyrazów wolnych
1.6. Dualizm w programowaniu liniowym
1.6.1. Zadanie dualne i jego własności
1.6.2. Ceny dualne i analiza wrażliwości w kształtowaniu optymalnych planów produkcji
1.7. Dualna metoda simpleks
1.7.1. Przebieg obliczeń
1.7.2. Pierwsza optymalna postać bazowa
1.7.3. Zadanie sprzeczne
1.7.4. Nieograniczona funkcja celu
1.7.5. Reguły postępowania w dualnej metodzie simpleks
1.8. Parametryczne programowanie liniowe
1.8.1. Funkcja celu zależna od parametru
1.8.2. Wektor wyrazów wolnych zależny od parametru
1.9. Przykłady wykorzystania programowania liniowego
1.9.1. Zagadnienie rozkroju
1.9.2. Zagadnienie diety
1.9.3. Parametryczne planowanie produkcji
 

Rozdział 2. Programowanie liniowe całkowitoliczbowe
2.1. Wprowadzenie
2.2. Metoda podziału i ograniczeń
2.2.1. Zadanie czyste
2.2.2. Zadanie mieszane
2.2.3. Reguły postępowania w metodzie podziału i ograniczeń
2.2.4. Zaokrąglanie rozwiązań
2.3. Metoda cięć
2.3.1. Konstrukcja równania cięcia
2.3.2. Reguły postępowania w metodzie cięć
2.4. Przykłady wykorzystania programowania liniowego całkowitoliczbowego
2.4.1. Zagadnienie produkcyjno-modernizacyjne
2.4.2. Optymalizacja planu wydawniczego
2.4.3. Zagadnienie lokalizacji
 

Rozdział 3. Zadanie transportowe i problem komiwojażera
3.1. Wprowadzenie
3.2. Zadanie transportowe i jego własności
3.2.1. Zadanie transportowe w ujęciu programowania liniowego
3.2.2. Zadanie dualne do zadania transportowego
3.2.3. Sformułowanie zadania transportowego
3.3. Pierwsze dopuszczalne rozwiązanie bazowe
3.3.1. Metoda minimalnego elementu macierzy kosztów
3.3.2. Metoda VAM
3.3.3. Metoda kąta północno-zachodniego
3.4. Metoda potencjałów
3.4.1. Badanie optymalności rozwiązania
3.4.2. Wybór zmiennej wprowadzanej do bazy
3.4.3. Wybór zmiennej opuszczającej bazę
3.4.4. Przejście do rozwiązania bazowego sąsiedniego
3.4.5. Kolejne iteracje
3.4.6. Degeneracja w zadaniu transportowym
3.4.7. Reguły postępowania w rozwiązywaniu zadania transportowego
3.5. Bilansowanie zadania transportowego
3.5.1. Podaż przewyższa popyt
3.5.2. Popyt przewyższa podaż
3.6. Problem komiwojażera
3.6.1. Problem komiwojażera a zagadnienie transportowe
3.6.2. Zadanie komiwojażera jako zadanie programowania całkowitoliczbowego
3.6.3. Mechanizmy działania algorytmu genetycznego
3.6.4. Symulacja działania algorytmu genetycznego
3.7. Przykłady wykorzystania zadania transportowego
3.7.1. Minimalizacja pustych przebiegów
3.7.2. Zagadnienie transportowo-produkcyjne
3.7.3. Zagadnienie przydziału
 

Rozdział 4. Metody wielokryterialne
4.1. Wprowadzenie
4.2. Zadanie wektorowej maksymalizacji
4.2.1. Rozwiązanie dominujące
4.2.2. Rozwiązanie niezdominowane
4.3. Metoda ADBASE
4.3.1. Rozszerzona tablica simpleksowa
4.3.2. Zadanie testujące
4.3.3. Sąsiednie bazowe rozwiązanie sprawne
4.3.4. Reguły postępowania w metodzie ADBASE
4.4. Generowanie wybranych rozwiązań sprawnych
4.4.1. Generowanie rozwiązań sprawnych za pomocą jednej funkcji celu
4.4.2. Metoda satysfakcjonującego poziomu kryteriów
4.4.3. Metoda sumy ważonej
4.4.4. Hierarchia kryteriów
4.4.5. Wykorzystanie punktu idealnego
4.4.6. Metoda interaktywna
4.5. Programowanie celowe
4.5.1. Bilansowanie celów
4.5.2. Hierarchizacja odchyleń
4.5.3. Ilustracja graficzna w przestrzeni decyzyjnej
4.5.4. Współczynniki wagowe
4.6. Wielokryterialne metody dyskretne
4.6.1. Metoda AHP
4.6.2. Metoda Promethee II
4.6.3. Metoda Electre I
4.7. Przykłady zastosowania metod wielokryterialnych
4.7.1. Organizacja kampanii reklamowej
4.7.2. Określenie strategii długookresowej firmy

Rozdział 5. Podejmowanie decyzji w warunkach niepełnej informacji
5.1. Wprowadzenie
5.2. Podejmowanie decyzji w warunkach ryzyka
5.2.1. Maksymalizacja oczekiwanej korzyści - decyzje jednoetapowe
5.2.2. Maksymalizacja oczekiwanej korzyści - decyzje wieloetapowe
5.2.3. Maksymalizacja oczekiwanej użyteczności
5.3. Podejmowanie decyzji w warunkach niepewności
5.3.1. Reguły min-max, max-min i max-max
5.3.2. Współczynnik ostrożności
5.3.3. Reguła braku dostatecznej racji
5.3.4. Reguła minimalnego żalu
5.3.5. Porównanie wyników uzyskanych przy zastosowaniu różnych reguł decyzyjnych
5.4. Gry dwuosobowe o sumie zero
5.4.1. Strategie dominujące i zdominowane
5.4.2. Punkt siodłowy
5.4.3. Strategie mieszane

Rozdział 6. Programowanie wypukłe i kwadratowe
6.1. Wprowadzenie
6.2. Zadanie programowania wypukłego
6.2.1. Zbiory wypukłe i funkcje wypukle
6.2.2. Sformułowanie zadania programowania wypukłego
6.2.3. Warunki Kuhna-Tuckera
6.2.4. Wykorzystanie warunków Kuhna-Tuckera do rozwiązywania zadań programowania wypukłego
6.3. Metoda Wolfe'a
6.3.1. Warunki Kuhna-Tuckera dla zadania programowania kwadratowego
6.3.2. Sformułowanie zadania zastępczego
6.3.3. Rozwiązanie zadania zastępczego
6.3.4. Przypadek ogólny
6.3.5. Reguły postępowania w metodzie Wolfe'a
6.4. Optymalny portfel akcji
6.4.1. Oczekiwana stopa zysku i ryzyko portfela
6.4.2. Optymalizacja portfela akcji jako zadanie programowania kwadratowego
6.4.3. Dwukryterialne zadanie poszukiwania optymalnego portfela akcji

Rozdział 7. Zarządzanie projektami
7.1. Wprowadzenie
7.2. Konstrukcja sieci czynności
7.2.1. Kolejność realizacji czynności
7.2.2. Właściwa numeracja zdarzeń
7.3. Metoda ścieżki krytycznej
7.3.1. Krok do przodu
7.3.2. Krok do tyłu
7.3.3. Rezerwy czynności
7.3.4. Harmonogramy czasowo-optymalne
7.3.5. Zdarzenia i czynności pozorne
7.3.6. Reguły postępowania w metodzie CPM
7.3.7. Czynności jako wierzchołki sieci
7.4. Zarządzanie zasobami środków
7.4.1. Rozwiązywanie konfliktów zasobów
7.4.2. Przyspieszenie realizacji czynności
7.4.3. Minimalizacja kosztu realizacji projektu przy zadanym czasie dyrektywnym
7.4.4. Minimalizacja czasu realizacji projektu przy zadanym koszcie
7.5. Metoda PERT
7.5.1. Oczekiwany czas realizacji projektu i jego wariancja
7.5.2. Prawdopodobieństwo realizacji projektu w zadanym czasie
7.5.3. Czas realizacji projektu z zadanym prawdopodobieństwem
7.6. Przykłady wykorzystania metod zarządzania projektami
7.6.1. Wdrożenie komputerowego systemu zamówień w firmie
7.6.2. Poszukiwanie czasu krytycznego jako zadanie programowania liniowego
7.6.3. Przyspieszenie realizacji projektu jako zadanie dwukryterialne

Rozdział 8. Programowanie sieciowe
8.1. Wprowadzenie
8.2. Minimalne drzewo rozpinające
8.2.1. Reguły postępowania przy poszukiwaniu minimalnego drzewa rozpinającego
8.2.2. Kolejne iteracje
8.3. Najkrótsze drogi w sieci
8.3.1. Reguły postępowania przy poszukiwaniu najkrótszych dróg w sieci
8.3.2. Kolejne iteracje
8.4. Maksymalny przepływ w sieci
8.4.1. Reguły postępowania przy poszukiwaniu maksymalnego przepływu w sieci
8.4.2. Kolejne iteracje
8.5. Przykłady wykorzystania programowania sieciowego
8.5.1. Dynamiczny problem wielkości zamówienia
8.5.2. Optymalizacja transportu gorącej wody z ciepłowni do terminala wysyłkowego
8.5.3. Optymalizacja przebiegu linii światłowodowej

Rozdział 9. Programowanie dynamiczne
9.1 Wprowadzenie
9.2. Metoda programowania dynamicznego
9.2.1. Składowe wieloetapowego procesu decyzyjnego
9.2.2. Stany i decyzje dopuszczalne
9.2.3. Wartości funkcji kosztów etapowych
9.2.4. Zasada optymalności Bellmana i równania optymalności
9.2.5. Reguły postępowania przy rozwiązywaniu zadań programowania dynamicznego
9.3. Przykłady wykorzystania programowania dynamicznego
9.3.1. Zagadnienie rozdziału środka
9.3.2. Zagadnienie alokacji
9.3.3. Dwukryterialne zagadnienie alokacji

Fragment
Badania operacyjne i decyzje
Słowo decyzja występuje w wielu sytuacjach i niesie ze sobą różne treści, stanowiąc nieodłączny element naszego życia. Bardzo wiele uwagi poświęcono i poświęca się procesowi podejmowania decyzji.

Zacznijmy od dwóch przykładów:

1. Inwestor zainteresowany jest takim portfelem papierów wartościowych, który przyniesie mu w przyszłości największy zysk przy minimalnym ryzyku. Podejmuje on decyzję o zakupie akcji i obligacji, które znajdą się w jego portfelu inwestycyjnym.
2. Przyjmijmy, że przedmiotem decyzji jest program inwestycyjny dla pewnego regionu. Można ogólnie powiedzieć, że celem programu jest rozwój społeczno-ekonomiczny regionu. Mamy więc w gruncie rzeczy dwa podstawowe cele, obejmujące sferę społeczną i gospodarczą. Dalej konkretyzując, możemy przyjąć, że cel rozwój gospodarczy zostanie osiągnięty, jeżeli nastąpi rozwój przemysłu, rolnictwa, budownictwa, rzemiosła.
Podobnie, celowi rozwój społeczny, rozumianemu jako poprawa warunków życia mieszkańców, odpowiada rozwój budownictwa mieszkaniowego, sieci komunikacyjnej, oświaty, służby zdrowia, poprawa stanu środowiska naturalnego. Zamiast jednego celu ogólnego mamy więc całą wiązkę celów cząstkowych, opisujących poszczególne aspekty rozwoju regionu 1.

Podejmując decyzję, możemy poprzestać na zadowoleniu się pierwszym rozwiązaniem, które nam przyjdzie do głowy, a częściej - które w pewien sposób wypracujemy. Pojawia się jednak pytanie: czy otrzymana decyzja jest jedyną możliwą, czy nie istnieją decyzje lepsze? Poszukując decyzji najlepszej, możemy iść drogą bardziej skomplikowaną. Najpierw tworzymy wiele wariantów decyzji, a potem wybieramy jeden z nich. Decyzję końcową wybieramy spośród wariantów dopuszczalnych, czyli tych, które spełniają wszystkie warunki ograniczające.
Możliwe jest przy tym wprowadzenie takiego języka, który pozwoli mówić o podejmowaniu decyzji bez wspominania o szczegółach dotyczących konkretnych problemów decyzyjnych. Językiem tym jest język modelowania matematycznego. Model jest pojęciem bardzo ogólnym, używanym w różnych dziedzinach. Celem tworzenia wszelkich modeli jest dążenie do zrozumienia otaczającej nas rzeczywistości, a także do pokonania problemów związanych z jej niezwykłą złożonością. Modelem matematycznym nazywamy zbiór symboli i relacji matematycznych oraz ścisłych zasad operowania nimi, przy czym zawarte w modelu symbole i relacje mają interpretację odnoszącą się do konkretnych elementów modelowanego wycinka rzeczywistości.

Decyzje gospodarcze należą do tych decyzji, których konsekwencje rozpatrujemy w kategoriach zysków i strat. Dlatego też zanim je podejmiemy, dokonujemy analizy sytuacji, ustalamy kryteria wyboru decyzji i poszukujemy rozwiązań optymalnych. Pomocne wówczas okazują się metody badań ilościowych prawidłowości występujących w zjawiskach ekonomicznych. Wspólną ich cechą jest wykorzystanie narzędzi matematycznych do prowadzenia analiz zjawisk i procesów gospodarczych, a także wnioskowanie na podstawie odpowiednio skonstruowanych modeli.

Do wspomnianych powyżej metod ilościowych należą badania operacyjne. Termin ten na pewno nie w pełni oddaje istotę i treść tej dziedziny wiedzy, a często prowadzi do mylnych skojarzeń. Kiedy autor niniejszej pracy podczas wizyty w Ameryce Północnej przekraczał granicę między Kanadą i USA i na pytanie o cel swej podróży odpowiedział, że zamierza uczestniczyć w konferencji z zakresu badań operacyjnych, celnik ze zrozumieniem pokiwał głową i stwierdził: "A, to pan jest chirurgiem".

Historia tej dziedziny wiedzy sięga do pierwszych modeli programowania matematycznego, sformułowanych przez XVIII-wiecznych ekonomistów; bardziej skomplikowane modele ekonomiczne zaproponowali przed drugą wojną światową von Neuman i Kantorowicz. Nazwa badania operacyjne zaistniała na dobre w okresie drugiej wojny światowej i związana była ściśle z analizą oraz planowaniem operacji wojskowych. Można więc powiedzieć, że w owym czasie nazwa była trafna.

W okresie od drugiej wojny światowej do dnia dzisiejszego nastąpił gwałtowny rozwój tej dziedziny wiedzy. Zastosowania metod badań operacyjnych znajdujemy obecnie praktycznie w każdej dziedzinie życia. Znakomitą orientację w różnorodności problematyki, w której można zastosować metody badań operacyjnych, daje dwumiesięcznik "International Abstracts in Operations Research", w którym znajdują się streszczenia artykułów, publikowanych w czołowych pismach z tego zakresu.

Budowa modeli i otrzymane na ich podstawie rekomendacje decyzyjne stanowią istotę podejścia charakterystycznego dla badań operacyjnych. W swojej pracy H. Wagner wymienia stadia analizy, które należy uznać za standardowe w przypadku analizy ilościowej (powinna ją poprzedzić dokładna analiza jakościowa).

Należą do nich:

• sformułowanie zadania, 
• budowa modelu, 
• rozwiązanie w języku matematyki, 
• wdrożenie wyników i doskonalenie modelu, 
• interpretacja otrzymanych wyników.

Mimo znacznego upływu czasu przedstawiony powyżej zarys postępowania pozostaje nadal aktualny. Istotnym elementem jest tu rozwiązanie zadania otrzymanego w wyniku analizy problemu. Bardzo często jest to zadanie z zakresu programowania matematycznego, którego istotę stanowi analiza i konstrukcja
algorytmów poszukiwania ekstremów funkcji wielu zmiennych na obszarze ograniczonym.
Do rozwiązania tych zadań konieczne jest zazwyczaj wykorzystanie komputerów, stąd też olbrzymi wpływ na rozwój badań operacyjnych mają postępy w informatyce.

Dziś, kiedy komputery osobiste wykorzystywane są powszechnie, przy czym chyba najczęściej do edycji tekstów, nie pamięta się już o tym, że w początkowym okresie rozwoju komputeryzacji jednym z głównych ich zadań było wykonywanie obliczeń , dla których podstawę stanowiły modele badań operacyjnych. Większość problemów decyzyjnych, które spotykamy w rzeczywistości, prowadzi do zagadnień zbyt dużych i zbyt złożonych, aby można je było rozwiązać na kartce papieru.

Obecnie istnieje wiele programów komputerowych, profesjonalnych i edukacyjnych, pozwalających rozwiązywać te problemy w praktyce, jak i w ramach kształcenia. Jednym z takich pakietów jest zbiór programów pod nazwą Badania operacyjne z komputerem. Wersja 2.01 (2007).

Cel i zakres książki
Książka ta jest podręcznikiem, który przy zachowaniu ścisłości i precyzji wykładu ma w bardzo przystępny sposób wprowadzić początkującego Czytelnika w problematykę badań operacyjnych. Praca przeznaczona jest dla przyszłych ekonomistów i inżynierów - studentów wydziałów zarządzania akademii ekonomicznych, politechnik oraz szkół zarządzania i biznesu. Może być również przydatna dla wszystkich tych osób, które chcą uzyskać podstawowe informacje dotyczące modelowania matematycznego w zarządzaniu.

Do jej zrozumienia wystarczająca jest znajomość matematyki w zakresie szkoły średniej oraz podstawowa wiedza o rozwiązywaniu układów równań liniowych i poszukiwaniu ekstremów funkcji wielu zmiennych. Pomimo że w książce w dużej mierze są rozpatrywane matematyczne aspekty zagadnienia podejmowania decyzji, nie jest to książka dla matematyków. Wskazuje na to sposób prezentacji materiału. Rozważania często rozpoczynają się od przykładu, w trakcie jego rozwiązywania przedstawiane jest intuicyjne uzasadnienie omawianych metod, a w końcu sformułowanie pewnych ogólnych zasad. Naruszony więc został tradycyjny ciąg narracji, wykorzystywany w podręcznikach matematycznych: definicja - twierdzenie - dowód - przykład. Autor ma jednak nadzieję, że będzie to z korzyścią dla Czytelnika niezbyt przywykłego do sformalizowanych rozważań matematycznych. Jednocześnie autor podziela pogląd, że uczący się lepiej zrozumieją metodologię budowy modeli, jeżeli będą mogli łatwo dostrzec strukturę formalną problemu decyzyjnego, stąd też zdecydował się na dokonanie podziału materiału względem podstawowych modeli badań operacyjnych.

W książce najwięcej miejsca poświęcono zagadnieniom programowania liniowego. Oprócz zagadnień związanych z graficzną metodą rozwiązania zadania programowania liniowego, metodą simpleks (prymalną) i sformułowaniem problemu dualnego pojawiają się nieco bardziej zaawansowane zagadnienia dualna metoda simpleks oraz programowanie parametryczne. Dalej omówiono szczególne modele liniowe zadanie całkowitoliczbowe oraz zadanie transportowe, obszernie przedstawiono modele wielokryterialnego programowania liniowego, które niezbyt często pojawiają się w polskich podręcznikach, przedstawiono również najczęściej wykorzystywane wielokryterialne metody dyskretne. Kolejne fragmenty pracy dotyczą podejmowania decyzji w warunkach niepewności i ryzyka, programowania wypukłego, metod zarządzania projektami, programowania sieciowego i programowania dynamicznego. Pokazano także możliwości wykorzystania bardzo popularnych obecnie algorytmów genetycznych.

W poszczególnych rozdziałach omówiono wiele zagadnień, głównie z zakresu zarządzania. Należą do nich m.in. problemy planowania produkcji, diety i rozkroju, wyboru optymalnego wariantu rozwoju mocy produkcyjnych, problemy: transportowo - produkcyjny i minimalizacji pustych przebiegów, wyboru portfela akcji, przeprowadzenia kampanii reklamowej, sterowania zapasami. Pozostałe problemy oraz zadania numeryczne, ilustrujące metody obliczeniowe, znajdują się na dołączonym do książki CD-ROM-ie.