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