2023年哈工大運籌學(xué)大作業(yè)對偶單純形法對比

運籌學(xué)課程

運籌學(xué)對偶單純形法與單純形法

對比分析大作業(yè)

哈爾濱工業(yè)大學(xué)工業(yè)工程系

學(xué)生姓名：

學(xué)號：11208401

指導(dǎo)教師：

成績：

評語：

運籌學(xué)對偶單純形法與單純形法對比分析

摘要：這篇論文重要介紹了對偶單純形法的實質(zhì)、原理、流程和合用條

件等。將對偶單純形法與單純形法的基本思想進(jìn)行對比分析，從而說明對偶

單純形法的優(yōu)點和合用范圍。

關(guān)鍵詞：對偶單純形法；對偶理論；單純形法;基本思想

在線性規(guī)劃初期發(fā)展階段的眾多重要發(fā)現(xiàn)中，對偶的概念及其分支是其

中最重要的內(nèi)容之一。這個發(fā)現(xiàn)指出，對于任何一個線性規(guī)劃問題都具有相

應(yīng)的稱為對偶問題的線性規(guī)劃問題。對偶問題與原問題的關(guān)系在眾多領(lǐng)域都

非常有用。

（一）教學(xué)目的：

通過對偶單純形法的學(xué)習(xí)，加深對對偶問題的理解。掌握對偶單純形法

的解題過程，理解對偶理論的其原理，了解對偶單純形法的作用和應(yīng)用范圍

（二）教學(xué)內(nèi)容：

1）對偶單純形法的思想來源

2）對偶單純形法原理

3）對偶理論的實質(zhì)

4）單純形法和對偶單純形法的比較

（三）教學(xué)進(jìn)程：

一、對偶單純形法的思想來源

所謂對偶單純形法，就是將單純形法應(yīng)用于對偶問題的計算，該方法是由

美國數(shù)學(xué)家C.萊姆基于1954年提出的，它并不是求解對偶問題解的方法,

而是運用對偶理論求解原問題的解的方法。

二、對偶問題的實質(zhì)

下面是原問題的標(biāo)準(zhǔn)形式以及其相應(yīng)的對偶問題:

原問題對偶問題

nm

MaxZ=〉CjX；MinW=biYi

i=ij=1

nn

s.t.ajjXj<bji=1,2,…/ns.t.2a.yi>Cjj=1,2,-j

Yi>0i=1,2,…,m

Xj>0j=1,2,…,n

從而可以發(fā)現(xiàn)如下規(guī)律：

1.原問題目的函數(shù)系數(shù)是對偶問題約束方程的右端項。

2.原問題約束方程的右端項是對偶問題目的函數(shù)的系數(shù)。

3.原問題一個變量在所有約束方程中的系數(shù)是對偶問題一個約束方程

中的所有系數(shù)。

三、對偶單純形法原理

對偶單純形法是通過尋找原問題的對偶問題的可行解來求解原問題的最

優(yōu)解的方法,它的應(yīng)用涉及影子價格和靈敏度分析等。為了理解對偶單純形法

為什么可以解出原方程的最優(yōu)解，我們需要對對偶理論的幾個基本原理有所

了解。

1.弱對偶性

假如有O=1，…，n）是原問題的可行解，式。=1，…，m）是其對偶問題的可行

解，則恒有

nin

￡c西w￡b岳

j=1i=1

證明：由于對偶方程中原問題的約束條件是各行的a“Xi之和小于等于y

i的系數(shù)bi,而對偶問題的約束條件是各行的aryi之和小于等于xj的系數(shù)g,

故將A=iCjXj和，二】b岳分別和'i==Nja”五比較，可得上述結(jié)論。

2.最優(yōu)性

假如A。=1，…，n）是原問題的可行解，力。=1，…，m）是其對偶問題的可行

解，且有

nm

2jCjXj=^biYi

j=1i=1

則3（j=1，…,n）是原問題的最優(yōu)解,《=1,…,m）是其對偶問題的最優(yōu)解。

證明：由

nm

￡酒式￡b岳

j=1i=1

可得

nmn

2jcixi-2jbiyi=2?CjXj

j=1i=1j=1

mnm

2,biyi-2,cjXj=2ubiyi

i=1j=1i=1

故可知&（j=1，…，n）是原問題的最優(yōu)解，1。=1，…，m）是其對偶問題的最

優(yōu)解。

3.強對偶性

假如原問題有最優(yōu)解，那么其對偶問題也有最優(yōu)解，且有maxz=minw.

證明：設(shè)8為原問題式（1）的最優(yōu)基，那么當(dāng)基為B時的檢查數(shù)為

c-G/可,其中圖為由基變量的價值系數(shù)組成的價值向量。

既然B為原問題式⑴的最優(yōu)基,那么有1-CQA401

令kcal那么有|C-GW0nE42C|,從而|丫=18］是對偶問題式（2）的

可行解。

這樣一來,卜=C"81是對偶問題的可行解,|x,i兄是原問題的最優(yōu)基可行

解。

由于回=OX"+CNXN=O咽,而|監(jiān)=.叫從而有叵卷L根據(jù)最優(yōu)

性，命題得證。

4.線性規(guī)劃的問題原問題及對偶問題之間存在一對互補的基解,其中原

問題的松弛變量相應(yīng)對偶問題的變量，對偶問題的剩余變量相應(yīng)原問題的變

量；這些互相相應(yīng)的變量假如在一個問題中是基變量，則在另一問題中是非基

變量；將這對互補的基解分別代入原問題和對偶問題的目的函數(shù)有Z=w。

四、對偶單純形算法流程

在上述的理論基礎(chǔ)上，可知用單純形法求解線性規(guī)劃問題時，在得到原

問題的一個基可行解問題同時，在檢查數(shù)行得到對偶問題的一個基解。單純形

法的基本思想是保持原問題為可行解的基礎(chǔ)上，通過迭代增大目的函數(shù)，當(dāng)其

對偶問題也為可行解時，就達(dá)成了目的函數(shù)的最優(yōu)值。

而對偶單純形法的基本思想則是保持對偶問題為可行解的前提下（即單

純性表最后一行檢查數(shù)都小于零），通過迭代減小目的函數(shù)，當(dāng)原問題也是可

行解時，就得到了目的函數(shù)的最優(yōu)解。

故我們可以得到對偶單純形法求解過程如下：

1.將原問題化為標(biāo)準(zhǔn)型，找到一個檢查數(shù)都小于等于零的對偶問題的初

始可行基。

2.擬定換出基的變量

對于小于零的b”找到最小的一個br,其相應(yīng)的X,為換出基的變量

3.擬定換入基的變量

（1）為了使迭代后表中的第r行基變量為正值，因而只有相應(yīng)期小于零

的非基變量才可以作為換入基的變量；

（2）為了使迭代后表中對偶問題仍為可行解，令

min[ci-zi,1Cs-Zs

0=j----------ari<0=-----------

JIa"ars

稱a”為主元素,xs為換入基的變量。

4.用換入變量替換換出變量，得到一個新的基。再次檢查是否所有的bi大

于等于零。假如是，則找到了最優(yōu)解，假如否，則再次進(jìn)行變換。

對偶單純形法的算法流程圖

化原問題為標(biāo)準(zhǔn)型

找出一個對偶問題的初始可行基Bo,計算

非基變量檢查數(shù)（所有檢查數(shù)。jWO）并

□

已找到最優(yōu)解

結(jié)束

五、對偶單純形法例題

下面用一個例子來說明對偶單純形法的解題過程。

Minz=5xi+2X2+4X3

(3x1+x2+2x3>4

j6x1+3x2+5x3>10

.(xl,x2,x3>0

L化為標(biāo)準(zhǔn)型

Maxz"=-5xI-2X2-4X3+0x4+0x5

'-3xl-x2-2x3+x4=-4

-6x1-3x2-5x3+x5=-10

、xl,x2,x3,x4,x5>0

2.列出原始單純形表

CL—5-2-400

CB基X]X5

x2x3X4

b

0X4-3-1-210

—4-6[-3]-501

0x5-1

0

cj-zj-5-2—400

3.找出最小的bi,即b5=.10.選擇x5作為換出變量。

r?一7?

min勺?2c2-z2

0ari<0

3322

故選擇a22為主元素,x2為換入變量，得到新的單純形表:

cjf-5-2—400

基XiX4

CBx2X3X5

b

0x4[-1]0-1/31-1/3

2/3215/30-1/3

-2X2

10/3

Cj-Zj-10-2/30-2/3

再次換入換出：

Cj-*—5-2-400

CB基x5

Xix2x3x4

b

-5Xi2/3101/3-11/3

-2x220112-1

Cj-Zj00-1/3-1-1/3

4.所有的bi都大于零，說明找到了最優(yōu)解。

X=(2/3,2,0)T

Maxi'=-10/3-4=-22/3

Minz=22/3.

但是，對偶單純形法并不是一種普遍算法，它有一定的局限性，不是任何線

性規(guī)劃問題都能用對偶單純形法計算的。當(dāng)線性規(guī)劃問題具有下面條件時，

可以用對偶單純形法求解：

①問題標(biāo)準(zhǔn)化后，價值系數(shù)全非正；

②所有約束全是不等式。

六、對偶單純形法的應(yīng)用

1.從上面的例題可以看出，原問題是求最小值，并且目的函數(shù)各項系數(shù)

都不小于零。所以在轉(zhuǎn)化成標(biāo)準(zhǔn)型后各項系數(shù)不大于零,從而以松弛變量為基

列出的單純形表滿足檢查數(shù)都不大于零，是其對偶問題的一個可行解。假如

原問題的標(biāo)準(zhǔn)形式中各項系數(shù)不都小于零，則不容易找到對偶問題的一個初

始可行解,就不適合使用對偶單純形法求解。

所以對偶單純形法合用于不易找到原方程的可行解而容易找到其對偶問

題的可行解的線性規(guī)劃問題。

2.我們知道，約束方程的數(shù)量對單純形法的計算過程要遠(yuǎn)遠(yuǎn)大于變量個數(shù)

的影響。假如m>n,那么對偶問題有n個約束方程，而原問題有m個約束方

程，所以對偶問題有更少的約束方程數(shù)量，那么通過對偶單純形法的運用比起

直接只用單純形法將會顯著的減少計算量。

3.弱對偶性和強對偶性是對偶理論的關(guān)鍵原理。對偶問題可以用來對原

問題的計劃方案進(jìn)行評價。我們可以用一個對偶問題的可行解和目前原問題

的計