Algorithm in Primal Dual Simplex
Procedure Simplex_Primal_Dual(A,b,c,x,unbounded,y)
{A:input matrix // b:known term vector}
{c: cost vector // x: feasible solution}
{y: optimal solution of D}
//////////
begin
optimal:=false; unbounded:=false;
I:={i: Aix=bi};
{Select the active constraints}
if I==None then grow_along(c,x,I,unbounded);
while not optimal or not unbounded do
begin
{g means yita and e means yipxilun}
if {gAI=c} has no solution then
begin compute e<: AIe=0, ce=1; grow_along(e,x,I,unbounded); end;
else if {gAI=c} has a solution and exists h: gh<0 then
begin compute e: AIe=uh; grow_along(e,x,I,unbounded); end;
else optimal:=true;
{the dual system has a solution: gAI=c, g>=0}
end;
end.
近期评论