1線性規(guī)劃-精品課件

1、第 一 章 線性規(guī)劃,Linear Programming,2024年3月25日,---第 1 章 線性規(guī)劃---,-1-,1.1 線性規(guī)劃概述（1）,線性規(guī)劃的廣泛應(yīng)用是計(jì)算機(jī)時(shí)代的產(chǎn)物。1902年，Julius Farkas 發(fā)表論文，闡述有關(guān)線性規(guī)劃問題。1938年，英國(guó)人康德進(jìn)行較詳細(xì)研究。1947年，美國(guó)學(xué)者George Dantzig（丹茨格）發(fā)明了求解線性規(guī)劃的單純形法（1951年發(fā)表），從而為線

2、性規(guī)劃的推廣奠定了基礎(chǔ)。有人認(rèn)為，求解線性規(guī)劃的單純形算法可與求解線性方程組的高斯消元法相媲美。,2024年3月25日,---第 1 章 線性規(guī)劃---,-2-,§1.1 線性規(guī)劃概述（2）,線性規(guī)劃的數(shù)學(xué)模型有三要素，從實(shí)際問題提煉成數(shù)學(xué)模型時(shí)，首先尋找需求解的未知量xj (j=1,…,n)，然后列舉三要素： 列寫與自變量（未知量）有關(guān)的若干個(gè)線性約束條件（等式或不等式）。列寫自變量xj取值限制（xj≥0，xj≤0

3、或不限）。列寫關(guān)于自變量的線性目標(biāo)函數(shù)值（極大值或極小值）。其中，前兩條稱為可行條件，最后一條稱為優(yōu)化條件。符合這三個(gè)條件的數(shù)學(xué)模型通常稱為線性規(guī)劃的一般型（general）。,2024年3月25日,---第 1 章 線性規(guī)劃---,-3-,1.1.1問題的提出 例1：某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，該兩種產(chǎn)品均需經(jīng)A、B、C、D四種不同設(shè)備上加工，按工藝資料規(guī)定，在各種不同設(shè)備上的加工時(shí)間及設(shè)備加工能力、單位產(chǎn)品利潤(rùn)如表中

4、所示。問:如何安排產(chǎn)品的生產(chǎn)計(jì)劃,才能使企業(yè)獲利最大?,1.1 一般線性規(guī)劃問題及數(shù)學(xué)模型（3）,2024年3月25日,---第 1 章 線性規(guī)劃---,-4-,建立模型：,設(shè) 產(chǎn)品的產(chǎn)量 甲??x1件 ，乙?? x2件，則,Maxz=2 x1+3 x2,,2 x1+2 x2 ? 12,x1+2 x2 ? 8,4 x1 ? 16 4

5、x2 ? 12,x1?0， x2 ?0,目標(biāo)(object) ：,限制條件(subject to )：,2024年3月25日,---第 1 章 線性規(guī)劃---,-5-,,例2、多產(chǎn)品生產(chǎn)問題（Max, ?）,生產(chǎn)甲乙電纜，1方案需銅每米2個(gè)單位鉛每米1個(gè)單位，售價(jià)6元每米，2方案需銅每米1個(gè)單位鉛每米1個(gè)單位，售價(jià)6元每米，現(xiàn)有銅10個(gè)單位，鉛8個(gè)單位，且第二種最多生產(chǎn)7米，問如何生產(chǎn)獲利最大設(shè)x1, x2 分別代表甲、乙兩種電

6、纜的生產(chǎn)量，,2024年3月25日,---第 1 章 線性規(guī)劃---,-6-,1.1.2線性規(guī)劃問題的一般數(shù)學(xué)模型,1.相關(guān)概念 （1）決策變量：指模型中要求解的未知量，簡(jiǎn)稱變量。,（2）目標(biāo)函數(shù)：指模型中要達(dá)到的目標(biāo)的數(shù)學(xué)表達(dá)式。,（3）約束條件：指模型中的變量取值所需要滿足的一切限制條件。,此三項(xiàng)內(nèi)容稱為模型結(jié)構(gòu)的三要素。,2024年3月25日,---第 1 章 線性規(guī)劃---,-7-,2.線性規(guī)劃模型的一般要求,

7、（1）變量：取值為連續(xù)的、可控的量； （2）目標(biāo)函數(shù)：線性表達(dá)式； （3）約束條件：線性的等式或者不等式。,2024年3月25日,---第 1 章 線性規(guī)劃---,-8-,3 . 線性規(guī)劃問題的一般表示方法,,（1）一般式： max z=c1x1+c2x2+………+cnxn s.t. a11x1+a12x2+………+a1nxn≤b1

8、 a21x1+a22x2+………+a2nxn≤b2 ………… ………………… am1x1+am2x2+………+amnxn≤bm x1 ,x2, ………,xn≥0 s.t.---subject to,,2024年3月25日,---第 1 章 線性規(guī)劃---,-9-,n (2) 和式： m

9、ax z=? cjxj j=1 n s.t. ? aijxj≤bi （i=1,2,……,m) j=1

10、 xj≥ 0 （j=1,2,……,n) 其中：cj---------表示目標(biāo)函數(shù)系數(shù) aij---------表示約束條件系數(shù) bi ---------表示約束右端項(xiàng),,2024年3月25日,---第 1 章 線性規(guī)劃---,-10-,n

11、 （4） 向量: max z=?cjxj n j=1 s.t ? pjxj≤b （i=1,2,……,m） j=1

12、 xj≥0 （j=1,2,……,n),,,（3） 矩陣: max z=CX s.t. AX≤b X≥0,2024年3月25日,---第 1 章 線性規(guī)劃---,-11-,4. 線性規(guī)劃模型的標(biāo)準(zhǔn)形式,（1）變量：所有變量均xj≥0 （2）目標(biāo)函數(shù)：為取“max”形式（3）約束條件

13、：全部約束方程均為“=”連接（4）約束右端項(xiàng)：bi≥ 0 非標(biāo)準(zhǔn)形式情況有變量： xj≤0 ,或xj無約束目標(biāo)函數(shù)：min 約束條件：“≤”或“≥”約束右端項(xiàng)： bi<0,2024年3月25日,---第 1 章 線性規(guī)劃---,-12-,LP的標(biāo)準(zhǔn)化：,（1）變量：若 xj?0，令 xj=-xj?，xj??0 若 xj無約束，則令 xj= xj?－xj??，xj??0，xj???0,

14、,,x,z,,,,,,,,z,zmin,z ?= - z,,z ? max,（3）約束方程：當(dāng) “?”時(shí)，引進(jìn)松弛（slack）變量+xs；如 x1+x2?3 ? x1+x2+ x3=3 當(dāng) “?”時(shí)，引進(jìn)剩余（surplus）變量 - xs；如 x1+2x2? 4 ? x1+2x2－x4=4,（2）目標(biāo)函數(shù)：若求 min z，則 令 z ? = -z，等價(jià)于求 max （z ?）即有 min

15、 z= - max （- z）,（4）約束右端項(xiàng)：當(dāng) bi < 0，則不等式兩端同乘（- 1）,2024年3月25日,---第 1 章 線性規(guī)劃---,-13-,例：將下述LP模型標(biāo)準(zhǔn)化：,obj. Min z=2x1- x2+3x3st. x1+2 x2+4x3 ? 6 3x1- 2x2+ x3 = 4 2x1- x2 - 3x3 ?5 x1 ? 0, x2無符號(hào)限制, x3 ? 0,,解

16、：設(shè) z?= - z, x2= x2? - x2? ?, x2? ?0 , x2? ? ?0, x3= - x3 ? , x3? ?0 ，x4?0, x5?0, 則有obj. Max z?= -2x1 + (x2? - x2? ? ) + 3x3 ?st. x1+2(x2? - x2? ? ) - 4x3 ?+x4=6 3x1 - 2(x2? - x2? ? ) - x3

17、?=42x1 - (x2? - x2? ?) + 3x3 ?-x5=5 x1 ?0, x2? ?0, x2? ? ?0, x3 ??0, x4 ?0, x5 ?0,,2024年3月25日,---第 1 章 線性規(guī)劃---,-14-,復(fù)習(xí)思考題：,1. 什么是模型結(jié)構(gòu)的三要素？2. 什么是線性規(guī)劃模型？能舉出線性規(guī)劃模型的例子嗎？3. LP模型中目標(biāo)函數(shù)系數(shù)、約束條件系數(shù)

18、、約束右端項(xiàng)的含義指的是什么？通常以什么符號(hào)表示？4. LP模型的一般表示方法有幾種形式？能否寫出這些形式？5. 什么是線性規(guī)劃模型的標(biāo)準(zhǔn)形式？為何提出標(biāo)準(zhǔn)形式？你能否把一個(gè)線性規(guī)劃模型的非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式？,2024年3月25日,---第 1 章 線性規(guī)劃---,-15-,1.1.3 簡(jiǎn)單線性規(guī)劃模型的建立,步驟：,（2）具體構(gòu)造模型：選擇合適的決策變量、確定目標(biāo)函數(shù)的表達(dá)式、約束條件的表達(dá)式，分析各變量取值的

19、符號(hào)限制。,（1）分析問題：確定決策內(nèi)容、要實(shí)現(xiàn)的目標(biāo)以及所受到的限制條件。,2024年3月25日,---第 1 章 線性規(guī)劃---,-16-,例1：某工廠在生產(chǎn)過程中需要使用濃度為80%的硫酸100 噸，而市面上只有濃度為30%，45%，73%，85%，92%的硫酸出售， 每噸的價(jià)格分別為400、700、1400、1900和2500元。 問：采用怎樣的購(gòu)買方案，才能使所需總費(fèi)用最??？,2024年3月25日,---第 1 章

20、 線性規(guī)劃---,-17-,模型：,設(shè) 第j 種硫酸需購(gòu)買 xj 噸，則,Minz=400x1+700x2+1400x3+1900x4+2500x5st. x1+x2+x3+x4+x5=100 30?x1+45?x2+73?x3+85 ? x4+92?x5=100?80? x1?0, x2?0, x3?0, x4?0, x5?0,,2024年3月25日,---第 1 章

21、 線性規(guī)劃---,-18-,例2：設(shè)有下面四個(gè)投資機(jī)會(huì)： 甲：在三年內(nèi)，投資人應(yīng)在每年年初投資，每年每元投資可獲利0.2元，每年取息后可重新將本息用于投資。 乙：在三年內(nèi)，投資人應(yīng)在第一年年初投資，每?jī)赡昝吭顿Y可獲利0.5元，兩年后取息，取息后可重新將本息用于投資。這種投資最多不得超過20,000元。 丙：在三年內(nèi)，投資人應(yīng)在第二年年初投資，兩年后每元投資可獲利0.6元。這種投資最多不得超過15,000元

22、。 ?。涸谌陜?nèi)，投資人應(yīng)在第三年年初投資，一年后每元投資可獲利0.4元。這種投資最多不得超過10,000元。 假定在這三年為一期的投資中，每期的開始有30,000元資金可供使用，問：采取怎樣的投資計(jì)劃，才能在第三年年底獲得最大收益？,2024年3月25日,---第 1 章 線性規(guī)劃---,-19-,模型：,設(shè) xij第 i 年投資于第 j 項(xiàng)目上的資金量，則,Maxz=0.2 (x11+x21+ x31)

23、 + 0.5 x12 + 0.6 x2 3+ 0.4 x34st. x11+ x12?30,000 x21+ x23?30,000? x12+ 0.2 x11 x31+ x34?30,000? x23 +0.2(x11+ x21)+0.5x12 x12 ?20,000 x23 ?15,000

24、 x34?10,000 xij?0, (i=1,2,3; j=1,2,3,4),,,,,,x11,x12,x21,x23,x31,x34,1,2,3,4,30,000,,,,2024年3月25日,---第 1 章 線性規(guī)劃---,-20-,例3：合理下料問題： 要制作100套鋼筋架子，每套含2.9米、2.1米、1.5米的鋼筋各一根。已知原料長(zhǎng)7.4米，問：如何下料

25、，使用料最省？,,,,,,,,,方案,下料數(shù),長(zhǎng)度,ⅠⅡⅢⅣⅤ,2.9米2.1米1.5米,121221 3123,合計(jì)(米),7.47.37.27.16.6,料頭(米),00.10.20.30.8,2024年3月25日,---第 1 章 線性規(guī)劃---,-21-,模型:,設(shè) xj ??為第j種方案用料的數(shù)量,則,Min z=0x1+0.1x2+0.2x3+0.3x4+

26、0.8x5st. x1+2x2 + x4 =100 2x3+2x4+ x5=100 3x1+ x2+2x3 +3x5=100 xj?0, (j=1,2,---,5),,思考題：目標(biāo)函數(shù)是否可以選取為 min

27、 z'=x1+x2+x3+x4+x5 ，為什 么？,2024年3月25日,---第 1 章 線性規(guī)劃---,-22-,例4：有A、B兩種產(chǎn)品，都需要經(jīng)過前、后兩到化學(xué)反應(yīng)過程。每種產(chǎn)品需要的反應(yīng)時(shí)間及其可供使用的總時(shí)間如表示。 每生產(chǎn)一個(gè)單位產(chǎn)品B的同時(shí)，會(huì)產(chǎn)生2個(gè)單位的副產(chǎn)品C，且不需外加任何費(fèi)用。副產(chǎn)品C的一部分可以出售盈利，其余的只能加以銷毀。 副產(chǎn)品C每賣出一個(gè)單位可獲

28、利3元，但是如果賣不出去，則每單位需銷毀費(fèi)用2元。預(yù)測(cè)表明，最多可售出5個(gè)單位的副產(chǎn)品C。 要求確定使利潤(rùn)最大的生產(chǎn)計(jì)劃。,2024年3月25日,---第 1 章 線性規(guī)劃---,-23-,模型：,設(shè) 產(chǎn)品的產(chǎn)量為 A?x1單位，B ? x2單位，已售出的產(chǎn)品C ? x3 單 位，銷毀的產(chǎn)品C ? x4單位，則,Max z=4x1+10x2+3x3－2x4st. 2x1+3x2?

29、16 3x1+4x2?24 2x2=x3+x4 x3? 5 xj?0, (j=1,2,3,4),,2024年3月25日,---第 1 章 線性規(guī)劃---,-24-,例5：一家晝夜服務(wù)的飯店，24小時(shí)中需要的服務(wù)員數(shù)如下表所示。每個(gè)服務(wù)員每天連續(xù)工作8小時(shí)，且在時(shí)段開始時(shí)上班。問：最少需要多少名服務(wù)員？試建立該問題的線性規(guī)劃模型。,20

30、24年3月25日,---第 1 章 線性規(guī)劃---,-25-,,模型：,設(shè) xj?第j時(shí)段開始上班工作的服務(wù)員數(shù)，則,Min z=x1+x2+x3+x4+x5+x6st. x6+x1?4 x1+x2?8 x2+x3?10 x3+x4?7 x4+x5?12 x5+x6?4 xj?0, (j=1,2,---,6),,2024

31、年3月25日,---第 1 章 線性規(guī)劃---,-26-,建立線性規(guī)劃模型要求：（1）要求決策的量是連續(xù)的、可控的量，或者是可以簡(jiǎn)化為連續(xù)取值的變量；（2）要求所解決的問題的目標(biāo)可用數(shù)值指標(biāo)描述，并且能表示成線性函數(shù)；（3）存在著多種決策方案可供選擇；（4）決策所受到的限制條件可用線性的等式或者不等式表示。,2024年3月25日,---第 1 章 線性規(guī)劃---,-27-,1.1.4線性規(guī)劃問題解的有關(guān)概念,設(shè)模型

32、 n max z=?cjxj j=1 n s.t. ?aijxj=bi （i=1,2,……,m)

33、 j=1 xj≥0 （j=1,2,……,n),,（1）可行解：滿足所有約束方程和變量符號(hào)限制條件的一組變量的取值。,（2）可行域：全部可行解的集合稱為可行域。,（3）最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解。,2024年3月25日,---第 1 章 線性規(guī)劃---,-28-,（4）基：設(shè)A為線性規(guī)劃模型約束條件系數(shù)矩陣（m ?

34、 n，m<n），而B為其m?m子矩陣，若|B|≠0，則稱B為該線性規(guī)劃模型的一個(gè)基。,（5）基變量：基中每個(gè)向量所對(duì)應(yīng)的變量稱為基變量。,（6）非基變量：模型中基變量之外的變量稱為非基變量。,（7）基本解（基解）：令模型中所有非基變量X非基=0后，由模型約束方程組 n ?aijxj =bi (i=1,2,……,m)得到的一組解。

35、 j=1,（8）基本可行解（基可行解）：在基本解中，同時(shí)又是可行解的解稱為基本可行解。,（9）可行基：對(duì)應(yīng)于基本可行解的基稱為可行基。,2024年3月25日,---第 1 章 線性規(guī)劃---,-29-,Max z=2x1+3x2 st. x1+x2≤3 x1+2x2≤4 x1,x2≥0,,,Max z=2x1+3x2 +0x3 +0x4

36、 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x4≥0,,A=,x1 x2 x3 x4,1 1 1 01 2 0 1,,可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。,設(shè),B=,1 0 0 1,,，令,，則,| B |=1≠0,,令 x1=x2 =0，則

37、 x3 =3, x4=4，X=(0,0,3,4)T,例：,x3 x4,——基變量,令,B=,,1 1 1 0,x1 x3,，則,令 x2=x4 =0，則 x3 =-1, x1=4，X=(4,0,-1,0)T,| B |=-1≠0,,——非基本可行解,——基本可行解,標(biāo)準(zhǔn)化,2024年3月25日,---第 1 章 線性規(guī)劃---,-30-,復(fù)習(xí)思考題： 1. 可行解和可行域有怎

38、樣的關(guān)系？ 2. 一個(gè)標(biāo)準(zhǔn)化LP模型，最多可有多少個(gè)基？ 3. 基本解是如何定義的？怎樣才能得到基本解？ 4. 可行解、基本解、基本可行解三者之間有什么關(guān)系？在LP模型中是否一定存在？ 5. 什么是可行基？,2024年3月25日,---第 1 章 線性規(guī)劃---,-31-,1.2線性規(guī)劃問題的圖解方法,* 利用作圖方法求解。 例

39、：max z=2x1+3x2 s.t 2x1+2x2?12 ----------① x1+2x2? 8 ----------② 4x1?16 ----------③ 4x2 ?12 ----------④ x1?0, x2?0,,2024年3月25日,---第

40、 1 章 線性規(guī)劃---,-32-,,,,,,,,,,,x1,x2,,,,,,,2,2,4,6,8,4,6,0,,,,,,,,,,,,,,①,②,④,③,,,,,Z=6,,Z=0,,(4,2),,,,Zmax,2024年3月25日,---第 1 章 線性規(guī)劃---,-33-,,,,,,,,,,A,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,A,B,,,,唯一解,無窮多解,無界解,無可行解,,?,?,?,2024年

41、3月25日,---第 1 章 線性規(guī)劃---,-34-,步驟：（1）作平面直角坐標(biāo)系，標(biāo)上刻度；（2）做出約束方程所在直線，確定可行域；（3）做出一條目標(biāo)函數(shù)等值線，判定優(yōu)化方向；（4）沿優(yōu)化方向移動(dòng)，確定與可行域相切的點(diǎn)，確定最優(yōu)解，并計(jì)算最優(yōu)值。,討論一：模型求解時(shí)，可得到如下幾種解的狀況：（1）唯一最優(yōu)解：只有一點(diǎn)為最優(yōu)解點(diǎn)，簡(jiǎn)稱唯一解；（2）無窮多最優(yōu)解：有許多點(diǎn)為最優(yōu)解點(diǎn)，簡(jiǎn)稱無窮多解；（3

42、）無界最優(yōu)解：最優(yōu)解取值無界，簡(jiǎn)稱無界解；（4）無可行解：無可行域，模型約束條件矛盾。,討論二：LP模型求解思路：（1）若LP模型可行域存在，則為一凸形集合；（2）若LP模型最優(yōu)解存在，則其應(yīng)在其可行域頂點(diǎn)上找到；（3）頂點(diǎn)與基本解、基本可行解的關(guān)系：,2024年3月25日,---第 1 章 線性規(guī)劃---,-35-,復(fù)習(xí)思考題：1. LP模型的可行域是否一定存在?2. 圖解中如何去判斷模型有唯一解、無

43、窮多解、無界解和無可行解？3. LP模型的可行域的頂點(diǎn)與什么解具有對(duì)應(yīng)關(guān)系？4.你認(rèn)為把所有的頂點(diǎn)都找出來，再通過比較目標(biāo)函數(shù)值大小的方式找出最優(yōu)解，是否是最好的算法？為什么？,2024年3月25日,---第 1 章 線性規(guī)劃---,-36-,1.3單純形法的基本原理（Simplex Method）,1.3.1 兩個(gè)概念：（1）凸集：對(duì)于集合C中任意兩點(diǎn)連線上的點(diǎn)，若也在C內(nèi)，則稱 C為凸集。,或者，任給

44、X1?C，X2 ?C，X=?X1+ (1-?)X2 ? C (0<?<1)，則C為凸集。,,,,,,,,,,,,,,,,,,,,,凸集,非凸集,2024年3月25日,---第 1 章 線性規(guī)劃---,-37-,（2）頂點(diǎn)：凸集中不成為任意兩點(diǎn)連線上的點(diǎn)，稱為凸集頂點(diǎn)。,或者， 設(shè)C為凸集，對(duì)于X?C，不存在任何X1?C，X2 ?C， 且X1≠X2，使得X=?X1+(1-?)X2?C， (0<?<1

45、)，則X為凸集頂點(diǎn)。,,,,,,,,,,,,X,X,X,X,X,2024年3月25日,---第 1 章 線性規(guī)劃---,-38-,定理1：若線性LP模型存在可行解，則可行域?yàn)橥辜?證明：設(shè) max z=CX st.AX=b X?0,,并設(shè)其可行域?yàn)镃，若X1、X2為其可行解，且X1≠X2 ，則 X1?C，X2 ?C， 即AX1=b，AX2=b，X1?0，X2?0，,又 X為X1、X2連線上一點(diǎn)，即 X

46、=?X1+(1-?)X2?C， (0<?<1)，∴ AX=?AX1+ (1-?)AX2 = ?b+ (1-?)b =b , (0<?<1)，且 X ?0， ∴ X ?C， ∴ C為凸集。,1.3.2 三個(gè)基本定理：,2024年3月25日,---第 1 章 線性規(guī)劃---,-39-,引理：線性規(guī)劃問題的可行解X=(x1, x2,······

47、,xn)T 為基本可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量線性獨(dú)立。,證：（1）必要性：X基本可行解?X的正分量所對(duì)應(yīng)的系數(shù)列向量線性獨(dú)立 可設(shè)X=(x1,x2,······,xk,0,0,······,0)T，若X為基本可行解，顯然，由基本可行解定義可知x1, x2,··&

48、#183;···,xk所對(duì)應(yīng)的系數(shù)列向量P1,P2,······,Pk應(yīng)該線性獨(dú)立。,（2）充分性： X的正分量所對(duì)應(yīng)的系數(shù)列向量線性獨(dú)立? X為基本可行解若A的秩為m，則X的正分量的個(gè)數(shù)k?m； 當(dāng)k=m時(shí)，則x1,x2,······,xk的系數(shù)列向量P1,P2,

49、3;·····,Pk恰好構(gòu)成基， ∴ X為基本可行解。 當(dāng)k<m時(shí)，則必定可再找出m-k個(gè)列向量與P1,P2,······,Pk一起構(gòu)成基， ∴ X為基本可行解。,2024年3月25日,---第 1 章 線性規(guī)劃---,-40-,證：用反證法 X非基本可行解?X非凸集頂點(diǎn)（1）

50、必要性：X非基本可行解? X非凸集頂點(diǎn) 不失一般性，設(shè)X=(x1,x2,······,xm,0,0,······,0)T，為非基本可行解，∵ X為可行解，,∴ ?pjxj=b，,j=1,n,即 ? pjxj=b ······(1),j=1

51、,m,又 X是非基本可行解， ∴ P1,P2,······,Pm線性相關(guān)，即有?1P1+?2P2+······+?mPm=0， 其中?1，?2，······，?m不全為0，兩端同乘?≠0，得??1P1+??2P2+···&#

52、183;··+??mPm=0，······（2）,定理2：線性規(guī)劃模型的基本可行解對(duì)應(yīng)其可行域的頂點(diǎn)。,2024年3月25日,---第 1 章 線性規(guī)劃---,-41-,由 (1)+(2)得 (x1+ ??1)P1+ (x2+ ??2)P2+······+ (xm+ ??m)Pm=b由 (

53、1)-(2)得 (x1 -??1)P1+ (x2 - ??2)P2+······+ (xm -??m)Pm=b,令X1=(x1+ ??1，x2+ ??2，······，xm+ ??m，0， ·····，0)T X2=(x1- ??1，x2- ??2，

54、3;·····，xm- ??m ，0，·····，0)T取?充分小,使得 xj? ??j?0， 則 X1、X2均為可行解，但 X=0.5X1+(1-0.5)X2， ∴ X是X1、X2連線上的點(diǎn)，∴ X非凸集頂點(diǎn)。,2024年3月25日,---第 1 章 線性規(guī)劃---,-42-,（2）充分性： X非凸集頂點(diǎn)? X非基本可行

55、解,設(shè)X=(x1,x2,······,xr,0,0,······,0)T為非凸集頂點(diǎn)，則必存在Y、Z兩點(diǎn)，使得,X=?Y+(1-?)Z，(0<?<1)，且Y、Z為可行解或者 xj=?yj+(1-?)zj (0<?<1)，（j=1,2,····

56、3;·,n)， yj?0，zj?0,∵ ?>0, 1-?>0 ，當(dāng)xj=0， 必有yj=zj=0,∴,? pjyj =,j=1,n,? pjyj=b ······(1),j=1,r,? pjzj =,j=1,n,? pjzj=b ······(2),j=1,r,? (yj-zj)pj=0,j=1,

57、r,,(1)-(2),得,即,(y1 - z1)P1+ (y2 - z2)P2+······+ (yr -zr)Pr=0,2024年3月25日,---第 1 章 線性規(guī)劃---,-43-,∵ Y、Z為不同兩點(diǎn)，∴ yj-zj不全為0，∴ P1,P2,······,Pr線性相關(guān)，∴ X非基本可行解。,202

58、4年3月25日,---第 1 章 線性規(guī)劃---,-44-,,,,,,,,,,,3,4,O,(3,3),C (4,2),6,6,,,2X1+2X2+X3=12,,,4X2+X5=12,,,4X1+X4=16,XA=(0,3,6,16,0)T,XO=(0,0,12,16,12)T,XB=(3,3,0,4,0)T,XC=(4,2,0,0,4)T,XD=(4,0,4,0,12)T,A,D,B,X1,X2,2024年3月25日,---第 1

59、 章 線性規(guī)劃---,-45-,z1=CX1=CX0-C?=zmax-C? ，z2=CX2=CX0+C? =zmax+C?∵ z0 = zmax ? z1 ， z0 = zmax ? z2 ，∴ z1 = z2 = z0 ，即 X1 、 X2也為最優(yōu)解，若X1、X2仍不是頂點(diǎn)，可如此遞推，直至找出一個(gè)頂點(diǎn)為最優(yōu)解。 從而，必然會(huì)找到一個(gè)基本可行解為最優(yōu)解。,定理3：若線性規(guī)劃模型有最優(yōu)解，則一定存在一個(gè)基本可行解為最優(yōu)解。

60、,證：設(shè) X0=(x10, x20,······,xn0)T 是線性規(guī)劃模型的一個(gè)最優(yōu)解，z0=zmax=CX0若X0非基本可行解，即非頂點(diǎn)，只要取?充分小，則必能找出X1= X0-??0 ，X2 = X0 +??0 ，即X1 、 X2為可行解，,2024年3月25日,---第 1 章 線性規(guī)劃---,-46-,單純形法的計(jì)算步驟：,初始基本可行解,,,新的基本可

61、行解,,,,,,,,,最優(yōu)否？,STOP,Y,N,2024年3月25日,---第 1 章 線性規(guī)劃---,-47-,1．初始基本可行解的確定：,設(shè)模型 n max z=?cjxj j=1

62、 n s.t. ?aijxj?bi （i=1,2,……,m) ???? j=1 xj?0 （j=1,2,……,n),n m max z=?cjxj + ? 0·xsi

63、 j=1 I=1 n s.t. ?aijxj+xsi=bi （i=1,2,……,m) j=1

64、 xj?0， xsi?0 （j=1,2,……,n; i=1,2, ……,m),化標(biāo)準(zhǔn)形,,,∴　初始基本可行解 X=(0,0,······,0, b1,b2,······,bm)T，,,n-m個(gè)0,2024年3月25日,---第 1 章 線性規(guī)劃---,-48-,2．從一個(gè)基本可行解向

65、另一個(gè)基本可行解轉(zhuǎn)換,不失一般性，設(shè)基本可行解X0=(x10, x20,······,xm0,0,······,0)T ，前m個(gè)分量為正值，秩為m，其系數(shù)矩陣為,P1 P2 …… Pm Pm+1 …… Pj…… Pn b 1 0 …… 0a 1,m+1 ·

66、;···· a1j ····· a 1n b1 0 1 …… 0 a 2,m+1 ····· a2j ····· a 2nb2 0 0 …… 1a m,m+1 ····

67、83; amj ····· a mn bm,……,……,……,……,……,……,……,……,……,……,……,,,∴ ? pjxj0 =,j=1,n,? pixi0=b ······(1),i=1,m,2024年3月25日,---第 1 章 線性規(guī)劃---,-49-,又P1 P2 …… Pm為一個(gè)基，任意一個(gè)非

68、基向量Pj可以以該組向量線性組合表示，即Pj = a1j P1 + a2j P2 +······+ amj Pm ，即 Pj =? aij pi ， 移項(xiàng)，兩端同乘?>0 ，有 ?(Pj-? aij pi )=0 ·········(2),i=1,m,i=1,m

69、,(1)+(2)： ?(xi 0- ?aij)Pi + ? Pj =b，取?充分小，使所有xi 0 - ?aij ?0，從而,i=1,m,X1 = (x1 0- ?a1j ,x2 0- ?a2j ,······,xm 0- ?amj ,0,······,?,·····

70、·,0)T,也是可行解。,當(dāng)取 ? = min — aij >0 = — ，則X1的前m個(gè)分量至少有一個(gè)xL1為0。,xi 0,aij,,alj,xL 0,,,i,∴ P1 , P2,······,PL-1, PL+1,······ Pm, Pj 線性無關(guān)。,2024年3月25日,

71、---第 1 章 線性規(guī)劃---,-50-,∴ X1 也為基本可行解。,3.最優(yōu)解的判別,依題義,z0 =? cjxj0 =?ci xi0,i=1,m,j=1,n,z1 =? cjxj1 =?ci(xi 0- ?aij) + cj ?,i=1,m,j=1,n,=?cixi 0+ ?(cj - ?ciaij)= z0 + ? ?j,i=1,m,i=1,m,2024年3月25日,---第 1 章 線性規(guī)劃---,-51-,因?&

72、gt;0，所以有如下結(jié)論：,(1) 對(duì)所有j，當(dāng) ?j?0 ，有z1 ? z0 ，即z0為最優(yōu)值，X0為最優(yōu)解；(2) 對(duì)所有j，當(dāng)?j?0 ，但存在某個(gè)非基變量?k=0，則對(duì)此Pk作 為新基向量得出的解X1 ，應(yīng)有z1 = z0 ，故z1 也為最優(yōu)值， 從而 X1為最優(yōu)解，且為基本可行解， ∴ X0、X1 連線上所有的點(diǎn)均為最優(yōu)解，因此該線性規(guī)劃模型 具有無窮多解；(3) 若存在某個(gè)?

73、j ? 0，但對(duì)應(yīng)aij?0，則因當(dāng) ???時(shí)，有z1 ??， ∴ 該線性規(guī)劃模型具有無界解。,2024年3月25日,---第 1 章 線性規(guī)劃---,-52-,1.4單純形法的計(jì)算及示例,1.4.1 單純形法幾何解釋---頂點(diǎn)尋優(yōu) 例： max z=2x1+3x2 max z=2x1+3x2+0x3 +0x4 s.t x1+x2?3

74、 標(biāo)準(zhǔn)化 s.t x1+x2+x3=3 x1+2x2 ? 4 ? x1+2x2+x4=4 x1?0, x2?0 xj?0, (j=1,2,3,4),,,（1）初始基本可行解的選擇：-----坐標(biāo)原點(diǎn)處,,,,令

75、 x1 =x2 =0,由 x1+x2+x3=3 x1+2x2+x4=4,（2）是否為最優(yōu)解的判定:-----計(jì)算檢驗(yàn)數(shù),若 x1↑1, 則 x3↓1, x4↓1, σ1= 2-（0?1+0 ?1）=2 σj =△z=cj-zj = cj-?ciaij ，稱 σj為檢驗(yàn)數(shù)。,x3=3 -(x1+x2) x4=4 -(x1+2x2),解得 X=( 0,0,3,4 )