運籌學(xué)第二章

1、第 2 次課 2學(xué)時 本次課教學(xué)重點： 線型規(guī)劃模型有關(guān)概念、圖解法求解線型規(guī)劃模型本次課教學(xué)難點： 線型規(guī)劃模型有關(guān)概念、各種解的情況分析本次課教學(xué)內(nèi)容：第二章線性規(guī)劃的圖解法第一節(jié)問題的提出一、引例例1. 某工廠在計劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表：資源限制設(shè)備11300臺時原料A21400千克原料B01250千克單位產(chǎn)品獲利50元100元問題：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？解：分析問題后可得數(shù)學(xué)模型： 目標(biāo)函數(shù)： 約束條件： 這是一個線性規(guī)劃模型，因為：目標(biāo)函數(shù)是線性函數(shù)，約束條件是一些線性的等式或

2、不等式。若目標(biāo)函數(shù)是非線性函數(shù)，或約束條件中有非線性的等式或不等式，則這樣的問題稱為非線性規(guī)劃。二、 一般建模過程1.理解要解決的問題，了解解題的目標(biāo)和條件；2.定義決策變量，每一組值表示一個方案；3.用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件三、 線性規(guī)劃模型的一般形式目標(biāo)函數(shù)： 約束條件： 第二節(jié)圖 解 法對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。 下面通過例1詳細(xì)講解其方法一、 有關(guān)概念1、 可行解：滿足約束條件的解2、 可行域：全體可行解的集合

3、。3、 最優(yōu)解：使得目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解。4、 凸集5、 松弛變量二、 圖解法求解線性規(guī)劃例1. 目標(biāo)函數(shù)： 約束條件： 解：(1)分別取決策變量為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點的坐標(biāo)代表了決策變量的一組值，例1的每個約束條件都代表一個半平面。x2x1X20X2=0x2x1X10X1=0（2）對每個不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2300x1+x2=3001001002002x1+x24002x1+x2=400300200300400100100x2250x2=25020030

4、0200300（3）把五個圖合并成一個圖，取各約束條件的公共部分，如圖2-1所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1（4）目標(biāo)函數(shù)，當(dāng)z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動等值線，當(dāng)移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50x1+100x2圖2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE綜上得到最優(yōu)解： 最優(yōu)目標(biāo)值 三、

5、線性規(guī)劃問題解的情況1、如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應(yīng)一個最優(yōu)解； 2、無窮多個最優(yōu)解。若將例1 中的目標(biāo)函數(shù)變?yōu)?，則線段BC 上的所有點都代表了最優(yōu)解； 3、 無界解。即可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件； 4、 無可行解。若在例1 的數(shù)學(xué)模型中再增加一個約束條件，則可行域為空域，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。例2 某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購進(jìn)125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時間也是不同

6、的，加工每噸A原料需要2個小時，加工每噸B原料需要1小時，而公司總共有600個加工小時。又知道每噸A原料的價格為2萬元，每噸B原料的價格為3萬元，試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買A，B兩種原料，使得購進(jìn)成本最低？解： 目標(biāo)函數(shù)： 約束條件： 采用圖解法。如下圖：100200300400500600100200300400600500x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200x1 x2 Q得Q點坐標(biāo)（250，100）為最優(yōu)解。教學(xué)組織1、課堂講授2、多媒體圖形演示作業(yè)布置： 1、P

7、23.2（1，2）第 3 次課 2學(xué)時 本次課教學(xué)重點： 化標(biāo)準(zhǔn)型、靈敏度分析本次課教學(xué)難點： 靈敏度分析本次課教學(xué)內(nèi)容：第三節(jié)圖解法的靈敏度分析一、線性規(guī)劃模型的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)： 約束條件： 標(biāo)準(zhǔn)形式四個特點：1目標(biāo)最大化； 2約束為等式； 3決策變量均非負(fù)； 4右端項非負(fù)。二、線性規(guī)劃模型標(biāo)準(zhǔn)化1.極小化目標(biāo)函數(shù)的問題： 設(shè)目標(biāo)函數(shù)為 (可以)令 z -f ， 則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即 但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即 Min f Max z2、約束條件不是等式的問題： （1）設(shè)約束條件為 可以引進(jìn)一個新的變量

8、 ，使它等于約束右邊與左邊之差 顯然， 也具有非負(fù)約束，即，這時新的約束條件成為 （2）當(dāng)約束條件為 時， 類似地令 顯然， 也具有非負(fù)約束，即，這時新的約束條件成為 3.右端項有負(fù)值的問題： 在標(biāo)準(zhǔn)形式中，要求右端項必須每一個分量非負(fù)。當(dāng)某一個右端項系數(shù)為負(fù)時，如 ，則把該等式約束兩端同時乘以-1，得到： 為了使約束由不等式成為等式而引進(jìn)的變量,當(dāng)不等式為“小于等于”時稱為“松弛變量”；當(dāng)不等式為“大于等于”時稱為“剩余變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進(jìn)不同的松弛變量。 例：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式  約束條件： x1 , x

9、2 , x3 0 解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令 次考慮約束，有2個不等式約束，引進(jìn)松弛變量。 三個約束條件的右端值為負(fù)，在等式兩邊同時乘-1。通過以上變換，可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題： 約束條件： 4. 變量無符號限制的問題 在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負(fù)約束。當(dāng)某一個變量xj沒有非負(fù)約束時，可以令 xj = xj- xj” 其中 xj0，xj”0 即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然xj的符號取決于xj和xj”的大小。三、 靈敏度分析靈敏度分析：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)）變化時，對最優(yōu)解產(chǎn)生的影響。1目標(biāo)

10、函數(shù)中的系數(shù) 的靈敏度分析 的變化只影響目標(biāo)函數(shù)等值線的斜率，不影響可行域。考慮例1的情況，目標(biāo)函數(shù) 在 (斜率為0 ) 到 ( 斜率為 )之間時，原最優(yōu)解 仍是最優(yōu)解。一般情況：；寫成斜截式 目標(biāo)函數(shù)等值線的斜率為 ， 當(dāng) 時，原最優(yōu)解仍是最優(yōu)解。假設(shè)產(chǎn)品的利潤100元不變，即，代到式（*）并整理得 假設(shè)產(chǎn)品的利潤 50 元不變，即 ，代到式（*）并整理得 假若產(chǎn)品、的利潤均改變，則可直接用式（*）來判斷。假設(shè)產(chǎn)品、的利潤分別為60元、55元，則 那么，最優(yōu)解為 和 的交點 。2 約束條件中右邊系數(shù)的靈敏度分析 當(dāng)約束條件中右邊系數(shù)變化時，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化。 考

11、慮例1的情況： （1）假設(shè)設(shè)備臺時增加10個臺時，即變化為310，這時可行域擴大，最優(yōu)解為 和 的交點 變化后的總利潤 變化前的總利潤 = 增加的利潤(50×60+ 100×250) (50 × 50+100 × 250) = 500 ，500 / 10 = 50 元 說明在一定范圍內(nèi)每增加（減少）1個臺時的設(shè)備能力就可增加（減少）50元利潤，稱為該約束條件的對偶價格。 （2）假設(shè)原料 A 增加10 千克時，即 變化為410，這時可行域擴大，但最優(yōu)解仍為 和 的交點 。此變化對總利潤無影響，該約束條件的對偶價格為 0 。 解釋：原最優(yōu)解沒有把原料 A 用盡，有50千克的剩余，因此增加10千克值增加了庫存，而不會增加利潤。 在