運(yùn)籌學(xué)第二章

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

2、不等式。若目標(biāo)函數(shù)是非線性函數(shù)，或約束條件中有非線性的等式或不等式，則這樣的問題稱為非線性規(guī)劃。二、 一般建模過程1.理解要解決的問題，了解解題的目標(biāo)和條件；2.定義決策變量，每一組值表示一個(gè)方案；3.用決策變量的線性函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件三、 線性規(guī)劃模型的一般形式目標(biāo)函數(shù)： 約束條件： 第二節(jié)圖 解 法對(duì)于只有兩個(gè)決策變量的線性規(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)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1的每個(gè)約束條件都代表一個(gè)半平面。x2x1X20X2=0x2x1X10X1=0（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2300x1+x2=3001001002002x1+x24002x1+x2=400300200300400100100x2250x2=25020030

4、0200300（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖2-1所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖2-1（4）目標(biāo)函數(shù)，當(dāng)z取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。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)解，則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解； 2、無窮多個(gè)最優(yōu)解。若將例1 中的目標(biāo)函數(shù)變?yōu)?，則線段BC 上的所有點(diǎn)都代表了最優(yōu)解； 3、 無界解。即可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯(cuò)，忽略了一些必要的約束條件； 4、 無可行解。若在例1 的數(shù)學(xué)模型中再增加一個(gè)約束條件，則可行域?yàn)榭沼?，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。例2 某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購(gòu)進(jìn)125噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同

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

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

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

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

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

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