對偶單純形法

2024年3月4日發(fā)(作者：收發(fā)文)

1.對偶問題模型

2.對偶例子，總結(jié)特點

3.對偶的相關(guān)性質(zhì)定理

4.對偶單純形法

1. 對偶問題模型

例：某化工廠利用R1、R2、R3 三種原料，生產(chǎn)Q1、Q2兩種產(chǎn)品，生產(chǎn)每公斤產(chǎn)品所需的各單位原料、工廠所擁有的個資源最大量及每公斤產(chǎn)品銷售利潤如下表所示，問每天應生產(chǎn)多少公斤Q1、Q2才能使利潤最大。

原料-產(chǎn)品-利潤表

產(chǎn)品

資源

R1原料（公斤）

R2原料（公斤）

R3原料（公斤）

利潤（萬元/公斤）

生產(chǎn)每公斤產(chǎn)品Q1

3.0

4.0

9.0

0.7

生產(chǎn)每公斤產(chǎn)品Q2

10.0

5.0

4.0

1.2

每天原料的最大

用量（公斤）

300

200

360

設每天生產(chǎn)Q1、Q2的產(chǎn)品量為x1，x2，可得到約束方程

Max s=0.7 x1 +1.2 x2

3x1 + 10x2?300

4x1 + 5x2?200

9x1 + 4x2?360

x1?0, x2?0

現(xiàn)在的問題是，如果另一個化工廠想全部購買該廠R1、R2、R3 三種原料，那么該廠在什么條件下出售這三種原料，才能使該廠在經(jīng)濟收入上不低于用等量的三種原料生產(chǎn)Q1、Q2產(chǎn)品獲得的最大利潤。

設三種原料出售單價分別為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

比較兩個線性規(guī)劃模型，其特征有

? 目標函數(shù)的要求上兩者相反，s求max，w求min

? 右端向量和目標函數(shù)的價值系數(shù)兩者對調(diào)

? 約束方程兩者符號相反，s是“?”，w是“?”

? 由s的約束方程書引入了同等數(shù)量的另一組非負變量u=( u1, u2, u3)T,且作為w的決策變量，約束方程數(shù)由m個變?yōu)閚個

2. 對偶問題及其轉(zhuǎn)化方

對偶問題在理論和實踐方面有著廣泛的應用

? 在某些情況下線性規(guī)劃的對偶問題比原解問題更容易

1

? 對偶變量對原問題的解提供了重要的經(jīng)濟意義

? 在處理一般型初始模型時可以不引入人工變量而采用對偶單純形法直接處理，減少計算量

? 推證出若干重要性質(zhì)和定理

? 作為線性規(guī)劃靈敏度分析的重要工具

例：求下列線性規(guī)劃的對偶問題：

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

需要注意的是，如果原問題的目標函數(shù)為求極小，其目標函數(shù)的系數(shù)需要乘-1變成求極大，如果某些約束為“?”，則這些約束需乘-1，變成“?”，才能產(chǎn)生相應的對偶問題。

例：求下列線性規(guī)劃的對偶問題：

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可轉(zhuǎn)化為3 x1 +18 x2-10x3?6和-3 x1 -18 x2+10x3?-6

綜上，原問題產(chǎn)生對偶問題特點如下：

? 對于含n個變量的和m個約束的原問題，對偶問題將有m個變量和n個約束

? 原問題中小于等于約束，在對偶問題中變?yōu)榇笥诘扔诩s束

? 求極大化的原問題變成了求極小的對偶問題

? 原問題中目標函數(shù)的系數(shù)為c1,c2,…,cn, 對偶問題中則為b1,b2,…,bm。

? 原問題中的約束條件的右邊項為b1,b2,…,bm，對偶問題中則為c1,c2,…,cn。

2

? 原問題與對偶問題的變量均為非負。

3. 對偶問題的相關(guān)性質(zhì)定理

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

對于上述兩式，對偶定理如下：

? 原問題最優(yōu)解中決策變量xj(j=1,2,…n)和松弛變量xn+i(=1,2,…m)與對偶問題最優(yōu)解中的剩余變量ym+i(i=1,2,…n)和決策變量yj(j=1,2,…,m)的檢驗數(shù)，在數(shù)值上（僅相差一個負號）對應相等。

? Smax= Wmin

2）互補松弛定理

? 如果原問題中的最優(yōu)解中，某一松弛變量xn+i(=1,2,…m)的值為非零，則對偶問題的最優(yōu)解中第j個變量yj(j=1,2,…,m)的值為零。反之，若對偶問題最優(yōu)解中，某一剩余變量

m+j(j=1,2,…,n)的值不為零，則原問題的最優(yōu)解中第j個變量xj(j=1,2,…,n)的值為零。

? 如果原問題中（或?qū)ε紗栴}中）第j個變量為正，則對偶問題中（或原問題中）的第j個約束應取等式。

例：構(gòu)造下列線性規(guī)劃問題的對偶問題并分別求解。

解：

原問題：

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.對偶單純形法

例：求解下列線性規(guī)劃問題

原問題：Min s=4x1+2x3

s.t. x1+x2-x3?5

x1-x2+4x3?8

xj?0,j=1,2,3

解：將這個問題轉(zhuǎn)化為標準型

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

初始解不可行，但最后一行檢驗數(shù)全部小于零，因而對求最大值的對偶問題滿足單純形法的最優(yōu)準則。

由對偶定理，這組基對偶可行。

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

第二步：確定換入、換出變量的位置。取非基變量的檢驗數(shù)于換出變量所在行的相應系數(shù)（0不考慮）之比，選比值最小的作為換入變量（對偶單純形準則Ⅱ），故應換入x3

非基變量

檢驗數(shù)

第二行系數(shù)

比值

x1

-4

-1

4

x2

0

2

--

x3

-2

-4

1/2

再次按照單純形法變化規(guī)則進行計算，可得到

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

此時一個非可行解已經(jīng)消除，但x4=-7仍是非可行的，再次利用準則Ⅱ

一個新的基本解

cj

cB

0

0

非基變量

檢驗數(shù)

第二行系數(shù)

比值

換入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

所有基變量非負，檢驗數(shù)非正，故這組解是一個最優(yōu)解 x1*

對偶單純形法的計算步驟

1. 列出初始單純形表

2. 若b列數(shù)字都為負，且檢驗數(shù)為非正，則為最優(yōu)解；b中含有負數(shù)，檢驗數(shù)非正，5

3.

4.

5.

6.

7.

進行以下計算

根據(jù)準則Ⅰ，確定換出變量xl

檢查xl所在行的各系數(shù)，若全部大于等于零，則無可行解停止計算；否則轉(zhuǎn)入下個步驟

計算非基變量檢驗數(shù)與xl所在行相應的小于零的系數(shù)的比較

根據(jù)準則Ⅱ壁紙最小者對應的呃變量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

解：轉(zhuǎn)化為標注型

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’

最優(yōu)解為s=5/3, x1=1/3, x2=2/3

對偶純形法的有點以下優(yōu)點

? 初始解可以是非可行解（檢驗數(shù)為非正）

? 對于變量少于約束條件的線性規(guī)劃，可減少計算工作量

? 在靈敏度分析、整數(shù)規(guī)劃中有時應用對偶單純形法會使問題的處理大大簡化

6