Autor Beitrag
jakobwenzel
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1889
Erhaltene Danke: 1

XP home, ubuntu
BDS 2006 Prof
BeitragVerfasst: So 11.01.09 23:07 
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: www.delphipraxis.net...c150001,0,asc,0.html

Vielen Dank schonmal im Voraus

Jakob

_________________
I thought what I'd do was, I'd pretend I was one of those deaf-mutes.
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: So 11.01.09 23:37 
Das ganz durchzudenken bin ich gerade nicht mehr in der Lage, hört sich aber nach Linearer Programmierung an; dafür gibt es z.B. GLPK: www.gnu.org/software/glpk/

_________________
>λ=
jakobwenzel Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1889
Erhaltene Danke: 1

XP home, ubuntu
BDS 2006 Prof
BeitragVerfasst: 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:
ausblenden volle Höhe 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;

  //Berechnung der Zeit
  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');

  //Anzahl Starts pro Disziplin
  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;

  //Starts pro Person
  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

_________________
I thought what I'd do was, I'd pretend I was one of those deaf-mutes.