badania operacyjne, USM dzienne, sem. zimowy 2008/2009, lista 4 1
Lista 4 (programowanie liniowe)
Zadanie 1 Przedsiębiorstwo produkuje cztery mieszanki A, B, C i D. Mieszanki A i B są
produktami podstawowymi, powstającymi z trzech surowców: S1, S2 i S3. Poniższa tabela
pokazuje, w jaki sposób surowce te mają być wymieszane a także ceny zbytu produktów A
i B. Zakładamy, że firma może sprzedać po podanych cenach tyle wyrobów ile wytworzy.
Produkt Specyfikacja Cena jednostkowa
co najmniej 20% S1
A co najmniej 40% S2 3 $/kg
nie więcej niż 10% S3
B co najmniej 10% S1 2.5 $/kg
nie więcej niż 30% S3
W celu zagwarantowania terminowych dostaw surowców przedsiębiorstwo zgodziło się
na to, że w rozpatrywanym okresie planowania zakupi pewne, minimalne ilości surowców.
Natomiast fizyczne uwarunkowania urządzeń produkcyjnych ograniczają z góry ilość każ-
dego z surowców jaką można przetworzyć. Oba rodzaje ograniczeń oraz jednostkowe ceny
surowców są podane w poniższej tabeli.
Surowiec Minimum Maksimum Cena jedn.
S1 2000 kg 6000 kg 2.1 $/kg
S2 3000 kg 5000 kg 1.6 $/kg
S3 4000 kg 7000 kg 1.1 $/kg
Z natury procesu produkcji wynika, że tylko pewna część każdego z surowców zużytych
do produkcji produktów A i B wchodzi w skład tych produktów. Reszta (odpady), których
ilość wyraża się każdorazowo poprzez znany współczynnik strat (patrz poniższa tabela),
może być albo zużyta do produkcji wyrobów C i D albo zniszczona na koszt firmy.
A B
S1 0.1 0,2
S2 0.2 0.2
S3 0.4 0.5
Drugorzędny wyrób C otrzymuje się poprzez zmieszanie dowolnych ilości odpadów z
surowców S1, S2 i S3 otrzymanych przy produkcji wyrobu A z oryginalnym surowcem
S1. Przy czym, oryginalny surowiec S1 musi stanowić (wagowo) dokładnie 20% mieszanki.
Podobnie, drugorzędny produkt D otrzymuje się poprzez wymieszanie dowolnych ilości
odpadów z surowców S1, S2 i S3 otrzymanych przy produkcji wyrobu B z oryginalnym
surowcem S2. Przy czym, oryginalny surowiec S2 musi stanowić (wagowo) dokładnie 30%
mieszanki. Przy produkcji produktów C i D nie powstają żadne odpady. Ceny rynkowe
produktów C i D wynoszą odpowiednio 0.6 $/kg i 0.5 $/kg.
Poniższa tabela zawiera koszty zniszczenia odpadów nie zużytych do produkcji wyro-
bów C i D. Koszty te są różne w zależności od pochodzenia odpadów.
A B
S1 0.1 $/kg 0.05 $/kg
S2 0.1 $/kg 0.05 $/kg
S3 0.2 $/kg 0.40 $/kg
badania operacyjne, USM dzienne, sem. zimowy 2008/2009, lista 4 2
Przedsiębiorstwo chce znalez
ć odpowiedz
na następujące pytania. Ile zakupić surowców
S1, S2 i S3? Jaką część każdego z surowców przeznaczyć na produkcję każdego produktu?
Jaką część odpadów z produkcji A i B zniszczyć a jaką przeznaczyć do produkcji wyrobów
drugorzędnych?
S1C
C
S1A OS1C
OS2C
S2A
A
OS3C
S3A
SUROWCE
Odpady niezużyte
S1,S2,S3
LIKWIDACJA
OS1D
S1B
OS2D
S2B
B
OS3D
S3B
S2D D
Zadanie 2 Pan X zarabia na życie kupując i sprzedając kukurydzę. Na dzień 1 stycznia
ma 50 ton kukurydzy i 10000$ gotówki. Pierwszego dnia każdego miesiąca pan X mo-
że kupić kukurydzę po następujących cenach za tonę: styczeń 300$, luty 350$, marzec
400$ i kwiecień 300$. W ostatnim dniu każdego miesiąca pan X może sprzedać kukurydzę
po następujących cenach za tonę: styczeń 250$, luty 400$, marzec 350$ i kwiecień 550$.
Pan X przechowuje kukurydzę w magazynie, który może pomieścić co najwyżej 100 ton.
Musi również mieć gotówkę na pokrycie każdego zakupu kukurydzy na początku miesią-
ca. Skonstruuj i rozwiąż model liniowy maksymalizacji gotówki pana X na koniec kwietnia.
Zadanie 3 W hali fabryki znajdują się 4 maszyny M1, M2, M3, M4 zlokalizowane w punk-
tach o współrzędnych: M1 : (3, 0); M2 : (0, -3); M3 : (-2, 1) i M4 : (1, 4). Należy wyzna-
czyć miejsce lokalizacji nowej maszyny M, której współrzędne lokalizacji oznaczymy przez
x1, x2, w następujących przypadkach:
a) Minimalizuje się sumę odległości nowej maszyny od czterech istniejących maszyn.
Wykorzystać metrykę odległości typu Manhattan np. odległość od punktu (x1, x2)
lokalizacji nowej maszyny do punktu (3, 0) lokalizacji maszyny M1 wynosi: |x1 - 3| +
|x2 - 0|.
b) Ponieważ między nową maszyną a maszynami M1, M2, M3, M4 występują przepły-
wy materiałów o zróżnicowanej wielkości, zmodyfikować problem tak, aby zminima-
lizować sumę ważononych odległości. Za wagi dla maszyn M1, M2, M3, M4 przyjąć
odpowiednio liczby: 5, 7, 3, 1.
c) Załóżmy, że nowa maszyna ma być zlokalizowana w prostokącie
{(x1, x2) : -1 d" x1 d" 1, -1 d" x2 d" 1}.
Sformułować model z a), b) oraz tym dodatkowym ograniczeniem.
d) Założyć, że nowa maszyna ma być zlokalizowana tak, aby odległość od pierwszej ma-
3
szyny nie była większa niż . Sformułuj model przy tym dodatkowym ograniczeniu.
2