1、Linear Programming,運 籌 學 課 件,線 性 規(guī) 劃,線性規(guī)劃問題 可行區(qū)域與基本可行解 單純形算法 初始可行解 對偶理論 靈敏度分析 計算軟件 案例分析,線 性 規(guī) 劃 問 題,線性規(guī)劃實例 生產計劃問題 運輸問題 線性規(guī)劃模型 一般形式 規(guī)范形式 標準形式 形式轉換 概念,某工廠用三種原料生產三種產品，已知的條件如表2.1.1所示，試制訂總利潤最大的生產計劃,生 產 計 劃 問 題,問 題 分 析,模 型,計 算 結 果,運 輸 問 題,問 題 分 析,模 型,一 般 形 式,目標函數,約束條件,注 釋,規(guī) 范 形 式,標 準 形 式,概 念,模 型 轉 換,約束轉換

2、實例,目標轉換,變量轉換,約 束 轉 換,不等式變等式 不等式變不等式,等式變不等式,不 等 式 變 等 式,松弛變量,剩余變量,不等式變不等式,例2.1.3 把問題轉化為標準形式,可行區(qū)域與基本可行解,圖解法 可行域的幾何結構 基本可行解與基本定理,圖 解 法,例2.2.1 解線性規(guī)劃,注 釋,可能出現的情況： 可行域是空集 可行域無界無最優(yōu)解 最優(yōu)解存在且唯一，則一定在頂點上達到 最優(yōu)解存在且不唯一，一定存在頂點是最優(yōu)解,可行域的幾何結構,基本假設 凸集 可行域的凸性,基 本 假 設,凸 集,可 行 域 的 凸 性,問 題,基 本 可 行 解 與 基 本 定 理,定義 基本定理 問題,基

3、本 可 行 解 定 義,基 本 定 理,問 題,單 純 形 算 法,理論方法 算法步驟 單純形表 算例,理 論 方 法,定理2.3.1,定 理 2.3.2,定 理 2.3.3,算 法 步 驟,單 純 形 表,算 例,初 始 單 純 形 表,迭 代 1,迭 代 2,初 始 解,兩階段法 大M法 說明,兩 階 段 法,基本思想 第一階段：通過求解輔助問題的最優(yōu)基可行 解得到原問題的初始基可行解。 第二階段：求原問題的最優(yōu)解 算例,輔 助 問 題,原 輔 助 題 問 與 題 的 關 系,求 輔 助 問 題 的 三 種 情 況,算 例,第 1 階 段,第 1 階 段,第 1 階 段,第 1 階 段,第

4、 1 階 段,第 2 階 段,大 M 法,說 明,對 偶 理 論,對偶規(guī)劃 對偶理論 對偶單純形算法,對 偶 規(guī) 劃,標準形式線性規(guī)劃的對偶規(guī)劃 規(guī)范形式線性規(guī)劃的對偶規(guī)劃 一般形式線性規(guī)劃的對偶規(guī)劃 實例,標準形式的對偶規(guī)劃,規(guī) 范 形 式 的 對 偶 規(guī) 劃,一般形式的對偶規(guī)劃,實 例,對 偶 理 論,定 理 2.5.1,定 理 2.5.2,定 理 2.5.5,對偶單純形算法,基本思想 算法過程 算例,基 本 思 想,單 純 形 算 法,對 偶 單 純 形,正 則 解,正則解,對偶可行解,正則解的單純性表,規(guī)劃無可行解,保持正則性,入基變量,否,算 法 過 程,初始正則解,是則停止,得最優(yōu)

5、解,選出基變量,檢查 是否無可 行解,是則停止,否,無最優(yōu)解,選入基變量,計算典式檢驗數,算 例,迭 代,迭 代,迭 代,靈 敏 度 分 析,概況 改變價值向量 改變右端向量,概 況,信息的不確定性 信息的變化： 價值向量市場變化 右端向量資源變化 系數矩陣技術進步 認知的誤差 分析方法 靜態(tài)分析- 比較靜態(tài)分析-動態(tài)分析,改變價值向量,一般改變情況 改變非基變量的價值向量 改變基變量的價值向量 算例,一 般 改 變,非 基 變 量,基 變 量,算 例,改變右端向量,基本思想 算例,基 本 思 想,算 例,計 算 軟 件,LinDo LinGo Matlab,LinDo,輸入模型 求解 點擊求

6、解按鈕 即可 結果,輸 入 模 型,!注釋內容，可用中文 !目標函數：最大-max,最小-min,大小寫不分 max 3 x1+5 x2+4 x3 !約束，以subject to開始 subject to 2 x1+3 x2=1500 2 x2+4 x3=800 3 x1+2 x2 +5 x3=2000 end,注 意 事 項,變量以字母開頭，下標寫在后面，系數與邊量之間加空格 不等號為:=( ) , =, =與 等同 變量非負約束可省略 結束時以end標示,結 果,LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 2675.000

7、VARIABLE VALUE REDUCED COST X1 375.000000 0.000000 X2 250.000000 0.000000 X3 75.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.050000 3) 0.000000 0.625000 4) 0.000000 0.300000,LinGo,輸入模型 LinDo模式 LinGo模式 求解 點擊求解按鈕 即可 結果,LinDo 輸 入 模 式,model: MAX=3*x1+5*x2+4*x3; 2*x1+3*x2=1500; 2*x2+4*x

8、3=800; 3*x1+2*x2+5*x3=2000; end,注意與LinDo的區(qū)別,目標函數中加等號 變量與系數之間用“*” Model:-end可省略,LinGo 模式,集 合 部 分,model: ！開始 sets: ！定義集合 ve/1.3/:c,x; co/1.3/:b; ma(co,ve):a; endsets ！注：集表達式：名稱/成員/：屬性 名稱（初始集）：屬性,定 義 數 據,data:！定義數據 c=3 5 4; b=1500 800 2000; a=2 3 0 0 2 4 3 2 5; Enddata ！注：數據的大小與集合定義中一致，分量中間用空格或逗號分開，數據結

9、束后用分號；,調 用 函 數,max=sum(ve(j):c(j)*x(j); for(co(i):sum(ve(j):a(i,j)*x(j)=b(i); 主要函數： for(set(set_index_list)|condition:expression) sum(set(set_index_list)|condition:expression) min(max)(set(set_index_list)|condition:expression),結 果,Global optimal solution found at iteration: 3 Objective value: 2675.0

10、00 Variable Value Reduced Cost C( 1) 3.000000 0.000000 C( 2) 5.000000 0.000000 C( 3) 4.000000 0.000000 X( 1) 375.0000 0.000000 X( 2) 250.0000 0.000000 X( 3) 75.00000 0.000000,B( 1) 1500.000 0.000000 B( 2) 800.0000 0.000000 B( 3) 2000.000 0.000000 A( 1, 1) 2.000000 0.000000 A( 1, 2) 3.000000 0.000000

11、 A( 1, 3) 0.000000 0.000000 A( 2, 1) 0.000000 0.000000 A( 2, 2) 2.000000 0.000000 A( 2, 3) 4.000000 0.000000 A( 3, 1) 3.000000 0.000000 A( 3, 2) 2.000000 0.000000 A( 3, 3) 5.000000 0.000000,Row Slack or Surplus Dual Price 1 2675.000 1.000000 2 0.000000 1.050000 3 0.000000 0.6250000 4 0.000000 0.3000

12、000,Scilab 函數,命令1：x,lagr,f=linpro(p,C,b ,x0) 命令2：x,lagr,f=linpro(p,C,b,ci,cs ,x0) 命令3：x,lagr,f=linpro(p,C,b,ci,cs,me ,x0) 命令4：x,lagr,f=linpro(p,C,b,ci,cs,me,x0 ,imp) 命令5： x1,crit=karmarkar(a,b,c,x0) 注意事項,命令1,問題形式 min p*x s.t. C*x = b,x,lagr,f=linpro(p,C,b ,x0）,命 令 2,命 令 3,命 令 4,x,lagr,f=linpro(p,C,b

13、,ci,cs,me,x0 ,imp) 問題形式 min p*x s.t. C(j,:) x = b(j), j=1,.,me C(j,:) x = b(j), j=me+1,.,me+md ci = x = cs 指定初始可行解x0,命 令 5,x1,crit=karmarkar(a,b,c,x0) 問題形式 min c*x s.t. a*x = b x=0,注 意 事 項,命令2和3中x0可省略，但命令4和5中不可省略 向量都是列向量，參數的順序不可換 命令3中等式約束必須在前面,人力資源分配問題,某個中型百貨商場對售貨人員（周工資200元）的需求經統計如下表 為了保證銷售人員充分休息，銷售

14、人員每周工作5天，休息2天。問應如何安排銷售人員的工作時間，使得所配售貨人員的總費用最??？,模 型 假 設,每天工作8小時，不考慮夜班的情況； 每個人的休息時間為連續(xù)的兩天時間； 每天安排的人員數不得低于需求量，但可以超過需求量,問 題 分 析,因素：不可變因素：需求量、休息時間、單位費用；可變因素：安排的人數、每人工作的時間、總費用； 方案：確定每天工作的人數，由于連續(xù)休息2天，當確定每個人開始休息的時間就等于知道工作的時間，因而確定每天開始休息的人數就知道每天開始工作的人數，從而求出每天工作的人數。 變量：每天開始休息的人數 約束條件 ： 1.每人休息時間2天，自然滿足。 2. 每天工作人數不低于需求量，第i天工作的人數就是從第i-2天往前數5天內開始工作的人數，所以有約束：,3.變量非負約束：,目標函數：總費用最小，總費用與使 用的總人數成正比。由于每個人必然在 且僅在某一天開始休息，所以總人數等 于,模 型,計 算,注 解,該問題本質上是個整數規(guī)劃問題，放松的線性規(guī)劃的最優(yōu)解是個整數解，所以兩規(guī)劃等價。 定義整數變量用函數gin(x1) gin(x7); 0-1整數變量為bin(x1),配 料 問 題,某化工廠要用三中原料混合配置 三種不同規(guī)格的產品各產品的規(guī)格 單價如表1，,問如何安排生產使得生產利潤最大？,原料的單價與每天最大供應量如表2,配 料 問