第二 對(duì)偶問(wèn)題

會(huì)計(jì)學(xué)1第二對(duì)偶問(wèn)題

上述兩個(gè)LP問(wèn)題的數(shù)學(xué)模型是在同一企業(yè)的資源狀況和生產(chǎn)條件下產(chǎn)生的，且是同一個(gè)問(wèn)題從不同角度考慮所產(chǎn)生的，因此兩者密切相關(guān)。稱這兩個(gè)LP問(wèn)題是互為對(duì)偶的兩個(gè)LP問(wèn)題。其中一個(gè)是另一個(gè)問(wèn)題的對(duì)偶問(wèn)題。

第1頁(yè)/共17頁(yè)

一般地對(duì)于任何一個(gè)線性規(guī)劃問(wèn)題都有一個(gè)與之相對(duì)應(yīng)的對(duì)偶問(wèn)題。原問(wèn)題與對(duì)偶問(wèn)題的一般形式為：

原問(wèn)題（LP）

對(duì)偶問(wèn)題（DP）相應(yīng)的矩陣形式為：第2頁(yè)/共17頁(yè)原問(wèn)題Max（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題Min（原問(wèn)題）約束條件數(shù)=m

變量個(gè)數(shù)=m第i個(gè)約束條件為“≤”第i個(gè)約束條件為“≥”第i個(gè)約束條件為“=”

第i個(gè)變量≥0

第i個(gè)變量≤0

第i個(gè)變量無(wú)限制變量個(gè)數(shù)=n

約束條件個(gè)數(shù)=n第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量無(wú)限制

第i個(gè)約束條件為“≥”第i個(gè)約束條件為“≤”第i個(gè)約束條件為“=”第i個(gè)約束條件的右端項(xiàng)目標(biāo)函第i個(gè)變量的系數(shù)

目標(biāo)函數(shù)第i個(gè)變量的系數(shù)第i個(gè)約束條件的右端頂

歸納對(duì)稱形式與非對(duì)稱形式的對(duì)偶,原問(wèn)題與對(duì)偶問(wèn)題之間的關(guān)系如下表所示：第3頁(yè)/共17頁(yè)

例1、寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題第4頁(yè)/共17頁(yè)例2求解下列線性規(guī)劃問(wèn)題：2.對(duì)偶單純形法第5頁(yè)/共17頁(yè)第6頁(yè)/共17頁(yè)第7頁(yè)/共17頁(yè)迭代終止條件：所有的Bi非負(fù)。第8頁(yè)/共17頁(yè)第9頁(yè)/共17頁(yè)3.1分析價(jià)值系數(shù)的變化3靈敏度分析

在單純形表中，價(jià)值系數(shù)的變化僅僅影響到檢驗(yàn)數(shù)的變化，只需要對(duì)檢驗(yàn)數(shù)進(jìn)行最優(yōu)性檢驗(yàn)，判斷是否需要繼續(xù)迭代即可。第10頁(yè)/共17頁(yè)CCBCNCSbXBXNXSCBB-1bIB-1NB-1ZCBB-1b0CBB-1N-CNCBB-1CCBCNCSbXBXNXSCsbBNIZCBCN03.2分析資源系數(shù)的變化資源系數(shù)的變化對(duì)最優(yōu)單純形標(biāo)的b列有影響。第11頁(yè)/共17頁(yè)第12頁(yè)/共17頁(yè)例題P65第13頁(yè)/共17頁(yè)CCBCNCSbXBXNXSCBB-1bIB-1NB-1ZCBB-1b0CBB-1N-CNCBB-1CCBCNCSbXBXNXSCsbBNIZCBCN03.3增加變量的變化1．計(jì)算該列技術(shù)系數(shù)。2．技術(shù)該列檢驗(yàn)數(shù)。第14頁(yè)/共17頁(yè)

例題：投產(chǎn)新產(chǎn)品，所需原料和設(shè)備分別為3、4、2單位，利潤(rùn)為3單位，問(wèn)最優(yōu)生產(chǎn)計(jì)劃如何變化？第15頁(yè)/共17頁(yè)3.4技術(shù)系數(shù)aij的變化

例題：如果乙產(chǎn)品所需原材料和設(shè)備分別為8、4、1