第二章對偶規(guī)劃

（1）標準型的矩陣形式——

（2）將式中矩陣寫成分塊矩陣形式

第2章

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

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

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

單純形乘子

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

cj

CB

XB

xjbCBCN

0

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

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

對偶問題的提出----§1.6對偶是指對同一問題從不同的角度觀察，得到兩種獨立的表述的思想。例1

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

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

當原問題和對偶問題都取得最優(yōu)解時，這一對線性規(guī)劃對應的目標函數(shù)值是相等的：

Zmax=Wmin=14

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

例2

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

成本構建對偶線性規(guī)劃模型：

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

則定義其對偶問題為:這兩個式子之間的變換關系稱為“對稱形式的對偶關系”。

（2）對稱形式的對偶關系的矩陣描述（L）

（3）怎樣從原始問題寫出其對偶問題？

對稱性問題按照定義“上、下”交換，“左、右”換位，不等式變號，“極大”變“極小”例3

寫出下面線性規(guī)劃的對偶規(guī)劃

（1）原問題（2）

對偶問題特點：對偶變量符號不限，系數(shù)陣轉置。(特點：等式約束)2.非對稱形式的對偶關系：為什么？證明略?？匆粋€具體例子：例4

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

原問題（或對偶問題）

對偶問題（或原問題）

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

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

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

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

（2）原始問題與對偶問題關系表對偶定理是揭示原始問題與對偶問題解之間重要關系的

定理1

對稱性定理(證明略)

對偶問題的對偶是原問題。第4節(jié)

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

極大化問題的任意一個可行解所對應的目標函數(shù)值是其對偶問題最優(yōu)目標函數(shù)值的一個下界。極大化問題有上界——推論2

極小化問題的任意一個可行解所對應的目標函數(shù)值是其對偶問題最優(yōu)目標函數(shù)值的一個上界。推論3

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

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

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