文章目錄

• 一、運輸規(guī)劃問題模型及變化
• 二、運輸規(guī)劃問題求解 ( 表上作業(yè)法 )

一、運輸規(guī)劃問題模型及變化

---

運輸規(guī)劃問題一般形式 ( 產(chǎn)銷平衡 ) :

$\mathrm{m}$ 個產(chǎn)地 : ${\mathrm{A}}_1,{\mathrm{A}}_2,{\mathrm{A}}_3,?,{\mathrm{A}}_{\mathrm{m}}$ ;

$\mathrm{n}$ 個銷地 : ${\mathrm{B}}_1,{\mathrm{B}}_2,{\mathrm{B}}_3,?,{\mathrm{B}}_{\mathrm{n}}$ ;

${\mathrm{a}}_{\mathrm{i}}$ 表示產(chǎn)地 ${\mathrm{A}}_{\mathrm{i}}$ 的產(chǎn)量 , $\mathrm{i}=1,2,3,?,\mathrm{m}$ ;

${\mathrm{b}}_{\mathrm{j}}$ 表示產(chǎn)地 ${\mathrm{B}}_{\mathrm{j}}$ 的銷量 , $\mathrm{j}=1,2,3,?,\mathrm{n}$ ;

${\mathrm{c}}_{\mathrm{i}\mathrm{j}}$ 表示將 ${\mathrm{A}}_{\mathrm{i}}$ 產(chǎn)地的產(chǎn)品運往 ${\mathrm{B}}_{\mathrm{j}}$ 銷地的運輸成本 ;

假設 ${\mathrm{x}}_{\mathrm{i}\mathrm{j}}$ 是從產(chǎn)地 ${\mathrm{A}}_{\mathrm{i}}$ 運往銷地 ${\mathrm{B}}_{\mathrm{j}}$ 的運輸量 ;

可以得到如下線性規(guī)劃模型 :

$\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{W}={\sum }_{\mathrm{i}=1}^{\mathrm{m}}{\sum }_{\mathrm{j}=1}^{\mathrm{n}}{\mathrm{c}}_{\mathrm{i}\mathrm{j}}{\mathrm{x}}_{\mathrm{i}\mathrm{j}}\\ \\ \mathrm{s}.\mathrm{t}?\begin{array}{l}{\sum }_{\mathrm{j}=1}^{\mathrm{n}}{\mathrm{x}}_{\mathrm{i}\mathrm{j}}={\mathrm{a}}_{\mathrm{i}}(\mathrm{i}=1,2,3,?,\mathrm{m})\\ \\ {\sum }_{\mathrm{i}=1}^{\mathrm{m}}{\mathrm{x}}_{\mathrm{i}\mathrm{j}}={\mathrm{b}}_{\mathrm{j}}(\mathrm{j}=1,2,3,?,\mathrm{n})\\ \\ {\mathrm{x}}_{\mathrm{i}\mathrm{j}}\ge 0(\mathrm{i}=1,2,3,?,\mathrm{m};\mathrm{j}=1,2,3,?,\mathrm{n})\end{array}\end{array}$

此外運輸規(guī)劃還有一些變化模型 :

① 目標函數(shù)求最大值 , 如利潤最大 ;

② 運輸能力限制 , 需要在模型中加入等式或不等式約束條件 ;

③ 產(chǎn)銷不平衡 , 參考 【運籌學】運輸規(guī)劃 ( 運輸規(guī)劃基變量個數(shù) | 運輸問題一般形式 | 產(chǎn)銷平衡 | 產(chǎn)銷不平衡 ) 三、運輸規(guī)劃中的產(chǎn)銷( 不 )平衡問題 ;

二、運輸規(guī)劃問題求解 ( 表上作業(yè)法 )

---

運輸問題線性規(guī)劃 本質(zhì)也是線性規(guī)劃 , 是特殊的線性規(guī)劃 , 其 最優(yōu)解 可以使用 單純形法 求得 ;

運輸問題是線性規(guī)劃中比較簡單的模型 , 其系數(shù)矩陣中的元素都是 $0,1$ , 是稀疏矩陣 , 可以使用簡化版的單純形法求最優(yōu)解 , 該方法稱為 " 表上作業(yè)法 " ;

$\mathrm{m}$ 個產(chǎn)地 , $\mathrm{n}$ 個銷地 , 變量個數(shù)是 $\mathrm{m}\times \mathrm{n}$ 個 ;

$\mathrm{m}$ 個產(chǎn)地 , $\mathrm{n}$ 個銷地 , 約束方程個數(shù)是 $\mathrm{m}+\mathrm{n}$ 個 , 這些約束方程中 , 有一個是多余的 , 最本質(zhì)的方程最多有 $\mathrm{m}+\mathrm{n}?1$ 個 ;

第一步 , 開始找 初始基可行解 , 基變量個數(shù)是 $\mathrm{m}+\mathrm{n}?1$ 個 , 基矩陣的秩是 $\mathrm{m}+\mathrm{n}?1$ ;

求解基可行解時 , 非基變量取值 $0$ , 基變量允許非 $0$ 變量 , 找 $\mathrm{m}+\mathrm{n}?1$ 個基變量 ,

第二步 , 找到一個規(guī)則 , 判斷是否是最優(yōu)解 ;

第三步 , 如果不是最優(yōu)解 , 進行 迭代 , 如何進行迭代 ;

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【运筹学】运输规划 ( 运输规划问题模型及变化 | 表上作业法引入 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。