物流工程中支付調(diào)度的旋轉(zhuǎn)算法
[摘 要] 本文討論的是在物流工程中，已知某項目的工程圖，求一個調(diào)度，使得收入或支出得凈現(xiàn)值達(dá)到最大值。該問題是一個非線性規(guī)劃，本文的主要結(jié)果是證明該調(diào)度問題等價與線性規(guī)劃并且對該問題提出求解方法旋轉(zhuǎn)算法。
[關(guān)鍵詞] 支付調(diào)度 旋轉(zhuǎn)算法
一、模型建立設(shè)變量是事件的發(fā)生時間，對于，是常數(shù)，它是的初始事件時間，活動在完成，規(guī)定活動在所有均完成時才能開始，代數(shù)上為: , 工程周期為，即。通常假定，并稱N - 1 維向量為一個調(diào)度,最后的約束條件化為。設(shè)E是節(jié)點弧關(guān)聯(lián)矩陣,它的元素按如下規(guī)則取值: 因為該網(wǎng)絡(luò)有N 個節(jié)點， 條弧，所以E 是N× 矩陣。于是調(diào)度約束為，其中。若視Dij為距離,那么從1 到N的最長路徑便是工程周期。設(shè)是周期， 表示。事件i的最早開始是它可能的最早時間,它等于 1 到i 的最長路徑。事件i的最遲開始時間是與的最遲時間相一致.例如，設(shè)是i 的最早開始時間， 是i 的最遲開始時間，則，其中位事件j的工時, ，其中為事件i的工時。在時刻，用于交易的貨幣和為, 是收入為正，支出為負(fù)。貨幣的折現(xiàn)率為。這樣，在的時刻交易的現(xiàn)值為。假設(shè).
任何調(diào)度T 的現(xiàn)值是，因此，支付調(diào)度問題的數(shù)學(xué)模型可以表示成如下形式: 。利用數(shù)學(xué)我們證明支付調(diào)度問題變換為線性規(guī)劃 其中C 是定義在A 上的行向量，具有個元素, , ,否則;G 是一個N× 的矩陣，其元素與矩陣E 的對應(yīng)關(guān)系是二、求解方法旋轉(zhuǎn)算法考慮 ，此問題的解法是從一個正基錐開始，每經(jīng)過一次旋轉(zhuǎn)運算得到一個新的正基錐。但其頂點對應(yīng)的'目標(biāo)值要小于或等于前一個正基錐的頂點對應(yīng)的目標(biāo)值。對于線性規(guī)劃的一個基，用分別表示基等式、基不等式、非基不等式的編號集。則是個基錐。如果存在一個充分物流工程中支付調(diào)度的旋轉(zhuǎn)算法付淑娟 河北廊坊廣播電視大學(xué)[摘 要] 本文討論的是在物流工程中，已知某項目的工程圖，求一個調(diào)度，使得收入或支出得凈現(xiàn)值達(dá)到最大值。該問題是一個非線性規(guī)劃，本文的主要結(jié)果是證明該調(diào)度問題等價與線性規(guī)劃并且對該問題提出求解方法旋轉(zhuǎn)算法。
[關(guān)鍵詞] 支付調(diào)度 旋轉(zhuǎn)算法大的數(shù)M 使得，則C 是最大化問題的一個正基錐。
從代數(shù)上看，C 為正基錐的充分必要條件是，c 可以表示為若C是正基錐并且其頂點是可行解，即;則是最優(yōu)解。
例如：求解解：以不等式組為初始基本不等式組，初始基向量為,基本解為。記前三個約束的系數(shù)向量為，右端的常數(shù)項為。則得初始表、第一次旋轉(zhuǎn)結(jié)果、第二次旋轉(zhuǎn)結(jié)果為以下三個表：
此時所有非基向量偏差都是負(fù)數(shù)，所以當(dāng)前正基錐是最優(yōu)正基錐。由于是基向量， 是非基向量所以，最優(yōu)解為。
參考文獻(xiàn)：
[1]張忠楨:凸規(guī)劃投資組合與網(wǎng)絡(luò)優(yōu)化的旋轉(zhuǎn)算法.武漢大學(xué)出版社,2004
【物流工程中支付調(diào)度的旋轉(zhuǎn)算法】相關(guān)文章：