運(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é)問(wèn)題的提出一、引例例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元問(wèn)題：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？解：分析問(wèn)題后可得數(shù)學(xué)模型： 目標(biāo)函數(shù)： 約束條件： 這是一個(gè)線性規(guī)劃模型，因?yàn)椋耗繕?biāo)函數(shù)是線性函數(shù)，約束條件是一些線性的等式或

2、不等式。若目標(biāo)函數(shù)是非線性函數(shù)，或約束條件中有非線性的等式或不等式，則這樣的問(wèn)題稱為非線性規(guī)劃。二、 一般建模過(guò)程1.理解要解決的問(wèn)題，了解解題的目標(biāo)和條件；2.定義決策變量，每一組值表示一個(gè)方案；3.用決策變量的線性函數(shù)形式寫(xiě)出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)；4.用一組決策變量的等式或不等式表示解決問(wèn)題過(guò)程中必須遵循的約束條件三、 線性規(guī)劃模型的一般形式目標(biāo)函數(shù)： 約束條件： 第二節(jié)圖 解 法對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問(wèn)題的有關(guān)概念，并求解。 下面通過(guò)例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ī)劃問(wèn)題解的情況1、如果線性規(guī)劃有最優(yōu)解，則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解； 2、無(wú)窮多個(gè)最優(yōu)解。若將例1 中的目標(biāo)函數(shù)變?yōu)?，則線段BC 上的所有點(diǎn)都代表了最優(yōu)解； 3、 無(wú)界解。即可行域的范圍延伸到無(wú)窮遠(yuǎn)，目標(biāo)函數(shù)值可以無(wú)窮大或無(wú)窮小。一般來(lái)說(shuō)，這說(shuō)明模型有錯(cuò)，忽略了一些必要的約束條件； 4、 無(wú)可行解。若在例1 的數(shù)學(xué)模型中再增加一個(gè)約束條件，則可行域?yàn)榭沼颍淮嬖跐M足約束條件的解，當(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萬(wàn)元，每噸B原料的價(jià)格為3萬(wàn)元，試問(wèn)在滿足生產(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ù)的問(wèn)題： 設(shè)目標(biāo)函數(shù)為 (可以)令 z -f ， 則該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解，即 但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即 Min f Max z2、約束條件不是等式的問(wèn)題： （1）設(shè)約束條件為 可以引進(jìn)一個(gè)新的變量

8、 ，使它等于約束右邊與左邊之差 顯然， 也具有非負(fù)約束，即，這時(shí)新的約束條件成為 （2）當(dāng)約束條件為 時(shí)， 類似地令 顯然， 也具有非負(fù)約束，即，這時(shí)新的約束條件成為 3.右端項(xiàng)有負(fù)值的問(wèn)題： 在標(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í)稱為“剩余變量”。如果原問(wèn)題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。 例：將以下線性規(guī)劃問(wèn)題轉(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。通過(guò)以上變換，可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題： 約束條件： 4. 變量無(wú)符號(hào)限制的問(wèn)題 在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量xj沒(méi)有非負(fù)約束時(shí)，可以令 xj = xj- xj” 其中 xj0，xj”0 即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(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)解。一般情況：；寫(xiě)成斜截式 目標(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)均改變，則可直接用式（*）來(lái)判斷。假設(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 元 說(shuō)明在一定范圍內(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)無(wú)影響，該約束條件的對(duì)偶價(jià)格為 0 。 解釋：原最優(yōu)解沒(méi)有把原料 A 用盡，有50千克的剩余，因此增加10千克值增加了庫(kù)存，而不會(huì)增加利潤(rùn)。 在