Program liniowy modelujący zadany problem
Oto problem, który próbuję rozwiązać:
„Firma wytwarza trzy produkty, nazwane produkt A, produkt B i produkt C. Firma ma 4 dostępnych pracowników, a pracownicy mają różne stawki za każdy z trzech produktów. Ponadto, ze względu na charakter ich umów, pracownicy pobierają różną kwotę w zależności od produktu, nad którym pracują. Czas potrzebny pracownikowi i na zrobienie iloczynu czasu A, B lub C oraz kwota, jaką pobierają w zależności od produktu, są podsumowane w dwóch tabelach dany.
Tabela 1: Czas w minutach potrzebny Pracownikowi i na wyprodukowanie jednej jednostki produktu j.
Tabela 2: Kwota zapłacona przez firmę za jedną godzinę pracownika i podczas pracy nad produktem j.
(Nie jestem w stanie tutaj utworzyć rzeczywistych tabel, ale dość łatwo jest zrozumieć, jaka jest struktura tabel z powyższych opisów tabel)
Załóżmy, że każdy pracownik pracuje 40 godzin tygodniowo. Ze względu na zobowiązania firmy wobec obecnych klientów, firma musi wyprodukować co najmniej 100 jednostek produktu A, 150 jednostek produktu B i 100 jednostek produktu C. Napisz program liniowy, który powie firmie, jak przypisać każdego pracownika, aby zapotrzebowanie na każdy widżet jest zaspokojone, a koszt dla firmy jest zminimalizowany.
Zatem musisz określić, jakie są zmienne decyzyjne, a następnie jaki jest wektor odpowiadający funkcji celu, macierz odpowiadająca ograniczeniom itp. "
Spędziłem godziny próbując sformułować to jako program liniowy i jedynym podejściem, jakie przyszło mi do głowy, było zminimalizowanie całkowitego kosztu poprzez nadanie mu postaci min CX, w której każdy element C, tj. C (i) (j) oznacza ilość, jaką pracownik i pobiera za pracę nad produktem j na jednostkę czasu, a każdy element X, tj. X (i) (j) oznacza całkowity czas, jaki pracownik i spędza na pracy nad produktem j. Ale to oczywiście nie jest właściwe podejście, ponieważ C i X mają być wektorami. Próbowałem wyszukać problemy, które mogą być podobne do tego, ale nie mogłem znaleźć żadnego.
Odpowiedzi
Jesteś na dobrej drodze. Możesz zgnieść$C$ i $X$macierze na wektory. Załóżmy na przykład, że masz dwóch pracowników i trzy produkty, więc to$C$ i $X$to macierze 2x3. Pozwolić$c=(C_{11}, C_{12}, C_{13}, C_{21}, C_{22}, C_{23})$ i pozwól $x = (X_{11}, \dots, X_{23})$. Teraz masz wektory.
Rozważmy okres planowania składający się z 1 tygodnia. Każdy pracownik pracuje 8 godzin dziennie i 5 dni w tygodniu, tak aby tygodniowy czas pracy był równy$40$ godziny $= 2,400$minuty. Pozwólcie przedstawić$4 \cdot 3 = 12 $ dodatnie zmienne całkowite oznaczone jako $x_{i,j}$ gdzie $i=1,2,3,4$ i $j=1,2,3$.
$x_{i,j}$ reprezentuje ilość j-tego produktu wykonanego przez i-tego pracownika, oczywiście powinna być dodatnią liczbą całkowitą.
$a_{i,j}$ to czas w minutach potrzebny pracownikowi i na wyprodukowanie jednej jednostki produktu j.
$b_{i,j}$ to koszt opłacony przez firmę za godzinę pracownika i podczas pracy nad produktem j
Chcemy sprostać tygodniowemu zapotrzebowaniu na te trzy produkty, wydając jak najmniej.
Funkcję celu można poprawnie sformułować jako
$ \min \sum_{i=1}^4 \sum_{j=1}^3 (a_{i,j}/60) \cdot b_{i,j} \cdot x_{i,j} $
z zastrzeżeniem $\left\{ \begin{array}{l} \sum_{i=1}^4 x_{i,1} \geq 100 \\ \sum_{i=1}^4 x_{i,2} \geq 150 \\ \sum_{i=1}^4 x_{i,3} \geq 100 \\ \sum_{j=1}^3 a_{1,j} x_{1,j} \leq 2,400 \\ \sum_{j=1}^3 a_{2,j} x_{2,j} \leq 2,400 \\ \sum_{j=1}^3 a_{3,j} x_{3,j} \leq 2,400 \\ \sum_{j=1}^3 a_{4,j} x_{4,j} \leq 2,400 \\ x_ij \in N \forall i=1,2,3,4 \forall j=1,2,3 \\ \end{array} \right. $
$ \sum_{i=1}^4 x_{i,j} \geq c_j $ wyznacza ograniczenie tygodniowego zapotrzebowania na j-ten produkt, gdzie $c_j $ to popyt na j-ty produkt.
$ \sum_{j=1}^3 a_{i,j} x_{i,j} $ to czas pracy spędzony przez i-tego pracownika, tzw $ \sum_{j=1}^3 a_{i,j} x_{i,j} \leq 2,400 $ wyznacza ograniczenie całkowitej ilości minut dostępnych dla i-tego pracownika w ciągu jednego tygodnia.