管理運籌學(xué)整數(shù)規(guī)劃(存儲版)
【正文】 A次年末才可收回投資故第二年年初的資金為 ， 于是 x2A+x2C+x2D = ； 第三年：年初的資金為 +， 于是 x3A+x3B+x3D = + ； 第四年：年初的資金為 +， 于是 x4A + x4D = + ； 第五年：年初的資金為 +， 于是 x5D = + ； 關(guān)于項目 A的投資額規(guī)定 : x1A ≥ 40000 y1A ， x1A ≤ 202200 y1A ， 202200是足夠大的數(shù)； 保證當(dāng) y1A = 0時， x1A = 0 ； 當(dāng) y1A = 1時， x1A ≥ 40000 。根據(jù)上面分析，若出現(xiàn)情況①，②則停機。 )，轉(zhuǎn) 2，進行以下一般步的迭代； 167。 。隱枚舉法的基本思想是根據(jù) 0— 1規(guī)劃的特點，進行分技逐步求解。轉(zhuǎn) 2； 任選一自由變量 xk ， 令 xk 為固定變量，分別固定為 xk = 0 與 xk ＝ 1， 令所有自由變量取零值，則得到兩個分枝。于是在此問題框的下方標(biāo)記“”； 情況三：若試探解不可行，且它的目標(biāo)值與目標(biāo)函數(shù)中對應(yīng)當(dāng)前自由變量的任一個系數(shù)之和大于所有已得到的上界中最小者時，說明在當(dāng)前問題的基礎(chǔ)上，固定任何自由變量都不可能對目標(biāo)函數(shù)有改善，于是在該問題框的下方標(biāo)記“”； 情況四：若試探解不可行，但所有變量已被置為固定變量，也應(yīng)剪枝，于是在該問題框的下方標(biāo)記“”。 如果仍存在尚未探明的分枝，則可任選一個未探明的分枝。 求 A到 E的最短路徑 。 記從 Bi (i=1, 2, 3) 到 E的最短路徑為 S(Bi)， 則從 A到 E的最短距離 S(A)可以表示為： 。 3 動態(tài)規(guī)劃的應(yīng)用 （見文本） 167。 值的問題，比較得到其中最小者，其對應(yīng)的試探解即原問題的最優(yōu)解，相應(yīng)值即原問題的最優(yōu)目標(biāo)值 f*；若沒有標(biāo)記 f175。 的值記在子問題框的旁邊，并在下方標(biāo)記上“”； 167。若 x = 0 是可行解，那末 f ＝ 0是該問題的最優(yōu)解，結(jié)束計算。 例： Min f = 5x14x2 . 3x1+4x2 ≤ 24 9x1+5x2 ≤ 45 x1,x2 ≥ 0 整數(shù) 167。 比較與剪枝： 對當(dāng)前子問題進行考察，若不需再進行計算，則稱之為剪枝。＝ +?， 而先不必費很大力量去求較好的上界。這時得到當(dāng)前問題 (A)最優(yōu)目標(biāo)值的一個下界 z ＝ z ,于是通過以下判斷可對此問題進一步計算。 該部門現(xiàn)有資金 10萬元，問它應(yīng)如何確定給這些項目的每年投資額，使到第五年末擁有的資金本利總額為最大 ? 解： 1) 設(shè) xiA、 xiB、 xiC、 xiD ( i ＝ 1， 2， 3， 4， 5)分別表示第 i 年年初給項目 A， B， C， D的投資額； 設(shè) yiA， yiB，是 0— 1變量，并規(guī)定取 1 時分別表示第 i 年給 A、 B投資，否則取 0（ i = 1, 2, 3, 4, 5）。已知在 A2 ， A3， A4， A5地建廠的固 定成本分別為 175千元、 300千元、 375千元、 500千元，另 外， A1產(chǎn)量及 A2， A3， A4， A5建成廠的產(chǎn)量，那時銷地 的銷量以及產(chǎn)地到銷地的單位運價 (每千箱運費 )如右表所示。 各種容器的固定費用只有在生產(chǎn)該種容器時才投入，為了說明固定費用的這種性質(zhì)，設(shè) yi = 1(當(dāng)生產(chǎn)第 i種容器 , 即 xi ＞ 0 時 ) 或 0（ 當(dāng)不生產(chǎn)第 i種容器即 xi = 0 時） 引入約束 xi ≤ M yi ， i =1， 2， 3， M充分大，以保證當(dāng) yi = 0 時， xi = 0 。 3整數(shù)規(guī)劃的應(yīng)用 (1) 一、投資場所的選擇 例 京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有 10個位置 Aj (j＝ 1， 2， 3， … ， 10)可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集度，規(guī)定： 在東區(qū)由 A1 ， A2 ， A3 三個點至多選擇兩個； 在西區(qū)由 A4 ， A5 兩個點中至少選一個； 在南區(qū)由 A6 ， A7 兩個點中至少選一個； 在北區(qū)由 A8 ， A9 ， A10 三個點中至少選兩個 。第八章 整數(shù)規(guī)劃 167。 2整數(shù)規(guī)劃的計算機求解 例 2： Max z = 15x1 + 10x2 + 7x3 . 5x1 10x2 + 7x3 ≤ 8 6x1 + 4x2 + 8x3 ≤ 12 3x1 + 2x2 + 2x3 ≤ 10 x1,x2,x3 ≥ 0 為整數(shù) 例 2： Max z = 15x1 + 10x2 + 7x3 . 5x1 10x2 + 7x3 ≤ 8 6x1 + 4x2 + 8x3 ≤ 12 3x1 + 2x2 + 2x3 ≤ 10 x1,x2,x3 ≥ 0 x3 為整數(shù) x1 為 01變量 用《
公司管理相關(guān)推薦
鄂ICP備17016276號-1