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

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