運(yùn)籌學(xué)二章對(duì)偶線性規(guī)-wenkub
2023-05-21 15:18:23 本頁(yè)面
【正文】 x3 . x1+3x2+4x3≥2 2x1+ x2+3x3≤3 x1+4x2+3x3=5 x1 ≥0, x2≤0 maxw=2y1+3y2+5y3 . y1+2y2+ y3≤2 3y1+ y2+4y3≥ 2 4y1+3y2+3y3≥4 y1≥0,y2≤0 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 18 課后作業(yè) P74 (4) 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 19 對(duì)偶問(wèn)題的基本性質(zhì) ?單純形法的矩陣描述 ?對(duì)偶問(wèn)題的基本性質(zhì) 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 20 一、單純形法計(jì)算的矩陣描述 Max Z=CX AX≤b X≥0 Max Z=CX AX+Xs=b X ≥0,Xs≥0 引入松弛變量 令 X=(XB,XN)T C=(CB,CN) A=(B,N) ?????????????????????????????????0,),(),(SNBSNBNNBBNBNBXXXbXXXNBXCXCXXCCM a x Z BXB+NXN+XS=b B1BXB+B1NXN+B1XS=B1b XB=B1bB1NXNB1XS MaxZ=CB(B1bB1NXNB1XS)+CNXN =CBB1b＋（ CNCBB1N)XNCBB1XS 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 21 某一決策變量 xk系數(shù)列向量迭代前為 Pk，迭代后為 B1Pk。YC?????????由此可以看出，當(dāng) X為最優(yōu)解時(shí)， Y為對(duì)偶問(wèn)題的可行解。 (對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題無(wú)界解或無(wú)可行解。 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 26 如果 X*,Y*分別為 LP,LD問(wèn)題的可行解，則 X*,Y*為最優(yōu)解的充要條件為： Y*’XS*=0 YS*’X*=0 ??????????0,0 SSXXbXAXCXM axZLP證明：設(shè) ???????????0Y,0YCYYbYi n WD 39。*39。***)()(,XYAYCXbYXAXYbYCXYXSS ???????為最優(yōu)解時(shí)，有當(dāng)**39。*39。??????????????? 當(dāng) LP中第 i個(gè)約束是嚴(yán)格不等式，則 Y中的 Yi必為0，如果 Yi不為 0,則 LP中第 i個(gè)約束為嚴(yán)格等式。 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 30 例：美佳公司 ???????????????0,52426155LP2212121221xxxxxxxxxM a x Z???????????????3,2,1,012526LD5241532132321jyyyyyyyyyM i n Wj…… ① …… ② …… ③ X*=(7/2,3/2,15/2,0,0)’ Z*= 由 1）可知： y1*為①變?yōu)?5x2≤16時(shí) Z*的增量， y1*＝ △ Z*＝ 0 Y2*為 ② 變?yōu)?6x1＋ 2x2≤25時(shí) Z*的增量 所以當(dāng) A的資源增加時(shí)， Z*無(wú)變化， Y1*＝ 0 LP中①約束為嚴(yán)格的不等式，表明 A沒(méi)有被充分利用。 3）新產(chǎn)品是否投產(chǎn)以及合理定價(jià)的問(wèn)題 ??? ???? miiijjjBjj yacPBCc11?例：美佳考慮生產(chǎn) 電器 Ⅲ ，要耗 A 3 ， B 2，調(diào)試 1個(gè)單位，市場(chǎng)價(jià)格 2元，問(wèn)是否值得生產(chǎn)。 注：該方法不是求解 LD的單純形法，而是利用對(duì)偶關(guān)系求解 LP的另一種方法。 如果 XB有分量 xl0，且該分量所在行的系數(shù) alj有負(fù)分量，則該解不是 LP的最優(yōu)解，繼續(xù)。 缺點(diǎn)： 不能保證所有的 Lp問(wèn)題的初始單純形表中的 δj≤0。通常把 X*代入新的約束條件。 cj 2 1 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x3 15/2 0 0 1 5/4 15/2 0 2 x1 7/2 1 0 0 1/4 1/2 0 1 x2 3/2 0 1 0 1/4 3/2 0 0 x6 12 3 2 0 0 0 1 δj 0 0 0 1/4 1/2 0 0 x3 15/2 0 0 1 5/4 15/2 0 2 x1 7/2 1 0 0 1/4 1/2 0 1 x2 3/2 0 1 0 1/4 3/2 0 0 0 0 1 0 x6 3/2 1/4 3/2 δj 0 0 0 1/4 1/2 0 θ 1 1/3 [ ] 0 x5 1 0 0 0 1/6 1 2/3 0 x3 15 0 0 1 5/2 0 5 2 x1 4 1 0 0 1/3 0 1/3 1 x2 0 0 1 0 1/2 0 1 δj 0 0 0 1/6 0 1/3 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 48 五、技術(shù)系數(shù) Pj發(fā)生變化分析 通常是按列即 Pj發(fā)生變化，該變化可轉(zhuǎn)變?yōu)樵黾?xj的情況： ?δk≤0 則 X*,Z*不變 ?δk＞ 0 在最終單純形表上進(jìn)行基變換（添加一個(gè)變量，增加一列），系數(shù)列向量應(yīng)相應(yīng)變化 Pk’=B1Pk 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 49 課后作業(yè) 。 若不滿足，把新約束放入最終單純形表中，用初等行變換使變成基解，再用對(duì)偶單純形法變換。 ?X*中基變量改變， Z*改變 XB XN XS XS B N I b XB I B1N B1 B1b δ 0 CNCBB1N CBB1 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 41 一、分析 cj變化 1. 當(dāng) CNj發(fā)生變化時(shí)， 對(duì)應(yīng)的 δNj變化 ? δNj≤0 X*,Z*不變 ? δNj＞ 0 用單純形法進(jìn)行基變換 XB XN XS XS B N I b XB I B1N B1 B1b δ 0 CNCBB1N CBB1 2. 當(dāng) CBi發(fā)生變化時(shí)， 所有 δNj變化 ? δNj≤0 X*不變 ,Z*變化 ? δNj＞ 0 用單純形法進(jìn)行基變換 2021/6/16 浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系 42 例 5：美佳公司 C1由 2變?yōu)?， 當(dāng) C2由 1變?yōu)?2時(shí)，最優(yōu)解有什么變化？ C1不變， C2在什么范圍內(nèi)變換時(shí)，最優(yōu)解不變？ Cj 2
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1