第1講線性規(guī)劃及單純形法課件

第1講

線性規(guī)劃及單純形法

山東輕工業(yè)學(xué)院數(shù)理學(xué)院李彬

E-mail:ribbenlee@126.com

telephonenumber1運(yùn)籌帷幄之中決勝千里之外線性規(guī)劃LinearProgramming數(shù)學(xué)建模課件.2§1線性規(guī)劃問題及模型§2圖解法§3單純形方法§4線性規(guī)劃應(yīng)用舉例分析.3§1問題的提出例1.某工廠在計(jì)劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表：問題：工廠應(yīng)分別生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠獲利最多？線性規(guī)劃模型：目標(biāo)函數(shù)：Maxz=50x1+100x2約束條件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0.4線性規(guī)劃的組成要素：目標(biāo)函數(shù)MaxF或MinF約束條件s.t.(subjectto)滿足于決策變量用符號來表示可控制的因素建模步驟1.理解要解決的問題，了解解題的目標(biāo)和條件；2.定義決策變量（x1，x2，…，xn），每一組值表示一個方案；3.用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件。.5一般形式目標(biāo)函數(shù)約束條件.6可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個特點(diǎn)：

-目標(biāo)最大化；-約束為等式；-決策變量均非負(fù)；-右端項(xiàng)非負(fù)。.7注釋.8規(guī)范形式.9標(biāo)準(zhǔn)形式.10概念.11模型轉(zhuǎn)換目標(biāo)轉(zhuǎn)換變量轉(zhuǎn)換.12約束轉(zhuǎn)換不等式變等式不等式變不等式等式變不等式.13不等式變等式松弛變量剩余變量.14不等式變不等式.15

例1

把問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式.16對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。下面通過例2詳細(xì)講解其方法?！?圖解法例2.目標(biāo)函數(shù)：Maxz=50x1+100x2約束條件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E).17（1）畫出線性規(guī)劃問題的可行域，如圖所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖1.18（2）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動等值線，當(dāng)移動到B點(diǎn)時，z在可行域內(nèi)實(shí)現(xiàn)了最大化。得到最優(yōu)解：x1=50，x2=250，最優(yōu)目標(biāo)值z=27500x1x2z=20000=50x1+100x2圖2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE.19圖解法步驟在平面上建立直角坐標(biāo)系；圖示約束條件；找出可行域；圖示目標(biāo)函數(shù)和尋找最優(yōu)解。.20例3某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購進(jìn)125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時間也是不同的，加工每噸A原料需要2個小時，加工每噸B原料需要1小時，而公司總共有600個加工小時。又知道每噸A原料的價格為2萬元，每噸B原料的價格為3萬元，試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買A，B兩種原料，使得購進(jìn)成本最低？.21解：目標(biāo)函數(shù)：Minf=2x1+3x2約束條件：s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0采用圖解法。如下圖：得Q點(diǎn)坐標(biāo)（250，100）為最優(yōu)解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q.22重要結(jié)論：如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點(diǎn)對應(yīng)一個最優(yōu)解；無窮多個最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)閙axz=50x1+50x2，則線段BC上的所有點(diǎn)都代表了最優(yōu)解；無界解。即可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件；無可行解。若在例1的數(shù)學(xué)模型中再增加一個約束條件4x1+3x2≥1200，則可行域?yàn)榭沼?，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。.23§3單純形方法單純形法的基本思路和原理單純形法的表格形式求目標(biāo)函數(shù)值最小的線性規(guī)劃的問題的

單純形表解法.24可行域的幾何結(jié)構(gòu)基本假設(shè)凸集可行域的凸性.25基本假設(shè).26凸集.27問題.28線性規(guī)劃問題解的特點(diǎn)若線性規(guī)劃問題存在唯一的最優(yōu)解，那么它必定在頂點(diǎn)上（基本可行解）。若線性規(guī)劃問題存在多個最優(yōu)解，那么必有幾個相鄰的頂點(diǎn)是最優(yōu)解，其它最優(yōu)解可以表示成這幾個頂點(diǎn)的凸組合。若一個頂點(diǎn)的目標(biāo)函數(shù)值比它的相鄰定點(diǎn)的目標(biāo)函數(shù)值要好的話，它就是最優(yōu)解。.291單純形法的基本思路和原理單純形法的基本思路：從可行域中某一個頂點(diǎn)開始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是,則再找另一個使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代，再判斷此點(diǎn)是否是最優(yōu)解。直到找到一個頂點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。例1在加上松弛變量之后我們可得到標(biāo)準(zhǔn)型如下：目標(biāo)函數(shù)：max50x1+100x2約束條件：x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250.xj≥0（j=1，2）,sj≥0（j=1，2,3）.30它的系數(shù)矩陣,

其中pj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個數(shù)n，為了找到一個初始基本可行解，先介紹以下幾個線性規(guī)劃的基本概念。

基：已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中m×m階非奇異子矩陣（即可逆矩陣），則稱B是線性規(guī)劃問題中的一個基。基向量：基B中的一列即稱為一個基向量?；鵅中共有m個基向量。非基向量：在A中除了基B之外的一列則稱之為基B的非基向量?；兞浚号c基向量pi相應(yīng)的變量xi叫基變量，基變量有m個。.31非基變量：與非基向量pj相應(yīng)的變量xj叫非基變量，非基變量有n－m個。由線性代數(shù)的知識知道，如果我們在約束方程組系數(shù)矩陣中找到一個基，令這個基的非基變量為零，再求解這個m元線性方程組就可得到唯一的解了，這個解我們稱之為線性規(guī)劃的基本解。在此例中我們不妨找到了

為A的一個基，令這個基的

非基變量x１，s2為零。這時約束方程就變?yōu)榛兞康募s束方程：

.32x2+s1＝300，x2=400，x2+s3=250.求解得到此線性規(guī)劃的一個基本解：x1=0，x2=400，s1=－100，s2=0，s3=－150由于在這個基本解中s1=－100，s3=－150，不滿足該線性規(guī)劃s1≥0，s3≥0的約束條件，顯然不是此線性規(guī)劃的可行解，一個基本解可以是可行解，也可以是非可行解，它們之間的主要區(qū)別在于其所有變量的解是否滿足非負(fù)的條件。我們把滿足非負(fù)條件的一個基本解叫做基本可行解，并把這樣的基叫做可行基。.33一般來說判斷一個基是否是可行基，只有在求出其基本解以后，當(dāng)其基本解所有變量的解都是大于等于零，才能斷定這個解是基本可行解，這個基是可行基。那么我們能否在求解之前，就找到一個可行基呢？也就是說我們找到的一個基能保證在求解之后得到的解一定是基本可行解呢？由于在線性規(guī)劃的標(biāo)準(zhǔn)型中要求bj都大于等于零，如果我們能找到一個基是單位矩陣，或者說一個基是由單位矩陣的各列向量所組成（至于各列向量的前后順序是無關(guān)緊要的事）例如，那么顯然所求得的基本解一定是基本可行解，這個單位矩陣或由單位矩陣各列向量組成的基一定是可行基。實(shí)際上這個基本可行解中的各個變量或等于某個bj或等于零。

.34在本例題中我們就找到了一個基是單位矩陣。在第一次找可行基時，所找到的基或?yàn)閱挝痪仃嚮驗(yàn)橛蓡挝痪仃嚨母髁邢蛄克M成，稱之為初始可行基，其相應(yīng)的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將構(gòu)造初始可行基，具體做法在以后詳細(xì)講述。.35基本可行解定義.36.37二、最優(yōu)性檢驗(yàn)所謂最優(yōu)性檢驗(yàn)就是判斷已求得的基本可行解是否是最優(yōu)解。1.最優(yōu)性檢驗(yàn)的依據(jù)——檢驗(yàn)數(shù)σj一般來說目標(biāo)函數(shù)中既包括基變量，又包括非基變量?，F(xiàn)在我們要求只用非基變量來表示目標(biāo)函數(shù)，這只要在約束等式中通過移項(xiàng)等處理就可以用非基變量來表示基變量，然后用非基變量的表示式代替目標(biāo)函數(shù)中基變量，這樣目標(biāo)函數(shù)中只含有非基變量了，或者說目標(biāo)函數(shù)中基變量的系數(shù)都為零了。此時目標(biāo)函數(shù)中所有變量的系數(shù)即為各變量的檢驗(yàn)數(shù)，把變量xi的檢驗(yàn)數(shù)記為σi。顯然所有基變量的檢驗(yàn)數(shù)必為零。在本例題中目標(biāo)函數(shù)為50x1+100x2。由于初始可行解中x1，x2為非基變量，所以此目標(biāo)函數(shù)已經(jīng)用非基變量表示了，不需要再代換出基變量了。這樣我們可知σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。.38設(shè)線性規(guī)劃模型為.39令基為B，并作相應(yīng)的矩陣分割，從約束條件得代入目標(biāo)函數(shù)得典式.40令則目標(biāo)函數(shù)可寫成所以可用判斷是否最優(yōu)解，它叫做檢驗(yàn)數(shù)。.41其中：.422.最優(yōu)解判別定理

對于求最大目標(biāo)函數(shù)的問題中，對于某個基本可行解，如果所有檢驗(yàn)數(shù)≤0，則這個基本可行解是最優(yōu)解。下面我們用通俗的說法來解釋最優(yōu)解判別定理。設(shè)用非基變量表示的目標(biāo)函數(shù)為如下形式

由于所有的xj的取值范圍為大于等于零，當(dāng)所有的都小于等于零時，可知是一個小于等于零的數(shù)，要使z的值最大，顯然只有為零。我們把這些xj取為非基變量(即令這些xj的值為零)，所求得的基本可行解就使目標(biāo)函數(shù)值最大為z0。**對于求目標(biāo)函數(shù)最小值的情況，只需把≤0改為≥0.43三、基變換通過檢驗(yàn)，我們知道這個初始基本可行解不是最優(yōu)解。下面介紹如何進(jìn)行基變換找到一個新的可行基，具體的做法是從可行基中換一個列向量，得到一個新的可行基，使得求解得到的新的基本可行解，其目標(biāo)函數(shù)值更優(yōu)。為了換基就要確定換入變量與換出變量。1.入基變量的確定從最優(yōu)解判別定理知道，當(dāng)某個σj＞0時，非基變量xj變?yōu)榛兞坎蝗×阒悼梢允鼓繕?biāo)函數(shù)值增大，故我們要選基檢驗(yàn)數(shù)大于0的非基變量換到基變量中去（稱之為入基變量）。若有兩個以上的σj＞0，則為了使目標(biāo)函數(shù)增加得更大些，一般選其中的σj最大者的非基變量為入基變量，在本例題中σ2=100是檢驗(yàn)數(shù)中最大的正數(shù)，故選x2為入基變量。.442.出基變量的確定在確定了x2為入基變量之后，我們要在原來的3個基變量s1，s2，s3中確定一個出基變量，也就是確定哪一個基變量變成非基變量呢？

如果把s3作為出基變量，則新的基變量為x2，s1，s2，因?yàn)榉腔兞縳1=s3=0，我們也可以從下式：x2+s1=300，x2+s2=400，x2=250，求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。因?yàn)榇私鉂M足非負(fù)條件，是基本可行解，故s3可以確定為出基變量。能否在求出基本解以前來確定出基變量呢？以下就來看在找出了初始基本可行解和確定了入基變量之后，怎么樣的基變量可以確定為出基變量呢？或者說出基變量要具有什么條件呢？

.45我們把確定出基變量的方法概括如下：把已確定的入基變量在各約束方程中的右端向量正的系數(shù)除以其所在約束方程中的常數(shù)項(xiàng)的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。這樣在下一步迭代的矩陣變換中可以確保新得到的bj值都大于等于零。在本例題中約束方程為

在第二步中已經(jīng)知道x2為入基變量，我們把各約束方程中x2的為正的系數(shù)除對應(yīng)的常量，得.46其中的值最小，所以可以知道在原基變量中系數(shù)向量為

的基變量s3為出基變量，這樣可知x2，s1，s2為基變量，x1，s3為非基變量。令非基變量為零，得x2+s1=300,x2+s2=400,x2=250.求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150.這時目標(biāo)函數(shù)值為50x1+100x2=50×0+100×250=25000。顯然比初始基本可行解x1=0,x2=0,s1=300,s3=250時的目標(biāo)函數(shù)值為0要好得多。下面我們再進(jìn)行檢驗(yàn)其最優(yōu)性，如果不是最優(yōu)解還要繼續(xù)進(jìn)行基變換，直至找到最優(yōu)解，或者能夠判斷出線性規(guī)劃無最優(yōu)解為止。.47單純形法的表格形式是把用單純形法求出基本可行解、檢驗(yàn)其最優(yōu)性、迭代某步驟都用表格的方式來計(jì)算求出，其表格的形式有些像增廣矩陣，而其計(jì)算的方法也大體上使用矩陣的行的初等變換。以下用單純形表格來求解第二章的例1。max50x1+100x2+0·s1+0·s2+0·s3.x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250，x1,x2,s1,s2,s3≥0.把上面的數(shù)據(jù)填入如下的單純形表格：.48按照線性規(guī)劃模型在表中填入相對應(yīng)的值，如上表所示；在上表中有一個m*m的單位矩陣，對應(yīng)的基變量為s1,s2,s3；在zj行中填入第j列與cB列中對應(yīng)的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位數(shù)填入0；在行中填入cj-zj所得的值，如；z表示把初始基本可行解代入目標(biāo)函數(shù)求得的目標(biāo)函數(shù)值，即b列*cB列；初始基本可行解為s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此確定s3為出基變量；由于，因此確定x2為入基變量。出基變量所在行，入基變量所在列的交匯處為主元，這里是a32=1，在表中畫圈以示區(qū)別。迭代次數(shù)基變量cBx1x2s1s2s3b比值Bi/ai2501000000s1s2s3000111002101001001300400250300/1400/1250/150100000z=0.49以下進(jìn)行第一次迭代，其變量為x2,s1,s2,通過矩陣行的初等變換，求出一個新的基本可行解，具體的做法用行的初等變換使得x2的系數(shù)向量p2變換成單位向量，由于主元在p2的第3分量上，所以這個單位向量是也就是主元素變成1。這樣我們又得到的第1次迭代的單純表如下所示。在上表中第3個基變量s1已被x2代替，故基變量列中的第3個基變量應(yīng)變?yōu)閤2。由于第0次迭代表中的主元a32已經(jīng)為1，因此第3行不變。為了使第1行的a12為0，只需把第3行*(-1)加到第1行即可。同樣可以求得第2行。求得第1次迭代的基本可行解為s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.迭代次數(shù)基變量cBx1x2s1s2s3b比值bi/aij501000001s1s2x2001001010-12001-1010015015025050/1150/2—50000-10025000.50從上表可以看出，第一次迭代的，因此不是最優(yōu)解。設(shè)x1為入基變量，從此值可知b1/a11=50為最小正數(shù)，因此，s1為出基變量，a11為主元，繼續(xù)迭代如下表所示。從上表中可知第二次迭代得到的基本可行解為x1=50,x2=250,s1=0,s2=50,s3=0,這時z=27500。由于檢驗(yàn)數(shù)都<0，因此所求得的基本可行解為最優(yōu)解，z=27500為最優(yōu)目標(biāo)函數(shù)值。實(shí)際上，我們可以連續(xù)地使用一個單純形表，不必一次迭代重畫一個表頭。迭代次數(shù)基變量cBx1x2s1s2s3b比值bi/aij501000002x1s2x25001001010-100-211010015050250

00-500-5027500.51算法步驟.52單純形表.53特例.7思路總結(jié)：.58例1模型與求解s.t.,數(shù)學(xué)模型.59標(biāo)準(zhǔn)化.60單純形表法求解430000001600250040025122.50100010001800500400043000.61第一次換基迭代4300000480050040000122.50100010-2-51400200160003000.62第二次換基迭代43000034400200400001010100-0.80.402-212004002200000-1.22.63第三次換基迭代：最優(yōu)解430000342006002000010100.51-0.5-0.4-0.40.4100260000-1-0.40.64例0靈敏度分析研究對象:.71改變價值向量改變右端向量改變矩陣增加新變量增加新的不等式約束增加新的等式約束.72概況信息的不確定性

信息的變化：

價值向量—市場變化

右端向量—資源變化系數(shù)矩陣—技術(shù)進(jìn)步

認(rèn)知的誤差分析方法

靜態(tài)分析-比較靜態(tài)分析-動態(tài)分析.73C的變化只影響檢驗(yàn)數(shù)（對偶問題的解），不影響原問題的基本解；b的變化只影響原問題的基本解，不影響檢驗(yàn)數(shù)（對偶問題的解）；靈敏度分析時，要弄清楚：1）系數(shù)在什么范圍內(nèi)變化時，最優(yōu)解（基）不變；2）若系數(shù)的變化使最優(yōu)解發(fā)生變化，如何最簡便地求得新最優(yōu)解。系數(shù)變化對解的結(jié)果的影響.74計(jì)算軟件LinGoMatlab.75人力