Math 448/548 - Example 3.2. Facility Location Problem (p.71-77)

Contents

clear all, clf
syms x y
r1 = sqrt((x-1)^2+(y-5)^2)^0.91;
r2 = sqrt((x-3)^2+(y-5)^2)^0.91;
r3 = sqrt((x-5)^2+(y-5)^2)^0.91;
r4 = sqrt((x-1)^2+(y-3)^2)^0.91;
r5 = sqrt((x-3)^2+(y-3)^2)^0.91;
r6 = sqrt((x-5)^2+(y-3)^2)^0.91;
r7 = sqrt((x-1)^2+(y-1)^2)^0.91;
r8 = sqrt((x-3)^2+(y-1)^2)^0.91;
r9 = sqrt((x-5)^2+(y-1)^2)^0.91;

z = 3.2+1.7*(6*r1+8*r2+8*r3+21*r4+6*r5+3*r6+18*r7+8*r8+6*r9)/84;
ezcontourf(z,[0 6 0 6])
colorbar, grid on
hold on

F = diff(z,x); G = diff(z,y);

DO NOT attempt to solve the system F=0,G=0 symbolically, it will take forever!

Random Search Method

a=0; b=6; c=0; d=6; % boundaries of the (x,y) domain
N=1000; % Number of points

x0 = a+(b-a)*rand(1);
y0 = c+(d-c)*rand(1);
zmin = subs(z,[x,y],[x0,y0]);

The Random Search Method picks at random (uniformly distributed) points in hte region {a,b}x[c,d] and records each time a lower value for z(x,y) has been found.

fprintf(' Iteration    z value\n\n');
for n=1:N
    xnew=a+(b-a)*rand(1);
    ynew=c+(d-c)*rand(1);
    znew=subs(z,[x,y],[xnew,ynew]);
    if znew<zmin
        xmin=xnew;
        ymin=ynew;
        zmin=znew;
        fprintf('%4.0f       %1.6f\n', n, zmin);
    end
end
 Iteration    z value

   2       7.186996
   4       6.989978
   8       6.565573
  17       6.528061
 108       6.487254
 157       6.479650
 200       6.473878
 290       6.463072

Optimization results

The optimal value obtained through this method will change significantly from run to run. The more random points are chosen, the more accurate the approximation.

The approximate optimal point is

[xmin,ymin]

% and the minimum value of the objective function is (approx)
zmin
ans =

    1.5970    2.7817


zmin =

    6.4631