Borysław
B.
Mgr inżynier
informatyki,
właściciel Matrix
Reliability
Temat: Model matematyczny dla zagadnienia CPM-Cost
Witam,Chciałem uprzejmie spytać czy ktoś nie pomógłby mi zbudować poprawny model matematyczny dla zagadnienia CPM-Cost.
Chodzi mi o model matematyczny w którym opiszę minimalizację kosztu realizacji projektu przy zadanym czasie dyrektywnym za pomocą programowania liniowego.
mamy sieć, którą przedstawia graf skierowany.
przyjmijmy, że mamy oznaczenia:
i, j - są to pary opisujące połączenie między elementem i, oraz elementem j w grafie
wektory t1_ij, t2_ij - są to odpowiednio czas graniczny dla połączenia i-j, któremu odpowiada wektor kosztów k1_ij, oraz czas normatywny, któremu odpowiada wektor kosztów k2_ij.
dla przykładu:
i | j | t1_ij | t2_ij | k1_ij | k2_ij|
--------------------------------------
1 | 2 | 10 | 200 | 20 | 100 |
2 | 3 | 20 | 300 | 10 | 150 |
...
Jak widać -
Czas normatywny (czyli ten najdłuższy przy którym koszt jest najmniejszy), oraz czas graniczny (czyli ten najkrótszy przy którym koszt jest największy) jest podany dla odpowiednich połączeń i-j.
Wyznaczam czas minimalny Tmin dla całego przedsięwzięcia za pomocą metody ścieżki krytycznej (Critical Path Method) używając wektora t1 dla połączeń i-j, oraz czas maksymalny (dyrektywny) Tmax za pomocą CPM dla wektora t2
Teraz rozwiązuje zadanie za pomocą programowania liniowego
??? Brak modelu ???
Rozwiązaniem zagadnienia jest wykres zależności kosztu przedsięwzięcia od czasu realizacji całego projektu. Rozwiązanie pokazuje jaki koszt przedsięwzięcia poniesiemy w określonym czasie, który mieści się między Tmin a Tmax.
Zacząłem budować model:
tij - niewiadome
dla każdego i, j
tij <= t2_ij //(normatywny)
tij >= t1_ij //(graniczny)
jeśli dla każdego połączenia i-j dla odpowiadających im danych z wektorów t1_ij, k1_ij, t2_ij, k2_ij
otrzymujemy wykres dany funkcją liniową k = at + b, a dokładniej
kij = aij*tij + bij to
Koszt całkowity przedsięwzięcia = (Suma po i,j) kij = (Suma po i,j)aij * tij + bij
func - to funkcja celu, którą minimalizujemy
Mamy więc ograniczenia dolne, ograniczenia górne, funkcję celu, brakuje nam tylko opisu sieci. Sieć, która jest grafem, chcę opisać w macierzy A. W macierzy A 1 oznacza połączenie "do", -1 połączenie wychodzące "od", 0 - brak połączenia
Co uzupełnić by model matematyczny był poprawny?Borysław Bobulski edytował(a) ten post dnia 20.01.10 o godzinie 19:06