| Ćwiczenie 2. Metoda simpleks w planowaniu liniowym |
| Zadanie . Przedsiębiorstwo ma możliwość produkować n rodzajów produkcji. W trakcie ich wytwarzania wykorzystuje trzy różne zasoby: 1 -sprzęt, 2 - surowce, 3 - półwyroby. Przedsiębiorstwo dysponuje pierwszym z zasobów w ilości b1 tys.jednostek, drugim – w ilości b2 ton i trzecim – w ilości b3 tys.sztuk. Dla produkcji jednej jednostki przemysłowej produkcji rodzaju j potrzeba odpowiednio zasobów w ilości: pierwszego - а1j tys.jednostek, drugiego - a2j ton, trzeciego - a3j tys.sztuk (j=1,2... n). Planowy zysk przedsiębiorstwa w realizacji jednej jednostki produkcji rodzaju j (j=1,2, ... n) wynosi сj pieniężnych jednostek. |
|
|
|
|
|
|
|
|
|
|
|
|
| Przykład rozwiązania zadania . Przedsiębiorstwo ma możliwość produkować cztery rodzaje produkcji P1, P2, P3, P4. W trakcie ich wytwarzania wykorzystuje trzy różne zasoby: sprzęt, surowce, półwyroby. Przedsiębiorstwo dysponuje pierwszym z zasobów w ilości b1 tys.sztuk, drugim – w ilości b2 ton i trzecim – w ilości b3 tys.sztuk. Dla produkcji jednej jednostki przemysłowej produkcji rodzaju j (j=1,2,3,4) potrzeba odpowiednio zasobów w ilości: pierwszego - а1j tys.sztuk, drugiego - a2j ton, trzeciego - a3j tys.sztuk (j=1,2,3,4). Planowy zysk przedsiębiorstwa w realizacji jednej jednostki produkcji rodzaju j (j=1,4) wynosi сj pieniężnych jednostek. |
| b1=4,2 b2=3,1 b3=3 a11=1.1 a12=0.90 a13=0.10 a14=2 a21=1.1 a22=0.1 a23=0.2 a24=2.1 a3l=3.1 a32=0.1 a33=0.4 a34=2.7 cl=2 c2=6 c3=2 c4=3. |
|
|
|
|
|
|
|
|
|
|
|
|
| Rozwiązanie. |
| Sformułujemy ekonomiczno – matematyczny model zadania obliczenia optymalnego planu wyprodukowania produktów, gwarantujący przedsiębiorstwu maksymalny zysk oraz minimalne rozchody zasobów. |
| Oznaczymy przez х1, х2, х3 , х4 – ilość jednostek produktów odpowiedniego rodzaju P1, P2, P3, P4 a przez Z – wartość zysku z realizacji tych produktów. Zapiszemy ogólnie wyliczony zysk (celową funkcję) Z – w następującej postaci: |
| Z = c1x1 + c2x2 + c3x3 + c4x4 = 2*x1 + 6*x2 + 2*x3+ 3*x4 |
| Zmienne х1, х2, х3 , х4 muszą spełniać ograniczenia na dysponujące przez przedsiębiorstwo zasoby. |
| Układ ograniczeń będzie miał postać: |
| 1.1*х1 + 0.9*х2 + 0.1*х3 + 2*х4 <= 4.2 |
| 1.1*х1 + 0.1*х2 + 0.2*х3 + 2.1*х4 <= 3.1 |
| 3.1*х1 + 0.1*х2 + 0.4*х3 + 2.7*х4 <= 3 |
| Według treści zadania zmienne х1 , х2 , х3 , х4 nie mogą być ujemne, tj. |
| xj>=0, j=1,2,3,4. |
| Zapisane wyżej relacje tworzą ekonomiczno – matematyczny model zadania. Więc matematyczny model zadania sprowadza się do obliczenia liczbowych wartości х1*, х2*, х3*, х4* zmiennych х1, х2, х3 , х4 spełniających zapisane powyżej nierówności i dla których liniowa funkcja Z osiągnie maksimum. |
| W kanonicznej postaci ZPL możemy zapisać |
| Z = 2*x1 + 6*x2 + 2*x3+ 3*x4 + 0*х5 + 0*х6 + 0*х7 --> max |
| 1.1*х1 + 0.9*х2 + 0.1*х3 + 2*х4 + 1*х5 + 0*х6 + 0*х7 = 4.2 |
| 1.1*х1 + 0.1*х2 + 0.2*х3 + 0*х5 + 1*х6 + 0*х7 = 3.1 |
| 3.1*х1 + 0.1*х2 + 0.4*х3 + 2.7*х4 + 0*х5 + 0*х6 + 1*х7 = 3 |
| xj>=0, j=1,2,3,4,5,6,7, |
| gdzie dodatkowe (bilansowe) nieujemne zmienne х5, х6, х7 oznaczają różnice pomiędzy prawymi a lewymi stronami tych nierówności. |
| Rozwiążemy zadanie metodą Simplex. |
| 1-szy krok. Dla rozwiązania zadania LP w Excel’u wprowadzimy wejściowe dane i dodatkowe zmienne w komórki tak, jak pokazane jest to na rys. W pierwszym wierszu jest zapisana celowa funkcja, kolejne wiersze – to są ograniczenia, ostatni wiersz – to jest indeksowy wiersz. Niektóre elementy indeksowego wiersza są ujemne, dlatego plan (0; 0; 0; 0; 4,2; 3,1; 3) nie jest optymalny. |
| 2-gi krok. Wybieramy najmniejszy ujemny element w indeksowym wierszu (-6) i obliczamy stosunki bi = bi/aij . Z obliczonych stosunków wybieramy najmniejszy. Na przecięciu kolumny i wiersza znajdujemy rozwiązujący element simpleks przekształcenia oraz zmienną, którą będzie wyeliminowana z bazowych (х5) i zmienną wprowadzoną do bazy (х2) |
| W wierszach według reguły prostokąta obliczamy nowe elementy simpleks tabeli. |
| 3-ci krok. Analizujemy indeksowy wiersz otrzymanej simpleks tabeli. Widzimy, że ona nie daje optymalne rozwiązanie. Dlatego musimy powtórzyć krok 2. |
| Ostatecznie w indeksowym wierszu otrzymamy tylko nieujemne elementy. To oznacza, że mamy optymalne rozwiązanie. Jak widać z tabeli, х2*=3,94; х3*=6,53; Zmax=36,69. |
| W arkuszu ZadanieMax jest: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1. Stworzony ekonomiczno – matematyczny model zadania. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wprowadzone zmienne decyzyjne x1, x2, x3, x4 ; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Stworzona funkcja celu Z --> max |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 2. Stworzona postać kanoniczna modelu. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wprowadzone dodatkowe zmienne x5, x6, x7; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Na podstawie postaci kanonicznej modelu tworzymy pierwszą tablicę simpleks. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zmienne produkcyjne |
Zmienne zapasów |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zmienne swobodne (ZS) |
Zmienne bazowe (ZB) |
|
|
|
|
|
|
|
|
|
| n= |
4 |
|
|
|
|
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
bi |
|
|
|
|
|
|
|
|
| b1= |
4,2 |
|
|
|
|
|
Z= |
2 |
6 |
2 |
3 |
0 |
0 |
0 |
|
--> max |
|
bi/aij |
|
|
|
|
|
| b2= |
3,1 |
|
1. |
Ograniczenia |
Zmienne bazowe |
x5 |
(.1) |
1,1 |
0,9 |
0,1 |
2 |
1 |
0 |
0 |
4,2 |
|
|
4,66666666666667 |
<-- min{bi/aij} |
|
|
|
|
| b3= |
3 |
|
|
x6 |
(.2) |
1,1 |
0,1 |
0,2 |
2,1 |
0 |
1 |
0 |
3,1 |
|
|
31 |
|
|
|
|
|
| a11= |
1,1 |
|
|
x7 |
(.3) |
3,1 |
0,1 |
0,4 |
2,7 |
0 |
0 |
1 |
3 |
|
|
30 |
|
|
|
|
|
| a12= |
0,9 |
|
|
Wiersz indeksowy |
zi - ci |
-2 |
-6 |
-2 |
-3 |
0 |
0 |
0 |
0 |
|
|
Tak, przekształcamy dalej |
|
|
|
|
|
| a13= |
0,1 |
|
|
|
|
|
|
D1 |
D2 |
D3 |
D4 |
|
|
|
Do |
|
|
|
|
|
|
|
|
| a14= |
2 |
|
|
|
Oceny w wierszu indeksowym zi-ci |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| a21= |
1,1 |
|
|
|
D0 = c1*b1 + c2*b2 + ... + cm*bm |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| a22= |
0,1 |
|
|
|
Dj = c1*a1j + c2*a2j + ... + cm*amj - cj |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| a23= |
0,2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| a24= |
2,1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| a31= |
3,1 |
|
|
|
|
|
|
ZS |
ZB |
ZS |
ZS |
ZS |
ZB |
ZB |
|
|
|
|
|
|
|
|
|
| a32= |
0,1 |
|
2. |
Ograniczenia |
Zmienne bazowe |
x2 |
(.1) |
1,22222222222222 |
1 |
0,111111111111111 |
2,22222222222222 |
1,11111111111111 |
0 |
0 |
4,667 |
|
|
42 |
|
|
|
|
|
| a33= |
0,4 |
|
|
x6 |
(.2) |
0,977777777777778 |
0 |
0,188888888888889 |
1,87777777777778 |
-0,111111111111111 |
1 |
0 |
2,633 |
|
|
13,9411764705882 |
|
|
|
|
|
| a34= |
2,7 |
|
|
x7 |
(.3) |
2,97777777777778 |
0 |
0,388888888888889 |
2,47777777777778 |
-0,111111111111111 |
0 |
1 |
2,533 |
|
|
6,51428571428571 |
<-- min{bi/aij} |
|
|
|
|
| c1= |
2 |
|
|
Wiersz indeksowy |
zi - ci |
5,33333333333333 |
0 |
-1,33333333333333 |
10,3333333333333 |
6,66666666666667 |
0 |
0 |
28 |
|
|
Tak, przekształcamy dalej |
|
|
|
|
|
| c2= |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| c3= |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| c4= |
3 |
|
|
|
|
|
|
ZS |
ZB |
ZB |
ZS |
ZS |
ZB |
ZS |
|
|
|
|
|
|
|
|
|
|
|
|
3. |
Ograniczenia |
Zmienne bazowe |
x2 |
(.1) |
0,371428571428571 |
1 |
0 |
1,51428571428571 |
1,14285714285714 |
0 |
-0,285714285714286 |
3,943 |
|
|
|
|
|
|
|
|
|
|
|
|
x6 |
(.2) |
-0,468571428571428 |
0 |
0 |
0,674285714285714 |
-0,057142857142857 |
1 |
-0,485714285714286 |
1,403 |
|
|
|
|
|
|
|
|
|
|
|
|
x3 |
(.3) |
7,65714285714286 |
0 |
1 |
6,37142857142857 |
-0,285714285714286 |
0 |
2,57142857142857 |
6,514 |
|
|
|
|
|
|
|
|
|
|
|
|
Wiersz indeksowy |
zi - ci |
15,5428571428571 |
0 |
0 |
18,8285714285714 |
6,28571428571429 |
0 |
3,42857142857143 |
36,686 |
|
|
Nie, mamy rozwiązanie |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rozwiązanie: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2= |
|
|
|
|
|
3,943 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x6= |
|
1,403 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x3= |
|
|
|
|
6,514 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
36,686 |
= Zmax |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Solver |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
x3 |
x4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Plan produkcji: |
|
|
|
|
0 |
3,9428571841861 |
6,51428557938167 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Funkcja celu: |
|
|
|
Z= |
2 |
6 |
2 |
3 |
= |
36,6857142638799 |
= Zmax |
|
Ilość niewykorzysanych zasobów |
|
|
|
|
|
|
|
|
|
|
Ograniczenia: |
|
|
|
(.1) |
1,1 |
0,9 |
0,1 |
2 |
= |
4,20000002370565 |
<= |
4,2 |
0,000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(.2) |
1,1 |
0,1 |
0,2 |
2,1 |
= |
1,69714283429494 |
<= |
3,1 |
1,403 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(.3) |
3,1 |
0,1 |
0,4 |
2,7 |
= |
2,99999995017128 |
<= |
3 |
0,000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zapiszemy model dualny (dwoisty) w postaci algebraicznej: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Model pierwotny (primarny): |
|
|
|
|
|
|
|
|
|
|
Model dualny: |
|
|
|
|
|
|
|
|
|
|
|
|
Funkcja celu |
|
|
|
|
|
|
|
|
|
|
Funkcja celu |
|
|
|
|
|
|
|
|
|
|
|
|
Z= |
2 |
*x1+ |
6 |
*x2+ |
2 |
*x3+ |
3 |
*x4 |
--> max |
|
F= |
4,2 |
*y1+ |
3,1 |
*y2+ |
3 |
*y3 |
--> min |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ograniczenia |
|
|
|
|
|
|
|
|
|
|
Ograniczenia |
|
|
|
|
|
|
|
|
|
|
|
|
(.1) |
1,1 |
*x1+ |
0,9 |
*x2+ |
0,1 |
*x3+ |
2 |
*x4 |
<= |
4,2 |
(o1) |
1,1 |
*y1+ |
1,1 |
*y2+ |
3,1 |
*y3 |
>= |
2 |
|
|
|
|
(.2) |
1,1 |
*x1+ |
0,1 |
*x2+ |
0,2 |
*x3+ |
2,1 |
*x4 |
<= |
3,1 |
(o2) |
0,9 |
*y1+ |
0,1 |
*y2+ |
0,1 |
*y3 |
>= |
6 |
|
|
|
|
(.3) |
3,1 |
*x1+ |
0,1 |
*x2+ |
0,4 |
*x3+ |
2,7 |
*x4 |
<= |
3 |
(o3) |
0,1 |
*y1+ |
0,2 |
*y2+ |
0,4 |
*y3 |
>= |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(o4) |
2 |
*y1+ |
2,1 |
*y2+ |
2,7 |
*y3 |
>= |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
W postaci kanonicznej |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Funkcja celu |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Z= |
2 |
*x1+ |
6 |
*x2+ |
2 |
*x3+ |
3 |
*x4+ |
0 |
*x5+ |
0 |
*x6+ |
0 |
*x7 |
--> max |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ograniczenia |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(.1) |
1,1 |
*x1+ |
0,9 |
*x2+ |
0,1 |
*x3+ |
2 |
*x4+ |
1 |
*x5+ |
0 |
*x6+ |
0 |
*x7 |
= |
4,2 |
|
|
|
|
|
|
|
(.2) |
1,1 |
*x1+ |
0,1 |
*x2+ |
0,2 |
*x3+ |
2,1 |
*x4+ |
0 |
*x5+ |
1 |
*x6+ |
0 |
*x7 |
= |
3,1 |
|
|
|
|
|
|
|
(.3) |
3,1 |
*x1+ |
0,1 |
*x2+ |
0,4 |
*x3+ |
2,7 |
*x4+ |
0 |
*x5+ |
0 |
*x6+ |
1 |
*x7 |
= |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Model dualny: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Funkcja celu |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F= |
4,2 |
*y1+ |
3,1 |
*y2+ |
3 |
*y3 + |
0 |
*y4+ |
0 |
*y5+ |
0 |
*y6 + |
0 |
*y7 |
--> min |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ograniczenia |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(o1) |
1,1 |
*y1+ |
1,1 |
*y2+ |
3,1 |
*y3 + |
-1 |
*y4+ |
0 |
*y5+ |
0 |
*y6 + |
0 |
*y7 |
= |
2 |
|
|
|
|
|
|
|
(o2) |
0,9 |
*y1+ |
0,1 |
*y2+ |
0,1 |
*y3 + |
0 |
*y4+ |
-1 |
*y5+ |
0 |
*y6 + |
0 |
*y7 |
= |
6 |
|
|
|
|
|
|
|
(o3) |
0,1 |
*y1+ |
0,2 |
*y2+ |
0,4 |
*y3 + |
0 |
*y4+ |
0 |
*y5+ |
-1 |
*y6 + |
0 |
*y7 |
= |
2 |
|
|
|
|
|
|
|
(o4) |
2 |
*y1+ |
2,1 |
*y2+ |
2,7 |
*y3 + |
0 |
*y4+ |
0 |
*y5+ |
0 |
*y6 + |
-1 |
*y7 |
= |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zmienne decyzyjne y1, y2, y3 mają sens ceny kupna zasobów (sprzętu, surowców, półwyrobów) dla uruchomienia produkcji P1, P2, P3, P4. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Funkcja celu w modelu dualnym jest koszt zakupu zasobów w ilościach 4,2 , 3,1, 3 cena których wynosi y1, y2, y3 odpowiednio. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ograniczenia pokazują udział w cenach produkcji P1, P2, P3, P4 odpowiedniego zasobu. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Na przykład, w ograniczeniu (o1) cena produkcji P1 składa się z 1,1*y1 - kosztu zasobu pierwszego, 1,1*y2 - kosztu zasobu drugiego, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3,1*y3 - kosztu zasobu trzeciego. Razem cena produkcji P1 powinna być nie niższa niż 2 jednostki pieniężne, oraz zmienna dodatkowa y4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
pokazuję nadwyżkę ceny produkcji P1 nad 2 jednostkami pieniężnymi.. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Analogicznie interpretujemy pozostałe ograniczenia. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dla rozwiązania zadania dualnego wprowadzimy współzależność pomiędzy zmiennymi zadania pierwotnego i dualnego: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
↕ |
↕ |
↕ |
↕ |
↕ |
↕ |
↕ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y4 |
y5 |
y6 |
y7 |
y1 |
y2 |
y3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Z twierdzenia optymalnośći wynika że w punkcie optymalnym |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Fmin = Zmax = |
|
|
36,686 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
oraz |
|
ilość produkcji |
|
|
|
|
nadwyżki ceny produkcji |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ZS |
x1 |
0 |
produkcja P1 |
|
ZB |
y4 |
15,5428571428571 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ZB |
x2 |
3,943 |
produkcja P2 |
|
ZS |
y5 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ZB |
x3 |
6,514 |
produkcja P3 |
|
ZS |
y6 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ZS |
x4 |
0 |
produkcja P4 |
|
ZB |
y7 |
18,8285714285714 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ilości zapasów zasobów |
|
|
|
|
ceny zasobów |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ZS |
x5 |
0 |
sprzęt |
|
ZB |
y1 |
6,28571428571429 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ZB |
x6 |
1,403 |
surowce |
|
ZS |
y2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ZS |
x7 |
0 |
półwyrobe |
|
ZB |
y3 |
3,42857142857143 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zmax= |
36,6857142857143 |
|
|
|
Fmin= |
36,6857142857143 |
|
|
|
|
|
|
|
|
|
|
|
| Zadanie. Zrobić najtańsze menu zawierające n dania (na przykład, ziemniaki, mięso, ...), jeżeli znane jest, że danie |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| pierwsze zawiera a11 materiału pożywnego 1 (na przykład, białku), a21 materiału pożywnego 2 (tłuszczu) i a31 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| materiału pożywnego 3 (witamin), a41 materiału pożywnego 4 (cukru) i jego koszt wynosi c1 pieniężnych jednostek. Analogicznie, danie |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| z numerem i zawiera a1i materiału pożywnego 1, a2i materiału pożywnego 2, a3i materiału |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| pożywnego 3 i a4i materiału pożywnego 4 i jego koszt wynosi ci pieniężnych jednostek. Materiału pożywnego 1 musi |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| być w menu nie mniej niż b1, materiału pożywnego 2 - nie mniej niż b2 , materiału 3 - nie mniej niż b3 , materiału 4 - nie mniej niż b4. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| b1=4,2 b2=3,1 b3=3 a11=1.1 a12=0.90 a13=0.10 a14=2 a21=1.1 a22=0.1 a23=0.2 a24=2.1 a3l=3.1 a32=0.1 a33=0.4 a34=2.7 cl=2 c2=6 c3=2 c4=3. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Rozwiązanie. |
|
|
|
|
|
| Sformułujemy ekonomiczno – matematyczny model zadania obliczenia optymalnego planu wyprodukowania menu, gwarantujący najtańsze koszty oraz maksymalnie zawierające materiały pożywne. |
|
|
|
|
|
| Oznaczymy przez х1, х2, х3 , х4 – ilość jednostek produktów odpowiedniego rodzaju P1, P2, P3, P4 a przez Z – wartość kosztów menu z tych produktów. Zapiszemy ogólnie wyliczony koszty (celową funkcję) Z – w następującej postaci: |
|
|
|
|
|
| Z = c1x1 + c2x2 + c3x3 + c4x4 = 2*x1 + 6*x2 + 2*x3+ 3*x4 |
|
|
|
|
|
| Zmienne х1, х2, х3 , х4 muszą spełniać ograniczenia na zawartość materiałów pożywnych. |
|
|
|
|
|
| Układ ograniczeń będzie miał postać: |
|
|
|
|
|
| 1.1*х1 + 0.9*х2 + 0.1*х3 + 2*х4 >= 4.2 |
|
|
|
|
|
| 1.1*х1 + 0.1*х2 + 0.2*х3 + 2.1*х4 >= 3.1 |
|
|
|
|
|
| 3.1*х1 + 0.1*х2 + 0.4*х3 + 2.7*х4 >= 3 |
|
|
|
|
|
| Według treści zadania zmienne х1 , х2 , х3 , х4 nie mogą być ujemne, tj. |
|
|
|
|
|
| xj>=0, j=1,2,3,4. |
|
|
|
|
|
| Zapisane wyżej relacje tworzą ekonomiczno – matematyczny model zadania. Więc matematyczny model zadania sprowadza się do obliczenia liczbowych wartości х1*, х2*, х3*, х4* zmiennych х1, х2, х3 , х4 spełniających zapisane powyżej nierówności |
|
|
|
|
|
| W kanonicznej postaci ZPL możemy zapisać |
|
|
|
|
|
| Z = 2*x1 + 6*x2 + 2*x3+ 3*x4 + 0*х5 + 0*х6 + 0*х7 --> min |
|
|
|
|
|
| 1.1*х1 + 0.9*х2 + 0.1*х3 + 2*х4 - 1*х5 - 0*х6 - 0*х7 = 4.2 |
|
|
|
|
|
| 1.1*х1 + 0.1*х2 + 0.2*х3 - 0*х5 - 1*х6 - 0*х7 = 3.1 |
|
|
|
|
|
| 3.1*х1 + 0.1*х2 + 0.4*х3 + 2.7*х4 - 0*х5 - 0*х6 - 1*х7 = 3 |
|
|
|
|
|
| xj>=0, j=1,2,3,4,5,6,7, |
|
|
|
|
|
| gdzie dodatkowe (bilansowe) nieujemne zmienne х5, х6, х7 oznaczają różnice pomiędzy prawymi a lewymi stronami tych nierówności. |
|
|
|
|
|
| Ponieważ dodatkowe zmienne zapisane ze znakiem "-", to oni nie mogą tworzyć bazy dla początkowego planu ZPL. Dla rozwiązania wprowadzimy |
|
|
|
|
|
| sztuczne zmienne w1, w2, w3 >=0 ze znakiem "+". |
|
|
|
|
|
| 1.1*х1 + 0.9*х2 + 0.1*х3 + 2*х4 - 1*х5 - 0*х6 - 0*х7 + 1*w1 + 0*w2 + 0*w3 = 4.2 |
|
|
|
|
|
| 1.1*х1 + 0.1*х2 + 0.2*х3 - 0*х5 - 1*х6 - 0*х7 + 0*w1 + 1*w2 + 0*w3 = 3.1 |
|
|
|
|
|
| 3.1*х1 + 0.1*х2 + 0.4*х3 + 2.7*х4 - 0*х5 - 0*х6 - 1*х7 + 0*w1 + 0*w2 + 1*w3= 3 |
|
|
|
|
|
| xj>=0, j=1,2,3,4,5,6,7, w1, w2, w3 >=0. |
|
|
|
|
|
| Funkcja celu ma postać |
|
|
|
|
|
| Z = 2*x1 + 6*x2 + 2*x3+ 3*x4 + 0*х5 + 0*х6 + 0*х7 + M*w1 + M*w2 + M*w3 --> min |
|
|
|
|
|
| gdzie M - dodatnia wartość, dążąca do nieskonczoności (dla zadania maksymalizacji będzie znak "-"). |
|
|
|
|
|
| Rozwiążem zadanie metodą Simplex. |
|
|
|
|
|
| 1-szy krok. Dla rozwiązania zadania LP w Excel’u wprowadzimy wejściowe dane i dodatkowe zmienne w komórki tak, jak pokazane jest to w tablice. W wierszu 2 – im jest zapisana celowa funkcja, wiersze 3-5 – to są ograniczenia, wiersz 6 – to jest indeksowy wiersz. Dla kolumny z numerem obliczma jego według wzoru Di = ScjBazowe*aji. |
|
|
|
|
|
| 2-gi krok. Wybieramy największy dodatni element w indeksowym wierszu M (6,8) i obliczamy stosunki bi = bi/aij (kolumna S). Z obliczonych stosunków wybieramy najmniejszy f (komórka S6). Na przecięciu kolumny I i wiersza 6 znajdujemy rozwiązujący element tablicy simplex. |
|
|
|
|
|
| Dalej prowadzimy przeksztalcenia tablicy simplex (patrz Zadanie ) |
|
|
|
|
|
| Na czwartym kroku w indeksowym M-wierszu mamy tylko ujemne i zerowe wartości. To oznacza, że mamy optymalne rozwiązanie. Jak widać z tabeli, x1* = x2* = x3* = 0; х4*=2,10; Zmin=6,30. |
|
|
|
|
|
| Obliczenie nadwyżki materiałów pożywnych zrobić samodzielnie. |
|
|
|
|
|
|
Rozwiąż zadania metodą simpleks |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Zadanie 1. |
Cukiernia produkuję dwa rodzaje wyrobów: landrynki i fruktynki. |
|
|
|
|
|
|
|
|
|
|
Dla produkcji 1 kg landrynek potrzeba 0,85 kg cukru, 0,23 kg syropu owocowego, 0,21 kg wody i 1,10 kJ energii elektrycznej. |
|
|
|
|
|
|
|
|
|
|
Dla produkcji 1 kg fruktynek potrzeba 0,72 kg cukru, 0,31 kg syropu owocowego, 0,29 kg wody i 1,70 kJ energii elektrycznej. |
|
|
|
|
|
|
|
|
|
|
Ilość cukru i syropu jest limitowana. Cukiernia dziennie nie może zużyć więcej niż 90 kg cukru i 36 kg syropu. |
|
|
|
|
|
|
|
|
|
|
Dzienne zużycie energii elektrycznej nie powinno przekroczyć 195 kJ, a wody - 39 litrów. |
|
|
|
|
|
|
|
|
|
|
Ze sprzedaży 1 kg landrynek cukiernia otrzymuję 12 zł, 1 kg fruktynek - 14 zł. |
|
|
|
|
|
|
|
|
|
|
Wyznacz plan produkcji cukierni w całej ilości kilogramów, przy którym przychód od sprzedaży wyrobów będzie maksymalny. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Zadanie 2. |
Fabryce obuwia potrzeba ze standardowych kawałków skóry wyciąć półwyroby trzech rodzajów (podeszwy, cholewy, dzioby i t.d.) w ilościach nie |
|
|
|
|
|
|
|
|
|
|
mniejszych niż 124, 68 , 112. Każdy kawałek skóry może być przekrojony na kawałki dwoma sposobami. Przy przekroju pierwszym sposobem |
|
|
|
|
|
|
|
|
|
|
otrzymujemy półwyroby każdego rodzaju odpowiednio 6, 4, 7 i 13,5 centymetrów kwadratowych odpadków, 2-im sposobem – |
|
|
|
|
|
|
|
|
|
|
odpowiednio 4, 9, 5 i 16,7 cm.kw. odpadków. |
|
|
|
|
|
|
|
|
|
|
Wyznaczyć ilość kawałków skóry ciętych 1-szym i 2-im sposobem, żeby otrzymać niezbędną ilość półwyrobów oraz żeby |
|
|
|
|
|
|
|
|
|
|
ilość odpadków była minimalna. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Zadanie 3. |
Firma ogrodnicza wytwarza szereg produktów do pielęgnacji trawników, z których najbardziej znanymi są dwa rodzaje nawozów sztucznych. |
|
|
|
|
|
|
|
|
|
|
Każdy z tych nawozów jest mieszanką dwóch składników: A i B. Obecnie firma ma w magazynie zapasy w wysokości 270 kg składnika A i 325 kg |
|
|
|
|
|
|
|
|
|
|
składnika B. Każdy kilogram nawozu pod nazwą Super wymaga zmieszania 0,45 kg składnika A i 0,55 kg B, natomiast każdy kilogram |
|
|
|
|
|
|
|
|
|
|
nawozu pod nazwa Extra wymaga zmieszania 0,72 kg A i 0,28 kg B. Trudności z dostaniem odpowiednich opakowań pojemnością 1 kg nakładają |
|
|
|
|
|
|
|
|
|
|
dodatkowe ograniczenia na wyprodukowaną ilość nawozów Super i Extra, a mianowicie firma nie może wytworzyć więcej niż 120 kg nawozu Super i |
|
|
|
|
|
|
|
|
|
|
140 kg nawozu Extra. Zysk ze sprzedaży każdego z typów nawozu wynosi odpowiednie 11,5 i 14,7 zł/kg. |
|
|
|
|
|
|
|
|
|
|
Zbuduj i rozwiąż zadanie programowania liniowego które pomoże określić plan produkcji nawozów Super i Extra, a również ilości |
|
|
|
|
|
|
|
|
|
|
składników A i B, tak aby zysk ze sprzedaży nawozów był jak największy. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Zadanie 4. |
Pasza dostarczana zwierzętom na fermie powinna zawierać co najmniej 750 g białka, 940 g węglowodanów i 65 g tłuszcza. Ferma dysponuję |
|
|
|
|
|
|
|
|
|
|
dwoma mieszankami pasz: Sianokiszonka i Kukurydzokiszonka. Sianokiszonka zawiera w 1 kg 27 g białka, 18 g węglowodanów i 2 g tłuszczu |
|
|
|
|
|
|
|
|
|
|
i kosztuję 0,25 zł/kg. Kukurydzokiszonka zawiera w 1 kg 19 g białka, 22 g węglowodanów i 1,2 g tłuszczu i kosztuję 0,32 zł/kg. |
|
|
|
|
|
|
|
|
|
|
Wyznacz dawkę pokarmową minimalizującą koszt opasu bydła. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Zadanie 5. |
Przedsiębiorstwo produkuję cztery rodzaje produkcji A, B, C, D z dwóch surowców 1 i 2. |
|
|
|
|
|
|
|
|
|
|
Ceny zakupu surowców oraz zużycie surowców dla jednostki produkcji zapisane są w tablicy. |
|
|
|
|
|
|
|
|
|
|
Również podana minimalna ilość produkcji niezbędna dla opłacalności działania przedsiębiorstwa. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
surowiec 1 |
surowiec 2 |
|
|
|
|
|
|
|
|
Cena surowca za kg |
11,5 |
8,4 |
|
|
|
|
|
|
|
|
Zużycie surowca w jednostce produkcji (kg/szt.) |
|
|
Minimalna ilość produkcji |
|
|
|
|
|
|
|
A |
1,3 |
2,6 |
23 |
|
|
|
|
|
|
|
B |
0,5 |
0,8 |
18 |
|
|
|
|
|
|
|
C |
2,4 |
1,3 |
45 |
|
|
|
|
|
|
|
D |
1,8 |
1,9 |
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wyznacz plan produkcji, minimalizujący koszty zakupu surowców. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Zadanie 6. |
Dla wyprodukowania komod i szaf, fabryka mebli wykorzystuje trzy rodzaje drzewa: dąb, sosnę i brzozę. Jednostkowe koszty zasobów |
|
|
|
|
|
|
|
|
|
|
potrzebne do produkcji jednego wyrobu, zysk ze sprzedaży jednostki produkcji i ogólna ilość zasobów każdego rodzaju produkcji są w tabeli |
|
|
|
|
|
|
|
|
|
|
|
Jednostkowe koszty zasobów potrzebne do produkcji jednego produktu |
Ogólna ilość zasobów, m3 |
|
|
|
|
|
|
|
Zasoby |
komoda |
szafa |
|
|
|
|
|
|
|
Dąb |
0,14 |
0,03 |
3,2 |
|
|
|
|
|
|
|
Brzoza |
0,13 |
0,09 |
1,6 |
|
|
|
|
|
|
|
Sosna |
0,43 |
0,18 |
4,52 |
|
|
|
|
|
|
|
Zysk ze sprzedaży jednego produktu (tys. zł.) |
0,53 |
0,24 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wyznacz plan produkcji, maksymalizujący zysk od sprzedaży mebli. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Zadanie 7. |
Fabryka samochodów osobowych produkuję dwa rodzaje aut: Lanos i Matiz. |
|
|
|
|
|
|
|
|
|
|
Dla produkcji jednego Lanosa potrzeba 400 kg stali, 220 kg metali kolorowych, 2,1 kg farby i 1100 kJ energii elektrycznej. |
|
|
|
|
|
|
|
|
|
|
Dla produkcji jednego Matiza potrzeba 465 kg stali, 310 kg metali kolorowych, 2,9 kg farby i 1700 kJ energii elektrycznej. |
|
|
|
|
|
|
|
|
|
|
Ilość stali, metali kolorowych, farby jest limitowana. FSO dziennie nie może zużyć więcej niż 29000 kg stali, 3600 kg metali kolorowych, 250 kg farby. |
|
|
|
|
|
|
|
|
|
|
Dzienne zużycie energii elektrycznej nie powinno przekroczyć 70000 kJ. |
|
|
|
|
|
|
|
|
|
|
Ze sprzedaży Lanosa FSO otrzymuję 1200 zł, Matiza - 1540 zł. |
|
|
|
|
|
|
|
|
|
|
Wyznacz plan produkcji FSO, przy którym przychód od sprzedaży aut będzie maksymalny. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Zadanie 8. |
Fabryce opakowań potrzeba ze standardowych kawałków plastyku wyciąć kartony czterech rodzaje (dla mleka, śmietany, soku, keczupu) |
|
|
|
|
|
|
|
|
|
|
w ilościach nie mniejszych niż 180, 65, 140, 90.Fabryka ma do cięcia dwie różne maszyny. Na pierwszej maszynie z jednego kawałku wychodzi |
|
|
|
|
|
|
|
|
|
|
odpowiednio 6, 4, 7, 3 kartony i 11,5 centymetrów kwadratowych odpadków, przy krojeniu drugą maszyną – |
|
|
|
|
|
|
|
|
|
|
odpowiednio 4, 7, 7, 5 i 9,7 cm.kw. odpadków. |
|
|
|
|
|
|
|
|
|
|
Wyznaczyć ilość kawałków plastyku ciętych 1-ą i 2-ą maszyną, żeby otrzymać niezbędną ilość półwyrobów oraz żeby |
|
|
|
|
|
|
|
|
|
|
ilość odpadków była minimalna. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Zadanie 9. |
Zużycie energii w ciągu doby człowiekiem zależy od rodzaju jego pracy. Naukowcy podzielili rodzaje pracy w zależności od wysiłku fizycznego na klasy. |
|
|
|
|
|
|
|
|
|
|
Dzienne wyżywienie studenta - to dorsz i kasza greczana (Arkusz Tabela produktów). |
|
|
|
|
|
|
|
|
|
|
Wyznacz najtańsze menu studenta (grupa 2), żeby on dostał w całości witaminy C, B1, B2 i odpowiednią dawkę energii. |
|
|
|
|
|
|
|
|
|
|
Podpowedż. Najpierw oblicz zawartość energii w jednostce wyżywienia. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zużycie człowiekiem energii w ciągu doby |
|
|
|
Podawaną wartość energetyczną oblicza się z zastosowaniem następujących współczynników przeliczeniowych: |
|
Witaminy i minerały, dzienne zalecane spożycie (DZS) |
|
1. słaby fizyczny wysiłek |
3000-3200 kcal |
|
|
węglowodany |
4 |
kcal/g |
|
Witamina C mg |
60 |
|
2. średni fizyczny wysiłek |
3200-3800 kcal |
|
|
białka |
4 |
kcal/g |
|
Tiamina (B1) mg |
1,4 |
|
3. ciężka fizyczna praca |
3800-4200 kcal |
|
|
tłuszcze |
9 |
kcal/g |
|
Ryboflawina (B2) mg |
1,6 |
|
4. bardzo ciężka fizyczna praca |
4200-5000 kcal |
|
|
|
|
|
|
|
|
|
|
|
|
| Produkt |
cena (za kilogram / litr) |
wartość wyżywienia (na 100 gramów produktu) |
witaminy (gramów na 100 gramów produktu) |
|
|
|
|
|
białko |
tłuszcz |
węglowodany |
C |
B1 |
B2 |
|
|
|
| dorsz |
11 |
16 |
0,6 |
0 |
3,2 |
0,1 |
0,2 |
|
|
|
| kasza greczana |
4 |
18 |
3,3 |
62,1 |
0,4 |
0,4 |
0,2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Zadanie 10. |
Kierowca chcę zaoszczędzić na tankowaniu swojego samochodu paliwem do pełna (pojemność zbiornika wynosi 50 litrów). |
|
|
|
|
|
|
|
|
|
|
On ma możliwość tankować benzyną-98, benzyną-95 lub benzyną-76 lub mieszankami tych benzyn. |
|
|
|
|
|
|
|
|
|
|
Dla opłacalności korzystania z różnych benzyn silnik powinien spełniać niektóre warunki na zużycie paliwa na 100 km, |
|
|
|
|
|
|
|
|
|
|
na remont silnika i tp. (patrz tablicę). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
benzyna-98 |
benzyna-95 |
benzyna-76 |
wymagania kierowcy |
|
|
|
|
|
|
zużycie paliwa l/100 km |
5,6 |
7 |
9,3 |
7,8 |
|
|
|
|
|
|
remont wtrysku silnika (przez godzin) |
1000 |
840 |
500 |
700 |
|
|
|
|
|
|
wymiana tłumiku (przez godzin) |
10000 |
8800 |
7000 |
8200 |
|
|
|
|
|
|
cena benzyny (zł/l) |
4,82 |
4,24 |
3,48 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wyznacz plan tankowania auta. |
|
|
|
|
|
|
|
|
|