工程最優(yōu)化方法

1、第二章第二章 線性規(guī)劃線性規(guī)劃 lixgi, 1 , 0)(mxhj, 1j , 0)( min f(x) s.t. 在模型在模型 中中當(dāng)當(dāng)f(x), g i(x), (i=1,l ), hj(x), (j=1,m)均為線性函數(shù)時，稱為均為線性函數(shù)時，稱為線性規(guī)劃線性規(guī)劃問題問題 Linear Programming ( LP ) 二維問題的圖解法二維問題的圖解法 線性規(guī)劃的基本定理線性規(guī)劃的基本定理 單純形法單純形法 大大M法法要點：要點：基本定理、頂點、標(biāo)準(zhǔn)形式、典范形式、可行基本解、基本定理、頂點、標(biāo)準(zhǔn)形式、典范形式、可行基本解、 價值系數(shù)、最優(yōu)性準(zhǔn)則、單純形表格法價值系數(shù)、最優(yōu)性準(zhǔn)則、

2、單純形表格法 研究重要性研究重要性（1）一些）一些 NLP 問題可簡化為問題可簡化為 LP 問題求解問題求解（2）是開發(fā)一些較復(fù)雜）是開發(fā)一些較復(fù)雜 NLP 算法的基礎(chǔ)算法的基礎(chǔ)（3）是所有最優(yōu)化方法中最常用的技術(shù)）是所有最優(yōu)化方法中最常用的技術(shù) ( 占占47；科學(xué)計算中，；科學(xué)計算中，LP的計算時間占的計算時間占1/4） 1939 1939年，蘇聯(lián)數(shù)學(xué)家康托洛維奇提出并解決了一個線性規(guī)劃年，蘇聯(lián)數(shù)學(xué)家康托洛維奇提出并解決了一個線性規(guī)劃問題（問題（生產(chǎn)組織與計劃中的數(shù)學(xué)方法生產(chǎn)組織與計劃中的數(shù)學(xué)方法） 1947 1947年，美國數(shù)學(xué)家年，美國數(shù)學(xué)家G.B.DantzingG.B.Dantzin

3、g提出單純形法，奠定了提出單純形法，奠定了LPLP的理論基礎(chǔ)的理論基礎(chǔ) 1832和和1911年，法國數(shù)學(xué)家年，法國數(shù)學(xué)家J. B. J.傅里葉和傅里葉和C.瓦萊普森分別瓦萊普森分別提出線性規(guī)劃的想法提出線性規(guī)劃的想法2.1 2.1 建立建立LPLP問題數(shù)學(xué)模型的實例問題數(shù)學(xué)模型的實例 （1）確定自變量）確定自變量建模的三個步驟建模的三個步驟 （2）把問題的約束條件表示成等式或不）把問題的約束條件表示成等式或不等式等式 （3）寫出目標(biāo)函數(shù)）寫出目標(biāo)函數(shù)例例2.1.1 確定職工編制問題確定職工編制問題 某廠每日某廠每日8小時的產(chǎn)量不低于小時的產(chǎn)量不低于1800件。為了進(jìn)行質(zhì)量控制，計劃聘請兩種件。

4、為了進(jìn)行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員。一級檢驗員的標(biāo)準(zhǔn)是：速度不同水平的檢驗員。一級檢驗員的標(biāo)準(zhǔn)是：速度 25件件/小時，正確率小時，正確率 98，計時工資計時工資 4元元/小時；二級檢驗員的標(biāo)準(zhǔn)是：速度小時；二級檢驗員的標(biāo)準(zhǔn)是：速度 15件件/小時，正確率小時，正確率 95，計時工資計時工資 3元元/小時。檢驗員每錯驗一次，工廠要損失小時。檢驗員每錯驗一次，工廠要損失2元?，F(xiàn)可供廠方聘請元?，F(xiàn)可供廠方聘請的檢驗員人數(shù)為一級的檢驗員人數(shù)為一級8人和二級人和二級10人。為使總檢驗費用最省，該工廠應(yīng)聘一人。為使總檢驗費用最省，該工廠應(yīng)聘一級和二級檢驗員各多少名？級和二級檢驗員各多少名？分

5、析：分析：設(shè)應(yīng)聘一級檢驗員設(shè)應(yīng)聘一級檢驗員x1 ，二級檢驗員，二級檢驗員x2 約束一：約束一：可聘兩級檢驗員人數(shù)可聘兩級檢驗員人數(shù) x1 8 x2 10 約束二：約束二：每日產(chǎn)量要求每日產(chǎn)量要求 8(25)x1+8(15)x2 1800 5x1+3x2 45 目標(biāo)函數(shù)目標(biāo)函數(shù) 一級檢驗員每小時費用一級檢驗員每小時費用 425 (0.02) (2)=5元元/小時小時 二級檢驗員每小時費用二級檢驗員每小時費用 315 (0.05) (2)=4.5元元/小時小時 f(x) = 8(5x1+4.5x2) = 40 x1+36x2 min f(x)=40 x1+36x2 s.t. 5x1+3x2 45

6、x18 x210 x1, x2 0數(shù)學(xué)模型數(shù)學(xué)模型隱含的隱含的約束條件約束條件2.2 2.2 二維問題的圖解法二維問題的圖解法圖解步驟圖解步驟（1）在在x10 x2坐標(biāo)平面上畫出可行域；坐標(biāo)平面上畫出可行域；（2）作目標(biāo)函數(shù)的等高線作目標(biāo)函數(shù)的等高線 (為一組平行的直線為一組平行的直線)，根據(jù)等高線函數(shù)值的變化規(guī)律及目標(biāo)函數(shù)的要根據(jù)等高線函數(shù)值的變化規(guī)律及目標(biāo)函數(shù)的要 求，確定等高線的移動方向，按此方向移動求，確定等高線的移動方向，按此方向移動 等高線，使其達(dá)到可行域的極限點（最優(yōu)點）；等高線，使其達(dá)到可行域的極限點（最優(yōu)點）；（3）根據(jù)最優(yōu)點的位置，聯(lián)立求解對應(yīng)的約束方程，根據(jù)最優(yōu)點的位置，

7、聯(lián)立求解對應(yīng)的約束方程， 求出最優(yōu)點坐標(biāo)；求出最優(yōu)點坐標(biāo)；（4）將最優(yōu)點坐標(biāo)代入目標(biāo)函數(shù)，求出最優(yōu)值。將最優(yōu)點坐標(biāo)代入目標(biāo)函數(shù)，求出最優(yōu)值。ABCD P19 例：例： max f(x)=4x1+3x2 s.t. 3x1+4x212 3x1+3x210 4x1+2x28 x1, x2 00 x1x2343x1+4x2=123x1+3x2=104x1+2x2=8f =7f =52/5最優(yōu)點最優(yōu)點(x1* =4/5, x2*=12/5)f *=52/5 ABCD 例：例： max f(x)=4x1+ 3 x2 s.t. 3x1+4x212 3x1+3x210 4x1+2x28 x1, x2 00 x

8、1x23x1+4x2123x1+3x2104x1+2x28f =4f =8最優(yōu)點：最優(yōu)點：CD上的所有點上的所有點f *=8 2.3 2.3 線性規(guī)劃問題的幾種特殊情況線性規(guī)劃問題的幾種特殊情況2.3.12.3.1 有無限個最優(yōu)解有無限個最優(yōu)解2 例：例： max f(x)=4x1+3x2 s.t. 3x1+4x2 12 3x1+3x2 10 4x1+2x2 8 x1, x2 00 x1x23x1+4x2=123x1+3x2=104x1+2x2=82.3.22.3.2 無界可行域無界可行域f 增大方向增大方向數(shù)學(xué)上存在數(shù)學(xué)上存在但對于實際問題，可但對于實際問題，可能是遺漏或?qū)戝e了約能是遺漏或?qū)?/p>

9、錯了約束條件！束條件！0 x1x23x1+4x2=123x1+3x2=104x1+2x2=82.3.32.3.3 可行域為空集可行域為空集 例：例： max f(x)=4x1+3x2 s.t. 3x1+4x2 12 3x1+3x2 10 4x1+2x2 8 x1, x2 02.4 2.4 線性規(guī)劃的基本定理線性規(guī)劃的基本定理2.4.1 2.4.1 凸集與頂點凸集與頂點凸集：凸集：設(shè)設(shè)M為為Rn中的一個集合，如果對中的一個集合，如果對M中任意兩點為端點中任意兩點為端點 的線段全部含于的線段全部含于M中，則稱中，則稱M為凸集。為凸集。 x(1) x(2) x(1) x(2) 直觀理解：直觀理解：內(nèi)

10、部沒有內(nèi)部沒有“洞洞”，邊界不向內(nèi)凹的形體，邊界不向內(nèi)凹的形體非凸集非凸集實例實例x(1) x(2) A B C D FE G H（球面上的所有（球面上的所有 點都是頂點）點都是頂點） 凸集的基本性質(zhì)凸集的基本性質(zhì)若若M1和和M2為凸集，為凸集，為正實數(shù)，則集合為正實數(shù)，則集合 （1）y|y =x, xM1 （2）y|y =x+z, xM1, zM2 （3）M1和和M2的交集的交集M1M2都為凸集。都為凸集。 頂點頂點如果凸集如果凸集M中的一個點中的一個點x不是不是M中任一線段的內(nèi)點，則中任一線段的內(nèi)點，則x是是M的一個頂點的一個頂點 K2.4.2 2.4.2 線性規(guī)劃的兩個重要性質(zhì)線性規(guī)劃的

11、兩個重要性質(zhì)基本定理基本定理（1）線性規(guī)劃的可行域是一個凸集；）線性規(guī)劃的可行域是一個凸集； （2）線性規(guī)劃若存在可行點，則必存在可行域的頂點；）線性規(guī)劃若存在可行點，則必存在可行域的頂點； 若存在最優(yōu)點，則至少有一個頂點是最優(yōu)點。若存在最優(yōu)點，則至少有一個頂點是最優(yōu)點。 定理的重要意義定理的重要意義（1）保證了頂點的存在性；）保證了頂點的存在性； （2）把一般要從無限個可行點中尋優(yōu)最優(yōu)點的問題）把一般要從無限個可行點中尋優(yōu)最優(yōu)點的問題 簡化為僅在有限個頂點中確定最優(yōu)點的問題簡化為僅在有限個頂點中確定最優(yōu)點的問題 問題：為什么頂點只有有限個？怎樣找出頂點？問題：為什么頂點只有有限個？怎樣找出頂

12、點？2.5 2.5 線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式一般一般LP標(biāo)準(zhǔn)標(biāo)準(zhǔn)LP單純形法求解標(biāo)準(zhǔn)單純形法求解標(biāo)準(zhǔn)LP 思路：思路： min z=c1x1+ c2x2+ cnxns.t. a11x1+ a12x2+ a1nxn=b1 a21x1+ a22x2+ a2nxn=b2 am1x1+ am2x2+ amnxn=bm目標(biāo)函數(shù)目標(biāo)函數(shù)x10, x20, , xn0b10, b20, , bm0非負(fù)條件非負(fù)條件約束方程組約束方程組 LP LP的標(biāo)準(zhǔn)形式：的標(biāo)準(zhǔn)形式： 用矩陣和向量表示的用矩陣和向量表示的LPLP的標(biāo)準(zhǔn)形式：的標(biāo)準(zhǔn)形式：c=c1,c2,cnT 價值系數(shù)向量價值系數(shù)向量x=x1,x

13、2,xnT 決策向量決策向量b=b1,b2,bnT 要求向量要求向量a11 a12 a1n a21 a22 a2n am1 am2 amn A= 系數(shù)矩陣系數(shù)矩陣 min z = cTx s.t. Ax = b x 0 b 0 目標(biāo)函數(shù)目標(biāo)函數(shù)非負(fù)條件非負(fù)條件約束方程組約束方程組n LP的維數(shù)的維數(shù) m LP的階數(shù)的階數(shù)2.5.1 2.5.1 將等式約束的右端化為非負(fù)將等式約束的右端化為非負(fù) 若某等式約束的若某等式約束的bi 0 2.5.2 2.5.2 化不等式約束為等式約束化不等式約束為等式約束 （1）若第若第 i 個約束條件為個約束條件為 ai1x1+ ai2x2+ ainxn bi 則引

14、入則引入“剩余變量剩余變量” wi 0 ，將不等式化為等式，將不等式化為等式 ai1x1+ ai2x2+ ainxnwi = bi （2）若第若第 i 個約束條件為個約束條件為 ai1x1+ ai2x2+ ainxn bi 則引入則引入“松弛變量松弛變量” wi 0 ，將不等式化為等式，將不等式化為等式 ai1x1+ ai2x2+ ainxnwi = bi 不利方面：維數(shù)增加了！不利方面：維數(shù)增加了?。ㄔ冢ㄔ贚P中存在可取任意值的自由變量中存在可取任意值的自由變量xj ，在標(biāo)準(zhǔn)形式中不允許存在），在標(biāo)準(zhǔn)形式中不允許存在）方法二：方法二： 引進(jìn)新變量引進(jìn)新變量xj0, xj”0, 作變換作變換x

15、j=xjxj”， 代入原問題消除代入原問題消除xj （參見（參見 PP25 例例2.5.1 )2.5.3 2.5.3 自由變量的處理自由變量的處理方法一：方法一：（消去法）（消去法） （1）先用松馳變量或剩余變量將約束條件中的不等式先用松馳變量或剩余變量將約束條件中的不等式 變?yōu)榈仁?；變?yōu)榈仁剑?（2）把自由變量把自由變量xj 從某個等式約束中解出；從某個等式約束中解出； （3）把已解出的）把已解出的xj 代入其余約束及目標(biāo)函數(shù)，代入其余約束及目標(biāo)函數(shù)， 新問題中消去了新問題中消去了xj 。2.5.4 2.5.4 化最大值問題為最小值問題化最大值問題為最小值問題 若原問題為若原問題為 max

16、z = d1x1+d2x2+ dnxn則引入新目標(biāo)函數(shù)則引入新目標(biāo)函數(shù) z = z ，而約束條件不變，而約束條件不變，原問題等價為原問題等價為 min z =- - d1x1- -d2x2- - -dnxn 上次課回顧上次課回顧 2.2 2.2 二維問題的圖解法二維問題的圖解法2.3 2.3 線性規(guī)劃問題的幾種特殊情況線性規(guī)劃問題的幾種特殊情況2.4 2.4 線性規(guī)劃的基本定理線性規(guī)劃的基本定理（1）線性規(guī)劃的可行域是一個凸集；）線性規(guī)劃的可行域是一個凸集； （2）線性規(guī)劃若存在可行點，則必存在可行域的頂點；）線性規(guī)劃若存在可行點，則必存在可行域的頂點； 若存在最優(yōu)點，則至少有一個頂點是最優(yōu)點

17、。若存在最優(yōu)點，則至少有一個頂點是最優(yōu)點。 2.5 2.5 線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式 min z = cTx s.t. Ax = b x 0 b 02.6 2.6 單純形法單純形法 19471947年由年由美國數(shù)學(xué)家美國數(shù)學(xué)家George Dantzig提出，實踐證明實用提出，實踐證明實用 有效，但理論上不能保證不出現(xiàn)有效，但理論上不能保證不出現(xiàn)退化退化和和迭代循環(huán)迭代循環(huán)的問題。的問題。 后有人提出了修正單后有人提出了修正單 純形法，有所簡化，計算量小了，純形法，有所簡化，計算量小了， 且能避免無限循環(huán)問題且能避免無限循環(huán)問題 求解條件：求解條件：在在LPLP標(biāo)準(zhǔn)形式中，標(biāo)準(zhǔn)形式

18、中，系數(shù)矩陣系數(shù)矩陣A A的的秩秩 m m （即（即m m個約束方程相互獨立）個約束方程相互獨立）否則，否則，n = m，約束方程組只有唯一解，約束方程組只有唯一解 或無解或無解 n m,n m,在在A中任選中任選mm方陣，其行列式至少有一個不等于方陣，其行列式至少有一個不等于0自由度自由度大于零大于零2.6.1 2.6.1 基本概念基本概念( (一一) ) 基本解基本解對于標(biāo)準(zhǔn)形式的對于標(biāo)準(zhǔn)形式的LP， min z=c1x1+ c2x2+ cnxns.t. a11x1+ a12x2+ a1nxn=b1 a21x1+ a22x2+ a2nxn=b2 am1x1+ am2x2+ amnxn=bm

19、x10, x20, , xn0b10, b20, , bm0如何求如何求 min ?2.6.1 2.6.1 基本概念基本概念( (一一) ) 基本解基本解對于標(biāo)準(zhǔn)形式的對于標(biāo)準(zhǔn)形式的LP，如何求如何求 min ?開開 始始解方程組解方程組 Ax = b是否滿足非負(fù)條件？是否滿足非負(fù)條件？否否將解將解x代入目標(biāo)函數(shù)代入目標(biāo)函數(shù)是是目標(biāo)函數(shù)值還能減小嗎？目標(biāo)函數(shù)值還能減小嗎？是是否否得出最優(yōu)解得出最優(yōu)解？ 變量數(shù)變量數(shù) n 方程個數(shù)方程個數(shù)m，可見其中的可見其中的 nm變量變量 可任意取值可任意取值非基本變量非基本變量基本變量基本變量基本解基本解（基本解的個數(shù)（基本解的個數(shù) Cnm個個 ）令其中令

20、其中nm個個變量等于變量等于0解出剩余的解出剩余的m個變量個變量(x1,x2,xm, 0,0)( (二二) ) 可行基本解可行基本解稱稱滿足非負(fù)條件滿足非負(fù)條件（xi 0 , i=1,2,n）的基本解為）的基本解為可行基本解可行基本解? 可行基本解有什么用可行基本解有什么用 ？考察下列線性規(guī)劃問題：考察下列線性規(guī)劃問題： min z=200 x1500 x2 s.t. 1.5x1+5x240 2x1+4x240 x1, x2 0 x20 x1102030AB2468101.5x1+5x2402x1+4x240DC圖解法可知圖解法可知頂點頂點D為最優(yōu)點為最優(yōu)點 x1*=10, x2*=5, z*

21、=4500 z= 2000引入松弛變量，將上述引入松弛變量，將上述LP化為標(biāo)準(zhǔn)形式：化為標(biāo)準(zhǔn)形式： min z=200 x1500 x2 s.t. 1.5x1+5x2 +x3 =40 2x1+4x2 +x4=40 x1, x2 , x3 , x4 0非基本變量非基本變量基本變量基本變量目標(biāo)函數(shù)值目標(biāo)函數(shù)值z是否為可行基本解是否為可行基本解x1x2=0 x3=40, x4=400是是x1x3=0 x2=8, x4=8 4000是是x1x4=0 x2=10, x3= 10否否 5000 x2x3=0 x1=80/3, x4= 40/3否否 16000/3x2x4=0 x1=20, x3=10是是

22、4000 x3x4=0 x1=10, x2=5是是 45000基本解的個數(shù)基本解的個數(shù) C426個個 引入松弛變量，將上述引入松弛變量，將上述LP化為標(biāo)準(zhǔn)形式：化為標(biāo)準(zhǔn)形式： min z=200 x1500 x2 s.t. 1.5x1+5x2 +x3 =40 2x1+4x2 +x4=40 x1, x2 , x3 , x4 0非基本變量非基本變量基本變量基本變量目標(biāo)函數(shù)值目標(biāo)函數(shù)值z是否為可行基本解是否為可行基本解x1x2=0 x3=40, x4=400是是x1x3=0 x2=8, x4=8 4000是是x1x4=0 x2=10, x3= 10否否 5000 x2x3=0 x1=80/3, x4

23、= 40/3否否 16000/3x2x4=0 x1=20, x3=10是是 4000 x3x4=0 x1=10, x2=5是是 4500082461020Cx20AB10D（最優(yōu)）（最優(yōu)）EFC對應(yīng)于右圖中的點對應(yīng)于右圖中的點BAEFCD(最優(yōu)最優(yōu)) LPLP的重要性質(zhì)：的重要性質(zhì)：可行域的每一個頂點與一個可行基可行域的每一個頂點與一個可行基本解相對應(yīng)本解相對應(yīng) 根據(jù)根據(jù)LP的基本定理，可知，的基本定理，可知，只須在有限個可行基本只須在有限個可行基本解中尋優(yōu)！解中尋優(yōu)！ ？如何最簡便地得到可行基本解？如何最簡便地得到可行基本解？如果從如果從LP的一般標(biāo)準(zhǔn)形式出發(fā)，如何獲得可行基本解？的一般標(biāo)準(zhǔn)

24、形式出發(fā)，如何獲得可行基本解？ min z=c1x1+ c2x2+ cnxns.t. a11x1+ a12x2+ a1nxn=b1 a21x1+ a22x2+ a2nxn=b2 am1x1+ am2x2+ amnxn=bmx10, x20, , xn0b10, b20, , bm0( (三三) ) 線性規(guī)劃的典范形式線性規(guī)劃的典范形式 x1 +a1,m+1xm+1+ a1nxn = b1 x2 +a2,m+1xm+1+ a2nxn = b2 xm +am,m+1xm+1+ amnxn = bm假設(shè)在假設(shè)在LP標(biāo)準(zhǔn)形式中的標(biāo)準(zhǔn)形式中的m個約束方程的形式是個約束方程的形式是優(yōu)點：優(yōu)點：令令m個特殊

25、變量為基本變量，其余個特殊變量為基本變量，其余nm個為非個為非基本變量，從而基本變量，從而可立即求得一個可行基本解可立即求得一個可行基本解 xi=bi, i=1,2,mxj=0, j=m+1,n 特點：特點：在在m個約個約束方程中有束方程中有m個個特殊變量，它們特殊變量，它們分別只在一個方分別只在一個方程中出現(xiàn)，且系程中出現(xiàn)，且系數(shù)為數(shù)為1 每一個典范形式與一個可行基本解相對應(yīng)每一個典范形式與一個可行基本解相對應(yīng) ? 如何最簡便地得到典范形式如何最簡便地得到典范形式? min z=c1x1+ c2x2+ cnxns.t. a11x1+ a12x2+ a1nxn=b1 a21x1+ a22x2+

26、 a2nxn=b2 am1x1+ am2x2+ amnxn=bmx10, x20, , xn0b10, b20, , bm0 x1 +a1,m+1xm+1+ a1nxn = b1 x2 +a2,m+1xm+1+ a2nxn = b2 xm +am,m+1xm+1+ amnxn = bm? 消元法消元法？2.6.2 2.6.2 單純形法的基本思路單純形法的基本思路 開開 始始初始可行基本解初始可行基本解x(0)z0=z(x(0) 下一個可行基本解下一個可行基本解x(i)要求要求 zi=z(x(i)zi1 目標(biāo)函數(shù)值還能減小嗎？目標(biāo)函數(shù)值還能減小嗎？是是否否得出最優(yōu)解得出最優(yōu)解( (一一) ) 迭

27、代過程的一般描述迭代過程的一般描述初始頂點初始頂點下一個下一個頂點頂點在一小撮可行基本解中在一小撮可行基本解中尋優(yōu)尋優(yōu) 初始初始典范形式典范形式下一個下一個典范形式典范形式目標(biāo)函數(shù)值下降目標(biāo)函數(shù)值下降( (二二) ) 由一個典范形式化為另一個典范形式的迭代過程由一個典范形式化為另一個典范形式的迭代過程 x1 +a1, m+1xm+1+ a1nxn = b1 x2 +a2, m+1xm+1+ a2nxn = b2 xm+am, m+1xm+1+ amnxn = bm假設(shè)初始典范形式是假設(shè)初始典范形式是xi=bi, i=1,2,m 基本變量基本變量xj=0, j=m+1,n 非基本變量非基本變量初

28、始可行基本解為初始可行基本解為 x1, x2,xm , 0,0T 或或迭代過程分為兩步：迭代過程分為兩步：（1）從原來的非基本變量中選出一個（稱為）從原來的非基本變量中選出一個（稱為進(jìn)基變量進(jìn)基變量）使其成為新的基本變量）使其成為新的基本變量（2）從原來的基本變量中選出一個（稱為）從原來的基本變量中選出一個（稱為離基變量離基變量）使其成為新的非基本變量）使其成為新的非基本變量選進(jìn)基變量和離基變量的原則：使目標(biāo)函數(shù)下降最快選進(jìn)基變量和離基變量的原則：使目標(biāo)函數(shù)下降最快稱為稱為xs的相對的相對價值系數(shù)，價值系數(shù)， 或或檢驗數(shù)檢驗數(shù)1、選取進(jìn)基變量、選取進(jìn)基變量 方法方法：依次讓某個非基本變量增加一

29、個單位值（：依次讓某個非基本變量增加一個單位值（01），），而其而其余非基本變量仍取余非基本變量仍取0，分別計算目標(biāo)函數(shù)的相應(yīng)變化量，選出，分別計算目標(biāo)函數(shù)的相應(yīng)變化量，選出使目標(biāo)函數(shù)下降最快的那個非基本變量作為進(jìn)基變量使目標(biāo)函數(shù)下降最快的那個非基本變量作為進(jìn)基變量設(shè)非基本變量設(shè)非基本變量xs=0 1，xj=0, (j=m+1,n, j s) ， 那么那么 目標(biāo)函數(shù)的變化量為目標(biāo)函數(shù)的變化量為 rs =miisisacc1目標(biāo)函數(shù)的變化量為目標(biāo)函數(shù)的變化量為 rs = cs ci aismi1 min z= c1 x1 + c2 x2 + + cm xm + cs xs + cnxn x1 +

30、a1,m+1xm+1 + + a1s xs + a1nxn = b1 x2 +a2,m+1xm+1 + + a2s xs + a2nxn = b2 xi +ai,m+1xm+1 + + ais xs + ainxn = bi xm +am,m+1xm+1 + ams xs + amnxn = bm需要特別注意的是需要特別注意的是：rs計算公式中計算公式中cB是基本變量在目標(biāo)函數(shù)中是基本變量在目標(biāo)函數(shù)中的價值系數(shù)，的價值系數(shù)，cB中元素的順序與約束方程組（從上到下）中基中元素的順序與約束方程組（從上到下）中基本變量的順序一致。本變量的順序一致。rs = cs ci ais = cs cBTAsm

31、i1目標(biāo)函數(shù)的變化量為目標(biāo)函數(shù)的變化量為 rs = cs ci aismi1 min z= c1 x1 + c2 x2 + + cm xm + cs xs + cnxn x1 +a1,m+1xm+1 + + a1s xs + a1nxn = b1 x2 +a2,m+1xm+1 + + a2s xs + a2nxn = b2 xi +ai,m+1xm+1 + + ais xs + ainxn = bi xm +am,m+1xm+1 + ams xs + amnxn = bm！基本變量的檢驗數(shù)均為零基本變量的檢驗數(shù)均為零?。ㄕ垍⒄眨ㄕ垍⒄誔P29驗證一下）驗證一下）1、選取進(jìn)基變量、選取進(jìn)基變量

32、方法方法：依次讓某個非基本變量增加一個單位值（：依次讓某個非基本變量增加一個單位值（01），），而其而其余非基本變量仍取余非基本變量仍取0，分別計算目標(biāo)函數(shù)的相應(yīng)變化量，選出，分別計算目標(biāo)函數(shù)的相應(yīng)變化量，選出使目標(biāo)函數(shù)下降最快的那個非基本變量作為進(jìn)基變量使目標(biāo)函數(shù)下降最快的那個非基本變量作為進(jìn)基變量設(shè)非基本變量設(shè)非基本變量xs=0 1，xj=0, (j=m+1,n, j s) ， 那么那么 目標(biāo)函數(shù)的變化量為目標(biāo)函數(shù)的變化量為 rs =miisisacc1選取進(jìn)基變量的原則選取進(jìn)基變量的原則：當(dāng)非基本變量相對價值系數(shù)的最小值當(dāng)非基本變量相對價值系數(shù)的最小值 rJ=min rj 0，則相應(yīng)的，

33、則相應(yīng)的xi 隨隨 xJ 的增加而減小的增加而減小(xi =biaiJ xJ )，為了滿足非負(fù)條件，為了滿足非負(fù)條件，必須有必須有 LJLiJiaJababxiJmin0在在xJ增大時，增大時，首先不滿足非首先不滿足非負(fù)條件的負(fù)條件的xL選選為離基變量為離基變量應(yīng)選取應(yīng)選取xL為離基變量為離基變量迭代一步后可行基本解變?yōu)榈徊胶罂尚谢窘庾優(yōu)?： x1, x2, xL1, 0, xL+1, xm, 0 , 0, xJ, 0,0T2.6.3 單純形表格與解題步驟單純形表格與解題步驟 例例2.6.1 求解線性規(guī)劃問題求解線性規(guī)劃問題 min z=3x12x2 s.t. x1+2x2 4 3x1+

34、2x2 14 x1x2 3 x1, x2 0解：解：引入松馳變量引入松馳變量, 將原問題化為標(biāo)準(zhǔn)形式將原問題化為標(biāo)準(zhǔn)形式 min z=3x12x2 s.t. x1+2x2 x3 =4 3x1+2x2 +x4 =14 x1x2 +x5 =3 xi 0， i=1，2，3，4，5嘿嘿，剛好是嘿嘿，剛好是典范形式！典范形式！迭代迭代次數(shù)次數(shù)cB xB 價值系數(shù)價值系數(shù) c b比值比值 （0）rT （1）rT （2）rT 3 2 0 0 0 x1 x2 x3 x4 x5 x3 x4 x50001 2 1 0 0 4 3 2 0 1 0 14 1 1 0 0 1 33 2 0 0 0 14/3 30=zx

35、3 x4 x1 0 03 0 1 1 0 1 7 0 5 0 1 3 5 1 1 0 0 1 3 7 1 0 5 0 0 3 9=zx3 x2 x1 023 0 0 1 1/5 8/5 6 0 1 0 1/5 3/5 1 1 0 0 1/5 2/5 4 0 0 0 1 0 14=z基本變量基本變量價值系數(shù)價值系數(shù)基本變量基本變量最優(yōu)化問題最優(yōu)化問題要求向量要求向量判判斷斷行行最優(yōu)解為最優(yōu)解為(4,1,6,0,0)T, z* = 14 min z=3x12x2 s.t. x1+2x2 x3 =4 3x1+2x2 +x4 =14 x1x2 +x5 =3 xi 0， i=1,5miisissaccr

36、1迭代迭代次數(shù)次數(shù)cB xB 價值系數(shù)價值系數(shù) c b比值比值 （0）rT （1）rT （2）rT 3 2 0 0 0 x1 x2 x3 x4 x5 x3 x4 x50001 2 1 0 0 4 3 2 0 1 0 14 1 1 0 0 1 33 2 0 0 0 14/3 30=zx3 x4 x1 0 03 0 1 1 0 1 7 0 5 0 1 3 5 1 1 0 0 1 3 7 1 0 5 0 0 3 9=zx3 x2 x1 023 0 0 1 1/5 8/5 6 0 1 0 1/5 3/5 1 1 0 0 1/5 2/5 4 0 0 0 1 0 14=z最優(yōu)解為最優(yōu)解為(4,1,6,0,

37、0)T, z* = 14 0=z！基本變量的檢驗數(shù)總為零！基本變量的檢驗數(shù)總為零！2.6.4 2.6.4 退化與循環(huán)退化與循環(huán) （一）（一）退化的可行基本解退化的可行基本解定義：定義：基本變量中有取零的可行基本解稱為退化的可行基本解。基本變量中有取零的可行基本解稱為退化的可行基本解。（1） 初始典范形式的基本解初始典范形式的基本解 就是退化的；就是退化的；( bi 中有等于零的中有等于零的 )（2）迭代過程求離基變量時，迭代過程求離基變量時， 若有一個以上的比值成為若有一個以上的比值成為 最小比值時最小比值時, 則新的可行基本解必是退化的。則新的可行基本解必是退化的?？赡艹霈F(xiàn)退化的可行基本解的

38、情況：可能出現(xiàn)退化的可行基本解的情況：（二）（二）循環(huán)循環(huán)在迭代過程中如出現(xiàn)退化的可行基本解，即出現(xiàn)等于在迭代過程中如出現(xiàn)退化的可行基本解，即出現(xiàn)等于0的的基本變量，如基本變量，如 xk = bk = 0 ，則下次迭代會出現(xiàn)什么情況呢，則下次迭代會出現(xiàn)什么情況呢？假設(shè)假設(shè)xJ被選為進(jìn)基變量，則被選為進(jìn)基變量，則xk=bkakJ xJ，比值，比值( bk/akJ )0 肯定為最小，所以肯定為最小，所以xk被選為離基變量。下一步迭代時，離基被選為離基變量。下一步迭代時，離基變量變量xk=0，則進(jìn)基變量，則進(jìn)基變量xJ =0，所以目標(biāo)函數(shù)值沒有下降，所以目標(biāo)函數(shù)值沒有下降，出現(xiàn)無限循環(huán)情況。出現(xiàn)無限

39、循環(huán)情況。 1976年，年，Bland 提出在迭代過程中遵循兩個規(guī)則，可避免出提出在迭代過程中遵循兩個規(guī)則，可避免出現(xiàn)循環(huán)問題：現(xiàn)循環(huán)問題：（1）如果有幾個非基本變量如果有幾個非基本變量xj的相對價值系數(shù)為負(fù)時，那么的相對價值系數(shù)為負(fù)時，那么選其中下標(biāo)選其中下標(biāo) 最小的為進(jìn)基變量，即如最小的為進(jìn)基變量，即如 J=minj|rj 0，就選，就選xJ為進(jìn)基變量為進(jìn)基變量 ；（選第一個（選第一個rj為負(fù)的）為負(fù)的）（2）選離基變量選離基變量xL時，若同時出現(xiàn)幾個最小比，取其中下標(biāo)時，若同時出現(xiàn)幾個最小比，取其中下標(biāo)最小的基本變量為離基變量。最小的基本變量為離基變量。 這樣處理，收斂速度會變慢，迭代次

40、數(shù)變多，為什么呢？這樣處理，收斂速度會變慢，迭代次數(shù)變多，為什么呢？到此為止，如果給定的到此為止，如果給定的LP為典范形式，我們馬上就能通過為典范形式，我們馬上就能通過單純形法求出最優(yōu)解。單純形法求出最優(yōu)解。但問題是如何由標(biāo)準(zhǔn)形式化為典范但問題是如何由標(biāo)準(zhǔn)形式化為典范形式？形式？用消去法？用消去法？沒有普遍意義沒有普遍意義 思路：思路：如果最初的標(biāo)準(zhǔn)形式不是典范形式，引入人工變量如果最初的標(biāo)準(zhǔn)形式不是典范形式，引入人工變量構(gòu)造一個以典范形式出現(xiàn)的新問題，然后以單純形法解之。構(gòu)造一個以典范形式出現(xiàn)的新問題，然后以單純形法解之。 2.6.5 2.6.5 求初始可行基本解求初始可行基本解 （一）（一

41、）大大M法法+xn+1+xn+2+xn+mMxn+1 Mxn+2 + Mxn+m+m min z=c1x1+ c2x2+ cnxn s.t. a11x1+ a12x2+ a1nxn =b1 a21x1+ a22x2+ a2nxn =b2 am1x1+ am2x2+ amnxn =bm xi0, i=1,2,n b10, b20, , bm0原問題原問題引入人工變量，構(gòu)造新問題引入人工變量，構(gòu)造新問題其中，其中，xn+1 ，xn+2 ， xn+m為人工變量，為人工變量，M為其價值系數(shù)，為其價值系數(shù)，是一個充分大的正數(shù)是一個充分大的正數(shù)只要只要M取得足夠大，新問題的最優(yōu)解與原問題的最優(yōu)解取得足夠大

42、，新問題的最優(yōu)解與原問題的最優(yōu)解是等價的：是等價的：(1) 若新問題不存在最優(yōu)解，即某些人工變量不等于零，若新問題不存在最優(yōu)解，即某些人工變量不等于零， 則原問題不存在最優(yōu)解；則原問題不存在最優(yōu)解； min z=c1x1+ c2x2+ cnxnMxn+1 Mxn+2 + Mxn+m反證法：反證法：如果原問題有解，這個解加上所有的人工變量，并令人工如果原問題有解，這個解加上所有的人工變量，并令人工變量取零值，構(gòu)成新問題的一個可行解，對應(yīng)這個可行解，變量取零值，構(gòu)成新問題的一個可行解，對應(yīng)這個可行解，新問題的目標(biāo)函數(shù)值為一有限值，導(dǎo)致矛盾！新問題的目標(biāo)函數(shù)值為一有限值，導(dǎo)致矛盾！ 只要只要M取得足

43、夠大，新問題的最優(yōu)解與原問題的最優(yōu)解取得足夠大，新問題的最優(yōu)解與原問題的最優(yōu)解是等價的：是等價的：(1) 若新問題不存在最優(yōu)解或有些人工變量不等于零，若新問題不存在最優(yōu)解或有些人工變量不等于零， 則原問題不存在最優(yōu)解；則原問題不存在最優(yōu)解；(2) 新問題最優(yōu)解中人工變量都取零，去掉人工變量即為新問題最優(yōu)解中人工變量都取零，去掉人工變量即為 原問題的最優(yōu)解。原問題的最優(yōu)解。例例2.6.2 用大用大M法求解法求解LP問題：問題： min z=4x1x2x3 s.t. 2x1+x2 +2x3=4 3x1+3x2 +x3=3 x1, x2 ,x30解：解：引入人工變量引入人工變量x4、x5，構(gòu)造新問題

44、：，構(gòu)造新問題： min z=4x1x2x3+Mx4+Mx5 s.t. 2x1+x2 +2x3+x4 =4 3x1+3x2 +x3 +x5 =3 xi0, i=1, 2, 3, 4, 5迭代迭代次數(shù)次數(shù)cB xB 價值系數(shù)價值系數(shù) c b比值比值 （0）rT （1）rT （2）rT （3）rT 4 1 1 M M x1 x2 x3 x4 x5 x4 x5MM 2 1 2 1 0 4 3 3 1 0 1 345M 14M 13M 0 0 217M=zx4 x1 M 4 0 1 4/3 1 2/3 2 3/2 3 0 3M 1/34/3M 0 4/3+5/3M 42M=z最優(yōu)解為最優(yōu)解為(0,2/

45、5,9/5)T, z* = 11/5 1 1 1/3 0 1/3 1x3 x1 1 4 0 3/4 1 3/4 1/2 3/2 2/5 0 13/4 0 1/4+M 3/2+M 7/2=z 1 5/4 0 1/4 1/2 1/2x3 x2 1 1 3/5 0 1 3/5 1/5 9/5 13/5 0 0 2/5+M 1/5+M 11/5=z 4/5 1 0 1/5 2/5 2/5+xn+1+xn+2+xn+m+m min z=c1x1+ c2x2+ cnxn s.t. a11x1+ a12x2+ a1nxn =b1 a21x1+ a22x2+ a2nxn =b2 am1x1+ am2x2+ a

46、mnxn =bm xi0, i=1,2,n b10, b20, , bm0原問題原問題引入人工變量，構(gòu)造新問題引入人工變量，構(gòu)造新問題其中其中xn+1 ，xn+2 ， xn+m為人工變量為人工變量（二）（二）兩階段法兩階段法min z=xn+1 xn+2 + xn+m第一階段：第一階段：在約束條件中引入人工變量，構(gòu)造一個典范形式的在約束條件中引入人工變量，構(gòu)造一個典范形式的 新問題，目標(biāo)函數(shù)為求所有人工變量之和的最小值。新問題，目標(biāo)函數(shù)為求所有人工變量之和的最小值。 用單純形法求解上述新問題，有兩種可能：用單純形法求解上述新問題，有兩種可能： （1）新目標(biāo)函數(shù)的最小值大于零新目標(biāo)函數(shù)的最小值大

47、于零 ( 即最優(yōu)解中至少有一個人工即最優(yōu)解中至少有一個人工 變量取正值變量取正值)，則原問題無解。，則原問題無解。 反證法：反證法： min z=xn+1 xn+2 + xn+m 如果原問題有解，這個解加上所有的人工變量，并令如果原問題有解，這個解加上所有的人工變量，并令人工變量取零值，構(gòu)成新問題的一個可行解，對應(yīng)這個可人工變量取零值，構(gòu)成新問題的一個可行解，對應(yīng)這個可行解，新問題的目標(biāo)函數(shù)值為零，導(dǎo)致矛盾！行解，新問題的目標(biāo)函數(shù)值為零，導(dǎo)致矛盾！ （2）新目標(biāo)函數(shù)的最小值為零，此時人工變量必為零。從最新目標(biāo)函數(shù)的最小值為零，此時人工變量必為零。從最 后后所得的典范形式中去掉所有人工變量，即得原問題的一個所得的典范形式中去掉所有人工變量，即得原問題的一個典范形式，為第二階段作好準(zhǔn)備；典范形式，為第二