Problem przydziału (przykład)
W pewnym dużym przedsiębiorstwie 4 sekretarki należy przydzielić do prowadzenia 4 różnych prac biurowych. Na podstawie obserwacji oszacowano czas (w min) jaki zajmuje tym sekretarkom wykonywanie poszczególnych prac, który podano w poniższej tabeli.
| Czas zadania 1 | Czas zadania 2 | Czas zadania 3 | Czas zadania 4 | |
|---|---|---|---|---|
| Sekretarka 1 | 420 | 480 | 240 | 360 |
| Sekretarka 2 | 480 | 420 | 300 | 360 |
| Sekretarka 3 | 420 | 540 | 300 | 420 |
| Sekretarka 4 | 360 | 480 | 360 | 480 |
Zakładając specjalizację sekretarek, tzn. że każda z nich będzie wykonywać tylko jedną pracę, określić optymalny z punktu widzenia minimalizacji łącznego czasu wykonywania prac przydział zadań sekretarkom. Sformułować model matematyczny zadania.
Rozwiązanie.
Krok 1. Rozwiązanie zadania za pomocą programu STORM.
uruchomić program STORM, wybrać moduł (2) Assignment i utworzyć nowy
model (Create a new data set).
wprowadzić następujące parametry do sekcji górnej:
title – ASNprzykład
number of rows (liczba sekretarek) – 4
number of cols (liczba zadań) – 4
objective type (typ funkcji celu) – MIN
wpisać parametry z tablicy czasu zadań do sekcji głównej
rozwiązać model (F7)
Rozwiązanie z programu STORM:
X = $\begin{matrix} & & 1 & \\ & 1 & & \\ & & & 1 \\ 1 & & & \\ \end{matrix}$
F(X) = 240 + 420 + 420 + 360 = 1440
Interpretacja rozwiązania : Sekretarka 1 powinna wykonywać pracę 3, sekretarka 2 – pracę 2, sekretarka 3 – pracę 4 i sekretarka 4 – pracę 1. Łączny czas wykonania wszystkich prac wyniesie 1440 minut.
Krok 2. Sformułowanie modelu matematycznego.
Wprowadzamy zmienne decyzyjne.
$$\text{xij} = \left\{ \begin{matrix}
1,\ \text{gdy}\ i - \text{ta}\ \text{sekretarka}\ be\text{dzie}\ \text{wykonywa}c\ j - a\ \text{prac}e \\
0,\ w\ \text{pozosta}l\text{yc}h\ \text{przypadkac}h \\
\end{matrix} \right.\ $$
Funkcja celu minimalizuje łączny czas pracy sekretarek:
f(xij) = 420x11 + 480x12 + 240x13 + 360x14 + 480x21 + 420x22 + 300x23 + 360x24 + 420x31 + 540x32 + 300x33 + 420x34 + 360x41 + 480x42 + 360x43 + 480x44 ⇒ min
Warunki, które muszą spełniać te zmienne, można zapisać następująco:
$$\left. \ \begin{matrix}
x11 + x12 + \ x13 + x14 = \ \ x1j = 1 \\
x21 + x22 + \ x23 + x24 = \ \ x2j = 1 \\
x31 + x32 + \ x33 + x34 = \ \ x3j = 1 \\
x41 + x42 + \ x43 + x44 = \ \ x4j = 1 \\
\end{matrix} \right\}\ \text{ka}z\text{da}\ \text{sekretarka}\ \text{mo}ze\ \text{wykonywa}c\ \text{tylko}\ \text{jedn}a\ \text{prac}e$$
$$\left. \ \begin{matrix}
x11 + x21 + \ x31 + x41 = \ \ \text{xi}1 = 1 \\
x12 + x22 + \ x32 + x42 = \ \ \text{xi}2 = 1 \\
x13 + x23 + \ x33 + x43 = \ \ \text{xi}3 = 1 \\
x14 + x24 + \ x34 + x44 = \ \ \text{xi}4 = 1 \\
\end{matrix} \right\}\ \text{ka}z\text{da}\ \text{praca}\ \text{mo}ze\ \text{by}c\ \text{wykonywana}\ \text{tylko}\ \text{przez}\ \text{jedn}a\ \text{sekterark}e$$
Zadania
Zadanie 89.
Określić optymalny przydział 5 pracowników do wykonywania czterech wyrobów, mając daną w poniższej tabeli liczbę baraków, jaką wytwarzają oni w ciągu tygodnia. Znak X oznacza, że pracownik 3 nie ma kwalifikacji do wytwarzania wyrobu 2. Sformułować model.
| Pracownik 1 | Pracownik 2 | Pracownik 3 | Pracownik 4 | Pracownik 5 | |
|---|---|---|---|---|---|
| Wyrób 1 | 20 | 26 | 22 | 16 | 30 |
| Wyrób 2 | 22 | 12 | x | 20 | 25 |
| Wyrób 3 | 8 | 16 | 14 | 6 | 10 |
| Wyrób 4 | 27 | 20 | 18 | 6 | 9 |
$$\text{xij} = \left\{ \begin{matrix}
1,\ \text{gdy}\ i - \text{ty\ }wyrob,\ j - \text{ty}\ \text{pracownik\ wykonuj}a\text{cy\ }wyrob \\
0,\ w\ \text{pozosta}l\text{yc}h\ \text{przypadkac}h \\
\end{matrix} \right.\ $$
Funkcja celu minimalizuje łączne braki pracowników dla wyrobów:
f(xij)=20x11+26x12+ 22x13+16x14+ 30x15+ 22x21+12x22+ 0x23+20x24+ 25x25+ 8x31+16x32+ 14x33+6x34+ 10x35+ 27x41+ 20x42+ 18x43+ 6x44 + 9x45 ->min
Warunki, które muszą spełniać te zmienne, można zapisać następująco:
$$\left. \ \begin{matrix}
x11 + x12 + \ x13 + x14\ + x15 = \ \ x1j = 1 \\
x21 + x22 + \ \mathbf{x}\mathbf{23} + x24\ + x25\ = \ \ x2j = 1 \\
x31 + x32 + \ x33 + x34\ + x35 = \ \ x3j = 1 \\
x41 + x42 + \ x43 + x44\ + x45 = \ \ x4j = 1 \\
\end{matrix} \right\}\ \text{ka}z\text{dy}\ wyrob\ \text{mo}ze\ byc\ wykonywany\ przez\ jednego\ prac.$$
$$\left. \ \begin{matrix}
x11 + x21 + \ x31 + x41 = \ \ \text{xi}1 = 1 \\
x12 + x22 + \ x32 + x42 = \ \ \text{xi}2 = 1 \\
x13 + \mathbf{x}\mathbf{23} + \ x33 + x43 = \ \ \text{xi}3 = 1 \\
x14 + x24 + \ x34 + x44 = \ \ \text{xi}4 = 1 \\
x15 + x25 + \ x35 + x45 = \ \ xi5 = 1 \\
\end{matrix} \right\}\ \text{ka}z\text{dy}\ praocniwk\ moze\ wykonywac\ jeden\ wyrob.$$
Interpretacja rozwiązania :
Pracownik1 powinien wykonywać pracę 3, pracownik 2 – wogóle, pracownik 3 – pracę 2 i pracownik 4 – pracę 1, pracownik 5 pracę 4. Łączne braki wyniosą 33.
Zadanie 91.
Firma konsultingowa zawarła umowy na wykonanie trzech projektów, które powinny być zrealizowane w możliwie najkrótszym czasie. Spośród pracowników firmy wytypowano czterech, którym można powierzyć kierowanie tymi projektami. Kandydaci sami ocenili liczbę dni, jaka byłaby potrzebna kierowanym przez nich zespołem na wykonanie poszczególnych projektów. Znak x oznacza że pracownik nie podejmie się wykonania projektu.
| Projekt 1 | Projekt 2 | Projekt 3 | |
|---|---|---|---|
| Kandydat 1 | 16 | 20 | 14 |
| Kandydat 2 | 19 | x | 20 |
| Kandydat 3 | 17 | 19 | 18 |
| Kandydat 4 | 21 | 16 | 25 |
Przydzielić kandydatów do kierowania poszczególnymi projektami, tak aby czas (liczba dni) potrzebny na realizację projektów był możliwie najkrótszy. Który z pracowników nie otrzyma zlecenia? Sformułować model.
$$\text{xij} = \left\{ \begin{matrix}
1,\ \text{gdy}\ i - \text{ty\ }\text{kandydat}\ \text{nadzoruje\ projekt}\ j - \text{ty}\ \text{projekt} \\
0,\ w\ \text{pozosta}l\text{yc}h\ \text{przypadkac}h \\
\end{matrix} \right.\ $$
Funkcja celu minimalizuje łączne czas na realizację projektów:
f(xij)= 16x11 + 20x12 + 14x13 +
19x21 + 20x23 +
17x31 + 19x32 + 18x33 +
21x41 + 16x42 + 25x43 ->min
Warunki, które muszą spełniać te zmienne, można zapisać następująco:
$\left. \ \begin{matrix} x11 + x12 + \ x13 = \ \ x1j = 1 \\ x21 + \mathbf{x}\mathbf{22} + \ x23 = \ \ x2j = 1 \\ x31 + x32 + \ x33 = \ \ x3j = 1 \\ x41 + x42 + \ x43 = \ \ x4j = 1 \\ \end{matrix} \right\}\ \text{ka}z\text{dy}\ \text{kandydat}\ \text{mo}ze\ kierowac\ \text{tylko}\ \text{jeden}\text{ym}\text{\ projekt}$em
$$\left. \ \begin{matrix}
x11 + x21 + \ x31 + x41 = \ \ \text{xi}1 = 1 \\
x12 + \mathbf{x}\mathbf{22} + \ x32 + x42 = \ \ \text{xi}2 = 1 \\
x13 + x23 + \ x33 + x43 = \ \ \text{xi}3 = 1 \\
\\
\\
\end{matrix} \right\}\ \text{ka}z\text{dy}\ \text{projekt}\ \text{mo}ze\ \text{by}c\ \text{nadzorowany}\ \text{tylko}\ p\text{rzez}\ \text{jedn}\text{ego\ }\text{kan.}$$
Zadanie 92.
Pewna firma dysponuje m.in. trzema samochodami osobowymi. Ponieważ samochody są eksploatowane już co najmniej od kilku lat, postanowiono wymienić je na nowe. Równocześnie zdecydowano, że star zostaną zaproponowane na korzystnych warunkach pracownikom firmy. Ogłoszono przetarg, w którym oferty z propozycją ceny, jaką są gotowi zapłacić (tys. zł), złożyło czterech pracowników.
| Ford | Mercedes | Polonez | |
|---|---|---|---|
| Oferta 1 | 19 | 35 | 15 |
| Oferta 2 | 21 | 39 | 12 |
| Oferta 3 | 18 | 40 | 14 |
| Oferta 4 | 20 | 26 | 16 |
Znaleźć optymalny przydział samochodów poszczególnym pracownikom, tak aby zmaksymalizować dla firmy przychód ze sprzedaży samochodów. Podać wysokość przychodu. Sformułować model.
$$\text{xij} = \left\{ \begin{matrix}
1,\ \text{gdy}\ i - ta\ oferta\ na\ samochod\ j - \text{ty}\ samochod \\
0,\ w\ \text{pozosta}l\text{yc}h\ \text{przypadkac}h \\
\end{matrix} \right.\ $$
Funkcja celu maksymalizuje łączny przychód ze sprzedaży samochodów
f(xij)= 19x11 + 35x12 + 15x13 + 21x21 + 39x22 + 12x23 + 18x31 + 40x32 + 14x33 + 20x41 + 26x42 + 16x43 ->max
Warunki, które muszą spełniać te zmienne, można zapisać następująco:
$$\left. \ \begin{matrix}
x11 + x12 + \ x13 = \ \ x1j = 1 \\
x21 + x22 + \ x23 = \ \ x2j = 1 \\
x31 + x32 + \ x33 = \ \ x3j = 1 \\
x41 + x42 + \ x43 = \ \ x4j = 1 \\
\end{matrix} \right\}\ \text{ka}z\text{da\ oferta}\ \text{mo}ze\ dotyczycc\ jednogo\ samochodu$$
$$\left. \ \begin{matrix}
x11 + x21 + \ x31 + x41 = \ \ \text{xi}1 = 1 \\
x12 + x22 + \ x32 + x42 = \ \ \text{xi}2 = 1 \\
x13 + x23 + \ x33 + x43 = \ \ \text{xi}3 = 1 \\
\\
\\
\end{matrix} \right\}\ \text{ka}z\text{dy}\ samochod\ moze\ miec\ tylko\ jedna\ ofert\text{\ LISTNUM\ }$$
Zarządzanie projektami. Metoda CPM (przykład)
Czynności składające się na przedsięwzięcie zamontowania silnika do samochodu, kolejność ich wykonywania oraz czasy trwania (w min) ustalone przed konstrukcję projektu zestawiono w poniższej tabeli.
| Czynności | Opis czynności | Czas trwania | Czynności poprzedzające |
|---|---|---|---|
| A | Zaczepić silnik hakami uchwytu | 3 | - |
| B | Podnieść silnik do góry | 2 | A |
| C | Opuścić silnik | 4 | B |
| D | … | 5 | A |
| E | … | 7 | C, D |
| F | … | 10 | C, D |
| G | … | 5 | E, F |
| H | … | 7 | E, F |
| I | … | 8 | G, H |
| J | … | 3 | I |
| K | … | 8 | J |
| L | … | 3 | J |
| M | … | 2 | J |
| N | … | 7 | K, L, M |
| O | … | 5 | C, D |
| P | … | 10 | O |
| R | … | 10 | P |
| S | … | 17 | I |
| T | … | 5 | R |
| U | … | 1 | T |
| W | … | 30 | N, U |
| X | … | 10 | S, W |
| V | … | 8 | S, W |
| Y | … | 15 | V, X |
| Z | … | 23 | Y |
Wyznaczyć termin końcowy realizacji przedsięwzięcia Tk oraz podać, jakie czynności leżą na ścieżce krytycznej. Co oznacza ścieżka krytyczna?
Rozwiązanie.
Rozwiązanie za pomocą programu STORM
uruchomić program STORM, wybrać moduł (6) Project Management CPM/PERT i utworzyć nowy model (Create a new data set)
wprowadzić następujące parametry do sekcji górnej:
title – CPMprzyklad
number of activites – 25 (maksymalnie może być 30)
activity time option – DET (wybranie opcji PROB powoduje zastosowanie probabilistycznej metody rozwiązania zadania – PERT; DET oznacza deterministyczną metodę, czyli CPM)
activity representation option – NODE (activity–on-node określamy bezpośrednich poprzedników, maksymalnie 25; activity-on-arc bezpośredni poprzednicy nie muszą być określeni
number of predecessor columns – 3 (maksymalna liczba poprzedników jaka może wystąpić do jednej czynności)
wpisać parametry czynności z tablicy głównej
rozwiązać model (F7)
Interpretacja rozwiązania : Termin końcowy realizacji przedsięwzięcia Tk = 130 (termin zamontowania silnika do samochodu), a na ścieżce krytycznej leżą następujące czynności: a-b-c-f-h-i-j-k-n-w-x-y-z.
Aby przedsięwzięcie zrealizować w najkrótszym możliwym czasie, przyjmuje się, że najpóźniejszy dopuszczalny moment zaistnienia zdarzenia końcowego jest równy najwcześniejszemu możliwemu terminowi jego zaistnienia.
Ścieżka krytyczna to droga, której czas przejścia jest najdłuższy (wszystkie czynności muszą być zakończone), a czas jej trwania (suma czasów kolejnych czynności) jest równy terminowi końcowemu. Czynności i zdarzenia leżące na ścieżce krytycznej mają zerowe zapasy czasu. Wyznaczenie ścieżki krytycznej ułatwia kontrolę przebiegu realizacji przedsięwzięcia i dotrzymanie terminu końcowego. W trakcie realizacji projektu szczególną uwagę należy zwrócić na czynności krytyczne – przekroczenie terminu zakończenia którejkolwiek z nich spowoduje opóźnienie całego projektu.
Zadania
Zadanie 131.
Mając dane zawarte w poniższej tabeli obliczyć najkrótszy czas realizacji przedsięwzięcia oraz wyznaczyć ścieżkę krytyczną. Opóźnienie których czynności spowoduje opóźnienie całego projektu?
| Czas trwania czynności | Oznaczenia czynności | Czynności poprzedzające |
|---|---|---|
| 5 | A | - |
| 7 | B | - |
| 4 | C | - |
| 2 | D | A |
| 8 | E | C |
| 3 | F | B, D, E |
| 2 | G | F |
| 5 | H | F |
| 6 | I | F |
| 4 | J | G |
| 3 | K | H |
| 1 | L | i |
Wyszukiwarka