運(yùn)籌學(xué)作業(yè)-王程130404026

1、運(yùn)籌學(xué)作業(yè)王程信管1302130404026目錄運(yùn)籌學(xué)作業(yè)1第一章線性規(guī)劃及單純形法 3第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析 24第三章運(yùn)輸問題53第四章目標(biāo)規(guī)劃63第五章整數(shù)規(guī)劃73第六章非線性規(guī)劃85第七章動(dòng)態(tài)規(guī)劃94第八章圖與網(wǎng)絡(luò)分析97第九章網(wǎng)絡(luò)計(jì)劃99第一章線性規(guī)劃及單純形法1.1 分別用圖解法和單純形法求下列線性規(guī)劃問題， 指出問題具有唯一最優(yōu)解、 無窮多最優(yōu)解、無界解還是無可行解；當(dāng)具有限最優(yōu)解時(shí)，指出單純形表中 的各基可行解對(duì)應(yīng)圖解法中可行域的哪一頂點(diǎn)。(1) min z = 2xi 3x24xi + 6x2 6s.t. , 3xi + 2x2 4xi, x2 0(2) max

2、 z = 3xi 2x2 2x1 + x2 w 2s.t. 3xi 十 4x2 至 i2xi, x2 0(3) max z = i0 xi + 5x23xi 4x2 9s.t. 5xi 2x28xi, x2 二 0解：圖解法：ax2(4) max z = 5xi 6x22xi - x2 至 2s.t. -2xi 3x2 02 i . .6 i當(dāng)x2 = x1- z經(jīng)過點(diǎn)（g ,g）時(shí)，z取小，且有無分多個(gè)取優(yōu)斛圖解法:該問題無可行解。圖解法：x1,1.3當(dāng)x2 = -2xi +1z經(jīng)過點(diǎn)（1,3）時(shí)，z取得唯一最優(yōu)解單純形法：在上述問題的約束條件中分別加入松弛變量為,x4 ,化為標(biāo)準(zhǔn)型:max

3、z u 10xi +5x2 0x3 0x43x1 4x2 x3 = 9i*3t *3x = (-,1,0,0) t,z =10 - 5 1 = 20 22x(0) =(0,0,9,8) t,表示圖中原點(diǎn)o(0,0 )x(1)=(8,0, 21,0)、表示圖中 c點(diǎn)55x(2) = (1,3 ,0,0) t,表示圖中 b點(diǎn)2s.t. 5x1 2x2 x4 = 8cj10500icbxbbx1x2x3x40x39341030x4852018/5cj -zj105000x321/5014/51-3/53/210x18/512/501/54cj-zj010-25x23/2015/14-3/1410x1

4、110-1/72/7cj -zj00-5/14-25/14x1,x2,x3,x4 - 0由線性規(guī)劃問題的標(biāo)準(zhǔn)型可列出單純初始形表逐步迭代，計(jì)算結(jié)果如下表所 示：單純形表的計(jì)算結(jié)果表明:單純形表迭代的第一步得單純形表迭代的第二步得單純形表迭代的第三步得圖解法：x2,51. 一 .當(dāng)x2 =5x1 -1z經(jīng)過點(diǎn)(2,2)時(shí)，z取得唯一最優(yōu)解。661.2將下述線性規(guī)劃問題化成標(biāo)準(zhǔn)形式。(1) min z= 3x1 4x2 - 2x3 5x44x1 - x2 2x3 - x4 = -2x1 + x2-x3 + 2x414s.t.2x1 3x2 x3 - x4 - 2, x2, x3 - 0,x4無約束

5、0,解：上述問題中令z = -z,x4 = x4- x4”,其中x4 - 0,x4 則該問題的標(biāo)準(zhǔn)形式為max z= 3x1 - 4x2 2x3 - 5x4- 5x44x1 x2 - 2x3 x4- x4 = 2x1 x2 - x3 2x4- 2x4 x5 = 14 s.t.2x1 3x2 x3 - x4 x4- x6 = 2”42,乂3%,4,乂6 - 0(2) min z - 2x1 - 2x2 3x3j_-x1 x2 x3 = 4s.t. 2x1x2 - x3 m 6、x1 w 0, x2 * 0, x3無約束解：上述問題中令z= -z, x, = -。5 = x3- x3”,其中x3之

6、0,x3”之0, 則該問題的標(biāo)準(zhǔn)形式為max z = 2x1 2x2 - x3 x3x1x2x3-x3= 4s.t. 2x1x2 - x3x3x4 = 6x1 , x2 , x3 , x3 , x4 1.3對(duì)下述線性規(guī)劃問題找出所有基解,(1) max z = 3x1 5x2x1+ x3 = 42 x2+ x4 = 12s.t.3x1 2x2 x5 = 18xj - 0 j =1,川,5指出哪些是基可行解，并確定最優(yōu)解。 minz = 5* - 2x2 3x3 2x4 x1 2x2 3x3 4x4 = 7s.t. 2k 2x2 x3 2x4 =3i為之。(j=1川,4)解：（1）該線性規(guī)劃問題

7、的全部基解見下表中的，打、者為基可行解，注*者為最優(yōu)解，z =36。在乒 廳pxix2x3x4x5z可行？2620036*v4306027v4600-642x094-6045x0640630v00412180v40012612v60-212018x(2)該線性規(guī)劃問題的標(biāo)準(zhǔn)形式為：max z = -5x1 2x2 - 3x3 -2x4x1 + 2x2 + 3x3 + 4x4 = 7s.t2x1+2x2+x3+2x4=3xj 至 0( j =1,111,4)其全部基解見下表中的，打、者為基可彳t解，注*者為最優(yōu)解，z*=5在乒 廳pxix2x3x4z，可行？0011-5*v0-1/202-5x0

8、-1/220-5*v-1/30011/6-2x2/5011/50-43/5v-411/20031x1.4題1.1 (3)中，若目標(biāo)函數(shù)變?yōu)?maxz = cx+d”,討論c,d的值如何變化, 使該問題可行域的每個(gè)頂點(diǎn)依次使目標(biāo)函數(shù)達(dá)到最優(yōu)。, 一cz 一z . _解：由目標(biāo)函數(shù)maxz = cx+dx2可得：x2 二為+二一 kx+二 其中k-一 d d d3當(dāng)-3wkw0時(shí)，可行域的頂點(diǎn)a使目標(biāo)函數(shù)達(dá)到最優(yōu)； 4 , 53當(dāng)-5 wk e-3時(shí)，可行域的頂點(diǎn)b使目標(biāo)函數(shù)達(dá)到最優(yōu);245當(dāng)kw?時(shí)，可行域的頂點(diǎn)c使目標(biāo)函數(shù)達(dá)到最優(yōu);2當(dāng)c=0,d e0或ce0,d =0時(shí)，最優(yōu)解為。點(diǎn)。1.6

9、分別用單純形法中的大 m法和兩階段法求解下列線性規(guī)劃問題，并指出屬 哪一類解。(1 min z = 2x1 3x2 x3 x1 4x2 2x3 - 8s.t. 3x1 2x26、x1，x2,x3 之 0(2) max z 10x1 15x2 12x35x1 3x2 x3 m 9s.t.-5x1 6x2 15x3 152x1 x2 x3 - 5x1, x2 , x3 - 0(1)解：大m怯：在上述線性規(guī)劃問題的約束條件中減去剩余變員、x5,再分別加上人工變量 %、乂7，得minz = 2x1 3x2 x3 0凡 0人 m為 mx7x十4x2+2x3 x4十凡=8s.bxi +2x2 治=6xi,

10、x2, xj,x4, xs, xj, x7 - 0其中m是一個(gè)任意大的正數(shù)，據(jù)此可列出初始單純形表如下:cj23100mm9cbxbbxix2x3x4x5x6x7mx68142-10102mx763200-1013cj-zj2-4m3-6m1-2mmm003x221/411/2-1/401/408mx7250-11/2-1-1/214/5cj-zj5 5一一m4 201m -231 g一一 m4 2m33m -2403x29/5013/5-3/101/103/10-1/102xi4/510-2/51/5-2/5-1/52/5cj-zj0001/21/2m-1/2m-1/2由單純形表的計(jì)算結(jié)果得

11、：最優(yōu)解 xt -,9,0,0,0,0,0 5,5目標(biāo)函數(shù)最優(yōu)值z(mì)* =2 4 3 9 =755x存在非基變量檢驗(yàn)數(shù) 仃3=0 ，故該線性規(guī)劃問題有無窮多最優(yōu)解。兩階段法：先在上述線性規(guī)劃問題的約束條件中減去剩余變量x4 , x5,再分別加上人工變量x6,x7，得第一階段的數(shù)學(xué)模型min w=x6 x7x1 +4x2 + 2x3 - x4 + x6 = 8s.t3xi + 2x2 - x5 + x7 = 6第一階段求得的最優(yōu)解 x* =7,9,0,00,0,0 t,目標(biāo)函數(shù)的最優(yōu)值5 5lxi,x2,x3, x4,x5,x6,x7 至 0cj00000119cbxbbxix2x3x4x5x6x

12、71x68142-101021x763200-1013cj-zj-4-6-211000x221/411/2-1/401/4081x7250-11/2-1-1/214/5cj-zj5-201_1213200x29/5013/5-3/101/103/10-1/100xi4/510-2/51/5-2/5-1/52/5cj -zj0000011據(jù)此可列出單純初始形表如下:w =0 ,因人t工變量x6 =x7 =0 ,所以.,90,0,0,0,0 |是原線性規(guī)劃問題的基可行解。于是可5 5以進(jìn)行第二階段計(jì)算，將第一階段的最終表中的人工變量取消， 并填入原問題的 目標(biāo)函數(shù)的系數(shù)，如下表：cj231009c

13、bxbbxix2x3x4x5322xi9/54/501103/5-2/5-3/10 1/51/10-2/5cj-zj0001/21/2由表中計(jì)算可知，原線性規(guī)劃問題的最優(yōu)解4 9”ccj二，二,0,0,0,0,05 5目標(biāo)函數(shù)的49 最優(yōu)值z(mì) =2父，+3父9=7,由于存在非基變量檢驗(yàn)數(shù) 仃3=0 ,故該線性規(guī)劃問題 55有無窮多最優(yōu)解。解：加法：在上述線性規(guī)劃問題的約束條件中加上松弛艾昆，減去剩余變峽,再加上人工變修，得maxz = 1(x+1% 12x3 0x4 0x5 佻 - mx5x1 +3x2十%十七=9xl, x2, x3, x4,x5, x6,x7-0其中m是一個(gè)任意大的正數(shù)，據(jù)

14、此可列出單純形表如下:cj101512000-m9cbxbbxix2x3x4x5x6x70x4953110009/50x515-56150100-mx7521100-115/2cj-zj10+2m15+m12+m00-m010xi9/513/51/51/500090x524091611003/2-mx77/50-1/53/5-2/50-117/3cj-zj09-m53 10+-m-2 - m50-m01012-mx1x3x73/23/21/210039/80 9/16-43/800103/161/16-7/16-1/80 1/16-3/8000-1001cj-zj027 43 m8800217

15、m8 1653m8 80-m0由單純性表的最終表可以看出，所有非基變量檢驗(yàn)數(shù)tj 0 ,且存在人工變量1x7 =-，故原線性規(guī)劃問題無可行解。 2兩階段法：在上述線性規(guī)劃問題的約束條件中加上松弛變量x4, x5,減去剩余變量x6，再加上人工變量x7,得第一階段的數(shù)學(xué)模型min w=x75x1 3x2 x3 x4 = 95x1 +6x2 +15x3 + x5 = 15 s.t.2x x2 x3 - x7 = 5x1,x2,x3,x4,x5,%,x7 - 0據(jù)此可列出單純初始形表如下:cj00000019cbxbx1x2x3x4x5x6x70乂4953110009/50乂515-56150100-

16、1x7521100-115/2cj-zj-2-1-1001010x19/513/51/51/500090x524091611003/21x7/50-1/53/5-2/50-117/3cj-zj0-1/53/5-2/50100x13/2139/8003/16-1/80000x33/209/1611/161/16001x71/20-43/800-7/16-3/80-11cj-zj0438007/163/8010第一階段求得最優(yōu)解x* = g0, ：0。,0,因人工變量為=“0，且非基變量檢驗(yàn)數(shù)5 0 ,所以原線性規(guī)劃問題無可行解。1.5考慮下述線性規(guī)劃問題：max z = c1x1c2x2可1為

17、a。？ “s.t. a21x1 a22x2 工 b2.七, x2 t 0式中,1eg 3,4 c2 6, -1 an 3,2 012 5,8 bi 12,2 821 4,4 %2工6, 10mb2m14,試確定目標(biāo)函數(shù)最優(yōu)值的下界和上界。解：（1）上界對(duì)應(yīng)的模型如下（c, b取大，a取?。﹎ax z = 3 x16 x2-1x1 + 2x2 0,可是pj 0 為某一常數(shù)，分別討論下列情況時(shí)最優(yōu)解的變化。(1)目標(biāo)函數(shù)變?yōu)閙axz=、cx；(2)目標(biāo)函數(shù)變?yōu)閙axz=(c +兒)x；c目標(biāo)函數(shù)變?yōu)閙axz = x,約束條件變?yōu)閍x=ub 。九解：最優(yōu)解不變；c為常數(shù)時(shí)最優(yōu)解不變，否則可能發(fā)生變化

18、；最優(yōu)解變?yōu)椋簒/入。1.13 某飼養(yǎng)場飼養(yǎng)動(dòng)物出售，設(shè)每頭動(dòng)物每天至少需要700g蛋白質(zhì)、30g礦物 質(zhì)、100mg維生素?，F(xiàn)有五種飼料可供選用，各種飼料每 kg營養(yǎng)成分含量及單 價(jià)如表1-22所示。表 1-22飼料蛋白質(zhì)/g礦物質(zhì)/g維生素/mg價(jià)格/(元/kg)1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8要求確定既滿足動(dòng)物生長的營養(yǎng)需要，又使費(fèi)用最省的選用飼料的方案。解：設(shè)xi表示第i種飼料數(shù)量，i= 1,2,3, 4,5min z = 0.2 x10.7 x20.4 x30.3x4 0.8x53xi2x2x36x4 18x5 .

19、700x1 + 0.5 x2 + 0.2 x3 + 2x4 + 0.5 x5 之 30 s.t.0.5 x1 + x2 + 0.2 x3 + 2x4 + 0.8 x5 之 100為 a0, i =1,2,3, 4,5最優(yōu)解為 xi = x2 = x3 = 0, x4 = 39.74, x = 25.64, z = 32.44（元）1.14 遼源街郵局從周一到周日每天所需的職員人數(shù)如下表1-23所示。職員分別安排在周內(nèi)某一天開始上班，并連續(xù)工作5天,休息2天。表1-23人周一 二三四五六日所需人數(shù)17131519141611要求確定：該郵局至少應(yīng)配備多少職員，才能滿足值班需要； 因從周一開始上班

20、的，雙休日都能休息；周二或周日開始上班的，雙休日 內(nèi)只能有一天得到休息；其他時(shí)間開始上班的，兩個(gè)雙休日都得不到休息，很 不合理。因此郵局準(zhǔn)備對(duì)每周上班的起始日進(jìn)行輪換 （但從起始日開始連續(xù)上5 大班的規(guī)定不變），問如何安排輪換，才能做到在一個(gè)星期內(nèi)每名職工享受到同 等的雙休日的休假天數(shù)； 該郵局職員中有一名領(lǐng)班，一名副領(lǐng)班。為便于領(lǐng)導(dǎo)，規(guī)定領(lǐng)班于每周一、 三、四、五、六上班，副領(lǐng)班于一、二、三、五、日這 5天上班。據(jù)此試重新 對(duì)上述要求和建模和求解。解：(1)設(shè)x(i =1,2,111,7)表示星期一至星期天開始上班的人數(shù)，則建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù):min z = x1 x2 x3 x4

21、 x5 x6 x7_13_15x1x4x5x6x7x2x5x6x7x1約束條件:s.t.x3x6x7xx2x4x7x1x2x3_19-14x5x1x2x3x4_ 16x6x2x3x4x5-11x7x3x4x5x6-17x1,x2,x3,x4,x5,x6,x7 - 0解得最優(yōu)解為 x* =(7,4,2,8,0,2,0),z* =23則該郵局至少應(yīng)配備23名職員，才能滿足值班需要。對(duì)這23名職工分別編號(hào)，23,以23周為一個(gè)周期，這23名 職工上班安排見下表。每周上班 時(shí)間起止周職工職工職工？職工？職工周一周五17281622172323,16周二周六81191223,1314710周三周日121

22、3131445561112周四下周一142115226137141320周五下周二222323,1141515162122此時(shí)只需在每天人數(shù)中減去領(lǐng)班和副領(lǐng)班兩人即可，重現(xiàn)建模如下:min z=x1 x2 x3 x4 x5 x6 x71 +x4 +x5 +x6 +x7 15x1 +x2 +x5 +x6 +x7 12x1 +x2 +x3 +x6 +x7 13x1 +x2 +x3 +x4 +x7 18 s.t.x1 +x2 +x3 +x4 +x5 12x2 + x3 + x4 + x5 + x6 之 16x3 + x4 + x5 + x6 + x7 10x1，x2,x3, x4,x5, %,x7

23、至 01.15 一艘貨輪分前、中、后三個(gè)艙位，它們的容積與最大允許載重量如表1-24所示?，F(xiàn)有三種貨物待運(yùn)，已知有關(guān)數(shù)據(jù)列于表 1-25。又為了艙運(yùn)安全，前、中、后艙的實(shí)際載重量大體積保持各艙最大允許載 重量的比例關(guān)系。具體要求：前、后艙分別與中艙之間載重量比例的偏差不超 過15%前、后艙之間不超過10%問該貨輪應(yīng)裝載a、b、c各多少件運(yùn)費(fèi)收入 為最大？試建立這個(gè)問題的線性規(guī)劃模型。表 1-24項(xiàng)目前艙中艙后艙最大允許載重量/t200030001500容積/m3400054001500表 1-25商品數(shù)量/件每件體積/（m3/件）每件重量/（tp|牛）運(yùn)價(jià)/（元/件）a6001081000b1

24、00056700c80075600解：用i=1,2,3表示a、b、c三種貨物，j=1,2,3表示前、中、后三個(gè)艙，用x(i , j)表示貨物i在艙j的裝載量。max z = 1000( x(1,1) x(1,2)+ x(1,3)+700( x(2,1)+ x(2,2)+ x(2,3)+600( x(3,1)+ x(3,2)+ x(3,3)商品數(shù)量約束：1) x(1,1) x(1,2)x(1,3) 6002) x(2,1)x(2, 2)x(2,3) 10003) x(3,1)x(3, 2)x(3,3) 800商品容積約束：4)10x(1,1) 5x(2,1)7x(3,1) 40005)10 x(

25、1,2) 5x(2, 2)7x(3, 2) 54006)10x(1,3)5x(2,3)7x(3,3)與 1500最大載重量約束：7)8x(1,1) 6x(2,1)5x(3,1) 2000 8)8x(1,2) 6x(2, 2) 5x(3, 2) 30009)8 x(1,3)6x(2,3)5x(3,3) 1500重量比例偏差約束：i0)8x(i,i)6x(2,i)5x(3,i)a(1 0.15)(8 x(i,2)6x(2,i)5x(3,2)211)8 x(1,1) 6x(2,1)5x(3,1) - 2(1 - 0.15)(8 x(1,2) 6x(2,1)5x(3, 2)312)8 x(1,3)6x

26、(2,3)13)8 x(1,3)6x(2,3)14)8 x(1,3)6x(2,3)15)8 x(1,3)6x(2,3)15x(3,3)(1 0.15)(8 x(1,2) 6x(2,1)5x(3,2)215x(3,3) - -(1 - 0.15)(8 x(1,2) 6x(2,1)5x(3, 2)5x(3,3) m 3(1 0.1)(8 x(1,1) 6x(2,1)5x(3,1)435x(3,3) - -(1 - 0.1)(8 x(1,1) 6x(2,1)5x(3,1)41.16 長城通信公司擬對(duì)新推出的一款手機(jī)收費(fèi)套餐服務(wù)進(jìn)行調(diào)查，以便進(jìn)一步設(shè)計(jì)改進(jìn)。調(diào)查對(duì)象設(shè)定為商界人士及大學(xué)生，要求：總共調(diào)

27、查600人，其中大學(xué)生不少于250人；方式分電話調(diào)查和問卷調(diào)查，其中問卷調(diào)查人數(shù)不 少于30%對(duì)大學(xué)生電話調(diào)查80%z上應(yīng)安排在周六或周日，對(duì)商界人士電話 調(diào)查80犯上應(yīng)安排在周一至周五；問卷調(diào)查時(shí)間不限。已知有關(guān)調(diào)查費(fèi)用如 表1-26所示，問該公司應(yīng)如何安排調(diào)查，使總的費(fèi)用為最省。表1-26元/人次調(diào)查對(duì)象電話調(diào)查問卷調(diào)查周一至周五周六、日大學(xué)生3.02.55.0商界人士3.53.05.0解：設(shè)xii,x2l為周一至周五對(duì)大學(xué)生和商界人士電話調(diào)查人數(shù)x12,x22為雙休日對(duì)上述 人員電話調(diào)查人數(shù)，xi3,x2分別為問卷調(diào)查人數(shù)，則數(shù)學(xué)模型為minz = 3.0x1 2.5x12 5.依3 3

28、.5x21 3.0x22 5.0x23為1為2 為3 x21 x22 ”23 = 600。x12 x13 -250x13 + x23 之 180 s.t.x -0.8x11 . 2x21、x21 +xl2-0.8i=r * r、*-r-r 一一一一一,一 一 * 取優(yōu)解xi1 =0,x12 =350x13 =0,x21 =58涇2 =11,x23 =180z =20141.17 生產(chǎn)存儲(chǔ)問題。某廠簽訂了 5種產(chǎn)品（i=1 ,，5）上半年的交貨合同。已知各產(chǎn)品在第j月（j=1，6）的合同交貨量dj ,該月售價(jià)sj 、成本價(jià) co及生產(chǎn)1件時(shí)所需工時(shí)aj。該廠第j月的正常生產(chǎn)工時(shí)為3,但必要時(shí)可加

29、班生產(chǎn)，第j月允許的最多加 班工時(shí)不超過3并且加班時(shí)間內(nèi)生產(chǎn)出來的產(chǎn)品每件成本增加額外費(fèi)用 c1 元。若生產(chǎn)出來的產(chǎn)品當(dāng)月不交貨，每件庫存 1個(gè)月交存儲(chǔ)費(fèi)p元。試為該廠 設(shè)計(jì)一個(gè)保證完成合同交貨，又使上半年預(yù)期盈利總額為最大的生產(chǎn)計(jì)劃安排。解：設(shè)xj為i種產(chǎn)品j月正常時(shí)間生產(chǎn)數(shù)，xj為加班時(shí)間生產(chǎn)數(shù)，模型為5656 jmaxz = (5-q )xj +(sj -cj - cj )xj - pi | 2 + dik) i，j，cz1 il j -1 k =1-5z ajxj wtj(j =1,ih,6)cg 5z a/j wtj(j=1川,6)s.t.( y工(xk+xik)” dik(j=1川

30、,6)kk w/j 01.18 宏銀公司承諾為某建設(shè)項(xiàng)目從 2003年起的4年中每年年初分別提供以下 數(shù)額貸款：2003年一100萬元，2004年一150萬元，2005年一120萬元，2006 年110萬元。以上貸款資金均需于 2002年年底前籌集齊。但為了充分發(fā)揮這 筆資金的作用，在滿足每年貸款額情況下，可將多余資金分別用于下列投資項(xiàng) i 于2003年年初購買a種債券，期限3年，到期后本息合計(jì)為投資額的140% 但限購60萬元； 于2003年年初購買b種債券，期限2年，到期后本息合計(jì)為投資額的125% 且限購90萬元； 于2004年年初購買c種債券，期限2年，到期后本息合計(jì)為投資額的130%

31、 但限購50萬元；于每年年初將任意數(shù)額的資金存放于銀行，年息 4%于每年年底取出。求宏銀公司應(yīng)如何運(yùn)用好這筆籌集到的資金，使2002年年底需籌集到的資金數(shù)額為最少。解：用xj(i為第1,2,3年年初，j =1,2,3, 4分別為a, b,c, d四類投資數(shù))min z =480 (刈 不？ 加 xd) (x21% x23 x24) (x31 x32 *33 *34)x11 +(1+140%)之 110x11 120x12 110x23 w50(x11 +x12 +x13 +x14)(1 +4%) 100(x21 +x22 +x23 +x24)(1 +4%) 150(x31 x32 x33 x3

32、4 )(1 4%) -1201.19 紅豆服裝廠新推出一款時(shí)裝，據(jù)經(jīng)驗(yàn)和市場調(diào)查，預(yù)測(cè)今后 6個(gè)月對(duì)該款時(shí)裝的需求 為：1 月一 3000 件,2 月一 3600 件，3 月一4000 件，4 月一4600 件,5 月一 4800 件，6 月一5000件。生產(chǎn)每件需熟練工人工作 4h,耗用原材料150元，售價(jià)為240元/件。該廠1月初 有熟練工80人，每人每月工作160h。為適應(yīng)生產(chǎn)需要，該廠可招收新工人培訓(xùn)，但培訓(xùn)一名新工人需占用熟練工人 50h用于指導(dǎo)操作，培訓(xùn)期為一個(gè)月，結(jié)束后即可上崗。 熟練工人每月工資2000元，新工人培訓(xùn)期間給予生活補(bǔ)貼800元，轉(zhuǎn)正后工資與生產(chǎn)效率同熟練工人。又熟

33、練工人（含轉(zhuǎn)正一個(gè)月后的新工人）每月初有2%因各種原因離職。已知該廠年初已加工出400件該款時(shí)裝作為庫存，要求 6月末存庫1000件。又每月生產(chǎn)出來時(shí)裝如不在 當(dāng)月交貨，庫存費(fèi)用為每件每月10元。試為該廠設(shè)計(jì)一個(gè)滿足各月及6月末庫存要求，又使16月總收入為最大的勞動(dòng)力安排方案。解：設(shè)該廠每月初擁有熟練工人數(shù)（t = 1川,6），每月招收培訓(xùn)的新工人數(shù)卻, 該廠月末庫存為it, 一月初庫存為i。，r為各月對(duì)時(shí)裝的需求數(shù)，則數(shù)學(xué)模型為6maxz= （每月銷售收入-熟練工人工資-培訓(xùn)工人補(bǔ)助-原材料費(fèi)-庫存費(fèi)）i 1it40xt-12.5yt -rit =it+40xt +40yt,+12.5yt-

34、r s.t.xt 1 =0.98xt ytxt,yt -0解得z*=87512元，各月有關(guān)數(shù)字如下：t123456xt8082.47106.62130.93128.32125.75yt4.0725.8026.45000it559.3400637.38970.021000第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析2.1寫出下列線性規(guī)劃問題的對(duì)偶問題，并以對(duì)偶問題為原問題，再寫出對(duì)偶的對(duì)偶問題。 min z = 2x1 2 x2 4 x3x1 +3x2 +4x3 2 i332 x1 +x2 +3x3 0, x3無約束解：對(duì)偶問題：max w = 2 y1 3 y2 5 y3y1 +2y2 + y3 m

35、23y1 + y2 + 4 y3 0, y2 m 0, y3無約束對(duì)偶的對(duì)偶問題：min v = 2m1 2m2 - 4m3123m1 + 3m2 + 4m3 21232m1 + m2 + 3m3 3s.t.| m14m2 3m3 = 5i m1, m2 - 0, m3無約束 3(2) max z = 5x1 6x2 3x3x1 + 2x2 + 2x3 = 5-x1 + 5x2 _ x3 之 3s.t.4x1 + 7x2 + 3x3 w 8、x1無約束，x2之0, x3 m 0解：對(duì)偶問題：min w = 5y1 3y2 8y3y1 - y2 + 4y3 =52y1 + 5y2+7丫3 至 6

36、 s.t.2y1 +3y3 m3、y1 無約束，y2 - 0, y3 - 0對(duì)偶的對(duì)偶問題：max v 5m1 6m2 3m3m1 + 2m2 + 2m3 = 0-m1 + 5m2 - 3m3 之 0s.t.4 m1 + 7m2 + 3m3 0m無約束，m2之0, m3 m 0m n(3) min z= cij xiji，j，n xj = q (i = 1川，m)j=ims.txj = bj(j =1,|,n)1 =1xj - 0 (i = 1川,m, j = 1,|,n)imn解：對(duì)偶問題：maxw= 、 aiyiv bjyj mi =1jyiyj m - cj (i = 1,川，m, j

37、= 1,m,n)s.t. j j(yi無限制，i = 1川,n+ mm n對(duì)偶的對(duì)偶問題： min v= c cij xijiw j dn xj = a (i = 1川，m)j=1ms.t?為=bj(j = 1jii ,n)i i txj - 0 (i = 1,|,m, j = 1川,n)n(4) max z -cjxjn na aij xj bi jns.t.2 a。 = bjgj =1(i = 1,|“，mi ； m)(i = mi 1,m1 2,|h，m)xj 2 0( j =1,lll, ni n)xj 無約束(j = ni +1,|,n)解：對(duì)偶問題： min w = b1y1b2y

38、2 th bmymm、aij yi - cj ( j = 1,2,ih,n1) i 1ms.t. 、 aij yi = cj (j = n1 1,n1 2,m,n) i 二yi 之 0( i = 1,1小)j無約束 (j = m1 +1,(|, m)n對(duì)偶的對(duì)偶問題： max z - cj xj j=1，n工 aij xjbi (i =1,111, m1 m)j vns.t.ajxj = bi(i = m +1,m+ 2,|,m)jxj 至 0( j =1,ih,n1 n)、xj無約束 (j = n1 + 1,111, n)2.2判斷下列說法是否正確，并說明為什么。如果線性規(guī)劃的原問題存在可行

39、解，則其對(duì)偶問題也一定存在可行解；答：錯(cuò)誤。如果原問題是無界解，則對(duì)偶問題無可行解。如果線性規(guī)劃的對(duì)偶問題無可行解，則原問題也一定無可行解；答：錯(cuò)誤。如果對(duì)偶問題無可行解，也可能是因?yàn)樵瓎栴}是無界解。在互為對(duì)偶的一對(duì)原問題與對(duì)偶問題中，不管原問題是求極大或極小，原問 題可行解的目標(biāo)函數(shù)值一定不超過其對(duì)偶問題可行解的目標(biāo)函數(shù)值； 答：錯(cuò)誤。如果原問題是求極小，則結(jié)論相反。任何線性規(guī)劃問題具有唯一的對(duì)偶問題。答：正確。2.5已知某求極大線性規(guī)劃問題用單純形法求解時(shí)的初始單純形表及最終單純形表如表2-30所小，求表中各括號(hào)內(nèi)未知數(shù)(a)(l)的值cj 322000cb基 bxix2x3x4x5x60x4(b)1111000x5 15(a)120100x6 202(c)1001cj-zj3220000x45/400(d)(l)-1/4-1/43 xi 25/410(e)03/4(i)2x25/201(f)0(h)1/2cj-zj0(k)(g)0-5/4(j)解：l=1 , k=0, a=2, c=3, h=-1/2 , b=10, e=5/4 , f=-1/2 , d=1/4 ,g=-3/4 , i=-1/4 ,j=-1/4.2.6給出線性規(guī)劃問題minz = 2% + 3x2 + 5x3 + 6x4x1 + 2x2 +