lecture 2.pdf

Wykład 1

Badania operacyjne zastosowanie naukowych metod do rozwiązywania pro

blemów zarządzania w celu wspomagania menedżerów w podejmowanie lepszych

decyzji.

I. Obserwaja ) II. Sformułowanie problemu ) III. Konstrukcja modelu )

IV. Rozwiązanie modelu ) V. Analiza i implementacja rozwiązania

Przykład:

I. Firma produkuje dwa wyroby W 1 i W 2 z dwóch surowców S 1 i S 2 . Firma

chce zaplanować produkcj¸e tak aby osi¸agn¸ać jak najwi¸ekszy zysk.

II. Zgromadzono nast¸epuj¸ace dane:

– 1 sztuka W 1 zużywa 2 kg S 1 i 1 kg S 2 .

– 1 sztuka W 2 zużywa 1 kg S 1 i 1 kg S 2 .

– Zapas S 1 wynosi 100 kg a zapas S 2 wynosi 80 kg.

– Zysk z 1 sztuki W 1 wynosi 3 zł a zysk z 1 sztuki W 2 wynosi 2 zł.

– Popyt na W 1 wynosi 40 szt. a popyt na W 2 jest nieograniczony.

III. Deﬁniujemyzmiennedecyzyjne x 1 ilośćprodukowanychszt. W 1 , x 2 ilość

produkowanych szt. W 2 . Model matematyczny ma nast¸apuj¸a postać:

MAX z = 3x 1 + 2x 2 [Maksymalizacja zysku]

2x 1 + x 2 100 [Zużycie surowca S 1 ]

x 1 + x 2 80 [Zużycie surowca S 2 ]

x 1 40

[Popyt na W 1 ]

x 1 0

x 2 0

Chcemy wi¸ec znaleźć plan produkcji maksymalizuj¸acy zysk przy posiada

nych zasobach (ograniczeniach).

drinż. AdamKasperski,drM.KulejBadaniaOperacyjne

IV. Stosujemy pewien algorytm (poznany w dalszej cz¸eści wykładu) aby roz

wi¸azać model. Otrzymujemy: x 1 = 20, x 2 = 60 czyli należy produkować 20

szt. wyrobu W 1 i 60 szt. wyrobu W 2 .

Model matematyczny:

MAX(MIN)z = f(x 1 , . . . , x N ) [Funkcja celu]

g 1 (x 1 , . . . , x N ) ( , =)b 1 [Ograniczenie 1]

. . .

g M (x 1 , . . . , x N ) ( , =)b M

[Ograniczenie m]

Zmienne x 1 , . . . , x N nazywamy zmiennymi decyzyjnymi . Rozwi¸azanie spełniaj¸ace

wszystkieograniczenianazywamy rozwi¸azaniemdopuszczalnym .Rozwi¸azaniedo

puszczalne dla którego wartość funkcji celu jest najwi¸eksza (najmniejsza) nazy

wamy rozwi¸azaniem optymalnym .

Funkcj¸epostaci h(x 1 , . . . , x N ) = a 1 x 1 +a 2 x 2 +· · ·+a N x N nazywamy funkcj¸aliniow¸a .

Model w którym wszystkie funkcje f, g 1 , . . . , g M s¸a liniowe nazywamy modelem

liniowym lub zadaniem programowania liniowego .Modelliniowymawi¸ecpostać:

MAX(MIN)z = c 1 x 1 + c 2 x 2 + · · · + c N x N [Funkcja celu]

a 11 x 1 + a 12 x 2 + · · · + a 1N x N ( , =)b 1 [Ograniczenie 1]

. . .

a M1 x 1 + a M2 x 2 + · · · + a MN x N ( , =)b M [Ograniczenie m]

x 1 0, . . . , x R 0, r n

[Ograniczenia na znak]

Specjanymi,wyróżnionymiograniczeniamiliniowymis¸aograniczenianaznakpo

staci x I 0.

Przykłady modeli liniowych

1. Problem ustalania diety . Pan X chce zestawić deser z czterech dań: tortu,

kremuczekoladowego,coliiciastek.Każdedaniezawierapewn¸ailośćkalorii,

czekolady, cukru i tłuszczu (w odpowiednich jednostkach). Ilości te podane

s¸a w poniższej tabeli.

KALORIE CZEKOLADA CUKIER TŁUSZCZ Cena

Tort(1porcja) 400 3 2 2 5zł

Krem(1porcja) 200 2 2 4 2zł

Cola(1butelka) 150 0 4 1 3zł

Ciastko(1szt.) 500 0 4 5 8zł

Pan X musi zjeść posiłek zawieraj¸acy co najmniej: 500 kalorii, 6 jednostek

czekolady, 10 dkg cukru i 8 dkg tłuszczu. Chce przy tym zminimalizować

koszt posiłku.

Zmienne decyzyjne :

drinż. AdamKasperski,drM.KulejBadaniaOperacyjne

• x 1 ilość porcji tortu.

• x 2 ilość porcji kremu.

• x 3 ilość butelek coli.

• x 4 ilość sztuk ciastek.

Model:

MIN z = 5x 1 + 2x 2 + 3x 3 + 8x 4 [Minimalizacja kosztu]

400x 1 + 200x 2 + 150x 3 + 500x 4 500 [Kalorie]

3x 1 + 2x 2 6 [Czekolada]

2x 1 + 2x 2 + 4x 3 + 4x 4 10 [Cukier]

2x 1 + 4x 2 + x 3 + 5x 4 8

[Tłuszcz]

x I 0, i = 1, . . . , 4

[Ograniczenia na znak]

Po rozwi¸azaniu modelu otrzymujemy optymaln¸a diet¸e: 3 porcje kremu i

1 butelk¸e coli (x 1 = 0, x 2 = 3, x 3 = 1, x 4 = 0).

2. Model procesu produkcyjnego Korporacja Rylon wytwarza cztery rodzaje

perfum: Brute, Chanelle, Super Brute i Super Chanelle. Proces produkcji

wygl¸ada nast¸epuj¸aco:

Brute

SuperBrute

sprzedaż

7$/jedn.

14$/jedn.

Materiał

sprzedaż

3$/szt.

sprzedaż

Chanelle

SuperChanelle

sprzedaż

6$/jedn.

10$/jedn.

• z 1 szt. materiału wytwarzane s¸a w ci¸agu 1 godziny 3 jedn. Brute i 4

jedn. Chanelle.

• 1 jedn. Brute jest przetwarzana w ci¸agu 3 godzin w 1 jedn. Super

Brute.

• 1 jedn. Chanelle jest przetwarzana w ci¸agu 2 godzin w 1 jedn. Super

Chanelle.

• Możnazakupićdo4000szt.materiałuiwykorzystaćdo6000h.pracy.

Należy opracowć plan produkcji maksymalizuj¸acy zysk.

Zmienne decyzyjne:

• x 1 liczba sprzedanych jedn. Brute.

• x 2 liczba sprzedanych jedn. Super Brute.

drinż. AdamKasperski,drM.KulejBadaniaOperacyjne

• x 3 liczba sprzedanych jedn. Chanelle.

• x 4 liczba sprzedanych jedn. Super Chanelle.

• x 5 liczba zakupionych szt. materiału.

Model:

MAX z = 7x 1 + 14x 2 + 6x 3 + 10x 4 − 3x 5 [Maksymalizacja zysku]

x 1 + x 2 − 3x 5 = 0

[Produkcja Brute i Super Brute]

x 3 + x 4 − 4x 5 = 0

[Produkcja Chanelle i Super Chanelle]

x 5 4000

[Limit materiału]

3x 2 + 2x 4 + x 5 6000

[Limit pracy]

x I 0, i = 1, . . . , 5

[Ograniczenia na znak]

Porozwi¸azaniumodeluotrzymujemyoptymalnyplanprodukcji:11333.333

jedn. Brute, 666.667 jedn. Super Brute i 16 000 jedn. Chanelle (x 1 =

11333.33, x 2 = 666.667, x 3 = 16000, x 4 = 0, x 5 = 4000). Zysk wynosi

172 666.667 $.

3. Model zapasów . Firma X produkuje pewien wyrób w ci¸agu 4 kwartałów.

Firma chce zminimalizować koszty i zaspokoić popyt. Odpowiednie dane

przedstawione s¸a w poniższej tabeli:

KW I KW II KW III KW IV

Popyt(szt.) 30 60 75 25

Zdolnośćprodukcyjna(szt.) 60 60 60 60

Kosztwytworzenia($/szt.) 55 50 50 55

Kosztmagazynowania($/szt.) 2 2 3

Napoczątkupierwszegoinakońcuczwartegokwartałuﬁrmaniemazapa

sów wyrobu.

Zmienne decyzyjne:

• x I produkcja w itym kwartale, i = 1, . . . 4.

• m I zapasy w itym kwartale, , i = 1, . . . 4.

x 1

m 1

x 2

m 2

x 3

m 3

x 4

drinż. AdamKasperski,drM.KulejBadaniaOperacyjne

Model:

MIN z = 55x 1 + 50x 2 + 50x 3 + 55x 4 + 2m 1 + 2m 2 + 3m 3 [Min. kosztu]

x 1 − m 1 = 30

[Bilans w I kw.]

m 1 + x 2 − m 2 = 60

[Bilans w II kw.]

m 2 + x 3 − m 3 = 75

[Bilans w III kw.]

m 3 + x 4 = 25

[Bilans w IV kw.]

x I 60, i = 1, . . . 4

[Zd. produkcyjne]

x I 0, m I 0, i = 1, . . . , 4

[Ograniczenia na znak]

Po rozwi¸azaniu modelu otrzymujemy: x 1 = 45, x 2 = 60, x 3 = 60, x 4 = 25,

m 1 = 15, m 2 = 15, m 3 = 0.

4. Model inwestycji ﬁnansowych. KorporacjaFincoIvestmentchcezainwesto

wać kwot¸e 100 000 $ w pi¸eć inwestycji A,B,C,D,E. Okres inwestycji trwa

trzy lata. Odpowiednie przepływy ﬁnansowe podane s¸a w poniższej tabeli:

0 1 2 3

A 1$ +0.5$ +1$

B 1$ +0.5$ 1$

C 1$ +1.2$

D 1$ +1.9$

E 1$ +1.5$

NaprzykładinwestycjaAjestdostępnawchwili0,wchwili1(tj.poroku)

otrzymujemy 0.5$ a w chwili 2 (tj.po dwóch latach ) otrzymujemy 1$ za

każdyzainwestowany1$wA.Korporacjatrzymaniezainwestowanepienią

dze w banku na 8% w skali roku. Ponadto nie chce inwestować w żadną

inwestycję więcej niż 75 000 $. Jak zainwestować posiadaną gotówkę aby

zmaksymalizować ilość gotówki na koniec trzeciego roku.

Zmienne decyzyjne:

• x A , x B , x C , x D , x E kwoty ulokowane w odpowiednie inwestycje.

• y 0 , y 1 , y 2 kwoty pozostaj¸ace w banku w chwilach 0, 1 i 2.

Model:

MAX z = x B + 1.9x D + 1.5x E + 1.08y 2 [Max. gotówki w chwili 3]

x A + x C + x D + y 0 = 100000 [Bilans w chwili 0 ]

0.5x A + 1.2x C + 1.08y 0 − x B − y 1 = 0 [Bilans w chwili 1]

x A + 0.5x B + 1.08y 1 − x E − y 2 = 0 [Bilans w chwili 2]

x A , x B , x C , x D , x E 75000

[Limit inwestycji]

x A , . . . , x E , y 0 , y 1 , y 2 0

[Ograniczenia na znak]

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: