《運(yùn)籌學(xué)》計(jì)算題《運(yùn)籌學(xué)》計(jì)算題

西安郵電學(xué)院試題庫(kù)管理系統(tǒng)——試題表第112頁(yè)共112頁(yè)專(zhuān)業(yè)代碼11專(zhuān)業(yè)名稱(chēng)信息管理與信息系統(tǒng)課程代碼18課程名稱(chēng)運(yùn)籌學(xué)試題類(lèi)型代碼08試題類(lèi)型名稱(chēng)計(jì)算題出題人管理員出題日期2005-知識(shí)點(diǎn)代碼題干答案評(píng)分標(biāo)準(zhǔn)難度系數(shù)認(rèn)知分類(lèi)建議分?jǐn)?shù)建議時(shí)間11180101工廠每月生產(chǎn)A、B、C三種產(chǎn)品,單件產(chǎn)品的原材料消耗量、設(shè)備臺(tái)時(shí)的消耗量、資源限量及單件產(chǎn)品利潤(rùn)如表所示．根據(jù)市場(chǎng)需求,預(yù)測(cè)三種產(chǎn)品最低月需求量分別是150、260和120,最高月需求是250、310和130.試建立該問(wèn)題的數(shù)學(xué)模型,使每月利潤(rùn)最大．產(chǎn)品資源ABC資源限量材料(kg)1.51.242500設(shè)備(臺(tái)時(shí))31.61.21400利潤(rùn)(元/件)101412設(shè)x1、x2、x3分別為產(chǎn)品A、B、C的產(chǎn)量，則數(shù)學(xué)模型為較易運(yùn)用108A、B兩種產(chǎn)品，都需要經(jīng)過(guò)前后兩道工序加工，每一個(gè)單位產(chǎn)品A需要前道工序1小時(shí)和后道工序2小時(shí)，每一個(gè)單位產(chǎn)品B需要前道工序2小時(shí)和后道工序3小時(shí)．可供利用的前道工序有11小時(shí)，后道工序有17小時(shí)．每加工一個(gè)單位產(chǎn)品B的同時(shí)，會(huì)產(chǎn)生兩個(gè)單位的副產(chǎn)品C，且不需要任何費(fèi)用，產(chǎn)品C一部分可出售贏利，其余的只能加以銷(xiāo)毀．出售單位產(chǎn)品A、B、C的利潤(rùn)分別為3、7、2元，每單位產(chǎn)品C的銷(xiāo)毀費(fèi)為1元．預(yù)測(cè)表明，產(chǎn)品C最多只能售出13個(gè)單位．試建立總利潤(rùn)最大的生產(chǎn)計(jì)劃數(shù)學(xué)模型．設(shè)x1,x2分別為產(chǎn)品A、B的產(chǎn)量，x3為副產(chǎn)品C的銷(xiāo)售量,x4為副產(chǎn)品C的銷(xiāo)毀量，有x3+x4=2x2,Z為總利潤(rùn)，則數(shù)學(xué)模型為某企業(yè)生產(chǎn)3種產(chǎn)品甲、乙、丙，產(chǎn)品所需的主要原料有A、B兩種，原料A每單位分別可生產(chǎn)產(chǎn)品甲、乙、丙底座12、18、16個(gè)；產(chǎn)品甲、乙、丙每個(gè)需要原料B分別為13kg、8kg、10kg，設(shè)備生產(chǎn)用時(shí)分別為10.5、12.5、8臺(tái)時(shí)，每個(gè)產(chǎn)品的利潤(rùn)分別為1450元、1650元、1300元。按月計(jì)劃，可提供的原料A為20單位，原料B350kg，設(shè)備月正常的工作時(shí)間為3000臺(tái)時(shí)。建立實(shí)現(xiàn)總利潤(rùn)最高的數(shù)學(xué)模型(不需要計(jì)算結(jié)果)。設(shè)x1,x2,x3為產(chǎn)品甲、乙、丙的數(shù)量Maxf(x)=1450x1+1650x2+1300x3S.t.x1/12+x2/18+x3/16≤2013x1+8x2+10x3≤35010.5x1+12.5x2+8x3≤3000x1,x2,x3≥0某工廠要用四種合金T1，T2，T3和T4為原料，經(jīng)熔煉成為一種新的不銹鋼G。這四種原料含元素鉻（Cr），錳（Mn）和鎳（Ni）的含量（%），這四種原料的單價(jià)以及新的不銹鋼材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30單價(jià)(元/公斤)115978276設(shè)熔煉時(shí)重量沒(méi)有損耗，要熔煉成100公斤不銹鋼G，應(yīng)選用原料T1，T2，T3和T4設(shè)選用原料T1，T2，T3和T4分別為x1，x2，x3，x4公斤，根據(jù)條件，可建立相應(yīng)的線(xiàn)性規(guī)劃XE"線(xiàn)性規(guī)劃"模型如下：minz=115x1+97x2+82x3+76x4s.t.0.0321x1+0.0453x2+0.0219x3+0.017x4≥3.200.0204x1+0.0112x2+0.0357x3+0.0433x4≥2.100.0582x1+0.0306x2+0.0427x3+0.0273x4≥4.30x1+x2+x3+x4=100x1,x2,x3,x4≥0設(shè)某種物資從兩個(gè)供應(yīng)地A1，A2運(yùn)往三個(gè)需求地B1，B2，B3。各供應(yīng)地的供應(yīng)量XE"供應(yīng)量"、各需求地的需求量XE"需求量"、每個(gè)供應(yīng)地到每個(gè)需求地的單位物資運(yùn)價(jià)如下表所示。運(yùn)價(jià)（元/噸）B1B2B3供應(yīng)量XE"供應(yīng)量"（噸）A123535A247825需求量XE"需求量"（噸）103020求使運(yùn)費(fèi)最小的線(xiàn)性規(guī)劃模型。設(shè)xij為從供應(yīng)地Ai運(yùn)往需求地Bj的物資數(shù)量（i=1,2；j=1,2,3），z為總運(yùn)費(fèi)，則總運(yùn)費(fèi)最小的線(xiàn)性規(guī)劃XE"線(xiàn)性規(guī)劃"模型為：minz=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35x21+x22+x23=25x11+x21=10x12+x22=30x13+x23=20xij≥0某企業(yè)生產(chǎn)3種產(chǎn)品甲、乙、丙，產(chǎn)品所需的主要原料有A、B兩種，原料A每單位分別可生產(chǎn)產(chǎn)品甲、乙、丙底座12、18、16個(gè)；產(chǎn)品甲、乙、丙每個(gè)需要原料B分別為13kg、8kg、10kg，設(shè)備生產(chǎn)用時(shí)分別為10.5、12.5、8臺(tái)時(shí)，每個(gè)產(chǎn)品的利潤(rùn)分別為1450元、1650元、1300元。按月計(jì)劃，可提供的原料A為20單位，原料B350kg，設(shè)備月正常的工作時(shí)間為3000臺(tái)時(shí)。建立實(shí)現(xiàn)總利潤(rùn)最高的數(shù)學(xué)模型(不需要計(jì)算結(jié)果)。設(shè)x1,x2,x3為產(chǎn)品甲、乙、丙的數(shù)量Maxf(x)=1450x1+1650x2+1300x3S.t.x1/12+x2/18+x3/16≤2013x1+8x2+10x3≤35010.5x1+12.5x2+8x3≤3000x1,x2,x3≥0有張、王、李、趙4位教師被分配教語(yǔ)文、數(shù)學(xué)、物理、化學(xué)4門(mén)課程，每位教師教一門(mén)課程，每門(mén)課程由一位老師教。根據(jù)這四位教師以往教課的情況，他們分別教這四門(mén)課程的平均成績(jī)?nèi)缦卤恚赫Z(yǔ)文數(shù)學(xué)物理化學(xué)張92688576王82917763李83907465趙93618375四位教師每人只能教一門(mén)課，每一門(mén)課只能由一個(gè)教師來(lái)教。要確定哪一位教師上哪一門(mén)課，使四門(mén)課的平均成績(jī)之和為最高。設(shè)xij（i=1,2,3,4；j=1,2,3,4）為第i個(gè)教師是否教第j門(mén)課，xij只能取值0或1，其意義如下：這個(gè)指派問(wèn)題XE"指派問(wèn)題"的線(xiàn)性規(guī)劃XE"線(xiàn)性規(guī)劃"模型為：maxz=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44s.t. x11+x12+x13+x14=1 x21+x22+x23+x24=1 x31+x32+x33+x34=1 x41+x42+x43+x44=1 x11+x21+x31+x41=1 x12+x22+x32+x42=1 x13+x23+x33+x43=1 x14+x24+x34+x44=1 xij=0,1中應(yīng)用88某工廠擁有A、B、C三種類(lèi)型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)XE"利潤(rùn)"以及三種設(shè)備可利用的時(shí)數(shù)如下表所示：每件產(chǎn)品占用的機(jī)時(shí)數(shù)（小時(shí)/件）產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品丁設(shè)備能力（小時(shí)）設(shè)備A1.51.02.41.02000設(shè)備B1.05.01.03.58000設(shè)備C1.53.03.51.05000利潤(rùn)XE"利潤(rùn)"（元/件）5.247.308.344.18用線(xiàn)性規(guī)劃XE"線(xiàn)性規(guī)劃"制訂使總利潤(rùn)XE"利潤(rùn)"最大的生產(chǎn)計(jì)劃?？梢越⑷缦碌木€(xiàn)性規(guī)劃XE"線(xiàn)性規(guī)劃"模型：Maxz=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.5x1+3.0x2+3.5x3+1.0x4≤5000x1,x2,x3,x4≥011180102求解下列線(xiàn)性規(guī)劃問(wèn)題maxz=x+xst.有可行解,但maxz無(wú)界1求解下列線(xiàn)性規(guī)劃問(wèn)題maxz=3x-2xst.無(wú)可行解求解下列線(xiàn)性規(guī)劃問(wèn)題maxz=3x+9xst.無(wú)窮多最優(yōu)解,z=66求解下列線(xiàn)性規(guī)劃問(wèn)題maxz=3x+4xst.惟一最優(yōu)解,z=30,x=20/3,x=8/3用圖解法解下列線(xiàn)性規(guī)劃的問(wèn)題。minz=-x+xs．t．唯一最優(yōu)解x用圖解法解下列線(xiàn)性規(guī)劃的問(wèn)題。maxz=-x+xs．t．多重解，在用圖解法解下列線(xiàn)性規(guī)劃的問(wèn)題。maxz=x+xs．t．可行域是空集用圖解法解下列線(xiàn)性規(guī)劃的問(wèn)題。minz=2x+3xs．t．唯一最優(yōu)解x，可行域無(wú)界。用圖解法解下列線(xiàn)性規(guī)劃的問(wèn)題。minz=xs．t．多重解，圖解下列線(xiàn)性規(guī)劃并指出解的形式：最優(yōu)解X＝（1/2，1/2）；最優(yōu)值Z=－1/2圖解下列線(xiàn)性規(guī)劃并指出解的形式：最優(yōu)解X＝（3/4，7/2）；最優(yōu)值Z=－45/4圖解下列線(xiàn)性規(guī)劃并指出解的形式：最優(yōu)解X＝（4，1）；最優(yōu)值Z=－10圖解下列線(xiàn)性規(guī)劃并指出解的形式：最優(yōu)解X＝（3/2，1/4）；最優(yōu)值Z=7/4圖解下列線(xiàn)性規(guī)劃并指出解的形式：最優(yōu)解X＝（3，0）；最優(yōu)值Z=3圖解下列線(xiàn)性規(guī)劃并指出解的形式：無(wú)界解。圖解下列線(xiàn)性規(guī)劃并指出解的形式：無(wú)可行解。圖解下列線(xiàn)性規(guī)劃并指出解的形式：最優(yōu)解X＝（2，4）；最優(yōu)值Z=13線(xiàn)性規(guī)劃問(wèn)題:maxz=cx+xst.試用圖解法分析,問(wèn)題最優(yōu)解隨c(<c<)取值不同的變化情況.c值最優(yōu)解<c<1c=11<c<2c=22<c<A點(diǎn)(6,0)AB線(xiàn)段B點(diǎn)(2,4)BC線(xiàn)段C點(diǎn)(0,5)11180103將下列線(xiàn)性規(guī)劃化為標(biāo)準(zhǔn)形式將絕對(duì)值化為兩個(gè)不等式，則標(biāo)準(zhǔn)形式為將下列線(xiàn)性規(guī)劃問(wèn)題變換成標(biāo)準(zhǔn)型，并列出初始單純型表。 將此線(xiàn)性規(guī)劃問(wèn)題變換成標(biāo)準(zhǔn)型：令，在約束條件中分別添加松弛變量、剩余變量和人工變量得： 列出初始單純型表如下：→21-22-M0基b-M4[1]11-1100611-11012+M1+MM-22-M00將下列線(xiàn)性規(guī)劃問(wèn)題變換成標(biāo)準(zhǔn)型，并列出初始單純型表。解：令化為標(biāo)準(zhǔn)型為 表略將下列線(xiàn)性規(guī)劃化為標(biāo)準(zhǔn)形式令為松馳變量，則標(biāo)準(zhǔn)形式為將下列線(xiàn)性規(guī)劃化為標(biāo)準(zhǔn)形式【解】方法1：方法2：令則標(biāo)準(zhǔn)型為將下列線(xiàn)性規(guī)劃化為標(biāo)準(zhǔn)形式令，線(xiàn)性規(guī)劃模型變?yōu)闃?biāo)準(zhǔn)型為將下列線(xiàn)性規(guī)劃問(wèn)題變換成標(biāo)準(zhǔn)型,并列出初始單純形表:minz=2x-x+2xst.令x=-x,x=x-x,化為標(biāo)準(zhǔn)型為maxz=2x+x-2x+2x-Mx+0xst.將下列線(xiàn)性規(guī)劃問(wèn)題變換成標(biāo)準(zhǔn)型,并列出初始單純形表:maxz=2x+x+3x+xst.令x=-x,x=x-x,化為標(biāo)準(zhǔn)型為maxz=2x-x+3x+x-x+0x-Mx+0x-Mxst.將下列線(xiàn)性規(guī)劃問(wèn)題maxz=s．t．（1）表示為矩陣形式；（2）化成典型式后，寫(xiě)出以為基變量的單純形表；c6-2100bCXxxxxx1x01/61-1/61/32/36x1-2/302/3-1/31/3011/60-23/65/38/311180104用單純形法求解minz=6x+4xst.惟一最優(yōu)解,z=3,x=1/2,x=0;用單純形法求解maxz=4x+8xst.無(wú)可行解用單純形法求解Maxz=3x+x-2xst．X單純型法求解下列線(xiàn)性規(guī)劃問(wèn)題，并指出問(wèn)題的解屬于哪一類(lèi)： 最優(yōu)解x1x2x3x4x5x320011/3-1/3x260101/20x12100-1/31/3cj-zj000-3/2-1單純型法求解下列線(xiàn)性規(guī)劃問(wèn)題，并指出問(wèn)題的解屬于哪一類(lèi)：最優(yōu)解x1x2x3x4x5x6x4100011-1-2x115101/201/21/2x2501-3/20-1/21/2cj-zj00-3/20-3/2-1/2用單純形法求解Minz=3x+x-5x-2xst．X用單純形法求解Maxz=x+xst．無(wú)界解用單純形法求解Minz=x-3x-2xst．X用單純形法求解Maxz=4x+14xst．多重解z在下列線(xiàn)性規(guī)劃問(wèn)題中,找出所有基解.指出哪些是基可行解并分別代入目標(biāo)函數(shù),比較找出最優(yōu)解.maxz=3x+5xst.z△00412180△4001261260-212018△4306027△0640630△26200364600-642094-6045在下列線(xiàn)性規(guī)劃問(wèn)題中,找出所有基解.指出哪些是基可行解并分別代入目標(biāo)函數(shù),比較找出最優(yōu)解.maxz=4x+12x+18xst.z000-3-503000-5120010-318-9/205/2002705/20-3030△03/210036△35/200042△005/29/2045考慮下列線(xiàn)性規(guī)劃：MaxZ=-5x1+5x2+13x3S.t.最優(yōu)單純形表為：XBb'X1X2X3X4X5X220-11310X510160-2-41-Z-10000250求此線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題的最優(yōu)解；(2)y*=(5,0)T；考慮線(xiàn)性規(guī)劃問(wèn)題maxz=2x+3xs．t．（1）求最優(yōu)解；（2）若增加變量x，它在目標(biāo)函數(shù)中的系數(shù)為5，在約束方程中的系數(shù)為3，2，6，3，根據(jù)原問(wèn)題的最優(yōu)解試求新的最優(yōu)解；答案：（1）x（2）x用單純形原理求解以下線(xiàn)性規(guī)劃問(wèn)題maxz=3x1+2x22x1-3x23-x1+x25x1,x20minz’=-3x1-2x22x1-3x2+x3=3-x1+x2+x4=5x1,x2,x3,x40第一次疊代取B=[a3，a4]，基變量為x3，x4，非基變量為x1，x2=0。將基變量和目標(biāo)函數(shù)用非基變量表示：z’=-3x1-2x2x3=3-2x1+3x2+x4=5+x1-x2選取x1進(jìn)基，當(dāng)x1=3/2時(shí)，x3=0離基，新的基變量為x1=3/2，x4=13/2，非基變量為x2，x3=0，目標(biāo)函數(shù)值為z’=-9/2。第二次疊代將基變量和目標(biāo)函數(shù)用非基變量表示：2x1=3+3x2-x3-x1+x4=5-x2將第一個(gè)約束中的基變量x1的系數(shù)變成1，x1=3/2+3/2x2-1/2x3-x1+x4=5-x2消去第二個(gè)約束中的基變量x1x1=3/2+3/2x2-1/2x3+x4=13/2+1/2x2-1/2x3將基變量x1代入目標(biāo)函數(shù)z’=-3x1-2x2=-3(3/2+3/2x2-1/2x3)-2x2=-9/2-13/3x2+3/2x3選取x2進(jìn)基，當(dāng)x2增加時(shí)，基變量x1和x4隨之增加，目標(biāo)函數(shù)z’無(wú)下界，即z無(wú)上界。已知線(xiàn)性規(guī)劃問(wèn)題maxz=x+3xst.表中所列的解(a)~(f)均滿(mǎn)足約束條件①②③,試指出表中哪些解是可行解,哪些是基解.哪些是基可行解序號(hào)xxxxx(a)24300(b)100-504(c)30274(d)14.540-0.5(e)02562(f)04520可行解有(a)(c)(e)(f),基解有(a)(b)(f),基可行解有(a)(f)用單純形法求解此問(wèn)題的最優(yōu)解為:x1=4,x2=2,x5=4,x3=x4=x1=0,z*=2′4+3′2=14用單純形法求解此問(wèn)題的最優(yōu)解為:x1=4,x2=9,x3=1,x4=x5=x6=x7=0,z*=-3′4+9+1=-2用單純形表求以下線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解。最優(yōu)解為x1=0，x2=3，x3=9，x4=0，x5=0，x6=12，minz’=-15，maxz=15求以下的線(xiàn)性規(guī)劃XE"線(xiàn)性規(guī)劃"問(wèn)題的基礎(chǔ)可行解：引進(jìn)松弛變量XE"松弛變量"x3，x4，x5≥0，得到minz=-2x1-x2 s.t.x1+x2+x3=6x2+x4=3x1+2x2+x5=9x1,x2,x3,x4,x5≥0其中 對(duì)于基XE"基" 是一退化XE"退化"的基XE"基"礎(chǔ)可行解XE"可行解"，即 X1=(x1，x2，x3，x4，x5)T=(3，3，0，0，0)T。同樣，對(duì)于基XE"基" B2=[a1，a2，a4]相應(yīng)的基XE"基"礎(chǔ)可行解XE"可行解"為 即 X2=(x1，x2，x3，x4，x5)T=(3，3，0，0，0)T再看基XE"基" B3=[a1，a2，a5]相應(yīng)的基XE"基"礎(chǔ)可行解XE"可行解"為 即 X3=(x1，x2，x3，x4，x5)T=(3，3，0，0，0)T某廠在數(shù)量分別為b，b的資源限制下生產(chǎn)三種產(chǎn)品，為求利潤(rùn)最大，利用單純形法得以下最優(yōu)表：表6cccc00bCXXXXXXccxx13-11-1212-4-3-4表中x（j=1，2，3）分別代表產(chǎn)品Ⅰ，Ⅱ，Ⅲ的產(chǎn)量，x，x是松弛變量。（1）求c，c，c。（2）求三種產(chǎn)品的最佳產(chǎn)量和最大利潤(rùn)。（3）B=（P，P）的逆矩陣是什么？（4）原料中那一種有剩余？為什么？（5）產(chǎn)品Ⅲ的價(jià)格在何種情況下投產(chǎn)它才會(huì)使利潤(rùn)變大？（1）c=2，c=3，c=1（2）x=1，x=2，X=0,z=8（3）B（4）兩種原料無(wú)剩余（5）c>5較難綜合1412求最大化問(wèn)題時(shí)有下表：表5cbCXXXXXXX4100-1-501-10-300-41e2300-30其中，，，，，e是未知常數(shù)，x，j=1,2,34,5,6.試在下述條件下，求出六個(gè)未知量的有關(guān)條件：（1）現(xiàn)行解是最優(yōu)解，且為多重解；（2）現(xiàn)行解是非可行解；（3）現(xiàn)行解是退化基本解；（4）無(wú)界解；（5）現(xiàn)行解可行，但以x替代第三個(gè)基變量后，目標(biāo)數(shù)值將增加。并求迭代后增值多少？（1）（2）e<0（3）e=0（4）（5）已知(x1，x2，x3)＝(4，0，4)是以下線(xiàn)性規(guī)劃的一個(gè)基礎(chǔ)可行解，以這個(gè)基為初始可行基，求解這個(gè)線(xiàn)性規(guī)劃問(wèn)題將問(wèn)題轉(zhuǎn)變?yōu)闃O小化，引進(jìn)松弛變量x3，線(xiàn)性規(guī)劃問(wèn)題成為minz’=-x1+2x2s.t.3x1+4x2=122x1-x2+x3=12x1,x2,x3≥0選取x1、x3為基變量，列出單純形表z’x1x2x3RHSz’11-200x10[3]4012x302-1112消去基變量x1在目標(biāo)函數(shù)和第二個(gè)約束條件中的系數(shù)z’x1x2x3RHSz’10-10/30-4x1014/304x300-11/314得到最優(yōu)解，最優(yōu)解為x1=4，x2=0，x3=4，minz’=-4，maxz=4。用單純形表求解以下線(xiàn)性規(guī)劃問(wèn)題標(biāo)準(zhǔn)化，將目標(biāo)函數(shù)轉(zhuǎn)變成極小化，引進(jìn)松弛變量x4,x5,x60,得到：minz’=-x1+2x2-x3s.t.x1+x2+x3+x4=122x1+x2-x3+x5=6-x1+3x2+x6=9x1,x2,x3,x4,x5,x6≥0列出初始單純形表z’x1x2x3x4x5x6RHSz’11-210000x4011[1]1001212/1x5021-10106--x60-1300019--選取x3為進(jìn)基變量，確定x4為離基變量z’x1x2x3x4x5x6RHSz’10-30-100-12x301111001212/1x50[3]201101818/3x60-1300019--得到最優(yōu)解（x1,x2,x3,x4,x5,x6）=（0,0,12,0,18,9），minz’=-12，maxz=12由于其中非基變量x1在目標(biāo)函數(shù)中的系數(shù)為0，x1進(jìn)基，x5離基，可以得到另一最優(yōu)解：z’x1x2x3x4x5x6RHSz’10-30-100-12x3001/312/3-1/306x1012/301/31/306x60011/301/31/3115新的最優(yōu)解為（x1,x2,x3,x4,x5,x6）=（6,0,6,0,0,15），minz’=-12，maxz=12原問(wèn)題最優(yōu)解的全體為：， （0≤≤1），都有maxz=12用單純形表求解以下線(xiàn)性規(guī)劃問(wèn)題（2）minz=-2x1-x2+3x3-5x4s.t.x1+2x2+4x3-x4≤62x1+3x2-x3+x4≤12x1+x3+x4≤4x1,x2,x3,x4≥0引進(jìn)松弛變量x5，x6，x70，得到minz=-2x1-x2+3x3-5x4s.t.x1+2x2+4x3-x4+x5=62x1+3x2-x3+x4+x6=12x1+x3+x4+x7=4x1,x2,x3,x4,x5,x6,x7≥0初始單純形表為zx1x2x3x4x5x6x7RHSz121-350000x50124-11006--x6023-110101212/1x70101[1]00144/1x4進(jìn)基，x7離基zx1x2x3x4x5x6x7RHSz1-31-8000-5-20x5022501011010/2x601[3]-2001-188/3x4010110014--x2進(jìn)基，x6離基zx1x2x3x4x5x6x7RHSz1-10/31-22/300-1/3-14/3-68/3x504/3019/301-2/35/314/3x201/31-2/3001/3-1/38/3x4010110014最優(yōu)解為：(x1,x2,x3,x4,x5,x6,x7)=(0,8/3,0,4,14/3,0,0)，minz=-68/3用單純形表求解以下線(xiàn)性規(guī)劃問(wèn)題將第一、第二個(gè)約束條件兩邊同乘以-1；引進(jìn)松弛變量x3，x4，x5，x6≥0，得到minz=3x1-x2s.t.x1+3x2+x3=32x1-3x2+x4=62x1+x2+x5=84x1-x2+x6=16x1,x2,x3,x4,x5,x6≥0初始單純形表為：zx1x2x3x4x5x6RHSz1-3100000x301[3]100033/3x402-301006--x5021001088/1x604-1000116--x2進(jìn)基，x3離基，zx1x2x3x4x5x6RHSz1-10/30-1/3000-1x201/311/30001x403011009x505/30-1/30107x6013/301/300117最優(yōu)解為：（x1,x2,x3,x4,x5,x6）=（0,1,0,9,7,17），minz=-1考慮線(xiàn)性規(guī)劃問(wèn)題maxz=2x+3xs．t．（1）若目標(biāo)函數(shù)中x的系數(shù)為4，約束方程中的系數(shù)為3，2，5，2，根據(jù)原問(wèn)題最優(yōu)解，試求新的最優(yōu)解；（2）若在（3）中的第二個(gè)約束方程中的系數(shù)為4，求最優(yōu)解。（1）x（2）x分別用圖解法和單純形法求解下列線(xiàn)性規(guī)劃，指出單純形法迭代的每一步的基可行解對(duì)應(yīng)于圖形上的那一個(gè)極點(diǎn)．圖解法單純形法：C(j)1300bRatioC(i)BasisX1X2X3X40X3-2[1]10220X42301124C(j)-Z(j)130003X2-21102M0X4[8]0-3160.75C(j)-Z(j)70-3063X2010.250.257/21X110-0.3750.1253/4C(j)-Z(j)00-0.375-0.87511.25對(duì)應(yīng)的頂點(diǎn)：基可行解可行域的頂點(diǎn)X(1)=（0，0，2，12）、X(2)=（0，2，0，6，）、X(3)=（、（0，0）（0，2）最優(yōu)解分別用圖解法和單純形法求解下列線(xiàn)性規(guī)劃，指出單純形法迭代的每一步的基可行解對(duì)應(yīng)于圖形上的那一個(gè)極點(diǎn)．圖解法單純形法：C(j)-3-5000bRatioBasisC(i)X1X2X3X4X5X301210063X401[4]010102.5X501100144C(j)-Z(j)-3-50000X30[0.5]01-0.5012X2-50.25100.2502.510X500.7500-0.2511.52C(j)-Z(j)-1.75001.250-12.5X1-3102-102MX2-501-0.50.5024X5000-1.5[0.5]100C(j)-Z(j)003.5-0.50-16X1-310-1022X2-50110-12X4000-3120C(j)-Z(j)00201-16對(duì)應(yīng)的頂點(diǎn)：基可行解可行域的頂點(diǎn)X(1)=（0，0，6，10，4）、X(2)=（0，2.5，1，0，1.5，）、X(3)=（2，2，0，0，0）X(4)=（2，2，0，0，0）（0，0）（0，2.5）(2，2)（2，2）最優(yōu)解：X=（2，2，0，0，0）；最優(yōu)值Z＝－16該題是退化基本可行解，5個(gè)基本可行解對(duì)應(yīng)4個(gè)極點(diǎn)。用單純形法求解下列線(xiàn)性規(guī)劃單純形表：C(j)34100R.H.S.RatioBasisC(i)X1X2X3X4X5X402[3]11011/3X501220133/2C(j)-Z(j)341000X24[2/3]11/31/301/31/2X50-1/304/3-2/317/3MC(j)-Z(j)1/30-1/3-4/30-4/3X1313/21/21/201/2X5001/23/2-1/215/2C(j)-Z(j)0-1/2-1/2-3/20-3/2最優(yōu)解：X=（1/2，0，0，0，5/2）；最優(yōu)值Z＝3/2用單純形法求解下列線(xiàn)性規(guī)劃單純形表：C(j)21-35000R.H.S.RatioBasisC(i)X1X2X3X4X5X6X7X50153-710030MX603-1[1]10101010X702-6-1[4]001205C(j)-Z(j)21-35000X509/2-11/25/40107/465MX605/2[1/2]5/4001-1/4510X451/2-3/2-1/41001/45MC(j)-Z(j)-1/217/2-7/4000-5/4X50320150111-1120MX21515/2002-1/21010X45807/2103-1/220MC(j)-Z(j)-430-2300-173因?yàn)棣?＝3>0并且ai7<0(i=1,2,3)，故原問(wèn)題具有無(wú)界解，即無(wú)最優(yōu)解。用單純形法求解下列線(xiàn)性規(guī)劃C(j)32-0.125000R.H.S.RatioBasisC(i)X1X2X3X4X5X6X40-1231004MX50[4]0-2010123X60384001103.3333C(j)-Z(j)32-0.1250000X40022.510.25073.5X1310-0.500.2503MX600[8]5.50-0.75110.125C(j)-Z(j)021.3750-0.7509X40001.12510.4375-0.256.756X1310-0.500.2503MX2201[0.6875]0-0.09380.1250.1250.181818C(j)-Z(j)0000-0.5625-0.259.25X3進(jìn)基、X2出基，得到另一個(gè)基本最優(yōu)解。C(j)32-0.125000R.H.S.RatioBasisX1X2X3X4X5X6X400-1.6010.5909-0.45456.54556X1310.73000.18180.09093.0909MX3-0.12501.4510-0.13640.18180.18180.1818C(j)-Z(j)0000-0.5625-0.259.25原問(wèn)題具有多重解。基本最優(yōu)解,最優(yōu)解的通解可表示為即用單純形法求解下列線(xiàn)性規(guī)劃單純形表：C(j)-2-1-41000R.H.S.RatioBasisC(i)X1X2X3X4X5X6X7X5012[1]-310088X600-1120101010X7027-5-1000120MC(j)-Z(j)-2-1-41000X3-4121-31008MX60-1-30[5]-11020.4X707170-2550160MC(j)-Z(j)270-11400X3-4[2/5]1/5102/53/5046/523X41-1/5-3/501-1/51/502/5MX7022000517035C(j)-Z(j)-1/52/5009/511/50X1-211/25/2013/2023X410-1/21/2101/205X7001-50-22124C(j)-Z(j)01/21/2025/20最優(yōu)解：X=（23，0，0，5，0，0，24）；最優(yōu)值Z＝－41用單純形法求解下列線(xiàn)性規(guī)劃單純形表：C(j)32100R.H.S.RatioBasisC(i)X1X2X3X4X5X4054610255X50[8]6301243C(j)-Z(j)321000X4000.254.1251-0.62510X1310.750.37500.1253C(j)-Z(j)0-0.25-0.1250-0.3759最優(yōu)解：X=（3，0，0，9，0）；最優(yōu)值Z＝9用單純形法求解下列線(xiàn)性規(guī)劃單純形表：C(j)56800R.H.S.RatioBasisC(i)X1X2X3X4X5X4013[2]105025X50143018026.6667C(j)-Z(j)568000X38[1/2]3/211/202550X50-1/2-1/20-3/215MC(j)-Z(j)1-60-40-200X151321050X50011-1130C(j)-Z(j)0-9-2-50-250最優(yōu)解：X=（50，0，0，0，0，30）；最優(yōu)值Z＝250已知某線(xiàn)性規(guī)劃的單純形表，求價(jià)值系數(shù)向量C及目標(biāo)函數(shù)值Z．Cjc1c2c3c4c5c6c7bCBXBx1x2x3x4x5x6x73x40121－30244x110－1020－100x60－140－4123/2λj0－1－1010－2由有c2＝－1＋（3×1＋4×0＋0×（－1））＝2c3＝－1＋（3×2＋4×（－1）＋0×4）＝1c5＝1＋（3×（－3）＋4×2＋0×（－4））＝0則λ＝(4,2,1,3,0,0,0,)，Z=CBXB=12已知線(xiàn)性規(guī)劃的最優(yōu)單純形表如表所示，求原線(xiàn)性規(guī)劃矩陣C、A、及b，最優(yōu)基B及．Cjc1c2c3c4c5bCBXBx1x2x3x4x5c1x11041/61/156c2x201－301/52λj00－1－2－3，c4＝c5＝0，求出c1＝12，c2＝11，c3＝14由得由得則有，已知線(xiàn)性規(guī)劃的單純形表．Cj－3a－1－1bCBXBx1x2x3x4－1x3－2210b1－1x43101b2λjλ1λ2λ3λ4當(dāng)=（）,=（）,a=（）時(shí)，為唯一最優(yōu)解.當(dāng)=（）,=（）,a=（）時(shí)，有多重解，此時(shí)λ＝（）(1)b1≥0,b2≥0,a<-3(2)b1≥0,b2≥0,a=－3,(-2,0,0,0)用單純形法求解線(xiàn)性規(guī)劃問(wèn)題maxz=3x+5xst.xxxxxx2x6x20010101001/31/2-1/3-1/301/3c000-3/2-1用單純形法求解線(xiàn)性規(guī)劃問(wèn)題maxz=2x-x+xst.xxxxxxx10x15x501000111/2-3/2100-11/2-1/2-21/21/2c00-3/20-3/2-1/2用單純形法求解線(xiàn)性規(guī)劃問(wèn)題maxz=6x+2x+10x+8xst.xxxxxxxx70x5x2011-5-601000112272121000-2-3c7600-66-22034用單純形法求解線(xiàn)性規(guī)劃問(wèn)題maxz=x+6x+4xst.xxxxxxx1/4x4x9/2001100010-1/81/2-1/4-1/81/61/123/8-1/65/12c000-10-2有無(wú)窮多最優(yōu)解.其中之一為x=11/2,x=9/4,x=7下表為用單純形法計(jì)算時(shí)的某一步的表格。已知該線(xiàn)性規(guī)劃的目標(biāo)函數(shù)為maxz=5x+3x，約束形式為≤,x,x為松弛變量,表中解代入目標(biāo)函數(shù)后得Z=10。xxxxx2xacd0e101/51cb-1fg求a~g的值；表中給出的解是否為最優(yōu)解。a=2，b=0，c=0，d=1，e=4/5，f=0，g=-5；表中給出的解為最優(yōu)解。下表為用單純形法計(jì)算時(shí)的某一步的表格。已知該線(xiàn)性規(guī)劃的目標(biāo)函數(shù)為maxz=28x+x+2x，約束形式為≤,x,x,x為松弛變量,表中解的目標(biāo)函數(shù)值為Z=14。xxxxxxx70x5x203600de-14/32f00115/20100cbc00-1g求a~g的值；表中給出的解是否為最優(yōu)解。a=7，b=-6，c=0，d=1，e=0，f=1/3，g=0；表中給出的解為最優(yōu)解。下表為某求極大值線(xiàn)性規(guī)劃問(wèn)題的初始單純形表及迭代后的表，x、x為松弛變量，試求表中a~l的值及各變量下標(biāo)m~t的值。xxxxxx6x1b-1c3de1001ca1-200xfx4gh2i-111/21/201c07jkla=-3，b=2，c=4，d=-2，e=2，f=1/3，g=1，h=0，i=5，j=-5，k=3/2，l=0；變量x的下標(biāo)為：m——4，n——5，s——1，t——6。11180105分別用大M法和兩階段法求解下列線(xiàn)性規(guī)劃：(1)大M法。數(shù)學(xué)模型為C(j)10-510-MR.H.S.RatioBasisC(i)X1X2X3X4X5X5-M53101102X40-51-101015MC(j)-Z(j)10-51000*BigM531000X11013/51/501/52X4004-91125C(j)-Z(j)0-11-10-220*BigM0000-10最優(yōu)解X＝(2,0,0)；Z=20兩階段法。第一階段：數(shù)學(xué)模型為C(j)00001R.H.S.RatioBasisC(i)X1X2X3X4X5X51[5]3101102X40-51-101015MC(j)-Z(j)-5-3-100X1013/51/501/52X4004-91125C(j)-Z(j)00001第二階段C(j)10-510R.H.S.RatioBasisC(i)X1X2X3X4X11013/51/5022X4004-9125MC(j)-Z(j)0-11-10最優(yōu)解X=(2,0,0)；Z=20用大M法求解下列線(xiàn)性規(guī)劃：大M法。數(shù)學(xué)模型為C(j)1015000-MR.H.S.RatioBasisC(i)X1X2X4X5X6X7X40[5]3100091.8X50-56010015MX7-M2100-1152.5C(j)-Z(j)101500000*BigM2100-100X11013/51/50009/5X5009110024X7-M0-1/5-2/50-117/5C(j)-Z(j)09-200018*BigM0-1/5-2/50-100因?yàn)閄7>0,原問(wèn)題無(wú)可行解。分別用大M法和兩階段法求解線(xiàn)性規(guī)劃問(wèn)題,并指出問(wèn)題的解屬于哪一類(lèi)maxz=4x+5x+xst.無(wú)可行解分別用大M法和兩階段法求解線(xiàn)性規(guī)劃問(wèn)題,并指出問(wèn)題的解屬于哪一類(lèi)maxz=2x+x+xst.有無(wú)窮多最優(yōu)解，例如X=（4，0，0），X=（0，0，8）用兩階段法求解以下線(xiàn)性規(guī)劃問(wèn)題解：將目標(biāo)函數(shù)轉(zhuǎn)化成極小化，引進(jìn)松弛變量x4，x5，x6≥0，得到minz’=-x1-3x2-4x3s.t.3x1+2x2+x4=13x2+3x3+x5=172x1+x2+x3=13x1,x2,x3,x4,x5,≥0引進(jìn)人工變量x60，構(gòu)造輔助問(wèn)題：minz’’=x6s.t.3x1+2x2+x4=13x2+3x3+x5=172x1+x2+x3+x6=13x1,x2,x3,x4,x5,x6≥0列出輔助問(wèn)題的系數(shù)矩陣表：z’’x1x2x3x4x5x6RHSz’’100000-10x4032010013x5001301017x6021100113消去基變量x6在目標(biāo)函數(shù)中的系數(shù)，并開(kāi)始單純形疊代：z’’x1x2x3x4x5x6RHSz’’121100013x40[3]201001313/3x5001301017--x602110011313/2x1進(jìn)基，x4離基，z’’x1x2x3x4x5x6RHSz’’10-1/31-2/30013/3x1012/301/30013/3--x500130101717/3x600-1/3[1]-2/30113/313/3x3進(jìn)基，x6離基，z’’x1x2x3x4x5x6RHSz’’100000-10x1012/301/30013/3x500202104x300-1/3[1]-2/30113/3輔助問(wèn)題已經(jīng)獲得最優(yōu)解，且minz’’=0，因而可以轉(zhuǎn)入第二階段，其系數(shù)矩陣表為：z’x1x2x3x4x5RHSz’1134000x1012/301/3013/3x50020214x300-1/31-2/3013/3消去基變量x1，x3在目標(biāo)函數(shù)中的系數(shù)：z’x1x2x3x4x5RHSz’1011/307/30-65/3x1012/301/3013/313/2x500[2]02144/2x300-1/31-2/3013/3--x2進(jìn)基，x5離基z’x1x2x3x4x5RHSz’1000-4/3-11/6-29x10100-1/3-1/33x2001021/22x30001-1/31/65得到原問(wèn)題的最優(yōu)解：（x1,x2,x3）=（3,2,5），minz’=-29，maxz=29用大M法和兩階段法求解。用大M法和兩階段法求解。用大M法和兩階段法求解。無(wú)可行解用大M法和兩階段法求解。用大M法和兩階段法求解。用兩階段法求解以下線(xiàn)性規(guī)劃問(wèn)題解：將問(wèn)題化為標(biāo)準(zhǔn)化形式：minz’=-2x1+x2-x3s.t.x1+x2-2x3+x4=84x1-x2+x3+x5=22x1+3x2-x3-x6=4x1,x2,x3,x4,x5,x6≥0引進(jìn)人工變量x7≥0，構(gòu)造輔助問(wèn)題：minz’’=x7s.t.x1+x2-2x3+x4=84x1-x2+x3+x5=22x1+3x2-x3-x6+x7=4x1,x2,x3,x4,x5,x6,x7≥0輔助問(wèn)題的系數(shù)矩陣為：z’’x1x2x3x4x5x6x7RHSz’’1000000-10x4011-210008x504-1101002x7023-100-114消去基變量x7在目標(biāo)函數(shù)中的系數(shù)z’’x1x2x3x4x5x6x7RHSz’’123-100-104x4011-2100088/1x504-1101002--x702[3]-100-1144/3x2進(jìn)基，x7離基，z’’x1x2x3x4x5x6x7RHSz’’1000000-10x401/30-5/3101/3-1/320/3x5014/302/301-1/3-1/310/3x202/31-1/300-1/31/34/3得到輔助問(wèn)題的最優(yōu)解，且minz’’=0，轉(zhuǎn)入第二階段。建立系數(shù)矩陣表：z’x1x2x3x4x5x6RHSz’12-110000x401/30-5/3101/320/3x5014/302/301-1/310/3x202/31-1/300-1/34/3消去基變量x2在目標(biāo)函數(shù)中的系數(shù)，得到z’x1x2x3x4x5x6RHSz’18/302/300-1/34/3x401/30-5/3101/320/3--x5014/30[2/3]01-1/310/310/2x202/31-1/300-1/34/3--x3進(jìn)基，x5離基z’x1x2x3x4x5x6RHSz’1-2000-10-2x40120015/2-1/215x3070103/2-1/25x2031001/2-1/23原問(wèn)題的最優(yōu)解為：（x1,x2,x3,x4,x5,x6）=（0,3,5,15,0,0），minz’=-2，maxz=2。用兩階段法求解以下線(xiàn)性規(guī)劃問(wèn)題引進(jìn)松弛變量x4，x5，x6≥0，得到minz=x1+3x2-x3s.t.x1+x2+x3-x4=3-x1+2x2-x5=2-x1+5x2+x3+x6=4x1,x2,x3,x4,x5,x6≥0引進(jìn)人工變量x7，x8≥0，構(gòu)造輔助問(wèn)題minz’=x7+x8s.t.x1+x2+x3-x4+x7=3-x1+2x2-x5+x8=2-x1+5x2+x3+x6=4x1,x2,x3,x4,x5,x6,x7,x80列出輔助問(wèn)題系數(shù)矩陣表z’x1x2x3x4x5x6x7x8RHSz’1000000-1-10x70111-100103x80-1200-10012x60-151001004消去基變量x7，x8在目標(biāo)函數(shù)中的系數(shù)，得到z’x1x2x3x4x5x6x7x8RHSz’1031-1-10005x7011[1]-1001033/1x80-1200-10012--x60-1510010044/1x3進(jìn)基，x6離基，z’x1x2x3x4x5x6x7x8RHSz’1-1200-10-102x30111-1001033/1x80-1200-100122/2x60-2[4]0101-1011/4x2進(jìn)基，x6離基z’x1x2x3x4x5x6x7x8RHSz’1000-1/2-1-1/2-1/203/2x103/200-5/40-1/45/4011/4x80000-1/2-1-1/21/213/2x30-1/2101/401/4-1/401/4得到輔助問(wèn)題的最優(yōu)解，但minz=3/2>0，因此原問(wèn)題無(wú)可行解。用大M法求解下面的線(xiàn)性規(guī)劃問(wèn)題引進(jìn)松弛變量x4，x50minz=2x1+3x2+x3s.t.4x1+x2-x3-x4＝16x1-2x2+x3-x5＝24x1,x2,x3,x4,x50引進(jìn)人工變量x6，x70，在目標(biāo)函數(shù)中增加人工變量minz=2x1+3x2+x3+Mx6+Mx7s.t.4x1+x2-x3-x4+x6＝16x1-2x2+x3-x5+x7＝24x1,x2,x3,x4,x5,x6,x70列出單純形表zX1x2x3x4x5x6x7RHSz1-2-3-100-M-M0X6041-1-101016X701-210-10124消去基變量x6、x7在目標(biāo)函數(shù)中的系數(shù)zx1x2x3X4x5x6x7RHSz15M-2-M-3-1-M-M0040MX60[4]1-1-101016X701-210-10124由于M是足夠大的正數(shù)，因此5M－2>0，x1進(jìn)基，x6離基zX1x2x3x4x5x6x7RHSz10-M-M-M--M-M+020M+8x1011/4-1/4-1/401/404x700-9/4[5/4]1/4-1-1/4120由于M+>0，x3進(jìn)基，x7離基zx1x2x3x4x5x6x7RHSz10-16/50-1/5-6/5-M+1/5-M-6/532x101-1/50-1/5-1/51/51/58x300-9/511/5-4/5-1/54/516由于-M+1/5<0，-M-6/5<0，已獲得最優(yōu)解，最優(yōu)解為：（x1，x2，x3，x4，x5，x6，x7）＝(8，0，16，0，0，0，0)，minz=32原問(wèn)題的解為：（x1，x2，x3，x4，x5）＝（8，0，16，0，0），minz=32分別用大M法和兩階段法求解線(xiàn)性規(guī)劃問(wèn)題,并指出問(wèn)題的解屬于哪一類(lèi)maxz=x+xst.有可行解,最優(yōu)解無(wú)界分別用大M法和兩階段法求解線(xiàn)性規(guī)劃問(wèn)題,并指出問(wèn)題的解屬于哪一類(lèi)maxz=x+2x+3x-xst.唯一最優(yōu)解X=(5/2,5/2,5/2,0)用兩階段法求解下列線(xiàn)性規(guī)劃：兩階段法第一階段：數(shù)學(xué)模型為C(j)000001R.H.S.RatioBasisC(i)X1X2X4X5X6X7X40[5]3100091.8X50-56010015MX712100-1152.5C(j)-Z(j)-2-10010514X1013/51/50009/5X5009110024X710-1/5-2/50-117/5C(j)-Z(j)01/52/5010因?yàn)閄7>0,原問(wèn)題無(wú)可行解。圖解法如下：用大M法求解下列線(xiàn)性規(guī)劃：【解】大M法。數(shù)學(xué)模型為C(j)23-11-M-M-MR.H.S.RatioBasisC(i)X1X2X3X4X5X6X7X8X9X10X11X9-M1-121-1194.5X621-1155X10-M2-1[3]-1-1110.3333X11-M11-1133C(j)-Z(j)23-11*BigM4-26-1-1-1X9-M-1/3-1/3[1.67]-12/31-2/38.335X6-2/32.33-2/311/3-1/34.67MX3-12/3-1/31-1/3-1/31/31/3MX11-M1/31/31/31/3-1-1/312.678C(j)-Z(j)2.672.672/3-1/31/3-1/3*BigM2-11-1-2X41-1/5-1/51-3/50.43/5-0.45MX6-0.82.2-0.413/50.4-3/583.6364X3-13/5-0.41-1/5-1/51/51/52MX11-M0.40.41/51/5-1-1/5-1/5112.5C(j)-Z(j)2.8[2.8]0.4-3/5-0.43/53*BigM0.40.41/51/5-1-1.2-1.2X411-0.50.5-0.50.5-0.50.55.5MX6-3-1.51-0.5[5.5]1.50.5-5.52.50.4545X3-111-113MX23110.50.5-2.5-0.5-0.52.52.5MC(j)-Z(j)-1-2712-710*BigM-1-1-1X41-0.271.00-0.640.090.450.64-0.455.73MX8-0.55-0.270.18-0.091.000.270.09-1.000.45MX3-1[0.45]1.00-0.270.18-0.090.270.093.457.6X23-0.361.00-0.180.450.270.18-0.273.64MC(j)-Z(j)3.820.91-1.27-1.36-0.911.3613.18*BigM-1-1-1X413/51-0.81/50.40.8-0.47.8MX81.2-3/50.4-1/513/51/5-14.6MX1212.2-3/50.4-1/53/51/57.6MX2310.8-0.43/51/50.4-1/56.4MC(j)-Z(j)-8.43.2-2.8-3/5-3.23/542.2*BigM-1-1-1無(wú)界解。用兩階段法求解下列線(xiàn)性規(guī)劃：兩階段法。第一階段：C(j)111R.H.S.RatioBasisC(i)X1X2X3X4X5X6X7X8X9X10X11X911-121-1199/2X621-1155X1012-1[3]-1-1111/3X11111-1133C(j)-Z(j)-42-611113X91-1/3-1/3[5/3]-12/31-2/325/35X6-2/37/3-2/311/3-1/314/3MX32/3-1/31-1/3-1/31/31/3MX1111/31/31/31/3-1-1/318/38C(j)-Z(j)-21-11211X4-1/5-1/51-3/52/53/5-2/55MX6-4/511/5-2/513/52/5-3/5840/11X33/5-2/51-1/5-1/51/51/52MX1112/5[2/5]1/51/5-1-1/5-1/5115/2C(j)-Z(j)-2/5-2/5-1/5-1/516/56/51X41-1/21/2-1/21/2-1/21/211/2MX6-3-3/21-1/211/23/21/2-11/25/25/11X311-113MX2111/21/2-5/2-1/2-1/25/25/2MC(j)-Z(j)111第二階段：C(j)23-11R.H.S.RatioBasisC(i)X1X2X3X4X5X6X7X8X411-1/21/2-1/211/2MX6-3-3/21-1/2[11/2]5/25/11X3-111-13MX23111/21/2-5/25/2MC(j)-Z(j)-1-2710X41-3/111-7/111/115/1163/11MX8-6/11-3/112/11-1/1115/11MX3-15/111-3/112/11-1/1138/1138/5X23-4/111-2/115/113/1140/11MC(j)-Z(j)42/111-14/11-15/1113.18X413/51-4/51/52/539/5MX86/5-3/52/5-1/5123/5MX12111/5-3/52/5-1/538/5MX2314/5-2/53/51/532/5MC(j)-Z(j)-42/516/5-14/5-3/542.2原問(wèn)題無(wú)界解。分別用大M法和兩階段法求解下列線(xiàn)性規(guī)劃：【解】大M法。數(shù)學(xué)模型為C(j)5-6-700MMR.H.S.RatioBasisC(i)X1X2X3S1S2A1A3A1M1[5]-3-1010153S205-610010020MA3M111000155C(j)-Z(j)5-6-70000*BigM-2-621000X2-61/51-3/5-1/501/503MS2031/5032/5-6/516/503895/16A3M4/50[8/5]1/50-1/5125/4C(j)-Z(j)31/50-53/5-6/506/50*BigM-4/50-8/5-1/506/50X2-61/210-1/801/83/815/4S20300-212-430X3-71/2011/80-1/85/85/4C(j)-Z(j)23/2001/80-1/853/8*BigM0000011兩階段法。第一階段：數(shù)學(xué)模型為C(j)0000011R.H.S.RatioBasisC(i)X1X2X3S1S2A1A3A1115-3-1010153S205-610010020MA31111000155C(j)-Z(j)-2-621000X201/51-3/5-1/501/503MS2031/5032/5-6/516/503895/16A314/50[8/5]1/50-1/5125/4C(j)-Z(j)-0.80-1.6-0.201.20X201/210-1/801/83/815/4S20300-212-430X301/2011/80-1/85/85/4C(j)-Z(j)0000011第二階段：C(j)5-6-700R.H.S.RatioBasisC(i)X1X2X3S1S2X2-61/210-1/8015/43S20300-2130MX3-71/2011/805/45C(j)-Z(j)23/2001/80最優(yōu)解：X=(0，3.75，1.25)；Z=－31.25即11180106設(shè)線(xiàn)性規(guī)劃取基分別指出對(duì)應(yīng)的基變量和非基變量，求出基本解，并說(shuō)明是不是可行基．B1：x1，x3為基變量，x2，x4為非基變量,基本解為X=（15，0，20，0）T，B1是可行基。B2：x1,x4是基變量，x2,x3為非基變量，基本解X=（25，0，0，－40）T，B2不是可行基設(shè)線(xiàn)性規(guī)劃對(duì)于基求所有變量的檢驗(yàn)數(shù),并判斷B是不是最優(yōu)基．,B不是最優(yōu)基，可以證明B是可行基。求出下列線(xiàn)性規(guī)劃問(wèn)題的所有最基本解和極點(diǎn)，并分析其是否退化，從中求出最優(yōu)解。maxz=x+x+xs．t．考慮下列線(xiàn)性規(guī)劃：MaxZ(x)=-5x1+5x2+13x3S.t.-x1+x2+3x3≤2012x1+4x2+10x3≤90x1,x2,x3≥0最優(yōu)單純形表為：XBb'X1X2X3X4X5X220-11310X510160-2-41-Z-10000250寫(xiě)出此線(xiàn)性規(guī)劃的最優(yōu)解、最優(yōu)基B和它的逆B-1；(1)x*=(0,20,0,0,10)Tz*=100已知線(xiàn)性規(guī)劃的最優(yōu)基為，試用矩陣公式求（1）最優(yōu)解；(2)單純形乘子；(3)(4)則(1)(2)(3)(4)注：該題有多重解：X(1)=(0，5，0，5/2)X(2)=(0，10/3，10/3，0)X(3)=(10，0，0，0)，x2是基變量，X(3)是退化基本可行解Z＝50已知某線(xiàn)性規(guī)劃問(wèn)題的約束條件為st.判斷下列各點(diǎn)是否為該線(xiàn)性規(guī)劃問(wèn)題可行域的凸集的頂點(diǎn):X=(5,15,0,20,0)X=(9,7,0,0,8)X=(15,5,10,0,0)該線(xiàn)性規(guī)劃問(wèn)題中p=p=p=p=p=因?yàn)?p+p+p=0,故不是凸集頂點(diǎn);(9,7,0,0,8)為非可行域的點(diǎn);因p,p,p線(xiàn)性相關(guān),故非凸集的頂點(diǎn).中應(yīng)用88已知下述線(xiàn)性規(guī)劃問(wèn)題具有無(wú)窮多最優(yōu)解,試寫(xiě)出其最優(yōu)解的一般表達(dá)式maxz=10x+5x+5xst.最優(yōu)解一般表達(dá)式為X=下述線(xiàn)形規(guī)劃問(wèn)題中，分別求目標(biāo)函數(shù)值z(mì)的上界和下界maxz=cx+cxst.式中：，，，，，，，，上界=21；下界=32/5下述線(xiàn)形規(guī)劃問(wèn)題中，分別求目標(biāo)函數(shù)值z(mì)的上界和下界maxz=cx-cxst.式中：，，，，，，，，上界=22.5；下界=4求出以下不等式組所定義的多面體的所有極點(diǎn)，其中B2、B4、B5、B7、B8、B10是可行基，相應(yīng)的基礎(chǔ)可行解為：X2= （x1，x2，x3，x4，x5）=（4/3，11/3，0，0，0）X4= （x1，x2，x3，x4，x5）=（5，0，0，0，11）X5= （x1，x2，x3，x4，x5）=（0，4，1，0，0）X7= （x1，x2，x3，x4，x5）=（0，5，0，0，1）X8= （x1，x2，x3，x4，x5）=（0，0，3，2，0）X10=（x1，x2，x3，x4，x5）=（0，0，0，5，6）原問(wèn)題的極點(diǎn)是：X2= （x1，x2，x3）=（4/3，11/3，0）X4= （x1，x2，x3）=（5，0，0）X5= （x1，x2，x3）=（0，4，1）X7= （x1，x2，x3）=（0，5，0）X8= （x1，x2，x3）=（0，0，3）X10=（x1，x2，x3）=（0，0，0）求出以下不等式組所定義的多面體的所有極點(diǎn)，答案：求解這個(gè)方程組，得到x4=1，x5=4；（x1,x2,x3,x4,x5）=（0,0,0,1,4）其中的基礎(chǔ)可行解有：（x1,x2,x3,x4,x5）=（1,0,0,0,5）（x1,x2,x3,x4,x5）=（0,1,0,0,2）（x1,x2,x3,x4,x5）=（0,0,1,0,4）（x1,x2,x3,x4,x5）=（0,0,0,1,4）原問(wèn)題的極點(diǎn)是：（x1,x2,x3）=（1,0,0）（x1,x2,x3）=（0,1,0）（x1,x2,x3）=（0,0,1）（x1,x2,x3）=（0,0,0）在以下問(wèn)題中，列出所有的基，指出其中的可行基，基礎(chǔ)可行解以及最優(yōu)解。（1）B1不是可行基，不是基礎(chǔ)可行解。（2）B2是可行基，是基礎(chǔ)可行解，目標(biāo)函數(shù)值為：（3）B3是基礎(chǔ)可行解，是基礎(chǔ)可行解，目標(biāo)函數(shù)值為：（4）B4不是可行基，不是基礎(chǔ)可行解。（5）B5是可行基，是基礎(chǔ)可行解，目標(biāo)函數(shù)值為：（6）B6是可行基，是基礎(chǔ)可行解，目標(biāo)函數(shù)值為：（7）B7不是可行基，不是基礎(chǔ)可行解。（8）B8不是可行基，不是基礎(chǔ)可行解。（9）B9是可行基，是基礎(chǔ)可行解，目標(biāo)函數(shù)值為：(10)B10是基礎(chǔ)可行解，目標(biāo)函數(shù)值為：在可行基B2、B3、B5、B6、B9、B10中，最優(yōu)基為B2，最優(yōu)解為：26/3是基礎(chǔ)可行解，目標(biāo)函數(shù)值為：難應(yīng)用101211180107建筑公司需要用6m長(zhǎng)的塑鋼材料制作A、B兩種型號(hào)的窗架．兩種窗架所需材料規(guī)格及數(shù)量如表所示：表窗架所需材料規(guī)格及數(shù)量型號(hào)A型號(hào)B每套窗架需要材料長(zhǎng)度（m）數(shù)量(根)長(zhǎng)度(m)數(shù)量(根)A1：1.72B1：2.72A2：1.33B1：2.03需要量（套）200150問(wèn)怎樣下料使得用料最少第一步：求下料方案，見(jiàn)下表。方案一二三四五六七八九十十一十二十三十四需要量B1:2.7m21110000000000300B2:2m01003221110000450A1:1.7m00100102103210400A2:101120010130234600余料0.600.30.700.30.70.610.10.900.40.8第二步：建立線(xiàn)性規(guī)劃數(shù)學(xué)模型設(shè)xj（j=1,2,…，14）為第j種方案使用原材料的根數(shù)，則（1）用料最少數(shù)學(xué)模型為用單純形法求解得到兩個(gè)基本最優(yōu)解X(1)=(50,200,0,0,84,0,0,0,0,0,0,200,0,0);Z=534X(2)=(0,200,100,0,84,0,0,0,0,0,0,150,0,0);Z=534中運(yùn)用108建筑公司需要用6m長(zhǎng)的塑鋼材料制作A、B兩種型號(hào)的窗架．兩種窗架所需材料規(guī)格及數(shù)量如表所示：表窗架所需材料規(guī)格及數(shù)量型號(hào)A型號(hào)B每套窗架需要材料長(zhǎng)度（m）數(shù)量(根)長(zhǎng)度(m)數(shù)量(根)A1：1.72B1：2.72A2：1.33B1：2.03需要量（套）200150問(wèn)怎樣下料使得余料最少。第一步：求下料方案，見(jiàn)下表。方案一二三四五六七八九十十一十二十三十四需要量B1:2.7m21110000000000300B2:2m01003221110000450A1:1.7m00100102103210400A2:1.3m01120010130234600余料0.600.30.700.30.70.610.10.900.40.8第二步：建立線(xiàn)性規(guī)劃數(shù)學(xué)模型設(shè)xj（j=1,2,…，14）為第j種方案使用原材料的根數(shù)，則余料最少數(shù)學(xué)模型為用單純形法求解得到兩個(gè)基本最優(yōu)解X(1)=(0,300,0,0,50,0,0,0,0,0,0,200,0,0);Z=0，用料550根X(2)=(0,450,0,0,0,0,0,0,0,0,0,200,0,0);Z=0，用料650根顯然用料最少的方案最優(yōu)。某投資人現(xiàn)有下列四種投資機(jī)會(huì),三年內(nèi)每年年初都有3萬(wàn)元（不計(jì)利息）可供投資：方案一：在三年內(nèi)投資人應(yīng)在每年年初投資，一年結(jié)算一次，年收益率是20％，下一年可繼續(xù)將本息投入獲利；方案二：在三年內(nèi)投資人應(yīng)在第一年年初投資，兩年結(jié)算一次，收益率是50％，下一年可繼續(xù)將本息投入獲利，這種投資最多不超過(guò)2萬(wàn)元；方案三：在三年內(nèi)投資人應(yīng)在第二年年初投資，兩年結(jié)算一次，收益率是60％，這種投資最多不超過(guò)1.5萬(wàn)元；方案四：在三年內(nèi)投資人應(yīng)在第三年年初投資，一年結(jié)算一次，年收益率是30％，這種投資最多不超過(guò)1萬(wàn)元．投資人應(yīng)采用怎樣的投資決策使三年的總收益最大，建立數(shù)學(xué)模型.是設(shè)xij為第i年投入第j項(xiàng)目的資金數(shù)，變量表如下項(xiàng)目一項(xiàng)目二項(xiàng)目三項(xiàng)目四第1年第2年第3年x11x21x31x12x23x34數(shù)學(xué)模型為最優(yōu)解X=(30000，0，66000，0，109200，0)；Z＝84720IV發(fā)展公司是商務(wù)房地產(chǎn)開(kāi)發(fā)項(xiàng)目的投資商．公司有機(jī)會(huì)在三個(gè)建設(shè)項(xiàng)目中投資：高層辦公樓、賓館及購(gòu)物中心，各項(xiàng)目不同年份所需資金和凈現(xiàn)值見(jiàn)表．三個(gè)項(xiàng)目的投資方案是：投資公司現(xiàn)在預(yù)付項(xiàng)目所需資金的百分比數(shù)，那么以后三年每年必須按此比例追加項(xiàng)目所需資金，也獲得同樣比例的凈現(xiàn)值．例如，公司按10％投資項(xiàng)目1，現(xiàn)在必須支付400萬(wàn)，今后三年分別投入600萬(wàn)、900萬(wàn)和100萬(wàn)，獲得凈現(xiàn)值450萬(wàn)．公司目前和預(yù)計(jì)今后三年可用于三個(gè)項(xiàng)目的投資金額是：現(xiàn)有2500萬(wàn)，一年后2000萬(wàn)，兩年后2000萬(wàn)，三年后1500萬(wàn)．當(dāng)年沒(méi)有用完的資金可以轉(zhuǎn)入下一年繼續(xù)使用．IV公司管理層希望設(shè)計(jì)一個(gè)組合投資方案，在每個(gè)項(xiàng)目中投資多少百分比，使其投資獲得的凈現(xiàn)值最大．年份10％項(xiàng)目所需資金（萬(wàn)元）項(xiàng)目1項(xiàng)目2項(xiàng)目30400800900160080050029008002003100700600凈現(xiàn)值450700500以1％為單位，計(jì)算累計(jì)投資比例和可用累計(jì)投資額，見(jiàn)表年份每種活動(dòng)單位資源使用量（每個(gè)百分點(diǎn)投資的累計(jì)數(shù)）項(xiàng)目1項(xiàng)目2項(xiàng)目3累計(jì)可用資金(萬(wàn)元)04080902500110016014045002190240160650032003102208000凈現(xiàn)值457050設(shè)xj為j項(xiàng)目投資比例，則數(shù)學(xué)模型：最優(yōu)解X＝（0，16.5049，13.1067）；Z=1810.68萬(wàn)元年份實(shí)際投資項(xiàng)目1比例：0項(xiàng)目2比例：16.5049項(xiàng)目3比例：13.1067累計(jì)投資(萬(wàn)元)001320.3921179.6032499.995102640.7841834.9384475.722203961.1762097.0726058.248305116.5192883.4747999.993凈現(xiàn)值01155.343655.335某煉油廠根據(jù)計(jì)劃每季度需供應(yīng)合同單位汽油15萬(wàn)t(噸)、煤油12萬(wàn)t、重油12萬(wàn)t。該廠從A,B兩處運(yùn)回原油提煉，已知兩處原油成分如表1—1所示。又如從A處采購(gòu)原油每t價(jià)格（包括運(yùn)費(fèi)、下同）為200元，B處原油每t價(jià)格為310元。試求：（a）選擇該煉油廠采購(gòu)原油的最優(yōu)決策；（b）如A處價(jià)格不變，B處降為290元/t,則最優(yōu)決策有何變化？A/%B/%含汽油含煤油含重油其他152050155030155每季度從A處采購(gòu)27.27萬(wàn)噸,從B處采購(gòu)21.82萬(wàn)噸,總費(fèi)用12218.2萬(wàn)元;改為每季度從A處采購(gòu)15萬(wàn)噸,從B處采購(gòu)30萬(wàn)噸,總費(fèi)用11700萬(wàn)元.某醫(yī)院晝24h各時(shí)段內(nèi)需要的護(hù)士數(shù)量如下：2∶00~6∶0010人，6∶00~10∶0015人，10∶00~14∶0025人，14∶00~18∶0020人，18∶00~22∶0018人，22∶00~2∶0012人。護(hù)士分別于2∶00，6∶00，10∶00，14∶00，18∶00，22∶00分6批上班，并連續(xù)工作8h。試確定：該醫(yī)院至少應(yīng)設(shè)多少名護(hù)士，才能滿(mǎn)足值班需要；總計(jì)需53名護(hù)士某人有一筆30萬(wàn)元的資金，在今后三年有以下投資項(xiàng)目：三年內(nèi)的每年年初