運籌學課件第二章線性規(guī)劃的對偶理論與靈敏度分析-在線瀏覽
2025-07-17 22:15本頁面
【正文】 種資源的出讓價格，為了使工廠出讓資源合算，顯然應該使出讓原來生產一件產品 Ⅰ的資源所得收入不低于自己生產產品 Ⅰ 的利潤，即 0y1+6y2+1y3 ≥2 對于產品 Ⅱ ，同樣可以建立類似的約束條件 5y1+2y2+1y3≥1 項目 產品 Ⅰ 產品 Ⅱ 每天可用能力 設備 A(h) 設備 B(h) 調試工序 (h) 0 6 1 5 2 1 15 24 5 利潤 (元 ) 2 1 y1 y2 y3 運籌學教程 當原問題和對偶問題都取得最優(yōu)解時，這一對線性規(guī)劃對應的目標函數(shù)值是相等的： Zmax=Wmin 顯然在滿足這兩個約束的前提下，價格越高，該工廠越合算，但價格太高，投資人方面又不會愿意購買。 運籌學教程 ??????????????????????????0,..21221122222112112211112211mnnmnnnnmmmmmyyycyayayacyayayacyayayatsybybybM i n W??????????????????????????????????0,..21221122222112112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMa x Z????????運籌學教程 （ 2） 對稱形式的對偶關系的矩陣描述 ???????0..YCYAtsYbbYM i n WTTTT（ D） ??????0..XbAXtsCXM a x Z（ L） （ 3） 從原問題寫出其對偶問題 按照定義； 記憶法則： “ 上 、 下 ” 交換 ， 換后矩陣轉置 。33239。333332321312232322212139。3339。3239。33322339。33322339。33222239。33122139。332239。 運籌學教程 準備工作： （ 1）標準型的矩陣形式 —— ?????????0,0..0SSSXXbIXAXtsXCXM a x Z（ 2）將式中矩陣寫成分塊矩陣形式 )( NB CCC ?? )( NB XXX ??)(),.. .,(],[ 21 INBPPPPIA mnn ????? ??運籌學教程 將分塊形式代入矩陣形式標準型 ， 得出兩個基本表達式： （ 1） 由約束條件 bIXNXBXIXXXNBIXAX SNBSNBS ????????????????? )( ?可得 用非基變量表示基變量的表達式： SNSNBXBNXBbBIXNXbBX1111 )(??????????運籌學教程 項目 非基變量 基變量 XB XN XS 0 XS b B N I CjZj CB CN 0 項目 基變量 非基變量 XB XN XS CB XB B1 b I B1 N B1 CjZj 0 CN CB B1 N CB B1 迭代后的單純形表 初始單純形表 對應初始單純形表中的單位陣 I， 迭代后為 B1 基變量的變換： 初始 XS=b； 迭代后 XB= B1b 約束系數(shù)矩陣的變化： [A,I]=[B,N,I]； [B1 A, B1 I]=[B1 B, B1 N, B1 I]=[I, B1 N, B1]. 約束系數(shù)矩陣的向量變化： PjT = B1 Pj CB CN 0 運籌學教程 檢驗數(shù)： CNCB B1 N≤0 (1)。 令 :CBCBI=0 (2) (1)+(2)得到 CNCB B1 N +CBCBI= CNCB B1 N +CBCBB1B =CB+CNCBB1(B+N)=CCBB1A ≤0 CB B1 ≤0。 Y≥0 Wmin= Y Tb= CBB1b=Zmax CYTA ≤ 0 C ≤ YTA C T≤ (YTA)T 檢驗數(shù)的相反數(shù)為其對偶問題的一個可行解 運籌學教程 ?????????????????????052426155.0002m a x3521242113254321jxyxxxyxxxyxxstxxxxxZ??????????????????012526.0052415m i n25321143154321iyxyyyyxyyyst
環(huán)評公示相關推薦
鄂ICP備17016276號-1