Katedra Algorytmów i Modelowania Systemów

Wydział Elektroniki, Telekomunikacji i Informatyki

Politechniki Gdańskiej

BADANIA OPERACYJNE

Część I - Programowanie liniowe

Materiały pomocnicze do ćwiczeń z przedmiotu „Badania operacyjne”

Literatura:

1. Jacek Błażewicz, Wojciech Celary, Roman Słowiński, Jan Węglarz: Badania     operacyjne dla informatyków. WNT, Warszawa 1983.

2. Saul I. Gass: Programowanie liniowe - Zastosowania. PWN,     Warszawa 1976.

3. Stanisław Krawczyk: Programowanie matematyczne. PWE, Warszawa 1980.

4. Zbigniew Jędrzejczyk, Karol Kukuła, Jerzy Skrzypek, Anna Walkosz: Badania     operacyjne w przykładach i zadaniach. PWN, Warszawa 1997.

WYBRANE  ZASTOSOWANIA  PROGRAMOWANIA LINIOWEGO

1. Zagadnienie o diecie (zadanie o mieszance)

              Mamy do dyspozycji różnych artykułów spożywczych (np. chleb, mięso, owoce) odpowiednio w liczbie   jednostek. Dzienna dieta powinna zapewnić spożycie  składników odżywczych (np. tłuszcze, białko, witaminy) w ilościach nie mniejszych niż jednostek. Znana jest macierz (tablica dietetyczna)

                                          ,

której element oznacza liczbę jednostek i-tego składnika odżywczego wchodzących w skład jednostki j-tego artykułu spożywczego. Znane są również ceny poszczególnych artykułów spożywczych.

              Należy określić, jakie artykuły spożywcze i w jakich ilościach powinny wchodzić w skład diety, aby dieta spełniała powyższe wymagania i aby jej całkowity koszt był najmniejszy.

Zad. 1.1. Dwa gatunki węgla: A i B zawierają zanieczyszczenia fosforem i popiołem. W pewnym procesie przemysłowym potrzeba co najmniej 90 t paliwa zawierającego nie więcej niż 0.03% fosforu i nie więcej niż 4% popiołu. Procent zanieczyszczeń i ceny zakupu poszczególnych gatunków węgla podano w poniższej tablicy.

1.      Jak zmieszać wymienione dwa gatunki węgla, aby uzyskać paliwo o możliwie najniższym koszcie, spełniające wyżej wymienione wymagania?

2.      Czy skład paliwa należy zmienić, jeżeli:

a)      cena gatunku B wzrośnie do 100 zł?

b)     wymagania dotyczące zawartości fosforu i popiołu się nie zmienią, będzie można jednak otrzymać gatunek B (w cenie 80 zł) zawierający 0.03% fosforu i 5% popiołu?

Zad. 1.2. Do karmienia bydła stosuje się między innymi dwa rodzaje kiszonek jako uzupełnienie paszy treściwej. Zasoby kiszonek kształtują się w taki sposób, że w ciągu doby można zużywać 16 kg I rodzaju kiszonki i 10 kg II rodzaju. Obydwa rodzaje kiszonek zawierają dwa istotne dla hodowli składniki, których ilości dostarczone zwierzętom w ciągu doby nie mogą być dowolne. Składnika należy dostarczyć bydłu co najwyżej 3.3 kg, a składnika co najmniej 2.6 kg w ciągu doby. Procentowa zawartość tych składników w obydwu rodzajach kiszonek przedstawia się następująco

Wyznaczyć ilości poszczególnych rodzajów kiszonek, jakie należy dodać do paszy treściwej, aby koszt takiego uzupełnienia był minimalny. Koszt produkcji 1 kg I rodzaju kiszonki wynosi 2 zł, a koszt produkcji 1 kg II rodzaju kiszonki wynosi 5 zł.

2. Zadanie ustalenia optymalnej struktury produkcji

              Firma dysponuje rodzajami czynników wytwórczych (surowce, maszyny, pracownicy) odpowiednio w ilościach jednostek, produkując  wyrobów. Firma powinna produkować nie mniej niż i nie więcej niż jednostek j-tego wyrobu (). Produkcja jednostki j-tego wyrobu daje przedsiębiorstwu zysk równy jednostek pieniężnych.

Znana jest macierz

                                                        ,

której element oznacza liczbę jednostek i-tego czynnika wytwórczego potrzebnych do wytworzenia jednostki j-tego wyrobu. Należy ustalić taki asortyment produkcji firmy (należy obliczyć ile jednostek każdego wyrobu powinna wytwarzać firma), aby produkcja przynosiła firmie maksymalny zysk.

Zad. 2.1. Zakład produkuje dwa wyroby, zużywając do tego celu pewną ilość środków produkcji, z których cztery: energia elektryczna, stal, drewno oraz praca są limitowane.  Zużycie środków produkcji na jednostkę wyrobu oraz zasoby poszczególnych środków produkcji są podane w poniższej tabeli.