Akademia Morska w Szczecinie
Wydział Inżynieryjno-Ekonomiczny Transportu

Badania operacyjne

Laboratorium

II ZIP, L02

Szczecin 2013

Badania operacyjne

Przedmiotem badań operacyjnych jest budowa i rozwiązywanie matematycznych modeli decyzyjnych odnoszących się do aspektów działalności prowadzenia firmy np. produkcje, koszty, wydajność, procesy transportowe, modele badań decyzyjnych. W wyniku rozwiązania modelu decyzyjnego otrzymamy rozwiązanie optymalne. Wynika z niego np. co należy produkować, aby firma otrzymała jak największe zyski w danych okolicznościach. Decyzja optymalna to decyzja, która jest decyzją dopuszczalną i jednocześnie jest najlepsza z punktu widzenia kryteriów oceny decyzji.

Podstawy na jakich opierajÄ… siÄ™ badania operacyjne sÄ… dwa warianty racjonalnego gospodarowania:

• Maksymalizacja efektu - firma posiada okreÅ›lone zasoby i zamówienia oraz ilość pracowników, zasoby materiałów, surowców. Należy te Å›rodki jak najlepiej wykorzystać by uzyskać maksymalny zysk.

• Minimalizacja nakÅ‚adu – firma wie co ma produkować, bo otrzymuje zamówienia. Należy je zrealizować po najmniejszych kosztach, bez zamiany parametrów jakoÅ›ciowych.

Metoda Simpleks

Metoda ta pomaga w podjęciu takiej decyzji, która pozwoli przy ograniczonych zasobach osiągnąć maksymalne korzyści (minimalizacja kosztów lub maksymalizacja zysków).

Metoda uniwersalna do rozwiązań liniowych

Założenia:

1. n > m

2. rzÄ…d macierzy A --> r(A)=m

Spośród n wektorów, m jest liniowo niezależnych. Każdy wektor spoza bazy można przedstawić jako kombinację wektorów bazowych.

Istota metody Simplex polega na tym, że znajduje się dowolne, bazowe rozwiązanie dopuszczalnie i sprawdza się czy jest to rozwiązanie optymalne. Sprawdzenie to polega na tym, że bada się czy wprowadzenie dodatkowych zmiennych nie ulepszy rozwiązania. Jeśli nie to rozwiązanie wyjścia jest optymalne. Jeśli natomiast ulepszy to wyznacza się nowe rozwiązanie i bada czy wprowadzone zmienne nie ulepszą tego nowego rozwiązania. Następnie znajdujemy badany wierzchołek i sprawdzamy czy w sąsiedztwie nie ma takiego, który da nam wyższe rozwiązanie funkcji celu. Jeśli nie, to jest to rozwiązanie optymalne.

Zaletą metody Simplex jest to, że do rozwiązania optymalnego dochodzi się najlepiej po n – iteracjach (metodach).

Kryterium optymalności ∆_j

∆_j = Z_j – C_j

Z_j = ∑C_i*Z_ij

i = 1, 2,..., n

j = (m+1, m+2,..., m+2

C_j – współczynnik funkcji celu zmiennych bazowych

Z_ij – współczynnik kombinacji liniowej

A_j = ∑A_iZ_ij

∆j ≥ 0, j = m+1, ..., n (rozwiązanie wyjściowe jest optymalnym)

∆j ≤ 0, Zij ≤ 0 (program jest sprzeczny)

∆j ≤ 0, Zij > 0 (program można ulepszyć)

Sformułowanie problemu transportowego

Problem transportowy występuje wtedy, gdy występuje n–dostawców jednego wyrobu, oraz m–odbiorców tego produktu. Przyjęte oznaczenia są optymalne:

• a_i – wielkość dostawy i = 1,2,… m

• b_j – wielkość zaopatrzenia j= 1,2,3… n

W tym przypadku należy ustalić kryterium, które określi czy rozwiązania są optymalne.

Kryterium tym będzie macierz {C_ij} – macierz kosztów jednostkowych.

Należy ustalić zmienną decyzyjną x_ij, gdzie:

• i – numer dostawcy,

• j – numer odbiorcy

Ekonomiczne sformułowanie problemu polega na właściwym powiązaniu dostawców i odbiorców, tak aby łączne koszty transportu były minimalne.

Ekonomiczne sformułowanie problemu to stworzenie tablicy:

    j i	1	2	...	N	ai
1 2 ... N	X11 X21 ... XN1	X12 X22 ... XN2	... ... ... ...	X1N X2N ... XNN	a1 a2 ... AN
	B1	B2	...	BN	∑Ai = ∑Bj

Następnie tworzona jest macierz kosztów:

	1	2	...	N
1 2 ... N	C11 C21 ... CN1	C12 C22 ... CN2	... ... ... ...	C1n C2n ... CNN

Funkcja celu:

Warunki ograniczajÄ…ce dla dostawcy:

Warunki ograniczajÄ…ce dla odbiorcy:

Warunek bilansowy:

Warunki zbilansowane to inaczej zbilansowane (zamknięte) zagadnienia transportowe, posiadają one rozwiązanie.

Modele sieciowe

Programowanie sieciowe służy do realizacji wielkich przedsięwzięć gospodarczych (budowa statków, remont turbiny, budowa osiedla). Chodzi o to, aby ustalić minimalny czas realizacji przedsięwzięcia.

Zasadniczą cechą zadań sieciowych jest podział analizowanego przedsięwzięcia na części składowe. Proces ten ma charakter kilkustopniowy.

Rodzaje ograniczeń:

1. Ograniczenia strukturalne - wyrażają konieczność respektowania reguł dotyczących poszczególnych operacji. Pytania, na które należy tu odpowiedzieć: jakie operacje powinny być wykonane przed rozpoczęciem badanej operacji? Jakie operacje należy wykonać po zakończeniu badanej operacji? Jakie operacje można wykonać łącznie z badaną operacją?

2. Ograniczenia lokalizujące w czasie - wymagają, aby konkretne czynności odbywały się w przedziale czasu, który jest z góry określony. Rozwiązanie takie jest dyktowane względami praktycznymi, gdyż z reguły realizacja założonych zadań, poza zakreślonym czasem jest niemożliwa lub kosztowna.

3. Ograniczenia wynikające z niesubstytucyjności i niepodzielności zasobów - pewne operacje nie mogą być wykonywane równolegle bądź ze względów technologicznych bądź z powodu zbyt małej liczby pracowników/maszyn.

4. Ograniczenia bilansowe - pewne procesy muszą być tak zorganizowane, aby całkowita liczba pracowników nigdy nie przekroczyła z góry założonych wielkości i nie była niższa od ustalonych limitów. Podobnie jest ze sprzętem.

Metoda CPM (Critical Path Method) to metoda ścieżki krytycznej, która wymaga rozróżnienia dwóch pojęć, czynności i węzłów. Istnieją trzy warunki sieci:

1. Istnieje 1 i tylko 1 węzeł, który nie jest końcem żadnej czynności

2. Istnieje 1 i tylko 1 węzeł, który nie jest początkiem żadnej czynności

3. Nie istniejÄ… cykle

Metoda CPM polega na ustaleniu ścieżki krytycznej, czyli ciągu czynności zależnych od siebie o jak najdłuższym czasie wykonania, będzie to zarazem najkrótszy czas wykonania danego przedsięwzięcia. Aby ustalić tę kolejność, należy pamiętać, że istnieją trzy rodzaje czynności:

1. Które czynności muszą być wykonane przed rozpoczęciem danej czynności

2. Które czynności mogą być wykonane równolegle z daną czynnością

3. Które czynności mogą się zacząć po zakończeniu omawianej czynności

Rozwiązywanie systemów dualnych

Zasady tworzenia programów dualnych:

• W programie dualnym jest tyle zmiennych decyzyjnych ile warunków ograniczajÄ…cych w programie pierwotnym (i odwrotnie).

• Jeżeli w programie pierwotnym funkcja celu jest maksymalizowana, to w programie dualnym jest minimalizowana (i odwrotnie).

• Współczynniki ukÅ‚adu nierównoÅ›ci w programie dualnym sÄ… transpozycjÄ… współczynników nierównoÅ›ci programu podstawowego.

• Współczynniki funkcji celu programu pierwotnego sÄ… wyrazami wolnymi ukÅ‚adu nierównoÅ›ci programu dualnego (i odwrotnie).

• KonstruujÄ…c program dualny należy mienić kierunki nierównoÅ›ci na przeciwne wzglÄ™dem programu pierwotnego.

• Programem dualnym wzglÄ™dem programu dualnego jest program pierwotny.

Interpretacja ekonomiczna: wartość zmiennej dualnej y_i mówi nam o ile zmieni się wartość funkcji celu zadania pierwotnego jeśli wartość wyrazu wolnego b_i wzrośnie o 1 (w określonym przedziale). Wartość zmiennej dualnej y_i nazywana jest także wyceną i-tego środka produkcji. Zakupienie jednostki danego środka produkcji zwiększa nam wartość funkcji celu o y_i (przynosi dodatkową korzyść w tej wysokości), zatem tyle ten środek jest dla nas wart. Jeśli chcielibyśmy go dokupić to opłaca nam się to zrobić po cenie niższej od y_i (wtedy osiągniemy jednostkową korzyść netto wynoszącą y_i minus koszt zakupu jednostki środka produkcji).