Transportproblem

[dominik_d]

Hallo zusammen,

ich bin ein absoluter Python-Einsteiger, respektive nutzen wir das Tool an der Uni im Rahmen eines Seminars. Ich finde es aber sehr hilfreich, was ich bis jetzt gesehen habe.

Ich möchte ein Transportproblem mit 6 Variablen lösen, wobei eine Variable je einer Lieferverbindung entspricht. Also xij entspricht einer Produktmenge, die vom Standort i zum Standort j transportiert wird.

Es gibt zwei Quellen und drei Senken mit Output (Produktionskapazitäten) und Input (Warenhäuser).

Auf dem Blattpapier kann ich das Gleichungssystem also die eine Gleichung mit den Restriktionen abbilden, aber Python spuckt nur Unsinn aus.

Wie ist da vorzugehen!?

Freue mich auf eine rege Diskussion.

Dominik

[EyDu]

Hallo und willkommen im Forum!

Wie sehen denn die Gleichungen und dein dazugehöriges Programm aus?

[dominik_d]

Wir nutzen Python 2.7.6.0. In der Spyderoberfläche sieht das dann so aus. Jedenfalls ist das mein Entwurf.
Aber er gibt mir kein Ergebnis für 6 Variablen, sondern nur für 3 und die entsprechen den Restriktionen 3 bis 5.

Code: Alles auswählen

from coopr.pyomo import *
from coopr.opt import SolverFactory

m = ConcreteModel()
m.x11 = Var(within = NonNegativeReals)
m.x12 = Var(within = NonNegativeReals)
m.x13 = Var(within = NonNegativeReals)
m.x21 = Var(within = NonNegativeReals)
m.x22 = Var(within = NonNegativeReals)
m.x23 = Var(within = NonNegativeReals)

m.obj = Objective(expr = (2500*m.x11 + 1700*m.x12 + 1800*m.x13 + 2500*m.x21 + 1800*m.x22 + 1400*m.x23)*90, sense=minimize)
m.con1 = Constraint(expr = m.x11 + m.x12 + m.x13 <= 350)
m.con2 = Constraint(expr = m.x21 + m.x22 + m.x23 <= 600)
m.con3 = Constraint(expr = m.x11 + m.x21 >= 325)
m.con4 = Constraint(expr = m.x12 + m.x22 >= 300)
m.con5 = Constraint(expr = m.x13 + m.x23 >= 275)


m.pprint()

inst = m.create()
inst.pprint()

opt = SolverFactory("glpk")
results = opt.solve(inst, suffixes= 'dual')
results.write()

[BlackJack]

@dominik_d: Also ist das weniger eine Python-Frage sondern wie man dieses `coopr`-Package benutzt.

[dominik_d]

Das ist durchaus möglich. Der Tutor ist pädagogisch leider suboptimal besetzt.
Mir ist gar nicht klar, wann man welches "Package" nutzt. An einer anderen Stelle wurde bspw. numpy genutzt ohne eine Erläuterung dazu.

Ich denke, dass man mit Python wirklich tolle Sachen machen kann, aber ich hab noch keinen richtigen Zugang dazu gefunden.
Im Großen und Ganzen geht es übrigens um die Modellierung von Kraftwerkparks zur Strombedarfsdeckung.

[EyDu]

So wie ich das sehe existiert keine Lösung für das Problem.

[BlackJack]

@dominik_d: Ich weiss nicht ob Du eventuell eine falsche Vorstellung davon hast was Python ist. Das ist eine allgemeine Programmiersprache. Darin kann man alles mögliche programmieren und es gibt Module und Pakete für alle möglichen Zwecke. Der Python Package Index listet etwa 44.000 Pakete. Einiges davon ist in reinem Python geschrieben, anderes enthält auch Erweiterungen die in C programmiert sind. Es gibt eigenständige Pakete, und solche die Software oder Bibliotheken, die in anderen Programmiersprachen geschrieben wurden, anbinden und von Python aus nutzbar machen.

In diesem Fall ist das Paket also Coopr. Und letztendlich verwendest Du zum Lösen konkret das GNU Linear Programming Kit, welches in C geschrieben ist.

Wenn Du also ein Problem *damit* hast, dann kann es sein, dass das kein allgemeines Python-Problem ist, sondern das man sowohl das Problemfeld, als auch diese eingesetzte Software kennen muss, um sinnvoll helfen zu können. Je spezieller das wird, umso unwahrscheinlicher wird es hier jemanden zu finden der sich damit auskennt. Das ist nicht total aussichtslos — hier lesen auch Studenten, Mathematiker, Naturwissenschaftler mit — ich wollte nur mal vorwarnen das es keine böse Absicht ist, wenn keine Antworten kommen.

@EyDu: Wenn ich das laufen lasse bekomme ich folgende Ausgabe (habe aber *keine* Ahnung wie man das deuten kann/soll):

Code: Alles auswählen

# ==========================================================
# = Solver Results                                         =
# ==========================================================
# ----------------------------------------------------------
#   Problem Information
# ----------------------------------------------------------
Problem: 
- Name: unknown
  Lower bound: 153675000.0
  Upper bound: 153675000.0
  Number of objectives: 1
  Number of constraints: 6
  Number of variables: 7
  Number of nonzeros: 13
  Sense: minimize
# ----------------------------------------------------------
#   Solver Information
# ----------------------------------------------------------
Solver: 
- Status: ok
  Termination condition: optimal
  Statistics: 
    Branch and bound: 
      Number of bounded subproblems: 0
      Number of created subproblems: 0
  Error rc: 0
# ----------------------------------------------------------
#   Solution Information
# ----------------------------------------------------------
Solution: 
- number of solutions: 1
  number of solutions displayed: 1
- Gap: 0.0
  Status: feasible
  Objective: 
    x1: 
      Id: 0
      Value: 153675000.0
  Variable: 
    x10:
      Id: 0
      Value: 325
    x12:
      Id: 2
      Value: 275
    x8:
      Id: 4
      Value: 300
  Constraint: 
    c_l_x5_:
      Dual: 153000
    c_l_x4_:
      Dual: 225000
    c_l_x6_:
      Dual: 126000

[EyDu]

@EyDu: Wenn ich das laufen lasse bekomme ich folgende Ausgabe (habe aber *keine* Ahnung wie man das deuten kann/soll):

Danke für den Hinweis, ich habe darauf mal einen anderen Solver ausprobiert. Der spuckt mir nun auch aus, dass es unendlich viele Lösungen gibt für obj = 153675000. Also auch der Wert, den das Programm ausspuckt.

Ich habe jetzt keine Lust das nachzuschauen, aber wahrscheinlich kann man den einzelnen Variablen auch Namen geben, dann sollte die Ausgabe auch lesbarer sein. So ist mir nicht klar, nach welchem Schema die Variablen durchnummeriert sind, ob da duale Variablen mit drin stecken und wie die anderen Lösungen aussehen.

Aber was lernt man aus der Geschichte: Verwende immer einen Zwei-Phasen-Solver, sonst sucht er dir keine initiale Lösung und scheitert. Argh