// (C) Jörg Bewersdorff 07-2003

// ====== SimplexTableau ==================================================

// Eine Instanz des Objekts SimplexTableau entspricht einem Simplex-Tableau
// zur Lösung eines Linearprogrammes der Form
//            cx  = Max!
//            Ax <= b              
//             x >= 0
// Die Zeilen und Spalten sind indiziert mit den Bezeichnungen der Variablen
// x and b.

// Starttableau:
// entstprechend
//            Zmax  =     cx  -> Max!
//      Schlupf(b)  = b - Ax
//               x >= 0
//
//                1    x1    x2     ...
//  Zmax          0    c1    c2     ...
//  Schlupf(b1)   b1  -a11  -a12    ...
//  Schlupf(b2)   b2  -a21  -a22    ...

// Beispiel:
// Set LP = new SimplexTableau()
// LP.Set_c("Name von x1", -2.0);
// LP.Set_c("Name von x2",  1.0);
// ...
// LP.Set_a("Name von b1", "Name von x1", 1.0);
// LP.Set_a("Name von b2", "Name von x3", 2.0);
// ...
// LP.Set_b("Name von b1", 3.0);
// ...
// LP.Optimiere();

// Output:
// LP.Max(), LP.Wert("Name von x1"), LP.Wert("Schlupf(Name von b2)")

// Der mathemtische Hintergrund wird u.a erläutert in
// Jörg Bewersdorff, "Glück, Logik und Bluff: Mathematik im Spiel -
// Methoden, Ergebnisse und Grenzen", Kapitel 3.4



function SimplexTableau()
{
  // Eigenschaften:
  this.fastnull=0.000000001;            // Const (überschreibbar)
  this.unendlich=1E20;                  // Const (überschreibbar)
  this.ZeilenName = new Abbildung();    // ZeilenNr  -> Variablenbezeichnung
  this.SpaltenName = new Abbildung();   // SpaltenNr -> Variablenbezeichnung
  this.ZeilenNr = new Abbildung();      // Variablenbezeichnung -> ZeilenNr     (während Init.)
  this.SpaltenNr = new Abbildung();     // Variablenbezeichnung -> SpaltenNr    (während Init.)
  this.a = new Abbildung();             // ZeilenNr,SpaltenNr -> Wert
  this.ZeilenAnz = 0;
  this.SpaltenAnz = 0;
  this.Status=0;                        // 0 vor Optimiere, 1 danach
  this.ZeilenName.DefBild(0,"Zmax");
  this.ZeilenNr.DefBild("Zmax",0);
  this.SpaltenName.DefBild(0,"1");
  this.SpaltenNr.DefBild("1",0);

  // Methoden:
  this.Set_a = SimplexTableauSet_a;
  this.Set_b = SimplexTableauSet_b;
  this.Set_c = SimplexTableauSet_c;
  this.Optimiere = SimplexTableauOptimiere;
  this.Max = SimplexTableauMax;
  this.Wert = SimplexTableauWert;
  this.Schattenpreis = SimplexTableauSchattenpreis;
  this.a_=SimplexTableaua_;
  this.SimplexSchritt=SimplexTableauSimplexSchritt;
  this.AsTable=SimplexTableauAsTable;
}

// ==========================================================================


function SimplexTableauSet_a(xName, bName, Wert)
// Setzt die Matrix-Koeffizienten
// (der Default-Wert ist 0):
{
  var z,s;
  if (this.Status>0)
  {
    alert("Kein Schreibzugriff mehr auf das Simplex-Tableau");
    return;
  }
  
  if (!this.ZeilenNr.DefBereichMember(bName))
  // Variable bName ist bisher noch nicht aufgetaucht:
  {
    this.ZeilenAnz++;
    this.ZeilenName.DefBild(this.ZeilenAnz,bName);
    this.ZeilenNr.DefBild(bName,this.ZeilenAnz);
  }

  if (!this.SpaltenNr.DefBereichMember(xName))
  // Variable xName ist bisher noch nicht aufgetaucht:
  {
    this.SpaltenAnz++;
    this.SpaltenName.DefBild(this.SpaltenAnz,xName);
    this.SpaltenNr.DefBild(xName,this.SpaltenAnz);
  }

  z=this.ZeilenNr.Bild(bName);
  s=this.SpaltenNr.Bild(xName);
  this.a.DefBild(z+","+s,-Wert);
}


function SimplexTableauSet_b(bName, Wert)
// Setzt die Koordinaten des Spaltenvektors b:
// (der Default-Wert ist 0)
{
  this.Set_a("1",bName,-Wert);
}


function SimplexTableauSet_c(xName, Wert)
// Setzt die Koordinaten des Zeilen-Vektors c:
// (der Default-Wert ist 0)
{
  this.Set_a(xName,"Zmax",-Wert);
}


function SimplexTableauOptimiere()
// führt die eigentliche Optimierung durch:
{
  var s,z,zName;
  if (this.Status!=0)
  {
    alert("Keine nochmalige Optimierung möglich");
    return;
  }
  this.Status=1;

  if (this.ZeilenAnz*this.SpaltenAnz==0)
  {
    alert("Optimierung ohne Daten nicht möglich");
    return;
  }

  // Fülle die Matrix mit Nullen auf:
  for (z=0;z<=this.ZeilenAnz;z++)
    for (s=0;s<=this.SpaltenAnz;s++)  
      if (!this.a.DefBereichMember(z+","+s))
        this.a.DefBild(z+","+s,0);

  // Ändere die Bezeichnungen der Zeilen:
  for (z=1;z<=this.ZeilenAnz;z++)
  {
    zName=this.ZeilenName.Bild(z);
    this.ZeilenName.DefBild(z,"Schlupf("+zName+")");
  }
   
  // lösche Abbildungen Var.Namen -> Zeilen-/Spaltennummern
  this.ZeilenNr = null;
  this.SpaltenNr = null;


  while (this.Status==1)
    this.SimplexSchritt();

  if (this.Status==3)
  {
    alert("Es existiert kein Maximum");
    return;
  }
}


function SimplexTableauMax()
// Maximum des Linear-Programmes:
{
  if (this.Status==0)
    this.Optimiere();

  if (this.Status==3)
  {
    alert("Es existiert kein Maximum");
    return;
  }
  return this.a_(0,0);
}


function SimplexTableauWert(VariablenName)
// Wert einer Variable zur Erreichung des Maximums:
{
  if (this.Status==0)
    this.Optimiere();

  if (this.Status==3)
  {
    alert("Es existiert kein Maximum");
    return "";
  }

  if (this.ZeilenName.BildBereichMember(VariablenName))
    return this.a_(this.ZeilenName.Urbild(VariablenName),0);

  if (this.SpaltenName.BildBereichMember(VariablenName))
    return 0;

  alert("Die Variable '" + VariablenName + "' ist unbekannt");
  return "";
}


function SimplexTableauSchattenpreis(VariablenName)
// Schattenpreis einer Variable im Maximum:
{
  if (this.Status==0)
    this.Optimiere();

  if (this.Status==3)
  {
    alert("Es existiert kein Maximum");
    return "";
  }

  if (this.ZeilenName.BildBereichMember(VariablenName))
    return 0;

  if (this.SpaltenName.BildBereichMember(VariablenName))
    return this.a_(0,this.SpaltenName.Urbild(VariablenName));

  alert("Die Variable '" + VariablenName + "' ist unbekannt");
  return "";
}


function SimplexTableaua_(zeile, spalte)
// vereinfachter Lese-Zugriff auf die Matrix-Elemente:
{
  return this.a.Bild(zeile+","+spalte);
}


function SimplexTableauSimplexSchritt()
// Ein Austauschschritt wird berechnet; der dabei erreichte Status
// (Abbruch, ...) wird in this.Status eingetragen
{
  var s, z, sPivot, zPivot, max0, minPiv, zNameAlt, sNameAlt, norm, fastnullAkt, Akt;

  // 1. Pivotsuche zur Vorbereitung eines Austauschschrittes:
  // a) Pivotzeile (suche Maximum in der nullten Zeile [ohne Spalte 0]):
  max0 = -this.unendlich;
  for (s=1;s<=this.SpaltenAnz;s++)
  {
    Akt=this.a_(0,s);
    if (Akt>max0)
    {
      max0=Akt;
      sPivot=s;      
    }
  }

  if (max0<=this.fastnull)
  // Simplex-Kriterium ist erfüllt: Maximum ist erreicht:
  {
    this.Status=2;
    return;
  }

  // b) suche Pivotzeile:
  // suche betragsmäßig minimalen Quotienten (gebildet aus 0. Zeile und 
  // Pivotspalte [sofern dort negativ]):
  minP = this.unendlich;                    // Initialisierung
  zPivot=0;
  for (z=1;z<=this.ZeilenAnz;z++)
  {
    Akt=this.a_(z, sPivot);                 // Pivotspaltenelement
    if (Akt<-this.fastnull)
    // Zeile besitzt negativen Eintrag in Pivotspalte:    
    {
      Akt=-this.a_(z,0)/Akt;                // negativer Quotient
      if (Akt<minP)
      // neues Minimum erreicht:
      {
        zPivot=z;
        minP=Akt;
      }
    }
  }
  if (zPivot==0) 
  {
    this.Status=3;          // unbeschränktes Maximum
    return;
  }

  // 2. Austausch:
  // a) vertausche die Variablen-Indezees:
  zNameAlt = this.ZeilenName.Bild(zPivot);
  sNameAlt = this.SpaltenName.Bild(sPivot);
  this.ZeilenName.DefBild(zPivot,sNameAlt);
  this.SpaltenName.DefBild(sPivot,zNameAlt);


  // b) Pivotelement:
  this.a.DefBild(zPivot+","+sPivot, 1/this.a_(zPivot,sPivot));

  // c) Pivotzeile (Berechnung mit aktuallisiertem Pivotelement):
  for (s=0;s<=this.SpaltenAnz;s++)
    if (s!=sPivot)
      this.a.DefBild(zPivot+","+s, -this.a_(zPivot,s)*this.a_(zPivot,sPivot));

  // d) Alles außer Pivotzeile und -spalte (Berechnung mit aktualisierter
  //    Pivotzeile und noch  u n v e r ä n d e r t e r  Pivotspalte):
  for (z=0;z<=this.ZeilenAnz;z++)
    if (z!=zPivot)
      for (s=0;s<=this.SpaltenAnz;s++)
        if (s!=sPivot)
          this.a.DefBild(z+","+s, this.a_(z,s)+this.a_(z,sPivot)*this.a_(zPivot,s));


  // e) Pivotspalte (Berechnung mit aktuallisiertem Pivotelement):
  for (z=0;z<=this.ZeilenAnz;z++)
    if (z!=zPivot)
      this.a.DefBild(z+","+sPivot, this.a_(z,sPivot)*this.a_(zPivot,sPivot));

  // f) Werte, die fast gleich 0 sind, werden gleich 0 gesetzt:
  norm = 0
  for (z=0;z<=this.ZeilenAnz;z++)
    for (s=0;s<=this.SpaltenAnz;s++)
      norm = norm + Math.abs(this.a_(z,s));
  norm = norm/this.ZeilenAnz/this.SpaltenAnz;
  fastnullAkt = norm * this.fastnull;
  for (z=0;z<=this.ZeilenAnz;z++)
    for (s=0;s<=this.SpaltenAnz;s++)
      if (Math.abs(this.a_(z,s))<fastnullAkt)
        this.a.DefBild(z+","+s, 0);
}


function SimplexTableauAsTable()
{
  var ret,s,z,R;
  R=1000000;
  ret='<br><table cellspacing="7">';
  for (z=-1;z<=this.ZeilenAnz;z++)
  {
    ret=ret+"<tr>";
    for (s=-1;s<=this.SpaltenAnz;s++)
    {
      if ((s==-1) && (z==-1))
        ret=ret+"<td></td>";
      else if (s==-1)
        ret=ret+"<td>"+this.ZeilenName.Bild(z)+"</td>";
      else if (z==-1)
        ret=ret+"<td>"+this.SpaltenName.Bild(s)+"</td>";
      else     
        ret=ret+"<td>"+Math.round(this.a_(z,s)*R)/R+"</td>";
    } 
    ret=ret+"</tr>";
  }
  ret=ret+"</table><br>";
  return ret;
}