BO-simplex.pdf

(108 KB) Pobierz
Wirtualna kancelaria korepetytorska i konsultacyjna. Usługi edukacyjne przez Internet.
Rozwiązywanie zadań, pisanie prac.
tel. 0 – 44 738 00 00
tel. kom. 799 079 789
e-mail: biuro@wszechwiedza.pl
Zadanie
Rafineria naftowa otrzymała zamówienie na dwa rodzaje specjalnych paliw węglowodorowych X
oraz Y. Zamówienie opiewa na minimum 4 000 galonów paliwa X i minimum 2 400 galonów
paliwa Y. Paliwa te mogą być wytwarzane niezależnie w dwóch procesach: P 1 i P 2 .
W ciągu 1 godziny trwania procesu P 1 zużywa się 1 baryłkę ropy A oraz 3 baryłki ropy B
i otrzymuje 100 galonów paliwa X oraz 30 galonów paliwa Y.
W ciągu 1 godziny trwania procesu P 2 zużywa się 4 baryłki ropy A oraz 2 baryłki ropy B
i otrzymuje 50 galonów paliwa X oraz 40 galonów paliwa Y.
Zasób ropy A wynosi 240 baryłek, a ropy B 180 baryłek.
Zysk z godziny produkcji według procesu P 1 wynosi 200 zł, a koszty 300 zł.
Zysk z godziny produkcji według procesu P 2 wynosi 500 zł, a koszty 600 zł.
Szef produkcji poszukuje takiej kombinacji procesów P 1 i P 2 (tzn. chce ustalić na ile godzin
uruchomić proces P 1 , a na ile P 2 ), aby osiągnąć maksymalny zysk.
Rozwiązanie
Powyższe zadanie możemy przedstawić jako następujące zagadnienie programowania liniowego:
zmienne decyzyjne:
x 1
- ilość godzin trwania procesu P 1 ,
x 2
- ilość godzin trwania procesu P 2 ,
funkcja celu:
f x 1 ,x 2 =200 x 1 500 x 2 max
ograniczenia:
x 1 4 x 2 ≤240
(limit ropy A)
3 x 1 2 x 2 ≤180
(limit ropy B)
100 x 1 50 x 2 ≥4000
(minimum ilości paliwa X)
30 x 1 40 x 2 ≥2400
(minimum ilości paliwa Y)
x 1 ≥0
x 2 ≥0
- warunki nieujemności, ze względu na sensowność rozwiązania.
- 1 -
907106609.087.png 907106609.098.png
 
Wirtualna kancelaria korepetytorska i konsultacyjna. Usługi edukacyjne przez Internet.
Rozwiązywanie zadań, pisanie prac.
tel. 0 – 44 738 00 00
tel. kom. 799 079 789
e-mail: biuro@wszechwiedza.pl
Powyższe zagadnienie rozwiązane zostanie metodą simplex.
W pierwszej kolejności, musimy sprowadzić zagadnienie do tzw. postaci kanonicznej.Dokonujemy
tego likwidując wszystkie nierówności. Likwidujemy je w taki sposób, iż zamieniamy je na
równania, poprzez wprowadzenie zmiennych swobodnych.
Po wprowadzeniu zmiennych swobodnych, nasz układ ograniczeń wygląda następująco:
x 1 4 x 2 s 1 =240
3 x 1 2 x 2 s 2 =180
100 x 1 50 x 2 − s 3 =4000
30 x 1 40 x 2 − s 4 =2400
x 1 ,x 2 ≥0
s 1 ,s 2 ,s 3 ,s 4 ≥0
Powyższych ograniczeń nie można jeszcze wykorzystać bezpośrednio w metodzie simplex, gdyż
zmienne nie generują bazy jednostkowej – zmienne swobodne w równaniu trzecim oraz czwartym
mają znaki ujemne. Aby wygenerować bazę jednostkową, wprowadzamy do tych równań zmienne
sztuczne.
x 1 4 x 2 s 1 =240
3 x 1 2 x 2 s 2 =180
100 x 1 50 x 2 − s 3 t 1 =4000
30 x 1 40 x 2 − s 4 t 2 =2400
x 1 ,x 2 ≥0
s 1 ,s 2 ,s 3 ,s 4 ≥0
t 1 ,t 2 =0
Wprowadzenie zmiennych sztucznych wymusza modyfikację funkcji celu – wprowadzamy do niej
zmienne sztuczne z wagą niekorzystną z punktu widzenia kierunku optymalizacji. W naszym
- 2 -
907106609.119.png 907106609.001.png
 
Wirtualna kancelaria korepetytorska i konsultacyjna. Usługi edukacyjne przez Internet.
Rozwiązywanie zadań, pisanie prac.
tel. 0 – 44 738 00 00
tel. kom. 799 079 789
e-mail: biuro@wszechwiedza.pl
przypadku (maksymalizacja) wprowadzamy je z wagą ujemną (– M , gdzie M jest bardzo dużą liczbą
dodatnią: M ∞). Funkcja celu będzie miała postać:
f x 1 ,x 2 ,s 1 ,s 2 ,s 3 ,s 4 ,t 1 ,t 2 =200 x 1 500 x 2 − Mt 1 − Mt 2 max
Budujemy I tablicę simplex.
I tablica simplex – rozwiązanie początkowe
baza: x B = [ s 1 , s 2 , t 1 , t 2 ]
x T x 1 x 2 s 1 s 2 s 3 s 4 t 1 t 2
x B c j 200
500
0
0
0
0
– M – M
b
240
wyj
240
s 1
0
1
4
1
0
0
0
0
0
s 2
0
3
2
0
1
0
0
0
0
180
60
t 1
– M 100
50
0
0
–1
0
1
0
4000
40
t 2
– M 30
40
0
0
0
–1
0
1
2400
80
z j -130 M -90 M 0
0 MM – M – M -6400 M
200
+130 M
500
Δ j
+90 M 0
0
– M – M 0
0
Kryterium wejścia do bazy spełnia zmienna x 1
– gdyż odpowiada jest największy dodatni
wskaźnik optymalności j . Kryterium wyjścia spełnia zmienna t 1
, gdyż odpowiada jej
najmiejsza dodatnia wartość ilorazów elementów kolumny b przez kolumnę zmiennej wchodzącej
x 1
.
Wobec tego:
wchodzi: x 1
,
wychodzi: t 1
.
- 3 -
907106609.022.png 907106609.033.png 907106609.042.png 907106609.043.png 907106609.044.png 907106609.045.png 907106609.046.png 907106609.047.png 907106609.048.png 907106609.049.png 907106609.050.png 907106609.051.png 907106609.052.png 907106609.053.png 907106609.054.png 907106609.055.png 907106609.056.png 907106609.057.png 907106609.058.png 907106609.059.png 907106609.060.png 907106609.061.png 907106609.062.png 907106609.063.png 907106609.064.png 907106609.065.png 907106609.066.png 907106609.067.png 907106609.068.png 907106609.069.png
 
Wirtualna kancelaria korepetytorska i konsultacyjna. Usługi edukacyjne przez Internet.
Rozwiązywanie zadań, pisanie prac.
tel. 0 – 44 738 00 00
tel. kom. 799 079 789
e-mail: biuro@wszechwiedza.pl
II Tablica simplex
baza: x B = [ s 1 , s 2 , x 1 , t 2 ]
x T x 1 x 2 s 1 s 2 s 3 s 4 t 1 t 2
x B c j 200
500
0
0
0
0
– M – M
b
200
wyj
57,14
s 1
0
0
3,5
1
0
0,01
0
–0,01
0
s 2
0
0
0,5
0
1
0,03
0
–0,03
0
60
120
x 1
200
1
0,5
0
0
–0,01
0
0,01
0
40
80
t 2
– M 0
25
0
0
0,3
–1
–0,3
1
1200
48
+0,3 M – M 8000-
100-
0,3 M M 2
–2 -
z j 200
25 M 0
0
1200 M
+0,3 M – M –2 -
2
400
+25 M 0
Δ j
0
0
0,3 M 0
wchodzi: x 2
,
wychodzi: t 2
.
III Tablica simplex
baza: x B = [ s 1 , s 2 , x 1 , x 2 ]
x T x 1 x 2 s 1 s 2 s 3 s 4 t 1 t 2
x B c j 200
500
0
0
0
0
– M – M
b
32
wyj
228,57
s 1
0
0
0
1
0
0,14
0,032 –0,14
–0,032
s 2
0
0
0
0
1
0,024
0,02
–0,024 –0,02
36
1800
x 1
1
0
0
0
0,02
0,016 –0,02
16
200
800
–0,016
x 2
500
0
1
0
0
0,012 –0,04
0,04
48
—
–0,012
z j 200
500
0
0
2,8
–16
– 2,8
16
27200
2,8 -M –16 –
M
Δ j
0
0
0
0
–2,8
16
wchodzi: s 4
,
wychodzi: s 1
- 4 -
907106609.070.png 907106609.071.png 907106609.072.png 907106609.073.png 907106609.074.png 907106609.075.png 907106609.076.png 907106609.077.png 907106609.078.png 907106609.079.png 907106609.080.png 907106609.081.png 907106609.082.png 907106609.083.png 907106609.084.png 907106609.085.png 907106609.086.png 907106609.088.png 907106609.089.png 907106609.090.png 907106609.091.png 907106609.092.png 907106609.093.png 907106609.094.png 907106609.095.png 907106609.096.png 907106609.097.png 907106609.099.png 907106609.100.png 907106609.101.png 907106609.102.png 907106609.103.png 907106609.104.png 907106609.105.png 907106609.106.png 907106609.107.png 907106609.108.png 907106609.109.png 907106609.110.png 907106609.111.png 907106609.112.png 907106609.113.png 907106609.114.png 907106609.115.png 907106609.116.png 907106609.117.png 907106609.118.png 907106609.120.png 907106609.121.png
 
Wirtualna kancelaria korepetytorska i konsultacyjna. Usługi edukacyjne przez Internet.
Rozwiązywanie zadań, pisanie prac.
tel. 0 – 44 738 00 00
tel. kom. 799 079 789
e-mail: biuro@wszechwiedza.pl
IV Tablica simplex
baza: x B = [ s 4 , s 2 , x 1 , x 2 ]
x T x 1 x 2 s 1 s 2 s 3 s 4 t 1 t 2
x B c j 200
500
0
0
0
0
– M – M
b
228,571
wyj
—
s 4
0
0
0
0
1
–1
7,1429
0,2286
–0,2286
s 2
0
0
1
0
0
31,429
0
1100
-0,1429
0,0286
–0,0286
x 1
200
1
0
0
0
0
11,429
—
-0,1429
0,0114
–0,0114
x 2
500
0
1
0
0
0
57,143
20000
0,29
0,0029
–0,0029
z j 200
500
0
0
0
0,8571
30857,14
114,286
–0,8571
0,8571
-M – M
–
114,286
Δ j
0
0
0
0
0,8571
wchodzi: s 3
,
wychodzi: s 2
V Tablica simplex
baza: x B = [ s 4 , s 2 , x 1 , x 2 ]
x T x 1 x 2 s 1 s 2 s 3 s 4 t 1 t 2
x B c j 200
500
0
0
0
0
– M – M
b
480
wyj
s 4
0
0
0
6
8
0
1
0
–1
s 3
0
0
–5
35
1
0
–1
0
1100
0
x 1
200
1
0
–0,2
0,4
0
0
0
0
24
x 2
500
0
1
0,3
–0,1
0
0
0
0
54
z j 200
500
110
30
0
0
0
0
31800
Δ j
0
0
–110 –30
0
0
– M – M
Wszystkie wskaźniki optymalności są liczbami niedodatnimi a w bazie nie pozostała żadna ze
zmiennych sztucznych, zatem uzyskane w 5. kroku rozwiązanie jest już rozwiązaniem optymalnym.
Rozwiązanie to jest następujące:
{ x 1 =24
x 2 =54
- 5 -
907106609.122.png 907106609.123.png 907106609.124.png 907106609.125.png 907106609.126.png 907106609.127.png 907106609.128.png 907106609.002.png 907106609.003.png 907106609.004.png 907106609.005.png 907106609.006.png 907106609.007.png 907106609.008.png 907106609.009.png 907106609.010.png 907106609.011.png 907106609.012.png 907106609.013.png 907106609.014.png 907106609.015.png 907106609.016.png 907106609.017.png 907106609.018.png 907106609.019.png 907106609.020.png 907106609.021.png 907106609.023.png 907106609.024.png 907106609.025.png 907106609.026.png 907106609.027.png 907106609.028.png 907106609.029.png 907106609.030.png 907106609.031.png 907106609.032.png 907106609.034.png 907106609.035.png 907106609.036.png 907106609.037.png 907106609.038.png 907106609.039.png 907106609.040.png 907106609.041.png
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin