taramath: Das bikriterielle Weber-Problem

Beschreibung

Gegeben seien durch existierende Standorte in der Ebene mit zugehörigen (positiven) Gewichten bzw. . Das bikriterielle Weber-Problem besteht darin, die Menge aller effizienten Lösungen des multikriteriellen Optimierungsproblems unter Berücksichtigung der beiden Zielfunktionen

zu bestimmen.

Im folgenden Beispiel lösen wir dieses Problem unter Verwendung eines numerischen Verfahrens, welches die Menge der effizienten Lösungen durch eine diskrete Punktmenge approximieren kann, falls es sich (wie in diesem Beispiel) bei um eine (differenzierbare) Kurve in der Ebene handelt.

Beispiel

Im folgenden Beispiel wird die Menge der effizienten Lösungen eines bikriteriellen Weber-Problems numerisch bestimmt. Dazu werden zunächst die Eingabedaten soie die Zielfunktionen definiert. Anschließend kommt eine Art Euler-Verfahren zum Einsatz, welche die Menge aller effizienten Lösungen approximiert. Schließlich wird das Ergebnis samt Eingabedaten graphisch dargestellt.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot"></div>
<script>

// Eingabedaten des bikriteriellen Weber-Problems: Standorte A sowie Gewichte w und v
var A = [[7,2],[3,5],[12,6],[9,15],[22,16],[17,18],[5,20]];
var w = [3,1,15,5,23,14,11];
var v = [12,13,9,1,3,2,1];

// Schrittweite zur numerischen Ableitung
var h = 1e-6;

// Schrittweite zur Anwendung des Euler-Verfahrens
var q = 0.1;

// Euklidischer Abstand zwischen zwei Punkten a und b
function distance (a, b) {
  return Math.sqrt((b[0]-a[0])*(b[0]-a[0]) + (b[1]-a[1])*(b[1]-a[1]));
};

// Zielfunktion f1
function f1 (x) {
  var s = 0;
  for (var k = 0; k < A.length; k++) s += w[k] * distance(x, A[k]);
  return s;
};

// Zielfunktion f2
function f2 (x) {
  var s = 0;
  for (var k = 0; k < A.length; k++) s += v[k] * distance(x, A[k]);
  return s;
};

// Gradient der Zielfunktion f1 (numerisch bestimmt)
function df1 (x) {
  return [(f1([x[0]+h,x[1]])-f1([x[0]-h,x[1]]))/(2*h), (f1([x[0],x[1]+h])-f1([x[0],x[1]-h]))/(2*h)];
};

// Gradient der Zielfunktion f2 (numerisch bestimmt)
function df2 (x) {
  return [(f2([x[0]+h,x[1]])-f2([x[0]-h,x[1]]))/(2*h), (f2([x[0],x[1]+h])-f2([x[0],x[1]-h]))/(2*h)];
};

// Hilfsfunktion g
function g (x) {
  var d1 = df1(x);
  var d2 = df2(x);
  return d1[0]*d2[1] - d1[1]*d2[0];
};

// Gradient der Hilfsfunktion g (numerisch bestimmt)
function dg (x) {
  return [(g([x[0]+h,x[1]])-g([x[0]-h,x[1]]))/(2*h), (g([x[0],x[1]+h])-g([x[0],x[1]-h]))/(2*h)];
};

// Funktion F zur Anwendung des Euler-Verfahrens
function F (x) {
  var z = dg(x);
  var s = Math.sqrt(z[0]*z[0]+z[1]*z[1]);
  return [z[1]/s, -z[0]/s];
};

// Bestimmung der Optimalloesungen der einzelnen Zielfunktion
var xopt_f1 = NonlinearProgramming.minimize(f1, [0,0])[0];
var xopt_f2 = NonlinearProgramming.minimize(f2, [0,0])[0];

// Anwendung des Euler-Verfahrens zur Schrittweite q
var XE = [];
var z = xopt_f1;
XE.push([z[0],z[1]]);
while ((distance(z, xopt_f2) > q) && (XE.length < 1e5)) {
  var u = F(z);
  z = [z[0]+q*u[0], z[1]+q*u[1]];
  XE.push([z[0],z[1]]);
};

// Darstellung der Standorte A sowie der Menge der effizienten Loesungen
Plot.init("plot", 320, 320);
Plot.options("grid_off", "frame_off");
Plot.range_x(0,24);
Plot.range_y(0,24);
Plot.options("dots");
Plot.add_list(A);
Plot.options("line");
Plot.add_list(XE);
Plot.draw();

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

Vorschau aktualisieren