对偶单纯形法

2024年3月4日发(作者：收发文)

1.对偶问题模型

2.对偶例子，总结特点

3.对偶的相关性质定理

4.对偶单纯形法

1. 对偶问题模型

例：某化工厂利用R1、R2、R3 三种原料，生产Q1、Q2两种产品，生产每公斤产品所需的各单位原料、工厂所拥有的个资源最大量及每公斤产品销售利润如下表所示，问每天应生产多少公斤Q1、Q2才能使利润最大。

原料-产品-利润表

产品

资源

R1原料（公斤）

R2原料（公斤）

R3原料（公斤）

利润（万元/公斤）

生产每公斤产品Q1

3.0

4.0

9.0

0.7

生产每公斤产品Q2

10.0

5.0

4.0

1.2

每天原料的最大

用量（公斤）

300

200

360

设每天生产Q1、Q2的产品量为x1，x2，可得到约束方程

Max s=0.7 x1 +1.2 x2

3x1 + 10x2300

4x1 + 5x2200

9x1 + 4x2360

x10, x20

现在的问题是，如果另一个化工厂想全部购买该厂R1、R2、R3 三种原料，那么该厂在什么条件下出售这三种原料，才能使该厂在经济收入上不低于用等量的三种原料生产Q1、Q2产品获得的最大利润。

设三种原料出售单价分别为u1, u2, u3, 可得到约束方程

Min W= 300 u1

+200

u2 +360 u3

3 u1

+4

u2 +9 u3

 0.7

10 u1

+5 u2 +9u3

 1.2

u10, u20, u30

一半钱这问题成为L，后者为其对偶问题成为D

比较两个线性规划模型，其特征有

 目标函数的要求上两者相反，s求max，w求min

 右端向量和目标函数的价值系数两者对调

 约束方程两者符号相反，s是“”，w是“”

 由s的约束方程书引入了同等数量的另一组非负变量u=( u1, u2, u3)T,且作为w的决策变量，约束方程数由m个变为n个

2. 对偶问题及其转化方

对偶问题在理论和实践方面有着广泛的应用

 在某些情况下线性规划的对偶问题比原解问题更容易

1

 对偶变量对原问题的解提供了重要的经济意义

 在处理一般型初始模型时可以不引入人工变量而采用对偶单纯形法直接处理，减少计算量

 推证出若干重要性质和定理

 作为线性规划灵敏度分析的重要工具

例：求下列线性规划的对偶问题：

Max s= x1 +2 x2

s.t. x1 -2x22

x1

9

-x1 + x25

x10, x20

解：其对偶问题为：min w=2y1+9y2+5y3

s.t. y1+y2-y31

-2y2+y32

y10, y20, y30

需要注意的是，如果原问题的目标函数为求极小，其目标函数的系数需要乘-1变成求极大，如果某些约束为“”，则这些约束需乘-1，变成“”，才能产生相应的对偶问题。

例：求下列线性规划的对偶问题：

Min s= -4x1 +18 x2-10x3

s.t. x1 +x2-x32

-2x1+ x31

x10, x20, x30

解：化为标准问题：

Max s= 4x1 -18 x2+10x3

s.t. -x1 -x2+x3-2

-2x1+ x31

x10, x20, x30

对偶问题为：

Min w=-2y1+y2

s.t. -y1-2y24

-y1-18

-y1+y210

y10, y20

若原问题的约束条件中含有等式约束条件，它的对偶问题的求法是将登时约束条件分解为两个不等式约束条件，然后按照上述标准求其对偶问题。例如：3 x1 +18 x2-10x3=6可转化为3 x1 +18 x2-10x36和-3 x1 -18 x2+10x3-6

综上，原问题产生对偶问题特点如下：

 对于含n个变量的和m个约束的原问题，对偶问题将有m个变量和n个约束

 原问题中小于等于约束，在对偶问题中变为大于等于约束

 求极大化的原问题变成了求极小的对偶问题

 原问题中目标函数的系数为c1,c2,…,cn, 对偶问题中则为b1,b2,…,bm。

 原问题中的约束条件的右边项为b1,b2,…,bm，对偶问题中则为c1,c2,…,cn。

2

 原问题与对偶问题的变量均为非负。

3. 对偶问题的相关性质定理

1) 对偶定理

M个不等式约束和n个变量约束的原问题：

Max s=c1x1+c2x2+…+cnxn

s.t. a11x1+a12x2+…+a1nxnb1

a21x1+a22x2+…+a2nxnb2

…

am1x1+am2x2+…+amnxnbm

xj0,j=1,2,…,m

引入m个松弛变量xn+1, xn+2, …, xn+m

Max s=c1x1+c2x2+…+cnxn

s.t. a11x1+a12x2+…+a1nxn

+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2

…

am1x1+am2x2+…+amnxn+xn+m=bm

xj0,j=1,2,…,n+m

同理，对偶问题n个剩余变量ym+1, ym+2, …, ym+n得对偶问题：

Min w=b1y1+b2y2+…+bnyn

s.t. a11y1+a21y2+…+am1ym

-ym+1=c1

a12y1+a22y2+…+am2ym-ym+2=c2

…

a1ny1+a2ny2+…+amnym-ym+n=cn

yj0,j=1,2,…,n+m

对于上述两式，对偶定理如下：

 原问题最优解中决策变量xj(j=1,2,…n)和松弛变量xn+i(=1,2,…m)与对偶问题最优解中的剩余变量ym+i(i=1,2,…n)和决策变量yj(j=1,2,…,m)的检验数，在数值上（仅相差一个负号）对应相等。

 Smax= Wmin

2）互补松弛定理

 如果原问题中的最优解中，某一松弛变量xn+i(=1,2,…m)的值为非零，则对偶问题的最优解中第j个变量yj(j=1,2,…,m)的值为零。反之，若对偶问题最优解中，某一剩余变量

m+j(j=1,2,…,n)的值不为零，则原问题的最优解中第j个变量xj(j=1,2,…,n)的值为零。

 如果原问题中（或对偶问题中）第j个变量为正，则对偶问题中（或原问题中）的第j个约束应取等式。

例：构造下列线性规划问题的对偶问题并分别求解。

解：

原问题：

Max s=5x1+4x2

3

s.t. 2x1+2x24

3x22

4x1+x23

xj0,j=1,2

对偶问题：

Min w=4y1+2y2+3y3

s.t. 2y1+4y35

2y1+3y2+y34

-y1+y210

y10, y20, y30

原问题的最后一张单纯形表

cj

cB

0

4

5

对偶问题的最后一张单纯形表

cj

cB

-3

-2

4.对偶单纯形法

例：求解下列线性规划问题

原问题：Min s=4x1+2x3

s.t. x1+x2-x35

x1-x2+4x38

xj0,j=1,2,3

解：将这个问题转化为标准型

Max s=-4 x1-2x3+0x4+0x5

s.t. -x1- x2+x3+x4=-5

-x1+2x2-4x3+x5=-8

xj0,j=1,2,…,5

以x4, x5作为基变量，则x4=-5，x5=-8

初始解不可行，但最后一行检验数全部小于零，因而对求最大值的对偶问题满足单纯形法的最优准则。

由对偶定理，这组基对偶可行。

4

6

b

3/2

2/3

7/12

-67/12

x1

0

0

1

0

0

x2

0

1

0

0

0

x3

1

0

0

0

0

x4

-1/2

1/3

-1/12

-11/12

0

x5

1/2

0

1/4

-5/4

xB

x3

x2

x1

θi

S

-4

b

5/4

11/12

-67/12

y1

1/2

1/2

-3/2

-2

y2

0

1

0

-3

y3

1

0

0

0

y4

-1/4

1/12

-7/12

0

y5

0

-1/3

-2/3

θi

yB

y3

y2

-w’

原问题的初始单纯形表

cj

cB

0

0

xB

x4

x5

b

-5

-8

0

6

x1

-1

-1

-4

0

x2

-1

2

0

0

x3

1

-4

-2

0

x4

1

0

0

0

x5

0

1

0

θi

-S

第一步：基变量存在负值，最小的那个应作为换出变量（对偶单纯形准则Ⅰ），故应换出x5

第二步：确定换入、换出变量的位置。取非基变量的检验数于换出变量所在行的相应系数（0不考虑）之比，选比值最小的作为换入变量（对偶单纯形准则Ⅱ），故应换入x3

非基变量

检验数

第二行系数

比值

x1

-4

-1

4

x2

0

2

--

x3

-2

-4

1/2

再次按照单纯形法变化规则进行计算，可得到

s’=- 4, x4=-7, x3=2

此时一个非可行解已经消除，但x4=-7仍是非可行的，再次利用准则Ⅱ

一个新的基本解

cj

cB

0

0

非基变量

检验数

第二行系数

比值

换入x2得到下表

cj

cB

0

0

xB

X2

X3

b

14

9

18

x1

-7/2

-5/4

14/5

x2

-1

-1/2

2

x3

-1/2

1/4

xB

x4

X3

b

-7

2

4

-4

x1

-5/4

1/4

-7/2

0

x2

--1/2

-1/2

-1

-2

x3

0

1

0

0

x4

1

0

0

0

x5

1/4

-1/4

-1/2

θi

-S’

-4

x1

5/2

6/4

-1

0

x2

1

0

0

-2

x3

0

1

0

0

x4

-2

-1

-2

0

x5

-1/2

-1/2

-1

θi

-S’

可得到 s’=- 18, x2=14, x3=9

所有基变量非负，检验数非正，故这组解是一个最优解 x1*

对偶单纯形法的计算步骤

1. 列出初始单纯形表

2. 若b列数字都为负，且检验数为非正，则为最优解；b中含有负数，检验数非正，5

3.

4.

5.

6.

7.

进行以下计算

根据准则Ⅰ，确定换出变量xl

检查xl所在行的各系数，若全部大于等于零，则无可行解停止计算；否则转入下个步骤

计算非基变量检验数与xl所在行相应的小于零的系数的比较

根据准则Ⅱ壁纸最小者对应的呃变量xk为换入变量

以aa,k为主元素，按照单纯形法迭代步骤2

例：Min s= 3x1 + x2+2x3

s.t. x1 +x2-x31

x1-2x2 +3x3-1

x10, x20, x30

解：转化为标注型

Max s= -3x1 - x2-2x3

s.t. -x1 -x2+x3+ x4=-1

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

Xj0, j=1, 2,…, 5

初始单纯形表及对偶单纯形法计算过程

Cj -4

cB

0

0

xB

x1

b

-1

1

0

1

-1

1

2/3

1/3

5/3

x1

-1

-1

-3

1

-3

-2

2

1

0

0

x2

-1

2

-1

1

0

0

1

0

0

-2

x3

2

-3

-2

-2

1

-4

-5/3

-1/3

-14/3

0

x4

1

0

0

-1

2

-1

-1/3

-2/3

-7/3

0

x5

0

1

0

0

1

0

1/3

-1/3

-2/3

θi

x5

-S’

-1

0

x2

x5

-S’

-1

-3

x2

x1

-S’

最优解为s=5/3, x1=1/3, x2=2/3

对偶纯形法的有点以下优点

 初始解可以是非可行解（检验数为非正）

 对于变量少于约束条件的线性规划，可减少计算工作量

 在灵敏度分析、整数规划中有时应用对偶单纯形法会使问题的处理大大简化

6