运筹学对偶单纯形法

关于运筹学对偶单纯形法第1页，课件共14页，创作于2023年2月方法：设原问题maxz=CXAX=bX≥0

设B是一个基，令B=(P1,P2,…,Pm)，它对应的变量为

XB=(

x1,x2,…,xm)

当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i<0,并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是1、对应基变量x1，x2，…

，xm的检验数是

σi=ci–zi=ci-CBB-1Pi=0，i=1,2,…,m2、对应非基变量xm+1，…

，xn的检验数是

σj=cj–zj=cj-CBB-1Pj

0，j=m+1,…,n第2页，课件共14页，创作于2023年2月每次迭代时，将基变量中的负分量xl取出（换出变量）,去替换非基变量中的xk，要求在所有检验数仍保持非正（对偶问题可行性）的前提下，进行基变换。从原问题来看，经过每次迭代,原问题由非可行解往可行解更靠近，当原问题得到可行解时，便得到了最优解（原问题、对偶问题）。注意：1.对偶单纯形法不是解对偶问题的单纯形法，而是应用对偶原理求解原问题最优解的一种方法。当然，当求解得到原问题的最优解的同时，也就得到对偶问题的最优解。2.在具体计算中，不另外构造单纯形表格，而是在原始问题的单纯形表格基础上进行对偶处理。第3页，课件共14页，创作于2023年2月对偶单纯形法的计算步骤:(1)根据线性规划问题，列出初始单纯形表，检查b列的数值，若都为非负，并且检验数都为非正，则已得到最优解。停止计算；若b列的数值至少还有一个负分量，检验数保持非正，那么进行计算。(3)

确定换入变量：检查xl所在行的各系数alj(j=1,2,…,n)。若所有的alj0,则无可行解，停止计算。(2)先确定换出变量：若

min{(B-1b)i|(B-1b)i<0}=(B-1b)l对应的基变量xl为换出变量。（实际上，可取任何一个取负值的基变量作为换出变量。取最小的含义是尽快）第4页，课件共14页，创作于2023年2月若存在alj<0,(j=1,2,…,n)，计算按θ规则所对应的非基变量xk为换入变量(保持对偶问题解的可行性)。(4)以alk为主元素，进行迭代，即进行矩阵行变换。得新的单纯形表。重复（1）-（4）步，直到求出最优解为止。为什么要用下式来确定换入变量呢？原因如下：第5页，课件共14页，创作于2023年2月第6页，课件共14页，创作于2023年2月第l行变成：行变换将Pk变成单位向量，因为bl<0，一定要求bl/alk0,要选主元素alk<0。检验数变成（行变换）要保证可行性，就要有jnew0，j=1,…,n),,1,,,0,,0,1,...

0,,0,(ln1lklklmlklklaaaaaabLLLL+),,0,,,0,,0,,0,,0(ln11klknklklmmlkkaaaaasssss---++LLLL第7页，课件共14页，创作于2023年2月令T={j|alj<0}

当jT时，alj0，从而jnew=j-alj/alkk<0，满足可行性。当jT时，jnew=j-alj/alkk=alj[j

/alj-k

/alk]

由于j，k，

alk，alj均小于0，从而上述括号内的比值均大于0。又由于alj<0，为保证jnew0，（jT）故只要选取就能有方括号内大于等于0，从而jnew0。第8页，课件共14页，创作于2023年2月

解:先将这问题转化（此时b可以是负的）,以便得到对偶问题的初始可行基

maxz=-2x1-3x2-4x3

-x1-2x2-x3+x4

=-3-2x1+x2-3x3+x5

=-4xj≥0,j=1,2,3,4,5

建立这个问题的初始单纯形表例：用对偶单纯形法求解：

minω=2x1+3x2+4x3

x1+2x2+x3

≥32x1-x2+3x3

≥4

x1,x2,x3

≥0第9页，课件共14页，创作于2023年2月第10页，课件共14页，创作于2023年2月第11页，课件共14页，创作于2023年2月则

X*=（11/5，2/5，0，0，0）T为原问题的最优解。同时Y*=（y1*，y2*）=（8/5，1/5）第12页，课件共14页，创作于2023年2月对偶单纯形法特点:(1)

简化计算：不引入人工变量将线性规划化成标准型,构造初始单纯形表(初始解是非可行解),只要检验数非负(最优检验数),就可以进行基的转换；(2)

适于变量多