《投資決策問題ppt課件》由會員分享，可在線閱讀，更多相關(guān)《投資決策問題ppt課件（21頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第三章 整數(shù)規(guī)劃模型,3.1 投資決策問題 3.2 背包問題 3.3 合理下料問題 3.4 生產(chǎn)組織與計劃問題 3.5 工廠選址問題 3.6 設(shè)備購置和安裝問題 3.7 旅行商問題,,,3.1 投資決策問題,問題,某市在“十五”計劃期間有b億元的資金可用于n個 項目的投資。 若對第i個項目投資，需資金 億 元，可獲利稅收入 億元。試確定一個投資方案， 使該方案下該市新增的利稅收入最多。 建立此問 題的數(shù)學(xué)模型。,解：,設(shè)該市獲得的新增利稅收入為z億元，并令 1，若對第i個項目投資 = i=1,2,…,n 0，若不對第i個項目投資 則上述問題的數(shù)學(xué)模型如下：,,,,,max z =,s.t. b,≤,=0或1；i=1，2，…，n,,,說明,1. 是本投資方案的總收益； 是 本投資方案的總投入。 2.這是個純整數(shù)規(guī)劃問題，也是一個0-1 規(guī)劃問題。由于目標(biāo)函數(shù)z是決策變量的線性函數(shù)，并且約束條件也是決策變量的線性不等式，所以這是個0-1整數(shù)線性規(guī)劃問題。,3.2 背包問題,問題,設(shè)有一個容積為b的背包，有n個體積 為 (i = 1，2，…，n),使用價值分別為 （i = 1，2，…，n）的物品可以裝入背包。 問應(yīng)選擇哪幾件物品裝入背包，才能得到 最大的使用價值？試建立數(shù)學(xué)模型。,解： 1 將第i件物品裝入背包 令 = 0 不將第i件物品裝入背包 (i=1,2,…,n) 并設(shè)裝入背包的總使用價值為z，則本背包 問題的數(shù)學(xué)模型為：,,,,max z =,s.t. b,≤,= 0或1；i=1，2，…，n,,說明,為裝入背包的物品的總價值，希望其取 最大值。 為裝入背包的物品的總體積，它不能超 過背包的容量。 3. 本模型也是一個0-1整數(shù)線性模型。,3.3 合理下料問題,問題,假設(shè)要利用某類鋼板下m種零件 ， ，…， 的毛料。根據(jù)既省料又容易操作的原則，人們在 一塊鋼板上，已經(jīng)設(shè)計出n種不同的下料方案。 設(shè)在第j種下料方案中，可下得第i種零件 的個 數(shù)為 ，第i種零件的需要量為 ，i=1，2，…， m。問應(yīng)如何下料，才能既滿足需要，又使所用 的鋼板總數(shù)最少？,解：設(shè)采用第j種方案下料的鋼板數(shù)為 ，所用鋼 板的塊數(shù)為y，則本問題的數(shù)學(xué)模型如下：,min y = s.t. i=1，2，…，m 0 I，j=1，2，…，n,≥,≥,∈,,說明,1.采用各種方案下料的鋼板數(shù) 的總和，即為 所用的鋼板數(shù)。 2.完工后，第i種零件下料的數(shù)目不少于 。 3.本模型是一個非0-1的整數(shù)規(guī)劃模型。,3.4 生產(chǎn)組織與計劃問題,問題,某工廠用m臺機床： ， ，…， ，加工n種 零件 ， ，…， 。在一個生產(chǎn)周期內(nèi)，已 知第i臺機床只能工作 個機時，i=1，2，…， m。該工廠必須完成加工零件 的數(shù)量為 個， j=1，2，…，n。機床 加工零件 一個所需的 機時和成本分別為 （機時/個）和 （元/個）。 問在這個生產(chǎn)周期，應(yīng)如何安排各機床的生產(chǎn)任 務(wù)，才能既完成生產(chǎn)任務(wù)，又使總的加工成本最 ??？,解：設(shè)機床 在一生產(chǎn)周期內(nèi)加工零件 的個數(shù)為 ， i=1，2，…，m； j=1，2，…，n。又設(shè)總的加工 成本為y，則本問題的數(shù)學(xué)模型如下：,min y = s.t. ，i=1，2，…，m ， j=1，2，…，n 0 ，且 I， i=1，2，…，m； j=1，2，…，n,≤,≥,≥,∈,,說明,1.總加工成本應(yīng)等于各機床 加工零件 的個數(shù) 乘以該機床加工零件 的單位成本 （元/個）的 總和。,2. 因為按問題要求，機床 加工各零件的機時不能 超過該機床能工作的機時數(shù) ，所以第一個約束 條件成立。 3. 因為按問題要求，各機床 加工零件 的數(shù)目不 能少于對 的需要量 ，所以第二個約束條件成 立。 4. 本模型是一個非0-1的整數(shù)規(guī)劃模型。,3.5 工廠選址問題,問題,設(shè)有n個需求點（如城市、倉庫或商店等），有m個 可供選擇的建廠地址。每個地址至多可建一個工廠。 在 i 地址建立工廠后的生產(chǎn)能力為 ，在 i 地址經(jīng) 營工廠，單位時間的固定成本為 （元），需求點 j 需求量為 ，從廠址 i 到需求點 j 的單位運費為 （元/噸）。問應(yīng)如何選擇廠址和安排運輸計劃，才 能得到經(jīng)濟上最少的方案？,解：設(shè)在單位時間內(nèi)，從廠址 i 運到 需求點j的物資 數(shù)量為 （噸），并引入布爾變量 1，若在 i 地建廠 = 0，若不在 i地建廠 又設(shè)單位時間的總花費為s（元），則本問題的 數(shù)學(xué)模型為：,,min s = +,s.t. ，i=1，2，…，m,≤,≥,，j = 1，2，…，n,≥,0， 其中 = 0 或 1， i=1，2，…，m j=1，2，…，n,,說明,是總運費， 是總生產(chǎn)成本。 是產(chǎn)地 i 運出的物資總量， 是產(chǎn)地i 的生產(chǎn)總量。 是所有產(chǎn)地運達需求點j的物資總量， 是j地的需求量。 本模型中的變量既有0-1變量，又有非0-1變 量，所以是一個混合型的整數(shù)規(guī)劃模型。,3.6 設(shè)備購置和安裝問題,問題,某工廠需要m種設(shè)備 ， ，…， ，設(shè) 的單價 為 元。該廠已有第i種設(shè)備 臺，i=1，2，…，m。 今有資金 M 元，可用于購置這些設(shè)備。另知該廠有 n處可安裝這些設(shè)備， 處最多能安裝 臺；將一臺 設(shè)備 安裝在 處，經(jīng)濟效益為 。應(yīng)如何購置和 安裝這些設(shè)備，才能使總的經(jīng)濟效益最高？,解：用 表示設(shè)備 安裝在 處的臺數(shù)， 表示購置 的臺數(shù)，z表示總的經(jīng)濟效益，則本問題的數(shù)學(xué) 模型為：,max z = s.t. + ，i=1，2，…，m j=1，2，…，n,≤,≤,≤,M,,,≥0,且 ， I，i=1，2，…，m,∈,j=1，2，…，n,,說明,是第i種設(shè)備安裝在第j處產(chǎn)生的效益；全 體各已安裝的設(shè)備產(chǎn)生的效益的總和即為總的 經(jīng)濟效益。 2.安裝設(shè)備 到各處的總數(shù)目不會超過設(shè)備 的 擁有數(shù)。即新購置的數(shù)目 與原有數(shù)目 之和。 3.安裝在j處的各種設(shè)備的總數(shù)目 不能超過j處 可安裝的數(shù)目 。 4.購置新設(shè)備的總花費 不能超過可用的資金 總量M。,3.7 旅行商問題,問題,一個商人擬到n個城市去推銷商品。已知每兩個 城市 和 之間的距離為 ，任何選擇一條道 路， 使得商人每個城市走一遍回到起點，且所 走的路徑最短。,本問題稱為旅行商問題（記為TSP），也叫貨郎 擔(dān)問題或郵路問題。是一種特殊的Hamilton（哈 密爾頓回路問題。,,,解： 令,1，商人選擇的路線包含從 到 的邊 = 0，否則,,≤,︱,︱,≤,︱,︱,≤n-2, S {1,2,…,n},∈,{0,1}; i,j=1,2,…,n; i ≠ j,說明,,為在路徑上出現(xiàn)的各條邊的長度總 和，亦即該路徑的長度。 =1表示從 向外走一次且只走一次。 =1表示從其他點走到 一次且僅一次。 若路徑不滿足第三個約束條件，則該路徑 中必然含有回路。,