數學建模常見模型學習筆記——線性規劃

在人們(men) 的生產(chan) 實踐中，經常會(hui) 遇到如何利用現有資源來安排生產(chan) ，以取得最大經濟效益的問題。 此類問題構成了運籌學的一個(ge) 重要分支—數學規劃，而線性規劃(Linear Programming 簡記 LP)則是數學規劃的一個(ge) 重要分支。

線性規劃的 Matlab 標準形式

線性規劃的目標函數可以是求最大值，也可以是求最小值，約束條件的不等號可以是小於(yu) 號也可以是大於(yu) 號。為(wei) 了避免這種形式多樣性帶來的不便，Matlab 中規定線性規劃的標準形式為(wei)

其中 c 和 x 為(wei) n 維列向量， A 、 Aeq 為(wei) 適當維數的矩陣， b 、 beq 為(wei) 適當維數的列向量。

線性規劃模型的特點

優(you) 點

有統一算法，任何線性規劃問題都能求解，解決(jue) 多變量最優(you) 決(jue) 策的方法。

缺點

對於(yu) 數據的準確性要求高，隻能對線性的問題進行規劃約束，而且計算量大，有由線性規劃演變的非線性規劃法等等後續的方法彌補，但是計算量增加許多。

例題實戰

 線性規劃常用於(yu) 運輸問題(產(chan) 銷平衡)、指派問題（匈牙利算法）、對偶理論與(yu) 靈敏度分析、投資的收益和風險等。接下來讓我們(men) 通過幾個(ge) 具體(ti) 實例來體(ti) 會(hui) “線性規劃”在建模方麵的實際應用。

運輸問題

例：

某商品有m個(ge) 產(chan) 地，n個(ge) 銷地，各產(chan) 地的產(chan) 量分別為(wei) a1，…，am，各銷地的需求量分別為(wei) b1，…，bm。若該商品由i產(chan) 地運到j銷地的單位運價(jia) 為(wei) c（ij），問應該如何調運才能使總運費最省？

01、產(chan) 銷平衡

存在產(chan) 銷平衡問題（當有也有生產(chan) 與(yu) 銷售量不平衡的情況），實際上不平衡的運輸問題可以轉換成平衡型的問題。通過虛設一個(ge) 產(chan) 地或銷售地並令運輸成本為(wei) 0。

02、解

當產(chan) 量等於(yu) 銷售量的時候有可行解且必有最優(you) 解。並且若產(chan) 量與(yu) 銷售量均為(wei) 整數時，必存在決(jue) 策變量均是整數的解。

03、表上作業(ye) 法

其約束條件的係數矩陣相當特殊，可用比較簡單的計算方法，習(xi) 慣上稱為(wei) 表上作業(ye) 法（由康托洛維奇和希奇柯克兩(liang) 人獨立地提出，簡稱康—希表上作業(ye) 法）。

指派問題

例：

擬分配n人去幹n項工作，每人幹且僅(jin) 幹一項工作，若分配第i人去幹第j項工作，需花費C(ij)單位時間，問應如何分配工作才能使工人花費的總時間最少？

01、矩陣表示法

指派問題的可行解可以用一個(ge) 矩陣表示，其每行每列均有且隻有一個(ge) 元素為(wei) 1，其餘(yu) 元素均為(wei) 0；問題中的變量隻能取 0 或1，從(cong) 而是一個(ge) 0-1 規劃問題。一般的0-1 規劃問題求解極為(wei) 困難。但指派問題並不難解，其約束方程組的係數矩陣十分特殊（被稱為(wei) 全單位模矩陣，其各階非零子式均為(wei) ±1），其非負可行解的分量隻能取 0或 1，故約束xijxij = 0或1可改寫(xie) 為(wei) xijxij≥ 0而不改變其解。此時，指派問題被轉化為(wei) 一個(ge) 特殊的運輸問題。

02、費藥類

由於(yu) 指派問題的特殊性，又存在著由匈牙利數學家 Konig 提出的更為(wei) 簡便的解法—匈牙利算法。算法主要依據:如果係數矩陣 C=(cij)C=(cij)一行（或一列）中每一元素都加上或減去同一個(ge) 數，得到一個(ge) 新矩陣BB，則以C或B為(wei) 係數矩陣的指派問題具有相同的最優(you) 指派。

對偶理論與(yu) 靈敏度分析

對偶問題的基本性質：

01、對稱性

對偶問題的對偶是原問題。

02、無界性

若原問題（對偶問題）為(wei) 無界解，則其對偶問題（原問題）無可行解。

03、對偶定理

若原問題有最優(you) 解，那麽(me) 對偶問題也有最優(you) 解；且目標函數值相同。

03、互補鬆弛性

若xˆ,yˆx^,y^分別是原問題和對偶問題的最優(you) 解，則

 

本期的模型學習(xi) 筆記之線性規劃到此告一段落啦。如果你對該算法有興(xing) 趣，可以自己動手查閱相關(guan) 資料，進行更加深入的了解~