【正文】 對偶問題最優(yōu)解： Y1=2,Y2=0 ? C1的變化范圍：以 C1代入末表， C1 ≥1 ?右端項變化范圍： xB= B1b ≥0 ? ?b1 ≥6， ?b2≥10 OR1 70 。 例題 6：新增一種 C產(chǎn)品，單位利潤 110元，使用勞動力 6工時，設備 5臺時，原材料 7公斤，問要否調(diào)整產(chǎn)品結(jié)構(gòu)？ 先算檢驗數(shù) σj =CjCBB1pj σ6=C6YP6=110（ 0， ， ）（ 6， 5， 7） T = = 大于零，有利可圖，將 P6左乘 B1，加入到末表之中，繼續(xù)迭代，直到求得最優(yōu)解。 ? 結(jié)合例題 1講解影子價格： y1=0:第一種資源過剩 y2=：設備臺時最緊張，每增加一個臺時， 利潤增加。若原問題最優(yōu)基為 B，則其對偶問題最優(yōu)解 Y*=CBB1 OR1 58 —影子價格 ? Z= ω=CX=Yb ?Z/ ? b=(Yb)’=Y ? Z=Yb= ∑yibi的意義： Y是檢驗數(shù)的反數(shù)。 3y1 +y3=1 x4 ≤ 0。則： 本期生產(chǎn) +上期庫存 本期庫存 =本期需求 OR1 49 第三章 對偶問題與靈敏度分析 ? 要求： 了解 LP對偶問題的實際背景 了解對偶問題的建立規(guī)則與基本性質(zhì) 掌握對偶最優(yōu)解的計算及其經(jīng)濟解釋 掌握 LP的靈敏度分析 理解計算機輸出的影子價格與靈敏度分 析的內(nèi)容 OR1 50 對偶問題 ? 對偶問題的提出 回顧例題 1： 現(xiàn)在 A、 B兩產(chǎn)品銷路不暢，可以將所有資源出租或外賣，現(xiàn)在要談判，我們的價格底線是什么？ 產(chǎn)品 A 產(chǎn)品 B 資源限制 勞動力 設備 原材料 9 4 3 4 5 10 360 200 300 單位利潤 70 120 OR1 51 對偶模型 ? 設每個工時收費 Y1元，設備臺時費用 Y2元，原材料附加費 Y3元。求費用最小的生產(chǎn)計劃。關(guān)鍵：設變量。 方案 料型 1 2 3 4 5 6 7 8 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2 0 3 1 0 4 合計 殘料 0 OR1 46 應用舉例之二 ? 例 14混合配方問題 A、 B、 C、 D四種原料配制三種產(chǎn)品，三類約束：技術(shù)要求、原料限量、市場容量。 ? 人工變量法之一：大 M法 人工變量價值系數(shù) M例 ? 人工變量法之二：構(gòu)造目標函數(shù)，分階段求解例 ? ：非基變量檢驗數(shù) σj= 0 ? ：有兩個以上 θ值相等 OR1 44 ? 程序說明 ? 應用舉例 例題 1 例題 2 OR1 45 ? 例 13合理下料問題 料長 ，截成 、 、 200根。否則轉(zhuǎn)下步 ? 若某 σK ≥ 0而 P’K ≤0 ， 則最優(yōu)解無界，結(jié)束。 XK 原是非基變量，取零值， 若 XK ≠0 將迫使某個原基變量為零，當 XK取值超過任意 b’i / a’ik 時 ,將破壞非負性條件 ,于是令 θ = min {b’i / a’ik a’ik 0 } =b’L/ a’Lk 。進行等價變換－－約束方程兩端分別左乘 B－ 1 得 X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 …………………………….. xm+a’mm+1xm+1+…+ a’mnxn=b’m 令非基變量為 0，得基可行解 X(0)=(b1’， b2’， ……b m， 0， ……0 ） T z0=∑cibi’ OR1 37 ? ： LP經(jīng)過若干步迭代，成為如下形式： X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x1=b’1 ∑ a’1jxj x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 x2=b’2 ∑a’2jxj …………………………….. …………….. xm+a’mm+1xm+1+…+ a’mnxn=b’m xm=b’m ∑a’mjxj OR1 38 單純形法 一般性表示 ： xi=b’i ∑a’ijxj i=1,2,…m 將 xi代入目標函數(shù)得 ： Z= ∑ cjxj = ∑ cixi+ ∑ cjxj = ∑ci（ b’i ∑a’ijxj ） + ∑ cjxj = ∑cibi’+ ∑(cj ∑ cia’ij)xj 令： σj= cj ∑ cia’ij z0=∑cibi’ 則 Z=z0+ ∑ σj xj σj判別準則 ： σj ≤0 時 ,達到最優(yōu)解 OR1 39 單純形法 ? 若存在 σj ≥ 0，則取 max{σj } = σK ，相應之非基變量 XK若取非零，將使 Z增加 ,故令