線性規劃的對偶理論課件(PPT 47頁)

對偶的定義
對偶問題的性質
對偶的經濟解釋
線性規劃的對偶理論
對偶原理
對偶問題概念：
任何一個線性規劃問題都有一個與之相對應
的線性規劃問題，如果前者稱為原始問題，後者
就稱為“對偶”問題。
對偶問題是對原問題從另一角度進行的描述
其最優解與原問題的最優解有著密切的聯係，在
求得一個線性規劃最優解的同時也就得到對偶線
性規劃的最優解，反之亦然。
對偶理論就是研究線性規劃及其對偶問題的
理論，是線性規劃理論的重要內容之一。
問題的導出
對偶問題的定義
原始問題
對偶問題的特點
（1）目標函數在一個問題中是求最大值在另一問題中則為求最小值
（2）一個問題中目標函數的係數是另一個問題中約束條件的右端項
（3）一個問題中的約束條件個數等於另一個問題中的變量數
（4）原問題的約束係數矩陣與對偶問題的約束係數矩陣互為轉置矩陣
3、互補鬆弛性
練習
已知線性規劃問題
THEEND
對偶單純形法
對偶單純形法的原理
對偶單純形法的應用步驟
對偶單純形法舉例
對偶單純形法的應用條件
對偶單純形法的優點和缺點
對偶單純形法原理
對偶單純形法應用條件
應用前提：
有一個基，其對應的基滿足:
①單純形表的檢驗數行全部非正（對偶可行）；
②變量取值可有負數（非可行解）。
對偶單純形法步驟
找一個基（可以不是可行的），建立初始對偶單純形表，檢驗數全部非負；
若b列元素非負，則已經是最優基。反之，則取相應行的基變量為出基變量
..............................