BADANIA OPERACYJNE

Program zajęć:

• Zakres badań operacyjnych.

Modelowanie problemów decyzyjnych.

• Programowanie liniowe. Przykłady zadań

decyzyjnych.

• Metoda geometryczna i metoda selekcji.

• Dualność, podstawowe twierdzenia i

przykłady.

• Metoda Simpleks.

• Zagadnienie transportowe.

• Przepływy międzygałęziowe.

Literatura:

Badania operacyjne. Teoria i zastosowania,

pod red. E. Majchrzak, Wydawnictwo
Politechniki Śląskiej, Gliwice 2007

Badania operacyjne pod red. W. Sikory,

PWE Warszawa 2008

Trzaskalik T., Wprowadzenie do badań

operacyjnych z komputerem, PWE
warszawa 2008

• Badania operacyjne w przykładach i

zadaniach, pod red. K. Kukuły, PWN,
Warszawa 2004

Badania operacyjne, pod red. E. Ignasiaka,

Polskie

Wydawnictwo

Ekonomiczne,

Warszawa 2001

Kozubski J. J., Wprowadzenie do badań

operacyjnych, Wydawnictwo Uniwersytetu
Gdańskiego, Gdańsk 1999

Początki badań operacyjnych sięgają okresu

drugiej wojny światowej.

Za ich prekursorów uważa się Leonida

Kantorowicza, jednego z pierwszych

laureatów nagrody Nobla w dziedzinie

ekonomii i Johna von Neumana, twórcę

teorii gier i podstaw informatyki.

Badania operacyjne (operations research) to

kompleksowa dziedzina nauki związana ściśle z

teorią podejmowania decyzji. Umożliwiają za

pomocą modeli matematyczno-ekonomicznych

praktyczne wyznaczenie metodyki rozwiązywania

ś

ciśle określonych problemów związanych z

podejmowaniem optymalnych decyzji w różnych,

konkretnych sytuacjach.

Etapy badań operacyjnych:

1. sformułowanie problemu decyzyjnego

2. budowa modelu matematycznego sytuacji

decyzyjnej

3. pozyskanie i przetwarzanie informacji

wyjściowej niezbędnej do ustalenia

parametrów modelu

4. procedura obliczeniowa lub postępowanie

symulacyjne za pomocą wybranego

algorytmu

5. analiza jakości rozwiązań modelu

6. weryfikacja modelu – sprawdzenie jego

adekwatności

7. wdrożenie rozwiązania

Z uwagi na rodzaj informacji, w badaniach

operacyjnych mamy do czynienia z:

•

modelami deterministycznymi,

•

modelami niedeterministycznymi

•

modelami w warunkach niepewności.

Ze względu na typ relacji zachodzących

między wielkościami, na które decydent ma

wpływ (zmiennymi), wyróżniamy

•

problemy liniowe

•

problemy nieliniowe.

Sytuacje decyzyjne – to sytuacje w których

podejmujemy decyzje

Decydent – to osoba podejmująca decyzję

Warunki w jakich działa decydent, nie

pozwalają na wybór dowolnej decyzji.
Decyzję

zgodną

z

warunkami

ograniczającymi

nazywa

się

decyzją

dopuszczalną.

Decyzja optymalna – to decyzja najlepsza

wybrana z decyzji dopuszczalnych.

Kryterium wyboru (oceny)– to kryterium,

według którego oceniamy decyzje jako
lepsze lub gorsze.

Problem (zagadnienie) decyzyjny - to opis

określonej

sytuacji

decyzyjnej.

Dalej

rozważać będziemy tylko takie sytuacje, w
których warunki ograniczające, kryterium
wyboru i decyzje dają się opisać w języku
matematycznym.

Zapis problemu decyzyjnego w języku

matematycznym to sformułowanie modelu
matematycznego, który będziemy nazywać
zadaniem decyzyjnym.

Rozważamy proces, w którym zmiennymi,

które należy ustalić są

.

Zmienne te nazywamy zmiennymi

decyzyjnymi.

1

2

,

, ....,

n

x

x

x

Rolę kryterium wyboru będzie pełnić pewna

funkcja

Z n zmiennych decyzyjnych

mierząca cel, który chce osiągnąć decydent.

FC:

1

2

1 1

2 2

( ,

,....,

)

.....

n

n n

Z x x

x

c x

c x

c x

=

=

+

+

+

Funkcję Z nazywamy funkcja celu (FC).

gdzie

są znanymi współczynnikami

,

1, 2,.....,

j

c

j

n

=

Proces poddany jest m ograniczeniom, które

zapisujemy w postaci układu równań lub

nierówności:

11 1

12 2

1

1

21 1

22 2

2

2

1 1

2 2

.....

.....

.............................

.....

n n

n n

m

m

mn n

m

a x

a x

a x

b

a x

a x

a x

b

a x

a

x

a

x

b

+

+

+

=

+

+

+

≤

+

+

+

≥

Dopuszczamy jedynie nieujemne wartości

czyli

0,

1, 2,.....,

j

x

j

n

≥

=

,

j

x

Zakładamy również, że prawe strony

ograniczeń są też nieujemne

0,

1, 2,.....,

i

b

i

m

≥

=

Decyzje dopuszczalne to taki układ wartości

zmiennych,

które

spełniają

wszystkie

warunki

opisujące

badaną

sytuację

(rozważany proces).

Zadanie polega więc na maksymalizacji lub

minimalizacji funkcji celu Z spełniającej

zadane ograniczenia i warunki brzegowe.

Tak sformułowane zagadnienie nazywa się

problemem optymalizacji liniowej (POL)

lub zadaniem programowania liniowego

(ZPL) gdyż wszystkie relacje (funkcja celu

i warunki ograniczające) są liniowe oraz

wszystkie zmienne są ciągłe.

Każdy wektor zmiennych decyzyjnych

spełniający warunki ograniczające

nazywamy rozwiązaniem dopuszczalnym

ZPL.

1

2

x=( ,

, ....,

)

n

x

x

x

Rozwiązanie dopuszczalne, dla którego

funkcja celu osiąga maksimum (minimum)

nazywamy rozwiązaniem optymalnym.