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

1、1,第三章 線性規(guī)劃問題的計算機求解,1“管理運籌學”軟件的操作方法 2“管理運籌學”軟件的輸出信息分析,2,第三章 線性規(guī)劃問題的計算機求解,隨書軟件為“管理運籌學”2.5版（Windows版），是“管理運籌學”2.0版（Windows版）的升級版。它包括：線性規(guī)劃、運輸問題、整數(shù)規(guī)劃（0-1整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標規(guī)劃、對策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關鍵路徑、存儲論、排隊論、決策分析、預測問題和層次分析法，共15個子模塊。,3,例1. 目標函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 300 (A)

2、2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E),1“管理運籌學”軟件的操作方法,1.軟件使用演示：（演示例1） 第一步：點擊“開始”-“程序”- “管理運籌學 2.5”，彈出主窗口。,4,1“管理運籌學”軟件的操作方法,第二步：選擇所需子模塊，點擊主窗口中的相應按鈕。本題中選用“線性規(guī)劃”方 法。點擊按鈕彈出如下界面：,5,1“管理運籌學”軟件的操作方法,第三步：點擊“新建”按鈕，輸入數(shù)據(jù)。本題中共有2個變量，3個約束條件，目標函 數(shù)取MAX。點擊“確定”后，在表中輸入Cj,bi和aij等值，并確定變量的正負約束。 輸入數(shù)值后的界面如下。在輸入中要

3、注意以下幾點：輸入的系數(shù)可以是整數(shù)、小 數(shù)，但不能是分數(shù)，要把分數(shù)先化為小數(shù)再輸入；輸入前先要合并同類項。,1“管理運籌學”軟件的操作方法,第四步：點擊“解決”按鈕，得出計算過程。計算過程界面輸出如下。,7,1“管理運籌學”軟件的操作方法,第五步：關閉計算過程界面，得出輸出結果。本題的運行結果界面如下。,在管理運籌學2.5版軟件中,線性規(guī)劃問題的結果輸出部分增加了線性規(guī)劃的逐步運算過程,將使讀者更容易掌握線性規(guī)劃計算的全過程,為方便軟件計算,本線性規(guī)劃使用了大M法以及數(shù)值分析方法。,8,2“管理運籌學”軟件的輸出信息分析,第六步：分析運行結果。 本題中目標函數(shù)的最優(yōu)值是27500，x1=50,

4、 x2=250。 相差值表示相應的決策變量的目標系數(shù)需要改進的數(shù)量，使得決策變量為正值，當決策變量已為正數(shù)時，相差數(shù)為零。 松弛/剩余變量的數(shù)值表示還有多少資源沒有被使用。如果為零，則表示與之相對應的資源已經(jīng)全部用上。 對偶價格表示其對應的資源每增加一個單位，將增加多少個單位的最優(yōu)值。 目標函數(shù)系數(shù)范圍表示最優(yōu)解不變的情況下，目標函數(shù)的決策變量系數(shù)的變化范圍。當前值是指當前的最優(yōu)解中的系數(shù)取值。 常數(shù)項范圍是指約束條件的右端常量。上限值和下限值是指當約束條件的右端常量在此范圍內(nèi)變化時，與其對應的約束條件的對偶價格不變。當前值是指現(xiàn)在的取值。 以上計算機輸出的目標函數(shù)系數(shù)和約束條件右邊值的靈敏度

5、分析都是在其他系數(shù)值不變，只有一個系數(shù)變化的基礎上得出的！,9,2“管理運籌學”軟件的輸出信息分析,當有多個系數(shù)變化時，需要進一步討論。 百分之一百法則：對于所有變化的目標函數(shù)決策系數(shù)（約束條 件右邊常數(shù)值），當其所有允許增加的百分比與允許減少的百分比 之和不超過100%時，最優(yōu)解不變（對偶價格不變，最優(yōu)解仍是原 來幾個線性方程的解）。 * 允許增加量 = 上限 - 現(xiàn)在值 c1 的允許增加量為 100 - 50 = 50 b1 的允許增加量為 325 - 300 = 25 * 允許減少量 = 現(xiàn)在值 - 下限 c2 的允許減少量為 100 - 50 = 50 b3 的允許減少量為 250 -

6、 200 = 50 * 允許增加的百分比 = 增加量 / 允許增加量 * 允許減少的百分比 = 減少量 / 允許減少量,10,2“管理運籌學”軟件的輸出信息分析,例： c1 變?yōu)?74 , c2 變?yōu)?78, 則 (74 - 50) / 50 + (100 - 78 ) / 50 = 92%，故最優(yōu)解不 變。 b1 變?yōu)?315 , b3 變?yōu)?240, 則 (315 - 300) / 25 + (250 - 240 ) / 50 = 80%，故對偶價 格不變（最優(yōu)解仍是原來幾個線性方程的解）。 在使用百分之一百法則進行靈敏度分析時，要注意： 1）當允許增加量（允許減少量）為無窮大時，則對任意

7、增加量（減少量），其允許增加（減少）百分比均看作零； 2）百分之一百法則是充分條件，但非必要條件；也就是說超過100%并不一定變化； 3）百分之一百法則不能用于目標函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時變化的情況。這種情況下，只有重新求解。,11,下面用“管理運籌學”軟件來分析第二章的例2，其數(shù)學模型如下： 目標函數(shù)： Min f = 2x1 + 3 x2 約束條件： s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 從上圖可知，當購進原材料A 250t，原料B 100t時，購進成本最低，為800萬元。,2“管理運籌學”軟件的輸出信息分析,12,

8、在松弛/剩余變量欄中，約束條件2的值為125，它表示對原料A的最低需求，即對A的剩余變量值為125；同理可知約束條件1的剩余變量值為0；約束條件3的松弛變量值為0。 在對偶價格欄中，約束條件3的對偶價格為1萬元，也就是說如果把加工時數(shù)從600小時增加到601小時，則總成本將得到改進，由800萬減少到799萬。也可知約束條件1的對偶條件為-4萬元，也就是說如果把購進原料A和B的總量下限從350t增加到351t，那么總成本將加大，由800萬增加到804萬。當然如果減少對原料A和B的總量的下限，那么總成本將得到改進。 在常數(shù)項范圍一欄中，知道當約束條件1的常數(shù)項在300到475范圍內(nèi)變化，且其他約束條件不變時，約束條件1的對偶價格不變，仍為-4；當約束條件2的常數(shù)項在負無窮到250范圍內(nèi)變化，而其他約束條件的常數(shù)項不變時，約束條件2的對偶價格不變，仍為0；當約束條件3的常數(shù)項在475到700范圍內(nèi)變化，而其他約束條件的常數(shù)項不變時，約束條件3的對偶價格不變，仍為1。,2“管理運籌學”軟件的輸出信息分析,13,注意： 當約束條件中的常數(shù)項增加一個單位時，最優(yōu)目標函數(shù)值增加的數(shù)量稱之為影子價格。在求目標函數(shù)最大時，當約束條件中的常數(shù)項增加一個單位時，目標函數(shù)值增加的數(shù)量就為改進的數(shù)量，所以影子價格等于對偶價格；在求目標函數(shù)值最小時，改進的數(shù)量就是減少的數(shù)量，所以影子價格即為負的對偶價格