第2章對偶理論和靈敏度分析-第3節(jié)

1、第2章 對偶理論和靈敏度分析第3節(jié) 對偶問題的提出第1章例1的不同表述v現(xiàn)從另一角度來討論這個問題。 假設(shè)該工廠的決策者決定不生產(chǎn)產(chǎn)品、，而將其所有資源出租或外售。這時工廠的決策者就要考慮給每種資源如何定價的問題。設(shè)用y1，y2，y3分別表示出租單位設(shè)備臺時的租金和出讓單位原材料A，B的附加額。他在做定價決策時，做如下比較：若用1個單位設(shè)備臺時和4個單位原材料A可以生產(chǎn)一件產(chǎn)品，可獲利2元，那么生產(chǎn)每件產(chǎn)品的設(shè)備臺時和原材料出租或出讓的所有收入應(yīng)不低于生產(chǎn)一件產(chǎn)品的利潤，這就有 y1+4y22資源 產(chǎn) 品 擁有量設(shè) 備1 2 8臺時原材料 A 40 16 kg原材料 B04 12 kgv同理將

2、生產(chǎn)每件產(chǎn)品的設(shè)備臺時和原材料出租或出讓的所有收入應(yīng)不低于生產(chǎn)一件產(chǎn)品的利潤，這就有 2y1+4y33v把工廠所有設(shè)備臺時和資源都出租或出讓，其收入為 =8y1+16y2+12y3v從工廠的決策者來看當(dāng)然愈大愈好；但受到接受方的制約，從接受者來看他的支付愈少愈好，所以工廠的決策者只能在滿足大于等于所有產(chǎn)品的利潤條件下，提出一個盡可能低的出租或出讓價格，才能實現(xiàn)其原意，為此需解如下的線性規(guī)劃問題 稱這個線性規(guī)劃問題為例1線性規(guī)劃問題(這里稱原問題)的對偶問題。 vmin =8y1+16y2+12y3v y1+4y2 2v 2y1 +4y33v yi0，i=1,2,3 (2-8)對偶問題的提出v對

3、偶是什么：對同一事物（或問題），從不同的角度（或立場）提出對立的兩種不同的表述。例如在平面內(nèi)，矩形的面積與其周長之間的關(guān)系，有兩種不同的表述方法。v（1）周長一定，面積最大的矩形是正方形。v（2）面積一定，周長最短的矩形是正方形。這是互為對偶關(guān)系的表述。v這種表述有利于加深對事物的認(rèn)識和理解。v線性規(guī)劃問題也有對偶關(guān)系。課堂練習(xí)v某廠生產(chǎn)產(chǎn)品有某廠生產(chǎn)產(chǎn)品有A，B，C三種運送方式，每種三種運送方式，每種方式運送的原料和設(shè)備方式運送的原料和設(shè)備臺數(shù)如表所示，要想花臺數(shù)如表所示，要想花費最少，需要如何運送費最少，需要如何運送方案，列出數(shù)學(xué)模型，方案，列出數(shù)學(xué)模型，并寫出其并寫出其對偶模型對偶模型A

4、BC資源限制原料1134120kg原料2342125kg設(shè)備421210臺成本346進(jìn)一步討論它們之間的關(guān)系v引例：求下列問題的對偶0,41501053max212212121xxxxxxxxxz進(jìn)一步討論它們之間的關(guān)系v從第1節(jié)得到檢驗數(shù)的表達(dá)式是vCN-CBBN-1N與-CBB-1在第1章已提到，當(dāng)檢驗數(shù)vCN-CBBN-1N0 (2-9) v-CBB-10 (2-10) v這表示線性規(guī)劃問題已得到最優(yōu)解。v也是作為得到最優(yōu)解的判斷條件。 現(xiàn)在討論這兩個條件。 v(1) (2-9)式，(2-10)式中都有乘子CBB-1，稱它為單純形乘子，用符號Y= CBB-1表示。v由(2-10)式，可得

5、到Y(jié)0v(2) 對應(yīng)基變量XB的檢驗數(shù)是0。v它是CB- CBB-1B=0。包括基變量在內(nèi)的所有檢驗數(shù)可用C- CBB-1A0表示。v從此可得C-CBB-1A=C-YA0 移項后，得到Y(jié)ACv(3) Y由(2-10)式，得到v-Y=- CBB- (2-11)v將(2-11)式兩邊右乘b，得到v-Yb=- CBB-1b (2-12)vYb= CBB-1b=zv因Y的上界為無限大，所以只存在最小值 v(4) 從這里可以得到另一個線性規(guī)劃問題 min =Yb YAC Y0v稱它為原線性規(guī)劃問題max z=CXAXb，X0的對偶規(guī)劃問題 對偶規(guī)劃問題（例題）求下列問題的對偶min =8x1+16x2+12x3 x1+4x2 2 2x1 +4x33 xi0，i=1,2,3對偶規(guī)劃問題（例題）oy,y,yyyyyy,y,yYY,Yyyymin,YminT321312132132134224