Revised Simplex Method Solution

Hello,

I'm trying to run a quick solver to find a solution to the following problem:

Maximise: z = 7x1 + 2x2 + 3x3 + x4 + x5 + x6

Subject to constraints: 2x1 + 7x2 + x3 + x6 = 30

5x1 + 8x2 + 2x4 <=20

x1 + x2 + x6 =>12

x1 + x3 + x5 + x6 <= 41

I currently have:

A = [2 7 1 0 0 1,

5 8 0 2 0 0,

1 1 0 0 0 1,

1 1 0 0 0 1]

b = [30 20 12 41]

f = [7 2 3 1 1 1]

I've been trying to use the function

linprog(f,A,b,.....

But am struggling to work out how to input the inequalities into the linprog.

Any advice?

Thanks!

Answer 1

[John D'Errico]

I would say to read the docs for linprog, where this will have been explained in some depth. But perhaps it may be confusing still.

From the help for linprog, we see:

 X = linprog(f,A,b) attempts to solve the linear programming problem:
 
             min f'*x    subject to:   A*x <= b
              x
 
    X = linprog(f,A,b,Aeq,beq) solves the problem above while additionally
    satisfying the equality constraints Aeq*x = beq. (Set A=[] and B=[] if
    no inequalities exist.)

You wrote A and b as:

A = [2 7 1 0 0 1,
        5 8 0 2 0 0,
        1 1 0 0 0 1,
        1 1 0 0 0 1]
b = [30 20 12 41]

So you made a good start. (The only reason I am answering your question.)

You actually have both EQUALITY and INEQUALITY constraints to supply here. And worse? They varied the direction of the inequalities. How nasty of them.

So, you have ONE equality constraint. Therefore Aeq and beq will have ONE row. Create those matrices separately.

As far as the inequalities go, you were given:

5x1 + 8x2 + 2x4 <=20

x1 + x2 + x6 =>12

x1 + x3 + x5 + x6 <= 41

But is that what you want? Or, do you need to have all the inequalities as <= inequalities? So multiply by -1 for the middle one. What does that do?

5x1 + 8x2 + 2x4 <= 20

-x1 + -x2 + -x6 <= -12

x1 + x3 + x5 + x6 <= 41

That second inequality will now have -1s in there.

I have confidence you can do the rest now.