如何用单纯形算法解决线性规划问题
How to solve linear programming problem with simplex algorithm
我正在使用 linprog 函数解决以下线性规划问题
%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
当我解决这个问题时,结果抛出但没有显示单纯形的任何结果 table 我用以下命令执行它
options = optimoptions('linprog','Algorithm','dual-simplex');
所以我有了单纯形算法
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
当我 运行 Xsol 函数时,它没有显示最优解,也没有显示单纯形 table 应该具有的其他值
根据 OP 说明,"I need the reduced costs, the dual solution and shadow prices."
1) 双重解决方案是影子价格。影子价格是对偶的解。
2) 最终的单纯形画面并不是获得所述 objectives 的唯一方法(尽管它会起作用)。
双重解决方案(影子价格)
您可以通过[x,fval,exitflag,output,lambda] = linprog(___)
获得对偶解。 lambda
是对偶解;请参阅 linprog
(link) 的 MATLAB 文档和示例。文档将这些称为拉格朗日乘数。
降低成本
使用或不使用双重解决方案都可以获得降低的成本。如果 f
是 objective 函数(成本)的系数,则当 LP 写成标准形式 A*x=b
时,降低的成本 = f'- p'*A
。如果其他人知道从输出中获得降低成本的更好方法,请post。我试图避免使用原始公式来省去基本变量的索引。
关于此的明确参考:
Bertsimas、Dimistris 和 Tsitsiklis,John N. 1997。线性优化简介,Athena Scientific & Dynamic Ideas, LLC,马萨诸塞州贝尔蒙特。第 148 页
我正在使用 linprog 函数解决以下线性规划问题
%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
当我解决这个问题时,结果抛出但没有显示单纯形的任何结果 table 我用以下命令执行它
options = optimoptions('linprog','Algorithm','dual-simplex');
所以我有了单纯形算法
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
当我 运行 Xsol 函数时,它没有显示最优解,也没有显示单纯形 table 应该具有的其他值
根据 OP 说明,"I need the reduced costs, the dual solution and shadow prices."
1) 双重解决方案是影子价格。影子价格是对偶的解。
2) 最终的单纯形画面并不是获得所述 objectives 的唯一方法(尽管它会起作用)。
双重解决方案(影子价格)
您可以通过[x,fval,exitflag,output,lambda] = linprog(___)
获得对偶解。 lambda
是对偶解;请参阅 linprog
(link) 的 MATLAB 文档和示例。文档将这些称为拉格朗日乘数。
降低成本
使用或不使用双重解决方案都可以获得降低的成本。如果 f
是 objective 函数(成本)的系数,则当 LP 写成标准形式 A*x=b
时,降低的成本 = f'- p'*A
。如果其他人知道从输出中获得降低成本的更好方法,请post。我试图避免使用原始公式来省去基本变量的索引。
关于此的明确参考:
Bertsimas、Dimistris 和 Tsitsiklis,John N. 1997。线性优化简介,Athena Scientific & Dynamic Ideas, LLC,马萨诸塞州贝尔蒙特。第 148 页