第二章對(duì)偶規(guī)劃

（1）標(biāo)準(zhǔn)型的矩陣形式——

（2）將式中矩陣寫(xiě)成分塊矩陣形式

第2章

對(duì)偶理論和靈敏度分析第1節(jié)單純形法的矩陣描述略講將分塊形式代入矩陣形式標(biāo)準(zhǔn)型，得出兩個(gè)基本表達(dá)式：（1）由約束條件

可得用非基變量表示基變量的表達(dá)式：（2-1）

略講（2）將式（2-1）代入目標(biāo)函數(shù)的表達(dá)式，可得：用非基變量表示目標(biāo)函數(shù)的表達(dá)式：略講（3）借助一個(gè)恒等式推出用非基變量表示目標(biāo)函數(shù)的另一個(gè)等價(jià)表達(dá)式：代入式（2-2），并令（2-4）

單純形乘子

略講三、單純形表格的矩陣形式：

cj

CB

XB

xjbCBCN

0

略講第2節(jié)改進(jìn)單純形法（自學(xué)）略講一、對(duì)偶思想1.

對(duì)偶思想舉例---矩形的面積與周長(zhǎng)關(guān)系的兩種表述：周長(zhǎng)一定的矩形中，以正方形面積最大；面積一定的矩形中，以正方形周長(zhǎng)最??；第3節(jié)

對(duì)偶問(wèn)題的提出----§1.6對(duì)偶是指對(duì)同一問(wèn)題從不同的角度觀察，得到兩種獨(dú)立的表述的思想。例1

要求制定一個(gè)生產(chǎn)計(jì)劃方案，在設(shè)備和原材料可能供應(yīng)的范圍內(nèi)，使得產(chǎn)品的總利潤(rùn)最大：甲產(chǎn)品乙產(chǎn)品提供量設(shè)備128臺(tái)時(shí)材料A4016kg材料B0412kg利潤(rùn)23單位元二、對(duì)偶問(wèn)題的提出它的對(duì)偶問(wèn)題就是一個(gè)價(jià)格系統(tǒng)，使在平衡了設(shè)備和原材料的直接成本后，所確定的價(jià)格系統(tǒng)最具有競(jìng)爭(zhēng)力。（用于生產(chǎn)第i種產(chǎn)品的資源轉(zhuǎn)讓收益不小于生產(chǎn)該種產(chǎn)品時(shí)獲得的利潤(rùn)）

若工廠自己不生產(chǎn)甲和乙產(chǎn)品，將現(xiàn)有的設(shè)備及原材料轉(zhuǎn)為外租時(shí)，那么上述的價(jià)格系統(tǒng)能保證不虧本又最富有競(jìng)爭(zhēng)力（包工及原材料的總價(jià)格最低）。

當(dāng)原問(wèn)題和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)，這一對(duì)線性規(guī)劃對(duì)應(yīng)的目標(biāo)函數(shù)值是相等的：

Zmax=Wmin=14

對(duì)偶變量的經(jīng)濟(jì)意義可以解釋為對(duì)設(shè)備及原材料的單位定價(jià)。表示對(duì)偶關(guān)系3.再舉一個(gè)對(duì)偶問(wèn)題的例子：飲食與營(yíng)養(yǎng)問(wèn)題

例2

采購(gòu)甲、乙、丙、丁4種食品量分別為x1，x2，x3，x4單位，在保證人體所需維生素A、B、C前提下，使總的花費(fèi)最小。

成本構(gòu)建對(duì)偶線性規(guī)劃模型：

換一個(gè)角度，生產(chǎn)營(yíng)養(yǎng)藥制品公司力圖制造各種營(yíng)養(yǎng)藥品代替食品。于是，營(yíng)養(yǎng)藥品的單位成本不能超過(guò)相應(yīng)食品的市場(chǎng)價(jià)格。制藥公司面對(duì)的問(wèn)題是為營(yíng)養(yǎng)藥品確定單價(jià)，以獲得最大的收益，同時(shí)與真正的食品競(jìng)爭(zhēng)。由此得到下面的對(duì)偶問(wèn)題：二、原問(wèn)題和對(duì)偶問(wèn)題的關(guān)系1.對(duì)稱形式的對(duì)偶關(guān)系（1）定義：若原問(wèn)題是

則定義其對(duì)偶問(wèn)題為:這兩個(gè)式子之間的變換關(guān)系稱為“對(duì)稱形式的對(duì)偶關(guān)系”。

（2）對(duì)稱形式的對(duì)偶關(guān)系的矩陣描述（L）

（3）怎樣從原始問(wèn)題寫(xiě)出其對(duì)偶問(wèn)題？

對(duì)稱性問(wèn)題按照定義“上、下”交換，“左、右”換位，不等式變號(hào)，“極大”變“極小”例3

寫(xiě)出下面線性規(guī)劃的對(duì)偶規(guī)劃

（1）原問(wèn)題（2）

對(duì)偶問(wèn)題特點(diǎn)：對(duì)偶變量符號(hào)不限，系數(shù)陣轉(zhuǎn)置。(特點(diǎn)：等式約束)2.非對(duì)稱形式的對(duì)偶關(guān)系：為什么？證明略?？匆粋€(gè)具體例子：例4

寫(xiě)出下面線性規(guī)劃的對(duì)偶規(guī)劃：

原問(wèn)題（或?qū)ε紗?wèn)題）

對(duì)偶問(wèn)題（或原問(wèn)題）

目標(biāo)函數(shù)MaxZ目標(biāo)函數(shù)MinW約束條件數(shù)：m個(gè)第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“=”

對(duì)偶變量數(shù)：m個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量是自由變量

決策變量數(shù)：n個(gè)第j個(gè)變量≥0第j個(gè)變量≤0第j個(gè)變量是自由變量

約束條件數(shù)：n第j個(gè)約束條件類型為“≥”第j個(gè)約束條件類型為“≤”第j個(gè)約束條件類型為“=”

（2）原始問(wèn)題與對(duì)偶問(wèn)題關(guān)系表對(duì)偶定理是揭示原始問(wèn)題與對(duì)偶問(wèn)題解之間重要關(guān)系的

定理1

對(duì)稱性定理(證明略)

對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。第4節(jié)

線性規(guī)劃的對(duì)偶理論一系列定理。定理2弱對(duì)偶定理對(duì)于任意的可行解成立該結(jié)論對(duì)非對(duì)稱形式的對(duì)偶問(wèn)題同樣成立。由該定理可以得到關(guān)于“界”的結(jié)果:極小化問(wèn)題有下界——推論1

極大化問(wèn)題的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題最優(yōu)目標(biāo)函數(shù)值的一個(gè)下界。極大化問(wèn)題有上界——推論2

極小化問(wèn)題的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題最優(yōu)目標(biāo)函數(shù)值的一個(gè)上界。推論3

若原問(wèn)題與對(duì)偶問(wèn)題都有可行解，則它們都有最優(yōu)解。能達(dá)到最優(yōu)（由連續(xù)函數(shù)的性質(zhì)得到）證畢推論4若原問(wèn)題(對(duì)偶問(wèn)題)為無(wú)界解，則其對(duì)偶問(wèn)題(原問(wèn)題)無(wú)可行解。其逆不真。證明由弱對(duì)偶定理得:C=bCX≤Yb弱對(duì)偶定理已知結(jié)論最優(yōu)解定義X=CX≤bY=特別取C≤Yb證明思路若原問(wèn)題有最優(yōu)，則對(duì)偶問(wèn)題也有最優(yōu)，且最優(yōu)值相等，反之亦然。定理4強(qiáng)對(duì)偶定理推論對(duì)偶問(wèn)題的最優(yōu)解為原問(wèn)題最優(yōu)表中，相應(yīng)的松弛變量的檢驗(yàn)數(shù)的相反數(shù)。單純形方法計(jì)算過(guò)程:略講甲產(chǎn)品乙產(chǎn)品提供量設(shè)備128臺(tái)時(shí)材料A4016kg材料B0412kg利潤(rùn)23單位元定理5互補(bǔ)松弛定理略講為了保證檢驗(yàn)數(shù)的非正性取第6節(jié)

對(duì)偶單純形法最小比值原則為了保證檢驗(yàn)數(shù)的非正性取應(yīng)知道此方法：回到（55張）前幾張PPT總結(jié)對(duì)偶單純性方法。作業(yè)P-73-1.12P-73-1.125/7202實(shí)際上，此題為無(wú)界解。舉例：舉例：第7節(jié)

靈敏度分析將模型寫(xiě)在黑板上二、思考練習(xí)考察線性規(guī)劃問(wèn)題(1)：一、討論總結(jié)對(duì)偶定理的應(yīng)用。寫(xiě)出其對(duì)偶問(wèn)題;討論：如果知道是原問(wèn)題的可行解（用什麼辦法可以較方便地尋找一個(gè)可行解？），能否對(duì)對(duì)偶問(wèn)題的目標(biāo)函數(shù)值做出估計(jì)？以此為啟發(fā)，能否對(duì)原問(wèn)題目標(biāo)函數(shù)值作出估計(jì)？