Borysław B.

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
Borysław B.

Borysław B. Mgr inżynier
informatyki,
właściciel Matrix
Reliability

Temat: Model matematyczny dla zagadnienia CPM-Cost

Oczywiście miałem na myśli macierz incydencji A.

Szkoda, że nikt nie ma dość wiedzy, by mi pomóc.Borysław Bobulski edytował(a) ten post dnia 20.01.10 o godzinie 19:05

Następna dyskusja:

OFERTA PRACY DLA MATEMATYKÓW




Wyślij zaproszenie do