# stuck on matlab simplex method

• Jan 7th 2011, 11:51 AM
matlabnoob
stuck on matlab simplex method
hi all,

can anyone help me with this?ive been stuck for days!(Crying)

im using the matlab code:

%
options=optimset('LargeScale','off','Simplex','on' );
%
% This code solves the problem:
%
% minimise x_1+x_2+x_3
%
% subject to the constraints
%
% b_11 x_1 + b_12 x_2 + b_13 x_3 >= 1
% b_21 x_1 + b_22 x_2 + b_23 x_3 >= 1
% b_31 x_1 + b_32 x_2 + b_33 x_3 >= 1
% x_1 >=0, x_2 >=0, x_3 >=0
%

%
B=[ 1 -6 -7;
-1 6 6;
7 -6 0];
A=-B;
f=[1;1;1];
b=-[1;1;1];
lb=zeros(3,1); % x_1, x_2 and x_3 are non-negative.
%
[x,value]=linprog(f,A,b,[],[],lb)

to solve for (see attached file)

my results are (when i run simplex_method.m):
x1 = 0
x2 = 0
x3 = 1/3

obviously this does not make any sense?? as x1 + x2 + x3 = 1

what am i doing wrong?? : (

P.S. im trying to minimise the problem in the second pic
• Jan 7th 2011, 12:39 PM
snowtea
If you want the condition x1 + x2 + x3 = 1, then you need:

[x,value]=linprog(f,A,b,[1 1 1],[1],lb)
• Jan 7th 2011, 12:52 PM
matlabnoob
Quote:

Originally Posted by snowtea
If you want the condition x1 + x2 + x3 = 1, then you need:

[x,value]=linprog(f,A,b,[1 1 1],[1],lb)

i did that and now i got:

x =
1.4667
1.5134
0.0008

value = 2.9809

andi got a message saying:
exiting: one or more of the residuals, duality gap or total relative error has grown 10000 times greater than its minimum value so far: the primal appears to be infeasible (and the dual ubnounded)
• Jan 7th 2011, 12:57 PM
snowtea
It is exactly what the message says. The minimum must be unbounded in the region you defined by A and b.
• Jan 7th 2011, 01:01 PM
matlabnoob
Quote:

Originally Posted by snowtea
It is exactly what the message says. The minimum must be unbounded in the region you defined by A and b.

i do not quite get what you mean? *thinks*
im not sure what matlab itself means when it says that...

all my inputs seem to be correct? and the code
• Jan 7th 2011, 01:06 PM
snowtea
There must be no minimum in the region either because the region is empty, or the region does not have a lower bound for x1+x2+x3.

Actually, I thought you wanted x1+x2+x3=1 as a constraint, but now that I think about it , this does not make sense as you want to minimize x1+x2+x3.

How do you know that the minimum is x1+x2+x3=1?
Isn't 0+0+1/3 = 1/3 less than that?
• Jan 7th 2011, 01:09 PM
matlabnoob
Quote:

Originally Posted by snowtea
There must be no minimum in the region either because the region is empty, or the region does not have a lower bound for x1+x2+x3.

Actually, I thought you wanted x1+x2+x3=1 as a constraint, but now that I think about it , this does not make sense as you want to minimize x1+x2+x3.

How do you know that the minimum is x1+x2+x3=1?
Isn't 0+0+1/3 = 1/3 less than that?

ah i see. i know that x1+x2+x3=1 because in the problem x1, x2 & x3 are all the probabilities and they sum up to 1
which is why am confused to why the code is failing..
• Jan 7th 2011, 01:12 PM
snowtea
Well, you need to figure out exactly what you are minimizing.

The code you wrote uses linear programming to minimize x1+x2+x3. This clearly is not the answer you need, since you already know x1+x2+x3 = 1.

What exactly are you trying to minimize?
• Jan 7th 2011, 01:19 PM
matlabnoob
im trying to minimise (please see my second attached file in my first post on this page). not sure how to attach files in replies..
• Jan 7th 2011, 01:31 PM
snowtea
So you are trying to minimize -w?
How do you transform this into linear programming with x1,x2,x3?

Well look at the value of x1 + x2 + x3 + (-w) = 1 + (-w), and minimize this.

So now you should have a 4 variable vector (x1,x2,x3,-w).
Also, remember to express the constraint x1+x2+x3=1 (which is the same as 1*x1+1*x2+1*x3+0*(-w) = 1)