 |
| - zadania - nauka - konkurs - literatura | |
| - Giro 2004 - Giro 2005 - Giro 2006 - TdF 2004 - TdF 2005 - TdF 2006 - TdF 2007 | |
maslowski.pl > badania operacyjne > nauka > lekcja 1ABC programowania liniowego - ZADANIE PRODUKCYJNE
Na tej stronie znajdziesz treść prostego zadania programowania liniowego oraz jego rozwiązanie „krok po kroku".
TREŚĆ ZADANIA
Zakład produkuje dwa wyroby A i B. Dane dotyczące zużycia surowców, ich zasobów oraz zysków jednostkowych zawarto w tabeli. Ułożyć zadanie programowania liniowego, opisujące plan produkcji, gwarantujący maksymalny zysk, gdy wiemy, że można wytworzyć maksymalnie 4000 ton wyrobu A lub 2000 ton wyrobu B.
| Środki produkcji | A | B | zasoby [w tonach] |
| Stal [kg/tonę wyrobu] | 2 | 4 | 12 |
| Tworzywo sztuczne [kg/tonę wyrobu] | 5 | 2 | 8 |
| Zysk jednostkowy [zł/kg wyrobu] | 2 | 4 | - |
ROZWIĄZANIE
Każde zadanie programowania liniowego składa się z następujących elementów:
- Definicja zmiennych
- Układ ograniczeń
- Funkcja celu (kryterium)
1. DEFINICJA ZMIENNYCH
Każde zadanie programowania liniowego należy rozpocząć od zdefiniowania zmiennych. Podane zadanie jest zadaniem typu "produkcyjnego". W takich zadaniach, w zdecydowanej większości przypadków jako zmienne należy obrać ilości produkowanych poszczególnych wyrobów. Generalnie, prawidłowo zdefinowane zmienne powinny w rozwiązaniu zadania dostarczyć informacji o sposobie postępowania przez przedsiębiorcę (rolnika, inwestora, itp.) bez konieczności wykonywania dodatkowych obliczeń. Zatem, w tym przypadku należy zmienne zdefiniować następująco:
x1 - ilość produkowanego wyrobu A [t]
x2 - ilość produkowanego wyrobu B [t]
Należy obowiązkowo pamiętać o podaniu jednostek w jakich definiuje się zmienne. Podstawowym kryterium doboru jednostek jest to, „aby się dobrze skracało". Zostanie to szczegółowo wyjaśnione w kolejnym kroku.
Należy unikać skrótowego definiowania zmiennych, np. w ten sposób:
x1 - A
x2 - B
Pamiętaj! Tak nie wolno!
2. UKŁAD OGRANICZEŃ
W zadaniach "produkcyjnych" większość ograniczeń dotyczy ilości posiadanych zasobów oraz zdolności produkcyjnych zakładu. Ograniczenie o ilości posiadanej stali (12 t) będzie wyglądało następująco:
2x1 + 4x2 ≤ 12 000
Dlaczego 12 000, a nie 12 jak jest podane w tabeli? Aby nie popełnić błędów, należy zawsze sprawdzić jednostki! Lewa strona powyższej nierówności ma następujące jednostki:
2[kg/t]*x1[t]+4[kg/t]*x2[t],
co po skróceniu (patrz uwaga o tym „aby się dobrze skracało") daje nam jednostkę lewej strony kg. Prawa strona nierówności musi mieć również tę samą jednostkę, a więc należy 12 t podane w tabeli zamienić na 12 000 kg.
Podobnie, uważając na jednostki, tworzymy ograniczenie dotyczące ilości posiadanych tworzyw sztucznych:
5x1 + 2x2 ≤ 8 000
W układzie ograniczeń należy jeszcze uwzględnić informację o maksymalnych zdolnościach produkcyjnych zakładu. Z treści zadania wiemy, że można wytworzyć maksymalnie 4000 ton wyrobu A lub 2000 ton wyrobu B. Informacja ta oznacza, że po wyprodukowaniu 4000 ton wyrobu A nie możemy już w ogóle produkować wyrobu B. Natomiast jeżeli wytworzymy 2000 ton wyrobu B nie możemy już produkować wyrobu A. Możliwe są natomiast wszelkie kombinacje liniowe leżące pomiędzy skrajnymi punktami (4000, 0) i (0, 2000), np (2000, 1000). Nie ma obowiązku również wykorzystywania mocy produkcyjnych zakładu w 100%, czyli możliwe jest również takie rozwiązanie (2000, 0). Wszystkie te przypadki można zawrzeć za pomocą następującej nierówności:
x1/4000 + x2/2000 ≤ 1
Aby układ ograniczeń był pełny, należy go uzupełnić o ograniczenia brzegowe:
x1 ≥ 0
x2 ≥ 0
3. FUNKCJA CELU
W tym zadaniu funkcja celu jest wyjątkowo prosta i nie wymaga wykonywania żadnych dodatkowych obliczeń; będzie ona mówiła o maksymalizacji zysku:
z = 2000x1 + 4000x2 → max
Pamiętajmy, że w tabeli podano zysk z 1 kg produktu, a zmienne zostały zdefiniowane w tonach.
Podsumowując, rozwiązanie całego zadania będzie wyglądało następująco:
x1 - ilość produkowanego wyrobu A [t]
x2 - ilość produkowanego wyrobu B [t]
z = 2000x1 + 4000x2 → max
2x1 + 4x2 ≤ 12 000
5x1 + 2x2 ≤ 8 000
x1/4000 + x2/2000 ≤ 1
x1 ≥ 0, x2 ≥ 0
