運(yùn)籌學(xué)課后試題

1、運(yùn)籌學(xué)課后試題答案運(yùn)籌學(xué)課后試題答案PAGE168運(yùn)籌學(xué)課后試題答案精選文檔第一章線性規(guī)劃1、由圖可得：最優(yōu)解為2、用圖解法求解線性規(guī)劃：Minz=2x1+x2x14x224x1x285x110 x20解：由圖可得：最優(yōu)解.精選文檔用圖解法求解線性規(guī)劃：Maxz=5x1+6x22x1x222x13x22x1,x20解：由圖可得：最優(yōu)解Maxz=5x1+6x2,Maxz=+.精選文檔用圖解法求解線性規(guī)劃：Maxz=2x1+x25x1156x12x2224x1x25x1,x20 x1x25，x13由圖可得：最大值所以x13x22maxZ=8.精選文檔Z2x13x2x12x284x1164x212x

2、j0,j1,2以下列圖，maxZ在（4，2）這一點(diǎn)達(dá)到最大值為2.將線性規(guī)劃模型化成標(biāo)準(zhǔn)形式：Minz=x1-2x2+3x3x1x2x37x1x2x323x1x22x35x10,x20,x3無拘束解：令Z=-Z,引進(jìn)廢弛變量x40，引入節(jié)余變量x50，并令x3=x3-x3,此中x30,x30Maxz=-x1+2x2-3x3+3x3x1x2x3x3x47x1x2x3x3x523x1x22x35x10,x20,x30,x30,x40,x50.精選文檔將線性規(guī)劃模型化為標(biāo)準(zhǔn)形式MinZ=x1+2x2+3x3-2x1x2x393x1x22x344x12x23x36x10，x20,x3無拘束解：令Z=-

3、z，引進(jìn)廢弛變量x40,引進(jìn)節(jié)余變量x50,獲取一低等價(jià)的標(biāo)準(zhǔn)形式。-2x1x2x3x493x1x22x3x544x12x23x36x10,x2,x4,x50,x2=-x2x3=x3-x3Z=-minZ=-x-2x2-3x31-2x1x2x3x3x493x1x22x3x3x544x12x23x3x368.maxZ=3x13x24x33x14x25x3x4406x14x23x3x566xj0,j1,2,3,4,5Cj33400iCBXBbx1x2x3x4x50X4403451080X5606430120j334004x383/54/511/5040/30 x54221/58/50-3/5160/

4、7j3/5-1/50-4/504x3204/714/35-1/73x11018/2101/75/21j0-3/70-31/35-1/7最優(yōu)解為（10,0，2,0,0），目標(biāo)函數(shù)maxZ=38.精選文檔用純真形法求解線性規(guī)劃問題：MaxZ=70 x1+120 x29x14x23604x16x22003x110 x2300解：MaxZ=70 x1+120 x29x14x2x33604x16x2x42003x110 x2x5300純真形表以下MaxZ=3908.精選文檔Z4x13x22x1+2x230005x1x24000 x1500 x1,x20解：引入廢弛變量x3,x4,x5(x3,x4,x50

5、)2x12x2x330005x1x2+x44000 x1x5500 xj0,j1,2,3,4,5Cj43000iCBXBbx1x2x3x4x50X330002210015000X4400050108000X550010001500Cj-Zj430001c1z14(020501)42c2z23(02+02.5+00)3Q查驗(yàn)數(shù)0,max(1,2)max(4,3)4,對(duì)應(yīng)的x1為換入變量.Qmin3000,4000,500500,x5為換出變量.251minCj43000iCBXBbx1x2x3x4x50X320000210-20X41500001-50X150010001Cj-Zj0000-4Q

6、非基變量查驗(yàn)數(shù)0，獲取最優(yōu)解：x1500,x20,x32000,x41500,x50,目標(biāo)函數(shù)的maxZ=41c1z14(020501)4500302000.精選文檔解：（1）引入廢弛變量X4，X5，X6，將原問題標(biāo)準(zhǔn)化，得maxZ=10X1+6X2+4X3X1+X2+X3+X4=10010X1+4X2+5X3+X5=6002X1+2X2+6X3+X6=300X1,X2,X3,X4,X5,X60獲取初始純真形表：Cj1064000CXbXXXXXXBB1234560X41001111001000X56001045010600X6300226001150Cj-Zj10640002）此中1=C1-

7、Z1=10-（01+010+02）=10，同理求得其余依據(jù)max=max10,6,4=10,對(duì)應(yīng)的X1為換入變量，計(jì)算獲取，min=min100/1,600/10,300/2=60,X5為換出變量，進(jìn)行旋轉(zhuǎn)運(yùn)算。（3）重復(fù)（2）過程獲取以下迭代過程Cj1064000CXbXXXXXXBB1234560X44003/51/21-1/100200/310X6012/51/201/10015010X18006/5501/511506Cj-Zj02-10-106X200/3015/65/3-1/60200/3210X100/3101/6-2/31/6015010X6100004-201150C-Zj0

8、0-8/3-10/3-2/30jj0，迭代已獲取最優(yōu)解，X*=（100/3，200/3，0，0，0，100）T，Z*=10100/3+6200/3+40=2200/3。.精選文檔12解：（1）引入廢弛變量X3，X4，X5將原問題標(biāo)準(zhǔn)化，得maxZ=2X1+X25X2+X3=156X1+2X2+X4=24X1+2X2+X5=5X1,X2,X3,X4,X50獲取初始純真形表：Cj21000CXbXXXXXBB123450X31505100-0X4246201040X55110015Cj-Zj210002）此中1=C1-Z1=2-（01+010+02）=2，同理求得其余依據(jù)max=max2,1,0=

9、2,對(duì)應(yīng)的X1為換入變量，計(jì)算獲取，min=min-,24/6,5/1=4,X4為換出變量，進(jìn)行旋轉(zhuǎn)運(yùn)算。（3）重復(fù)（2）過程獲取以下迭代過程Cj106400CXbXXXXXBB123450X3150510032X411/301/601210X102/30-1/613/25Cj-Zj01/30-1/300X15/20015/4-15/232X17/21001/4-1/211X23/2010-1/43/2C-Zj000-1/4-1/2jj0，迭代已獲取最優(yōu)解，X*=（7/2，3/2，0，0，0）T，Z*=27/2+3/2=17/2。.精選文檔13解：引入廢弛變量X3、X4，拘束條件化成等式，將原

10、問題進(jìn)行標(biāo)準(zhǔn)化，得：Max1+X23X123=15+5X+X5X+2X+X=10124X1,X2,X3,X401）確立初始可行基為單位矩陣I=P3，P4，基變量為X3，X4，X5，非基變量為X1，X2，則有：Max1+3X2X3=15-3X1-5X2X=10-5X-2X241Xi0，j=1，2，3，4Cj100CBXBbx1x2x3x40 x315351050 x41052012cjzj100將題求解過程列成純真形表格形式，表1由上述可得，將x1替代為x4表2，純真形迭代過程Cj100CBXBbx1x2x3x40 x39019/51-3/545/19x1212/501/55.精選文檔cjzj0

11、00由表2可得，將x2替代為x3Cj100CBXBbx1x2x3x41x245015-3191919x120102519-1919cjzj0001-2表3最后純真形表=0,41x*=（20，45=5，非基變量查驗(yàn)數(shù)3=-，獲取該線性規(guī)劃另一最優(yōu)解，0,0）,z*21919該線性規(guī)劃擁有無量多個(gè)解用純真形法求解線性規(guī)劃問題：maxz2x1x25x2156x12x224s.t.x25x11，20 x0 x解：（1）將原問題轉(zhuǎn)變成標(biāo)準(zhǔn)形式，得.精選文檔maxz2x1x20 x30 x40 x55x2x3156x12x2x424s.t.x2x55x1x10,x20,x30,x40,x50（2）建立純真

12、性，并進(jìn)行迭代運(yùn)算Cj21000CXbXXXXX8B123450X150510030X4246101040X51100155C-Zj21000j0X3150510032X1411/601/60240X105/60-1/616/55Cj-Zj02/30-1/300X90011-632X19/51001/5-1/511X26/5010-1/56/5C-Zj000-1/5-4/5j196T44（3）獲取最優(yōu)解X*=(5,5,9,0,0)，Z*=5用純真形法求解線性規(guī)劃問題：.精選文檔maxzx1x2x-22122x1x22s.t.x24x1x10，x20解：（1）將原問題轉(zhuǎn)變成標(biāo)準(zhǔn)形式，得maxzx

13、1x20 x30 x40 x5x12x2x322xx2x124s.t.x2x54x1x10,x20,x30,x40,x50（2）建立純真性，并進(jìn)行迭代運(yùn)算Cj21000CXbXXXXX8B123450X3211210020X42-21010-0X4-11001-5Cj-Zj110001X121-21000X460-32100X560-1101Cj-Zj03-100本例第二個(gè)純真形表中，非基變量X2對(duì)應(yīng)的查驗(yàn)數(shù)0，而且對(duì)應(yīng)的變量系數(shù)ai，2（0i=1，2，3），依據(jù)無界解判斷定理，該線性規(guī)劃問題有無界解（或無最優(yōu)解）。假如從方程角度看，第二個(gè)表格復(fù)原線性方程.精選文檔maxz3x1-x22x1-

14、2x2x32.32x6stx2x34x2x3x56也即：x122x2-x3.x43x2-2x36x5x2-x36令x3=0，則x122x2.x43x26x5x26此時(shí)，若x2進(jìn)基，則x1，x4，x5會(huì)和基變量x2同時(shí)增添，同時(shí)目標(biāo)函數(shù)值無窮增長(zhǎng)，所以本題無解。16解：（1）引入廢弛變量X3，X4，X5將原問題標(biāo)準(zhǔn)化，得maxZ=2X1+4X2+0X3+0X4+0X5X1+2X2+X3=8X1+X4=4X2+X5=3X1,X2,X3,X4,X50（1）獲取初始純真形表：Cj24000CBXBbX1X2X3X4X50X812100430X4410010-0X53010013C-Zj24000j（2

15、）重復(fù)（1）過程獲取以下迭代過程.精選文檔C106400jCBXBbX1X2X3X4X50X210100230X441001044X2301001-C-Zj2000-4j2X12101000X4200-1104X3010012Cj-Zj00-2005=0，3=0增添人工變量x6,x7,獲?。篗axZ=-5X1-2X2-4X3-MX6-MX73X1+X2+2X3-X4+X6=46X1+3X2+5X3-X5+X7=10X1,x2,x3,x4,x5=0大M法求解過程以下：cj-5-2-400-M-MiCBXBbX1X2X3X4X5X6X7-MX64312-10104/3-MX7106350-1015

16、/3cj-zj-5+9M-2+4M-4+7M-M-M00-5X14/311/32/3-1/301/30-MX720112-1-211cj-zj0-1/3+M-2/3+M-5/3+2M-M5/3-3M0-5X15/311/25/60-1/601/610/3.精選文檔0X4101/21/21-1/2-11/22cj-zj01/21/60-5/6-M5/6-M-5X12/3101/3-11/31-1/3-2X220112-1-21cj-zj00-1/3-1-1/31-M1/3-M最優(yōu)解為X1*=2/3,X2*=2,X3*=0最優(yōu)目標(biāo)函數(shù)值minZ=22/319、解：化為標(biāo)準(zhǔn)形式：maxZ=-540

17、x1-450 x2-720 x33x1+5x2+9x3-x4=709x1+5x2+3x3-x5=30X1,x2,x3,x4,x5=0增添人工變量x6,x7,獲?。簃axZ=-540 x1-450 x2-720 x3-Mx6-Mx73x1+5x2+9x3-x4+x6=709x1+5x2+3x3-x5+x7=30X1,x2,x3,x4,x5=0大M法求解過程以下：cj-540-450-72000-M-MiCBXBbX1X2X3X4X5X6X7-MX670359-101070/3-MX730(9)530-10130/9cj-zj12M-54010M-45012M-72-M-M000-MX660010

18、/3(8)-11/31-1/3-540X110/315/91/30-1/901/910cj-zj0-150+10M/38M-540MM/3-600-M/3+60.精選文檔-720X315/205/121-1/81/241/8-1/2418-540X15/61(5/12)01/24-1/8-1/241/82cj-zj01250135/-475/12135/2-M75/2-M2-720X320/3-1011/61/61/6-1/6-450X2212/5101/10-3/10-1/103/10-360-450-7207515-75-155700-18000-75-1575-M15-M最優(yōu)解為X*=(

19、0,2,20/3,0,0)最優(yōu)目標(biāo)函數(shù)值minZ=5700解：先將其化成標(biāo)準(zhǔn)形式，有maxz=-3x1+x3+0 x4+0 x5x1+x2+x3+x4=4（a）-2x1+x2-x3-x5=1（b）3x2+x3=9（c）x1，x2，x3，x4，x50這類狀況可以增添兩列單位向量P6，P7，連同拘束條件中的向量P4組成單位矩陣P4P6P7100010001P，P是人為增添上去的，它相當(dāng)于在上述問題的拘束條件（b）中增添變量x6，拘束條件（c）67中增添變量x7，這兩個(gè)變量相應(yīng)稱為人工變量。因?yàn)榫惺鴹l件（b）（c）在增添人工變量前已是等式，為使這些等式獲取知足，所以在最優(yōu)解中人工變量取值一定為零。為

20、此，令目標(biāo)函數(shù)中人工變量的系數(shù)為隨意大的負(fù)數(shù)，用“-M”代表。增添人工變量后數(shù)學(xué)模型變成maxz=-3x1+x3+0 x4+0 x5-Mx6-Mx7x1+x2+x3+x4=4.精選文檔-2x1+x2-x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x70獲取初始可行解X0(0,0,0,4,0,1,9)，并列出初始純真形表。在純真形法迭代運(yùn)算中，M可看作一個(gè)數(shù)學(xué)符號(hào)一同參加運(yùn)算。查驗(yàn)數(shù)中含M符號(hào)的，當(dāng)M的系數(shù)為正時(shí)，該查驗(yàn)數(shù)為正；當(dāng)M的系數(shù)為負(fù)時(shí)，該查驗(yàn)數(shù)為負(fù)。求解過程見下表cj-30100-M-MC基bXX2X3X4X5X6X7B10 x441111000-Mx6

21、1-21-10-110-Mx790310001cj-zj-2M-34M10-M000 x4330211-100 x21-21-10-110-Mx7660403-31cj-zj6M-304M+103M-4M00 x400001-1/2-1/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/20 x400001-1/21/2-1/20 x2100-1/41/41/45/2-1/21x33/23/20103/4-3/41/4cj-zj-9/2000-3/4-M+3/4-M-1/4最優(yōu)解為（0，5/2，3/2）.精選文檔2

22、1、解：將原問題轉(zhuǎn)變成標(biāo)準(zhǔn)型Maxz=3x1+2x22x1+x2+x3=2s.t.3x1+4x2-x4=12Xi0，i=1,2,3,4此后增添人工變量x5，將原線性規(guī)劃問題變成Maxz=3x1+2x2-Mx52x1+x2+x3=2s.t.3x1+4x2-x4+x5=12Xi0，i=1,2,3,4,5取基變量為x3,x5,建立純真形表，迭代過程以下：Cj3200-MCbXbBX1X2X3X4X5i0X32211002-MX512340-113Cj-zj3+3M2+4M0-M0Cj3200-MCbXbBX1X2X3X4X5i0X2221100-MX54-50-4-11Cj-zj3-5M0-4M-M

23、0在純真形表中，非基變量的查驗(yàn)值都是小于0，而人工變量仍不為0，則該線性規(guī)劃無最優(yōu)解。22、解：假定甲、乙倆種產(chǎn)品產(chǎn)量分別為x1、x2，產(chǎn)品售后的最大收益為z，則依據(jù)題意可建立以.精選文檔下線性規(guī)劃模型：Max=70 x1+120 x29x1+4x2360s.t.4x1+6x22003x1+10 x2300Xi0，i=1,223.解：設(shè)甲、乙產(chǎn)品的生產(chǎn)數(shù)目應(yīng)為x1、x2，則x1、x20,設(shè)是產(chǎn)品售后的總收益，則zmaxz70 x1120 x2s.t9x14x23604x16x22003x110 x2300 x1,x2024.解：設(shè)甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)目為x1,x2，設(shè)z為產(chǎn)品售后總收益，則m

24、axz=4x13x2s.t.2x12x230005x124000 x1500 x1,x20設(shè)1、x2、x3分別為產(chǎn)品、B、C的產(chǎn)量，則數(shù)學(xué)模型為25.xAmaxZ10 x114x212x3x1x24x325003x1x2x31400150 x1250 x2310120 x3130 x1,x2,x30.精選文檔26.設(shè)x1,x2分別為產(chǎn)品A、B的產(chǎn)量，x3為副產(chǎn)品C的銷售量，x4為副產(chǎn)品C的銷毀量，有x3+x42x2,Z為總收益，則數(shù)學(xué)模型為maxZ3x17x22x3-x4x12x2112x13x2172x2x3x40 x313xj0,j1,2,3,4設(shè)生產(chǎn)四種產(chǎn)品分別為X1,X2,X3X4,則

25、應(yīng)知足的目標(biāo)函數(shù)為max=2X1+3X2+X3+X4知足的拘束條件為1+3X2+X3418002X1+X2+X3+X4280012+X+X1800343X+X+2X+3X18001234X11000X2600X3500X4400設(shè)X1=A銷售的數(shù)目，X2=A在第二車間加工后的銷售數(shù)目，X3=B的銷售數(shù)目，X4=B在第三車間加工后的銷售數(shù)目，X5=第一車間所用的原料數(shù)目目標(biāo)函數(shù)為maxZ=8X12+7X3+8X45知足的拘束條件為X51000003X2+2X45200000X1+X23X5=0X3+X42X5=0X1,X2,X3,X40.精選文檔29,解:現(xiàn)在我們對(duì)本問題定義三種不同樣形式的決議

26、變量，進(jìn)而從不同樣的門路來建立模型.（1）設(shè)工廠第j季度生產(chǎn)產(chǎn)品xj噸第一，考慮拘束條件：第一季度末工廠需交貨20噸，故應(yīng)有x1=20；第一季度末交貨后積余（x1-20）噸；第二季度末工廠需交貨20噸，故應(yīng)有x1-20+x2=20；近似地，應(yīng)有x1x240 x330；第四時(shí)度末供貨后工廠不可以積壓產(chǎn)品，故應(yīng)有x1x2x370 x410；又考慮到工廠每個(gè)季度的生產(chǎn)能力，故應(yīng)有0 xjaj.其次，考慮目標(biāo)函數(shù)：第一季度工廠的生產(chǎn)花費(fèi)為x1，第二季度工廠生產(chǎn)的花費(fèi)包括生產(chǎn)花費(fèi)14x2及積壓產(chǎn)品的存貯費(fèi)0.2(x120)；近似地，第三季度花費(fèi)為30.2(x1x240)，第四時(shí)度花費(fèi)為40.2(x1x2

27、x370).工廠一年的費(fèi)用即為這四個(gè)季度花費(fèi)之和.整理后，得以下線性規(guī)劃模型：minz123426s.t.x1x240 x1x2x370 x1x2x3x48020 x130，0 x240，0 x320，0 x410.（2）設(shè)第j季度工廠生產(chǎn)的產(chǎn)品為xj噸，第j季度初存貯的產(chǎn)品為yj噸（顯然，y10）.因?yàn)槊考径瘸醯拇尜A量為上季度存貯量、生產(chǎn)量之和與上季度的需求量之差，又考慮到第四時(shí)度末存貯量為零，故有：x120y2，y2x220y3，y3x330y4，y4x410；同時(shí)，每季度的生產(chǎn)量不可以超出生產(chǎn)能力：xjaj；而工廠四個(gè)季度的總花費(fèi)由每季的生產(chǎn)花費(fèi)與存貯花費(fèi)組成，于是得線性規(guī)劃：minz1

28、y214x233y44s.t.x1y220y2x2y320y3x3y430y4x4100 x1300 x2400 x3200 x410yj0，j，3，4.2.精選文檔（3）第i季度生而用于第j季度末交的品數(shù)目xij噸.依據(jù)合同要求，必有：x1120，x12x2220，x13x23x3330，x14x24x34x4410.又每季度生而用于當(dāng)季和此后各季交的品數(shù)不行能超季工廠的生能力，故有：x11x12x13x1430，x22x23x2440，x33x3420，x4410.第i季度生的用于第j季度交的每噸品的用cijdi0.2(ji)，于是，有性劃模型：minz=1112131414x222324

29、333444s.t.x1120 x12x2220 x13x23x3330 x14x24x34x4410 x11x12x13x1430 x22x23x2440 x33x3420 x4410 xij0i1，4；j1，4，ji.30,解xiji#型機(jī)被派遺去j#工廠行任的架數(shù).甲方的目是希望事件“最少摧一個(gè)工廠”的概率最大.相當(dāng)于希望事件“不摧任何工廠”的概率f最小.我有：.精選文檔f(10.10)x11(10.20)x12(10.15)x13(10.08)x21(10.16)x22(10.12)x23它不是線性的，為此將上式改寫為zlogfx11logx12logx13logx21logx22lo

30、gx23log于是，模型的目標(biāo)函數(shù)為1112130362x212223對(duì)于燃料的拘束條件為：2450 x112480 x122570 x132450 x212480 x22222332570 x2323100 xij480003i1j1經(jīng)過整理，即為550 x11580 x12670 x13400 x21420 x22480 x2348000.飛機(jī)數(shù)目拘束：33x1j40，x2j28j1j1綜上所述，本問題的線性規(guī)劃模型為：maxz=x1112x13x2122x23s.t.550 x11580 x12670 x13400 x21420 x22480 x2348000 x11x12x1340 x

31、21x22x2328xij0，i1，2；j1，2，3.第二章線性規(guī)劃對(duì)偶問題和對(duì)偶變量的經(jīng)濟(jì)意義是什么？.精選文檔從經(jīng)濟(jì)學(xué)的角度來說,對(duì)偶變量反應(yīng)的是對(duì)應(yīng)的原變量的邊沿效應(yīng),即每增添一單位的原變量使目標(biāo)函數(shù)變化的值,當(dāng)原變量在目標(biāo)函數(shù)獲得最優(yōu)解時(shí)沒實(shí)用完的狀況下,原變量的增加不會(huì)改變目標(biāo)函數(shù)的值,此時(shí)原變量的邊沿效應(yīng)為0,即對(duì)偶變量為0,這就是強(qiáng)對(duì)偶理論。簡(jiǎn)述對(duì)偶純真形法的計(jì)算步驟。它與純真形法的異同之處是什么？計(jì)算步驟見書P-42純真形法對(duì)偶純真形法保證原問題是可行解的狀況下向保證對(duì)偶問題是可行解的狀況下向原問原理對(duì)偶問題可行的方向迭代題可行的方向迭代最優(yōu)解看非基變量的查驗(yàn)數(shù)能否都小于看對(duì)偶

32、純真形表的B-1b能否都大于等于判斷等于零零最大最小比值原則最小最小比值原則最大：查驗(yàn)數(shù)最大的那個(gè)非基變量最小：B-1b列數(shù)字最?。ㄘ?fù)數(shù)）的那個(gè)對(duì)迭代為換入變量；應(yīng)的基變量為換出變量；原則最?。築-1b/aik最小的那個(gè)對(duì)應(yīng)的最小：(cj-zi)/alj最小的那個(gè)對(duì)應(yīng)的非基變基變量為換出變量量為換入變量什么是資源的影子價(jià)錢？他和相應(yīng)的市場(chǎng)價(jià)錢之間有什么差別？對(duì)偶變量yi的意義代表在資源最優(yōu)利用條件下對(duì)第i種資源的估價(jià)，這是依據(jù)資源在生產(chǎn)作用中做出的貢獻(xiàn)而獲取的估價(jià)，稱為影子價(jià)錢。市場(chǎng)價(jià)錢是指實(shí)質(zhì)發(fā)生的市場(chǎng)交易價(jià)錢，它是計(jì)量財(cái)務(wù)支出和收入的直接依據(jù)；時(shí)機(jī)成本或支付意向就是經(jīng)濟(jì)解析中的影子價(jià)錢。怎

33、樣依據(jù)原問題和對(duì)偶問題之間的對(duì)應(yīng)關(guān)系，找出兩個(gè)問題變量之間、解及查驗(yàn)數(shù)之間的關(guān)系？1）對(duì)偶(min型)變量的最優(yōu)解等于原問題廢弛變量查驗(yàn)數(shù)的絕對(duì)值2）對(duì)偶問題最優(yōu)解的節(jié)余變量解值等于原問題對(duì)應(yīng)變量的查驗(yàn)數(shù)的絕對(duì)值3）因?yàn)樵瓎栴}和對(duì)偶問題是互相對(duì)偶的，所以對(duì)偶問題的查驗(yàn)數(shù)與原問題的解也有近似上述關(guān)系。.精選文檔（4）更一般地講，不論原問題能否標(biāo)準(zhǔn)，在最優(yōu)解的純真型表中，都有原問題虛變量(廢弛或節(jié)余)的查驗(yàn)數(shù)對(duì)應(yīng)其對(duì)偶問題實(shí)變量(對(duì)偶變量)的最優(yōu)解，原問題實(shí)變量(決議變量)的查驗(yàn)數(shù)對(duì)應(yīng)其對(duì)偶問題虛變量(廢弛或節(jié)余變量)的最優(yōu)解。5.(1)minw=30y1+80y2(2)maxw=30y1+80y

34、2+50y3y+4y2y-y2+4y212133y1+2y223y1+5y2+2y383y1+4y2-4-3y1+4y2-4y3=-4y,y0y0,y無窮制，y0121236.解：maxz=-4x-2x-6x=23-2x1-4x2-8x3+x4=-24s.t.-4x1-x2-4x3+x5=-8x0,j=1,2,3,4,5jcj-4-2-600cBxBbx1x2x3x4x50 x4-24-2-4-8100 x5-8-4-1-401cj-zj-4-2-6-2x261/211/2-1/400 x5-2-7/20-7/2-1/41cj-zj-30-5-1/20-4x14/71011/14-2/7-2x

35、240/010-2/71/77c-z00-2-2/7-6/7jj所以：x*=(4/7,40/7,0,0,0),z*=96/7.z=x1+2x2+3x3+4x4x1+2x2+2x3+3x4+x5=202x1+x2+3x3+2x4+x6=20.精選文檔xj0,j=1,2,3,4,5,6對(duì)偶問題：minw=20y1+20y2y1+2y21y1+y2-y3=12y1+y222y1+y2-y4=22y+3y32y+3y-y=3121253y1+2y243y1+2y2-y6=4y1,y20yi0,i=1,.,6已知對(duì)偶問題最優(yōu)解為：y1*=6/5,y2*=1/5.代入，得：y3=3/5,y4=3/5,y5

36、=0,y6=0Y*XS=(y1,y2)(x5,x6)T=0X*YS=(x1,x2,x3,x4)T(y3,y4,y5,y6)=0so：x5=x6=0,x1=x2=0代入得,x3=x4=4,So:最優(yōu)解x*=(0,0,4,4).8.設(shè)甲、乙、丙3種產(chǎn)品數(shù)目分別為x1,x2,x3，總收益為zmaxz=4x1+x2+5x3x1+2x2+3x3456x1+3x2+5x3+x4=453x+4x+5x303x+4x+5x+x=301231235x1,x2,x30 xi0,i=1,.,5cj-4-2-600icxbx1x2x3x4x5i0 x4563510940 x3034501156cj-zj415005X

37、63/54/101/135500X153-101-154.精選文檔c-z1-300-1jj4x51-101/3-1/1/335x3011-1/2/355c-z0-80-1/-2/jj/333所以最優(yōu)解為x*=(5,0,3)z*=20+15=35即甲生產(chǎn)5件，乙不生產(chǎn)，丙生產(chǎn)3件。(2)p=c-BB-1P=(c1,1,5,0,0)-(c1,5)1-1/301/3-1/3011-1/52/5=(c1,1,5,0,0)-(c1-,5c1/3,5,c1/3-1,-c1/3+2)=(0,c1/3-4,0,1-c1/3,c1/3-2)c1/3-401-c1/30so:3c16c1/3-20So:當(dāng)年的收益

38、在3，6時(shí)，最優(yōu)解不變(3)設(shè)丁為x6,C6=5/2,P6=(3,2)T-11/3-1/331/3P6=BP6=-1/52/521/5C=C-CB-P=5/2-(4,5)1/366B161/5=1/60持續(xù)迭代cj415005/2cxbxxxx4xX1ii2356.精選文檔4x51-01/-111/331/31/355x3011-1/21135/5/55cj-zj0-0-1/-18/332/3/65X1055-121/2654x01-2/-0125/331cj-zj0-1/-07/25/331So:最優(yōu)解x*=(0,0,0,15)Z*即值得安排生產(chǎn)，最優(yōu)計(jì)劃為甲、乙、丙不生產(chǎn)，丁生產(chǎn)15件4）

39、由（1）知對(duì)偶價(jià)錢為2/30.5.所以應(yīng)購買45/5*5-30=15,應(yīng)購進(jìn)15單位的B5）1500cxbx1xxx4B23i0X431093550X3450060c-z15jj5X93/51102/50X-101415-1cj-zj-20-01.精選文檔5X64/5101/350X-101115cj-zj-300-1SO:X=(0,0,6)Z=30即乙不生產(chǎn)，丙生產(chǎn)6件解：（1）設(shè)x1,x2,x3分別為產(chǎn)品甲、乙、丙的產(chǎn)量，其模型為maxz10 x16x24x3x1x2x310010 x14x25x36002x12x26x3300 x1,x2,x30；得此問題的最后純真形表以下：（表34）表

40、34cj1064000CBXBbx1x2x3x4x5x66x2200/3015/65/31/6010 x1100/3101/62/31/600 x610000401zj2200/310620/310/32/30cjzj008/310/32/30可得X100/3,200/3,0T，z2200/3；2）X175/6,275/6,25T；（3）6c115；（4）45；（5）該產(chǎn)品值得安排生產(chǎn)；（6）X95/3,175/3,10T。10.(1)由題意已知原線性規(guī)劃問題目標(biāo)函數(shù)為Max（因j0為最優(yōu)），且c4、c5為0（廢弛變量目標(biāo)函數(shù)系數(shù)為0）。.精選文檔c21c31c1422c1611c1依據(jù)jcj

41、CBB1Pj知：0c34，得：c2226c3101c1023依據(jù)B1011105012105A|b222，得：A|b11011531101102632則原線性規(guī)劃問題的數(shù)學(xué)模型為：其對(duì)偶問題的數(shù)學(xué)模型為：MaxZ6x12x210 x3Min5y110y2x22x353y26s.t.3x1x2x310s.t.y1y22x1,x2,x302y1y210y1,y20直接由表寫出對(duì)偶問題得最優(yōu)解為：Y*4,2(3)令原解xi(XB)i(B-1b)ibi，得br的變化范圍為：Maxbi/air|air0brMinbi/air|air0，此中：airB1。則：iiirMax51b1Min515b115，則

42、0b1202()，即226(4)以單價(jià)購入第一種資源是值得的，因其小于該資源“影子價(jià)錢”（即2.54），可盈余；第二種資源應(yīng)要價(jià)最少為2（影子價(jià)錢），不然不如自己組織生產(chǎn)。第三章運(yùn)輸問題習(xí)題答案判斷表3-35至3-36中的方案能否為運(yùn)輸問題的初始方案。表3-35運(yùn)量表B1B2B3B4B5產(chǎn)量A1015251A2301545.精選文檔A2510353A43535銷量1045152545表3-36運(yùn)量表銷產(chǎn)地B1B2B3B4B5產(chǎn)量地A152025A1812302A31552040A42020銷量2038172020解：表3-35不是初始方案。表3-35中只有7個(gè)數(shù)字格，而作為初始解，應(yīng)有mn14

43、518個(gè)數(shù)字格，所以給出的調(diào)運(yùn)方案不可以作為初始方案。表3-36是初始方案。表3-36中有8個(gè)數(shù)字格，而作為初始解，應(yīng)有mn14518個(gè)數(shù)字格，所以給出的調(diào)運(yùn)方案能作為初始方案。表3-37為某運(yùn)輸問題各產(chǎn)地到各銷地之間的單位運(yùn)價(jià)表和產(chǎn)銷平衡表，試用最小元素法、伏格爾法求初始基本可行解。表3-37單位運(yùn)價(jià)表和產(chǎn)銷平衡表銷地單位運(yùn)價(jià)B1B2B3產(chǎn)量（噸）產(chǎn)地A151812A224114A36743銷量（噸）9101130.精選文檔解：最小元素法在表3-37中找出最小運(yùn)價(jià)1，表示先將A1的產(chǎn)品運(yùn)送到B2，在（A1，B2）的交錯(cuò)處填上10；同時(shí)，B2的銷量得以知足，劃掉其所在列，得表3-37-1。2)

44、在表3-37-1中未劃去的元素中再找出最小運(yùn)價(jià)1，確立A的產(chǎn)品運(yùn)送到B，在（A，B）2323的交錯(cuò)處填上11；同時(shí)，B3的銷量得以知足，劃掉其所在列，得表3-37-2。3)在表3-37-2中未劃去的元素中再找出最小運(yùn)價(jià)2；重復(fù)進(jìn)行下去，直至所有運(yùn)價(jià)都被劃掉，獲取一個(gè)運(yùn)輸方案，即初始基本可行解，見表3-37-3。.精選文檔解：伏格爾法計(jì)算各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行，見表3-37-4；2)在所有行差、列差中找到max差額6，選出它所在第三列中的min運(yùn)費(fèi)1，確立A2的產(chǎn)品運(yùn)送到B3，在（A2，B3）的交錯(cuò)處填上11；同時(shí)，B3的銷量得以知足，劃掉其所在列，得表

45、3-37-5。.精選文檔3)對(duì)表3-37-5中未劃掉的元素再分別計(jì)算各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行；并重復(fù)1）、2），直至給出初始解如表3-37-6所示。用表上作業(yè)法求解表3-38和表3-39描繪的運(yùn)輸問題。表3-38單位運(yùn)價(jià)表和產(chǎn)銷平衡表銷地單位運(yùn)價(jià)B1B2B3B4B5產(chǎn)量.精選文檔產(chǎn)地A1015202040501A22040153030100A33035402550150銷量25115603070表3-39單位運(yùn)價(jià)表和產(chǎn)銷平衡表銷地單位運(yùn)價(jià)B1B2B3B4產(chǎn)量產(chǎn)地A198131418A21010121424A89111363A4107111212銷量614

46、3530解表3-38。利用伏格爾法給出初始解，過程以下：計(jì)算各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行；2)在所有行差、列差中找到max差額，選出它所內(nèi)行或列中的min運(yùn)費(fèi)，確立供銷關(guān)系（填入數(shù)字）；劃掉知足產(chǎn)量的行或知足銷量的列；若產(chǎn)、銷同時(shí)知足，在對(duì)應(yīng)同時(shí)劃掉的那行或那列的隨意空格處填0，再同時(shí)劃掉那行或那列；對(duì)未劃掉的元素再分別計(jì)算各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行；4)重復(fù)1）、2），直至給出初始解，如圖表3-38-1所示。.精選文檔利用位勢(shì)法進(jìn)行查驗(yàn)。1)在初始可行解的表格上增添一行一列，在列中填入ui，內(nèi)行中填入vj；2)計(jì)算位勢(shì)

47、。令u10，對(duì)于數(shù)字格，依據(jù)uivjcij(i,jB)接踵計(jì)算ui,vj，得表3-38-2。3)計(jì)算查驗(yàn)數(shù)（只計(jì)算空格查驗(yàn)數(shù)，數(shù)字格查驗(yàn)數(shù)為0），如表3-38-3所示。4)最優(yōu)解的判斷。因?yàn)樗胁轵?yàn)數(shù)都非負(fù)，故初始解即為最優(yōu)解，如表3-38-1所示。因?yàn)楸?精選文檔3-38-3中有查驗(yàn)數(shù)為0，故該問題有無量多最優(yōu)解。最小運(yùn)費(fèi)為：Z25305015653560153025403030508125解表3-39.該問題中，總產(chǎn)量為18+24+6+12=60，總銷量為6+14+35+30=85，銷量大于產(chǎn)量，屬于供銷不平衡問題，虛構(gòu)新的產(chǎn)地，產(chǎn)量為85-60=25噸，其產(chǎn)品運(yùn)往各銷地的運(yùn)價(jià)為0。獲取新

48、的產(chǎn)銷平衡表如表3-39-1所示。針對(duì)表3-39-1利用伏格爾法給出初始解，過程以下：計(jì)算各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行；2)在所有行差、列差中找到max差額12，選出它所內(nèi)行或列中的min運(yùn)費(fèi)，確立A5的產(chǎn)品運(yùn)送到B4，在（A5，B4）的交錯(cuò)處填上25；同時(shí)，A5的產(chǎn)量得以知足，劃掉其所內(nèi)行，得表3-39-2供銷關(guān)系（填入數(shù)字）；.精選文檔對(duì)未劃掉的元素再分別計(jì)算各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行；重復(fù)1）、2），直至給出初始解，如表3-39-3所示。注：若填入某個(gè)數(shù)字時(shí)，產(chǎn)量、銷量同時(shí)知足，在對(duì)應(yīng)同時(shí)劃掉的那行或那列的隨意空格

49、處（本題選擇最小運(yùn)費(fèi)處）填0，再同時(shí)劃掉那行或那列（本題在確立（A3，B1）處的6時(shí)產(chǎn)銷同時(shí)知足，在最小運(yùn)費(fèi)9（A3，B2）處填0）。.精選文檔利用位勢(shì)法進(jìn)行查驗(yàn)。1)在初始可行解的表格上增添一行一列，在列中填入ui，內(nèi)行中填入vj；2)計(jì)算位勢(shì)。令u10，對(duì)于數(shù)字格，依據(jù)uivjcij(i,jB)接踵計(jì)算ui,vj，如表3-39-4所示。3)依據(jù)ijcij(uivj)(i,jN)計(jì)算所有空格的查驗(yàn)數(shù)。如12c12(u1v2)9(07)2上述計(jì)算可以直接在表進(jìn)步行，最后結(jié)果如表3-39-5所示。.精選文檔因?yàn)榇嬖谪?fù)查驗(yàn)數(shù)，沒有達(dá)到最優(yōu)解，需進(jìn)行閉回路調(diào)整。閉回路調(diào)整。a)找出最小負(fù)查驗(yàn)數(shù)（-3

50、）所對(duì)應(yīng)空格（A3，B3）的閉回路，如表3-39-6所示；b)確立最大調(diào)整量1min0,110；奇數(shù)極點(diǎn)加，偶數(shù)極點(diǎn)減。c)調(diào)整后的方案如表3-39-7所示。.精選文檔重復(fù)進(jìn)行查驗(yàn)數(shù)計(jì)算，進(jìn)行解得最優(yōu)性判斷，直至所有查驗(yàn)數(shù)非負(fù)，達(dá)到最優(yōu)解。計(jì)算過程如表3-39-8至表3-39-15所示。以空格（A4，B3）為調(diào)入格，以（A4，B3）（A4，B2）（A1，B2）（A1，B3）（A4，B3）為閉回路進(jìn)行調(diào)整，調(diào)整量2min12,1111，得表3-39-9。.精選文檔計(jì)算位勢(shì)：計(jì)算查驗(yàn)數(shù)：.精選文檔以空格（A4，B4）為調(diào)入格，以（A4，B4）（A4，B2）（A1，B2）（A1，B4）（A4，B4）

51、為閉回路進(jìn)行調(diào)整，調(diào)整量3min1,51，得表3-39-12。計(jì)算位勢(shì)和查驗(yàn)數(shù)如表3-39-13所示。.精選文檔以空格（A1，B1）為調(diào)入格，以（A1，B1）（A1，B4）（A4，B4）（A4，B3）（A3，B3）（A，B）（A，B）為閉回路進(jìn)行調(diào)整，調(diào)整量3min4,11,64，得表3-39-14。3111計(jì)算位勢(shì)和查驗(yàn)數(shù)如表3-39-15所示。.精選文檔可以看出，所有查驗(yàn)數(shù)非負(fù)，已獲取最優(yōu)解，如表3-39-14所示。因?yàn)榭崭?A4,B2)的檢驗(yàn)數(shù)為0，表示該問題有無量多最優(yōu)解。最小運(yùn)輸成本為Z49281482412411711512633。某石油企業(yè)設(shè)有四個(gè)煉油廠，它們生產(chǎn)一般汽油，并為七

52、個(gè)銷售區(qū)服務(wù)，生產(chǎn)和需求及從各煉油廠運(yùn)往各銷售區(qū)每公升汽油平均運(yùn)費(fèi)（單位：角/公升）如表3-40所示。問應(yīng)怎樣安排調(diào)運(yùn)，使運(yùn)費(fèi)最省。表3-40煉油廠供給銷售區(qū)的有關(guān)數(shù)據(jù)銷地銷售區(qū)銷售區(qū)銷售區(qū)銷售區(qū)銷售區(qū)銷售區(qū)銷售區(qū)日產(chǎn)量運(yùn)費(fèi)1234567（萬公產(chǎn)地升）煉油廠1652636335煉油廠2375869225煉油廠3486558515煉油廠4744747440日最大銷25201025101510售量（萬.精選文檔公升）解：設(shè)xij為煉油廠i供給給顧客j的汽油數(shù)目，則該問題的模型以下：maxZ6x115x122x136x143x156x163x17+3x217x225x238x246x259x262x

53、27+4x318x326x335x345x358x365x37+7x414x424x437x444x457x464x47x11x12x13x14x15x16x1735x21x22x23x24x25x26x27=25x31x32x33x34x35x36x37=15x41x42x43x44x45x46x4740 x11x21x31x4125s.t.x12x22x32x4220 x13xxx43102333x14x24x34x4425x15x25x35x4510 x16x26x36x4615x17x27x37x4710 xij0(i1,2,3,4:j1,2,3,4,5,6,7)利用Excel電子表格

54、求解該問題，重點(diǎn)步驟如圖3-1圖3-3所示。圖3-1原始數(shù)據(jù)和最優(yōu)解表使用到的部分公式以下：J10=SUM(C10:I10)；C14=SUM(C10:C13)；K16=SUMPRODUCT(C3:I6,C10:I13)。.精選文檔圖3-2規(guī)劃求解參數(shù)設(shè)置表I圖3-3規(guī)劃求解參數(shù)設(shè)置II所以，最有供給方案為，最低運(yùn)費(fèi)為480。某企業(yè)在四個(gè)工廠中特意生產(chǎn)一種產(chǎn)品。在將來的四個(gè)月中，有四個(gè)處于國(guó)內(nèi)不同樣地域的暗藏顧客（批發(fā)商）很可能大批采買。顧客1是企業(yè)優(yōu)先級(jí)最高的顧客，所以他的所有訂購量都應(yīng)當(dāng)知足；顧客2和顧客3也是企業(yè)很重要的顧客，所以營(yíng)銷經(jīng)理以為最少要知足他們訂單的1/3；顧客4，營(yíng)銷經(jīng)理以為

55、不需要進(jìn)行特別考慮。因?yàn)檫\(yùn)輸成本上的差別，銷售一個(gè)產(chǎn).精選文檔品獲取的凈收益也不同樣，其在很大程度上取決于哪個(gè)工廠供給哪個(gè)顧客（見表3-41）。那么，怎樣供給貨物使企業(yè)總收益最大？表3-41工廠供給顧客的有關(guān)數(shù)據(jù)銷地單位運(yùn)價(jià)顧客1顧客2顧客3顧客4產(chǎn)量（kg）產(chǎn)地A19813141800A2101012142400A38911131600A107111222004訂購量（kg）1600140034003000解：依據(jù)題意，各工廠要知足不同樣顧客的需求（采買量），即每位顧客的實(shí)質(zhì)供給量大于等于其最小采買量而小于等于其最大采買量，獲取表3-41-1。表3-41-1xij銷地單位運(yùn)價(jià)顧客1顧客2顧客

56、3顧客4產(chǎn)量（kg）產(chǎn)地A19813141800A2101012142400A38911131600A410711122200最小采買量（kg）160014001/334001/30最大采買量（kg）1600140034003000設(shè)xij為工廠i供給給顧客j的產(chǎn)品數(shù)目，則該問題的模型以下：.精選文檔maxZ9x118x1213x1314x1410 x2110 x2212x2314x248x319x3211x3313x3410 x417x4211x4312x44x11x12x13x141800（工廠1）x21x22x23x242400（工廠2）x31x32x33x341600（工廠3）x41x

57、42x43x442200（工廠4）s.t.x11x21x31x411600（顧客1）14003x12x22xx421400（顧客2）3234003x13x23x33x433400（顧客3）x14x24x34x443000（顧客4）xij0(i,j1,2,3,4)利用Excel電子表格求解該問題，重點(diǎn)步驟如圖3-4圖3-6所示。圖3-4原始數(shù)據(jù)和最優(yōu)解表使用到的部分公式以下：G8=SUM(C18:F8)；C15=SUM(C8:C11)；I15=SUMPRODUCT(C2:F5,C8:F11)。.精選文檔圖3-5規(guī)劃求解參數(shù)設(shè)置表I圖3-6規(guī)劃求解參數(shù)設(shè)置表II所以，最有供給方案為最大收益為342

58、67。某玩具企業(yè)生產(chǎn)三種新式玩具，每個(gè)月可供給量分別為1500、2500、3000件，分別送到三個(gè)玩具店銷售。已知每個(gè)月各玩具店各樣玩具的總預(yù)期銷售量均為2000件，因?yàn)榻?jīng)營(yíng)方面的原因，各玩具店銷售各樣玩具的盈余額不同樣（見表3-42）。又有甲玩具店要求最少供給B玩具1000.精選文檔件，而拒絕引進(jìn)A玩具。求知足上述條件下使總贏利最大的供銷分派方案。表3-42三種新式玩具的有關(guān)數(shù)據(jù)玩具店可供給量盈余甲乙丙（件）新式玩具A561500B159102500C1311123000預(yù)期銷量（件）200020002000解：設(shè)xij為三種各玩具i供給給各玩具店j的數(shù)目，依據(jù)題意甲玩具店要求最少供給B玩具

59、1000件，而拒絕引進(jìn)A玩具可得，A玩具不可以供給給甲玩具店，B玩具最少供給甲玩具店1000件，故該問題的模型以下：maxZ5x126x1315x219x2210 x23+13x3111x3212x33x11x12x13x211500 x21x22x232500 x31x32x333000 x110s.t.x211000 x21x312000 x12x22x322000 x13x23x332000 xij0(i,j1,2,3)利用Excel電子表格求解該問題，重點(diǎn)步驟如圖3-7圖3-9所示。.精選文檔圖3-7原始數(shù)據(jù)和最優(yōu)解表使用到的部分公式以下：F7=SUM(C7:E7)；C10=SUM(C

60、7:C9)；H12=SUMPRODUCT(C2:E4,C7:E9)。圖3-8規(guī)劃求解參數(shù)設(shè)置表I.精選文檔圖3-9規(guī)劃求解參數(shù)設(shè)置表II所以，最有供給方案為最大收益為72000。.精選文檔第四章整數(shù)規(guī)劃習(xí)題答案用分支定界法求解以下整數(shù)規(guī)劃問題：（1）x2（2）3x12x2maxZx1maxZ14x19x2512x13x2146x13x212x1x29x1,x2且全整x1,x20且全整0解：（1）暫不考慮整數(shù)拘束，利用圖解法求解對(duì)應(yīng)的廢弛問題LP：maxZx1x214x19x251LPs.t.6x13x21x1,x20獲取最優(yōu)解和最有目標(biāo)函數(shù)值為x132,x2309z(0)8718該解不符合整數(shù)