by W.Lindner LindnerW@t-online.de We solve the example of J. Chinneck (chapter4.pdf) using EULER. URL: http://www.sce.carleton.ca/faculty/chinneck/po.html The LP is: Maximize Z = 15x1 + 10x2 subject to x1>=0 x2>=0 x1<=2 x2<=3 x1+x2<=4 In Matrixnotation: x y s1 s2 s3 b 1 0 1 0 0 2 0 1 0 1 0 3 1 1 0 0 1 4 -15 -10 The situation is:
>loadimg("Lp-Bild1");
>load "MRT.e"; >A=[1,0,1,0,0,2;0,1,0,1,0,3;1,1,0,0,1,4;-15,-10,0,0,0,0]
Column 1 to 3: 1 0 1 0 1 0 1 1 0 -15 -10 0 Column 4 to 6: 0 0 2 1 0 3 0 1 4 0 0 0
The (last) row of the objective function has his smallest value -15 in column 1. So we choose column A[,1] as our pivotCOLUMN. To choose the corresponding ROW we make the MinimalRatioTest (MRT):
>MRT1(A,1) // MRT by inspecting with the eyes
Quotients : 2.00 no limit 4.00
>MRT (A,1) // we control our pivot positions
Quotients : 2 4 Take : i=1 j=1
The MinimalRatioTest MRT b/pivotcolumn[1] has his smallest value in row 1. So we pivotizise at position (1,1). Calculate A[k]:=A[k]-A[k,1]/A[1,1]*A[1] for k=2,3,4 (without 1):
>A1=pivotize(A,1,1)
Column 1 to 3: 1 0 1 0 1 0 0 1 -1 0 -10 15 Column 4 to 6: 0 0 2 1 0 3 0 1 2 0 0 30
We see: (x1,x2,s1,s2,s3)=(2,0,0,3,2) with z=30. The objective functin row has his smallest value -10 in column 2. So we choose column A[,2] as new pivotCOLUMN.
>MRT1(A1,2) // choose pivot row for yourself
Quotients : no limit 3.00 2.00
>MRT (A1,2) // test your choise
Quotients : 3 2 Take : i=3 j=2
The MinimalRatioTest MRT b/pivotColumn[2] has his smallest value in row 3. So we pivotizise at position (3,2). We calculate A[k]:=A[k]-A[k,2]/A[3,2]*A[2] for k=1,2,4 (without 3):
>A2=pivotize(A1,3,2)
Column 1 to 3: 1 0 1 0 0 1 0 1 -1 0 0 5 Column 4 to 6: 0 0 2 1 -1 1 0 1 2 0 10 50
We see: (x1,x2,s1,s2,s3)=(2,2,0,1,0) with z=50. The row of the objective function has no negative entry: STOP! We get the solution: x1=2, x2=2 and z=50. The situation now is:
>loadimg("Lp-Bild2.png");
Now we have a procedural understanding of the simplex method. We get a conceptual understanding by studying the text of John Chinneck. We control our result with the numeric tool EULER :
>shortformat; >A=[1,0,1,0,0;0,1,0,1,0;1,1,0,0,1]
1 0 1 0 0 0 1 0 1 0 1 1 0 0 1
>b=[2;3;4]
2 3 4
>c=[15,10,0,0,0]
[ 15 10 0 0 0 ]
>{x,r,i}=simplex(A,b,c, max=1); r,
0
>x // solution
2 2 0 0 0
>c.x // check
[ 50 ]
We control our result with the symbolic CAS Maxima:
>:: load("simplex"); >:: A := matrix([1,0,1,0,0],[0,1,0,1,0],[1,1,0,0,1])
[ 1 0 1 0 0 ] [ ] [ 0 1 0 1 0 ] [ ] [ 1 1 0 0 1 ]
>:: b:=[2,3,4]
[2, 3, 4]
>:: c:=[-15,-10,0,0,0]
[- 15, - 10, 0, 0, 0]
>:: linear_program(A, b, c)
[[2, 2, 0, 1, 0], - 50]
.. or:
>:: maximize_lp(15*x1 + 10*x2, [ x1>=0, x2>=0, x1<=2, x2<=3, x1+x2<=4])
[50, [x2 = 2, x1 = 2]]
-------------------------------------------- Exercise: Solve the following LP via the example above. . What is the term of the objective function? . Formulate the LP as A*X=B with constrains. --------------------------------------------
>fracformat(10); >LP:=[-1, 1, 1, 1, 0, 0; ... > 1, -2, 1, 0, 1, 0; ... > 1, 1, 0, 0, 0, 1; ... > 0, 0, -1, 0, 0, 0]
-1 1 1 1 0 0 1 -2 1 0 1 0 1 1 0 0 0 1 0 0 -1 0 0 0