數學建模算法與應用之線性規劃

數學建模算法與(yu) 應用之“線性規劃”

1、什麽(me) 是線性規化？

線性規劃（Linear programming,簡稱LP），是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個(ge) 重要分支，它是輔助人們(men) 進行科學管理的一種數學方法。研究線性約束條件下線性目標函數的極值問題的數學理論和方法。

線性規劃問題是在一組線性約束條件的限製下，求一線性目標函數最大或最小的問題。關(guan) 鍵在於(yu) 選定適當的決(jue) 策變量。

2、線性規化簡介

數學模型：

（1）列出約束條件及目標函數

（2）畫出約束條件所表示的可行域

（3）在可行域內(nei) 求目標函數的最優(you) 解及最優(you) 值

3、模型建立

從(cong) 實際問題中建立數學模型一般有以下三個(ge) 步驟；

1.根據影響所要達到目的的因素找到決(jue) 策變量；

2.由決(jue) 策變量和所在達到目的之間的函數關(guan) 係確定目標函數；

3.由決(jue) 策變量所受的限製條件確定決(jue) 策變量所要滿足的約束條件。

接下來讓我們(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），問應該如何調運才能使總運費最省？

數學建模算法與(yu) 應用之“線性規劃”

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)單位時間，問應如何分配工作才能使工人花費的總時間最少？

數學建模算法與(yu) 應用之“線性規劃”

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、互補鬆弛性