Solver "solved" nicht
Jörg Nissen
ich habe eigentlich ein klassisches Problem für den Solver. Ich habe
verschiedene Abteilungen, die einen bestimmten Werbeetat (nach einem
Punktesystem) haben. Dieser Werbeetat kann pro Abteilung für bestimmte
Werbeprojekte ausgegeben werden. Je nach Abteilung kann die betreffende
Abteilung 2 bis 7 Werbeprojekte starten.
Das Ergebnis der Vorjahresprojekte ist bekannt und der Erfolg (ebenfalls
nach einem Punktesystem) liegt vor. Ich möchte nun den maximalen Erfolg
bei einem vorgegebenen Werbeetat ermitteln. Dazu habe ich folgende
Tabelle aufgestellt.
Etat: 138 Etat max.: 140
Erfolg: 1025
Abteilung 1
Kosten Erfolg Projekt Solver erw. Erfolg
8 23 A 0 0
7 23 B 0 0
6 29 C 1 29
7 23 D 0 0
5 25 E 0 0
7 32 F 1 32
Abteilung 2
5 35 A 1 35
8 33 B 0 0
.
.
.
Abteilung 6
7 47 A 1 47
7 44 B 0 0
4 45 C 1 45
8 45 D 0 0
7 40 E 0 0
Solver soll nun das Feld "Erfolg" maximieren. Dazu ist die Spalte
"Solver" als "veränderbare Werte" mit der Nebenbedingung "binär"
definiert. Weitere Nebenbedingungen sind eine Zwischensumme der Spalte
Solver pro Abteilung, die gleich der Werbeprojekte (2 bis 7) sein muß,
sowie "Etat" <= "Etat max.".
Die Formel im Feld "Erfolg" lautet "=Summenprodukt(B:B;D:D)".
Ich habe Solver mit verschiedenen Optionen laufen lassen, bin aber mit
keinem Ergebnis zufrieden. Wenn ich meine Tabelle erzeugt habe und
Solver zum ersten Mal laufen lasse (Option "Lineares Modell
voraussetzen" deaktiviert), findet er kein Ergebnis. Alle Werte in der
"Solver"-Spalte stehen auf "0".
Aktiviere ich die Option "Lineares Modell voraussetzen", bricht die
Verarbeitung mit dem Fehler "Das lineare Modell wurde nicht eingehalten"
ab, ich habe aber eine Lösung. Diese ist zwar nicht die optimale, aber
immerhin.
Starte ich Solver dann noch einmal ohne die besagte Option, finder
Solver keine passende Lösung, die präsentierte Zwischenlösung
berücksichtigt aber die Nebenbedingung "Maximale Werbeprojekte in dieser
Abteilung" nicht (Wert ist um 1 zu hoch). Passe ich diese Lösung dann
manuell an (bewußt nicht die optimale Lösung) und starte Solver erneut,
behauptet er ganz stolz, eine Lösung gefunden zu haben. Statt nun aber
meine Lösung zu optimieren, übernimmt er einfach meine manuell
korrigierte.
Die ganze Geschichte ist mittlerweile sehr frustrierend, da jede
Excel-Dokumentation behauptet, Solver sei "das Werkzeug", um solche
Probleme zu lösen.
Vielleicht übersehe ich ja einen entscheidenden Faktor. Jede Hilfe wird
dankbar angenommen.
mfg
Jörg
P.S.: Excel 97 SR2
Franz-Josef Raabe
ich kenne die zugrundeliegenden Verfahren nicht explizit, aber
grundsätzlich braucht der Solver ein Problem, bei dem schrittweise
leichte Änderungen der Lösung auch die Zielvariable ändern. Das scheint
auch bei binären Variablen nötig zu sein. Wenn sich die Zielvariable
unter Berücksichtigung der Nebenbedingungen nur in Sprüngen ändert,
scheitert der Solver. Ganz schlichtes Beispiel einer Sprungfunktion, die
der Solver nicht hinkriegt:
Zelle A1: =(A2=B2)*1
Zelle A2: 1
Zelle B2: 0
A1 ist immer dann = 1, wenn A2 gleich B2 ist, sonst 0. A1 soll maximiert
werden, B2 ist veränderbarer Wert, Nebenbedinung binär.
Der Solver behauptet, B2 = 0 sei Optimum. Das liegt daran, daß jede
_kleine_ Änderung an B2 die Zielzelle A1 nicht verändert. Dass B2=1 sein
muß sieht zwar jeder der Formel an, der Solver aber nicht. Er wendet die
Formel aber nur an, und die liefert praktisch immer 0.
Es könnte sein, daß Deine Zielfunktion über die Nebenbedingung
"Werbeprojekte der Abteilung" ähnlich gelagert ist.
Der Solver ist leider kein generelles Optimierungsprogramm, sondern
testet schrittweise Änderungen. Damit bleibt er sogar bei
differenzierbaren Funktionen aus der Schule an lokalen Extremwerten
hängen, mit Pech sogar an einem Minimum, obwohl er ein Maximum suchen
soll.
MfG
Franz-Josef
Jörg Nissen schrieb:
Jörg Nissen
vielen Dank für Deine Erläuterungen zu diesem Thema. Der Solver scheint
wirklich nicht der "King" unter den Excel-Tools zu sein.
Mittlerweile ist es mir aber nach vielem probieren und überlegen gelungen, den
Solver doch dazu zu überreden, eine Lösung zu liefern. Es scheint sogar nach
oberflächlicher Prüfung tatsächlich das Optimum zu sein.
Gibt es vielleicht irgendwo gute Dokumentation zu diesem Tool?
mfg
Jörg
Franz-Josef Raabe schrieb: