版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
1、第 一 章 線性規(guī)劃,Linear Programming,2024年3月25日,---第 1 章 線性規(guī)劃---,-1-,1.1 線性規(guī)劃概述(1),線性規(guī)劃的廣泛應用是計算機時代的產(chǎn)物。1902年,Julius Farkas 發(fā)表論文,闡述有關線性規(guī)劃問題。1938年,英國人康德進行較詳細研究。1947年,美國學者George Dantzig(丹茨格)發(fā)明了求解線性規(guī)劃的單純形法(1951年發(fā)表),從而為線
2、性規(guī)劃的推廣奠定了基礎。有人認為,求解線性規(guī)劃的單純形算法可與求解線性方程組的高斯消元法相媲美。,2024年3月25日,---第 1 章 線性規(guī)劃---,-2-,§1.1 線性規(guī)劃概述(2),線性規(guī)劃的數(shù)學模型有三要素,從實際問題提煉成數(shù)學模型時,首先尋找需求解的未知量xj (j=1,…,n),然后列舉三要素: 列寫與自變量(未知量)有關的若干個線性約束條件(等式或不等式)。列寫自變量xj取值限制(xj≥0,xj≤0
3、或不限)。列寫關于自變量的線性目標函數(shù)值(極大值或極小值)。其中,前兩條稱為可行條件,最后一條稱為優(yōu)化條件。符合這三個條件的數(shù)學模型通常稱為線性規(guī)劃的一般型(general)。,2024年3月25日,---第 1 章 線性規(guī)劃---,-3-,1.1.1問題的提出 例1:某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品,該兩種產(chǎn)品均需經(jīng)A、B、C、D四種不同設備上加工,按工藝資料規(guī)定,在各種不同設備上的加工時間及設備加工能力、單位產(chǎn)品利潤如表中
4、所示。問:如何安排產(chǎn)品的生產(chǎn)計劃,才能使企業(yè)獲利最大?,1.1 一般線性規(guī)劃問題及數(shù)學模型(3),2024年3月25日,---第 1 章 線性規(guī)劃---,-4-,建立模型:,設 產(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,目標(object) :,限制條件(subject to ):,2024年3月25日,---第 1 章 線性規(guī)劃---,-5-,,例2、多產(chǎn)品生產(chǎn)問題(Max, ?),生產(chǎn)甲乙電纜,1方案需銅每米2個單位鉛每米1個單位,售價6元每米,2方案需銅每米1個單位鉛每米1個單位,售價6元每米,現(xiàn)有銅10個單位,鉛8個單位,且第二種最多生產(chǎn)7米,問如何生產(chǎn)獲利最大設x1, x2 分別代表甲、乙兩種電
6、纜的生產(chǎn)量,,2024年3月25日,---第 1 章 線性規(guī)劃---,-6-,1.1.2線性規(guī)劃問題的一般數(shù)學模型,1.相關概念 (1)決策變量:指模型中要求解的未知量,簡稱變量。,(2)目標函數(shù):指模型中要達到的目標的數(shù)學表達式。,(3)約束條件:指模型中的變量取值所需要滿足的一切限制條件。,此三項內(nèi)容稱為模型結構的三要素。,2024年3月25日,---第 1 章 線性規(guī)劃---,-7-,2.線性規(guī)劃模型的一般要求,
7、(1)變量:取值為連續(xù)的、可控的量; (2)目標函數(shù):線性表達式; (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---------表示目標函數(shù)系數(shù) aij---------表示約束條件系數(shù) bi ---------表示約束右端項,,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ī)劃模型的標準形式,(1)變量:所有變量均xj≥0 (2)目標函數(shù):為取“max”形式(3)約束條件
13、:全部約束方程均為“=”連接(4)約束右端項:bi≥ 0 非標準形式情況有變量: xj≤0 ,或xj無約束目標函數(shù):min 約束條件:“≤”或“≥”約束右端項: bi<0,2024年3月25日,---第 1 章 線性規(guī)劃---,-12-,LP的標準化:,(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)約束方程:當 “?”時,引進松弛(slack)變量+xs;如 x1+x2?3 ? x1+x2+ x3=3 當 “?”時,引進剩余(surplus)變量 - xs;如 x1+2x2? 4 ? x1+2x2-x4=4,(2)目標函數(shù):若求 min z,則 令 z ? = -z,等價于求 max (z ?)即有 min
15、 z= - max (- z),(4)約束右端項:當 bi < 0,則不等式兩端同乘(- 1),2024年3月25日,---第 1 章 線性規(guī)劃---,-13-,例:將下述LP模型標準化:,obj. Min z=2x1- x2+3x3st. x1+2 x2+4x3 ? 6 3x1- 2x2+ x3 = 4 2x1- x2 - 3x3 ?5 x1 ? 0, x2無符號限制, x3 ? 0,,解
16、:設 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-,復習思考題:,1. 什么是模型結構的三要素?2. 什么是線性規(guī)劃模型?能舉出線性規(guī)劃模型的例子嗎?3. LP模型中目標函數(shù)系數(shù)、約束條件系數(shù)
18、、約束右端項的含義指的是什么?通常以什么符號表示?4. LP模型的一般表示方法有幾種形式?能否寫出這些形式?5. 什么是線性規(guī)劃模型的標準形式?為何提出標準形式?你能否把一個線性規(guī)劃模型的非標準形式轉(zhuǎn)化為標準形式?,2024年3月25日,---第 1 章 線性規(guī)劃---,-15-,1.1.3 簡單線性規(guī)劃模型的建立,步驟:,(2)具體構造模型:選擇合適的決策變量、確定目標函數(shù)的表達式、約束條件的表達式,分析各變量取值的
19、符號限制。,(1)分析問題:確定決策內(nèi)容、要實現(xiàn)的目標以及所受到的限制條件。,2024年3月25日,---第 1 章 線性規(guī)劃---,-16-,例1:某工廠在生產(chǎn)過程中需要使用濃度為80%的硫酸100 噸,而市面上只有濃度為30%,45%,73%,85%,92%的硫酸出售, 每噸的價格分別為400、700、1400、1900和2500元。 問:采用怎樣的購買方案,才能使所需總費用最?。?2024年3月25日,---第 1 章
20、 線性規(guī)劃---,-17-,模型:,設 第j 種硫酸需購買 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:設有下面四個投資機會: 甲:在三年內(nèi),投資人應在每年年初投資,每年每元投資可獲利0.2元,每年取息后可重新將本息用于投資。 乙:在三年內(nèi),投資人應在第一年年初投資,每兩年每元投資可獲利0.5元,兩年后取息,取息后可重新將本息用于投資。這種投資最多不得超過20,000元。 丙:在三年內(nèi),投資人應在第二年年初投資,兩年后每元投資可獲利0.6元。這種投資最多不得超過15,000元
22、。 ?。涸谌陜?nèi),投資人應在第三年年初投資,一年后每元投資可獲利0.4元。這種投資最多不得超過10,000元。 假定在這三年為一期的投資中,每期的開始有30,000元資金可供使用,問:采取怎樣的投資計劃,才能在第三年年底獲得最大收益?,2024年3月25日,---第 1 章 線性規(guī)劃---,-19-,模型:,設 xij第 i 年投資于第 j 項目上的資金量,則,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米的鋼筋各一根。已知原料長7.4米,問:如何下料
25、,使用料最?。?,,,,,,,,方案,下料數(shù),長度,ⅠⅡⅢⅣⅤ,2.9米2.1米1.5米,121221 3123,合計(米),7.47.37.27.16.6,料頭(米),00.10.20.30.8,2024年3月25日,---第 1 章 線性規(guī)劃---,-21-,模型:,設 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),,思考題:目標函數(shù)是否可以選取為 min
27、 z'=x1+x2+x3+x4+x5 ,為什 么?,2024年3月25日,---第 1 章 線性規(guī)劃---,-22-,例4:有A、B兩種產(chǎn)品,都需要經(jīng)過前、后兩到化學反應過程。每種產(chǎn)品需要的反應時間及其可供使用的總時間如表示。 每生產(chǎn)一個單位產(chǎn)品B的同時,會產(chǎn)生2個單位的副產(chǎn)品C,且不需外加任何費用。副產(chǎn)品C的一部分可以出售盈利,其余的只能加以銷毀。 副產(chǎn)品C每賣出一個單位可獲
28、利3元,但是如果賣不出去,則每單位需銷毀費用2元。預測表明,最多可售出5個單位的副產(chǎn)品C。 要求確定使利潤最大的生產(chǎn)計劃。,2024年3月25日,---第 1 章 線性規(guī)劃---,-23-,模型:,設 產(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:一家晝夜服務的飯店,24小時中需要的服務員數(shù)如下表所示。每個服務員每天連續(xù)工作8小時,且在時段開始時上班。問:最少需要多少名服務員?試建立該問題的線性規(guī)劃模型。,20
30、24年3月25日,---第 1 章 線性規(guī)劃---,-25-,,模型:,設 xj?第j時段開始上班工作的服務員數(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ù)的、可控的量,或者是可以簡化為連續(xù)取值的變量;(2)要求所解決的問題的目標可用數(shù)值指標描述,并且能表示成線性函數(shù);(3)存在著多種決策方案可供選擇;(4)決策所受到的限制條件可用線性的等式或者不等式表示。,2024年3月25日,---第 1 章 線性規(guī)劃---,-27-,1.1.4線性規(guī)劃問題解的有關概念,設模型
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)可行解:滿足所有約束方程和變量符號限制條件的一組變量的取值。,(2)可行域:全部可行解的集合稱為可行域。,(3)最優(yōu)解:使目標函數(shù)達到最優(yōu)值的可行解。,2024年3月25日,---第 1 章 線性規(guī)劃---,-28-,(4)基:設A為線性規(guī)劃模型約束條件系數(shù)矩陣(m ?
34、 n,m<n),而B為其m?m子矩陣,若|B|≠0,則稱B為該線性規(guī)劃模型的一個基。,(5)基變量:基中每個向量所對應的變量稱為基變量。,(6)非基變量:模型中基變量之外的變量稱為非基變量。,(7)基本解(基解):令模型中所有非基變量X非基=0后,由模型約束方程組 n ?aijxj =bi (i=1,2,……,m)得到的一組解。
35、 j=1,(8)基本可行解(基可行解):在基本解中,同時又是可行解的解稱為基本可行解。,(9)可行基:對應于基本可行解的基稱為可行基。,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 等。,設,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,,——非基本可行解,——基本可行解,標準化,2024年3月25日,---第 1 章 線性規(guī)劃---,-30-,復習思考題: 1. 可行解和可行域有怎
38、樣的關系? 2. 一個標準化LP模型,最多可有多少個基? 3. 基本解是如何定義的?怎樣才能得到基本解? 4. 可行解、基本解、基本可行解三者之間有什么關系?在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)作平面直角坐標系,標上刻度;(2)做出約束方程所在直線,確定可行域;(3)做出一條目標函數(shù)等值線,判定優(yōu)化方向;(4)沿優(yōu)化方向移動,確定與可行域相切的點,確定最優(yōu)解,并計算最優(yōu)值。,討論一:模型求解時,可得到如下幾種解的狀況:(1)唯一最優(yōu)解:只有一點為最優(yōu)解點,簡稱唯一解;(2)無窮多最優(yōu)解:有許多點為最優(yōu)解點,簡稱無窮多解;(3
42、)無界最優(yōu)解:最優(yōu)解取值無界,簡稱無界解;(4)無可行解:無可行域,模型約束條件矛盾。,討論二:LP模型求解思路:(1)若LP模型可行域存在,則為一凸形集合;(2)若LP模型最優(yōu)解存在,則其應在其可行域頂點上找到;(3)頂點與基本解、基本可行解的關系:,2024年3月25日,---第 1 章 線性規(guī)劃---,-35-,復習思考題:1. LP模型的可行域是否一定存在?2. 圖解中如何去判斷模型有唯一解、無
43、窮多解、無界解和無可行解?3. LP模型的可行域的頂點與什么解具有對應關系?4.你認為把所有的頂點都找出來,再通過比較目標函數(shù)值大小的方式找出最優(yōu)解,是否是最好的算法?為什么?,2024年3月25日,---第 1 章 線性規(guī)劃---,-36-,1.3單純形法的基本原理(Simplex Method),1.3.1 兩個概念:(1)凸集:對于集合C中任意兩點連線上的點,若也在C內(nèi),則稱 C為凸集。,或者,任給
44、X1?C,X2 ?C,X=?X1+ (1-?)X2 ? C (0<?<1),則C為凸集。,,,,,,,,,,,,,,,,,,,,,凸集,非凸集,2024年3月25日,---第 1 章 線性規(guī)劃---,-37-,(2)頂點:凸集中不成為任意兩點連線上的點,稱為凸集頂點。,或者, 設C為凸集,對于X?C,不存在任何X1?C,X2 ?C, 且X1≠X2,使得X=?X1+(1-?)X2?C, (0<?<1
45、),則X為凸集頂點。,,,,,,,,,,,,X,X,X,X,X,2024年3月25日,---第 1 章 線性規(guī)劃---,-38-,定理1:若線性LP模型存在可行解,則可行域為凸集。,證明:設 max z=CX st.AX=b X?0,,并設其可行域為C,若X1、X2為其可行解,且X1≠X2 ,則 X1?C,X2 ?C, 即AX1=b,AX2=b,X1?0,X2?0,,又 X為X1、X2連線上一點,即 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 三個基本定理:,2024年3月25日,---第 1 章 線性規(guī)劃---,-39-,引理:線性規(guī)劃問題的可行解X=(x1, x2,······
47、,xn)T 為基本可行解的充要條件是X的正分量所對應的系數(shù)列向量線性獨立。,證:(1)必要性:X基本可行解?X的正分量所對應的系數(shù)列向量線性獨立 可設X=(x1,x2,······,xk,0,0,······,0)T,若X為基本可行解,顯然,由基本可行解定義可知x1, x2,··&
48、#183;···,xk所對應的系數(shù)列向量P1,P2,······,Pk應該線性獨立。,(2)充分性: X的正分量所對應的系數(shù)列向量線性獨立? X為基本可行解若A的秩為m,則X的正分量的個數(shù)k?m; 當k=m時,則x1,x2,······,xk的系數(shù)列向量P1,P2,
49、3;·····,Pk恰好構成基, ∴ X為基本可行解。 當k<m時,則必定可再找出m-k個列向量與P1,P2,······,Pk一起構成基, ∴ X為基本可行解。,2024年3月25日,---第 1 章 線性規(guī)劃---,-40-,證:用反證法 X非基本可行解?X非凸集頂點(1)
50、必要性:X非基本可行解? X非凸集頂點 不失一般性,設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線性相關,即有?1P1+?2P2+······+?mPm=0, 其中?1,?2,······,?m不全為0,兩端同乘?≠0,得??1P1+??2P2+···
52、183;··+??mPm=0,······(2),定理2:線性規(guī)劃模型的基本可行解對應其可行域的頂點。,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連線上的點,∴ X非凸集頂點。,2024年3月25日,---第 1 章 線性規(guī)劃---,-42-,(2)充分性: X非凸集頂點? X非基本可行
55、解,設X=(x1,x2,······,xr,0,0,······,0)T為非凸集頂點,則必存在Y、Z兩點,使得,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 ,當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為不同兩點,∴ yj-zj不全為0,∴ P1,P2,······,Pr線性相關,∴ 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仍不是頂點,可如此遞推,直至找出一個頂點為最優(yōu)解。 從而,必然會找到一個基本可行解為最優(yōu)解。,定理3:若線性規(guī)劃模型有最優(yōu)解,則一定存在一個基本可行解為最優(yōu)解。
60、,證:設 X0=(x10, x20,······,xn0)T 是線性規(guī)劃模型的一個最優(yōu)解,z0=zmax=CX0若X0非基本可行解,即非頂點,只要取?充分小,則必能找出X1= X0-??0 ,X2 = X0 +??0 ,即X1 、 X2為可行解,,2024年3月25日,---第 1 章 線性規(guī)劃---,-46-,單純形法的計算步驟:,初始基本可行解,,,新的基本可
61、行解,,,,,,,,,最優(yōu)否?,STOP,Y,N,2024年3月25日,---第 1 章 線性規(guī)劃---,-47-,1.初始基本可行解的確定:,設模型 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),化標準形,,,∴ 初始基本可行解 X=(0,0,······,0, b1,b2,······,bm)T,,,n-m個0,2024年3月25日,---第 1 章 線性規(guī)劃---,-48-,2.從一個基本可行解向
65、另一個基本可行解轉(zhuǎn)換,不失一般性,設基本可行解X0=(x10, x20,······,xm0,0,······,0)T ,前m個分量為正值,秩為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為一個基,任意一個非
68、基向量Pj可以以該組向量線性組合表示,即Pj = a1j P1 + a2j P2 +······+ amj Pm ,即 Pj =? aij pi , 移項,兩端同乘?>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,也是可行解。,當取 ? = min — aij >0 = — ,則X1的前m個分量至少有一個xL1為0。,xi 0,aij,,alj,xL 0,,,i,∴ P1 , P2,······,PL-1, PL+1,······ Pm, Pj 線性無關。,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,所以有如下結論:,(1) 對所有j,當 ?j?0 ,有z1 ? z0 ,即z0為最優(yōu)值,X0為最優(yōu)解;(2) 對所有j,當?j?0 ,但存在某個非基變量?k=0,則對此Pk作 為新基向量得出的解X1 ,應有z1 = z0 ,故z1 也為最優(yōu)值, 從而 X1為最優(yōu)解,且為基本可行解, ∴ X0、X1 連線上所有的點均為最優(yōu)解,因此該線性規(guī)劃模型 具有無窮多解;(3) 若存在某個?
73、j ? 0,但對應aij?0,則因當 ???時,有z1 ??, ∴ 該線性規(guī)劃模型具有無界解。,2024年3月25日,---第 1 章 線性規(guī)劃---,-52-,1.4單純形法的計算及示例,1.4.1 單純形法幾何解釋---頂點尋優(yōu) 例: max z=2x1+3x2 max z=2x1+3x2+0x3 +0x4 s.t x1+x2?3
74、 標準化 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)初始基本可行解的選擇:-----坐標原點處,,,,令
75、 x1 =x2 =0,由 x1+x2+x3=3 x1+2x2+x4=4,(2)是否為最優(yōu)解的判定:-----計算檢驗數(shù),若 x1↑1, 則 x3↓1, x4↓1, σ1= 2-(0?1+0 ?1)=2 σj =△z=cj-zj = cj-?ciaij ,稱 σj為檢驗數(shù)。,x3=3 -(x1+x2) x4=4 -(x1+2x2),解得 X=( 0,0,3,4 )
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
評論
0/150
提交評論