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