Ekonomia matematyczna II

Prowadzący ćwiczenia

mgr inż. Piotr Betlej

Programowanie liniowe - program dualny

Liniowe zagadnienia maksymalizacji i minimalizacji często omawia się jako dwa oddzielne typy problemów. W istocie jednak każde zagadnienie minimalizacji ma odpowiednik w postaci zagadnienia maksymalizacji. Podobnie dla każdego zagadnienia maksymalizacji zawsze istnieje odpowiadające mu zagadnienie minimalizacji. Jedno z tych zagadnień liniowych zazwyczaj jest nazywane zagadnieniem pierwotnym lub prymarnym, a jego odpowiednik zagadnieniem podwójnym lub dualnym. Zagadnienia maksymalizacji i minimalizacji nie są więc tak rozłączne, jak mogło by się wydawać. Ponieważ wartości optymalne funkcji celu w zagadnieniach prymarnym i dualnym są zawsze identyczne, możemy więc rozwiązać to z nich, które jest łatwiejsze.

Zmienne decyzyjne zagadnienia prymarnego oznaczamy przez xj, a zmienne decyzyjne zagadnienia dualnego przez yi.

Struktury zagadnień prymarnego i dualnego są ze sobą powiązane w następujący sposób:

Zagadnienie prymarne:

Zmaksymalizować ∏ = 3x1 + 4x2 + 3x3 MAX

przy warunkach:

oraz x1, x2, x3 >= 0

Zagadnienie dualne:

Zminimalizować ∏* = 12y1 + 42y2 MIN

Przy warunkach:

oraz y1, y2 >= 0

Reguły dotyczące programu dualnego

Program dualny względem programu podstawowego tworzymy wykorzystując następujące reguły:

1. W programie dualnym jest tyle zmiennych decyzyjnych ile warunków ograniczających w programie pierwotnym (i odwrotnie).

2. Jeżeli w programie pierwotnym funkcja celu jest maksymalizowana, to w programie dualnym jest minimalizowana (i odwrotnie).

3. Współczynniki układu nierówności w programie dualnym są transpozycją współczynników nierówności programu podstawowego.

4. Współczynniki funkcji celu programu pierwotnego są wyrazami wolnymi układu nierówności programu dualnego (i odwrotnie).

5. Konstruując program dualny należy mienić kierunki nierówności na przeciwne względem programu pierwotnego.

6. Programem dualnym względem programu dualnego jest program pierwotny.

Rozwiązanie programu pierwotnego, gdy dysponujemy rozwiązaniem programu dualnego, obliczamy z zastosowaniem poniższych reguł:

1. Wartości funkcji celów w rozwiązaniach obu programów są takie same.

2. Jeżeli warunek ograniczający programu dualnego jest w rozwiązaniu optymalnym nie wiążący, to odpowiadająca mu zmienna decyzyjna programu podstawowego przyjmuje wartość 0.

Przykład:

Przedsiębiorstwo produkuje cztery wyroby: W1, W2, W3 i W4. Dwa spośród wielu środków wykorzystywanych w procesie produkcji są limitowane. Limity te wynoszą: na środek pierwszy - 90 000 jednostek, na środek drugi - 120 000 jednostek. Nakłady limitowanych środków na jednostkę produkcji podano w tabeli:

Środki produkcji	Jednostkowe nakłady na produkcję wyrobu				Limit
		W1	W2	W3		W4
I	1	2	1,5	6	90000
II	2	2	1,5	4	120000
Zysk	4,00 zł	6,00 zł	3,00 zł	12,00 zł

Zysk osiągany na jednostce produkcji kształtuje się odpowiednio: 4, 6, 3 i 12zł. Ustalić optymalne rozmiary produkcji poszczególnych wyrobów. Podać łączny zysk zrealizowany przy optymalnym asortymencie produkcji.

Rozwiązanie

Za x­1, x2, x3, x4 oznaczamy liczbę wyrobów W1, W2, W3, W4. Przedstawione zadania możemy przedstawić za pomocą modelu:

1X1 + 2x2 +1,5 x3 + 6x4 <= 90000

2x1 + 2x2 + 1,5x3 + 4x4 <= 120000

X1, x2, x3, x4 >= 0

F(x1,x2,x3,x4) = 4x1 + 6x2 + 3x3 + 12 x4 --- max

Powyższy modele nazywamy programem pierwotnym. Ze względu jednak na dużą liczbę zmiennych zadanie to rozwiązywać będziemy za pomocą programu dualnego względem programu pierwotnego.

Po uwzględnieniu wszystkich zależności program dualny będzie miał postać:

y1 + 1y2 >= 4

2y1 + 2y2 >= 6

1,5y1 + 1,5 y2 >= 3

6y1 + 4y2 >= 12

y1, y2 >= 0

G(y1, y2) = 90000y1 + 120000y2 --- min

Rozwiązując powyższy model metodą graficzną otrzymujemy następujący wynik:

y1 = 2 oraz y2 = 1, G(y1, y2) = 300000

Aby przejść do rozwiązania pierwotnego należy wpierw sprawdzić, które warunki programu dualnego w rozwiązaniu optymalnym są spełnione ostro (z nierównością), a które słabo (zachodzi równość). Po podstawieniu wartości y1 = 2 oraz y2 = 1 stwierdzamy iż warunki (1) oraz (2) są spełnione słabo, a warunki (3) i (4) są spełnione ostro. Stąd wniosek, że zmienne x3 oraz x4 przyjmują wartość zero. Zatem do rozwiązania pozostaje układ równań o dwóch niewiadomych:

X1 + 2x2 = 90000

2x1 + 2x2 = 120000

Rozwiązaniem tego układu są: x1 = 30000 x2 = 30000, F(x1,x2,x3,x4) = 300000

Zadania

1. Gospodarstwo rolne prowadzi hodowlę bydła rogatego. Zwierzętom należy w pożywieniu dostarczyć m.in. składnika odżywczego A w ilości, co najmniej 60 jedn., zawartego w produktach P₁ i P₂ służących jako pasza. Produkty P₁ i P₂ zawierają także pewne ilości składników B i C. Ze względu na szkodliwe działanie tych składników zwierzęta powinny je otrzymywać w ograniczonych ilościach: składnika B co najwyżej 200 jedn., a składnika C co najwyżej 280 jedn. Zawartość interesujących nas składników w poszczególnych produktach oraz ceny produktów podano w tabeli:

Składniki	Zawartość składnika w jedn. produktu
		P1	P2
A	3	3
B	10	4
C	6	9
Ceny produktów (zł)	9	18

Wiedząc ponadto, że w diecie powinno się znaleźć, co najwyżej 10 jedn. produktu P1 określić wielkość zakupu poszczególnych produktów, aby zrealizować wymagania co do składu paszy i aby koszt zakupu produktów był minimalny.

2. W gospodarstwie hodowlanym sporządzana jest mieszanka paszowa dla trzody chlewnej, z dwóch produktów: P₁ i P₂. Mieszanka paszowa ma dostarczyć trzodzie chlewnej pewnych składników odżywczych: S₁, S₂, S₃ w ilościach nie mniejszych niż ustalone minima. Zawartość składników odżywczych w jednostce poszczególnych produktów, ceny produktów a także minimalne ilości składników podano w tabeli:

Składniki	Zawartość składnika w 1 kg produktu		Minimalna ilość składnika
		P1		P2
S1	3	9	27
S2	8	4	32
S3	12	3	36
Cena (w zł)	6	9

1. W jakiej ilości należy kupić produkty P₁ i P₂, aby dostarczyć trzodzie chlewnej wymaganych składników odżywczych i aby koszt był minimalny (rozwiąż zadanie metodą graficzną przedstawiając wizualizację rozwiązania).

2. Oblicz minimalny koszt zakupu.

3. Ustal, w jakim zakresie mogą się zmieniać ceny produktów P₁ i P₂ aby obliczone wielkości zakupu nadal były optymalne.

3. Przedsiębiorstwo produkuje dwa wyroby: W1 i W2. Ograniczeniem w procesie produkcji są zapasy trzech surowców: S1, S2, S3. W tablicy podano jednostkowe nakłady surowców na produkcję wyrobów, zapasy surowców oraz ceny wyrobów.

Surowce	Zużycie surowca w kg na 1 szt. wyrobu		Zapas surowca
		W1		W2
S1	2	1	1000
S2	3	3	2400
S3	1,5	0	600
Cena w zł	30	20

Ustalić rozmiary produkcji wyrobów W1 i W2, które gwarantują maksymalny przychód z ich sprzedaży przy istniejących zapasach surowców. Oblicz, w jakich przedziałach mogą zmieniać się ceny produktów, aby rozwiązanie pozostawało optymalne. Oblicz, w jakich przedziałach mogą zmieniać się zapasy surowca, aby te same warunki ograniczające pozostawały wiążące dla optymalnego rozwiązania.

4. Zakład dziewiarski wyspecjalizował się w produkcji dwóch wyrobów wełnianych: W₁ i W₂. Wąskim gardłem procesu produkcji są maszyny typu r1 i r2. W tabeli podano normy pracy maszyn przy produkcji wyrobów W₁ i W₂ oraz ich zdolności produkcyjne.

Maszyny	Czas pracy maszyn (w godz.) na jednostkę wyrobu		Dopuszczalny czas pracy maszyn w ciągu dnia
		W1	W2
r1	2	1	12
r2	2	2	20

Ustalić plan produkcji zapewniający maksymalny łączny przychód ze sprzedaży. Ceny zbytu: W₁ - 50 zł, W₂ - 75 zł, z tym że uwarunkowania rynkowe dyktują, aby ilość produktu W₁ była 2,5 razy większa od ilości produktu W₂. Oblicz maksymalny przychód.

5. Dyrekcja przedsiębiorstwa rozważa podjęcie produkcji trzech nowych wyrobów: W1, W2, W3. O ewentualnym ograniczeniu produkcji tych wyrobów stanowią zapasy dwóch surowców: S1 i S2. Miesięczne limity surowców wynoszą: S1 - 3600 kg, S2 - 4800 kg. Normy zużycia surowców przy produkcji poszczególnych wyrobów, oraz zyski jednostkowe ze sprzedaży wyrobów podano w tabeli:

Surowce	Zużycie surowców (w kg / 1 szt. wyrobu)
		W1	W2	W3
S1	5	3	0
S2	1	2	4
Zysk jednostkowy (w zł)	10	24	12

1. Które z wyrobów i w jakich ilościach powinno produkować przedsiębiorstwo, by osiągnąć maksimum zysku nie przekraczając limitów zapasów surowców?

2. Zapisz model matematyczny dla powyższego zadania i dla programu dualnego.

3. Oblicz wielkość maksymalnego zysku.

4. Ile wyniesie maksymalny zysk, gdyby okazało się, że uzupełniono zapas surowca S2 i obecnie wynosi on 5000 kg?

6. Punkt usługowy otrzymał zamówienie na wycięcie szyb do 300 jednakowych okien, z tym że na jedno okno składają się 2 szyby typu e₁ oraz 3 szyby typu e₂. Szyby wycina się z jednakowych płyt szklanych i można je wycinać trzema sposobami. Ilość szyb i odpad powstały w procesie wycinania przedstawiono w tabeli:

Szyby	Sposoby cięcia płyty
		I	II	III
e1	6	4	3
e2	0	4	6
Odpad (w kg)	0,6	1,6	1,2

1. Podaj optymalny sposób cięcia płyt szklanych tak, aby łączny odpad powstały przy cięciu był minimalny. W rozwiązaniu wykorzystaj metodę graficzną, przedstawiając wizualizację rozwiązania.

2. Oblicz wielkość minimalnego odpadu.

3. Ile wyniesie minimalny odpad, gdyby okazało się, że zaistniała potrzeba wyprodukowania dodatkowych 50 szyb typu e₁.

Mnożenie macierzy

 

 

Mnożenie macierzy nie jest już taką prostą sprawą. Operacja z początku może wydać się skomplikowana, ale po krótkiej wprawie wykonuje się ją już mnemotechnicznie.

 

Najpierw potrzebujemy zdefiniować sobie iloczyn skalarny dwóch wektorów.

 

Wektorem nazywamy macierz o jednej kolumnie.

 

Iloczynem skalarnym dwóch wektorów nazywamy liczbę która jest sumą iloczynów odpowiednich składowych wektorów.

 




 

 

Mnożenie macierzy jest możliwe dla macierzy o odpowiednich wymiarach.

Jeżeli chcemy przeprowadzić mnożenie AთB to liczba kolumn macierzy A musi być równa liczbie wierzy macierzy B.

Mnożenie macierzy nie jest przemienne tzn. chcąc wykonać mnożenie

BთA liczba kolumn macierzy B musi być równa liczbie wierszy macierzy A.

 

 

Co jest wynikiem mnożenia?

 

 

Wynikiem mnożenia macierzy A_nxmთB_mxk jest macierz C o wymiarze nxk.

 

Czyli po prostu przy mnożeniu macierzy o wymiarach nxm przez macierz o wymiarach kxl

• -         po pierwsze „wewnętrzne” wymiary muszą się zgadzać => m=k

• -         wynikiem jest macierz o wymiarach nxl

 

 

Jaką postać będzie miała macierz C?

 

Otóż każdy element macierzy C - c_ij jest równy iloczynowi skalarnemu i-tego wiersza macierzy stojącej po lewej stronie znaku mnożnie, przez j-tą kolumnę macierzy stojącej po prawej stronie znaku mnożenia.

 

np.

 




 

 

 

Definicja

Iloczynem macierzy A=[a_ij]_nxp przez macierz B=[b_ij]_pxm nazywamy taką macierz C=[c_ij]_nxm piszemy C=AთB, że


dla i=1,2,...,n;j=1,2,...,m

 

W ogólnym przypadku mnożenie macierzy nie jest przemienne, natomiast jeżeli AთB=BთA to macierze A i B nazywamy przemiennymi.

Ekonomia matematyczna II mgr inż. Piotr Betlej

Strona 5/8

---