taralino

.minimize

Die Funktion LinearProgramming.minimize(c, A, b) erwartet folgende (verpflichtende) Argumente:

Argument	Datentyp	Hinweis
c	Datenfeld	Vektor zur Definition der Kosten (Kostenvektor)
A	Datenfeld	Matrix zur Definition der Nebenbedingungen
b	Datenfeld	Vektor zur Definition der Nebenbedingungen

Es wird das lineare Programm

mit dem Simplex-Verfahren gelöst. Falls das lineare Programm keine (beschränkte) Optimallösung besitzt, wird eine entsprechende Zeichenkette zurückgegeben. Anderenfalls wird ein Objekt bestehend aus folgenden Variablen zurückgegeben:

Variable	Datentyp	Hinweis
x	Datenfeld	Optimallösung
value	Zahl	Zielfunktionswert der Optimallösung
iterations	Datenfeld	Anzahl der Iterationen

Die Anzahl der Iterationen wird als Vektor mit zwei Einträgen zurückgegeben, nämlich die Anzahl der benötigten Iterationen für Phase 1 sowie die Anzahl der benötigten Iterationen für Phase 2 des Simplex-Verfahrens.

Optionen der Funktion

Es können folgende Optionen verwendet werden:

Variable	Datentyp	Hinweis	Default-Wert
signs	Datenfeld	Vektor	(1,1,...,1)
constraints	Datenfeld	Vektor	(0,0,...,0)
method	Zeichenkette	-	steepest_edge
accuracy	Zahl	positiv	0.000001

Der Vektor signs muss die gleiche Länge haben wie der Kostenvektor c. Definiert werden dadurch die Vorzeichen der Variablen mit folgender Bedeutung:

Eintrag	Wert	Bedeutung
j-ter Eintrag	1	j-te Variable ist stets größer oder gleich 0 (Standard)
j-ter Eintrag	-1	j-te Variable ist stets kleiner oder gleich 0
j-ter Eintrag	0	j-te Variable ist im Vorzeichen unbeschränkt

Der Vektor constraints muss die gleiche Länge haben wie der Vektor b. Definiert wird dadurch, ob es sich bei den Nebenbedingungen jeweils um eine Gleichung oder eine Ungleichung handelt:

Eintrag	Wert	Bedeutung
i-ter Eintrag	0	i-te Nebenbedingung ist eine Gleichung (Standard)
i-ter Eintrag	1	i-te Nebenbedingung ist eine Ungleichung mit Größer-Gleich
i-ter Eintrag	-1	i-te Nebenbedingung ist eine Ungleichung mit Kleiner-Gleich

Mittels method kann definiert werden, welche Pivotregel beim Simplex-Verfahren zum Einsatz kommt. Dabei stehen folgende Möglichkeiten zur Auswahl:

steepest_edge	Größtmögliche Verbesserung des Zielfunktionswertes in jedem Schritt (Standard)
first_index	Es werden jeweils die Indize mit den kleinsten Werten verwendet
smallest_value	Es werden jeweils die Indize gewählt, welche zu den kleinsten negativen Kosten gehören
random	Aus der Menge aller möglichen Indize werden rein zufällige Indize gewählt
bland	Es wird Blands Pivotregel verwendet

Bei der Anwendung numerischer Verfahren zur Lösung von linearen Programmen sind numerische Ungenauigkeiten zu erwarten, sodass jedes lineare Programm nur bis zu einer gewissen Genauigkeit gelöst werden kann. Die Option accuracy definiert daher die gewünschte Genauigkeit, die bei sämtlichen Vergleichen während des Simplex-Verfahrens verwendet wird.

Beispiel

Das folgende Beispiel löst ein lineares Programm in Standardform und gibt die Optimallösung sowie den zugehörigen Zielfunktionswert aus.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>

// Eingabedaten
var c = [ 3, -5, 0, 2, 1 ];
var A = [
  [  5, -2,  3, -4,  1 ],
  [  0,  1,  0,  1,  0 ],
  [ -2,  5, -3,  1, -1 ]
];
var b = [ -6, 9, -3 ];

// Lineares Programm loesen
var S = LinearProgramming.minimize(c, A, b);

// Ausgabe
Console.print("Optimalloesung:");
Console.print(S.x);
Console.print("Zielfunktionswert:");
Console.print(S.value);

</script>
</body>
</html>

Vorschau Download Kopie speichern

Beispiel

Das folgende Beispiel löst ein Beispiel bestehend aus 32 Variablen und 27 Nebenbedingungen. Zu beachten ist, dass einige der Nebenbedingungen als Ungleichungen formuliert sind. Daher ist die Option constraints zwingend erforderlich.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>

// Eingabedaten
var D = LinearProgramming.example();
var c = D.c;
var A = D.A;
var b = D.b;
var z = D.z;
var s = D.s;

// Lineares Programm loesen
var S = LinearProgramming.minimize(c, A, b, {signs:z, constraints:s, method:"random"});

// Ausgabe
Console.print("Optimalloesung:");
Console.print(S.x);
Console.print("Zielfunktionswert:");
Console.print(S.value);
Console.print("Iterationen:");
Console.print(S.iterations);
Console.print("Vektor zur Definition der Nebenbedingungen:");
Console.print(s);

</script>
</body>
</html>

Vorschau Download Kopie speichern