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

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

2、潤(rùn)（元/件）43建立使利潤(rùn)最大的生產(chǎn)計(jì)劃的數(shù)學(xué)模型，不求解。解：設(shè)甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量為 Xi、X2,設(shè)z為產(chǎn)品售后總利潤(rùn)，則 max z = 4x 1+3x23、一家工廠制造甲、乙、丙三種產(chǎn)品，需要三種資源一一技術(shù)服務(wù)、勞動(dòng)力和行政管理。每種產(chǎn)品的資源消耗量、單位產(chǎn)品銷售后所能獲得的利潤(rùn)值以及這三種資源的儲(chǔ)備量如下表所示：技術(shù)服務(wù)行政管理單位利潤(rùn)甲110210乙1426丙1564資源儲(chǔ)備量100600300建立使得該廠能獲得最大利潤(rùn)的生產(chǎn)計(jì)劃的線性規(guī)劃模型，不求解。解：建立線性規(guī)劃數(shù)學(xué)模型：設(shè)甲、乙、丙三種產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為X1、X2、X3,則X1、X2、X3>0,設(shè)z是產(chǎn)品售后的

3、總利潤(rùn)，則maX z =10x 1+6X2+4X3.4、一個(gè)登山隊(duì)員，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相器材、通信器材等。每種物品的重量合重要性系數(shù)如表所示。設(shè)登山隊(duì)員可攜帶的最大重量為25kg,試選擇該隊(duì)員所應(yīng)攜帶的物品。序號(hào)1234567物品食品氧氣冰鎬繩索帳篷照木皤材通信設(shè)備重量/Kg55261224重要性系數(shù)201518148410試建立隊(duì)員所能攜帶物品最大量的線性規(guī)劃模型，不求解。解：引入01變量x, x=1表示應(yīng)攜帶物品i , , Xi=0表示不應(yīng)攜帶物品I5、工廠每月生產(chǎn) A B、C三種產(chǎn)品，單件產(chǎn)品的原材料消耗量、設(shè)備臺(tái)時(shí)的消耗量、資源限量及單件產(chǎn)品利潤(rùn)如下

4、圖所示：工、產(chǎn)資品源、ABC資源限量材料（kg）42500設(shè)備（臺(tái)時(shí)）31400利潤(rùn)（元/件）101412根據(jù)市場(chǎng)需求，預(yù)測(cè)三種產(chǎn)品最低月需求量分別是150、260、120,最高需求量是250、310、130,試建立該問(wèn)題數(shù)學(xué)模型，使每月利潤(rùn)最大，為求解。解：設(shè)每月生產(chǎn) A B C數(shù)量為X1,X2,X3。6、A、B兩種產(chǎn)品，都需要經(jīng)過(guò)前后兩道工序，每一個(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一部分可出售盈利，

5、 其余只能加以銷毀。出售A、B、C的利潤(rùn)分別為3、7、2元，每單位產(chǎn)品C的銷毀費(fèi)用為1元。預(yù)測(cè)表明，產(chǎn)品C最多只能售出13個(gè)單位。試建立總利潤(rùn)最大的 生產(chǎn)計(jì)劃數(shù)學(xué)模型，不求解。解：設(shè)每月生產(chǎn) A B數(shù)量為x，X2，銷毀的產(chǎn)品C為X3。7、靠近某河流有兩個(gè)化工廠 （參見(jiàn)附圖），流經(jīng)第一化工廠的河流流量為每天 500m3,在兩個(gè)工廠之間有一條流量為 200萬(wàn)m3的支流。第一化工廠每天排放有某種 優(yōu)化物質(zhì)的工業(yè)污水 2萬(wàn)m3 ,第二化工廠每天排放該污水萬(wàn) m3 o從第一化工廠的 出來(lái)的污水在流至第二化工廠的過(guò)程中，有20班自然凈化。根據(jù)環(huán)保要求，河流中的污水含量不應(yīng)大于 %這兩個(gè)工廠的都需要各自處理

6、一部分工業(yè)污水。第一化 工廠的處理成本是1000元/萬(wàn)m3 ,第二化工廠的為 800元/萬(wàn)m3?，F(xiàn)在要問(wèn)滿足 環(huán)保的條件下，每廠各應(yīng)處理多少工業(yè)污水，才能使兩個(gè)工廠的總的污水處理費(fèi) 用最少列出數(shù)學(xué)模型，不求解。3和X2萬(wàn)m 3,0.8x1 x2 1.6 stx2 1.4x1,x2 0,希望獲得其中3種營(yíng)養(yǎng)物，其分8、消費(fèi)者購(gòu)買某一時(shí)期需要的營(yíng)養(yǎng)物（如大米、豬肉、牛奶等）的營(yíng)養(yǎng)成分（如：蛋白質(zhì)、脂肪、維生素等）。設(shè)市面上現(xiàn)有這 別含有各種營(yíng)養(yǎng)成分?jǐn)?shù)量，以及各營(yíng)養(yǎng)物價(jià)格和根據(jù)醫(yī)生建議消費(fèi)者這段時(shí)間至 少需要的各種營(yíng)養(yǎng)成分的數(shù)量（單位都略去）見(jiàn)下表養(yǎng)物 營(yíng)養(yǎng)成分甲乙丙至少需要的營(yíng)養(yǎng)成分?jǐn)?shù)量A4620

7、80B11265C10370D21735450價(jià)格252045問(wèn)：消費(fèi)者怎么購(gòu)買營(yíng)養(yǎng)物，才能既獲得必要的營(yíng)養(yǎng)成分，而花錢最少只建立模型，不用計(jì)算。解：設(shè)購(gòu)買甲、乙、丙三種營(yíng)養(yǎng)物的數(shù)量分別為Xi、X2和X3,則根據(jù)題意可得如下線性規(guī)劃模型：9、某公司生產(chǎn)的產(chǎn)品 A, B, C和D都要經(jīng)過(guò)下列工序：包I、立銃、鉆孔和裝配。已知每單位產(chǎn)品所需工時(shí)及本月四道工序可用生產(chǎn)時(shí)間如下表所示：刨立銃鉆孔裝配AB.CD可用生產(chǎn)時(shí)間（小時(shí)）1800280030006000又知四種產(chǎn)品對(duì)利潤(rùn)貢獻(xiàn)及本月最少銷售需要單位如下:產(chǎn)品最少銷售需要單位元/單位A1002B6003C5001D4004問(wèn)該公司該如何安排生產(chǎn)使利

8、潤(rùn)收入為最大（只需建立模型）解：設(shè)生產(chǎn)四種產(chǎn)品分別 Xi,X2,X 3,x 4單位則應(yīng)滿足的目標(biāo)函數(shù)為：max z=2 x i+3 X2+X3+ x 4滿足的約束條件為：10、某航空公司擁有10架大型客機(jī)、15架中型客機(jī)和2架小型客機(jī)，現(xiàn)要安排從一機(jī)場(chǎng)到4城市的航行計(jì)劃，有關(guān)數(shù)據(jù)如表1-5,要求每天到D城有2個(gè)航次（往返），到A,B,C城市各4個(gè)航次（往返），每架飛機(jī)每天只能完成一個(gè)航次，且飛行時(shí)間最多為18小時(shí)，求利潤(rùn)最大的航班計(jì)劃客機(jī)類型到達(dá)城市飛行費(fèi)用（元/次）飛行收入（元/次）飛行時(shí)間（h/d ）大型A600050001B700070002C8000100005D10000180001

9、0中型A100030002B200040004C400060008D20小型A200040001B350055002C600080006D19解：設(shè)大型客機(jī)飛往 A城的架次為X1A,中型客機(jī)飛往 A城的架次為X2A,小型客機(jī)飛往A城的架次為X3A,其余依此類推。資源限制 派出的大型客機(jī)架次不能超過(guò) 10架，表示為同理X2A X2B X2CX3A X3B X3C152班次約束飛往各城的班次要滿足非負(fù)性約束Xj 0 且為整數(shù)；（i=1,2,3產(chǎn)A,B,C,D）目標(biāo)函數(shù)為maxz 1000x1A 0x1B 2000x1c 8000Xid+2000x2A2000x2B 2000X2C 2000x3A

10、2000X3B 2000X3C 2 B2 C3A3 B3C11、AR1AR2AR4AR6聯(lián)邦航空局的最大產(chǎn)量（每月生產(chǎn)的飛機(jī)數(shù)目）8171115建造飛機(jī)所需要的時(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ì)算）。Jonathan Kuring是該公司飛機(jī)制造 管理的主任，他想要確定下個(gè)月的生產(chǎn)計(jì)劃安排，以便使盈利貢獻(xiàn)最大化。解：設(shè)人表示下個(gè)月生產(chǎn) AR1型

11、飛機(jī)的數(shù)目，X2表示AR2型，X3表示AR4型，x,表 示AR6型目標(biāo)函數(shù)： maxz 62x1 84x2 103x3 125x44xi 7x2 9x3 11x4270x1 x2 2x3 2x4 60Xi 8約束條件：x 17X3 11x4 15X1,X2,X3,X40Xi,X2, X3,X4 為整數(shù)12、永輝食品廠在第一車間用 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元。3 個(gè)車

12、間每月最多有原料N的單位購(gòu)入價(jià)為2元，上述生產(chǎn)費(fèi)用不包括工資在內(nèi)20 萬(wàn)工時(shí)，每工時(shí)工資元，每加工1 單位 N 需要工時(shí)，若A 繼續(xù)加工，每單位需3 工時(shí)，如 B 繼續(xù)加工，每單位需2 工時(shí)。原料N 每月最多能得到 10 萬(wàn)單位。問(wèn)如何安排生產(chǎn)，使工廠獲利最大解：設(shè)xi為產(chǎn)品A的售出量；X2為A在第二車間加工后的售出量；X3表示產(chǎn)品B的售出量；X4表示B在第三車間加工后的售出量；X5為第一車間所用原材料的數(shù)量，則目標(biāo)函數(shù)為： maX z 8X1 9.5 X2 7X3 8X4 2.75 X5X5 1000003X2 2X4 1.5X5 200000約束條件：X1 X2 3X5 0X3 X4 2

13、X50X1,X2,X3,X4,X5 0?化標(biāo)準(zhǔn)形式(5)1、將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式min z x12x23x3xi又2X37xi又2X3234又22x35xi 0x20x3無(wú)約束maxz'x1 2x2 3(x4 x5) 0 x6 0 x7Xix2x4x5x67xix2x4x5x723xix22x35xi 70解：2、將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式解：3、將下列線性規(guī)劃變?yōu)樽畲笾禈?biāo)準(zhǔn)形。解:? 圖解法（ 5 ）1、用圖解法求解下面線性規(guī)劃 min z = 3x1+2x2解：可行解域?yàn)閍bcda ，最優(yōu)解為b 點(diǎn)。由方程組2x1 4x222x20解出x1=11， x2=0*x1X*

14、=x2=（11， 0） Tmin z =3X 11+2X0= 332、用圖解法求解下面線性規(guī)劃min z =2x 1+x2解：從上圖分析，可行解域?yàn)閍bcde,最優(yōu)解為 e點(diǎn)。由方程組x1x2x1解出 x 1=5， x2=3*x1X*=（ 5， 3 ）x23、已知線性規(guī)劃問(wèn)題如下：.min z =Z *= 2 x 5+3=13Max Z= x1 3x2用圖解法求解，并寫出解的情況解：5xi+10X2=50由圖可知:5xi 10X250Xl+X2=1解之得:Xi貝U max Z=2+3*4=14 4、用圖解法求解下面線性規(guī)劃問(wèn)題解:5、用圖解法求解下面線性規(guī)劃問(wèn)題圖解如下:可知，目標(biāo)函數(shù)在B(4

15、, 2)處取得最大值，故原問(wèn)題的最優(yōu)解為X* (4,2)T,目標(biāo)函數(shù)最大值為z* 2*43*214。二、單純型法(15)1、用單純型法求解下面線性規(guī)劃問(wèn)題的解max z= 3x i+3x2+4x33x1 4x2 5x3 406x1 4x2 3x3 66 .x1,x2, x30解：加入松弛變量x4, x5,得到等效的標(biāo)準(zhǔn)模型:max z= 3x 1+3x2+4x3+0 x 4+0 x 53xi 4x2 5x3 x440.6x1 4x2 3x3x5 66xj 0, j 1,2,5列表計(jì)算如下:33400CBXBbx1x2x3x4x59 L0x44034(5)1080x566643012200000

16、334 t004x383/54/511/5040/30x542(21/5 )8/50-3/511012/516/544/503/5 t-1/50-4/504x3204/712/7-1/73x11018/210-1/75/21324/745/71/7380-3/70-5/7-1/7X=(10, 0, 2, 0, 0) T -.max z =3X10+4X2 =382、用單純型法求解下面線性規(guī)劃問(wèn)題的解 max z =70x i+120X29xi 4x2 3604xi 6x2 200.3xi 10x2300x1, x2 0解：加入松弛變量X3, X4, X5,得到等效的標(biāo)準(zhǔn)模型:max z =70

17、x 1+120x2+0 x 3+0 x 4+0 x 5列表計(jì)算如下:CBXBb70x1120x20x30x40x59 L0x336094100900x420046010100/30x53003(10)001300x32400x420120x2300x31860/1170x1100/11120x2300/11. X二(10011，max z =7000070120 t039/501(11/5 )003/101036120034 t00001100010701200000T300186011 '110)X +120X11300 = 4300011 - 110000400/10-2/5310

18、0/11-3/5101/1010001201239/1119/115/11-3/11-3/222/11170/1130/11-170/1130/113、用單純型法求解下面線性規(guī)劃問(wèn)題的解2x1 2x2 3000max z = 4x 1+3x2.5x1 2.5x2 4000x1500x1 , x20解：加入松弛變量x3, x4, x5,得到等效的標(biāo)準(zhǔn)形式:max z= 4x 1+3x2+0 x 3+0 x 4+0 x 5.2x1 5x1 x1Xj2x22.5x20，jx3x4x51,2,30004000500.,5用表解形式的單純形法求解，列表計(jì)算如下*43000CBXBbxix2x3x4x59

19、 L0x33000221003000/2 =15000x4400050104000/5 =8000x5500(i)0001500/1 =500000004 t30000x320000210-22000/2 =10000x415000001-51500/ =6004xi500100014000403 t00-40x3800001(2)800/2 =4003X2600010-24xi50010001500/1 =500430-20002 t0x54000013X214000114X11001043104600 00-10據(jù)上表，X*= (100, 1400, 0, 0, 400) Tmax z =

20、 4X 100+3X 1400=460 4、用單純型法求解下面線性規(guī)劃問(wèn)題的解max z =10x 1+6X2+4X3解：加入松弛變量X4, X5, X6,得到等效的標(biāo)準(zhǔn)模型:max z =10x 1+6X2+4X3+0 x 4+0 x 5+0 x 6X1 x2 x3 x410010x1 4x2 5x3X5600.2x1 2x2 6x3x6 300Xj 0,j 1,2,6列表計(jì)算如下:1064000CBXBbx1x2x3x4x5x69 L0x41001111001000x5600(10)45010600x630022600115000000010 t640000x4400(3/5 ) 1/21

21、-1/100200/310x16012/51/201/1001500x618006/550-1/51150104501002t 10- 106x2200/3015/65/3-1/6010x1100/3101/6 -2/31/600x6100004-20110620/3 10/32/30一008/3 10/30 2/3*100200_ T. X二(c ，0，0, 0, 100)33100200 2200max z=10X+6X=3335、用單純型法求解下面線性規(guī)劃問(wèn)題的解用單純形法求解，并指出問(wèn)題的解屬于哪一類。解：（1）、將原問(wèn)題劃為標(biāo)準(zhǔn)形得：3x1 x2 x3 x4 =604-22000b0

22、603111000101-120100402-220014-220004-22000b03004-51-304101-1201002004-60-2102-60-404-22000b0100011-1-1415101/201/21/4-2501-3/20-1/21/400-30-3-1/2所以X= (15, 5, 0, 10, 0, 0) T為唯一最優(yōu)解Max Z=4*15-2*5=506、用單純形法求解下述 LP問(wèn)題。解：引入松弛變量X3、X4,化為標(biāo)準(zhǔn)形式：構(gòu)造單純形表，計(jì)算如下：100015351050105201210009019/51 3/545/19212/501/55000 1/

23、2145/19015/19 3/1920/1910 2/195/19000 1/2由單純形表，可得兩個(gè)最優(yōu)解 X(2,0,9,0)T、X(20/19,45 /19,0,0) T ,所以兩點(diǎn)之間的所有解都是最優(yōu)解，即最優(yōu)解集合為：X(1)*出，其中01maxz 2x1 X25x2156x12x224X1x25x1 0x2 07、用單純形法解線性規(guī)劃問(wèn)題解：化為標(biāo)準(zhǔn)型maxz 2x1 x2 0x3 0x4 0x55x2x3 156x12x2x4 24x1x2 x5 5x1 5 0列出單純形表C21000CBXbXiX2X3X4X50x3150510040乂4246201050x5511001-Z0

24、210000x3150510032x1411/301/60120x5102/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ī)劃問(wèn)題的解 max z x1 x2Xi2x222x1x22x1x24x1 0 x2 0解：C11000CBXbx1x2x3x4x50x3211210020x42-210100X54-11001-Z0110001Xi21-21000X460-32100X5

25、60-1101-Z-203-100把表格還原為線性方程令 X 3=0此時(shí)，若讓X2進(jìn)基，則會(huì)和基變量X1同時(shí)增加，使目標(biāo)函數(shù)值無(wú)限增長(zhǎng)，所以本題無(wú)界9、用單純型法求解下面線性規(guī)劃問(wèn)題的解C24000CBXbbX1X2X3X4X50X381210040X441001030X5301001-Z0240000X321010-220X441001044X2301001-Z-122000-42X121010-20X4200-1124X2301001-Z-2000-2002x14100100x5100-1/21/214x22011/2-1/20-Z-2000-200Z*=20, X*=(2,3,0,2,0

26、)' Z*=20, X*=(4,2,0,0,1)max z 3x1 5x2x142x2123x12x218x10x2010、用單純型法求解下面線性規(guī)劃問(wèn)題的解解：列表如下C35000CBXbbx1x2x3x4x50x341010060乂4120201090x51832001-Z0350000x341010045x260101/2030x56300-11-Z-30300-5/200X360011/3-1/35X220101/203Xi2100-1/31/3-Z-20000-3/2-1X*=(2,6,6,0,0)'Z*=3611、用單純型法求解下面線性規(guī)劃問(wèn)題的解解：化為標(biāo)準(zhǔn)型單純

27、型表如下：C21000CBXbbX1X2X3X4X50X31505100一0X4246201040X55110015Z0210000X3150510032X1411/301/60120X5102/30-1/613/2Z001/30-1/300X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2Z17/2000-1/4-1/2由些可得，問(wèn)題的最優(yōu)解為Xi=7/2 , X2=3/2 ,最優(yōu)值max z=17/212、用大M法求解如下線性規(guī)劃模型:min z =5x 1 + 2x2+4x3解：用大M法，先化為等效的 標(biāo)準(zhǔn)模型：max z = 5xi 2x

28、2 4x3.增加人工變量x6、X7,得到：max z/ = 5xi 2x2 4x3 M<6 M<7大M法單純形表求解過(guò)程如下：-5-2-400MMCBXBb9 Lx1x2x3x4x5x6x7一 Mx64(3)1210104/3一 Mx7106350 1015/39M-4M-7MMMMM9M- 5t4M- 27M- 4M M00-5x14/311/32/3-1/301/30一 Mx72011-1-211-M一-5 -M- 5/3-2M+5/3 M 2M- 5/3 -M10/32M- 5/30M-1/3MM- 2/3- M - 3M+5/30t-5x15/311/25/60-1/601

29、/610/30x410(1/2)1/21 1/211/22-5 5/2-25/605/60-5/601/2 t1/60-5/6一 MM+5/65x12/3101/3-11/311/32x2201121-21一-5-211/311/311/322300-1/3-1-1/3M+1-M+1/3x*=(2a，2,0,0, 0) T最優(yōu)目標(biāo)函數(shù)值min z =-/一max z二一（一22)=22313、用大M法求解如下線性規(guī)劃模型*min z=540x 1+450x2 + 720x3解：用大M法,先化為等效的標(biāo)準(zhǔn)模型：max z/ = 540xi一 450x2 一720x3增加人工變量X6、X7,得到：

30、max Z = - 540xi 450X2 720X3 Mx Mx大M法單純形表求解過(guò)程如下：CBXBb-540-45072000M Mx1x2x3x4x5x6x79 L一 Mx670359-101070/3一 Mx730(9)530-10130/9=10/312M-10M-12MMM一 M一 M12M- 540t10M- 45012M-720一 M一 M00一 Mx660010/3(8)-11/31-1/360/8=10/3/1一540x110/315/91/30-1/901/9/3=10-300+10/3M-8M一180一 MM/3+60一 MM/3-600-150+10/3M8M-540

31、tMM/3-600M/3+6015/2/5一720x315/205/121-1/81/241/8-1/24/12=185/6/5/一540x15/61(5/12 )01/24-1/8-1/241/812=2-540-572-720一135/2475/12135/2 75/20125 t0135/2-475/12 135/2 -M75/2 M 720-450x3x220/32-1011/61/61/61/612/5101/10-3/10-1/103/10一5700.肉- 360450-7207515-75 15 18000-75-1575-M15-M寸偶問(wèn)題的最優(yōu)解是 x= (0, 2,0, 0

32、) T3最優(yōu)目標(biāo)函數(shù)值 min z = ( 5700) =570014、用單純形法求解線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)形式有加入人工變量則為列出單純形表C-30100一 M-MCbXbbXiX2X3X4X5X6X70X441111000-MX61-21-10-110-MX790310001-Z10M-2M-34M10-M000X4330211-100X21-21-10-110-MX7660403-31-Z6M6M-304M+103M-4M00X400001-1/2-1/21/20X23011/30001/3-3X11102/301/2-1/21/6-Z300303/2-M-3/2-M+1/20X40000

33、1-1/21/2-1/20X25/2-1/2100-1/41/41/41X33/23/20103/4-3/41/4-Z-3/2-9/2000-3/4-M+3/4-M-1/4人工變量已不在基變量中，X*=(0,5/2,3/2,0,0,0,0)'Z*=3/215、用單純形法求解線性規(guī)劃問(wèn)題解化為標(biāo)準(zhǔn)形式有 列表計(jì)算C-3-200MCBXBbX1X2X3X4X50X32211002MX512340-113-Z-12M3M+34M+20-M0-2X2221100MX54-50-4-11-Z4-4M-5M-10-4M-2-M0X*=(0,2,0,0,4)'Z*=4M-4 說(shuō)明原問(wèn)題無(wú)解?

34、 寫對(duì)偶問(wèn)題(10)1、寫出下列線性繪畫問(wèn)題的對(duì)偶問(wèn)題解:2、寫出下述線性規(guī)劃的對(duì)偶問(wèn)題maxzX1 4x23X32x13x25X323x1X26X31X1X2X34X10x20x3無(wú)約束解3、寫出下列線性規(guī)劃的對(duì)偶問(wèn)題min z25x12x2 3x3X1X2X31X12x2X312x1X2X31X10X20 X3無(wú)約束解:maxwy1y2y3y1y22y325y12 y2y32y1y2y33y10V2 0y3無(wú)約束4、寫出下列線性規(guī)劃的對(duì)偶問(wèn)題maxz2x1 x24x32x13x2X313x1X2X34X1X33Xi 0 X2 0 X3無(wú)約束? 對(duì)偶性質(zhì)1、已知線性規(guī)劃問(wèn)題如下：Max Z=

35、 x1 3x2已知該問(wèn)題的解為(2, 4)利用對(duì)偶性質(zhì)寫出對(duì)偶問(wèn)題的最優(yōu)解。解：該問(wèn)題的對(duì)偶問(wèn)題為：將X=(2,4)T代入原問(wèn)題可知：xiX2>1為嚴(yán)格不等式，所以V20由對(duì)偶問(wèn)題性質(zhì)可知：50yi 4y3 14解之串：Vi 1/5所以 Y= (1/5 , 0, 1) TM Min Z=142、已知線性規(guī)劃問(wèn)題、用圖解法求對(duì)偶問(wèn)題的解；利用(b)的結(jié)果及對(duì)偶性質(zhì)求原問(wèn)題解。，一，、一，一八，*8 1答案：(對(duì)偶問(wèn)題的最優(yōu)解為Y(8,1)；5 5(依據(jù)z*=w*及互補(bǔ)松弛性，有 X4=0，且解得愿問(wèn)題最優(yōu)解 X*=(7/5,0,1/5,0)。3、已知線性規(guī)劃問(wèn)題已知其對(duì)偶問(wèn)題的最優(yōu)解為y*

36、 4,y2 3,最優(yōu)值為z* 5。試用對(duì)偶理論找出原 55問(wèn)題的最優(yōu)解。解先寫出它的對(duì)偶問(wèn)題y12 y22yy232y1 3y3y V2 243yi V2 3y；,y；的值代入約束條件，得，為嚴(yán)格不等式；設(shè)原問(wèn)題的最優(yōu)解為x* (x*,x5),由互補(bǔ)松弛性得x2 x3 x； 0。因* *y1，y20；原問(wèn)題的兩個(gè)約束條件應(yīng)取等式，故有求解后得到x*1,x5 1；故原問(wèn)題的最優(yōu)解為X 1 0 0 0 1;最優(yōu)值為 w 5。4、已知下列問(wèn)題的最優(yōu)解為X*=(1/7,11/7),用互補(bǔ)松弛定理求其對(duì)偶問(wèn)題的最優(yōu)解。解：第一步，寫出對(duì)偶問(wèn)題第三步:將最優(yōu)解代入標(biāo)準(zhǔn)型中,確定松弛變量取值第四步:利用互補(bǔ)

37、松弛定理3x1x2 x12x2S323y1V2y3y1 S1x1 2x2 3x2 1x2S3y2y23y3y2S2x1 3xx1,x2 0x3S1x1, x2 0 xs,：2s，3S 0y10V2 0V3 0y1S，2s0DP : min w2yiy3第二步,將LP, DP都化為標(biāo)準(zhǔn)型3y2LP : max z x1 2x2LP : maXxz x1 2x2Y*=0Yis=0Ys=0第五步：將Y3*=0Ys=0Ys=0代入約束條件則有 yy1 2y： 12V2對(duì)偶問(wèn)題的最優(yōu)解為Y*=(4/7,5/7,0)maxz x1 x25、已知線性規(guī)劃問(wèn)題：Xx2x32,試用對(duì)偶理論證明2x1x2x31x1，x2,x30上述線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。證明：首先看到該問(wèn)題存在可行解，例如X 0 0 0,而上述問(wèn)題的對(duì)偶問(wèn)min w2y1y2y12 y21題為：y1y21y1y20y1，y20由第一約束條件可知對(duì)偶問(wèn)題無(wú)可行解，因而無(wú)最優(yōu)解。由此，原問(wèn)題也無(wú)最優(yōu)解。5、已知線性規(guī)劃問(wèn)題(1)寫出其對(duì)偶問(wèn)題；(2)用圖解法求對(duì)偶問(wèn)題的解；(3)利用(2)的結(jié)果及對(duì)偶性質(zhì)求原問(wèn)題解。解：(1)原線性規(guī)劃問(wèn)題可化為:其對(duì)偶問(wèn)題為：(2)用圖解法解得Y*