單純形講稿.ppt

1、第一章線性規(guī)劃與單純形法,第一節(jié)線性規(guī)劃的基本概念 第二節(jié)線性規(guī)劃的標(biāo)準(zhǔn)形式和解的性質(zhì) 第三節(jié)單純形法 第四節(jié)人工變量法 第五節(jié)線性規(guī)劃應(yīng)用舉例,本章學(xué)習(xí)目的和要求,通過本章的學(xué)習(xí)，要求學(xué)生掌握線性規(guī)劃的圖解法，深刻理解單純形法的解題思路，熟練掌握其運(yùn)算步驟，并能在實(shí)際問題中加以運(yùn)用。,主要研究目的,1已有一定數(shù)量的人力、物力、財(cái)力資源，研究如何充分合理地使用才能使完成的任務(wù)量最大。（如：利潤(rùn)、產(chǎn)值等最大。 maximum） 2當(dāng)一項(xiàng)任務(wù)量確定以后，研究如何統(tǒng)籌安排，才能使完成任務(wù)耗費(fèi)的資源量為最小。（如：成本最小。minimum）,第一節(jié)線性規(guī)劃的基本概念,一、線性規(guī)劃的數(shù)學(xué)模型 【例1-1

2、】 某廠生產(chǎn)P、Q兩種產(chǎn)品，主要消耗A、B、C三種原料，已知單位產(chǎn)品的原料消耗數(shù)量等資料如表1-1所示。,表11,要求確定P、Q的產(chǎn)量，使產(chǎn)值最大。,解：設(shè)P、Q的產(chǎn)量分別為x1，x2，則問題的模型為,【例1-2】 某公司打算利用甲、乙、丙3種原料配置一種新型保健飲料，已知每千克原料中兩種主要保健成分A，B的含量及原料單價(jià)如表1-2所示。,產(chǎn)品質(zhì)量標(biāo)準(zhǔn)規(guī)定每千克飲料中，營(yíng)養(yǎng)成分A，B的含量不低于10個(gè)與8個(gè)單位。如何制定飲料配方，既滿足質(zhì)量標(biāo)準(zhǔn)又使成本最低？,解：設(shè)每千克飲料中原料甲，乙，丙的投入量分為x1，x2，x3千克，則問題的模型為：,【例1-3】 A1，A2是兩個(gè)糧庫(kù)，每月分別可調(diào)出糧

3、食30噸與40噸，三個(gè)糧店B1，B2，B3每月的需求量分別為20噸，25噸與18噸。糧庫(kù)與糧店之間每噸糧食的運(yùn)費(fèi)如下表1-3所示（單位：元/噸）。,糧店,運(yùn)費(fèi),糧庫(kù),要求安排糧食調(diào)運(yùn)方案，在滿足需求的前提下，使總運(yùn)費(fèi)最低。,解：設(shè)從糧庫(kù)Ai到糧店Bj的調(diào)運(yùn)量為xij，i=1，2，j=1，2，3，則問題的模型為：,上述三個(gè)問題屬于同一類型的決策優(yōu)化問題，它們具有下列共同特點(diǎn)： （1）每個(gè)行動(dòng)方案可用一組變量（x1，xn）的值表示，這些變量一般取非負(fù)值； （2）變量的變化要受某些限制，這些限制條件用一些線性等式或不等式表示； （3）有一個(gè)需要優(yōu)化的目標(biāo)，它也是變量的線性函數(shù)。 具備以上三個(gè)特點(diǎn)的數(shù)

4、學(xué)模型稱為線性規(guī)劃（Linear Programming，簡(jiǎn)記為L(zhǎng)P）。,實(shí)際問題中線性的含義,一是嚴(yán)格的比例性，如生產(chǎn)某產(chǎn)品對(duì)資源的消耗量和可獲取的利潤(rùn)，同其生產(chǎn)數(shù)量嚴(yán)格成比例。 二是可疊加性，如生產(chǎn)多種產(chǎn)品時(shí)對(duì)某項(xiàng)資源的消耗量應(yīng)等于各產(chǎn)品對(duì)該項(xiàng)資源的消耗量之和。,線性規(guī)劃的一般形式為：,變量x1，x2，xn稱為決策變量，目標(biāo)函數(shù)中變量系數(shù)cj，稱為價(jià)值系數(shù)，bi稱為右端常數(shù)，約束條件（1-3）稱為非負(fù)約束，（1-2）稱為技術(shù)約束，系數(shù)aij稱為技術(shù)系數(shù)。滿足全部約束條件的變量值（x1，xn）稱為可行解，可行解的集合稱為可行域，記為R；使目標(biāo)函數(shù)取得最大（最小）值的可行解（x1，xn）稱為最

5、優(yōu)解。,（1-3）,（1-2）,（1-1）,采用求和符號(hào)，線性規(guī)劃的一般形式可以簡(jiǎn)寫為：,用向量形式可表示為：,用矩陣和向量形式表示為：,式中：X=（x1，x2，xn）T C=（c1，c2，cn） b=（b1，b2，bm）T A=（aij）mn Pj=（a1j，a2j，amj）T,二、圖解法,當(dāng)決策變量個(gè)數(shù)n=2時(shí)，LP問題可以通過在平面上作圖的方法求解，稱為圖解法。 圖解法求解的目的： 1.判別線性規(guī)劃問題的求解結(jié)局。 2.在存在最優(yōu)解的條件下，把問題的最優(yōu)解找出來。,【例1-4】 求下列問題的最優(yōu)解。,（1）確定問題的可行域R。,可行域R是凸多角形OQ1Q2Q3Q4,（2）分析目標(biāo)函數(shù)Z的

6、等值線平行移動(dòng)與Z值的關(guān)系，確定最優(yōu)解的位置。,當(dāng)z取定值時(shí)，方程z=2x1+5x2或x2=2/5x1+z/5表示一條斜率為2/5的直線 l ， 稱為z的等值線，它在x2軸上的截距為z/5。當(dāng)l向右上方平行移動(dòng)且保持與R有共同部分時(shí)，z值不斷上升，由于l的斜率為2/5，因此當(dāng)l向右上方平移的過程中，與R最后的公共點(diǎn)是Q3，z在Q3達(dá)到最大值。,（3）計(jì)算最優(yōu)解。,點(diǎn)Q3是直線l1與l3的交點(diǎn)，它的坐標(biāo)由方程組,決定，從中解得x1=2，x2=3。這就是問題的最優(yōu)解，相應(yīng)的目標(biāo)函數(shù)值z(mì)=2253=19。最優(yōu)產(chǎn)量計(jì)劃是P，Q分別生產(chǎn)2個(gè)與3個(gè)單位，最大產(chǎn)值為19萬元。這時(shí)原料A與C用完，B剩余4噸。

7、,線性規(guī)劃問題求解的幾種可能結(jié)局：,1.唯一最優(yōu)解：如上例。 2.無窮多最優(yōu)解：如Z換成maxZ=2X1+4X2,，此時(shí)最優(yōu)解在線段Q2Q3 上達(dá)到，有無窮多最優(yōu)解。 已求得Q3的坐標(biāo)為（2，3）；Q2坐標(biāo)由方程組,決定，從中解得x1=3，x2=5/2。 設(shè)， ，線段Q2Q3上的點(diǎn)可用 X1+（1）X2（01）表示。因此，X1+（1）X2（01）是問題的全部最優(yōu)解。,3.無界解,如約束條件只保留第3個(gè)，即4X212，這時(shí)可行域無界，Z值可無限上升，無最優(yōu)解，簡(jiǎn)稱無界解，即有可行解，但目標(biāo)函數(shù)值無解。 產(chǎn)生原因：是由于在建立實(shí)際問題的數(shù)學(xué)模型中遺漏了某些必要的資源約束條件。,4.無解或無可行解,

8、O,x2,D,A,2,4,x1,B,C,l1,l2,l,可行域是空集，問題無可行解，當(dāng)然更無最優(yōu)解。 注意：考試中如出現(xiàn)3、4兩種情況，一定自己搞錯(cuò)了，必須重新解。,圖解法得到的啟示,1.求解線性規(guī)劃問題時(shí)，解的情況有：唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解。 2.若線性規(guī)劃問題的可行域存在，則可行域是一凸集。 3.若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解一定在某個(gè)頂點(diǎn)可達(dá)到。 4.解題思路是：先找出凸集的任一頂點(diǎn)，計(jì)算Z值，比較相鄰頂點(diǎn)Z值，如大，轉(zhuǎn)到相鄰頂點(diǎn)，一直到找出使Z值最大的頂點(diǎn)為止。,第二節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)形式和解的性質(zhì),一、 LP的標(biāo)準(zhǔn)形式,稱為線性規(guī)劃問題的標(biāo)準(zhǔn)形式（其中右端常

9、數(shù)b1，b2，bm0）。,線性規(guī)劃標(biāo)準(zhǔn)形式的特點(diǎn)： 1. 約束條件全部是等式 2. 目標(biāo)函數(shù)限定求最大值,變換一般LP為標(biāo)準(zhǔn)形式的方法： （1）如果原問題目標(biāo)函數(shù)求極小值：,令z1=z，轉(zhuǎn)化為求。 （2）若某個(gè)右端常數(shù)bi0，則以1乘該約束兩端。 （3）若某約束為“”型的不等式約束，則在左端加上一個(gè)非負(fù)變量，稱為松弛變量，使不等式化為等式；若某約束為“”型，則在左端減去一個(gè)非負(fù)變量，稱為剩余變量，或者仍然稱為松弛變量，使不等式轉(zhuǎn)化為等式。（目標(biāo)函數(shù)不變） （4）若某個(gè)xj的符號(hào)約束為xj0；那么令xj=xj，則xj0；若某個(gè)xj無符號(hào)限制，令xj=xjxj，其中xj0，xj0。（目標(biāo)函數(shù)變）,

10、例：把LP問題,化為標(biāo)準(zhǔn)形式 在三個(gè)技術(shù)約束中，分別加入松弛變量x3，x4，x5，問題化為標(biāo)準(zhǔn)形式：,解,例 將下列線性規(guī)劃化成標(biāo)準(zhǔn)型,得到,例、將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)型,令x2=-x4,x3=x5-x6,s.t.,化為標(biāo)準(zhǔn)形式,【例1-9】 把LP問題,線性規(guī)劃可行解得概念,在線性規(guī)劃問題中，滿足約束條件的解稱為可行解；所有可行解的集合稱為可行域；使目標(biāo)函數(shù)達(dá)到最優(yōu)值的解稱為最優(yōu)解。,矩陣的介紹,單位矩陣的介紹,注意：若矩陣的元素只有一行，則稱其為行矩陣；若只有一列則稱其為列矩陣,設(shè)系數(shù)矩陣A的秩是m，即A的m個(gè)行向量是線 性無關(guān)的。若B是A的m階子陣，稱B為問題的 一個(gè)基。設(shè)B=（，）

11、，稱對(duì)應(yīng)的 變量， 為基變量，其它的變量稱為 非基變量。令非基變量等于0，從方程組可以唯一 解出基變量的值，從而得到方程組的一個(gè)解，稱 為基本解；如果它的各個(gè)分量非負(fù)，即它同時(shí)又 是可行解，則稱之為基可行解，對(duì)應(yīng)的基稱為可行基。 可行解是約束方程組的解并且滿足非負(fù)條件； 基本解是約束方程組具有特定性質(zhì)的解，它至多有m 個(gè)非0分量，但未必滿足非負(fù)性?；尚薪馔瑫r(shí)具有 兩者的性質(zhì)。,【例】,它的系數(shù)矩陣為：,A的子矩陣（P3，P4，P5）正好是單位矩陣，這種式的方程組稱為典式，或稱為對(duì)x3，x4，x5的解出形式。以（P3，P4，P5）為基，令非基變量x1=x2=0，則基變量正好等于右端常數(shù)值，得到

12、基可行解X=（0，0，8，20，12）T。,第三節(jié) 單純形法 （重點(diǎn)）,一、 單純形法的解題思路,【例】,約束方程組已經(jīng)是對(duì)于x3，x4，x5的解出形式，以它們作為第一組（初始）基變量，得基可行解X1=(0,0,8,20,12)T，目標(biāo)函數(shù)值z(mì)1=0。,（1）,從目標(biāo)函數(shù)z=2x1+5x2來看，如果x1或x2成為基變量（簡(jiǎn)稱入基），變成正值，則z值將會(huì)上升。由于x2系數(shù)更大，引入x2更有利于z的上升，故首先選擇x2入基，x1仍然保持是非基變量。此時(shí)約束方程組實(shí)際成為：,可知x5min8/2，20/2，12/4=3 這時(shí)x5=0，因此，x5退出基，成為非基變量。,把約束方程組（1）轉(zhuǎn)化為對(duì)新基變

13、量x2,x3,x4的解出形式：,從中可得基可行解X2=(0,3,2,14,0)T，相應(yīng)z2=53=15，函數(shù)值上升了15個(gè)單位。,（2）,由（2）第三式得到x2=3 x5，代入z的表達(dá)式，得到 z=2x1+5x2=2x1+5（3x5）=2x1x5+15 x1的系數(shù)為正，故引入x1，x5保持為0 由知x1min2/1，14/5，=2 取x1=2，則x3=0，x3退出基。然后把方程組（2）變換為對(duì)x1，x2，x4的解出形式：,（3）,新的基可行解X3=(2,3,0,4,0)T，相應(yīng)z值z(mì)3=22+53=19,由（3）的第一式得到x1=2x3+ x5代入（2）中。 z=2（2x3+x5）x5+15=

14、2x3x5+19 此式表明z19，而當(dāng)X=X3時(shí)，z=19，因此X3是問題最優(yōu)解，z的最優(yōu)值是19萬元。 總結(jié)： 單純形法是一種迭代算法，每步迭代包括下列環(huán)節(jié)： 首先判定當(dāng)前基可行解是否最優(yōu)，若是，則結(jié)束；否則，先確定換入變量，再確定換出變量，最后把方程組轉(zhuǎn)化為對(duì)新基變量的解出形式，得到新的基可行解。,二、 單純形法要點(diǎn)和單純形表,1. 檢驗(yàn)數(shù)的意義和計(jì)算公式,假定所有b1，bm0。顯然問題有基可行解X1=(b1,b2,bm,0,0)T，相應(yīng)目標(biāo)函數(shù)值。 i=（1，2，m）,基變量的檢驗(yàn)數(shù)永遠(yuǎn)為0。 非基變量xj的檢驗(yàn)數(shù)j是引入xj一個(gè)單位時(shí)目標(biāo)函數(shù)z的改變量，只有j0時(shí)，方值得讓xj入基。,

15、2.單純形表,表1-5,總結(jié),從表中可以直接讀出基可行解X：xi=bi（i=1，m），其它xj=0； 相應(yīng)目標(biāo)函數(shù)值，是CB列與b列元素乘積之和； 每個(gè)變量xj（包括基變量在內(nèi)）的檢驗(yàn)數(shù)j，等于cj減去CB列元素與表中xj的系數(shù)列向量元素乘積之和。 單純形法的全部分析和計(jì)算過程，可以比較方便地在單純形表中完成。,(1)基變量的檢驗(yàn)數(shù)永遠(yuǎn)為0。 (2)非基變量xj的檢驗(yàn)數(shù)j是引入xj一個(gè)單位時(shí)目標(biāo)函數(shù)z的改變量，只有j0時(shí)，方值得讓xj入基。 (3)每個(gè)變量xj（包括基變量在內(nèi)）的檢驗(yàn)數(shù)j，等于cj減去基變量?jī)r(jià)值系數(shù)行矩陣元素與表中xj的系數(shù)列矩陣元素乘積之和,單純形法解題注意問題：,總結(jié),3.

16、 單純形法的基本法則,法則1 最優(yōu)性判定法則 若對(duì)基可行解X1，所有檢驗(yàn)數(shù)j0，則X1為最優(yōu)解。,法則2 換入變量確定法則（最大價(jià)值系數(shù)法則） 設(shè)，則xk為換入變量。,法則3 換出變量確定法則 （最小比值法則） 設(shè)xk為換入變量，并設(shè) 則最小比值所在行的原基變量xl為換出變量。,法則4 換基迭代運(yùn)算法則 對(duì)方程組的增廣矩陣實(shí)施行的初等變換，使主元alk化為1，主元列其它元素化為0。具體地說，第l行乘以1/alk，并將第l行的aik/alk倍加到第i行上去，i=1，2，m，il。,例一求下列LP問題的最優(yōu)解,例二求下列LP問題的最優(yōu)解,三、 關(guān)于單純形法的補(bǔ)充說明,1. 無窮多最優(yōu)解與唯一最優(yōu)解的判別法則 若對(duì)某可行解X1， （1）所有檢驗(yàn)數(shù)j0，且有一個(gè)非基變量xk的檢驗(yàn)數(shù)等于0，則問題有無窮多最優(yōu)解；（2）所有非基變量的檢驗(yàn)數(shù)j0，則問題有唯一最優(yōu)解。,例三求下列LP問題的最優(yōu)解,2. 無最優(yōu)解（無界解）的判定,若對(duì)基可行解X1，存在非基變量xk的檢驗(yàn)數(shù)k0，但aik0，i=1，2，m即xk的系數(shù)列向量無正分量，則問題無最優(yōu)解。 如上例中，,3. 求min z 的情況,這時(shí)可以有兩種處理方式： 一種方式是令z1=z，轉(zhuǎn)化為求max z1， 另一種是直接計(jì)算。 最優(yōu)性檢驗(yàn)條件改為：所有j0； 換入變量確定法則改為：如果則xk為換入變量。 單純形法的其它要點(diǎn)