taramath: Klassisches Transportproblem

Beispiel

Im folgenden Beispiel lösen wir das klassische Transportproblem unter Verwendung von Angebotsorten und Nachfrageorten. Alle weiteren Eingabedaten werden zufällig generiert, wobei die Transportkosten unter Verwendung der Euklidischen Norm definiert werden. Anschließend wird das Problem als lineares Programm formuliert und gelöst, bevor das Ergebnis dargestellt wird.

<!DOCTYPE html>
<html>

<head>
  <script src="taramath.js"></script>
</head>

<body>

<div id="plot"></div>

<script>

  var r = 3; // Anzahl Angebotsorte
  var s = 24; // Anzahl Nachfrageorte

  var n = r*s;
  var m = r+s;

  function distance (A, B) {
    return Math.sqrt((A[0]-B[0])*(A[0]-B[0]) + (A[1]-B[1])*(A[1]-B[1]));
  };

  // Festlegung Angebotsorte
  var G = [];
  var u = [];
  for (var i = 0; i < r; i++) G.push([10+Math.floor(80*Math.random()), 10+Math.floor(80*Math.random())]);
  for (var i = 0; i < r; i++) u.push(0);

  // Festlegung Nachfrageorte
  var H = [];
  var w = [];
  for (var j = 0; j < s; j++) H.push([Math.floor(100*Math.random()), Math.floor(100*Math.random())]);
  for (var j = 0; j < s; j++) w.push(Math.floor(100*Math.random())+1);

  // Warenverfuegbarkeit Angebotsorte
  var h = 0;
  for (var j = 0; j < s; j++) h += w[j];
  for (var k = 0; k < h; k++) u[Math.floor(r*Math.random())]++;

  // Definition Transportkosten
  var c = new Array(n);
  for (var i = 0; i < r; i++) for (var j = 0; j < s; j++) c[i*s+j] = distance(G[i], H[j]);

  // Aufstellen Vektor b
  var b = new Array(m);
  for (var j = 0; j < s; j++) b[j] = w[j];
  for (var i = 0; i < r; i++) b[s+i] = u[i];

  // Aufstellen Matrix A
  var A = new Array(m);
  for (var i = 0; i < m; i++) A[i] = new Array(n);
  for (var i = 0; i < m; i++) for (var j = 0; j < n; j++) A[i][j] = 0;
  for (var j = 0; j < s; j++) for (var i = 0; i < r; i++) A[j][i*s+j] = 1;
  for (var i = 0; i < r; i++) for (var j = 0; j < s; j++) A[s+i][i*s+j] = 1;

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

  // Loesung darstellen
  var x = S[0];
  Svg.init("plot", 320, 320);
  Svg.resize(-5, 105, -5, 105);
  Svg.clear("#f0f0f0");
  for (var k = 0; k < n; k++) if (x[k] > 0) {
    var ig = Math.floor(k/s);
    var ih = k % s;
    Svg.line(G[ig][0], G[ig][1], H[ih][0], H[ih][1], "#999999");
  };
  for (var i = 0; i < r; i++) Svg.disc(G[i][0], G[i][1], 2, "#ff0000");
  for (var i = 0; i < s; i++) Svg.disc(H[i][0], H[i][1], 1, "#0000ff");
  Svg.draw();

</script>

</body>
</html>

Vorschau aktualisieren

Klassisches Transportproblem

formuliert als lineares Programm