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.

	Procentowe zawartości zanieczyszczeń		Cena zakupu 1 tony
Gatunek	fosforu	popiołu	[zł]
A	0.02	3	100
B	0.05	5	80

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:

1. cena gatunku B wzrośnie do 100 zł?

2. 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

	Procentowa zawartość składników w kiszonce
I rodzaj kiszonki	30	20
II rodzaj kiszonki	10	20

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.

	Zużycie środków produkcji na jednostkę wyrobu
	Energia	Stal	Drewno	Praca
Wyrób I	5	5	6	10
Wyrób II	25	10	0	10
Zasoby środków produkcji	1200	600	420	900

Ile poszczególnych wyrobów powinien produkować zakład, aby zysk jego był maksymalny, jeśli zysk jednostkowy wynosi:

- z produkcji wyrobu I 10 zł,

- z produkcji wyrobu II 20 zł ?

Zad. 2.2. Zakład ma możliwość produkowania albo wyrobu A albo wyrobu B, przy czym dziennie może maksymalnie wyprodukować albo 9 sztuk wyrobu A albo 12 sztuk wyrobu B. Wyroby te produkowane są z tego samego podstawowego surowca, którego dzienne zużycie jest ograniczone i wynosi 14 ton; przy czym zużycie jego na jednostkę produktu A wynosi 1 tonę, a na jednostkę produktu B zużywa się go dwa razy więcej.

1. Wyznaczyć optymalny plan produkcji, wiedząc że zysk jednostkowy z tytułu produkcji wyrobu A wynosi 100 zł, a z B - 400 zł. Jednoczesnie ze względu na popyt ilość wyrobu A nie może przekraczać 0.8 ilości wyrobu B.

2. Jak wpłynie na rozwiązanie zniesienie ograniczenia na moc produkcyjną zakładu?

3A. Problem przydziału I

 wyrobów (czynności) można wykonywać na
miejscach produkcji (stanowiskach pracy, maszynach). Zakładamy, że każdy rodzaj wyrobu może być wykonany na każdym miejscu produkcji. Znane są ograniczenia na moce produkcyjne poszczególnych miejsc produkcji
(np. maksymalny dopuszczalny czas pracy) oraz plan wykonania poszczególnych wyrobów
. Ponadto dana jest macierz

,

której element
oznacza koszt (czas) i-tego miejsca produkcji przy wykonywaniu jednostki j-tego wyrobu (wydajność i-tego miejsca produkcji przy wykonywaniu j-tego wyrobu).

Należy zaproponować optymalny przydział zadań produkcyjnych do poszczególnych miejsc produkcji z punktu widzenia jednego z poniższych kryteriów:

1. minimalizacja kosztów (czasu wykonania) zadań planowych,

2. maksymalizacja ilości wykonanych wyrobów.

Zad. 3.1. Park maszynowy w przedsiebiorstwie składa się m.in. z 4 obrabiarek, na których można wykonywać trzy różne czynności. Każdą z czynności można realizować jednocześnie tylko na jednej obrabiarce oraz każda obrabiarka może wykonywać w danym momencie tylko jedną pracę. Określ najlepszy rozdział czynności między obrabiarki tak, aby łączny czas pracy maszyn był minimalny. Czas wykonywania poszczególnych czynności podany jest w poniższej tablicy.

	Czas wykonywania czynności na obrabiarce
Czynności
	5	1	6	4
	4	8	5	3
	7	2	5	6

3B. Problem przydziału II (zagadnienie doboru)

Niech danych będzie
stanowisk i
kandydatów na te stanowiska. Każdy kandydat może być zatrudniony tylko na jednym stanowisku a każde stanowisko może być zajęte tylko przez jednego kandydata. Przydzielenie kandydata
na stanowisko
związane jest z kosztem
. Należy znaleźć takie przyporządkowanie poszczególnych kandydatów do poszczególnych stanowisk, aby łączny koszt był najmniejszy.

Zad. 3.2. MPK zamierza przekształcić cztery warsztaty naprawcze taboru w specjalizowane punkty obsługi czterech typów samochodów osobowych: forda, volkswagena, toyoty i fiata. Dana jest tablica
, której element
oznacza średni czas remontu (w dniach) j-ego typu samochodu w i-tym warsztacie.

	Ford	Volkswagen	Toyota	Fiat
	5	7	8	7
	6	4	7	6
	7	5	6	5
	4	3	5	9

Przydzielić poszczególnym warsztatom remonty wymienionych typów samochodów w taki sposób, aby sumaryczny czas wykonywania remontów był minimalny.

Zad. 3.3. Czterech robotników:
  może produkować cztery wyroby:
. W poniższej tablicy podano nakłady czasu pracy każdego robotnika na jednostkę poszczególnych wyrobów.

Robotnicy
	1	0.5	0.25	2
	2	0.1	0.50	1
	2	0.2	1.00	2
	1	0.5	0.25	0.5

Zakładając, że każdy robotnik będzie produkował tylko jeden wyrób, określić ich przydział optymalny z punktu widzenia:

1. minimalizacji łącznych nakładów czasu pracy,

2. maksymalizacji ilości wyprodukowanych wyrobów (wydajności).

Uwaga: Wydajność jest odwrotnością pracochłonności.

4. Zagadnienie transportowe

dostawców posiada jednorodny towar odpowiednio w ilościach jednostek. Całą masę towarową należy przetransportować do
odbiorców, których zapotrzebowanie odpowiednio wynosi jednostek. Znana jest macierz

,

której element
oznacza koszt transportu jednostki towaru od i-tego dostawcy do j-tego odbiorcy. Należy wyznaczyć taką macierz

,

gdzie
oznacza liczbę jednostek towaru, którą należy przetransportować od i-tego dostawcy do j-tego odbiorcy, aby sumaryczny koszt transportu był najmniejszy.

Zad. 4.1 Trzech dostawców posiada jednorodny towar w ilości
,
,
jednostek. Całą masę towarową należy przetransportować do pięciu odbiorców , których zapotrzebowanie odpowiednio wynosi
,
,
,
,
. Koszty transportu jednostki towaru od poszczególnych dostawców do poszczególnych odbiorców są zestawione w poniższej macierzy

Wyznaczyć minimalny koszt transportu.

Zad. 4.2. Trzy kopalnie:
dostarczają węgiel do pięciu składów opału położonych w różnych miejscowościach. Każdy ze składów może przyjąć 400 t węgla miesięcznie, natomiast możliwości wydobywcze kopalń wynoszą:
,
 i 
po
miesięcznie. Koszty wydobycia 1 t węgla w kopalniach wynoszą odpowiednio: 108, 96 i 102 zł, natomiast jednostkowe koszty transportu w żł za tonę (zależnie od odległości) zawiera poniższa tablica.

	Składy opału
Kopalnie
	14	5	9	24	15
	30	24	11	8	19
	9	22	15	7	18

Ustalić plan przewozu węgla, majacy na celu minimalizację łącznych kosztów wydobycia i transportu węgla.

5. Zadania o optymalnym rozkroju

Zad. 5.1. Tartak otrzymał zamówienie na wykonanie co najmniej 300 kompletów belek. Każdy komplet składa się z 7 belek o długości 0.7 m oraz 4 belek o długości 2.5 m. W jaki sposób powinny być cięte dłużyce o długości 5.2 m, aby odpad powstały w procesie cięcia był minimalny ?

Zad. 5.2. Tartak dysponuje dwoma grupami kłód drewna. Pierwsza grupa składa się z 99 kłód o długości 6.6 m, druga z 60 kłód o długości 4.8 m. Jak należy pociąć te kłody, aby otrzymać maksymalną liczbę kompletów składających się z 2 belek o długości 2.2 m i jednej belki o długości 1.3 m ?

6. Ogólny problem plecakowy

Danych jest n rzeczy każda w nieograniczonej ilości sztuk. Rzecz (jedna sztuka) waży jednostek i ma wartość jednostek pieniężnych. Dana jest ponadto maksymalna pojemność plecaka, wynosząca W jednostek. Należy wyznaczyć liczby sztuk poszczególnych rzeczy , których całkowita waga nie przekracza W i których sumaryczna wartość jest największa spośród wszystkich wypełnień plecaka rzeczami o pojemności nie przekraczającej W.

Ogólny problem plecakowy jest modelem matematycznym rozmaitych zagadnień spotykanych w praktyce, np. załadowanie kontenera, pociągu, promu, samochodu, walizki.

Zad. 6.1. Rozwiązać ogólny problem plecakowy dla przykładu scharakteryzowanego tabelą

	1	2	3	W
	9	6	4
	7	5	3	20

Zad. 6.2. Rozwiązać ogólny problem plecakowy dla przykładu scharakteryzowanego tabelą

	1	2	3	4	5	W
	6	2	5	7	8
	6	1	3	2	4	15

Zad. 6.3. Rozwiązać ogólny problem plecakowy dla przykładu scharakteryzowanego tabelą

	1	2	3	4	W
	6	10	8	4
	5	8	7	3	18

7. Gry macierzowe

Zad. 7.1. Znaleźć rozwiazanie gry macierzowej określonej macierzą

.

Zad. 7.2. Znaleźć rozwiazanie gry macierzowej określonej macierzą

.

Zad. 7.3. Znaleźć rozwiazanie gry macierzowej określonej macierzą

.

Zad. 7.4. Dana jest macierz wypłat
gry macierzowej dwuosobowej

(
jest parametrem).

1. Rozwiązać tę grę przyjmując
   .

2. Dla jakich warości parametru
   istnieją rozwiązania gry w zbiorze strategii czystych?

8. Gry z naturą

Zad. 8.1. Poszukiwanie niesprawności odbiornika radiowego można rozpocząć od jednego z czterech układów: A, B, C, D. W poniższej tabeli podano procent udanych prób uruchomienia odbiorników w określonym czasie w zalezności od kolejności szukania uszkodzeń oraz występowania uczkodzenia

	A	B	C	D
A	80	30	10	25
B	12	90	42	36
C	25	40	85	52
D	10	70	40	95

Ustalić kolejność szukania niesprawności, jeżeli zależy nam, aby:

1. średnia liczba udanych prób była największa,

2. zminimalizować względne straty w stosunku do najlepszego możliwego stanu rzeczy,

3. stosować kryterium Hurwitza dla
   .

9. Zadania rachunkowe

Zad. 9.1. Znaleźć maksimum funkcji

na zbiorze ograniczonym nierównościami

Zad. 9.2. Znaleźć minimum funkcji

na zbiorze ograniczonym nierównościami

Zad. 9.3. Znaleźć maksimum funkcji

na zbiorze ograniczonym nierównościami

Zad. 9.4. Znaleźć maksimum funkcji

na zbiorze ograniczonym nierównościami

Zad. 9.5. Znaleźć minimum funkcji

na zbiorze ograniczonym nierównościami

Zad. 9.6. Znaleźć maksimum funkcji

na zbiorze

- całkowite.

Zad. 9.7. Znaleźć maksimum funkcji

na zbiorze

- całkowite.

Zad. 9.8. Znaleźć maksimum funkcji

na zbiorze

- całkowite.

1

11

---