第3章線性規(guī)劃問題的計(jì)算機(jī)求解ppt課件

1、管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第三章第三章 線性規(guī)劃問題的計(jì)算機(jī)求解線性規(guī)劃問題的計(jì)算機(jī)求解1“管理運(yùn)籌學(xué)軟件的操作方法2“管理運(yùn)籌學(xué)軟件的輸出信息分析管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)第三章第三章 線性規(guī)劃問題的計(jì)算機(jī)求解線性規(guī)劃問題的計(jì)算機(jī)求解 隨書軟件為“管理運(yùn)籌學(xué)2.0版Window版），是1.0版DOS版的升級(jí)版。它包括：線性規(guī)劃、運(yùn)輸問題、整數(shù)規(guī)劃0-1整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標(biāo)規(guī)劃、對(duì)策論、最短路徑、最小生成樹、最大流量、最小費(fèi)用最大流、關(guān)鍵路徑、存儲(chǔ)論、排隊(duì)論、決策分析、預(yù)測(cè)問題和層次分析法，共15個(gè)子模塊。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)例例1.目標(biāo)函數(shù)：目標(biāo)函數(shù)： Ma

2、x z = 50 x1 + 100 x2 約束條件：約束條件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)1 1“管理運(yùn)籌學(xué)軟件的操作方法管理運(yùn)籌學(xué)軟件的操作方法1.1.軟件使用演示：（演示例軟件使用演示：（演示例1 1）第一步：點(diǎn)擊第一步：點(diǎn)擊“開場(chǎng)開場(chǎng)”-“-“程序程序”- “- “管理運(yùn)籌學(xué)管理運(yùn)籌學(xué)2.0”2.0”，彈出主窗口。，彈出主窗口。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1 1“管理運(yùn)籌學(xué)軟件的操作方法管理運(yùn)籌學(xué)軟件的操作方法第二步：選擇所需子模塊，點(diǎn)擊主窗口中的相應(yīng)按鈕。本題中選用第二步：選擇所

3、需子模塊，點(diǎn)擊主窗口中的相應(yīng)按鈕。本題中選用“線性規(guī)劃線性規(guī)劃方方法。點(diǎn)擊按鈕彈出如下界面：法。點(diǎn)擊按鈕彈出如下界面：管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1 1“管理運(yùn)籌學(xué)軟件的操作方法管理運(yùn)籌學(xué)軟件的操作方法第三步：點(diǎn)擊第三步：點(diǎn)擊“新建按鈕，輸入數(shù)據(jù)。本題中共有新建按鈕，輸入數(shù)據(jù)。本題中共有2個(gè)變量，個(gè)變量，4個(gè)約束條件，目個(gè)約束條件，目標(biāo)函標(biāo)函數(shù)取數(shù)取MAX。點(diǎn)擊。點(diǎn)擊“確定后，在表中輸入確定后，在表中輸入Cj,bi和和aij等值，并確定變量的正負(fù)約束。等值，并確定變量的正負(fù)約束。輸入數(shù)值后的界面如下。輸入數(shù)值后的界面如下。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)1 1“管理運(yùn)籌學(xué)軟件的操作方法管理運(yùn)籌學(xué)軟

4、件的操作方法第四步：點(diǎn)擊第四步：點(diǎn)擊“處置按鈕，得出計(jì)算結(jié)果。本題的運(yùn)行結(jié)果界面如下。處置按鈕，得出計(jì)算結(jié)果。本題的運(yùn)行結(jié)果界面如下。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2“管理運(yùn)籌學(xué)軟件的輸出信息分管理運(yùn)籌學(xué)軟件的輸出信息分析析第五步：分析運(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ù)為零。松弛/剩余變量的數(shù)值表示還有多少資源沒有被使用。如果為零，則表示與之相對(duì)應(yīng)的資源已經(jīng)全部用上。對(duì)偶價(jià)格表示其對(duì)應(yīng)的資源每增加一個(gè)單位，將增加多少個(gè)單位的最優(yōu)值。目標(biāo)函數(shù)系數(shù)范圍表示最優(yōu)

5、解不變的情況下，目標(biāo)函數(shù)的決策變量系數(shù)的變化范圍。當(dāng)前值是指當(dāng)前的最優(yōu)解中的系數(shù)取值。常數(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)運(yùn) 籌籌 學(xué)學(xué)2 2“管理運(yùn)籌學(xué)軟件的輸出信息分管理運(yùn)籌學(xué)軟件的輸出信息分析析2.當(dāng)有多個(gè)系數(shù)變化時(shí)，需要進(jìn)一步討論。 百分之一百法則：對(duì)于所有變化的目標(biāo)函數(shù)決策系數(shù)約束條件右邊常數(shù)值），當(dāng)其所有允許增加的百分比與允許減少的百分比之和不超過

6、100%時(shí)，最優(yōu)解不變對(duì)偶價(jià)格不變，最優(yōu)解仍是原來幾個(gè)線性方程的解）。 * 允許增加量 = 上限 - 現(xiàn)在值 c1 的允許增加量為 100 - 50 = 50 b1 的允許增加量為 325 - 300 = 25 * 允許減少量 = 現(xiàn)在值 - 下限 c2 的允許減少量為 100 - 50 = 50 b3 的允許減少量為 250 - 200 = 50 * 允許增加的百分比 = 增加量 / 允許增加量 * 允許減少的百分比 = 減少量 / 允許減少量 管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)2 2“管理運(yùn)籌學(xué)軟件的輸出信息分管理運(yùn)籌學(xué)軟件的輸出信息分析析 例：例： c1 變?yōu)樽優(yōu)?74 , c2 變?yōu)樽優(yōu)?7

7、8, 那么那么 (74 - 50) / 50 + (100 - 78 ) / 50 = 92%，故最優(yōu)解不，故最優(yōu)解不變。變。 b1 變?yōu)樽優(yōu)?315 , b3 變?yōu)樽優(yōu)?240, 那么那么 (315 - 50) / 25 + (250 - 240 ) / 50 = 80%，故對(duì)偶價(jià)，故對(duì)偶價(jià)格不變最優(yōu)解仍是原來幾個(gè)線性方程的解）。格不變最優(yōu)解仍是原來幾個(gè)線性方程的解）。在使用百分之一百法則進(jìn)行靈敏度分析時(shí)，要注意：在使用百分之一百法則進(jìn)行靈敏度分析時(shí)，要注意：1當(dāng)允許增加量允許減少量為無窮大時(shí)，則對(duì)任意增加量減少量），其允許增加減少百分比均當(dāng)允許增加量允許減少量為無窮大時(shí)，則對(duì)任意增加量減少

8、量），其允許增加減少百分比均看作看作0；2百分之一百法則是充分條件，但非必要條件；也就是說超過百分之一百法則是充分條件，但非必要條件；也就是說超過100%并不一定變化；并不一定變化；3百分之一百法則不能用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時(shí)變化的情況。這種情況下，百分之一百法則不能用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時(shí)變化的情況。這種情況下，只有重新求解。只有重新求解。管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 下面用“管理運(yùn)籌學(xué)軟件來分析第二章的例2，其數(shù)學(xué)模型如下： 目標(biāo)函數(shù)： Min f = 2x1 + 3 x2 約束條件： s.t. x1 + x2 350 x1 125 2 x1

9、 + x2 600 x1 , x2 0 從上圖可知，當(dāng)購(gòu)進(jìn)原材料A 250t，原料B 100t時(shí)，購(gòu)進(jìn)成本最低，為800萬元。2 2“管理運(yùn)籌學(xué)軟件的輸出信息分管理運(yùn)籌學(xué)軟件的輸出信息分析析管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué) 在松弛/剩余變量欄中，約束條件2的值為125，它表示對(duì)原料A的最低需求，即對(duì)A的剩余變量值為125；同理可知約束條件1的剩余變量值為0；約束條件3的松弛變量值為0。 在對(duì)偶價(jià)格欄中，約束條件3的對(duì)偶價(jià)格為1萬元，也就是說如果把加工時(shí)數(shù)從600小時(shí)增加到601小時(shí)，則總成本將得到改進(jìn)，由800萬減少到799萬。也可知約束條件1的對(duì)偶條件為-4萬元，也就是說如果把購(gòu)進(jìn)原料A的下限從

10、125t增加到126t，那么總成本將加大，由800萬增加到804萬。當(dāng)然如果減少對(duì)原料A的下限，那么總成本將得到改進(jìn)。 在常數(shù)項(xiàng)范圍一欄中，知道當(dāng)約束條件1的常數(shù)項(xiàng)在300475范圍內(nèi)變化，且其他約束條件不變時(shí)，約束條件1的對(duì)偶價(jià)格不變；當(dāng)約束條件2的常數(shù)項(xiàng)在負(fù)無窮到250范圍內(nèi)變化，而其他約束條件的常數(shù)項(xiàng)不變時(shí)，約束條件2的對(duì)偶價(jià)格不變，仍為0；當(dāng)約束條件3的常數(shù)項(xiàng)在475700內(nèi)變化，而其他約束條件的常數(shù)項(xiàng)不變時(shí)，約束條件3的對(duì)偶價(jià)格不變，仍為1。2 2“管理運(yùn)籌學(xué)軟件的輸出信息分管理運(yùn)籌學(xué)軟件的輸出信息分析析管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)注意：當(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ù)量，所以影