【正文】 x21 + x22+ x24 = ； x31 + x32+ x33 = + ； x41 + x42 = + ； x51 = + ； xi2 ≤ 30 ( I =1 、 4 )， x33 ≤ 80 ， x24 ≤ 100 xij ≥ 0 ( i = 1 、 5； j = 4） b) Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+ . x11+ x12 = 200 x21 + x22+ x24 = ； x31 + x32+ x33 = + ； x41 + x42 = + ； x51 = + ； xi2 ≤ 30 ( I =1 、 4 )， x33 ≤ 80 ， x24 ≤ 100 + + + ≥ 330 xij ≥ 0 ( i = 1 、 5； j = 4）例：投資問題（續(xù)）41線性規(guī)劃問題的進(jìn)一步研究（ ）2. 1 對(duì)偶原理對(duì)偶問題： 考慮前文例 1 若設(shè)備和原料都用于外協(xié)加工，工廠收取加工費(fèi)。定理 22 （最優(yōu)性準(zhǔn)則定理）若 x, y 分別為（ LP）和（ DP）的可行解，且 cT x = bT y ，那么 x, y分別為（ LP）和（ DP）的最優(yōu)解。 根據(jù) f = bT y* = b1y1* + b2y2* + ?? + bmym* 可知 ?f / ?bi = yi* yi* 表示 bi 變化 1個(gè)單位對(duì)目標(biāo) f 產(chǎn)生的影響，稱 yi* 為 bi的影子價(jià)格。線性規(guī)劃問題的進(jìn)一步研究（ ）462. 2 對(duì)偶單純形法? 對(duì)偶單純形法在什么情況下使用 ： 應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基本解滿足 ① 單純形表的檢驗(yàn)數(shù)行全部非正（對(duì)偶可行）； ② 變量取值可有負(fù)數(shù)（非可行解）。應(yīng) 1 1能夠找到最優(yōu)基 B的逆矩陣 B ，以及 B N，檢驗(yàn)數(shù)等。 Max{?j / asj ? asj 0 } ≤ ?cs ≤ Min{?j / asj ? asj 0 } 例 : Max Z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 . x1 + 2x2+ x3 = 8 4x1 + x4 =16 4x2 +x5 = 12 x1 , x2 , x3 , x4 , x5 ≥ 0 線性規(guī)劃問題的進(jìn)一步研究（ ）55例、下表為最優(yōu)單純形表，考慮基變量系數(shù) c2 發(fā)生變化從表中看到 σ j = Cj （ C1 * a1j + C5 * a5j + （ C2 +ΔC 2 ） * a2j ） j = 4可得到 3 ≤ ΔC 2 ≤ 1 時(shí)，原最優(yōu)解不變。由此可得，最優(yōu)基不變的條件是 Max{bi / air ? air 0 } ≤ ?br ≤ Min{bi / air ? air 0 }線性規(guī)劃問題的進(jìn)一步研究（ ）57例、上例最優(yōu)單純形表如下 ? 0 0 ?這里 B1 = ? 2 1 ? 各列分別對(duì)應(yīng) b b b3 的單一 ? 0 ?變化。計(jì)算得到線性規(guī)劃問題的進(jìn)一步研究（ ）用單純形法進(jìn)一步求解，可得： x* = ( 1,0,0,0,2 )T f* = 59? 增加一個(gè)約束 增加約束一個(gè)之后，應(yīng)把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入1個(gè)新的非負(fù)變量（原約束若是小于等于形式可引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過矩陣行變換把對(duì)應(yīng)基變量的元素變?yōu)?0，進(jìn)一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼狻＞€性規(guī)劃問題的進(jìn)一步研究（ ）可得最優(yōu)解： x* = ( ,0,0, )T f* = 61線性規(guī)劃問題的進(jìn)一步研究（ ）2. 3 靈敏度分析 (內(nèi)容，為重點(diǎn) ) Ci 發(fā)生變化 Bj發(fā)生變化 增加一個(gè)變量 增加一個(gè)約束 A中元素發(fā)生變化**習(xí)題： p 100 習(xí)題 2 24返回目錄623. 1 運(yùn)輸問題模型與性質(zhì) ? 運(yù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)用最??？運(yùn) 輸 問 題（ ） 63解： 產(chǎn)銷平衡問題： 總產(chǎn)量 = 總銷量 設(shè) xij 為從產(chǎn)地 Ai運(yùn)往銷地 Bj的運(yùn)輸量，得到下列運(yùn)輸量表： Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 . x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij ≥ 0 ( i = 1 、 2； j = 3）運(yùn) 輸 問 題（ ） 64? 系數(shù)矩陣? 1 1 1 0 0 0 ?? 0 0 0 1 1 1 ?? 1 0 0 1 0 0 ?? 0 1 0 0 1 0 ?? 0 0 1 0 0 1 ?特點(diǎn)： 共有 m+n行，分別表示產(chǎn)地和銷地； mn列分別表示各變量；每列只有兩個(gè) 1，其余為 0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用；運(yùn) 輸 問 題（ ） 65? 設(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 。 * 運(yùn)輸問題的 m + n 1 個(gè)變量構(gòu)成基變量的充分必要條件是不含閉回路。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。運(yùn) 輸 問 題（ ） 69*運(yùn) 輸 問 題（ ） 70*運(yùn) 輸 問 題（ ） 71最優(yōu)性檢驗(yàn)： 因?yàn)榍笞钚?，?dāng)所有檢驗(yàn)數(shù)均大于等于 0時(shí)為最優(yōu)解（ 1）位勢(shì)法求檢驗(yàn)數(shù)：? 位勢(shì)： 設(shè)對(duì)應(yīng)基變量 xij 的 m + n 1 個(gè) ij ，存在 ui , vj 滿足 ui + vj = cij ， i = 1, … , m 。 j = 1, … , n運(yùn) 輸 問 題（ ） 72? 前例，位勢(shì)法求檢驗(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) 輸 問 題（ ） 73主元變換：（ 1）選負(fù)檢驗(yàn)數(shù)中最小者 ?rk，那么 xrk 為主元，作為進(jìn)基變量； （上頁(yè)圖中 x24 ）（ 2）以為 xrk 起點(diǎn)找一條閉回路，除 xrk 外其余頂點(diǎn)必須為基變量格； （上頁(yè)圖中 藍(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)解。供應(yīng)能力分別為 1500、4000噸，運(yùn)價(jià)如下表。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表。運(yùn) 輸 問 題（例題）81例、 某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供 12 20臺(tái)同一規(guī)格的柴油機(jī)。運(yùn) 輸 問 題（例題）82解： 設(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)。加班生產(chǎn)機(jī)器每臺(tái)增加成本 1萬元。續(xù)下頁(yè) 產(chǎn)銷平衡與運(yùn)價(jià)表：運(yùn) 輸 問 題（例題）85 **習(xí)題： p 124 習(xí)題 3 33， 34運(yùn) 輸 問 題（例題）返回目錄864. 1 動(dòng)態(tài)規(guī)劃概念與模型? 多階段決策過程特點(diǎn)要點(diǎn)：階段，狀態(tài)，決策，狀態(tài)轉(zhuǎn)移方程， k后部子過程動(dòng) 態(tài) 規(guī) 劃 () 87? 動(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ī) 劃 () 88? 建模過程