《運(yùn)籌學(xué)》題庫

1、 運(yùn)籌學(xué)習(xí)題庫數(shù)學(xué)建模題（5）1、某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需要A、B、C三種資源，每種產(chǎn)品的資源消耗量及單位產(chǎn)品銷售后所能獲得的利潤值以及這三種資源的儲(chǔ)備如下表所示：ABC甲94370乙4610120360200300試建立使得該廠能獲得最大利潤的生產(chǎn)計(jì)劃的線性規(guī)劃模型，不求解。解：設(shè)甲、乙產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為xl、x2，則xl、x220,設(shè)z是產(chǎn)品售后的總利潤，則maxz=70 x1+120 x2s.t.9x+4x360124x+6x20012x+10 x0122、某公司生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)所需原材料、工時(shí)和零件等有關(guān)數(shù)據(jù)如下：甲乙可用量原材料（噸/件）223000噸工時(shí)（工時(shí)

2、/件）52.54000工時(shí)零件（套/件）1500套產(chǎn)品利潤（元/件）43建立使利潤最大的生產(chǎn)計(jì)劃的數(shù)學(xué)模型，不求解。解：設(shè)甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量為x、X，12設(shè)Z為產(chǎn)品售后總利潤，則maxz=4x+3x12s.t.2x+2x3000125x+2.5x400012x0123、一家工廠制造甲、乙、丙三種產(chǎn)品，需要三種資源技術(shù)服務(wù)、勞動(dòng)力和行政管理。每種產(chǎn)品的資源消耗量、單位產(chǎn)品銷售后所能獲得的利潤值以及這三種資源的儲(chǔ)備量如下表所示：技術(shù)服務(wù)勞動(dòng)力行政管理單位利潤1010資源儲(chǔ)備量|100600300建立使得該廠能獲得最大利潤的生產(chǎn)計(jì)劃的線性規(guī)劃模型，不求解。解：建立線性規(guī)劃數(shù)學(xué)模型：設(shè)甲、乙、丙

3、三種產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為x、x、x，則x、x、x0,設(shè)z是產(chǎn)品售后的TOC o 1-5 h z123123總利潤，貝ymaxz=10 x+6x+4x123Stx+x+x10012310 x+4x+5x600彳1232x+2x+6x0J1234、一個(gè)登山隊(duì)員，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相器材、通信器材等。每種物品的重量合重要性系數(shù)如表所示。設(shè)登山隊(duì)員可攜帶的最大重量為25kg,試選擇該隊(duì)員所應(yīng)攜帶的物品。序號(hào)1234567物品食品氧氣冰鎬繩索帳篷照相器材通信設(shè)備重量/Kg55261224重要性系數(shù)201518148410試建立隊(duì)員所能攜帶物品最大量的線性規(guī)劃模型，不求解。

4、解：引入01變量x,x=1表示應(yīng)攜帶物品i,x=0表示不應(yīng)攜帶物品ITOC o 1-5 h ziiinaxz=20 x+15x+18x+14x+8x+4x+10 x2345675x+5x+2x+6x+12x+2x+4x251、234567x=0或1,i=1,2,.,7i5、工廠每月生產(chǎn)A、B、C三種產(chǎn)品，單件產(chǎn)品的原材料消耗量、設(shè)備臺(tái)時(shí)的消耗量、資源限量及單件產(chǎn)品利潤如下圖所示：I資、品源ABC資源限量材料（kg）1.51.242500設(shè)備（臺(tái)時(shí)）31.61.21400利潤（元/件）101412根據(jù)市場需求，預(yù)測三種產(chǎn)品最低月需求量分別是150、260、120,最高需求量是250、310、13

5、0,試建立該問題數(shù)學(xué)模型，使每月利潤最大，為求解。TOC o 1-5 h z解：設(shè)每月生產(chǎn)A、B、C數(shù)量為x,x,x。123MaxZ=10 x+14x+12x123廠1.5x+1.2x+4x25001233x+1.6x+1.2x1400123150 x2501260 x3102120 x01236、A、B兩種產(chǎn)品，都需要經(jīng)過前后兩道工序，每一個(gè)單位產(chǎn)品A需要前道工序1小時(shí)和后道工序2小時(shí)，每單位產(chǎn)品B需要前道工序2小時(shí)和后道工序3小時(shí)?？晒├玫那暗拦ば蛴?1小時(shí)，后道工序有17小時(shí)。每加工一個(gè)單位產(chǎn)品B的同時(shí)，會(huì)產(chǎn)生兩個(gè)單位的副產(chǎn)品C，且不需要任何費(fèi)用，產(chǎn)品C一部分可出售盈利，其余只能加以銷

6、毀。出售A、B、C的利潤分別為3、7、2元，每單位產(chǎn)品C的銷毀費(fèi)用為1元。預(yù)測表明，產(chǎn)品C最多只能售出13個(gè)單位。試建立總利潤最大的生產(chǎn)計(jì)劃數(shù)學(xué)模型，不求解。解：設(shè)每月生產(chǎn)A、B數(shù)量為x,x,銷毀的產(chǎn)品C為x。23MaxZ=3x+7x+2（2x一x）一x12233廠x+2x11122x+3x17122x一x01237、靠近某河流有兩個(gè)化工廠（參見附圖），流經(jīng)第一化工廠的河流流量為每天500m3，在兩個(gè)工廠之間有一條流量為200萬m3的支流。第一化工廠每天排放有某種優(yōu)化物質(zhì)的工業(yè)污水2萬m3，第二化工廠每天排放該污水1.4萬m3。從第一化工廠的出來的污水在流至第二化工廠的過程中，有20%可自然凈

7、化。根據(jù)環(huán)保要求，河流中的污水含量不應(yīng)大于0.2%。這兩個(gè)工廠的都需要各自處理一部分工業(yè)污水。第一化工廠的處理成本是1000元/萬m3，第二化工廠的為800元/萬m3。現(xiàn)在要問滿足環(huán)保的條件下，每廠各應(yīng)處理多少工業(yè)污水，才能使兩個(gè)工廠的總的污水處理費(fèi)用最少？列出數(shù)學(xué)模型，不求解。500萬m3200萬m3解：設(shè)第一化工廠和第二化工廠的污水處理量分別為每天X1m3和x2萬m3,minZ二1000 x+800 x120.8x+x1.612x80123x+x+2x65S.t.701321x+7x+35x450123x,x,x01239、某公司生產(chǎn)的產(chǎn)品A，B，C和D都要經(jīng)過下列工序：刨、立銑、鉆孔和裝

8、配。已知每單位產(chǎn)品所需工時(shí)及本月四道工序可用生產(chǎn)時(shí)間如下表所示：刨立銑鉆孔裝配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生產(chǎn)時(shí)間（小時(shí)）1800280030006000又知四種產(chǎn)品對利潤貢獻(xiàn)及本月最少銷售需要單位如下：產(chǎn)品最少銷售需要單位元/單位A1002B6003C5001D4004問該公司該如何安排生產(chǎn)使利潤收入為最大？（只需建立模型）解：設(shè)生產(chǎn)四種產(chǎn)品分別x1,x2,x3,x4單位則應(yīng)滿足的目標(biāo)函數(shù)為：maxz=2x1+3x2+x3+x4滿足的約束條件為：0.5x+x+x+0.5x1800TOC o 1-5 h z12

9、342x+x+x+x280012340.5x+0.5x+x+x300012343x+x+2x+3x60001001x6002x5003x400410、某航空公司擁有10架大型客機(jī)、15架中型客機(jī)和2架小型客機(jī)，現(xiàn)要安排從一機(jī)場到4城市的航行計(jì)劃，有關(guān)數(shù)據(jù)如表1-5，要求每天到D城有2個(gè)航次（往返），到A,B,C城市各4個(gè)航次（往返），每架飛機(jī)每天只能完成一個(gè)航次，且飛行時(shí)間最多為18小時(shí)，求利潤最大的航班計(jì)劃?？蜋C(jī)類型到達(dá)城市飛行費(fèi)用（元/次）飛行收入（元/次）飛行時(shí)間（h/d）大型A6000700080001000050007000100001800012510BCD中型A100020004

10、00030004000600024820BCD小型A20003500600040005500800012619BCD解：設(shè)大型客機(jī)飛往A城的架次為x1A，中型客機(jī)飛往A城的架次為x2A，小型客機(jī)飛往A城的架次為x3A，其余依此類推。資源限制派出的大型客機(jī)架次不能超過10架，表示為x+x+x+x10TOC o 1-5 h z1A1B1C1D同理x+x+x152A2B2Cx+x+x0且為整數(shù)；（i=l,2,3;j=A,B,C,D）ij目標(biāo)函數(shù)為maxz=1000 x+0 x+2000 x+8000 x+2000 x+1A1B1C1D2A2000 x+2000 x+2000 x+2000 x+200

11、0 x2B2C3A3B3C11、CRISP公司制造四種類型的小型飛機(jī)：AR1型（具有一個(gè)座位的飛機(jī)）、AR2型（具有兩個(gè)座位的飛機(jī)）、AR4型（具有四個(gè)座位的飛機(jī)）以及AR6型（具有六個(gè)座位的飛機(jī)）。AR1和AR2一般由私人飛行員購買，而AR4和AR6一般由公司購買，以便加強(qiáng)公司的飛行編隊(duì)。為了提高安全性，聯(lián)邦航空局（F.A.A）對小型飛機(jī)的制造做出了許多規(guī)定。一般的聯(lián)邦航空局制造規(guī)章和檢測是基于一個(gè)月進(jìn)度表進(jìn)行的，因此小型飛機(jī)的制造是以月為單位進(jìn)行的。表說明了CRISP公司的有關(guān)飛機(jī)制造的重要信息。AR1AR2AR4AR6聯(lián)邦航空局的最大產(chǎn)量（每月生產(chǎn)的飛機(jī)數(shù)目）8171115建造飛機(jī)所需要

12、的時(shí)間（天）47911每架飛機(jī)所需要的生產(chǎn)經(jīng)理數(shù)目1122每架飛機(jī)的盈利貢獻(xiàn)（千美元）6284103125CRISP公司下個(gè)月可以得到的生產(chǎn)經(jīng)理的總數(shù)是60人。該公司的飛機(jī)制造設(shè)施可以同時(shí)在任何給定的時(shí)間生產(chǎn)多達(dá)9架飛機(jī)。因此，下一個(gè)月可以得到的制造天數(shù)是270天（9*30，每月按30天計(jì)算）。JonathanKuring是該公司飛機(jī)制造管理的主任，他想要確定下個(gè)月的生產(chǎn)計(jì)劃安排，以便使盈利貢獻(xiàn)最大化。解：設(shè)x表示下個(gè)月生產(chǎn)AR1型飛機(jī)的數(shù)目，x表示AR2型，x表示AR4型，x表示1234AR6型目標(biāo)函數(shù)：maxz=62x+84x+103x+125x12344x+7x+9x+llx270123

13、4x+x+2x+2x601234x81約束條件：x172x113x01234x,x,x,x為整數(shù)123412、永輝食品廠在第一車間用1單位原料N可加工3單位產(chǎn)品A及2單位產(chǎn)品B,產(chǎn)品A可以按單位售價(jià)8元出售，也可以在第二車間繼續(xù)加工，單位生產(chǎn)費(fèi)用要增加6元，加工后單位售價(jià)增加9元。產(chǎn)品B可以按單位售價(jià)7元出售，也可以在第三車間繼續(xù)加工，單位生產(chǎn)費(fèi)用要增加4元，加工后單位售價(jià)可增加6元。原料N的單位購入價(jià)為2元，上述生產(chǎn)費(fèi)用不包括工資在內(nèi)。3個(gè)車間每月最多有20萬工時(shí)，每工時(shí)工資0.5元，每加工1單位N需要1.5工時(shí)，若A繼續(xù)加工，每單位需3工時(shí)，如B繼續(xù)加工，每單位需2工時(shí)。原料N每月最多能得

14、到10萬單位。問如何安排生產(chǎn)，使工廠獲利最大？解：設(shè)x為產(chǎn)品A的售出量；x為A在第二車間加工后的售出量；x表示產(chǎn)品B的售出123量;x4表示B在第三車間加工后的售出量；x5為第一車間所用原材料的數(shù)量,則目標(biāo)函數(shù)為：maxz=8x+9.5x+7x+8x一2.75xTOC o 1-5 h z12345x10000053x+2x+1.5x20000045約束條件：012345化標(biāo)準(zhǔn)形式（5）1、將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式解：minz=x-2x+3x123x+x+x21233x+x+2x=5123x0 x0 x無約束v123maxz=-x+2x-3(x-x)+0-x+0-xx+1x21+2x445

15、67x+x=756xx+xxx=2124573xx2x=5123x0172、將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式minz=x+2x+3x123二2x+x+x421234x2x3x=6123x0 x無約束v123解：2x+x+xx+x=9123343x+x+2x2x一x=4123354x+2x+3x3x61233x0J15maxz=x-2x一3x+3x12333、將下列線性規(guī)劃變?yōu)樽畲笾禈?biāo)準(zhǔn)形。minz=-3x+4x-2x+5x12344xx+2xx=2TOC o 1-5 h z1234x+x+3xx14st0,x無約束1234解：maxz=3x一4x+2x一5x+5xTOC o 1-5 h z123

16、44一4x+x一2x+x一x=212344x+x+3x一x+x+x=14stI123445一2x+3x一x+2x一2x一x=2123446x,x,x,x,x,xx0123445,6圖解法(5)1、用圖解法求解下面線性規(guī)劃minz=3x+2x122x+4x2212x+4x10122x一x712x一3x012解：可行解域?yàn)閍bcda,最優(yōu)解為b點(diǎn)?！?兀+4x=22Q12由方程組x=0解出X=ll,x2=02x.X*二1=(11,0)T丿2.minz=3X11+2X0=332、用圖解法求解下面線性規(guī)劃minz=2X+X12一x+4x82125x02解：從上圖分析，可行解域?yàn)閍bcde，最優(yōu)解為e點(diǎn)

17、。由方程組x+x=812X=5解出X=5,x2=31X.X*二X=（5,3）t丿2.minz=Z*=2X5+3=133、已知線性規(guī)劃問題如下：MaxZ=x+3x12f5x+10 xi50 x012x15x+10 x=5012由圖可知：5x+10 x12二50解之得：X=2x二42則maxZ=2+3*4=144、用圖解法求解下面線性規(guī)劃問題maxz二2x+x12”5x15i6x+2x24St.12x+x012解：5、用圖解法求解下面線性規(guī)劃問題maxz二2x+3x12x+2x812x16s.t14x0,j二1,2j值為z*二2*4+3*2二14。二、單純型法（15）1、用單純型法求解下面線性規(guī)劃

18、問題的解maxz=3x+3x2+4x33x+4x+5x40TOC o 1-5 h z123v6x+4x+3x0123解：加入松弛變量x,x,得到等效的標(biāo)準(zhǔn)模型:45maxz=3x1+3x2+4x3+0 x+0 x3x+4x+5x+x二4012340,j二1,2,.,5j列表計(jì)算如下：CBXBb3x13x24x30 x40 x59L0 x44034(5)1080 x566643012200000334t004x383/54/511/5040/30 x542(21/5)8/503/511012/516/544/503/5t1/504/504x3204/712/71/73x11018/2101/75

19、/21324/745/71/73803/705/71/7X*=(10,0,2,0,0)t.maxz=3X10+4X2=382、用單純型法求解下面線性規(guī)劃問題的解maxz=70 x+120 x12”9x+4x360124x+6x20012s.t.3x+10 x012解：加入松弛變量X,x,x，得到等效的標(biāo)準(zhǔn)模型:345maxz=70 x1+120 x2+0 x3+0 x4+0 x5s.t.=360=200=3009x+4x+xTOC o 1-5 h z1234x+6x+x1243x+10 x+x125x0,j=1,2,.j5j列表計(jì)算如下：70120000CBXBbx1x2x3x4x59L0 x

20、336094100900 x420046010100/30 x53003(10)001300000070120t0000 x324039/5010-2/5400/130 x420(11/5)001-3/5100/11120 x2303/101001/1010036120001234t000-120 x31860/11001-39/1119/1170 x1100/111005/11-3/11120 x2300/110103/222/1143000701200170/1130/1111000-170/11-30/111003001860 x*(，-,0,0)T11111110030043000-m

21、axz=70Xit+120rr=f3、用單純型法求解下面線性規(guī)劃問題的解2x+2x3000125x+2.5x4000maxz=4x+3xS.t.V1212x02解：加入松弛變量X,3x4，X，得到等效的標(biāo)準(zhǔn)形式:5maxz=4x+3x+012x+03x+0XS.t.V42x+2x+x1235x+2.5x+x二4000124x+x二50015x0,j二1,2,.,5j二3000用表解形式的單純形法求解，列表計(jì)算如下：CBXBbx3x4x53000400050043000 xxxxx123452210052.5010(1)0001000004f30009L3000/2=15004000/5=800

22、500/1=5000 x30 x4200015004x500i0210-20(2.5)01-5100014000403f00-42000/2=10001500/2.5=600 x3x2x180060050040014001004600001400014001-0.8(2)100.4-2301.2-200-1.22f0.5-0.4111-0.400-0.50.40310.400-1-0.40據(jù)上表，X*=(100,1400,0,0,400)Tmaxz=4X100+3X1400=4604、用單純型法求解下面線性規(guī)劃問題的解maxz=10 x+6x+4x123s.t.800/2=400500/1=5

23、00 x+x+x10012310 x+4x+5x6001232x+2x+6x0123得到等效的標(biāo)準(zhǔn)模型：解：加入松弛變量X,X,X,456maxz=10 x+6x+4x+0 x+0 x+0 x12x+x+x+x123410 x+4x+5x1232x+2x+6x123x0,j=1,2,.,656=100=600Vs.t.+x6=300100 x*=(丁,200丁,0,0,0,100)Tj列表計(jì)算如下：1064000CBXBbx1x2x3x4x5x69L0 x41001111001000 x5600(10)45010600 x630022600115000000010f640000 x4400(3

24、/5)1/21-1/100200/310 x16012/51/201/1001500 x618006/550-1/51150104501002f-10-106x2200/3015/65/3-1/6010 x1100/3101/6-2/31/600 x6100004-201220010620/310/32/30300-8/3-10/3-2/301002002200/.maxz=10Xr+6X5、用單純型法求解下面線性規(guī)劃問題的解MaxZ=4x-2x+2x1233x+x+x60TOC o 1-5 h z123x一x+2x101232x+2x一2x0123用單純形法求解，并指出問題的解屬于哪一類解：

25、（1）、將原問題劃為標(biāo)準(zhǔn)形得：MaxZ=4x一2x+2x+0 x+0 x+0 x123456廣3x+x+x+x=601234x一x+2x+x=1012352x+2x一2x+x=401236.x,x,x,x,x,x0123456Cj4-22000CBXBbx1x2x3x4x5x60 x4603111000 x5101-120100 x6402-22001j4-22000Cj4-22000CBXBbx1x2x3x4x5x60 x43004-51-304x1101-120100 x62004-60-21oj02-60-40Cj4-22000CBXBbx1x2x3x4x5x60 x4100011-1-

26、14x115101/201/21/4-2x2501-3/20-1/21/4oj00-30-3-1/2所以X=(15,5,0,10,0,0)T為唯一最優(yōu)解MaxZ=4*15-2*5=506、用單純形法求解下述LP問題。maxz二2.5x+x123x+5x1512s.t5x+2x012解：引入松弛變量x3、x4,化為標(biāo)準(zhǔn)形式:maxz二2.5x+x123x+5x+x二15123s.t25x+2x+x二101234構(gòu)造單純形表,計(jì)算如下：cj2.5cXEbx0 x1530 x105oj2.50 x3901009xxx5105201210019/513/545/192.5x1212/501/55j00

27、01/21x45/19015/193/192.5x20/19102/195/19j0001/2由單純形表，可得兩個(gè)最優(yōu)解X二(2,0,9,0)T、X二(20/19,45/19,0,0)T，所以兩點(diǎn)之間的所有解都是最優(yōu)解，即最優(yōu)解集合為：aX+(1-a)X，其中0a1。7、用單純形法解線性規(guī)劃問題maxz=2x+x15x22156x+2x2412x+x0 x012解：化為標(biāo)準(zhǔn)型maxz=2x+x+0 x+0 x+0 x123455x+x=15236x+2x+x=24124x+x+x=5125x01-5列出單純形表c.21000cXbxx2x3xxox31505100ox424620104ox51

28、10015-Z021000ox3150510032x1411/301/60120 x5102/30-1/613/2-Z-801/30-1/300X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2-Z-20000-1/4-1/2Z*=17/2,X*=(7/2,3/2,15/2,0,0)8、用單純型法求解下面線性規(guī)劃問題的解解:maxz=x+x12x2x2122x+x2i2x+x0 x012c.11000CBXBbX1X2X3X4X50X3211210020X42-210100X54-11001-Z0110001X121-21000X460-3210

29、0X560-1101-Z-203-100把表格還原為線性方程maxz=3xx+223x2x+x=2123V3x+2x+x=6234x+x+x=6V235x=2+2x-x123Vx=6+3x2x423x=6+x-x523令X=03x=2+2x12Vx=6+3x42x=6+x52此時(shí)，若讓X2進(jìn)基，則會(huì)和基變量Xi同時(shí)增加，使目標(biāo)函數(shù)值無限增長，所以本題無界9、用單純型法求解下面線性規(guī)劃問題的解maxz=2x+4x12x+2x812x41x0 x0I12c.24000cBXBbx1x2x3x4x50 x381210040 x44100100 x53010013-Z0240000 x321010-2

30、20 x441001044x2301001-Z-122000-42x121010-20 x4200-1124x2301001-Z-2000-2002x14100100 x5100-1/21/214x2011/2-1/20Z*=20,X*=(2,3,0,2,0)Z*=20,X*=(4,2,0,0,1)10、用單純型法求解下面線性規(guī)劃問題的解maxz=3x+15x2x141V2x2123x+2x0 x012解：列表如下C.35000cBXBbx1x2x3x4x50 x34101000 x4120201060 x518320019-Z0350000 x341010045x260101/200 x56

31、300-113 123 -Z-30300-5/200 x360011/3-1/35x220101/203x12100-1/31/3-Z-20000-3/2-1X*=(2,6,6,0,0)Z*=3611、用單純型法求解下面線性規(guī)劃問題的解maxz二2x+x12”5x15i6x+2x24St.12x+x012解：化為標(biāo)準(zhǔn)型maxz=2x+x12x+x=1513x+2x+x=24St.012345單純型表如下：c.21000CXbxx2xxx0 x31505100一0 x4246201040 x55110015Z0210000 x3150510032x1411/301/60120 x102/30-1

32、/613/2Z001/30-1/300 x315/20015/4-15/22x17/21001/4-1/21xc3/2010-1/43/2Z17/2000-1/4-1/2由些可得，問題的最優(yōu)解為X=7/2,x2=3/2，最優(yōu)值maxz=17/212、用大M法求解如下線性規(guī)劃模型：minz=5x2x4x1233x+x+2x4123v6x+3x+5x10123x,x,x0解：用大M法，先化為等效的標(biāo)準(zhǔn)模型：maxz/=5x2x4x123s.t.廠TOC o 1-5 h z HYPERLINK l bookmark154 3x+x+2x-x二412340,j二1,2,.,5j增加人工變量X、x，得到

33、：67maxz/=5x2x4xMxMx12367s.t3x+x+2x-x+x二412346701239x+5x+3x30123x,1x,x230minz=540 x450 x720 x解：用大M法，先化為等效的標(biāo)準(zhǔn)模型:maxz/=-540 x-450 x-720 x123s.t.廠3x+5x+9x-x二7012340,j二1,2,.,5j增加人工變量X、X,得到：67maXz/=-540X-450X-720X-MX-MXTOC o 1-5 h z12367s.t3x+5x+9x-x+x二70123460,j1,2,.,5j大M法單純形表求解過程如下：-540-450-72000-M-MCBX

34、BbX1x2x3x4x5x6x79L-Mx670359-101070/3(9)30/9=10/-Mx730530-1013-12M-10M-12MMM-M-M12M-540f10M-45012M-720-M-M00-Mx660010/3(8)-11/31-1/360/8=2.5540X110/315/91/30-1/901/910/3/1/3=10-300+10/3M-8M-180-M-M/3+60-MM/3-600-150+10/3M8M-540fMM/3600M/3+60TOC o 1-5 h z720 x315/205/1211/81/241/81/24540 x15/61(5/12)0

35、1/241/81/241/8540572720135/2475/12135/275/215/2/5/12=185/6/5/12=2x3720450 x220/32112/5011/61/61/61/6101/103/101/103/10360-57001804507207515751500751575M15M0125f0135/2475/12135/2M75/2M20:該對偶問題的最優(yōu)解是x*=(0,2,3，0，0)t最優(yōu)目標(biāo)函數(shù)值minz=(5700)=570014、用單純形法求解線性規(guī)劃問題maxz=-3x+x13x+x+x10 x0 x0123化成標(biāo)準(zhǔn)形式有maxz=3x+x+0 x+0

36、 x5134x+x+x+x=412342x+xxx=101-5加入人工變量則為maxz=3x+x+0 x+0 x一Mx一Mx134567”x+x+x+x=4i234一2x+x一x一x+x=1017列出單純形表c.-30100-M-McBJXBbx1x2x3xx5xx70 x441111000-Mx1-21-10-110-Mx790310001-Z10M-2M-34M10-M000 x4330211-100 x21-21-10-110-Mx7660403-31-Z6M6M-304M+103M-4M00 x400001-1/2-1/21/20 x23011/30001/3-3x11102/301/

37、2-1/21/6-Z300303/2-M-3/2-M+1/20 x400001-1/21/2-1/20 x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4-Z-M-1/4人工變量已不在基變量中，X*=(0,5/2,3/2,0,0,0,0)Z*=3/215、用單純形法求解線性規(guī)劃問題maxz=3x一2x”2x+11x22120 x012解化為標(biāo)準(zhǔn)形式有maxz=-3x-2x+0 x+0 x+Mx123452x+x+x=21233x+4xx+x=121245x015列表計(jì)算c.3200McBXBbx1x2x3x4x50 x322i1002Mx512340-11

38、3-Z-12M3M+34M+20-M0-2x2221100Mx54-50-4-11-Z4-4M-5M-10-4M-2-M0X*=(0,2,0,0,4)Z*=4M-4說明原問題無解寫對偶問題(10)1、寫出下列線性繪畫問題的對偶問題maxz=2x+x+3x+xTOC o 1-5 h z1234廠x+x+x+x1134x,x0,x,x無約束1324解：mino=5y一4y+y123y+2y+y2123yy=1123123y+y=113y0,y無約束,y01232、寫出下述線性規(guī)劃的對偶問題maxz=x+4x+3x1232x+3x5x10 x11233y1+y301y02y3無約束3、寫出下列線性規(guī)

39、劃的對偶問題minz=25x+2x+3x123x+xx11232xx+x=1123x0 x0 x無約束J123解：maxw=y+y12+y3y+iy+22y3252y1y02y=3y無約束334、寫出下列線性規(guī)劃的對偶問題maxz=2x+x+4x1232x+3x+x11233xx+x40 x21233y-y112y+y+y=4123y0y無約束J123151515 151515 4 對偶性質(zhì)1、已知線性規(guī)劃問題如下：MaxZ=x+3x12I5x+10 x112x01/10y+y+y3123.y,y0;y0為嚴(yán)格不等式所以y廣0132#X=（2,4）祇入原問題可知：x1+x21由對偶問題性質(zhì)可知

40、：50y+4y=1413解之得：y1=1/5y2MinZ=1410y1+y3二3所以Y=（1/5,0，1）t2、已知線性規(guī)劃問題minz=2x+3x+5x+6x1234x+2x+3x123v2x+xx+3x0（j二123,4）j用圖解法求對偶問題的解；利用（b）的結(jié)果及對偶性質(zhì)求原問題解。答案：（對偶問題的最優(yōu)解為y*二（5,5）；（依據(jù)z*=w*及互補(bǔ)松弛性，有x=0，且2x+3x+5x=19/51234123452x一x+3x+x+x312345x0,j=1,2,5j已知其對偶問題的最優(yōu)解為y;=yj，最優(yōu)值為z*=5。試用對偶理論找出原問題的最優(yōu)解。先寫出它的對偶問題miXZ二4y1+3

41、y2s.t.y+2y2122y1+3y35y+y21231+y20將y1*,y2*的值代入約束條件，得，為嚴(yán)格不等式；設(shè)原問題的最優(yōu)解為2x；=x4二0。因y；,y20；原問題的兩個(gè)約束條,x*），由互補(bǔ)松弛性得x*二5件應(yīng)取等式，故有3x*+x*=42x*+x*=3求解后得到x*=1,x=1;故原問題的最優(yōu)解為2 #2 X*二10001；最優(yōu)值為W*=5。4、已知下列問題的最優(yōu)解為X*=(l/7,ll/7),用互補(bǔ)松弛定理求其對偶問題的最優(yōu)解。LP:maxz=x+2x123x+x212x+2x312x一3x0解：第一步，寫出對偶問題第二步，將LP,DP都化為標(biāo)準(zhǔn)型LP:maxz=x+2x12

42、1233y-y+y1i23y+2y3y20v1y02y03DP:minw=2y+3y+y3x+x+x=2121S一x+2x+x=30 x,0J1S2S3S第三步：將最優(yōu)解代入標(biāo)準(zhǔn)型中，3y-y+y一y=1i231Sy+2y一3y一y=2011y02y03y,1S2S0DP:minw=2y+3y+y123確定松弛變量取值c111771c11F2x7713113x771Sx1Sx2S+x3Sx3S第四步：利用互補(bǔ)松弛定理Y*X=(Y*,Y*,Y*)23(X)1SX2SIX丿3S=Y*X11SFY*X22SFY*X33S=0Y*=03YX*=(YS1S,Y2S*=YX1S1*FYX*=02S2Y=0

43、Y=01S2S 第五步：將Y3*=0Y1S=0Y2S=0代入約束條件則有3yi-y2yi+2y2對偶問題的最優(yōu)解為Y*=（4/7,5/7,0）maxz二x+x廠x11+22x2+x32x+xx01235、已知線性規(guī)劃問題：，試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解。證明：首先看到該問題存在可行解，例如X=（000）,而上述問題的對偶問題為:minwi2y+y12一y1一2y21y+y10Iy1,y20由第一約束條件可知對偶問題無可行解，因而無最優(yōu)解。由此，原問題也無最優(yōu)解。5、已知線性規(guī)劃問題minz=2x+3x+5x+6x1234x+2x+3x+x22x+xx+3x0（ji1,2,3,4）4

44、j（1）（2）（3）解：（1）原線性規(guī)劃問題可化為寫出其對偶問題；用圖解法求對偶問題的解；利用（2）的結(jié)果及對偶性質(zhì)求原問題解。minzi2x+3x+5x+6x1234x+2x+3x+x21234s.t.31234x0(j=1,2,3,4丿j其對偶問題為：maxw=2y+3y12y+2y2122y-y312s.t.3y+y512y-3y61281用圖解法解得Y*=（yi,y2）=（5,5）3）由互補(bǔ)松弛性定理知道，y-3y1219w*=-51231123x01-3解：先化為標(biāo)準(zhǔn)型maxz=-15x一24x一5x+0-x12346x+x一x=22345x+2x+x一x=11235x015約束條件

45、兩邊同乘(-1)TOC o 1-5 h z一6x一x+x=一2234一2x一x+x=一1235X*=(0,1/4,1/2)Y*=(7/2,3/2)列單純形表c-15-24-500cBXBbx1x2x3x4x50 x4-20-6-1100 xE1-5-2-101-15-24-50045-240 x2x51/3-1/30-5101/62/3-1/6-1/301-150-1-4033/212-24x21/4-5/410-1/41/4-5xo1/215/2011/2-3/2-15/200-7/2-3/22、用對偶單純形法解下列線性規(guī)劃問題minz=4x+12x+18xTOC o 1-5 h z23x+

46、3x31353x0 HYPERLINK l bookmark104 V1-3解：改寫為標(biāo)準(zhǔn)形式maxz=-4x112x18x+0 x+0 x2345x3x+x=3134v2x2x+x=523x0515列單純形表如下：c.4121800cXbxx2x3xxox4310-310oxE50-2-201-4-12-180069ox4-3-10-310-12xc5/20110-1/2-40-60-64212-18-12x3X。13/21/3-1/30110-1/31/30-1/2-200-2-6X*=(0,3/2,1)Y*=(2,6)3、用對偶單純形法求解下面的問題minz=12x+8x+16x+12x

47、2x1234+x+4x21232x+2x+4x3124x,x,x,x01234解：令z=-z，則問題可以標(biāo)準(zhǔn)化為:maxz=-12x-8x-16x-12x12342xx4x+x=212352x2x4x+x=31246x,x,x,x,x,x0123456取(P5P)=60）、1為初始基，則1丿（一2）一3）其余X,=0是非基可行解，但Y=CB-1是對偶可行解，建立單純形表（見表4-1）B=0,最優(yōu)值z=14.。X計(jì)算結(jié)果如下：最優(yōu)解2X3X或最優(yōu)解1X21其余Xj=。，最優(yōu)值z=詠X)8本例如果用單純形法計(jì)算,確定初始基可行解時(shí)，還需要引入兩個(gè)人工變量3計(jì)算量要多于對歐單純形法。表3-1：C-1

48、2一8一16-12009備注CBXBB-1bX1X2XX34X5X60X5-2-2一1一4010L=20X6一3-2-20(3013/4K=4-121612000X5X4-2-240102L=1-123/41/21/20101/43/2K=2一6-216003一8-12X2X421/4210402111/201/4L=2K=1或3-208023一8X101一4431-125X11/2104一211/2靈敏度分析1、已知線性規(guī)劃的標(biāo)準(zhǔn)形式為maxz二一x+2x+x+0-x+0-x12345x+x+x+x-6123401一5其最優(yōu)單純形表如下C.-12100CBXBbx1x2x3x4x52x261

49、11100 x51030111Z1230120問：(1)當(dāng)q由一1變?yōu)?時(shí)，求新問題的最優(yōu)解(2)討論C2在什么范圍內(nèi)變化時(shí)，原有的最優(yōu)解仍是最優(yōu)解解：由表可知，C1是非基變量的價(jià)值系數(shù)，因此q的改變只影響Q=c一z=(c+Ac)一CB-1p-(c一CB-1p)+Ac=+Ac=一3+5=2011111B11B1111可見最優(yōu)性準(zhǔn)則已不滿足，繼續(xù)迭代C.42100CXbxx2x3xx2x261111060 x5103011110/3Z12201202x28/3012/32/31/34x110/3101/31/31/3Z-56/3005/38/32/3(2)要使原最優(yōu)解仍為最優(yōu)解，只要在新的條件下

50、滿足OW0成立，因?yàn)閤2是基變量，所以所有的。值都將發(fā)生變化2o=CCB-1AB-(c,c,c,c,c)一CB-1(p,p,p,p,p)51012345B.(1*=(-1,c20，)-22；叩12oY113411一10-(T，c2，1，0，0)一(叮)(1311100111丿-(-1,c,1,0,0)-(c,c,c,c,0)22222-(-1c,0,1c,-c,0)0222一1-c02即1-C02-c02則C三1c+c1c-12222所以當(dāng)x2的系數(shù)c22-1時(shí)，原最優(yōu)解仍能保持為最優(yōu)解。解：X=B-1(b+Ab)=B102_-13_1/30-2/33_-1_11-12二0112二500131

51、/301/3322已知線性規(guī)劃問題及其最優(yōu)單純形表maxz=XX+4x123X+X+2x9i23X+XX2123X+X+X01-5最優(yōu)單純形表如下：c.23100CBXBbx1x2x3x4x52x1110-14-163xo2012-1110/3-Z-800-3-5-1若p由原來的31/3-7/3T1/101/3，最優(yōu)解將如何改變(4-1丫1/10)仃/15)解：計(jì)算p=B-1p!_=33-11丿(1/3丿(7/30丿繼續(xù)迭代a=(23門5=1/60I7/30丿C,23100CBXBbx1x2x3x4x52x11101/154-1153xo2017/30-1160/7-Z-8001/6-5-12

52、x13/71-2/7030/7-9/7151x360/70-30/71-30/7-30/760/7-Z-66/70-5/70-30/7-12/7X*=(3/7,0,60/7,0,0)Z*=66/7例4(仍以例2為例)已知線性規(guī)劃問題及其最優(yōu)單純形表maxz=-x一x+4x123x+x+2x9123x+xx2123一x+x+x4123c.114000CBXBbx1x2x3xx5x1x11/31-1/301/30-2/30 x560200114x313/302/311/301/3-Z-170-40-10-2現(xiàn)增加一個(gè)新變量x7，且c7=3,p7=(3,l,-3)，求新問題的最優(yōu)解。1/30-2/3

53、、解：由表知：B-1=011J/301/3丿=c-CB-1p7B=3-(-1,0,4)7=6“1/30-2/3勺、勺、=B一1p=70111=-2J/301/3丿一3丿0丿7繼續(xù)迭代C.1140003CBXBbx1x2x3xx5xx71x11/31-1/301/30-2/330 x56020011-24x313/302/311/301/30-Z-170-40-10-263x71/91/3-1/901/90-2/910 x556/92/316/902/915/90 5、線性規(guī)劃問題 4x313/302/311/301/30-Z-53/3-2-10/30-5/30-2/30X*=(0,0,13/3

54、,0,56/9,0,1/9)Z*=53/35已知線性規(guī)劃問題及其最優(yōu)單純形表C114000CJXbxxxxxx2351x11/31-1/301/30-2/30 x560200114xo13/302/311/301/3-Z-170-40-10-2現(xiàn)增加新約束-3Xi+X2+6學(xué)17，求新問題的最優(yōu)解。TOC o 1-5 h z113解：將原問題的最優(yōu)解代入新增約束-3x3+0+6二=2517不滿足新增加的約束條件，因此引入松弛變量x7后，新增約束變?yōu)?3X1+X2+6X3+X7-17，加進(jìn)最優(yōu)表得:C.1140000CBXBbx1x2x3xx5xx71x11/31-1/301/30-2/330

55、x56020011-24x313/302/311/301/300 x717-3160001-Z-170-40-10-201x11/31-1/301/30-2/300 x5602001104x313/302/311/301/300 x7-80-46-10-41-Z-170-40-10-20b/ajrj111/21x15/311/301/200-1/60 x54010-1/4101/44x311/301/311/4001/120 x20101/401-1/4-Z-130-20-1/200-1/2TOC o 1-5 h zX*=(5/3,0,ll/3,0,4,2,0)Z*=13maxZ=2xx+x1

56、23廠x+x+x6123x+2x0123用單純形法求解得最終單純形表如下表所示。x1x2x3x4x5x1611110XE1003111c-zjj10-3-1-20試說明分別發(fā)生如下變化時(shí)，新的最優(yōu)解是什么？(l)目標(biāo)函數(shù)變?yōu)閙axZ=2xi+3x2+x3；2)約束條件右端項(xiàng)由變?yōu)樵鎏硪粋€(gè)新的約束-+2x32。2)因?yàn)锽1=1011。所以B-1b=111111c.2-11000iCxbxx2x3xx2x3111100 x703111c-zjj10-3-1-20因?yàn)樗械臋z驗(yàn)數(shù)均小于等于零，故最優(yōu)解為X*=(3,0,0,0,7)解：(1)c.231000iCxbxx2x3xx2x61111020

57、x10031110c-z01-1-202x18/3102/32/3-1/323Xc10/3011/31/31/30c-zjj100-4/3-7/3-1/3因?yàn)樗械臋z驗(yàn)數(shù)均小于等于零。故最優(yōu)解為X*=(8/3,10/3,0,0,0)(3)由于一x+2x=6+2x0=62左右兩端同時(shí)乘以“-1”并加上松弛變量x,136得到x一2x+x=一2136C.2-110000iCxbxx2x3xxx2x61111000 x100311100 x-210-2001C-Z0-3-1-2002x161111000 x100311100 x-80-1-3-101C-z0-3-1-2002x110/312/302/

58、301/30 x522/308/302/311/31x28/301/311/30-1/3C-zjj10-8/30-5/30-1/3因?yàn)樗械臋z驗(yàn)數(shù)均小于等于零，故最優(yōu)解為X*二(10/3,0,8/3,0,22/3)第三章運(yùn)輸問題（15）1、安排一個(gè)使總運(yùn)費(fèi)最低的運(yùn)輸計(jì)劃，并求出最低運(yùn)費(fèi)。一運(yùn)-價(jià)-龍肖地產(chǎn)地TA1A2A3A4產(chǎn)量產(chǎn)161110950210761470312881130需求量30405030要求：先用最小元素法求出一個(gè)初始方案，再用閉回路法，求檢驗(yàn)數(shù)。如果不是最優(yōu)，改進(jìn)為最優(yōu)。解：1）先用最小費(fèi)用法（最小元素法）求此問題的初始基本可行解：銷產(chǎn)地用地A1A2A3A4Si611109

59、5030XX20210761470X2050X312881130X20X10dj30405030150150初始方案：Z=6X30+9X20+7X20+6X50+8X20+11X10=10702）用閉回路法，求檢驗(yàn)數(shù)：費(fèi)銷*A1A2A3A4Si1611510595030XX20210-37614470X2050X312-48811130X20X10j該指派問題的最優(yōu)方案就是上面用“最小費(fèi)用法”求得的初始方案求出最小費(fèi)用Z=6X30+9X20+7X20+6X50+8X20+11X10=10702、給定下列運(yùn)輸問題：（表中數(shù)據(jù)為產(chǎn)地Ai到銷地Bj的單位運(yùn)費(fèi)）B1B2B3B4siA1123410A2

60、876580A391011915dj82212181）用最小費(fèi)用法求初始運(yùn)輸方案，并寫出相應(yīng)的總運(yùn)費(fèi)；（5分）2）用1）得到的基本可行解，繼續(xù)迭代求該問題的最優(yōu)解。（10分）ii2）用閉回路法，求檢驗(yàn)數(shù):選x34作為入基變量迭代調(diào)整。用表上閉回路法進(jìn)行迭代調(diào)整：j最優(yōu)方案為:4822441220A2運(yùn)銷價(jià)產(chǎn)A】A2A3A4產(chǎn)量19129650273776036591150需求量40406020。要求：（i）用最小費(fèi)用法建立運(yùn)輸計(jì)劃的初始方案;用位勢法做最優(yōu)解檢驗(yàn)；求最優(yōu)解和最優(yōu)方案的運(yùn)費(fèi)。最小運(yùn)費(fèi)Z=1X8+2X2+6X12+5X8+10X20g9X10=4143、下列是將產(chǎn)品從三個(gè)產(chǎn)地運(yùn)往四