4線性規(guī)劃對偶問題(專業(yè)版)

　　

【正文】 制造 B產(chǎn)品每件需勞動力 5人，原料 8公斤，電力5度，工廠可使用的勞動力最多為 3500人，原料最多為 4000公斤，電力最多為 2022度， A產(chǎn)品每件利潤 6元， B產(chǎn)品每件利潤 7元，問如何安排生產(chǎn)，才使工廠的利潤最大？可列出如下的線性規(guī)劃模型： 52對偶問題解的意義設(shè) y1,y2分別是 A， B產(chǎn)品的生產(chǎn)量，則：可求得最優(yōu)解：53對偶問題解的意義 最優(yōu)單純形表如下：最優(yōu)基底 B=(P1， P4， P2)， B1=？工廠的勞動力增加一個單位，工廠可增加多少利潤？54對偶問題解的意義設(shè)工廠的勞動力從 3500增加到 3500+?b1在基底 B下，基本解為 B1(b+ ?b)此時，目標函數(shù)值為：55對偶問題解的意義勞動力每增加一個單位，工廠可增加利潤： 16/25同理可算得電力每增加一個單位，工廠可增加利潤： 19/25原料增加下一個單位，工廠可增加多少利潤？利潤增加為 056對偶問題解的意義原料的增加，工廠的利潤不能增加。即在單純形表中要求檢驗數(shù)行小于零，而初始基本解不一定可行。18無界性l 若（ LP）的目標函數(shù) (求 Max)在可行域內(nèi)無上界，則對偶問題（ LD）是不可行的。16弱對偶性：弱對偶性：17最優(yōu)性l 若 X＊ ， Y＊ 分別是（ LP）和（ LD）的可行解，且 CTX＊ ＝ bTY＊ ，則 X＊ ， Y＊ 分別是（ LP）和（ LD）的最優(yōu)解。?0則 x是 (LP)的最優(yōu)解。對偶問題的目標函數(shù)：第一個約束對應(yīng)于第一個變量。58某房產(chǎn)公司有水泥 120單位，木材 160單位和玻璃 400單位，用以建造 A型和 B型住宅，建一棟 A型住宅需用水泥，木材，玻璃分別為 1， 2， 2個單位，售價每棟 100萬元，建一棟 B型住宅需用水泥，木材，玻璃分別為1， 2， 5個單位，售價每棟 150萬元，公司如何安排這兩種住宅的建設(shè)，可使銷售收入最大？設(shè) A， B型住宅各建 x1,x2棟：則銷售收入為： 100x1+150x2水泥約束： x1+x2?120木材約束： x1+x2 ? 160玻璃約束： x1+5x2 ? 400596061最優(yōu)解： A型住宅建 50棟， B型住宅建 60棟，最大收入 14000。39原問題與對偶問題之間的關(guān)系l 原問題 (LP)的第 i約束條件為 ?型，則對偶問題 (LD)的第 i個變量 yi ?0。19無界性l 該定理的逆定理不成立。10線性規(guī)劃的對偶問題稱 (LP)和 (LD)是一對相互對偶的線性規(guī)劃問題目標函數(shù)求最小，約束條件寫成大于等于；目標函數(shù)求最大，約束條件寫成小于等于。27用對偶單純形法求解 (