P. Kowalik, Laboratorium badań operacyjnych - zadanie przydziału z ustalonym poziomem produkcji i limitowanym czasem
1
pracy  planowanie wielkości produkcji.
14. Zadanie przydziału z ustalonym poziomem produkcji i limitowanym
czasem pracy  planowanie wielkości produkcji (wersja uproszczona)
Producent może wytwarzać n rodzajów wyrobów. Każdy z wyrobów można być wytworzony na jednym z m
stanowisk (np. maszyn, linii produkcyjnych etc.). Każde ze stanowisk ma określone:
" wydajności (mierzone jako czasy wyprodukowania 1 jednostki poszczególnych wyrobów),
" koszt 1 jednostki czasu pracy,
" górny limit łącznego czasu pracy.
Należy zaplanować ile wyrobów produkować na każdym ze stanowisk, aby osiągnąć jeden z następujących
celów:
" zminimalizować łączny czas pracy
" zminimalizować łączny koszt pracy
nie przekraczając przy tym limitów czasu pracy poszczególnych stanowisk i produkując wymagane ilości
wyrobów każdego z rodzajów.
Parametry zadania to:
aij , i=1,...,m; j=1,...,n  czas wyprodukowania jednej jednostki j-tego wyrobu na i-tym stanowisku (mierzony
np. w h/t, h/m3, min/szt, s/g etc.)
bi , i=1,...,m  maksymalny czas pracy na i-tym stanowisku przeznaczony na wyprodukowanie wyrobów
wszystkich rodzajów (mierzony np. w h, min, s);
ci , i=1,...,m  koszt jednej jednostki czasu pracy i-tego stanowiska (mierzony np. w PLN/h, PLN/min, PLN/s);
d , j=1,...,n  wymagany poziom produkcji j-tego wyrobu (mierzony np. w t, m3, szt, l etc.).
j
Zmienne decyzyjne to:
xij , i=1,...,m; j=1,...,n  ilość j-tego wyrobu wyprodukowana na i-tym stanowisku (liczona np. w t, m3, szt, etc.)
Model matematyczny to
a11x11 + a12 x12 + ... + a1n x1n +
a21x21 + a22 x22 + ... + a2n x2n +
łączny czas pracy (1 wariant)
... +
am1xm1 + am 2xm 2 + ... + amn xmn min
c1(a11x11 + a12x12 + ... + a1nx1n ) +
c2 (a21x21 + a22x22 + ... + a2nx2n ) +
łączny koszt pracy (2 wariant)
... +
cm (am1xm1 + am2xm2 + ... + amn xmn ) min
przy ograniczeniach
xij e" 0 i=1,...,m; j=1,...,n ilości wyrobów są nieujemne; xij - całkowite (opcjonalnie - dla wyrobów liczonych
w szt.)
rzeczywiste czasy maksymalne możliwe rzeczywiste wielkości wymagane
pracy stanowisk czasy pracy stanowisk produkcji poziomy produkcji
a11x11 + a12x12 + ...+ a1n x1n d" b1 x11 + x21 + ... + xm1 = d1
a21x21 + a22 x22 + ...+ a2n x2n d" b2 x12 + x22 + ...+ xm2 = d2
... ...
am1xm1 + am2xm2 + ...+ amn xmn d" bm x1n + x2n + ... + xmn = dn
Uwaga  brak  gwarantowanych rozwiązań całkowitoliczbowych
Rozważane tu zadanie przydziału, mimo podobieństwa do zadania transportowego, nie ma  zagwarantowanych
rozwiązań całkowitoliczbowych bez dodawania warunków całkowitoliczbowości zmiennych. Wynika to z faktu, tylko
jedna z grup warunków zawiera sumy  zwykłe zmiennych, natomiast druga sumy iloczynów zmiennych i liczb. W
związku z powyższym twierdzenie o rozwiązaniach całkowitoliczbowych zadania transportowego nie ma zastosowania
dla rozważanych modeli.
P. Kowalik, Laboratorium badań operacyjnych - zadanie przydziału z ustalonym poziomem produkcji i limitowanym czasem
2
pracy  planowanie wielkości produkcji.
Zadanie
4 rodzaje detali mogą być wytwarzane na jednej z 3 obrabiarek. Czasy wytworzenia każdego z rodzajów detali
na poszczególnych obrabiarkach są zróżnicowane.
Obra- Czasy wytworzenia 1 szt detalu (min/szt) Maksymalne czasy
biarki D1 D2 D3 D4 pracy (min)
O1 5 3 10 12 2500
O2 11 8,5 2 7 3300
O3 14,5 1 5 5,5 2400
Wymagane poziomy produkcji (szt)
200 800 780 600
Zaplanować wielkość produkcji detali na poszczególnych obrabiarkach, minimalizując przy tym łączny czas
pracy:
1. bez całkowitoliczbowości zmiennych;
2. z całkowitoliczbowością zmiennych;
3. z całkowitoliczbowością zmiennych (z ewentualnie ustawioną opcją Przyjmij model liniowy) oraz wartością
opcji Tolerancja 0%.
Model matematyczny do zadania
Zmienne decyzyjne to:
xij , i=1,2,3; j=1,2,3,4  liczba detali j-tego typu wyprodukowana na i-tej obrabiarce (liczona w sztukach detali
j-tego typu, oznaczenie: szt D1,& , szt D4),
W niniejszym zadaniu stanowiskami pracy, dla których planowane są wielkości produkcji, są oczywiście
obrabiarki.
Funkcja celu reprezentuje łączny czas pracy. ,
5x11 + 3x12 + 10x13 + 12x14 +
łączny czas pracy obrabiarek
11x21 + 8,5x22 + 2x23 + 7x24 +
w minutach
14,5x31 + 1x32 + 5x33 + 5,5x34 min
przy ograniczeniach
rzeczywiste czasy maksymalne możliwe rzeczywiste wielkości wymagane poziomy
pracy stanowisk czasy pracy stanowisk produkcji detali produkcji detali
(obrabiarek) (obrabiarek)
x11 + x21 + x31 = 200
5x11 + 3x12 + 10x13 + 12x14 d" 2500
x12 + x22 + x32 = 800
11x21 + 8,5x22 + 2x23 + 7x24 d" 3300
x13 + x23 + .x33 = 780
14,5x31 + 1x32 + 5x33 + 5,5x34 d" 2400
x14 + x24 + x34 = 600
xij e" 0 , i=1,2,3; j=1,2,3,4  liczby detali nie mogą być ujemne
xij - całkowite  liczby detali muszą być całkowite
Objaśnienia do modelu
Czasy pracy poszczególnych obrabiarek to:
5x11 + 3x12 + 10x13 + 12x14
11x21 + 8,5x22 + 2x23 + 7x24
14,5x31 + 1x32 + 5x33 + 5,5x34 .
Dla przykładu pierwsza z sum iloczynów jest rozpisana poniżej z jednostkami:
min min min min
5 x11szt D1 + 3 x12 szt D2 + 10 x13szt D3 + 12 x14 szt D4 .
szt D1 szt D2 szt D3 szt D4
P. Kowalik, Laboratorium badań operacyjnych - zadanie przydziału z ustalonym poziomem produkcji i limitowanym czasem
3
pracy  planowanie wielkości produkcji.
Jak widać sztuki detali wszystkich typów się  skracają a zatem cała formuła jest wyrażona w minutach. Ana-
logiczne obliczenia można wykonać dla dwóch kolejnych sum iloczynów. Funkcja celu dla 1 wariantu (łączny
czas pracy wszystkich stanowisk - obrabiarek w minutach) jest sumą trzech powyższych formuł.
Sumy iloczynów oznaczające czasy pracy obrabiarek występują także w warunkach uwzględniających
limitowane czasy pracy obrabiarek ograniczających (w lewych stronach nierówności).
Wprowadzanie danych do komórek arkusza
W niniejszym zadaniu komórkami pełniącymi rolę zmiennych decyzyjnych będą B9, C9, D9, E9, B10, C10,
D10, E10, B11, C11, D11, E11 czyli (w skrócie) zakres (tablica) B9:E11. Odpowiedniość pomiędzy
komórkami a zmiennymi jest następująca:
B9 - x11 , C9 - x12 , D9 - x13 , E9 - x14
B10 - x21 , C10 - x22 , D10 - x23 , E10 - x24
B11 - x31 , C11 - x32 , D11 - x33 , E11 - x34
Rozmieszczenie danych
Funkcja celu (łączny czas pracy wszystkich stanowisk - obrabiarek w minutach) to suma iloczynów
współczynników wydajności (czasy wyprodukowania detali na poszczególnych stanowiskach) i wielkości
produkcji na tychże stanowiskach. Ponieważ jednak czasy pracy poszczególnych 3 stanowisk-obrabiarek wy-
stępują także w warunkach ograniczających, zatem w komórkach zostaną umieszczone 3 oddzielne sumy
iloczynów. Funkcja celu będzie zatem sumą tychże sum iloczynów.
Informacja na temat formuł: wprowadzanych przez użytkownika i kopiowanych (funkcja celu i warunki
ograniczające)
Zapis matematyczny
Formuły  dosłowne tzn. takie, które należałoby wpisać Formuły umieszczone w arkuszu
Uwagi
przy literalnym  przełożeniu zapisu matematycznego na odpowiadające formułom  dosłownym
składnię Excela
Wprowadzona
5x11 + 3x12 + 10x13 + 12x14
F9 =SUMA.ILOCZYNÓW(B3:E3;B9:E9) przez
=B3*B9+C3*C9+D3*D9+E3*E9
użytkownika
11x21 + 8,5x22 + 2x23 + 7x24 Otrzymana przez
F10 =SUMA.ILOCZYNÓW(B4:E4;B10:E10)
kopiowanie z F9
=B4*B10+C4*C10+D4*D10+E4*E10
11x21 + 8,5x22 + 2x23 + 7x24 + Otrzymana przez
F11 =SUMA.ILOCZYNÓW(B5:E5;B11:E11)
kopiowanie z F9
=B5*B11+C5*C11+D5*D11+E5*E11
Komórka
P. Kowalik, Laboratorium badań operacyjnych - zadanie przydziału z ustalonym poziomem produkcji i limitowanym czasem
4
pracy  planowanie wielkości produkcji.
Zapis matematyczny
Formuły  dosłowne tzn. takie, które należałoby wpisać Formuły umieszczone w arkuszu
Uwagi
przy literalnym  przełożeniu zapisu matematycznego na odpowiadające formułom  dosłownym
składnię Excela
Wprowadzona
x11 + x21 + x31
B13 =SUMA(B9:B11) przez
=B9+B10+B11
użytkownika
Otrzymana przez
x12 + x22 + x32
C13 =SUMA(C9:C11) kopiowanie
=C9+C10+C11
z B13
Otrzymana przez
x13 + x23 + x33
D13 =SUMA(D9:D11) kopiowanie
=D9+D10+D11
z B13
Otrzymana przez
x14 + x24 + x34
E13 =SUMA(E9:E11) kopiowanie
=E9+E10+E11
z B13
5x11 + 3x12 + 10x13 + 12x14 +
11x21 + 8,5x22 + 2x23 + 7x24 +
Otrzymana przez
F13 =SUMA(F9:F11) kopiowanie
14,5x31 + 1x32 + 5x33 + 5,5x34
z B13
=B3*B9+C3*C9+D3*D9+E3*E9+
B4*B10+C4*C10+D4*D10+E4*E10+
B5*B11+C5*C11+D5*D11+E5*E111
Wygląd arkusza po kopiowaniu
Wygląd arkusza po kopiowaniu (widok formuł)
Komórka
P. Kowalik, Laboratorium badań operacyjnych - zadanie przydziału z ustalonym poziomem produkcji i limitowanym czasem
5
pracy  planowanie wielkości produkcji.
Ustawienia Solvera
Na tym etapie zakończyło się wprowadzanie danych bezpośrednio do komórek arkusza.
Mamy następujące związki między zapisem matematycznym a zapisem w Excelu:
B9 - x11 , C9 - x12 , D9 - x13 , E9 - x14 , B10 - x21 , C10 - x22 , D10 - x23 , E10 - x24
B11 - x31 , C11 - x32 , D11 - x33 , E11 - x34
xij , i=1,2,3; j=1,2,3,4  liczba detali j-tego typu wyprodukowana na i-tej obrabiarce (liczona w sztukach detali
j-tego typu,
5x11 + 3x12 + 10x13 + 12x14 +
łączny czas pracy obrabiarek
F13 11x21 + 8,5x22 + 2x23 + 7x24 +
w minutach
14,5x31 + 1x32 + 5x33 + 5,5x34 min
przy ograniczeniach
rzeczywiste czasy maksymalne możliwe rzeczywiste wymagane
pracy stanowisk czasy pracy stanowisk wielkości poziomy
(obrabiarek) (obrabiarek) produkcji detali produkcji detali
x11 + x21 + x31 = 200
F9 5x11 + 3x12 + 10x13 + 12x14 d" 2500 F3 B13 B7
F10 11x21 + 8,5x22 + 2x23 + 7x24 d" 3300 F4 C13 x12 + x22 + x32 = 800 C7
F11 F5 D13 x13 + x23 + .x33 = 780 D7
14,5x31 + 1x32 + 5x33 + 5,5x34 d" 2400
E13 E7
x14 + x24 + x34 = 600
B9:E11 xij e" 0 , i=1,2,3; j=1,2,3,4  liczby detali nie mogą być ujemne
B9:E11 xij - całkowite  liczby detali muszą być całkowite
Rozwiązania
Ad. 1 Zminimalizować łączny czas pracy obrabiarek (obliczenia bez całkowitoliczbowości zmiennych).
Warunek poniżej został pominięty
B9:E11 xij - całkowite  liczby detali muszą być całkowite
Ustawienia Solvera  minimalizacja czasu pracy (bez całkowitoliczbowości zmiennych)
P. Kowalik, Laboratorium badań operacyjnych - zadanie przydziału z ustalonym poziomem produkcji i limitowanym czasem
6
pracy  planowanie wielkości produkcji.
Rozwiązanie przy ustawieniach domyślnych Solvera bez warunków całkowitoliczbowości zmiennych.
Jak widać, nie jest to rozwiązanie całkowitoliczbowe. Nie jest to również jedno z rozwiązań alternatywnych
niecałkowitoliczbowych. Można ten fakt rozpoznać po wartości funkcji celu. Gdyby istniało alternatywne roz-
wiązanie całkowitoliczbowe, to optymalna wartość funkcji celu byłaby liczbą całkowitą lub z  końcówką ,5
jako suma iloczynów parametrów aij (całkowite wielokrotności 0,5 czyli liczby całkowite lub z  końcówką
,5).
Przykład ten pokazuje, że pomimo podobieństwa w zapisie do zadania transportowego, rozpatrywane zadanie
przydziału nie ma  zagwarantowanych rozwiązań całkowitoliczbowych, gdy prawe strony warunków ograni-
czających są całkowite. Oznacza to konieczność dodania warunków całkowitoliczbowości zmiennych.
Ad. 2 Zminimalizować łączny czas pracy obrabiarek (obliczenia z całkowitoliczbowością zmiennych).
Aby rozwiązać zadanie z całkowitoliczbowością zmiennych należy w Solverze dodać warunek B9:E11 int,
który po zatwierdzaniu jest wyświetlany jako $B$9:$E$11=całkowita.
Ustawienia Solvera  minimalizacja czasu pracy (z całkowitoliczbowością zmiennych)
Okazuje się, że po dodaniu warunków całkowitoliczbowości zmiennych, Solver może  w zależności od wersji
Excel a także od konkretnego komputera - znalez
ć rozwiązania zadania z różnymi wartościami minimów i to
pomimo komunikatu  Solver znalazł rozwiązanie . Poniżej są pokazane przykłady takich rozwiązań.
P. Kowalik, Laboratorium badań operacyjnych - zadanie przydziału z ustalonym poziomem produkcji i limitowanym czasem
7
pracy  planowanie wielkości produkcji.
Różne rozwiązania przy ustawieniach domyślnych Solvera z warunkami całkowitoliczbowości
zmiennych.
P. Kowalik, Laboratorium badań operacyjnych - zadanie przydziału z ustalonym poziomem produkcji i limitowanym czasem
8
pracy  planowanie wielkości produkcji.
Powyższe zróżnicowanie rozwiązań wynika z tego iż ze względu na potencjalnie bardzo długi czas
wykonywania obliczeń z warunkami całkowitoliczbowości dopuszczone jest domyślnie znajdowanie wartości
funkcji celu gorszych niż optymalna. Jest ona zdefiniowana następująco(wg pliku pomocy do Excela 2007).
Tolerancja.
Wartość procentowa informująca, w jakim stopniu wartość komórki docelowej rozwiązania spełniająca
ograniczenia całkowite może odbiegać od rzeczywistej wartości optymalnej, aby została uznana za możliwą do
zaakceptowania. Ta opcja ma zastosowanie tylko w przypadku zadań z ograniczeniami całkowitymi. Wyższa
wartość tolerancji przyspiesza proces poszukiwania rozwiązania.
Domyślna wartość opcji Tolerancja to 5%. W Excelu 2010, 2013 i 2016 odpowiednikiem opcji Tolerancja jest
opcja Optymalność całkowitoliczbowa z domyślną wartością 1%
Ad. 3 Zminimalizować łączny czas pracy obrabiarek (obliczenia z całkowitoliczbowością zmiennych oraz
z ustawioną opcją Przyjmij model liniowy i wartością opcji Tolerancja 0%)
Aby uzyskać dokładny wynik, należy wartość wyżej wymienionej opcji wyzerować. Ponadto dla zwiększenia
dokładności wskazane jest użycie metody simpleks (Opcja Przyjmij model liniowy lub w Excelu
2010/2013/2016 w głównym oknie opcja Wybierz metodę rozwiązywania: LP simpleks)
P. Kowalik, Laboratorium badań operacyjnych - zadanie przydziału z ustalonym poziomem produkcji i limitowanym czasem
9
pracy  planowanie wielkości produkcji.
Rozwiązanie z warunkami całkowitoliczbowości zmiennych oraz włączoną opcją Solvera Przyjmij model
liniowy (albo dla wersji 2010+ Wybierz metodę rozwiązywania: LP simpleks) i opcją Tolerancja (albo dla
wersji 2010+ Optymalność całkowitoliczbowa) ustawioną na 0%.
*
xij
D1 D2 D3 D4
O1 200 1 0 61
O2 0 0 780 248
O3 0 799 0 291
Minimalny czas pracy potrzebny na wytworzenie wymaganej liczby detali to 7430,5 min (123 h 50 min
30 sek).