4線性規劃對偶問題(留存版)

　　

【正文】 LD),列出初始單純形表如下：28最優解：剩余變量 y3,y4下的檢驗數： 24, 8最優單純形表可求得最優解如下：對偶問題的最優解 ：y1=24 ,y2=829對偶問題（ LP）的初始單純形表如下：30最優解：松弛變量的檢驗數：2 , 231標準形式的對偶問題最優解的性質若標準形式（ LP）有基本最優解 y＊ ，且：則 (LD)的最優解為：標準形式的對偶問題：（ LP）中基本最優解y*的檢驗數？32標準形式的對偶問題最優解的性質基本解 y*的檢驗數： CT –CBTB1A? 0ATy*=AT(CBTB1)T?C y*是對偶問題的可行解對偶問題（ LD）的目標函數值原問題（ LP）的目標函數值f*=z*,兩目標函數值相等 。l (LP)的每一個約束對應于 (LD)的每一個變量。相應的對偶變量 y2,y30 增加這兩種資源， 可使利潤增加！增加這種資源，利潤不能增加 !64對偶問題的最優解？第一第二個約束是緊的。l 原問題 (LP)的第 i個變量 yi為 ? 0，則對偶問題 (LD)的第 i個約束條件為 ?型 。20(LP)和 (LD)都是不可行的。1線性規劃的對偶問題的例子某工廠生產 A， B兩種產品，已知制造 A產品每件需勞動力 7人，原料 5公斤，電力 2度。無界性的逆定理不成立21互補松弛性質22互補松弛性質l 若（ LP）有最優解 X * ，則（ LD）也有最優解Y * ，且有 X * TV * ＝ 0， Y * TU * ＝ 0l 其中 V * ＝ ATY * － C ， U * ＝ b － AX * 。l 原問題 (LP)的第 i個變量 yi無非負限制 ，則對偶問題(LD)的第 i個約束條件為 =型 。求解：最優解：。l 同樣對偶問題 (LD)的目標函數求 Min,主約束條件為?型，則稱此約束為規范約束，否則稱為非規范約束。2425(LD)的剩余變量：(LP)的松弛變量：它們的最優解滿足互補松弛性質 !26對偶問題最優解的性質l 對稱形式：l 若（ LP）有最優解 X＊ ， 則對偶問題（ LD）也有最優解 Y＊ ， 且 y＊ 是（ LP）最優單純形表中松弛變量 V下的檢驗數的負值； X＊ 是（ LD）最優單純形表中剩余變量 U下的檢驗數的負值。7線性規劃的對偶問題現有某個制藥廠要推銷維生素 B和維生素 C藥劑，廠商希望飼養場能夠用維生素 B和維生素 C藥劑來配制混合飼料，為做到這一點，必須保證維生素 B和維生素 C的價格不超過上述兩種配料，在這種條件下，應如何確定維生素 B和 C藥劑的價格，使制藥廠的