Kurs Badania operacyjne.pdf

(2653 KB) Pobierz
Optymalizacja liniowa
. . .
Metody graficzne
Algorytm sympleks
Badania operacyjne
Kurs dla studiów licencjackich zaocznych na
kierunku informatyka w WSB-NLU wspierany
materiałami na CD
Marian Mrozek
Marian.Mrozek@wsb-nlu.edu.pl
Ograniczenia mieszane
Problem minimalizacyjny
Analiza
. . .
Problem dualny
Zagadnienie transportowe
Zagadnienie rozdziału
. . .
Programowanie
. . .
Metody sieciowe
Metoda ścieżki krytycznej
Testy
Bogdan Batko
bbatko@wsb-nlu.edu.pl
MMrozek
&
BBatko
Strona tytułowa
Strona
1
z
138
Powrót
Pełny ekran
Zamknij
Wyjdź
1.
1.1.
Optymalizacja liniowa - przykłady
Model programowania liniowego
Optymalizacja liniowa
. . .
Metody graficzne
Algorytm sympleks
Ograniczenia mieszane
W procesie produkcji zwykle spotykamy się z koniecznością podejmowania decyzji w wa-
runkach utrudnianych dodatkowo przez pewne ograniczenia (np. zasób surowców, zatrud-
nienie, kapitał, itp.). Zadaniem menedżera jest taka alokacja ograniczonych dóbr, by op-
tymalizować wybrany parametr (np. maksymalizować zysk, minimalizować koszty, maksy-
malizować wykorzystanie systemu, itp.). Problemy takie często można modelować progra-
mami liniowymi. Technika rozwiązywania takich zagadnień nazywa się
programowaniem
liniowym (linear programming LP)
. Ojcem tej teorii jest George Danzing (1947),
który opracował algebraiczny sposób rozwiązywania zagadnień optymalizacji liniowej. Dziś
programowanie liniowe znajduje szerokie zastosowania (również poza zarządzaniem). W
praktyce do obliczeń wykorzystuje się komputery. Zatem, jeżeli zagadnienie ma charakter
liniowy i potrafimy zbudować jego model matematyczny, to rozwiązanie jest natychmias-
towe.
1.2.
Przykłady modeli liniowych
Problem minimalizacyjny
Analiza
. . .
Problem dualny
Zagadnienie transportowe
Zagadnienie rozdziału
. . .
Programowanie
. . .
Metody sieciowe
Metoda ścieżki krytycznej
Testy
MMrozek
&
BBatko
Strona tytułowa
W tym paragrafie zajmiemy się budową modelu matematycznego dla danego problemu.
W przykładach ograniczymy się jedynie do zbudowania modelu, niektóre z nich zostaną
rozwiązane w dalszej części wykładu.
Przykład 1 (krawiec)
Zakład krawiecki szyje spodnie i marynarki. Zbyt na te produkty
jest nieograniczony, natomiast ograniczone są dzienne zasoby materiału, podszewki i siły
roboczej. Zyski jednostkowe i normy zużycia środków produkcji przedstawia tabela:
Strona
2
z
138
Powrót
Pełny ekran
Zamknij
Wyjdź
Optymalizacja liniowa
. . .
Dane jednostkowe
Spodnie Marynarki
Zysk (zł)
30
80
Materiał (m
2
)
2,5
2
Podszewka (m
2
)
–
2
Zatrudnienie (h)
2
4
Ograniczenia środków produkcji przedstawia tablica:
Ograniczenia produkcyjne
Materiał (m
2
)
25
2
Podszewka (m )
12
Zatrudnienie (h)
30
Należy wyznaczyć asortyment produkcji maksymalizujący zysk.
Metody graficzne
Algorytm sympleks
Ograniczenia mieszane
Problem minimalizacyjny
Analiza
. . .
Problem dualny
Zagadnienie transportowe
Zagadnienie rozdziału
. . .
Programowanie
. . .
Metody sieciowe
Metoda ścieżki krytycznej
Testy
MMrozek
&
BBatko
Strona tytułowa
Zapis matematyczny problemu:
x
1
plan. prod. dzienna spodni (szt.)
x
2
plan. prod. dzienna marynarek (szt.)
Zmaksymalizować:
30x
1
+ 80x
2
przy ograniczeniach:
Materiał:
2, 5x
1
+ 2x
2
25m
2
Podszewka:
2x
2
12m
2
Zatrudnienie:
2x
1
+ 4x
2
30h
x
1
0,
x
2
0
Strona
3
z
138
Powrót
Pełny ekran
Zamknij
Wyjdź
Optymalizacja liniowa
. . .
Przykład 2 (stolarz)
Przedsiębiorstwo stolarskie wytwarza stoły i kredensy. Zbyt na
te artykuły jest nieograniczony, natomiast ograniczona jest wielkość zatrudnienia, zasoby
tarcicy i szkła. Zyski jednostkowe i normy zużycia środków produkcji przedstawia tabela:
Dane jednostkowe
Stół
Zysk (zł.)
300
Tarcica (m
3
)
0,3
Szkło (m
2
)
—
Zatrudnienie (w rob. godz.) 9,2
Metody graficzne
Algorytm sympleks
Ograniczenia mieszane
Problem minimalizacyjny
Kredens
200
0,6
2
4
Analiza
. . .
Problem dualny
Zagadnienie transportowe
Zagadnienie rozdziału
. . .
Programowanie
. . .
Metody sieciowe
Ograniczenia zasobów środków produkcji przedstawiono poniżej:
Ograniczenia produkcyjne
Tarcica (m
3
)
24
2
Szkło (m )
40
Zatrudnienie (w rob. godz.
h)
520
Jak powinien wyglądać dzienny asortyment produkcji pozwalający na maksymalizację zys-
ku?
Zapis matematyczny problemu:
Metoda ścieżki krytycznej
Testy
MMrozek
&
BBatko
Strona tytułowa
Strona
4
z
138
Powrót
Pełny ekran
Zamknij
Wyjdź
Optymalizacja liniowa
. . .
Metody graficzne
x
1
plan. prod. dzienna stołów (szt.)
x
2
plan. prod. dzienna kredensów (szt.)
Zmaksymalizować:
300x
1
+ 200x
2
przy ograniczeniach:
Tarcica:
0, 3x
1
+ 0, 6x
2
24m
3
Algorytm sympleks
Ograniczenia mieszane
Problem minimalizacyjny
Analiza
. . .
Problem dualny
Zagadnienie transportowe
Zagadnienie rozdziału
. . .
Programowanie
. . .
Metody sieciowe
Metoda ścieżki krytycznej
Szkło:
2x
2
40m
2
Zatrudnienie:
9, 2x
1
+ 4x
2
520h
x
1
0,
x
2
0
Przykład 3 (produkcja płatków)
(zob. [2]) Firma produkująca płatki śniadaniowe
rozważa wypuszczenie na rynek nowego produktu. Ma to być mieszanka pszenicy, ryżu i
kukurydzy.
pszenica
Białko(g/oz)
Węglow.(g/oz)
Kalorie/oz
Koszt/oz
4
20
90
$0,03
Dane
ryż kukurydza
2
25
110
$0,05
2
21
100
$0,02
limit
na opak. 12oz
min 27g
min 240g
max 1260cal
Testy
MMrozek
&
BBatko
Strona tytułowa
Strona
5
z
138
Powrót
Pełny ekran
Problem: zminimalizować koszt produkcji opakowania przy spełnieniu wymaganych wa-
runków.
Zapis matematyczny problemu:
Zamknij
Wyjdź

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin