3.1 線性規劃的對偶問題
一、 對偶問題的提出
換位思考
家具廠的線性規劃問題，該問題站在家具廠管理者的角度追求銷售收入最大
某企業家有一批待加工的訂單，有意利用該家具廠的木工和油漆工資源來加工他的產品。他
需要與家具廠談判付給該廠每個工時的**。如果該企業家已對家具廠的經營情況有詳細了
解，他可以構造乙個數學模型來研究如何才能既讓家具廠覺得有利可圖，肯把資源出租給他，
又使自己付的租金最少。
目標:租金最少；-付給木工工時的租金；-付給油漆工工時的租金
所付租金應不低於家具廠利用這些資源所能得到的利益
1）支付相當於生產乙個桌子的木工、油漆工的租金應不低於生產乙個桌子的收入
2）支付相當於生產乙個椅子的木工、油漆工的租金應不低於生產乙個椅子的收入
3）付給每種工時的租金應不小於零
二、 原問題與對偶問題的數學模型
1. 對稱形式的對偶
原問題和對偶問題只含有不等式約束時，一對對偶問題的模型是對稱的，稱為對稱形式的對偶。
原問題：
對偶問題：
2. 非對稱形式的對偶
若原問題的約束條件全部是等式約束（即線性規劃的標準型），即
則其對偶問題的數學模型為
可把原問題寫成其等價的對稱形式：
min z =cx
axbaxb
x0即min z =c***0
設y1=(y1,y2,…,ym), y2=(ym+1,ym+2,…,y2m)。根據對稱形式的對偶模型，寫出上述問題的對偶問題：
max w =(y1,y2)·
(y1,y2)·c
y10 y20
即max w =( y1-y2)·b
( y1-y2)ac
y10 y20
令y= y1-y2, 得對偶問題為：
max w = yb
yacy是自由變數
3. 原問題與對偶問題的對應關係
原問題：
對偶問題：
原問題：
對偶問題：
3.2 對偶問題的基本性質和基本定理
一、 對稱性定理
對稱性定理：對偶問題的對偶是原問題。
二、 弱對偶性定理
弱對偶性定理：若x和y分別是原問題和對偶問題的可行解，則有c xyb。
三、 最優性定理
最優性定理：若x和y分別是原問題和對偶問題的可行解，且有c x=yb，則x
和y分別是原問題和對偶問題的最優解。
四、 對偶定理
對偶定理：有一對對偶的線性規劃問題，若其一有乙個有限的最優解，則另乙個也有最優解，
且相應的目標函式值相等。若任乙個問題具有無界解，則另乙個問題無可行解。
五、 單純型乘子y的定理
單純型乘子y的定理：若線性規劃原問題有乙個對應於基b的最優基本可行解，則此時的單
純型乘子y= cb是相應於對偶問題的乙個最優解。
六、 對稱形式對偶的互補鬆弛定理
對稱形式對偶的互補鬆弛定理：若x和y分別是原問題和對偶問題的可行解，則x和
y都是最優解的充要條件是，對所有i和j，下列關係式成立：
1. 如果x>0，必有yp=c
2. 如果y p< c，必有x=0
3. 如果y>0，必有ax=b
4. 如果ax>b，必有y=0
其中p是a的第j列，a是a的第i行。
互補鬆弛定理意味著：如果原問題最優解x中第j個變數x為正，則其對偶問題中與之
對應的第j個約束式在最優情況下必呈嚴格等式（即其鬆弛變數為0）；而如果對偶問題中
第j個約束式在最優情況下呈嚴格不等式，則原問題最優解x中第j個變數x必為0。
類似地，如果對偶問題最優解y中第i個對偶變數y為正，則其原問題中與之對應的第
i個約束在最優情況下必呈嚴格等式（即其剩餘變數為0）；而如果原問題中第i個約束在
最優情況下呈嚴格不等式，則對偶問題最優解y中第i個對偶變數y必為0。
互補鬆弛性： 為最優解
對一對對偶規劃的最優解而言，如果對應某一約束條件的對偶變數的值為非零，則該約
束條件取嚴格等式；反之，如果某個約束條件取嚴格不等式，則其對應的對偶變數一定為零。
七、 非對稱形式對偶的互補鬆弛定理
非對稱形式對偶的互補鬆弛定理：若x和y分別是原問題和對偶問題的可行解，則x
和y都是最優解的充要條件是，對所有j，下列關係式成立：
1. 如果x>0，必有yp=c
2. 如果y p< c，必有x=0
例：已知線性規劃問題
試用對偶理論證明上述線性規劃問題無最優解
該問題存在可行解，如
又對偶問題為
由第乙個約束條件知對偶問題無可行解，由此可知其原問題無最優解
八、 最優對偶變數（影子**）的經濟解釋
由對偶定理可知，當達到最優解時，原問題和對偶問題的目標函式值相等。
如果在得到最優解時，某種資源並未完全利用，其剩餘量就是該約束中剩餘變數的取值，那
麼該約束相對應的影子**一定為零。因為在得到最優解時，這種資源並不緊缺，故此時再
增加這種資源不會帶來任何效益。反之，如果某種資源的影子**大於零，就說明再增加這
種資源的可獲量，還回帶來一定的經濟效益，即在原問題的最優解中，這種資源必定已被全
部利用，相應的約束條件必然保持等式。
第四章對偶線性規劃問題
1.略2.用對偶單純形方法解1.1 解 把問題標準化 即 1 作對應於對偶可行基的單純形表 2 因表中基變數值有負數，而且 2對應的行都有負數，所以要進行換基迭代。3 換基迭代 求軸心項 以基變數中 2對應的行中所有負數去除檢驗數，其中最小的商1所對應的除數 1就是軸心項。進行換基迭代得新基 因為表...
寫出下列線性規劃問題的對偶問題 10分
二 求解下列線性規劃問題 15分 三 分配甲 乙 丙 丁四個人去完成a b c d e五項任務，每個人完成各項任務的時間如下表所示。由於任務數多於人數，故考慮任務e必須完成，其它4項中可任選3項完成，試確定最優分配方案，使完成任務的總時間為最少。15分 單位 小時 四 某河流中有幾個島嶼，如下圖所示...
運籌學 第二章線性規劃的對偶問題
習題二2.1 寫出下列線性規劃問題的對偶問題 1 max z 10x1 x2 2x3 2 max z 2x1 x2 3x3 x4 st.x1 x2 2 x3 10st.x1 x2 x3 x4 5 4x1 x2 x3 202x1 x2 3x3 4 xj 0 j 1,2,3x1 x3 x4 1 x1，x...