運籌學第3章線性規(guī)劃問題的計算機求解課件

第三章

線性規(guī)劃問題的計算機求解§1“管理運籌學”軟件的操作方法§2“管理運籌學”軟件的輸出信息分析1第三章

線性規(guī)劃問題的計算機求解§1“管理運籌學”軟件第三章

線性規(guī)劃問題的計算機求解

隨書軟件為“管理運籌學”2.5版（Window版），是2.0版（DOS版）的升級版。它包括：線性規(guī)劃、運輸問題、整數規(guī)劃（0-1整數規(guī)劃、純整數規(guī)劃和混合整數規(guī)劃）、目標規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關鍵路徑、存儲論、排隊論、決策分析、預測問題和層次分析法，共15個子模塊。2第三章

線性規(guī)劃問題的計算機求解§1“管理運籌學”軟件的操作方法【例1】用軟件求下列線性規(guī)劃的最優(yōu)解1.軟件使用演示：第一步：點擊“開始”->“程序”->“管理運籌學2.0”，彈出主窗口?！?“管理運籌學”軟件的操作方法3§1“管理運籌學”軟件的操作方法【例1】用軟件求下列線性規(guī)本題選用“線性規(guī)劃”4本題選用“線性規(guī)劃”4第二步：選擇所需子模塊，點擊主窗口中的相應按鈕。本題中選用“線性規(guī)劃”方法。點擊按鈕彈出如下界面：點擊“新建”按鈕5第二步：選擇所需子模塊，點擊主窗口中的相應按鈕。本題中選用“輸入變量個數輸入約束條件個數目標函數點擊“確定”236輸入變量個數輸入約束目標函數點擊“確定”236點擊“解決”按鈕23max7點擊“解決”按鈕23max788第五步：分析運行結果。本題中目標函數的最優(yōu)值是27500，x1=50,x2=250。相差值表示相應的決策變量的目標系數需要改進的數量，使得決策變量為正值，當決策變量已為正數時，相差數為零?！肮芾磉\籌學”軟件的輸出信息分析9第五步：分析運行結果。相差值表示相應“管理運籌學”軟件的輸出松弛/剩余變量的數值表示還有多少資源沒有被使用。如果為零，則表示與之相對應的資源已經全部用上。“管理運籌學”軟件的輸出信息分析10松弛/剩余變量的數值表示還有多少資源沒有被使用。“管理運籌學對偶價格表示其對應的資源每增加一個單位，將增加多少個單位的最優(yōu)值?！肮芾磉\籌學”軟件的輸出信息分析11對偶價格表示其對應的資源每增加一個單位，“管理運籌學”軟件的目標函數系數范圍表示最優(yōu)解不變的情況下，目標函數的決策變量系數的變化范圍。當前值是指當前的最優(yōu)解中的系數取值?！肮芾磉\籌學”軟件的輸出信息分析12目標函數系數范圍表示最優(yōu)解不變的情況下，“管理運籌學”軟件的常數項范圍是指約束條件的右端常量。上限值和下限值是指當約束條件的右端常量在此范圍內變化時，與其對應的約束條件的對偶價格不變。當前值是指現在的取值?！肮芾磉\籌學”軟件的輸出信息分析13常數項范圍是指約束條件的右端常量。上限值和下限值是指當“管理“管理運籌學”軟件的輸出信息分析【例2】用軟件求下列線性規(guī)劃的最優(yōu)解第一步：點擊“開始”->“程序”->“管理運籌學2.0”，彈出主窗口。14“管理運籌學”軟件的輸出信息分析【例2】用軟件求下列線性規(guī)劃本題選用“線性規(guī)劃”15本題選用“線性規(guī)劃”15第二步：選擇所需子模塊，點擊主窗口中的相應按鈕。本題中選用“線性規(guī)劃”方法。點擊按鈕彈出如下界面：點擊“新建”按鈕16第二步：選擇所需子模塊，點擊主窗口中的相應按鈕。本題中選用“輸入變量個數輸入約束條件個數目標函數點擊“確定”23min17輸入變量個數輸入約束目標函數點擊“確定”23min171818

“管理運籌學”軟件的輸出信息分析常數項范圍是指約束條件的右端常量。上限值和下限值是指當約束條件的右端常量在此范圍內變化時，與其對應的約束條件的對偶價格不變。當前值是指現在的取值。

以上計算機輸出的目標函數系數和約束條件右邊值的靈敏度分析都是在其他系數值不變，只有一個系數變化的基礎上得出的！“管理運籌學”軟件的輸出信息分析19“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸出信“管理運籌學”軟件的輸出信息分析2.當有多個系數變化時，需要進一步討論。

百分之一百法則：

對于所有變化的目標函數決策系數（約束條件右邊常數值），當其所有允許增加的百分比與允許減少的百分比之和不超過100%時，最優(yōu)解不變（對偶價格不變，最優(yōu)解仍是原來幾個線性方程的解）。

“管理運籌學”軟件的輸出信息分析20“管理運籌學”軟件的輸出信息分析2.當有多個系數變化時，需要§2“管理運籌學”軟件的輸出信息分析*允許增加量=上限-現在值

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

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

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

b3的允許減少量為250-200=50*“管理運籌學”軟件的輸出信息分析21§2“管理運籌學”軟件的輸出信息分析*允許增加量=§2“管理運籌學”軟件的輸出信息分析

允許增加的百分比=增加量/允許增加量*允許減少的百分比=減少量/允許減少量例：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%，故對偶價格不變（最優(yōu)解仍是原來幾個線性方程的解）?！肮芾磉\籌學”軟件的輸出信息分析22§2“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸§2“管理運籌學”軟件的輸出信息分析在使用百分之一百法則進行靈敏度分析時，要注意：1）當允許增加量（允許減少量）為無窮大時，則對任意增加量（減少量），其允許增加（減少）百分比均看作0；2）百分之一百法則是充分條件，但非必要條件；也就是說超過100%并不一定變化；3）百分之一百法則不能用于目標函數決策變量系數和約束條件右邊常數值同時變化的情況。這種情況下，只有重新求解?！肮芾磉\籌學”軟件的輸出信息分析23§2“管理運籌學”軟件的輸出信息分析在使用百分之一百法則進下面用“管理運籌學”軟件來分析第二章的例2，其數學模型如下：

目標函數：

Minf=2x1+3x2

約束條件：

s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

§2“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸出信息分析24下面用“管理運籌學”軟件來分析第二章的例2，其數學模型如下：§2“管理運籌學”軟件的輸出信息分析從上圖可知，當購進原材料A250t，原料B100t時，購進成本最低，為800萬元?！肮芾磉\籌學”軟件的輸出信息分析25§2“管理運籌學”軟件的輸出信息分析從上圖可知，當購進原材在松弛/剩余變量欄中，約束條件2的值為125，它表示對原料A的最低需求，即對A的剩余變量值為125；同理可知約束條件1的剩余變量值為0；約束條件3的松弛變量值為0.在對偶價格欄中，約束條件3的對偶價格為1萬元，也就是說如果把加工時數從600小時增加到601小時，則總成本將得到改進，由800萬減少到799萬。也可知約束條件1的對偶條件為-4萬元，也就是說如果把購進原料A的下限從125t增加到126t，那么總成本將加大，由800萬增加到804萬。當然如果減少對原料A的下限，那么總成本將得到改進。§2“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸出信息分析26§2“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸§2“管理運籌學”軟件的輸出信息分析在常數項范圍一欄中，知道當約束條件1的常數項在300—475范圍內變化，且其他約束條件不變時，約束條件1的對偶價格不變；當約束條件2的常數項在負無窮到250范圍內變化，而其他約束條件的常數項不變時，約束條件2的對偶價格不變，仍為0；當約束條件3的常數項在475—700內變化，而其他約束條件的常數項不變時，約束條件3的對偶價格不變，仍為1。“管理運籌學”軟件的輸出信息分析27§2“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸注意：當約束條件中的常數項增加一個單位時，最優(yōu)目標函數值增加的數量稱之為影子價格。在求目標函數最大時，當約束條件中的常數項增加一個單位時，目標函數值增加的數量就為改進的數量，所以影子價格等于對偶價格；在求目標函數值最小時，改進的數量就是減少的數量，所以影子價格即為負的對偶價格?！?“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸出信息分析28注意：§2“管理運籌學”軟件的輸出信息分析“管理運籌學”軟§2“管理運籌學”軟件的輸出信息分析2.“管理運籌學”軟件可以解決含有100個變量50個約束方程的線性規(guī)劃問題，可以解決工商管理中大量的問題。如果想要解決更大的線性規(guī)劃問題，可以使用由芝加哥大學的L.E.Schrage開發(fā)的Lindo計算機軟件包的微型計算機版本Lindo/PC。“管理運籌學”軟件的輸出信息分析29§2“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸第三章

線性規(guī)劃問題的計算機求解§1“管理運籌學”軟件的操作方法§2“管理運籌學”軟件的輸出信息分析30第三章

線性規(guī)劃問題的計算機求解§1“管理運籌學”軟件第三章

線性規(guī)劃問題的計算機求解

隨書軟件為“管理運籌學”2.5版（Window版），是2.0版（DOS版）的升級版。它包括：線性規(guī)劃、運輸問題、整數規(guī)劃（0-1整數規(guī)劃、純整數規(guī)劃和混合整數規(guī)劃）、目標規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關鍵路徑、存儲論、排隊論、決策分析、預測問題和層次分析法，共15個子模塊。31第三章

線性規(guī)劃問題的計算機求解§1“管理運籌學”軟件的操作方法【例1】用軟件求下列線性規(guī)劃的最優(yōu)解1.軟件使用演示：第一步：點擊“開始”->“程序”->“管理運籌學2.0”，彈出主窗口?！?“管理運籌學”軟件的操作方法32§1“管理運籌學”軟件的操作方法【例1】用軟件求下列線性規(guī)本題選用“線性規(guī)劃”33本題選用“線性規(guī)劃”4第二步：選擇所需子模塊，點擊主窗口中的相應按鈕。本題中選用“線性規(guī)劃”方法。點擊按鈕彈出如下界面：點擊“新建”按鈕34第二步：選擇所需子模塊，點擊主窗口中的相應按鈕。本題中選用“輸入變量個數輸入約束條件個數目標函數點擊“確定”2335輸入變量個數輸入約束目標函數點擊“確定”236點擊“解決”按鈕23max36點擊“解決”按鈕23max7378第五步：分析運行結果。本題中目標函數的最優(yōu)值是27500，x1=50,x2=250。相差值表示相應的決策變量的目標系數需要改進的數量，使得決策變量為正值，當決策變量已為正數時，相差數為零。“管理運籌學”軟件的輸出信息分析38第五步：分析運行結果。相差值表示相應“管理運籌學”軟件的輸出松弛/剩余變量的數值表示還有多少資源沒有被使用。如果為零，則表示與之相對應的資源已經全部用上?！肮芾磉\籌學”軟件的輸出信息分析39松弛/剩余變量的數值表示還有多少資源沒有被使用?！肮芾磉\籌學對偶價格表示其對應的資源每增加一個單位，將增加多少個單位的最優(yōu)值。“管理運籌學”軟件的輸出信息分析40對偶價格表示其對應的資源每增加一個單位，“管理運籌學”軟件的目標函數系數范圍表示最優(yōu)解不變的情況下，目標函數的決策變量系數的變化范圍。當前值是指當前的最優(yōu)解中的系數取值?！肮芾磉\籌學”軟件的輸出信息分析41目標函數系數范圍表示最優(yōu)解不變的情況下，“管理運籌學”軟件的常數項范圍是指約束條件的右端常量。上限值和下限值是指當約束條件的右端常量在此范圍內變化時，與其對應的約束條件的對偶價格不變。當前值是指現在的取值?！肮芾磉\籌學”軟件的輸出信息分析42常數項范圍是指約束條件的右端常量。上限值和下限值是指當“管理“管理運籌學”軟件的輸出信息分析【例2】用軟件求下列線性規(guī)劃的最優(yōu)解第一步：點擊“開始”->“程序”->“管理運籌學2.0”，彈出主窗口。43“管理運籌學”軟件的輸出信息分析【例2】用軟件求下列線性規(guī)劃本題選用“線性規(guī)劃”44本題選用“線性規(guī)劃”15第二步：選擇所需子模塊，點擊主窗口中的相應按鈕。本題中選用“線性規(guī)劃”方法。點擊按鈕彈出如下界面：點擊“新建”按鈕45第二步：選擇所需子模塊，點擊主窗口中的相應按鈕。本題中選用“輸入變量個數輸入約束條件個數目標函數點擊“確定”23min46輸入變量個數輸入約束目標函數點擊“確定”23min174718

“管理運籌學”軟件的輸出信息分析常數項范圍是指約束條件的右端常量。上限值和下限值是指當約束條件的右端常量在此范圍內變化時，與其對應的約束條件的對偶價格不變。當前值是指現在的取值。

以上計算機輸出的目標函數系數和約束條件右邊值的靈敏度分析都是在其他系數值不變，只有一個系數變化的基礎上得出的！“管理運籌學”軟件的輸出信息分析48“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸出信“管理運籌學”軟件的輸出信息分析2.當有多個系數變化時，需要進一步討論。

百分之一百法則：

對于所有變化的目標函數決策系數（約束條件右邊常數值），當其所有允許增加的百分比與允許減少的百分比之和不超過100%時，最優(yōu)解不變（對偶價格不變，最優(yōu)解仍是原來幾個線性方程的解）。

“管理運籌學”軟件的輸出信息分析49“管理運籌學”軟件的輸出信息分析2.當有多個系數變化時，需要§2“管理運籌學”軟件的輸出信息分析*允許增加量=上限-現在值

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

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

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

b3的允許減少量為250-200=50*“管理運籌學”軟件的輸出信息分析50§2“管理運籌學”軟件的輸出信息分析*允許增加量=§2“管理運籌學”軟件的輸出信息分析

允許增加的百分比=增加量/允許增加量*允許減少的百分比=減少量/允許減少量例：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%，故對偶價格不變（最優(yōu)解仍是原來幾個線性方程的解）?！肮芾磉\籌學”軟件的輸出信息分析51§2“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸§2“管理運籌學”軟件的輸出信息分析在使用百分之一百法則進行靈敏度分析時，要注意：1）當允許增加量（允許減少量）為無窮大時，則對任意增加量（減少量），其允許增加（減少）百分比均看作0；2）百分之一百法則是充分條件，但非必要條件；也就是說超過100%并不一定變化；3）百分之一百法則不能用于目標函數決策變量系數和約束條件右邊常數值同時變化的情況。這種情況下，只有重新求解?！肮芾磉\籌學”軟件的輸出信息分析52§2“管理運籌學”軟件的輸出信息分析在使用百分之一百法則進下面用“管理運籌學”軟件來分析第二章的例2，其數學模型如下：

目標函數：

Minf=2x1+3x2

約束條件：

s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

§2“管理運籌學”軟件的輸出信息分析“管理運籌學”軟件的輸出信息分析53下面用“管理運籌學”軟件來分析第二章的例2，其數學模型如下：§2“管理運籌學”軟件的輸出信息分析從上圖可知，當購進原材料A250t，原料B100t時，購進成本最低，為800萬元。“管理運籌學”軟件的輸出信息分析54§2“管理運籌學”軟件的輸出信息分析從上圖可知，當購進原材在松弛/剩余變量欄中，約束條件2的值為125，它表示對原料A的最低需求，即對A的剩余變量值為125；同理可知約束條件1的剩余變量值為0；約束條件3的松弛變量值為0.在對偶價格欄中，約束條件3的對偶價格為1萬元，也就是說如果把加工時數從600小時增加到601小時，則