運(yùn)籌學(xué)第3章線性規(guī)劃問(wèn)題的計(jì)算機(jī)求解

第三章

線性規(guī)劃問(wèn)題的計(jì)算機(jī)求解§1“管理運(yùn)籌學(xué)”軟件的操作方法§2“管理運(yùn)籌學(xué)”軟件的輸出信息分析1可編輯ppt第三章

線性規(guī)劃問(wèn)題的計(jì)算機(jī)求解

隨書(shū)軟件為“管理運(yùn)籌學(xué)”2.5版（Window版），是2.0版（DOS版）的升級(jí)版。它包括：線性規(guī)劃、運(yùn)輸問(wèn)題、整數(shù)規(guī)劃（0-1整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對(duì)策論、最短路徑、最小生成樹(shù)、最大流量、最小費(fèi)用最大流、關(guān)鍵路徑、存儲(chǔ)論、排隊(duì)論、決策分析、預(yù)測(cè)問(wèn)題和層次分析法，共15個(gè)子模塊。2可編輯ppt§1“管理運(yùn)籌學(xué)”軟件的操作方法【例1】用軟件求下列線性規(guī)劃的最優(yōu)解1.軟件使用演示：第一步：點(diǎn)擊“開(kāi)始”->“程序”->“管理運(yùn)籌學(xué)2.0”，彈出主窗口。§1“管理運(yùn)籌學(xué)”軟件的操作方法3可編輯ppt本題選用“線性規(guī)劃”4可編輯ppt第二步：選擇所需子模塊，點(diǎn)擊主窗口中的相應(yīng)按鈕。本題中選用“線性規(guī)劃”方法。點(diǎn)擊按鈕彈出如下界面：點(diǎn)擊“新建”按鈕5可編輯ppt輸入變量個(gè)數(shù)輸入約束條件個(gè)數(shù)目標(biāo)函數(shù)點(diǎn)擊“確定”236可編輯ppt點(diǎn)擊“解決”按鈕23max7可編輯ppt8可編輯ppt第五步：分析運(yùn)行結(jié)果。本題中目標(biāo)函數(shù)的最優(yōu)值是27500，x1=50,x2=250。相差值表示相應(yīng)的決策變量的目標(biāo)系數(shù)需要改進(jìn)的數(shù)量，使得決策變量為正值，當(dāng)決策變量已為正數(shù)時(shí)，相差數(shù)為零。“管理運(yùn)籌學(xué)”軟件的輸出信息分析9可編輯ppt松弛/剩余變量的數(shù)值表示還有多少資源沒(méi)有被使用。如果為零，則表示與之相對(duì)應(yīng)的資源已經(jīng)全部用上?！肮芾磉\(yùn)籌學(xué)”軟件的輸出信息分析10可編輯ppt對(duì)偶價(jià)格表示其對(duì)應(yīng)的資源每增加一個(gè)單位，將增加多少個(gè)單位的最優(yōu)值?！肮芾磉\(yùn)籌學(xué)”軟件的輸出信息分析11可編輯ppt目標(biāo)函數(shù)系數(shù)范圍表示最優(yōu)解不變的情況下，目標(biāo)函數(shù)的決策變量系數(shù)的變化范圍。當(dāng)前值是指當(dāng)前的最優(yōu)解中的系數(shù)取值。“管理運(yùn)籌學(xué)”軟件的輸出信息分析12可編輯ppt常數(shù)項(xiàng)范圍是指約束條件的右端常量。上限值和下限值是指當(dāng)約束條件的右端常量在此范圍內(nèi)變化時(shí)，與其對(duì)應(yīng)的約束條件的對(duì)偶價(jià)格不變。當(dāng)前值是指現(xiàn)在的取值?！肮芾磉\(yùn)籌學(xué)”軟件的輸出信息分析13可編輯ppt“管理運(yùn)籌學(xué)”軟件的輸出信息分析【例2】用軟件求下列線性規(guī)劃的最優(yōu)解第一步：點(diǎn)擊“開(kāi)始”->“程序”->“管理運(yùn)籌學(xué)2.0”，彈出主窗口。14可編輯ppt本題選用“線性規(guī)劃”15可編輯ppt第二步：選擇所需子模塊，點(diǎn)擊主窗口中的相應(yīng)按鈕。本題中選用“線性規(guī)劃”方法。點(diǎn)擊按鈕彈出如下界面：點(diǎn)擊“新建”按鈕16可編輯ppt輸入變量個(gè)數(shù)輸入約束條件個(gè)數(shù)目標(biāo)函數(shù)點(diǎn)擊“確定”23min17可編輯ppt18可編輯ppt

“管理運(yùn)籌學(xué)”軟件的輸出信息分析常數(shù)項(xiàng)范圍是指約束條件的右端常量。上限值和下限值是指當(dāng)約束條件的右端常量在此范圍內(nèi)變化時(shí)，與其對(duì)應(yīng)的約束條件的對(duì)偶價(jià)格不變。當(dāng)前值是指現(xiàn)在的取值。

以上計(jì)算機(jī)輸出的目標(biāo)函數(shù)系數(shù)和約束條件右邊值的靈敏度分析都是在其他系數(shù)值不變，只有一個(gè)系數(shù)變化的基礎(chǔ)上得出的！“管理運(yùn)籌學(xué)”軟件的輸出信息分析19可編輯ppt“管理運(yùn)籌學(xué)”軟件的輸出信息分析2.當(dāng)有多個(gè)系數(shù)變化時(shí)，需要進(jìn)一步討論。

百分之一百法則：

對(duì)于所有變化的目標(biāo)函數(shù)決策系數(shù)（約束條件右邊常數(shù)值），當(dāng)其所有允許增加的百分比與允許減少的百分比之和不超過(guò)100%時(shí)，最優(yōu)解不變（對(duì)偶價(jià)格不變，最優(yōu)解仍是原來(lái)幾個(gè)線性方程的解）。

“管理運(yùn)籌學(xué)”軟件的輸出信息分析20可編輯ppt§2“管理運(yùn)籌學(xué)”軟件的輸出信息分析*允許增加量=上限-現(xiàn)在值

c1的允許增加量為100-50=50

b1的允許增加量為325-300=25*允許減少量=現(xiàn)在值-下限

c2的允許減少量為100-50=50

b3的允許減少量為250-200=50*“管理運(yùn)籌學(xué)”軟件的輸出信息分析21可編輯ppt§2“管理運(yùn)籌學(xué)”軟件的輸出信息分析

允許增加的百分比=增加量/允許增加量*允許減少的百分比=減少量/允許減少量例：c1變?yōu)?4,c2變?yōu)?8,則(74-50)/50+(100-78)/50=92%，故最優(yōu)解不變。

b1變?yōu)?15,b3變?yōu)?40,則(315-300)/25+(250-240)/50=80%，故對(duì)偶價(jià)格不變（最優(yōu)解仍是原來(lái)幾個(gè)線性方程的解）?！肮芾磉\(yùn)籌學(xué)”軟件的輸出信息分析22可編輯ppt§2“管理運(yùn)籌學(xué)”軟件的輸出信息分析在使用百分之一百法則進(jìn)行靈敏度分析時(shí)，要注意：1）當(dāng)允許增加量（允許減少量）為無(wú)窮大時(shí)，則對(duì)任意增加量（減少量），其允許增加（減少）百分比均看作0；2）百分之一百法則是充分條件，但非必要條件；也就是說(shuō)超過(guò)100%并不一定變化；3）百分之一百法則不能用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時(shí)變化的情況。這種情況下，只有重新求解?！肮芾磉\(yùn)籌學(xué)”軟件的輸出信息分析23可編輯ppt下面用“管理運(yùn)籌學(xué)”軟件來(lái)分析第二章的例2，其數(shù)學(xué)模型如下：

目標(biāo)函數(shù)：

Minf=2x1+3x2

約束條件：

s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

§2“管理運(yùn)籌學(xué)”軟件的輸出信息分析“管理運(yùn)籌學(xué)”軟件的輸出信息分析24可編輯ppt§2“管理運(yùn)籌學(xué)”軟件的輸出信息分析從上圖可知，當(dāng)購(gòu)進(jìn)原材料A250t，原料B100t時(shí)，購(gòu)進(jìn)成本最低，為800萬(wàn)元。“管理運(yùn)籌學(xué)”軟件的輸出信息分析25可編輯ppt在松弛/剩余變量欄中，約束條件2的值為125，它表示對(duì)原料A的最低需求，即對(duì)A的剩余變量值為125；同理可知約束條件1的剩余變量值為0；約束條件3的松弛變量值為0.在對(duì)偶價(jià)格欄中，約束條件3的對(duì)偶價(jià)格為1萬(wàn)元，也就是說(shuō)如果把加工時(shí)數(shù)從600小時(shí)增加到601小時(shí)，則總成本將得到改進(jìn)，由800萬(wàn)減少到799萬(wàn)。也可知約束條件1的對(duì)偶條件為-4萬(wàn)元，也就是說(shuō)如果把購(gòu)進(jìn)原料A的下限從125t增加到126t，那么總成本將加大，由800萬(wàn)增加到804萬(wàn)。當(dāng)然如果減少對(duì)原料A的下限，那么總成本將得到改進(jìn)。§2“管理運(yùn)籌學(xué)”軟件的輸出信息分析“管理運(yùn)籌學(xué)”軟件的輸出信息分析26可編輯ppt§2“管理運(yùn)籌學(xué)”軟件的輸出信息分析在常數(shù)項(xiàng)范圍一欄中，知道當(dāng)約束條件1的常數(shù)項(xiàng)在300—475范圍內(nèi)變化，且其他約束條件不變時(shí)，約束條件1的對(duì)偶價(jià)格不變；當(dāng)約束條件2的常數(shù)項(xiàng)在負(fù)無(wú)窮到250范圍內(nèi)變化，而其他約束條件的常數(shù)項(xiàng)不變時(shí)，約束條件2的對(duì)偶價(jià)格不變，仍為0；當(dāng)約束條件3的常數(shù)項(xiàng)在475—700內(nèi)變化，而其他約束條件的常數(shù)項(xiàng)不變時(shí)，約束條件3的對(duì)偶價(jià)格不變，仍為1。“管理運(yùn)籌學(xué)”軟件的輸出信息分析27可編輯ppt注意：當(dāng)約束條件中的常數(shù)項(xiàng)增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值增加的數(shù)量稱之為影子價(jià)格。在求目標(biāo)函數(shù)最大時(shí)，當(dāng)約束條件中的常數(shù)項(xiàng)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)值增加的數(shù)量就為改進(jìn)的數(shù)量，所以影子價(jià)格等于對(duì)偶價(jià)格；在求目標(biāo)函數(shù)值最小時(shí)，改進(jìn)的數(shù)量就是減少的數(shù)量，所以影子價(jià)格即為負(fù)的對(duì)偶價(jià)格?！?“管理運(yùn)籌學(xué)”軟件的輸出信息分析“管理運(yùn)籌學(xué)”軟件的輸出信息