【正文】 = = 大于零，有利可圖，將 P6左乘 B1，加入到末表之中，繼續(xù)迭代，直到求得最優(yōu)解。若原問題最優(yōu)基為 B，則其對偶問題最優(yōu)解 Y*=CBB1 OR1 58 —影子價格 ? Z= ω=CX=Yb ?Z/ ? b=(Yb)’=Y ? Z=Yb= ∑yibi的意義： Y是檢驗數(shù)的反數(shù)。則： 本期生產(chǎn) +上期庫存 本期庫存 =本期需求 OR1 49 第三章 對偶問題與靈敏度分析 ? 要求： 了解 LP對偶問題的實際背景 了解對偶問題的建立規(guī)則與基本性質(zhì) 掌握對偶最優(yōu)解的計算及其經(jīng)濟(jì)解釋 掌握 LP的靈敏度分析 理解計算機(jī)輸出的影子價格與靈敏度分 析的內(nèi)容 OR1 50 對偶問題 ? 對偶問題的提出 回顧例題 1： 現(xiàn)在 A、 B兩產(chǎn)品銷路不暢，可以將所有資源出租或外賣，現(xiàn)在要談判，我們的價格底線是什么？ 產(chǎn)品 A 產(chǎn)品 B 資源限制 勞動力 設(shè)備 原材料 9 4 3 4 5 10 360 200 300 單位利潤 70 120 OR1 51 對偶模型 ? 設(shè)每個工時收費 Y1元，設(shè)備臺時費用 Y2元，原材料附加費 Y3元。關(guān)鍵：設(shè)變量。 ? 人工變量法之一：大 M法 人工變量價值系數(shù) M例 ? 人工變量法之二：構(gòu)造目標(biāo)函數(shù)，分階段求解例 ? ：非基變量檢驗數(shù) σj= 0 ? ：有兩個以上 θ值相等 OR1 44 ? 程序說明 ? 應(yīng)用舉例 例題 1 例題 2 OR1 45 ? 例 13合理下料問題 料長 ，截成 、 、 200根。 XK 原是非基變量，取零值， 若 XK ≠0 將迫使某個原基變量為零，當(dāng) XK取值超過任意 b’i / a’ik 時 ,將破壞非負(fù)性條件 ,于是令 θ = min {b’i / a’ik a’ik 0 } =b’L/ a’Lk 。 ? 基解的數(shù)目：最多 Cmn=n!/m!(nm)! OR1 34 例題 6 基可行解說明 maxZ=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+5X2 +x4=200 A= 4 5 0 1 0 3X1+10X2+x5 =300 3 10 0 0 1 Xj≥0 j=1,2,…,5 這里 m=3,n=5。 n j=1 n j=1 OR1 32 基解的概念 不失一般性 ,設(shè) B是 A的前 m列 ,即B=(p1,p2,…,p m） ,其相對應(yīng)的變量XB=(x1,x2,…,x m)T,稱為基變量；其余變量XN=(Xm+1,…, Xn)T稱為非基變量。 凸集：集合內(nèi)任意兩點的連線上的點均屬于這個集合。 可行域：即可行解的集合。據(jù)統(tǒng)計： 序號 時段 最少人數(shù) 安排人數(shù) 1 06—10 60 X1 2 10—14 70 X2 3 14—18 60 X3 4 18—22 50 X4 5 22—02 20 X5 6 02—06 30 x6 OR1 17 例題 3建模 ? 目標(biāo)函數(shù)： min Z=x1+x2+x3+x4+x5+x6 ? 約束條件： x1+x2 ≥70 x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非負(fù)性約束： xj ≥0,j=1,2,…6 OR1 18 歸納：線性規(guī)劃的一般模式 ? 目標(biāo)函數(shù)： max(min)Z=c1x1+c2x2+c3x3+…+c nxn ? 約束條件： a11x1+a12x2+a13x3+…+a 1nxn ≤(= ≥)b1 a21x1+a22x2+a23x3+…+a 2nxn ≤(= ≥)b2 … … … … am1x1+am2x2+am3x3+…+a mnxn ≤(= ≥)bn 非負(fù)性約束： x1 ≥0,x2 ≥0,…,x n ≥0 OR1 19 ? 由中學(xué)知識可知： y=ax+b是一條直線，同理： Z=70x1+120x2→x 2=70/120x1Z/120也是一條直線，以 Z為參數(shù)的一族等值線?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表： 飼料 Va Vb Vc 價格元 /KG I II III IV V 3 2 1 6 18 1 2 1 2 2 7 4 9 5 營養(yǎng)要求 700 30 200 OR1 15 例題 2建模 ? 設(shè)抓取飼料 I x1kg。 ? 本書有現(xiàn)成的程序可以利用 ? 要學(xué)會解題的思路與方法，建立模型很重要。 ? 形象模型：如地球儀、沙盤、風(fēng)洞 ? 模擬模型：建港口，模擬船只到達(dá)。 ? 定性有主觀性也有有效性，定量有科學(xué)性也有局限性。OPERATIONS RESEARCH 運(yùn)籌學(xué) Ⅰ ? ——怎樣把事情做到最好 ? 郝英奇 OR1 1 第一章 緒論 ? Operations 漢語翻譯 工作、操作、行動、手術(shù)、運(yùn)算 Operations Research 日本 ——運(yùn)用學(xué) 港臺 ——作業(yè)研究 中國大陸 ——運(yùn)籌學(xué) Operational Research原來名稱，意為軍事行動研究——歷史淵源 OR1 2 緒論 ? 運(yùn)籌學(xué)的歷史 早期運(yùn)籌思想：田忌賽馬 丁渭修宮 沈括運(yùn)糧 Erlang 1917 排隊論 Harris 1920 存儲論 Levinson 1930 零售貿(mào)易