jakobwenzel - So 11.01.09 23:07
Titel: Optimale Aufstellung bei Wettbewerb
Hallo zusammen!
Bei einem Schwimmwettbewerb muss pro Disziplin eine bestimmte, je nach Disziplin verschiedene, Anzahl an Personen starten, die wiederum in nur einer bestimmten Gesamtanzahl an Disziplinen starten dürfen. Die Gesamtanzahl der Person ist auch festgelegt. Die Zeit der gesamten Mannschaft wird durch Addition der Einzelzeiten bestimmt.
Mein Programm soll nun aus einer Liste von Personen und ihren Zeiten in den einzelnen Disziplinen die optimale Aufstellung berechnen. Leider fällt mir dazu kein besserer Algorithmus als simples Durchprobieren aller Möglichkeiten ein, dessen Laufzeit bei 10 Personen und 5 Disziplinen schon relativ bescheiden ist (rechnet seit 50 Minuten...).
Gibt es da irgendeinen besseren Ansatz?
Crosspost DP:
http://www.delphipraxis.net/topic150001,0,asc,0.html
Vielen Dank schonmal im Voraus
Jakob
jakobwenzel - Mo 12.01.09 19:44
Whow, das hat mir schonmal sehr viel weiter geholfen.
Ich speicher mir jetzt eine Datei im "CPLEX LP Format" um dann mit der glpsol.exe die Lösung zu berechnen.
Die zu optimierenden Werte hab ich jetzt Ny/x genannt, wobei y die Zeile (=Person) und x die Spalte (=Disziplin) ist. Die Variablen können jeweils 1 (=dabei) oder 0 (=nicht dabei) haben.
So sieht das speichern dann in Delphi aus:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
| procedure SaveLP(filename: String;RowCount,ColCount:Integer);
var
sList: TStringList;
s:String;
Row: Integer;
Col: Integer;
begin
sList:=TStringList.Create;
sList.Add('Minimize');
for Row := 0 to RowCount - 1 do
begin
if Row>0 then
s:=' + '
else
s:='value: ';
for Col := 0 to ColCount - 1 do
s:=s+' '+TimeToSecStr(LPList[Row][Col])+' N'+Inttostr(Row)+'/'+Inttostr(Col)+' +';
sList.Add(Copy(s,1,length(s)-1));
end;
sList.Add('subject to');
for Col := 0 to ColCount - 1 do
begin
s:='ns'+Inttostr(col)+': ';
for Row := 0 to RowCount - 1 do
begin
s:=s+' N'+Inttostr(Row)+'/'+Inttostr(Col)+' +'
end;
s:=Copy(s,1,length(s)-1);
s:=s+' = '+Inttostr(RowList.HeaderRow.NumStarts[Col]);
sList.Add(s);
end;
for row := 0 to RowCount - 1 do
begin
s:='np'+Inttostr(row)+': ';
for col := 0 to ColCount - 1 do
begin
s:=s+' N'+Inttostr(Row)+'/'+Inttostr(Col)+' +';
end;
s:=Copy(s,1,length(s)-1);
s:=s+' <='+Inttostr(RowList.Settings.FNumPersonStarts);
sList.Add(s);
end;
sList.Add('Bounds');
for row := 0 to RowCount - 1 do
for col := 0 to ColCount - 1 do
sList.Add(' N'+Inttostr(Row)+'/'+Inttostr(Col)+' <=1');
sList.Add('Integer');
for row := 0 to RowCount - 1 do
for col := 0 to ColCount - 1 do
sList.Add(' N'+Inttostr(Row)+'/'+Inttostr(Col));
sList.SaveToFile(filename);
sList.Free;
end; |
Falls sich irgendwer den Code aufmerksam (naja, Kommentare lesen reicht eigentlich) durchgelesen hat, wird merken, dass die Beschränkung auf die Gesamtzahl noch fehlt, was auch noch mein Problem ist.
Bei dem Format kann man ja nur Faktor * Variable + nächster Faktor * ... rechnen, womit sich das meines Wissens nicht machen lässt.
Hat irgendwer nen Tipp? :wink:
Jakob