運籌學(xué)對偶問題ppt課件(2)(已修改)
2025-05-15 18:35 本頁面
【正文】 第二章 LP的對偶理論與靈敏度分析 線性規(guī)劃的對偶問題 I II 每天可用能力 設(shè)備 A（ h） 設(shè)備 B（ h） 調(diào)試工序（ h） 0 6 1 5 2 1 15 24 5 利潤（元） 2 1 問公司應(yīng)每天制造兩種家電各多少件，使獲取的利潤最大。 例 1 ???????????????0,52426155s . t .2m a x212121221xxxxxxxxxz問題 美佳公司愿意以多大的代價出讓自己所擁有的生產(chǎn)資源？ 設(shè) y1,y2和 y3分別表示出讓資源 A， B和調(diào)試工序的單價，則美佳公司同意出讓的條件將是 同意出讓生產(chǎn)產(chǎn)品 I的資源 同意出讓生產(chǎn)產(chǎn)品 II的資源 購買者希望用最少的代價獲得這些資源 ，因此 26 32 ?? yy125 321 ??? yyy321 52415m i n yyyz ???這樣得到一個新的線性規(guī)劃問題 ??????????????0,1252652415m i n32132132321yyyyyyyyyyyw稱這一問題是原來的 LP問題的 對偶線性規(guī)劃問題 或 對偶問題 ，原來的 LP問題也稱為原問題 。 LP問題的對稱形式 ? 變量 ：所有變量均具有非負約束 ? 約束條件 ： 最大化問題 所有約束條件都是“ ≤”型的 最小化問題 所有約束條件都是“ ≥”型的 對稱形式下的對偶關(guān)系 項目 原問題 對偶問題 A b C 目標函數(shù) 約束條件 決策變量 約束條件系數(shù)矩陣 約束條件右端項向量 目標函數(shù)系數(shù)向量 max z=CX AX≤b X≥0 約束條件系數(shù)矩陣轉(zhuǎn)置 目標函數(shù)的系數(shù)向量 約束條件的右端項向量 min w=Yb’ A’Y ≥C’ Y ≥0 原問題 max z 對偶問題 min w n個決策變量 m個約束條件 n個約束條件 m個決策變量 約束條件“ ≤”型 決策變量 ≥0 決策變量 ≥0 約束條件“ ≥”型 對稱形式的對應(yīng)關(guān)系 對偶問題的對偶是原問題，即對偶關(guān)系是相互對稱的關(guān)系 非對稱形式下的對偶關(guān)系 原問題 （對偶問題） max z 對偶問題 （原問題） min w n個決策變量 m個約束條件 n個約束條件 m個決策變量 約束條件“ ≤”型 約束條件“ ≥”型 約束條件“ =”型 決策變量 ≥0 決策變量 ≤0 決策變量無約束 決策變量 ≥0 決策變量 ≤0 決策變量無約束 約束條件“ ≥”型 約束條件“ ≤”型 約束條件“ =”型 單純形法的矩陣表示 ??????0m a xXbAXCXz? ?? ?NBNBCCCNBAXXX????????? ,????????00m a xXbIXAX SXCXz sbBXBNXBIXbIXNXBXSNBSNB111 ??? ??????原來添加松弛變量 XS 將 XB的系數(shù)矩陣化為單位矩陣 ???????????0,00m a xNBSNBXXCXCzXXbIXNXBXsNNBBCB CN 0 XB XN XS 0 XS b B N I CB CN 0 CB CN 0 XB XN XS CB XB B1b I B1N B1 0 CN –CBB1N –CB
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1