[高等教育]4線性規(guī)劃的對偶問題(更新版)
【正文】 y y? ? ?? ? ???? ? ?????兩個線性規(guī)劃之間的關(guān)系？ 5 線性規(guī)劃的對偶問題 飼養(yǎng)場的混合飼料由兩種配料組成，混合飼料 必須含有維生素 B和維生素 C，并且維生素 B和 C的含量分別不低于 5和 6，現(xiàn)已知第一種配料中 每單位維生素 B含量為 3，維生素 C含量為 3，單 價為 13，第二種配料中每單位維生素 B含量為 1， 維生素 C含量為 4，單價為 10，問在保證營養(yǎng)的 條件下，應(yīng)如何配方，使混合飼料的費用最小？ 6 線性規(guī)劃的對偶問題 設(shè)第一種配料用 x1單位，第二種配料用 x2單位 第一個約束為維生素 B的含量， 第二個約束為維生素 C的含量。 18 無界性 ? 若（ LP）的目標函數(shù) (求 Max)在可行域內(nèi)無上界，則對偶問題（ LD）是不可行的。 ? 証：若 y＊ ， Y＊ 分別是（ LP）和（ LD）的最優(yōu)解，則 CTX*=bTY*. 23 將它們化成標準形式，并求出最優(yōu)解。 即在單純形表中要求檢驗數(shù)行小于零，而 初始基本解不一定可行。 40 原問題與對偶問題之間的關(guān)系 ? 原問題 (LP)的目標函數(shù)求 May,主約束條件為 ?型，則稱此約束為規(guī)范約束，否則稱為非規(guī)范約束。制 造 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) ??????????????????????????? ????????????????12521259151125725225312595151280260300202240003500010bbbb此時，目標函數(shù)值為： 1251612521513 7 6 0)2 8 0(7)3 0 0(6*bbbS???????????55 對偶問題解的意義 勞動力每增加一個單位，工廠可增加利潤： 16/25 同理可算得電力每增加一個單位，工廠可增加利潤： 19/25 ???????????????????????????????????????????325732531351325725225312595151280260300202240003500010bbbb3251932573513 7 6 0)2 8 0(7)3 0 0(6*bbbS???????????原料增加下一個單位， 工廠可增加多少利潤？ 利潤增加為 0 56 對偶問題解的意義 原料的增加，工廠的利潤
教學課件相關(guān)推薦
鄂ICP備17016276號-1