对偶单纯形法

2013-2014（1）专业课程实践论文
对偶单纯形法
一、 算法理论

对偶单纯形法是解决线性规划问题的一种方法。
考虑线性规划：

123
23
123
1,2,3

min z=15245.. 62 521 0xxxstxxxxxxxx















引进剩余变量45,xx，将其化为标准形并列成表格为
0 6 1 -1 0 5 2 1 0 -1 2
1
15 24 5 0 0 0
为使中心部位具有单位子块，易想到把底线以上部分均变号，于是有
0 -6 -1 1 0 - 5 -2 -1 0 1 -2
-1
15 24 5 0 0 0
可见此表以具备特点1、3、4。
当一个线性规划问题具有特点1-中心部位具有单位子块，特点3-底行相
应于单位子块位置元素为0，特点4-底行其他元素非负等三个特点而同时又不
具有特点2-右行列元素非负特点，即满足特点1、3、4时可使用此方法求出
最优解。
此方法运用所允许的运算，始终不破坏第1、3、4三个特点，而逐步调出
第2个特点的办法，以解出最优解。
其具体的步骤为：
1. 从右列负元素中任选一个。如上例选-2；
2.
从所选行位于中心部位的负元素中确定一个，由于要保持第3、4的特
点不被破坏，理应取相应底行的元素与该负元素之比中最大者。如上例中由

24524
max,,616





所以选-6.
3. 进行旋转运算。如上例旋转以后得
0 1 1/6 -1/6 0 - 5 0 -2/3 -1/3 1 1/3
- 1/3
15 0 1 4 0 -8
如此往复直至第2个特点也被满足，并得到最优解。
该matlab程序可以解决在标准形下满足第1、3、4特点的线性规划问题。
二、算法框图
输入

是否达到最优解是否有最优解输出最优解
否

改写成标准
形式

进行旋转运
算

否
是
输出无可行

解

选择中心部
位负元素

是
三、算法程序
建立函数
function x=lindual(c,A,b)
[n1,n2]=size(A);
A=[-A,eye(n1)];c=[-c,zeros(1,n1)];
x1=[zeros(1,n2),b'];lk=[n2+1:n1+n2];
b=-b;
while(1)
x=x1(1:n2);
s1=[lk',b,A];
c;
x1;
cc=[];ci=[];
for i=1:n1
if b(i)<0
cc=[cc,b(i)];
ci=[ci,i];
end
end
nc=length(cc);
if nc==0
fprintf('达到最优解');
break
end
cliu=cc(1);
cl=ci(1);
for j=1:nc
if abs(cc(j))>abs(cliu)
cliu=cc(j);
cl=j;
end
end
cc1=[];ci1=[];
for i=1:n1+n2
if A(cl,i)<0
cc1=[cc1,A(cl,i)];
ci1=[ci1,i];
end
end
nc1=length(cc1);
if nc1==0
fprintf('无可行解');
break
end
cliu=c(ci1(1))/cc1(1);
cl1=ci1(1);
for j=1:nc1
if c(ci1(j))/cc1(j)cliu=c(ci1(j))/cc1(j);
cl1=ci1(j);
end
end
b(cl)=b(cl)/A(cl,cl1);
A(cl,:)=A(cl,:)/A(cl,cl1);
for k=1:n1
if k~=cl
b(k)=b(k)-b(cl)*A(k,cl1);
A(k,:)=A(k,:)-A(cl,:).*A(k,cl1);
end
end
c=c-c(cl1).*A(cl,:);
x1(lk(cl))=0;
lk(cl)=cl1;
for kk=1:n1
x1(lk(kk))=b(kk);
end
x=x1(1:n2);
end
四、算法实现
例1. 用对偶单纯形法解下列线性规划

123
23
123
1,2,3

min z=15245.. 62 5+21 0xxxstxxxxxxxx















解：利用matlab数学软件的解答方法为：
（1）输入题中已知条件：
>>c=[15 24 5];A=[0 6 1;5 2 1];b=[2;1];
（2）调用函数求出最优解：
>>x=lindual(c,A,b)
（3）求最优值：
>>z=c*x’
运行结果如下：

例2. 用对偶单纯形法解下列线性规划

12
12
12
1,2

min z=.. 24 +77 0xxstxxxxxx















解：利用matlab数学软件的解答方法为：
（1）输入题中已知条件：
>> c=[1 1];A=[2 1;1 7];b=[4;7];
（2）调用函数求出最优解：
>>x=lindual(c,A,b)
（3）求最优值：
>>z=c*x’
运行结果如下：

例3. 用对偶单纯形法解下列线性规划
12341234123412341,2,3,4min z=324.. 2450 3722 52615 0xxxxstxxxxxxxxxxxxxxxx
解：利用matlab数学软件的解答方法为：
（1）输入题中已知条件：
>> c=[3 2 1 4];A=[2 4 5 1;3 -1 7 -2;5 2 1 6];b=[0;2;15];
（2）调用函数求出最优解：
>>x=lindual(c,A,b)
（3）求最优值：
>>z=c*x’
运行结果如下：
例4. 用对偶单纯形法解下列线性规划
1234123412341341,2,3,4min z=-235.. 246 2312 4 0xxxxstxxxxxxxxxxxxxxx
解：利用matlab数学软件的解答方法为：
（1）输入题中已知条件：
>> c=[-2 -1 3 -5];A=[-1 -2 -4 1;-2 -3 1 -1;-1 0 -1 -1];b=[6;12;4];
（2）调用函数求出最优解：
>>x=lindual(c,A,b)
（3）求最优值：
>>z=c*x’
运行结果如下：