mba__運籌學_127頁-資料下載頁

　　

【正文】 地被使用；運 輸 問 題（ ） 65? 設 xij 為從產地 Ai運往銷地 Bj的運輸量，得到下列一般運輸量問題的模型： m n Min f = ? ? cij xij i=1 j=i n . ? xij = si i = 1,2,…,m j=1 m ? xij = dj j = 1,2,…,n i=1 xij ≥ 0 (i = 1,2,…,m 。 j = 1,2,…,n) ?一般運輸模型： 產銷平衡 A A … 、 Am 表示某物資的 m個產地； B B … 、 Bn 表示某物質的 n個銷地； si 表示產地 Ai的產量； dj 表示銷地 Bj 的銷量； cij 表示把物資為從產地 Ai運往銷地 Bj的單位運價。運 輸 問 題（ ） 66運 輸 問 題（ ） ? 變化： 1）有時目標函數求最大，如求利潤最大或營業額最大等； 2）當某些運輸線路上的能力有限制時，模型中可直接加入（等式或不等式）約束； 3）產銷不平衡時，可加入虛設的產地（產大于銷時）或銷地（銷大于產時）。67運 輸 問 題（ ） ? 求解思路 是 基本可行解 最優否 結束 否 換基? 運輸問題基變量的特點 * 運輸問題的基變量共有 m + n 1 個， A的秩為 m + n 1。 * 運輸問題的 m + n 1 個變量構成基變量的充分必要條件是不含閉回路。 要弄清下列概念 ：閉回路、閉回路的頂點。683. 2 運輸問題的表上作業法 —— 本章重點初始基本可行解的確定：（ 1）西北角法： 從西北角（左上角）格開始，在格內的右下角標上 允許取得 的最大數。然后按行（列）標下一格的數。若某行（列）的產量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。（ 2）最小元素法： 從運價最小的格開始，在格內的右下角標上 允許取得 的最大數。然后按運價從小到大順序填數。若某行（列）的產量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。注： 應用西北角法和最小元素法，每次填完數，都只劃去一行或一列，只有最后一個元例外（同時劃去一行和一列）。當填上一個數后行、列同時飽和時，也應任意劃去一行（列）在保留的列（行）任意沒被劃去的格內標一個 0。運 輸 問 題（ ） 69*運 輸 問 題（ ） 70*運 輸 問 題（ ） 71最優性檢驗： 因為求最小，當所有檢驗數均大于等于 0時為最優解（ 1）位勢法求檢驗數：? 位勢： 設對應基變量 xij 的 m + n 1 個 ij ，存在 ui , vj 滿足 ui + vj = cij ， i = 1, … , m 。 j = 1, … , n . 稱這些 ui , vj 為該基本可行解對應的位勢。 由于有 m + n 個變量（ ui , vj ）， m + n 1 個方程（基變量個數），故有一個自由變量，位勢不唯一。? 利用位勢求檢驗數： ?ij = cij ui vj i = 1, … , m 。 j = 1, … , n運 輸 問 題（ ） 72? 前例，位勢法求檢驗數： step 1 從任意基變量對應的 cij 開始，任取 ui 或 vj ，然后利用公式 cij = ui + vj 依次找出 m + n 個 ui , vj ； 從 c14 = 10 開始 step 2 計算非基變量的檢驗數 ?ij = cij ui vj ； 填入圓圈內運 輸 問 題（ ） 73主元變換：（ 1）選負檢驗數中最小者 ?rk，那么 xrk 為主元，作為進基變量； （上頁圖中 x24 ）（ 2）以為 xrk 起點找一條閉回路，除 xrk 外其余頂點必須為基變量格； （上頁圖中 藍色回路）（ 3）為閉回路的每一個頂點標號， xrk 為 1，沿一個方向依次給各頂點標號；（ 4）求 ?=min{xij?xij對應閉回路上的偶數標號格 }= xpq那么確定 xpq為出基變量， ?為調整量；（ 5）對閉回路的各奇標號頂點 xij + ?，對各偶標號頂點 xij ?，特別 xpq ? = 0，變為非基變量；運 輸 問 題（ ） 重復 3步，直到所有檢驗數均非負，得到最優解。74主元變換： 由前面得到 ? = 1，于是運 輸 問 題（ ） ?ij ≥ 0，得到最優解 x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3, 其余 xij = 0 。 最優費用： f* = 3*5+10*2+1*3+8*1+4*6+5*3 = 85**習題： p 123 習題 3 31, 32753. 3 產銷不平衡的運輸問題 產量大于銷量 例、 某公司從兩個產地 A A2將物品運往三個銷地 B B B3，各產地的產量、各銷地的銷量和各產地運往個銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最小？解 ：增加一個虛設的銷地運輸費用為 0運 輸 問 題（ ） 76銷量大于產量 例、 某公司從兩個產地 A A2將物品運往三個銷地 B BB3，各產地的產量、各銷地的銷量和各產地運往個銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最小？解 ：增加一個虛設的產地運輸費用為 0運 輸 問 題（ ） 77? 下面給出一些例題，可作為建模的練習：例、 石家莊北方研究院有一、二、三，三個區。每年分別需要用煤 3000、 1000、 2023噸，由河北臨城、山西盂縣兩處煤礦負責供應，價格、質量相同。供應能力分別為 1500、4000噸，運價如下表。由于需大于供，經院研究決定一區供應量可減少 0200噸，二區必須滿足需求量，三區供應量不少于 1700噸，試求總費用為最低的調運方案。運 輸 問 題（例題）78解： 根據題意，作出產銷平衡與運價表： 取 M 代表一個很大的正數，其作用是強迫相應的 x3 x3 x34取值為 0。 運 輸 問 題（例題）79例、 設有 A、 B、 C三個化肥廠供應 4四個地區的農用化肥。假設效果相同，有關數據如下表。試求總費用為最低的化肥調撥方案。運 輸 問 題（例題）80解： 根據題意，作出產銷平衡與運價表： 最低要求必須滿足，因此把相應的虛設產地運費取為 M ，而最高要求與最低要求的差允許按需要安排，因此把相應的虛設產地運費取為 0 。對應 4”的銷量 50 是考慮問題本身適當取的數據，根據產銷平衡要求確定 D的產量為 50。運 輸 問 題（例題）81例、 某廠按合同規定須于當年每個季度末分別提供 12 20臺同一規格的柴油機。已知該廠各季度的生產能力及生產每臺柴油機的成本如下表。如果生產出來的柴油機當季不交貨，每臺每積壓一個季度需儲存、維護等費用。試求在完成合同的情況下，使該廠全年生產總費用為最小的決策方案。運 輸 問 題（例題）82解： 設 xij為第 i 季度生產的第 j 季度交貨的柴油機數目，那末應滿足：交貨： x11 = 10 生產： x11 + x12 + x13 + x14 ≤ 25 x12 + x22 = 15 x22 + x23 + x24 ≤ 35 x13 + x23 + x33 = 25 x33 + x34 ≤ 30 x14 + x24 + x34 + x44 = 20 x44 ≤ 10 把第 i 季度生產的柴油機數目看作第 i 個生產廠的產量；把第 j 季度交貨的柴油機數目看作第 j 個銷售點的銷量；成本加儲存、維護等費用看作運費。可構造下列產銷平衡問題： 目標函數： Min f = x11 + x12 + x13 + x14 + x22 + x23 + x24 + x33 + x34 + x44 運 輸 問 題（例題）83例、 光明儀器廠生產電腦繡花機是以產定銷的。已知 1至 6月份各月的生產能力、合同銷量和單臺電腦繡花機平均生產費用見下表 已知上年末庫存 103臺繡花機，如果當月生產出來的機器當月不交貨，則需要運到分廠庫房，每臺增加運輸成本 ,每臺機器每月的平均倉儲費、維護費為 。在 78月份銷售淡季，全廠停產 1個月，因此在 6月份完成銷售合同后還要留出庫存 80臺。加班生產機器每臺增加成本 1萬元。問應如何安排 16月份的生產，可使總的生產費用（包括運輸、倉儲、維護）最少？運 輸 問 題（例題）84解： 這個生產存儲問題可化為運輸問題來做。考慮：各月生產與交貨分別視為產地和銷地 1） 16月份合計生產能力（包括上年末儲存量）為 743臺，銷量為 707臺。設一假想銷地銷量為 36； 2）上年末庫存 103臺，只有倉儲費和運輸費，把它列為的 0行； 3） 6月份的需求除 70臺銷量外，還要 80臺庫存，其需求應為 70+80=150臺； 4） 16表示 16月份正常生產情況， 1’6’表示 16月份加班生產情況。續下頁 產銷平衡與運價表：運 輸 問 題（例題）85 **習題： p 124 習題 3 33， 34運 輸 問 題（例題）返回目錄864. 1 動態規劃概念與模型? 多階段決策過程特點要點：階段，狀態，決策，狀態轉移方程， k后部子過程動 態 規 劃 () 87? 動態規劃模型 n opt R( u1, … , u n ) = ? rk ( xk , uk ) k=1 . xk+1 = Tk ( xk , uk ) xk ? Xk ； uk ? Uk k = 1,…,n ?： 表示對 n階段效應進行綜合（常用 ? 或 ? ）； opt ：最優化（ Max 或 Min） R( u1, … , u n )：目標函數（最優值函數） xk+1 = Tk ( xk , uk ) ：狀態轉移方程 Xk ：狀態可能集合 Uk：決策允許集合動 態 規 劃 () 88? 建模過程