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

第二章線性規(guī)劃的圖解法第1頁，課件共33頁，創(chuàng)作于2023年2月

學習重點及難點

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

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

（重點)3、圖解法的靈敏度分析(熟練掌握)第二章線性規(guī)劃的圖解法第2頁，課件共33頁，創(chuàng)作于2023年2月第二章線性規(guī)劃的圖解法線性規(guī)劃（LinearProgramming，簡記為LP）是運籌學的一個重要分支，是運籌學中研究較早、發(fā)展較快、理論上較為成熟和應用上極為廣泛的一個分支。特別是1947年G.B.Dantying提出了一般線性規(guī)劃問題求解的方法——單純形法之后，線性規(guī)劃的理論與應用都得到了極大的發(fā)展。單純形法的有效性使它不僅是線性規(guī)劃的最基本的算法之一，而且已成為整數規(guī)劃和非線性規(guī)劃某些算法的基礎。第3頁，課件共33頁，創(chuàng)作于2023年2月§1線性規(guī)劃問題及其數學模型一、線性規(guī)劃問題的提出

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

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

(2)由決策變量和所要達到目的之間的函數關系確定目標函數.(3)由決策變量所受的限制條件確定決策變量所要滿足的約束條件；第4頁，課件共33頁，創(chuàng)作于2023年2月例1.資源的合理利用問題

某廠生產甲、乙兩種產品，要消耗A、B、C三種資源，已知每生產單位產品甲需要A、B、C資源分別是3、2、0，生產單位產品乙需要A、B、C資源分別是2、1、3，資源A、B、C的現有數量分別是65、40、75，甲、乙兩種產品的單位利潤分別是1500、2500，問如何安排生產計劃，使得既能充分利用現有資源又使總利潤最大？第5頁，課件共33頁，創(chuàng)作于2023年2月產品甲產品乙資源的限制資源A3265資源B2140資源C0375單位利潤15002500第6頁，課件共33頁，創(chuàng)作于2023年2月解：將一個實際問題轉化為線性規(guī)劃模型有以下幾個步驟：1．確定決策變量：設x1表示生產甲產品的數量；x2表示生產乙產品的數量2．確定目標函數：工廠的目標是總利潤最大

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

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

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

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

x1

0,x2

0第7頁，課件共33頁，創(chuàng)作于2023年2月用max表示最大值，s.t.（subjectto的簡寫）表示約束條件，

得到該問題的數學模型為：

maxZ=1500x1+2500x23x1+2x2

65s.t.2x1+x2

40

3x275x1,x2

0線性規(guī)劃數學模型三要素：

決策變量、目標函數、約束條件第8頁，課件共33頁，創(chuàng)作于2023年2月例2配料問題某化工廠根據一項合同要為用戶生產一種用甲、乙兩種原料混合配制而成的特殊產品.甲、乙兩種原料都含有A、B、C三種化學成分，其含量（%）和單位成本以及按合同規(guī)定產品中三種化學成分的最低含量（%）限制如表所示.問廠方應如何配制該產品，使得總成本達到最??？第9頁，課件共33頁，創(chuàng)作于2023年2月原料化學成分甲乙產品成分最低含量A1234B232C3155單位成本32第10頁，課件共33頁，創(chuàng)作于2023年2月解：(1)確定決策變量：設每單位該產品用x1單位甲原料和x2單位乙原料配制而成.

(2)明確目標函數：成本最小，即求

z=3x1+2x2的最小值

(3)所滿足的約束條件對化學成分A的要求：12x1+3x2≥4

對化學成分B的要求：2x1+3x2≥2

對化學成分C的要求：3x1+15x2≥5

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

x1，x2≥0第11頁，課件共33頁，創(chuàng)作于2023年2月則問題的數學模型為：記為minz=3x1+2x212x1+3x2≥42x1+3x2≥2S.t.3x1+15x2≥5

x1+x2=1

x1，x2≥0第12頁，課件共33頁，創(chuàng)作于2023年2月例3運輸問題設某種物資有兩個產地A1，A2，其產量分別為2000噸、1100噸，另有四個銷地B1、B2、B3、B4需要該種物資，其需求量分別為1700噸、1100噸、200噸、100噸.已知每噸運費如表所示，問如何調運，才能使總運費最省？銷地產地B1B2B3B4A12125715A251513715第13頁，課件共33頁，創(chuàng)作于2023年2月解：設xij表示由產地Ai運往銷地Bj（i=1,2；j=1,2,3,4）的運量.

目標函數為總運費最小:minZ=21x11+25x12+7x13+15x14+51x21

+51x22+37x23+15x24

由于總產量與總需求量相等（產銷平衡）,所以有約束條件：對產地產量的約束:

x11+x12+x13+x14=2000

x21+x22+x23+x24=1100

對銷地需求量的約束:x11+x21=1700

x12+x13=1100

x13+x23=200

x14+x24=100

另外xij是運輸量，應滿足xij≥0（i=1,2；j=1,2,3,4）第14頁，課件共33頁，創(chuàng)作于2023年2月所以產銷平衡運輸問題的模型可記為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）.第15頁，課件共33頁，創(chuàng)作于2023年2月二、線性規(guī)劃問題的數學模型具體分析例1、例2、例3，雖然它們的背景意義各不相同，但從數學模型角度，卻具有以下一些共同要點：第一，求一組決策變量xi，并往往要求它們?yōu)榉秦摚坏诙?，確定決策變量可能受到的約束，稱為約束條件，它們可以用決策變量的線性等式或線性不等式來表示；第三，在滿足約束條件的前提下，使某個函數值達到最大（如利潤等）或最?。ㄈ绯杀尽⑦\費等）.該函數稱為目標函數，它是決策變量的線性函數.具備以上三個要素的問題稱為線性規(guī)劃問題.簡單地說，線性規(guī)劃問題就是求一個線性目標函數在一組線性約束條件下的極值問題.第16頁，課件共33頁，創(chuàng)作于2023年2月二、線性規(guī)劃問題的數學模型一般表示形式：………………………........................................……第17頁，課件共33頁，創(chuàng)作于2023年2月

1、和式其他常用表示形式：………第18頁，課件共33頁，創(chuàng)作于2023年2月

2、矩陣式…………………………...……………第19頁，課件共33頁，創(chuàng)作于2023年2月

3、向量式……………第20頁，課件共33頁，創(chuàng)作于2023年2月302010當z值不斷增加時，該直線x2=

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

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

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

65①2x1+x2

40②

3x275③

x1,x2

0④

由圖示可知最優(yōu)點為B（5，25），最優(yōu)值為70000可行域、可行解、最優(yōu)解、最優(yōu)1可行域③②①50等值線B唯一最優(yōu)解第21頁，課件共33頁，創(chuàng)作于2023年2月**如將例1的目標函數設為z=1500x1+1000x2

，那么，最優(yōu)情況下，目標函數的等值線與直線1重合這時，最優(yōu)解有無窮多個，是線段BC上的所有點，最優(yōu)值為32500②①50BC無窮多最優(yōu)解第22頁，課件共33頁，創(chuàng)作于2023年2月無界解如將例1的約束條件變?yōu)?3x1+2x2≥652x1+x2≥403x2≥75

x1，x2≥0那么，可行域成為一個上無界的區(qū)域，最優(yōu)值z→∞，這時，問題無有限最優(yōu)解，即解無界1③②①50B第23頁，課件共33頁，創(chuàng)作于2023年2月無可行解（無解）.如下述線性規(guī)劃問題

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

x1,x2≥0用圖解法求解時看出不存在滿足所有約束的公共區(qū)域（可行域）,即無可行解，當然也無最優(yōu)解。這時，也簡稱為無解.第24頁，課件共33頁，創(chuàng)作于2023年2月線性規(guī)劃問題解的特點和幾種可能情況：線性規(guī)劃問題的可行解的集合是凸集凸集的極點（頂點）的個數是有限的最優(yōu)解如果存在只可能在凸集的極點上取得，而不可能發(fā)生在凸集的內部線性規(guī)劃問題的解可能是：唯一解、無窮多最優(yōu)解、無界解和無可行解(無解)第25頁，課件共33頁，創(chuàng)作于2023年2月教科書:P221、2課后作業(yè)第26頁，課件共33頁，創(chuàng)作于2023年2月謝謝！本章結束第27頁，課件共33頁，創(chuàng)作于2023年2月§3線性規(guī)劃圖解法的靈敏度分析靈敏度分析：在建立數學模型和求得最優(yōu)解之后，研究線性規(guī)劃的一些系數的變化對最優(yōu)解產生什么影響？重要的原因：1、模型中的系數一般都是估計值和預測值，不一定非常準確；2、即使這些系數在某一時刻是精確值，它們也會隨著市場條件的變化而變化，不會一成不變；3、有了靈敏度分析就不必為了應付這些變化而不停的建立新的模型和求新的最優(yōu)解。第28頁，課件共33頁，創(chuàng)作于2023年2月3020一、目標函數中的系數的靈敏度分析

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

65①2x1+x2

40②

3x275③

x1,x2

01③②①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第29頁，課件共33頁，創(chuàng)作于2023年2月一、目標函數中的系數的靈敏度分析

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

c2，最優(yōu)解不變第30頁，課件共33頁，創(chuàng)作于2023年2月3020

maxZ=1500x1+2500x2s.t.3