How to solve linear programming problem with simplex algorithm

Question

I am solving the following problem of linear programming using the linprog function

%Objective Function
     %X1    X2    X3    X4    X5    X6    X7    X8    X9    X10   X11   X12   X13   X14   X15   X16   X17   X18
f = [0.669 0.654 0.503 0.683 0.670 0.673 0.749 0.655 0.660 0.583 1.243 0.639 2.024 2.156 1.672 0.473 0.139 0.687];

A = [];   b = [];   %Sin restricciones de desigualdad

%Restricciones de igualdad son:
     %X1  X2    X3   X4   X5   X6   X7   X8   X9   X10  X11   X12  X13  X14  X15  X16  X17  X18
Aeq=[0.1 0.12 0.335 0.15 0.18 0.19 0.12 0.15 0.15 0.15   0   0.15 0.11  0   0.13  0     0  0.46; %Nitrogeno
     0.3 0.24   0   0.03 0.05 0.04 0.27 0.03 0.24 0.15   0    0   0.52 0.52  0    0     0    0 ; %Fosforo
     0.1 0.12   0   0.31 0.15 0.19 0.08 0.2  0.12 0.15  0.50  0    0   0.34 0.44  0     0    0 ; %Potasio
      0    0    0    0    0    0    0    0    0    0     0   0.26  0    0    0    0    0.50  0 ; %Calcio
      0    0    0    0   0.06  0    0    0    0    0     0    0    0    0    0   0.17   0    0]; %Magnesio


beq = [285.71 ; %Demanda nutricional de Nitrogeno (kg/ha)
       305.33 ; %Demanda nutricional de Fosforo (kg/ha)
          450 ; %Demanda nutricional de Potasio (kg/ha)
       262.50 ; %Demanda nutricional de Calcio (kg/ha)
        41.50]; %Demanda nutricional de Magnesio (kg/ha)

%Limite inferior
lb = zeros(18,1);   
%Limite superior
ub = inf(18,1);        

x = linprog(f, A, b, Aeq, beq, lb, ub, options)

Solucion_optima = f*x

When I solve this is the result that throws me but does not show any results of the simplex table and I execute it with the following command

options = optimoptions('linprog','Algorithm','dual-simplex');

So I have the simplex algorithm

iterM=100;

In=size(Aeq,1);

Xsol=[Aeq eye(In) beq
    f zeros(1,In) 0];

for iter=1:1:iterM
    fin=Xsol(end,1:end-1)<0;
    if fin==0
        break
    end
[a,c]=min(Xsol(end,:));

Xre=Xsol(:,end)./Xsol(:,c);

i=Xre<=0;

d=Xre;
d(i)=inf;

[beq,f]=min(d);

Xsol(f,1:end)=Xsol(f,1:end)/Xsol(f,c);

for i=1:1:size(Xsol,1)

    if i~=f
        Xsol(i,:)=Xsol(i,:)-(Xsol(i,c)*Xsol(f,:));
    end
end

end

for i=1:1:size(f,2)
    d=logical(Xsol(:,i));
    X(i,1)=Xsol(d,end)
end

When I run the Xsol function it does not show me the optimal solution nor the other values that the simplex table should have

Are you seeking the final "simplex tableau" for the resulting solution (basic feasible solution)? It's unclear what you're asking for. Please edit the question to be clearer on what you're looking for. — SecretAgentMan
– SecretAgentMan, Commented Nov 8, 2018 at 22:02
This is the final table of the simplex for the resulting solution — John Doe
– John Doe, Commented Nov 8, 2018 at 22:31
If the simplex algorithm solves (problem is feasible and bounded), then it terminates at a basic feasible solution. I believe this solution (an extreme point) is provided by the output. When you say "final table", do you mean the "tableau" format? — SecretAgentMan
– SecretAgentMan, Commented Nov 8, 2018 at 22:34
The "tableau" can be obtained by taking inv(B)*A where B is the final basis (some of the columns of constraint matrix A). — SecretAgentMan
– SecretAgentMan, Commented Nov 8, 2018 at 22:35
If that's what I mean, you can create an answer with the solution — John Doe
– John Doe, Commented Nov 8, 2018 at 22:37

SecretAgentMan · Accepted Answer · 2018-11-08 23:03:56Z

2

Based on the OP stating, "I need the reduced costs, the dual solution and shadow prices."

1) The dual solution is the shadow prices. The shadow prices are the solution to the dual.

2) The final simplex tableau is not the only way to obtain the stated objectives (though it would work).

Dual Solution (Shadow prices)
You can obtain the dual solution via [x,fval,exitflag,output,lambda] = linprog(___). The lambda is the dual solution; see MATLAB's documentation and examples for linprog (link). The documentation calls these Lagrange multipliers.

Reduced Costs
The reduced costs are obtainable with or without the dual solution. If f is the coefficients of the objective function (costs), then the reduced costs = f'- p'*A when the LP is written in standard form A*x=b. If someone else knows a better way to get the reduced costs from the output, please post. I've tried to avoid the primal formula to spare pulling out the index of basic variables.

A clear reference on this:
Bertsimas, Dimistris, and Tsitsiklis, John N. 1997. Introduction to Linear Optimization, Athena Scientific & Dynamic Ideas, LLC, Belmont, MA. page 148

answered Nov 8, 2018 at 23:03

SecretAgentMan

2,8708 gold badges26 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

John Doe Over a year ago

In lambda it shows me the following lambda = struct with fields: lower: [18×1 double] upper: [18×1 double] eqlin: [5×1 double] ineqlin: []

SecretAgentMan Over a year ago

@SebastianSalazar , forgive me, I'm not understanding what you're asking. What's wrong?

SecretAgentMan Over a year ago

If this is for schoolwork and you're used to the standard form representation A*x=b, then solve with upper bounds = +inf and lower bounds = -inf and put the bounds into A instead (make sure to add slack variables to the problem if you're not going to let linprog do it for you) Then the output would be more familiar.

Collectives™ on Stack Overflow

How to solve linear programming problem with simplex algorithm

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related