第二章 線性規(guī)劃的圖解法

第二章線性規(guī)劃的圖解法第一頁(yè)，共三十三頁(yè)，編輯于2023年，星期四

學(xué)習(xí)重點(diǎn)及難點(diǎn)

1、線性規(guī)劃問(wèn)題的建模及圖解法

(熟練掌握)2、圖解法的求解過(guò)程及解的各種情況

（重點(diǎn))3、圖解法的靈敏度分析(熟練掌握)第二章線性規(guī)劃的圖解法第二頁(yè)，共三十三頁(yè)，編輯于2023年，星期四第二章線性規(guī)劃的圖解法線性規(guī)劃（LinearProgramming，簡(jiǎn)記為L(zhǎng)P）是運(yùn)籌學(xué)的一個(gè)重要分支，是運(yùn)籌學(xué)中研究較早、發(fā)展較快、理論上較為成熟和應(yīng)用上極為廣泛的一個(gè)分支。特別是1947年G.B.Dantying提出了一般線性規(guī)劃問(wèn)題求解的方法——單純形法之后，線性規(guī)劃的理論與應(yīng)用都得到了極大的發(fā)展。單純形法的有效性使它不僅是線性規(guī)劃的最基本的算法之一，而且已成為整數(shù)規(guī)劃和非線性規(guī)劃某些算法的基礎(chǔ)。第三頁(yè)，共三十三頁(yè)，編輯于2023年，星期四§1線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型一、線性規(guī)劃問(wèn)題的提出

要利用線性規(guī)劃的方法解決實(shí)際問(wèn)題，首先要建立其數(shù)學(xué)模型.數(shù)學(xué)模型是描述實(shí)際問(wèn)題共性的抽象的數(shù)學(xué)形式，因此可以利用純數(shù)學(xué)的方法進(jìn)行研究，從而得到實(shí)際問(wèn)題的性質(zhì)及其解決的辦法。從實(shí)際問(wèn)題中建立數(shù)學(xué)模型，主要有以下三個(gè)步驟：

(1)根據(jù)影響所要達(dá)到目的的因素確定決策變量；

(2)由決策變量和所要達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù).(3)由決策變量所受的限制條件確定決策變量所要滿(mǎn)足的約束條件；第四頁(yè)，共三十三頁(yè)，編輯于2023年，星期四例1.資源的合理利用問(wèn)題

某廠生產(chǎn)甲、乙兩種產(chǎn)品，要消耗A、B、C三種資源，已知每生產(chǎn)單位產(chǎn)品甲需要A、B、C資源分別是3、2、0，生產(chǎn)單位產(chǎn)品乙需要A、B、C資源分別是2、1、3，資源A、B、C的現(xiàn)有數(shù)量分別是65、40、75，甲、乙兩種產(chǎn)品的單位利潤(rùn)分別是1500、2500，問(wèn)如何安排生產(chǎn)計(jì)劃，使得既能充分利用現(xiàn)有資源又使總利潤(rùn)最大？第五頁(yè)，共三十三頁(yè)，編輯于2023年，星期四產(chǎn)品甲產(chǎn)品乙資源的限制資源A3265資源B2140資源C0375單位利潤(rùn)15002500第六頁(yè)，共三十三頁(yè)，編輯于2023年，星期四解：將一個(gè)實(shí)際問(wèn)題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個(gè)步驟：1．確定決策變量：設(shè)x1表示生產(chǎn)甲產(chǎn)品的數(shù)量；x2表示生產(chǎn)乙產(chǎn)品的數(shù)量2．確定目標(biāo)函數(shù)：工廠的目標(biāo)是總利潤(rùn)最大

maxz=1500x1+2500x23．確定約束條件：

3x1+2x265（A資源的限制）

2x1+x240（B資源的限制）

3x275（C資源的限制）4．變量取值限制：一般情況，決策變量只取大于等于0的值（非負(fù)值）

x10,x20第七頁(yè)，共三十三頁(yè)，編輯于2023年，星期四用max表示最大值，s.t.（subjectto的簡(jiǎn)寫(xiě)）表示約束條件，

得到該問(wèn)題的數(shù)學(xué)模型為：

maxZ=1500x1+2500x23x1+2x265s.t.2x1+x240

3x275x1,x20線性規(guī)劃數(shù)學(xué)模型三要素：

決策變量、目標(biāo)函數(shù)、約束條件第八頁(yè)，共三十三頁(yè)，編輯于2023年，星期四例2配料問(wèn)題某化工廠根據(jù)一項(xiàng)合同要為用戶(hù)生產(chǎn)一種用甲、乙兩種原料混合配制而成的特殊產(chǎn)品.甲、乙兩種原料都含有A、B、C三種化學(xué)成分，其含量（%）和單位成本以及按合同規(guī)定產(chǎn)品中三種化學(xué)成分的最低含量（%）限制如表所示.問(wèn)廠方應(yīng)如何配制該產(chǎn)品，使得總成本達(dá)到最??？第九頁(yè)，共三十三頁(yè)，編輯于2023年，星期四原料化學(xué)成分甲乙產(chǎn)品成分最低含量A1234B232C3155單位成本32第十頁(yè)，共三十三頁(yè)，編輯于2023年，星期四解：(1)確定決策變量：設(shè)每單位該產(chǎn)品用x1單位甲原料和x2單位乙原料配制而成.

(2)明確目標(biāo)函數(shù)：成本最小，即求

z=3x1+2x2的最小值

(3)所滿(mǎn)足的約束條件對(duì)化學(xué)成分A的要求：12x1+3x2≥4

對(duì)化學(xué)成分B的要求：2x1+3x2≥2

對(duì)化學(xué)成分C的要求：3x1+15x2≥5

配料平衡條件：x1+x2=1(4)變量基本要求：

x1，x2≥0第十一頁(yè)，共三十三頁(yè)，編輯于2023年，星期四則問(wèn)題的數(shù)學(xué)模型為：記為minz=3x1+2x212x1+3x2≥42x1+3x2≥2S.t.3x1+15x2≥5

x1+x2=1

x1，x2≥0第十二頁(yè)，共三十三頁(yè)，編輯于2023年，星期四例3運(yùn)輸問(wèn)題設(shè)某種物資有兩個(gè)產(chǎn)地A1，A2，其產(chǎn)量分別為2000噸、1100噸，另有四個(gè)銷(xiāo)地B1、B2、B3、B4需要該種物資，其需求量分別為1700噸、1100噸、200噸、100噸.已知每噸運(yùn)費(fèi)如表所示，問(wèn)如何調(diào)運(yùn)，才能使總運(yùn)費(fèi)最??？銷(xiāo)地產(chǎn)地B1B2B3B4A12125715A251513715第十三頁(yè)，共三十三頁(yè)，編輯于2023年，星期四解：設(shè)xij表示由產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj（i=1,2；j=1,2,3,4）的運(yùn)量.

目標(biāo)函數(shù)為總運(yùn)費(fèi)最小:minZ=21x11+25x12+7x13+15x14+51x21

+51x22+37x23+15x24

由于總產(chǎn)量與總需求量相等（產(chǎn)銷(xiāo)平衡）,所以有約束條件：對(duì)產(chǎn)地產(chǎn)量的約束:

x11+x12+x13+x14=2000

x21+x22+x23+x24=1100

對(duì)銷(xiāo)地需求量的約束:x11+x21=1700

x12+x13=1100

x13+x23=200

x14+x24=100

另外xij是運(yùn)輸量，應(yīng)滿(mǎn)足xij≥0（i=1,2；j=1,2,3,4）第十四頁(yè)，共三十三頁(yè)，編輯于2023年，星期四所以產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的模型可記為minz=21x11+25x12+7x13+15x14

+51x21+51x22+37x23+15x24s.t.x11+x12+x13+x14=2000

x21+x22+x23+x24=1100

x11+x21=1700

x12+x22=1100

x13+x23=200

x14+x24=100

xij

≥0（i=1,2；j=1,2,3,4）.第十五頁(yè)，共三十三頁(yè)，編輯于2023年，星期四二、線性規(guī)劃問(wèn)題的數(shù)學(xué)模型具體分析例1、例2、例3，雖然它們的背景意義各不相同，但從數(shù)學(xué)模型角度，卻具有以下一些共同要點(diǎn)：第一，求一組決策變量xi，并往往要求它們?yōu)榉秦?fù)；第二，確定決策變量可能受到的約束，稱(chēng)為約束條件，它們可以用決策變量的線性等式或線性不等式來(lái)表示；第三，在滿(mǎn)足約束條件的前提下，使某個(gè)函數(shù)值達(dá)到最大（如利潤(rùn)等）或最?。ㄈ绯杀?、運(yùn)費(fèi)等）.該函數(shù)稱(chēng)為目標(biāo)函數(shù)，它是決策變量的線性函數(shù).具備以上三個(gè)要素的問(wèn)題稱(chēng)為線性規(guī)劃問(wèn)題.簡(jiǎn)單地說(shuō)，線性規(guī)劃問(wèn)題就是求一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問(wèn)題.第十六頁(yè)，共三十三頁(yè)，編輯于2023年，星期四二、線性規(guī)劃問(wèn)題的數(shù)學(xué)模型一般表示形式：………………………........................................……第十七頁(yè)，共三十三頁(yè)，編輯于2023年，星期四

1、和式其他常用表示形式：………第十八頁(yè)，共三十三頁(yè)，編輯于2023年，星期四

2、矩陣式…………………………...……………第十九頁(yè)，共三十三頁(yè)，編輯于2023年，星期四

3、向量式……………第二十頁(yè)，共三十三頁(yè)，編輯于2023年，星期四302010當(dāng)z值不斷增加時(shí)，該直線x2=

-（3/5）x1+Z/2500沿著其法線方向向右上方移動(dòng)。

§2線性規(guī)劃的圖解法

maxZ=1500x1+2500x2s.t.3x1+2x265①2x1+x240②

3x275③

x1,x20④

由圖示可知最優(yōu)點(diǎn)為B（5，25），最優(yōu)值為70000可行域、可行解、最優(yōu)解、最優(yōu)1可行域③②①50等值線B唯一最優(yōu)解第二十一頁(yè)，共三十三頁(yè)，編輯于2023年，星期四**如將例1的目標(biāo)函數(shù)設(shè)為z=1500x1+1000x2

，那么，最優(yōu)情況下，目標(biāo)函數(shù)的等值線與直線1重合這時(shí)，最優(yōu)解有無(wú)窮多個(gè)，是線段BC上的所有點(diǎn)，最優(yōu)值為32500②①50BC無(wú)窮多最優(yōu)解第二十二頁(yè)，共三十三頁(yè)，編輯于2023年，星期四無(wú)界解如將例1的約束條件變?yōu)?3x1+2x2≥652x1+x2≥403x2≥75

x1，x2≥0那么，可行域成為一個(gè)上無(wú)界的區(qū)域，最優(yōu)值z(mì)→∞，這時(shí)，問(wèn)題無(wú)有限最優(yōu)解，即解無(wú)界1③②①50B第二十三頁(yè)，共三十三頁(yè)，編輯于2023年，星期四無(wú)可行解（無(wú)解）.如下述線性規(guī)劃問(wèn)題

maxz=2x1+x2s.t.x1+x2≤22x1+3x2≥8

x1,x2≥0用圖解法求解時(shí)看出不存在滿(mǎn)足所有約束的公共區(qū)域（可行域）,即無(wú)可行解，當(dāng)然也無(wú)最優(yōu)解。這時(shí)，也簡(jiǎn)稱(chēng)為無(wú)解.第二十四頁(yè)，共三十三頁(yè)，編輯于2023年，星期四線性規(guī)劃問(wèn)題解的特點(diǎn)和幾種可能情況：線性規(guī)劃問(wèn)題的可行解的集合是凸集凸集的極點(diǎn)（頂點(diǎn)）的個(gè)數(shù)是有限的最優(yōu)解如果存在只可能在凸集的極點(diǎn)上取得，而不可能發(fā)生在凸集的內(nèi)部線性規(guī)劃問(wèn)題的解可能是：唯一解、無(wú)窮多最優(yōu)解、無(wú)界解和無(wú)可行解(無(wú)解)第二十五頁(yè)，共三十三頁(yè)，編輯于2023年，星期四教科書(shū):P221、2課后作業(yè)第二十六頁(yè)，共三十三頁(yè)，編輯于2023年，星期四謝謝！本章結(jié)束第二十七頁(yè)，共三十三頁(yè)，編輯于2023年，星期四§3線性規(guī)劃圖解法的靈敏度分析靈敏度分析：在建立數(shù)學(xué)模型和求得最優(yōu)解之后，研究線性規(guī)劃的一些系數(shù)的變化對(duì)最優(yōu)解產(chǎn)生什么影響？重要的原因：1、模型中的系數(shù)一般都是估計(jì)值和預(yù)測(cè)值，不一定非常準(zhǔn)確；2、即使這些系數(shù)在某一時(shí)刻是精確值，它們也會(huì)隨著市場(chǎng)條件的變化而變化，不會(huì)一成不變；3、有了靈敏度分析就不必為了應(yīng)付這些變化而不停的建立新的模型和求新的最優(yōu)解。第二十八頁(yè)，共三十三頁(yè)，編輯于2023年，星期四3020一、目標(biāo)函數(shù)中的系數(shù)的靈敏度分析

maxZ=1500x1+2500x2s.t.3x1+2x265①2x1+x240②

3x275③

x1,x201③②①50B由圖示可知最優(yōu)解為B(5，25),最優(yōu)值為70000x2

=-3x1/2+65②-3/2x2=25③0Z=c1x1+c2x2x2=-c1x1/c2+z/c2-c1/c2-3/2<-c1/c2<0第二十九頁(yè)，共三十三頁(yè)，編輯于2023年，星期四一、目標(biāo)函數(shù)中的系數(shù)的靈敏度分析

-3/2≤-c1/c2≤0當(dāng)c2=2500不變時(shí)，0≤c1≤3750，最優(yōu)解不變當(dāng)c1=1500不變時(shí)，1000≤

c2，最優(yōu)解不變第三十頁(yè)，共三十三頁(yè)，編輯于2023年，星期四3020

maxZ=1500x1+2500x2s.t.3x1+