Definicja i krótki zarys historii
badań operacyjnych (1)
Wykład 1
Część 1 Badania operacyjne - dyscyplina naukowa
uważana najczęściej za jedną z dziedzin
Badania operacyjne
nauk o zarzÄ…dzaniu (ang. management
science), Å‚Ä…czÄ…ca elementy
jako dziedzina wiedzy
" ekonomii,
" matematyki
" naukowych metod organizacji,
.
1
Definicja i krótki zarys historii Definicja i krótki zarys historii
badań operacyjnych (2) badań operacyjnych (3)
a zajmujÄ…ca siÄ™ tworzeniem
Polska nazwa  badania operacyjne jest
tłumaczeniem angielskich terminów
" modeli,
operational research (UK)/operations
" metod,
research (USA). Pochodzi ona od badań
" reguł postępowania
na efektywnością operacji wojskowych
prowadzÄ…cych do podejmowania racjonalnych
(przede wszystkim o charakterze
decyzji.
logistycznym) podczas drugiej wojny
światowej.
Podstawowe pojęcia (1)
Zastosowanie badań
operacyjnych w praktyce
Parametrami modeli matematycznych
Przedmiotem zainteresowania w badaniach
operacyjnych są najczęściej problemy, które, występujących w badaniach operacyjnych
niezależnie od ich szczegółowej natury, można
nazywamy ustalone tzn. niezmienne
scharakteryzować na dwa podstawowe sposoby:
podczas obliczeń liczby oznaczające np.
" maksymalizacja efektywności (maksymalizacja
" parametry techniczne maszyn,
zysku, stosunku przychodów do kosztów,
wydajności procesu produkcyjnego,
" koszty/przychody/zyski jednostkowe,
przepustowości sieci, szybkości obsługi klientów)
" opisane liczbowo wymogi prawne,
" minimalizacja nakładów (minimalizacja kosztów,
zapotrzebowania na towary/usługi,
czasu pracy/podróży, przebytej drogi, zużycia
surowców i energii, minimalizacja ryzyka)
" parametry rozkładów prawdopodobieństwa.
6
Podstawowe pojęcia (2) Podstawowe pojęcia (3)
Poza zmiennymi decyzyjnymi w modelach
Zmienne w modelach matematycznych
matematycznych mogą też pojawić się tzw.
występujących w badaniach operacyjnych
zmienne pomocnicze. Zmienne te nie
nazywa się często zmiennymi decyzyjnymi.
reprezentują wielkości, co do których są
W sensie matematycznym są to zwykłe
podejmowane decyzje opisywane przez
zmienne, a określenie  decyzyjne ma
model. Mogą one służyć do uproszczenia
jedynie na celu podkreślenie faktu, że
zapisu modelu lub być wykorzystywane
oznaczają one wielkości, które, w
przez algorytmy rozwiÄ…zujÄ…ce problem.
przeciwieństwie do parametrów modelu,
można zmieniać (np. wielkość produkcji,
ilość przewiezionych towarów).
7 8
Programowanie liniowe
- definicja słowna
Wykład 1
Programowanie liniowe jest to maksymalizacja lub
Część 2
x1 x2 xn
minimalizacja liniowej funkcji wielu zmiennych , ,& ,
Programowanie liniowe -
(zwanej funkcjÄ… celu), gdy zmienne te podlegajÄ… liniowym
warunkom ograniczającym w postaci równań lub
informacje wstępne
nierówności d", e".
Słowo  liniowy oznacza, iż funkcja celu oraz lewe strony
warunków ograniczających mogą być zapisane jako
x1 x2 xn
parametr_1" + parametr_2" +& + parametr_n"
a prawe strony warunków ograniczających to liczby.
9 10
Programowanie liniowe
Programowanie liniowe
- wyjaśnienie nazwy
- stosowane skróty
Słowo "programowanie" występujące w nazwie Programowanie liniowe jako jeden z rodzajów
 programowanie liniowe (a także w innych optymalizacji jest niekiedy oznaczane skrótem
nazwach poddziedzin badań operacyjnych) nie PL (albo LP od ang. linear programming).
oznacza programowania w sensie tworzenia Konkretny liniowy problem optymalizacyjny
programów komputerowych. Słowo to jest czyli zadanie programowania liniowego jest
używane jako synonim słowa  planowanie oznaczane skrótem ZPL.
(ang. planning) i wywodzi siÄ™ z terminologii
stosowanej w poczÄ…tkach badan operacyjnych w
czasie drugiej wojny światowej.
11 12
Programowanie liniowe - postać ogólna (1) Programowanie liniowe - postać ogólna (2)
c1x1 + c2x2 + ...+ cnxn max/ min
aij ,bi,cj sÄ… to parametry
(funkcja celu)
zadania/modelu programowania liniowego
przy ograniczeniach
xj - sÄ… to zmienne
ai1x1 + ai2x2 + ...+ ainxn d" bi
i =1,2,..., p
zadania/modelu programowania liniowego
ai1x1 + ai2x2 + ...+ ainxn e" bi .&
i = p +1,2,...,q
ai1x1 + ai2x2 + ...+ ainxn = bi & .
i = q +1,2,...,m
(ograniczenia funkcyjne)
x e" 0
j = 1,2,...,n1, n1 d" n
j
(warunki nieujemności zmiennych)
13 14
Czy warunki nieujemności zmiennych są Dlaczego warunki nieujemności zmiennych
liniowymi warunkami ograniczającymi? są  wyróżnione w postaci ogólnej ZPL?
Tak. Każdy warunek nieujemności zmiennej 1. Najważniejsza metoda rozwiązywania
można zapisać następująco: ZPL, tzw. metoda simpleks wymaga
nieujemności zmiennych (gdy któraś z
nich może przyjmować wartości
1x1 + 0x2 +...+ 0xn e" 0
x1 e" 0 Ô!
ujemne, wymagane sÄ… pewne
0x1 +1x2 + ...+ 0xn e" 0
x2 e" 0 Ô!
przekształcenia ZPL).
2. W zastosowaniach praktycznych PL
M
zmienne muszą być najczęściej
xn e" 0 Ô! 0x1 + 0x2 + ...+1xn e" 0
nieujemne, ponieważ opisują wielkości
przyjmujące wartości nieujemne.
15 16
Czy jest możliwe zapisane ogólnej
Programowanie liniowe - postać
postaci ZPL w prostszej postaci?
standardowa dla maksymalizacji
c1x1 + c2x2 + ...+ cnxn max
Tak. Każde ZPL można sprowadzić do postaci zwanej
(funkcja celu)
niekiedy postaciÄ… standardowÄ….
Występują dwa warianty postaci standardowej:
przy ograniczeniach
" z maksymalizacjÄ… funkcji celu i wszystkimi
a11x1 + a12x2 + ...+ a1nxn d" b1
ograniczeniami funkcyjnymi typu d" ;
" z minimalizacjÄ… funkcji celu i wszystkimi
a21x1 + a22x2 + ...+ a2nxn d" b2
ograniczeniami funkcyjnymi typu e".
M
Nierówności w ograniczeniach funkcyjnych typu d"
am1x1 + am2x2 + ...+ amnxn d" bm
w zadaniach maksymalizacji oraz typu e" w zadaniach
minimalizacji nazywane są nierównościami typowymi.
(ograniczenia funkcyjne)
x e" 0 j = 1,2,...,n
j
17 18
(warunki nieujemności zmiennych)
Programowanie liniowe - postać
Zbiór rozwiązań dopuszczalnych zadania
standardowa dla minimalizacji
programowania liniowego - definicja
c1x1 + c2x2 + ...+ cnxn min
n
(funkcja celu)
x = (x1, x2 ,..., xn )" R
Zbiór wszystkich spełniających
wszystkie warunki ograniczajÄ…ce danego zadania
przy ograniczeniach
programowania liniowego nazywamy zbiorem
rozwiązań dopuszczalnych (lub krótko: zbiorem
a11x1 + a12x2 +...+ a1nxn e" b1
dopuszczalnym) D a jego elementy rozwiÄ…zaniami
a21x1 + a22x2 + ...+ a2nxn e" b2
dopuszczalnymi.
M
am1x1 + am2x2 + ...+ amnxn e" bm
(ograniczenia funkcyjne)
x e" 0 j = 1,2,..., n
j
19 20
(warunki nieujemności zmiennych)
Zbiór ograniczony 
Zbiór wypukły - definicja
definicja
Zbiór nazywamy wypukłym, jeżeli dla dowolnych
Zbiór nazywamy ograniczonym,
jeżeli istnieje kula
dwóch punktów należących do tego zbioru, jest w nim
(na płaszczyz
nie koło)
zawarty cały odcinek łączący te punkty.
zawierająca ten zbiór
Zbiór wypukły
Zbiór niewypukły
Zbiór ograniczony Zbiór nieograniczony
  rozciąga się do nieskończoności
21 22
Zbiór rozwiązań dopuszczalnych ZPL  Zbiór rozwiązań dopuszczalnych ZPL 
twierdzenie o kształcie zbioru (1) twierdzenie o kształcie zbioru (2)
Niech n oznacza liczbÄ™ zmiennych
2) zbiorem nieograniczonym:
decyzyjnych. Wtedy z geometrycznego
dla n=2 - nieograniczonym wypukłym
punktu widzenia zbiór rozwiązań
podzbiorem płaszczyzny, którego krawędzie
dopuszczalnych D zadania programowania
są półprostymi i ewentualnie odcinkami;
liniowego może być
dla ne"3 - nieograniczonym wypukłym
1) zbiorem ograniczonym:
podzbiorem przestrzeni n-wymiarowej,
dla n=2 - wielokątem wypukłym;
którego krawędzie są półprostymi i
dla n=3 - wielościanem wypukłym;
ewentualnie odcinkami.
dla n>3 - n-wymiarowym  wielościanem
wypukłym.
23 24
Czy można stwierdzić bez obliczeń, czy
Zbiór rozwiązań dopuszczalnych ZPL 
zbiór dopuszczalny jest ograniczony/
twierdzenie o kształcie zbioru (3)
nieograniczony/pusty?
W ogólnym przypadku jest to niemożliwe.
Dla pewnych zestawów warunków
ograniczających zbiór dopuszczalny D
Jednakże istnieją istotne z praktycznego punktu
widzenia typy ZPL, dla których przy realistycznych
może mieć szczególną postać:
parametrach można orzec, że zbiór dopuszczalny D
" Jest figurą o niższym wymiarze niż
jest niepusty i, odpowiednio, ograniczony albo
wymiar przestrzeni (np. jest wielokÄ…tem
nieograniczony.
lub nieograniczonym podzbiorem
Niekiedy można również stwierdzić bez obliczeń, że
płaszczyzny w przestrzeni 3-wymiarowej),
zbiór dopuszczalny D jest pusty. Można ten fakt
a w szczególności półprostą, odcinkiem
wywnioskować z wartości niektórych parametrów w
czy wręcz pojedynczym punktem. warunkach ograniczających albo z występowania
jednocześnie warunków ograniczających w oczywisty
" Jest zbiorem pustym (przypadek
sposób sprzecznych, jak np.
sprzeczności warunków ograniczających). 25 26
3x1 + 7x2 + 4,1x3 d" 5 3x1 + 7x2 + 4,1x3 e" 8
Jak można stwierdzić, czy dane liczby są
Zbiór rozwiązań dopuszczalnych
rozwiÄ…zaniem dopuszczalnym?
kształt zbioru c.d.
W ogólnym przypadku sprawdzenie czy dane
n
x = (x1, x2 ,..., xn )" R
jest rozwiÄ…zaniem dopuszczalnym
danego zadania programowania liniowego wymaga
Wielokąt wypukły
podstawienia wszystkich powyższych liczb do
Wielokąt niewypukły
wszystkich warunków ograniczających.
Sprawdzenie niektórych warunków takich jak np.
warunki nieujemności zmiennych jest naturalnie
trywialne, ale oczywiście rozbudowane ograniczenia
funkcyjne wymagają szczegółowych obliczeń. Wielościan wypukły
Wielościan niewypukły
Przykłady wielokątów i wielościanów wypukłych i niewy-
27 28
pukłych
Zbiór rozwiązań dopuszczalnych - przykłady
Zbiór rozwiązań dopuszczalnych - przykłady
Przykład 1 - zbiór dopuszczalny jest wielokątem
Przykład 2 - zbiór rozwiązań dopuszczalnych jest
(zbiór ograniczony).
nieograniczonym podzbiorem płaszczyzny
(zbiór nieograniczony).
Zbiór dopuszczalny może mieć taki kształt np. gdy wszystkie
x2
ak1x1 + ak 2x2 e" bk z dodatnimi
ograniczenia funkcyjne mają postać
parametrami
x2
D
D
D
x1
Zbiór rozwiązań dopuszczalnych D dla przypadku n=2.
Zbiór dopuszczalny może mieć taki kształt, gdy wszystkie
ak1x1 + ak 2x2 d" bk z
ograniczenia funkcyjne mają postać
dodatnimi parametrami.
29 30
x1
Zbiór rozwiązań dopuszczalnych-przykłady
Zbiór rozwiązań dopuszczalnych
Przykład 4 - zbiór rozwiązań dopuszczalnych D jest pusty.
Przykład 3 - zbiór dopuszczalny na płaszczyz
nie (czyli w przestrzeni
Taka sytuacja może mieć miejsce, gdy w warunkach ograniczających
2-wymiarowej) jest odcinkiem (czyli jest jednowymiarowy). Zbiór
ak1x1 + ak 2 x2 d" bk oraz
występują wzajemnie się wykluczające nierówności
dopuszczalny może mieć taki kształt np. gdy w modelu występują
a x1 + a x2 = b a x1 + a x2 e" b
ograniczenia  równościowe czyli typu j1 j 2 j . j1 j 2 j .
Zbiór D (odcinek) jest częścią wspólną prostej
x2
a x1 + a x2 = b x2
j1 j 2 j oraz części wspólnej 3 pół-
a x1 + a x2 = bj płaszczyzn (wyznaczonych przez warunki
j1 j 2
nieujemności zmiennych oraz nierówność
ak1x1 + ak 2x2 = bk . Część wspólna w/w 3 półpłasz-
D
czyzn jest oznaczona jako szary trójkąt.
a x1 + a x2 e" bj
j1 j 2
ak1x1 + ak 2 x2 d" bk
ak1x1 + ak 2 x2 d" bk
x1
x1
31 32
RozwiÄ…zanie optymalne zadania Twierdzenie o rozwiÄ…zaniach
programowania liniowego - definicja optymalnych zadania progr. liniowego
Rozwiązaniem optymalnym (lub krótko  rozwiązaniem)
Jeżeli istnieje rozwiązanie optymalne zadania
zadania programowania liniowego nazywamy każdy zbiór
programowania liniowego, to są to współrzędne
n liczb należących do zbioru rozwiązań dopuszczalnych D:
przynajmniej jednego z wierzchołków zbioru
* * *
x* = (x1 , x2,..., xn ) " D
dopuszczalnego D.
c1x1 + c2x2 +...+ cnxn osiÄ…ga maksimum
dla których funkcja celu
Rozwiązaniami optymalnymi ZPL mogą być
albo minimum.
również współrzędne dwóch lub więcej
RozwiÄ…zanie optymalne:
wierzchołków zbioru dopuszczalnego D. Jest to
" istnieje, jeżeli D jest zbiorem ograniczonym.
" może nie istnieć, jeżeli D jest zbiorem nieograniczonym przypadek tzw. rozwiązań wielokrotnych/
" nie istnieje, jeżeli D jest zbiorem pustym
alternatywnych.
Wówczas rozwiązaniami są również współrzędne
*
xi ,i = 1,..., n
Uwaga: Symbole: oznaczajÄ… konkretne liczby
wszystkich punktów (jest ich nieskończenie wiele)
będące rozwiązaniem, a nie zmienne!
położonych pomiędzy w/w punktami.
33 34
Rozwiązania wierzchołkowe
Czy każde ZPL ma rozwiązanie?
i niewierzchołkowe zadania
1. Tak, jeżeli zbiór rozwiązań dopuszczalnych D jest
programowania liniowego - definicja
zbiorem ograniczonym tzn. punktem, odcinkiem,
wielokątem wypukłym, wielościanem wypukłym lub
Rozwiązaniem wierzchołkowym zadania
n-wymiarowym  wielościanem .
programowania liniowego nazywane jest każde
2. Może nie mieć, jeżeli zbiór rozwiązań
rozwiązanie optymalne, które jest
dopuszczalnych D jest zbiorem nieograniczonym
współrzędnymi jednego z wierzchołków
tzn. półprostą, nieograniczonym wypukłym
podzbiorem płaszczyzny lub przestrzeni n-
zbioru dopuszczalnego D.
wymiarowej (n>3), którego krawędzie są półprostymi
Każde inne rozwiązanie optymalne nazywane
i ewentualnie odcinkami. W takim przypadku nie
jest rozwiązaniem niewierzchołkowym
istnieje maksimum (tzn. funkcja celu dąży do +")
albo minimum (tzn. funkcja celu dąży do -").
zadania programowania liniowego.
3. Nie, jeżeli zbiór rozwiązań dopuszczalnych D jest
35 36
zbiorem pustym.
Wnioski z twierdzenia
Ile rozwiązań może mieć ZPL?
o rozwiÄ…zaniach optymalnych ZPL
W praktyce powyższe twierdzenie oznacza, że aby
1. Zero - zawsze gdy zbiór dopuszczalny jest
znalez
ć rozwiązanie ZPL, trzeba sprawdzić wartości
pusty oraz dla niektórych zbiorów
funkcji celu jedynie dla współrzędnych każdego z
nieograniczonych (wtedy funkcja celu dąży do
wierzchołków zbioru dopuszczalnego D tzn.
podstawić współrzędne wierzchołków zbioru
+" albo -" )
dopuszczalnego D do funkcji celu i sprawdzić, dla
którego z wierzchołków zostanie osiągnięte
2. Jedno - gdy zbiór dopuszczalny jest niepusty. maksimum lub minimum.
Takie sprawdzanie może jednak zawieść w przypadku
gdy zbiór dopuszczalny jest nieograniczony, a funkcja
3. Nieskończenie wiele - gdy zbiór dopuszczalny
celu dąży do +" albo -". Metody obliczeniowe
używane w praktyce pozwalają jednak na wykrycie
jest niepusty.
takiej sytuacji. Ponadto, poprawnie przygotowane
modele rzeczywistych sytuacji decyzyjnych niemal
nigdy nie mają nieskończonego max/min.
37 38
Przykład sprawdzania Przykład sprawdzania
dopuszczalności rozwiązań ZPL (1) dopuszczalności rozwiązań ZPL (2)
x2
x2 4x1 +10x2 max
4x1 +10x2 max
3
3
przy ograniczeniach
przy ograniczeniach
3,5x1 + 10x2 d" 23
3,5x1 + 10x2 d" 23
C
C
E
E
x1 d" 2
x1 d" 2 2
2
F
F
x1 e" 0 x2 e" 0
x1 e" 0 x2 e" 0 , B
D
, B
D
x1, x2 -całkowite H 1
x1, x2 -całkowite H 1
G
G
Zbiór dopuszczalny
to czworokÄ…t
o wierzchołkach:
A
A
(0,0), (2,0), (0;2,3) 3 x1
1
0 2
1 3 x1
0 2
oraz (2;1,6).
Podstawienie do warunków ograniczających
2 2
1 e" 0 dopuszcz.
3,5Å"1,8 +10 Å"1 = 23 d" 23 1,8 d" 2 1,8 e" 0, 2
D(1,8;1 ) , ,
3 3 3
Podstawienie do warunków ograniczających
3,5Å" 2 +10 Å" 2 = 27 > 23 0,8 d" 2 0,8 e" 0, 1,5 e" 0
E(2;2) , , nie jest dopuszcz.
3,5Å"0 +10 Å"0 = 0 d" 23, 0 d" 2
0 e" 0 0 e" 0 dopuszcz.
A(0,0) , ,
3,5Å" 2 +10 Å"5 = 23 d" 23 0,8 d" 2 0,8 e" 0, 1,5 e" 0
F(2;1,6) , , dopuszcz.
3,5Å" 0,8 +10 Å"1,5 = 17,8 d" 23 0,8 d" 2 0,8 e" 0, 1,5 e" 0
B(0,8;1,5) , , dopuszcz.
3,5Å" 2,5 +10 Å" 0,8 = 16,75 d" 23 2,5 > 2
G(2,5;0,8) , nie jest dopuszcz. 40
3,5Å"1+10 Å" 2 = 23,5 > 23 0,8 d" 2 0,8 e" 0, 1,5 e" 0
C(1;2) , , nie jest dopuszcz. 39
3,5Å" 2 +10 Å"5 = 23 d" 23 0,8 d" 2 - 0,2 < 0
H(-0,2;1,1) , , nie jest dopuszcz.
Programowanie liniowe Programowanie liniowe
Rozwiązywanie zadań (1) Rozwiązywanie zadań (2)
Rozwiązywanie zadań programowania Zadania programowania liniowego z 2
liniowego nie może być oparte o zmiennymi decyzyjnymi można
obliczanie pochodnych, ponieważ rozwiązywać przy pomocy tzw. metody
pochodna funkcji celu po każdej ze graficznej. Zostanie ona przedstawiona
zmiennych jest stałą liczbą, a zatem nie póz
niej w celu zilustrowania pewnych
ma sensu przyrównywanie jej do zera. charakterystycznych własności
programowania liniowego.
41 42
Metoda graficzna rozwiÄ…zywania
Programowanie liniowe
zadania programowania liniowego
Rozwiązywanie zadań (3)
Przykład
Uniwersalną metodą rozwiązywania zadań Zadanie z maksymalizacją funkcji celu (wszystkie
współczynniki funkcji celu i ograniczeń są dodatnie)
programowania liniowego jest algorytm
x2 Dla współrzędnych tego punktu funkcja
simpleks (metoda simpleks). Nie będziemy
celu osiąga maksimum równe zmax.
go jednak omawiać, ponieważ jest on bardzo
Niebieski odcinek jest geometrycznÄ… re-
prezentacjÄ… wszystkich par liczb X1, X2
pracochłonny, a osoby używające w praktyce
* *
(x1 , x2 ) należących do zbioru dopuszczalnego
programowania liniowego mają do dyspozycji D, dla których, po ich podstawieniu do
( X , X )
1 2
funkcji celu, przyjmie ona wartość z.
bardzo wiele programów komputerowych, D
x1
które wykonają niezbędne obliczenia.
43 44
Twierdzenie o kształcie zbioru
RozwiÄ…zania wielokrotne zadania
rozwiązań wielokrotnych ZPL (1)
programowania liniowego
Przykład
Zbiór wszystkich rozwiązań wielokrotnych ZPL może
RozwiÄ…zania wielokrotne.
Zbiór rozwiązań wielokrotnych
mieć następującą postać geometryczną
Przypadek n=2 (2 zmienne decy-
(geometr. jest to odcinek)
x2
zyjne) dla standardowej postaci
" dla n=2 - odcinek
zadania programowania liniowego
RozwiÄ…zania
wierzchołkowe z dodatnimi parametrami.
" dla n=3 - wielokąt wypukły lub odcinek
* *
(x11, x21)
* * Dla współrzędnych punktów
" dla n>3  co najwyżej (n-1)-wymiarowy  wielościan
(x12, x22 )
* * * * * *
x1 = (x11, x21) oraz x2 = (x12 , x22 )
wypukły, wielokąt wypukły lub odcinek.
funkcja celu osiÄ…ga maksimum
D * * * *
c1 x11 + c2 x21 = c1 x12 + c2 x22 = zmax .
tzn.
x1
Funkcja celu osiąga maksimum również dla współrzędnych wszystkich
* * * * * *
x1 = (x11, x21) x2 = (x12 , x22 )
punktów odcinka o końcach oraz .
45 46
RozwiÄ…zania wielokrotne zadania
Twierdzenie o kształcie zbioru
programowania liniowego a
rozwiązań wielokrotnych ZPL (2)
oprogramowanie optymalizacyjne
Jeżeli zbiór dopuszczalny D jest nieograniczony, to
W przypadku, gdy istniejÄ… rozwiÄ…zania wielokrotne
zbiór rozwiązań wielokrotnych może mieć postać
zadania programowania liniowego, wiele
zbioru nieograniczonego o wymiarze co najwyżej o programów komputerowych, w tym dodatek do
Excela o nazwie Solver niestety nie pokazuje
1 mniejszym niż liczba zmiennych n: półprostej,
wszystkich rozwiązań  wierzchołkowych , a
nieograniczonego podzbioru płaszczyzny/
jedynie jedno z nich.
przestrzeni, którego krawędziami są półproste i
Można co prawda stwierdzić, że rozwiązania
ewentualnie odcinki,.
alternatywne istniejÄ…, ale wszelkie metody
Przypadki te sÄ… jednak nieistotne z praktycznego
postępowania, które to umożliwiają, są dość
punktu widzenia, ponieważ modele dla realnych
niewygodne w użyciu.
sytuacji decyzyjnych w zasadzie nigdy nie majÄ…
rozwiązań o takiej postaci.
47 48
Wybór optymalnego planu produkcji 
Wykład 1
sformułowanie słowne (1)
Część 3
Firma może produkować n rodzajów wyrobów.
Programowanie liniowe:
Zakładamy, że wszystkie wyprodukowane wyroby
zostaną sprzedane i to ze stałymi zyskami
Wybór optymalnego planu
jednostkowymi (tzn. nie zależącymi od wielkości
produkcji/sprzedaży). Do produkcji wyrobów
(asortymentu) produkcji przy
zużywanych jest m różnych rodzajów środków
ograniczonej dostępności
produkcji (surowce, energia, maszyny, siła
robocza, powierzchnia magazynowa etc.),
środków produkcji
dostępnych w ograniczonych ilościach w
pewnym ustalonym okresie czasu.
49 50
Wybór optymalnego planu produkcji  Wybór optymalnego planu produkcji 
model ogólny - sformułowanie słowne (2) parametry modelu (1)
Dane sÄ…:
Należy określić, które wyroby i w jakich ilościach
aij
produkować, aby nie przekraczając posiadanych " - jednostkowe zużycie i-tego środka produkcji
tzn. ilość tego środka zużywana na wytworzenie
zasobów środków produkcji, zmaksymalizować
jednej jednostki j-tego wyrobu, liczona np. w
zysk ze sprzedaży tychże wyrobów w pewnym
g/kg, mg/l, kg/m3, kWh/t, h/t itp.
ustalonym okresie czasu.
(i=1,...,m; j = 1,...,n);
" bi- maksymalne dostępne zasoby i-tego środka
produkcji w rozważanym okresie czasu, liczone
np. w kg, l, hl, t, m2, m3, m (i=1,...,m);
51 52
Wybór optymalnego planu produkcji  Wybór optymalnego planu produkcji 
parametry modelu (2) zmienne decyzyjne
" cj- zysk jednostkowy dla wyrobu j-tego rodzaju Zmiennymi decyzyjnymi w tym zagadnieniu sÄ…
tzn. zysk pochodzący ze sprzedaży jednej wielkości produkcji i sprzedaży wyrobów:
jednostki wyrobu, liczony w PLN/m, PLN/kg,
" x
- wielkość produkcji j-ego wyrobu liczona np.
j
PLN/m3, PLN/t itp. (zamiast PLN może być
w kg, l, hl, t, m3,m2, m, szt. (naturalnie wyroby
oczywiście dowolna inna waluta, ale dla
różnych rodzajów mogą być liczone w różnych
wszystkich wyrobów jednakowa) (j = 1,...,n).
jednostkach np. niektóre w kg a inne w litrach).
53 54
Wybór optymalnego planu produkcji  Programowanie liniowe -
ogólny model matematyczny wybór optymalnego planu produkcji
c1x1 + c2 x2 + ... + cn xn max
- łączny zysk ze sprzedaży wyrobów
przy ograniczeniach
rzeczywiste zużycie maksymalne dostępne zasoby
środków produkcji środków produkcji
a11x1 + a12 x2 + ... + a1n xn d" b1
a21x1 + a22 x2 + ... + a2n xn d" b2
M M
am1x1 + am2 x2 + ... + amn xn d" bm
xn e" 0
x1 e" 0 x2 e" 0,...., ilości wyrobów nie mogą być ujemne
,
55 56
Wybór optymalnego planu produkcji  uwagi:
Istnienie rozwiÄ…zania dla zadania
wielkość produkcji a wielkość sprzedaży
optymalnego planu produkcji
W modelu występuje założenie wielkość produkcji =
wielkość sprzedaży (zmienne decyzyjne w
Rozważany model wyboru planu produkcji
funkcji celu oznaczają de facto wielkości
gwarantuje istnienie rozwiÄ…zania
sprzedaży natomiast w warunkach
ograniczających - wielkości produkcji). optymalnego dla dowolnych realistycznych
W rzeczywistości albo:
parametrów tzn.
wszystkich wyprodukowanych wyrobów nie
aij
nieujemnych , dodatnich (wartości
bi
uda się sprzedać (zatem te niesprzedane nie
c
parametrów funkcji celu nie mają znaczenia ).
przynoszÄ… zysku) j
albo:
Jest tak, ponieważ dla parametrów takich jak
produkcja jest realizowana w ramach
wyżej zbiór rozwiązań dopuszczalnych jest
konkretnych zamówień, które nie muszą się
niepusty
pokrywać z wyliczonym, optymalnym (tzn.
57 58
maksymalizujÄ…cym zysk) planem produkcji.
Wybór optymalnego planu produkcji
Wybór optymalnego planu produkcji
a kwestia podzielności wyrobów
a postać standardowa ZPL
Jeżeli choć jeden z rodzajów wyrobów musi być (ze
względu na swoją niepodzielność, np. jest to
Ogólne wzory dla zadania wyboru
urządzenie, maszyna, produkt odzieżowy itp.) liczony w
optymalnego planu (asortymentu)
sztukach, to wtedy może być konieczne dodanie
warunków całkowitoliczbowości zmiennej/ych,
produkcji sÄ… identyczne jak podana
ponieważ nie ma żadnej gwarancji, że rozwiązanie
wcześniej postać standardowa zadania
przyjmie wartości całkowitoliczbowe.
programowania liniowego dla
Oznacza to, że rozważane zadanie stanie się zadaniem
tzw. liniowego programowania całkowitoliczbowego. maksymalizacji.
Niepodzielność wyrobów występuje częściej niż to się
na pozór wydaje, ponieważ nawet wyroby podzielne (np.
soki, sery, proszek do prania) z reguły są pakowane w
niepodzielne opakowania o ustalonych rozmiarach
59 60
Wybór optymalnej diety 
sformułowanie słowne
Wykład 1
Zakładamy, że w pewnym ustalonym okresie
czasu (najczęściej 1 dnia) należy spożyć co
Część 4
najmniej minimalne wymagane ilości m
różnych składników odżywczych (takich jak
białko, węglowodany, tłuszcze, witaminy, sole
mineralne itp. a także odpowiednią ilość kalorii)
Programowanie liniowe:
zawartych w dostępnych produktach n
rodzajów.
zadanie optymalnej diety
Zakładamy ponadto, że koszty jednostkowe
produktów są stałe i nie zależą od wielkości
zakupu a ilość zakupiona = wielkość
spożycia.
62
Wybór optymalnej diety  Wybór optymalnej diety 
sformułowanie słowne cd. parametry modelu
aij
" - zawartość i-tego składnika
Należy zaplanować, które produkty spożywcze
i w jakich ilościach należy zakupić aby
odżywczego na jednostkę j-tego
zminimalizować łączne koszty ich zakupu w
produktu np. ilość gramów białka na kg
rozważanym okresie, dostarczając przy tym co
kiszonki w mieszance paszowej, gramów
najmniej tyle składników odżywczych, ile
węglowodanów na kg dżemu, dekagra-
wymagajÄ… normy.
mów tłuszczu na kg mięsa, miligramów
witaminy C na litr soku itp. (czyli
zawartości te są liczone w takich
jednostkach jak g/kg, dag/kg, mg/l,
kcal/kg) (i= 1,...,m; j = 1,...,n);
63 64
Wybór optymalnej diety 
Wybór optymalnej diety 
zmienne decyzyjne
parametry modelu c.d.
bi
" - minimalne wymagane spożycie i-tego
składnika odżywczego w rozważanym
Zmiennymi decyzyjnymi w tym zagadnieniu sÄ…
okresie (liczone w takich jednostkach jak mg,
ilości produktów spożywczych:
g, kg, ml, l, cm3, kcal) (i=1,...,m);
x
" j - wielkość zakupu (i spożycia) j-ego
c
" j - cena jednostkowa dla j-tego produktu spożywczego.
produktu (j = 1,...,n) (liczona w PLN/l,
PLN/kg, PLN/m3, PLN/t itp.  zamiast PLN
może być oczywiście dowolna inna waluta, ale
dla wszystkich produktów jednakowa).
65 66
Wybór optymalnej diety 
Programowanie liniowe -
ogólny model matematyczny
wybór optymalnej diety
c1x1 + c2 x2 + ... + cn xn min
Wybór optymalnej (najtańszej) diety - model ogólny
łączny koszt zakupu produktów
przy ograniczeniach
Wyboru diety można dokonać zakupując niektóre lub wszystkie spośród
n różnych dostępnych produktów spożywczych.
rzeczywiste spożycie minimalne wymagane spożycie
składników odżywczych składników odżywczych
&
a11x1 + a12 x2 + ... + a1n xn e" b1
a21x1 + a22 x2 + ... + a2n xn e" b2
? ? ? ? ?
M M &
x1kg x2 kg x3 kg x4 l xn kg
am1x1 + am2 x2 + ... + amn xn e" bm
x1 e" 0 x2 e" 0 xn e" 0
, ,...., ilości produktów nie mogą być
67 68
ujemne
Wybór optymalnej diety  aspekty Czy zadanie optymalnej diety ma
praktyczne żywienia ludzi zawsze rozwiązanie?
Choć nie ma to znaczenia z punktu widzenia
złożoności obliczeń, z praktycznego punktu
Zadanie optymalnej diety w podanej wyżej
widzenia ten model jest stosowany raczej do
( podręcznikowej ) postaci (tzn. wyłącznie z
układania planów żywienia dla zwierząt niż
dolnymi limitami spożycia składników), gdzie
dla ludzi, a to ze względu na pominięcie
c
aij bi j
parametry , , sÄ… dodatnie (ewentualnie
kwestii walorów smakowych oraz nieuchronną
aij
niektóre mogą wynosić 0, jeżeli składnik i
monotonię tak ułożonej diety.
nie jest zawarty w produkcie j) ma zawsze
rozwiÄ…zanie.
Rozwiązanie to jednak może mieć znaczne
przekroczone minimalne limity spożycia dla
niektórych składników.
69 70
Czy w zadaniu optymalnej diety
istnieje maksimum funkcji celu?
Zadanie optymalnej diety w wersji tylko z dolnymi
limitami spożycia składników jest przykładem
zadania, w którym nie istnieje maksimum funkcji
celu (alternatywnie można powiedzieć, że
maksimum to wynosi  plus nieskończoność ).
Konsekwencją tego faktu jest np. komunikat błędu
przy rozwiązywaniu zadania Solverem, jeśli parametr
 Równa jest ustawiony omyłkowo na Maks zamiast
na Min
71 72
Wybór optymalnej diety  rozszerzenie
Wybór optymalnej diety 
modelu o górne normy spożycia
przekroczenie spożycia składników
di
Jeżeli istnieją górne normy zawartości składników to
Jak już wspomniano wcześniej najtańsza
do zadania należy dołączyć następującą grupę warunków
dieta może mieć znacznie przekroczone
ograniczajÄ…cych:
spożycie niektórych składników. Wynika
stąd, iż  realne zadanie optymalnej diety rzeczywiste spożycie maks.dopuszczalne spożycie
składników odżywczych składników odżywczych
powinno uwzględnić nie tylko minimalne
a11x1 + a12 x2 + ... + a1n xn d" d1
wymagane spożycie składników, ale także
maksymalne dopuszczalne ze względów
a21x1 + a22 x2 + ... + a2n xn d" d2
zdrowotnych spożycie składników
M M
(zasada  co za dużo to niezdrowo ).
am1x1 + am2x2 + ...+ amn xn d" dm
73 74
Wybór optymalnej diety  Czy zadanie optymalnej diety z górnymi
ogólny model matematyczny z dolnymi i
normami spożycia składników ma
górnymi normami spożycia
zawsze rozwiÄ…zanie?
c1x1 + c2 x2 + ... + cn xn min
- łączny koszt zakupu produktów
Nie, ponieważ warunki ograniczające z górnymi i
przy ograniczeniach
dolnymi limitami (normami) mogą się okazać
rzeczywiste spożycie minimalne wymagane spożycie
sprzeczne, zwłaszcza jeżeli do stworzenia diety
składników odżywczych składników odżywczych
użyte są produkty o mało zróżnicowanym
a11x1 + a12 x2 + ... + a1n xn e" b1
składzie.
M M
Próba rozwiązania w Excelu skutkuje następującym
am1x1 + am2 x2 + ... + amn xn e" bm
komunikatem:
rzeczywiste spożycie maksymalne dopuszczalne spożycie
składników odżywczych składników odżywczych
a11x1 + a12 x2 + ... + a1n xn d" d1
M M
am1x1 + am2x2 + ...+ amn xn d" dm
x1 e" 0 x2 e" 0 xn e" 0
, ,...., ilości produktów
75 76
nie mogą być ujemne
Wybór optymalnej diety 
Wybór optymalnej diety 
uwagi historyczne
uwagi historyczne c.d.
Zadanie optymalnej diety jest historycznie rzecz biorÄ…c
jednym z pierwszych modeli programowania
10 pracownikom korzystajÄ…cym z
liniowego zastosowanym w praktyce. Co ciekawe,
mechanicznych kalkulatorów
zostało ono pierwotnie użyte do ułożenia diety dla
Å‚Ä…czny czas
ludzi.
120 roboczodniówek czyli ok. 1000 godzin.
RozwiÄ…zanie przy pomocy metody simpleks zadania
optymalnej diety z:
" 77 zmiennymi (n=77 - wybór dotyczył 77 produktów
spożywczych),
" 9 ograniczeniami funkcyjnymi (m=9 -
uwzględniono 9 składników odżywczych)
zajęło jesienią 1947 roku:
77 78
Wybór optymalnej diety  Wybór optymalnej diety 
uwagi historyczne uwagi historyczne
79 80
Programowanie liniowe -
zadanie optymalnej mieszanki
Wykład 1
Model matematyczny identyczny jak w zadaniu
Część 5
optymalnej diety może również być użyty przy
wyborze najtańszej mieszanki  docelowej
dowolnych substancji (niekoniecznie produktów
spożywczych) spełniającej dolne i ewentualnie
Programowanie liniowe:
górne normy zawartości składników.
zadanie optymalnej mieszanki Substancje te sÄ… dalej nazywane roboczo
mieszankami  składowymi , czyli jednorodnymi
(ang. blending problem)
mieszaninami związków chemicznych i/lub
pierwiastków (przykładem są produkty spożywcze
w zadaniu optymalnej diety).
82
Programowanie liniowe -
Zadanie optymalnej mieszanki (podejście
zadanie optymalnej mieszanki
 procentowe )  sformułowanie słowne
Zadanie optymalnej mieszanki może być również
Należy zaplanować, które mieszanki
sformułowane w taki sposób, że zarówno:
 składowe i w jakich ilościach (lub
" zawartości składników w mieszankach
udziałach procentowych) należy zakupić
 składowych
aby zminimalizować łączny koszt 1
jednostki mieszanki  docelowej ,
jak i
zapewniając przy tym, że zawartości
" wymagane ilości składników zawartych w
składników w mieszance  docelowej będą
mieszance  docelowej
takie jak przewidujÄ… wymagania (dolne lub
mogą być wyrażone nie w liczbach bezwzględnych,
górne normy). Ponadto, ilości mieszanek
ale w procentach.
 składowych muszą się sumować do 1
jednostki (np. do 1 kilograma), w której to
Funkcja celu oznacza wtedy Å‚Ä…czny koszt jednej
jednostce są mierzone zarówno mieszanki
jednostki mieszanki  docelowej .
83 84
 składowe jak i mieszanka  docelowa .
Model matematyczny dla zadania optymalnej
Model matematyczny dla zadania optymalnej
mieszanki (podejście  procentowe ) 
mieszanki (podejście  procentowe ) - parametry
parametry cd.
bi / di- minimalne wymagane/maksymalne
"
aij
" - zawartość procentowa i-tego składnika w j-
dopuszczalne zawartości procentowe i-tego
tej mieszance  składowej (i= 1,...,m; j = 1,...,n) 
składnika w mieszance  docelowej
ilość procent każdego ze składników zawartych w
(i=1,...,m). Są one liczbowo równe wymaganej
mieszance  składowej . Ilości  procentowe są
liczbie dag czy cl przypadajÄ…cej na kg/litr
liczbowo równe ilości dag składnika na kg
mieszanki  docelowej .
mieszanki  składowej (dag/kg) albo centylitrów
c
" j - cena jednostkowa dla j-tej mieszanki
składnika na litr mieszanki  składowej (cl/l, cl 
 składowej (j = 1,...,n), liczona np. w PLN/l,
centylitr=0,01 litra), oczywiście pod warunkiem, że
PLN/kg, PLN/m3, PLN/t itp.  zamiast PLN może
jednostkami, w których liczone są mieszanki
być oczywiście dowolna inna waluta, ale dla
 składowe są odpowiednio kilogramy czy litry.
wszystkich mieszanek  składowych jednakowa.
85 86
Zadanie optymalnej mieszanki (podejście
Model matematyczny dla zadania optymalnej
 procentowe ) - model matematyczny (1)
mieszanki (podejście  procentowe ) 
c1x1 + c2 x2 + ... + cn xn min
zmienne decyzyjne
Å‚Ä…czny koszt 1 jedn. (np. kg, l, t) mieszanki  docelowej
Zmiennymi decyzyjnymi są ilości mieszanek
przy ograniczeniach
składowych:
rzeczywiste % zawart. składn. minimalne wymagane % zawart.
" x
j - ilość j-tej mieszanki  składowej liczona np.
w mieszance  docelowej składn.w mieszance  docelowej
w kg (po przemnożeniu przez 100% ilość ta jest
a11x1 + a12 x2 + ... + a1n xn e" b1
równa udziałowi procentowemu j-tej mieszanki
M M
 składowej w mieszance  docelowej ).
am1x1 + am2 x2 + ... + amn xn e" bm
rzeczywiste % zawart. składn maksymalne dopuszczalne zawart.
w mieszance  docelowej składn.w mieszance  docelowej
a11x1 + a12 x2 + ... + a1n xn d" d1
M M
am1x1 + am2 x2 + ... + amn xn d" dm
87 88
Zadanie optymalnej mieszanki (podejście
Zadanie optymalnej mieszanki (podejście
 procentowe ) -  dokładne normy
 procentowe ) - model matematyczny (2)
zawartości składników
x1 + x2 + ... + xn = 1 ilości mieszanek  składowych
bi
Parametry mogą również w szczególności
muszą się sumować do 1 (1 jednostki mieszanki
oznaczać dokładne procentowe zawartości
 docelowej )
składników w mieszance docelowej.
x1 e" 0 x2 e" 0 xn e" 0
, ,...., ilości mieszanek  składowych
Jeżeli wszystkie procentowe zawartości składników
nie mogą być ujemne.
w mieszance docelowej mają postać równości, to
model matematyczny przybiera wtedy postać
podaną na następnym slajdzie.
89 90
Zadanie optymalnej mieszanki (podejście
Zadanie optymalnej mieszanki (podejście
 procentowe ) - model matematyczny:
 procentowe ) z  dokładnymi normami
 dokładne normy zawartości składników
zawartości składn.  uwagi (1)
c1x1 + c2 x2 + ... + cn xn min
aij
bi
Jeżeli parametry i opisują  pełne
Å‚Ä…czny koszt 1 jedn. (np. kg, l, t) mieszanki  docelowej
zawartości mieszanek składowych i docelowej
przy ograniczeniach
tzn. opisują zawartości wszystkich ich
rzeczywiste zawartości wymagane zawartości
składników, co matematycznie można zapisać
składników w mieszance składników w mieszance
jako:
 docelowej  docelowej
m m
a11x1 + a12x2 + ... + a1nxn = b1
=1
"aij "b = 1
j
oraz
M M
j=1 j=1
am1x1 + am2x2 + ... + amn xn = bm
albo równoważnie:
m m
x1 + x2 + ... + xn = 1 ilości mieszanek  składowych muszą
się sumować do 1 (1 jednostki mieszanki  docelowej ) "a = 100% oraz "b = 100%
ij j
j=1 j=1
x1 e" 0 x2 e" 0 xn e" 0
, ,...., ilości mieszanek  składowych nie
91 92
mogą być ujemne.
Zadanie optymalnej mieszanki (podejście
Zadanie optymalnej mieszanki (podejście
 procentowe ) z  dokładnymi normami
 procentowe )  zadanie przykładowe
zawartości składn.  uwagi (2)
Należy wymieszać ze sobą 6 stopów ołowiu, cynku i cyny o ró-
a warunki ograniczające związane z zawartością
żnych zawartościach składników i cenach za kg tak, aby
składników mają postać równości, to wtedy
otrzymać nowy stop o zadanym składzie procentowym i jak
najniższej cenie za kg. Dane liczbowe są zawarte w tabeli.
można zrezygnować z warunku
x1 + x2 + ... + xn = 1
Stopy  składowe
Zawartość
S1 S2 S3 S4 S5 S6
ponieważ warunki związane z zawartością
składników
Ceny jednostko-
w stopie
we stopów
gwarantują jego spełnienie.
5,50 5,70 5,80 6,00 6,10 5,30  docelowym
 składowych
(w % lub
(PLN/kg)
alternatywnie
Zawartości składników w sto-
w dag/kg)
pach  składowych (w % lub
Składniki stopów alternatywnie w dag/kg)
ołów (Pb) 33 28 40 50 20 20 30
cynk (Zn) 17 30 50 20 49 50 30
cyna (Sn) 50 42 10 30 31 30 40
93 94
Zadanie optymalnej mieszanki (podejście
Zadanie optymalnej mieszanki (podejście
 procentowe )  zadanie przykładowe:
 procentowe )  zadanie przykładowe:
tworzenie modelu
tworzenie modelu
x1 + x2 + ... + x6 = 1 jest de facto zbędne,
1.Ograniczenie
x1, x2 , x3, x4 , x5 , x6 - ilości stopów  składowych
ponieważ dodanie stronami 3 ograniczeń na ilości
(odpowiednio S1, S2,& ,S6) w kg
składników prowadzi do równoważnej mu równości
5,5x1 + 5,7x2 + 5,8x3 + 6x4 + 6,1x5 + 5,3x6 min
-
100x1 + 100x2 + 100x3 + 100x4 + 100x5 + 100x6 = 100
.
Å‚Ä…czny koszt 1 kg stopu  docelowego
aij bi
Jest to przypadek zadania, gdy parametry i opisujÄ…
przy ograniczeniach
 pełne zawartości mieszanek  składowych (czyli
rzeczywiste zawartości wymagane zawartości składn.
zawartości wszystkich składników).
składn. w stopie  docelowym w stopie  docelowym
2. Funkcja celu  rozpisana z jednostkami miar to:
33x1 + 28x2 + 40x3 + 50x4 + 20x5 + 20x6 = 30
17x1 + 30x2 + 50x3 + 20x4 + 49x5 + 50x6 = 30
PLN PLN PLN
5,5 x1kg S1+ 5,7 x2kg S2 + ... + 5,3 x6kg S6.
50x1 + 42x2 +10x3 + 30x4 + 31x5 + 30x6 = 40
kg S1 kg S2 kg S6
x1 + x2 + ...+ x6 = 1 ilości stopów w sumie wynoszą 1 kg
x1 e" 0 x2 e" 0 x6 e" 0
, ,...., ilości stopów  składowych
Zatem po  skróceniu kg stopów  składowych jednostka
95 96
nie mogą być ujemne.
funkcji celu to PLN.
Zadanie optymalnej mieszanki (podejście Zadanie optymalnej mieszanki (podejście
 procentowe )  zadanie przykładowe:  procentowe )  zadanie przykładowe:
tworzenie modelu tworzenie modelu
Biorąc pod uwagę w/w rozważania, można  rozpisać
3. Procentowy skład stopu  docelowego to:
warunki ograniczające z jednostkami miar (przykładowo
30% Pb, 30% Zn i 40% Sn.
podany jest pierwszy z nich):
W przeliczeniu na jednostki bezwzględne oznacza to, że
dag Pb dag Pb dag Pb
1 kg stopu  docelowego składa się z 30 dag Pb, 30 dag
33 x1kg S1+ 28 x2kg S 2 + ... + 20 x6kg S6 = 30 dag Pb
kg S1 kg S 2 kg S6
Zn i 40 dag Sn (czyli wartości liczbowe w jednostkach
bezwzględnych są takie same jak wartości
Po  skróceniu kg stopów  składowych widać, że obie
procentowe).
strony nierówności wyrażają się w dag składnika
Analogicznie, jeżeli chodzi o zawartości składników w
(np.dag Pb). Co ważniejsze jednak, współczynniki w
stopach  składowych to np. 33% zawartości Pb w 1-ym
warunkach ograniczajÄ…cych liczone w dag na kg majÄ…
stopie składowym (S1) oznacza dokładnie to samo co
te same wartości liczbowe co współczynniki
zawartość 33 dag ołowiu na 1 kg S1.
 procentowe , dlatego też nie wymagają one żadnych
dodatkowych przeliczeń.
97 98
Zadanie optymalnej mieszanki (podejście
 procentowe )  zadanie przykładowe:
rozwiÄ…zanie
Minimalny koszt 1 kg stopu  docelowego wynosi 5,474 PLN.
W tym celu należy zmieszać stopy  składowe w ilościach:
* *
x1 = x2 =
0,606 kg (60,6%), 0 kg (0%),
* *
x3 = x4 =
0,106 kg (10,6%) 0 kg (0%),
* *
x5 = x6 =
0 kg (0%), 0,288 kg (28,8%).
Odpowiada to zawartościom procentowym stopów  składowych
w stopie  docelowym w następujących proporcjach: 60,6%
pierwszego, 10,6% trzeciego oraz 28,8% szóstego. Oznacza to
zatem, że mieszanka stopów  składowych o dowolnej masie
m kg wymieszana w w-w proporcjach będzie miała dla wyma-
ganych procentowych zawartości składników najniższy możliwy
koszt równy 5,474"m PLN.
99