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

考試資料歡迎下載考試資料歡迎下載/考試資料歡迎下載運(yùn)籌學(xué)習(xí)題庫(kù)數(shù)學(xué)建模題（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)，則maxz=70x1+120x2s.t.2、某公司生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)所需原材料、工時(shí)和零件等有關(guān)數(shù)據(jù)如下：甲乙可用量原材料（噸/件）工時(shí)（工時(shí)/件）零件（套/件）2252.513000噸4000工時(shí)500套產(chǎn)品利潤(rùn)（元/件）43建立使利潤(rùn)最大的生產(chǎn)計(jì)劃的數(shù)學(xué)模型，不求解。解：設(shè)甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量為x1、x2，設(shè)z為產(chǎn)品售后總利潤(rùn)，則maxz=4x1+3x2s.t.3、一家工廠制造甲、乙、丙三種產(chǎn)品，需要三種資源——技術(shù)服務(wù)、勞動(dòng)力和行政管理。每種產(chǎn)品的資源消耗量、單位產(chǎn)品銷售后所能獲得的利潤(rùn)值以及這三種資源的儲(chǔ)備量如下表所示：技術(shù)服務(wù)勞動(dòng)力行政管理單位利潤(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)品售后的總利潤(rùn)，則maxz=10x1+6x2+4x3s.t.4、一個(gè)登山隊(duì)員，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相器材、通信器材等。每種物品的重量合重要性系數(shù)如表所示。設(shè)登山隊(duì)員可攜帶的最大重量為25kg,序號(hào)1234567物品食品氧氣冰鎬繩索帳篷照相器材通信設(shè)備重量/Kg55261224重要性系數(shù)201518148410試建立隊(duì)員所能攜帶物品最大量的線性規(guī)劃模型，不求解。解：引入0—1變量xi,xi=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)如下圖所示：產(chǎn)產(chǎn)品資源ABC資源限量材料（kg）1.51.242500設(shè)備（臺(tái)時(shí)）31.61.21400利潤(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ù)量為。6、A、B兩種產(chǎn)品，都需要經(jīng)過(guò)前后兩道工序，每一個(gè)單位產(chǎn)品A需要前道工序1小時(shí)和后道工序2小時(shí)，每單位產(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一部分可出售盈利，其余只能加以銷毀。出售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ù)量為銷毀的產(chǎn)品C為。7、靠近某河流有兩個(gè)化工廠（參見(jiàn)附圖），流經(jīng)第一化工廠的河流流量為每天500，在兩個(gè)工廠之間有一條流量為200萬(wàn)的支流。第一化工廠每天排放有某種優(yōu)化物質(zhì)的工業(yè)污水2萬(wàn)，第二化工廠每天排放該污水1.4萬(wàn)。從第一化工廠的出來(lái)的污水在流至第二化工廠的過(guò)程中，有20%可自然凈化。根據(jù)環(huán)保要求，河流中的污水含量不應(yīng)大于0.2%。這兩個(gè)工廠的都需要各自處理一部分工業(yè)污水。第一化工廠的處理成本是1000元/萬(wàn)，第二化工廠的為800元/萬(wàn)。現(xiàn)在要問(wèn)滿足環(huán)保的條件下，每廠各應(yīng)處理多少工業(yè)污水，才能使兩個(gè)工廠的總的污水處理費(fèi)用最少？列出數(shù)學(xué)模型，不求解。附圖：¤工廠1¤工廠2500萬(wàn)200萬(wàn)解：設(shè)第一化工廠和第二化工廠的污水處理量分別為每天和x2萬(wàn)，st8、消費(fèi)者購(gòu)買某一時(shí)期需要的營(yíng)養(yǎng)物（如大米、豬肉、牛奶等），希望獲得其中的營(yíng)養(yǎng)成分（如：蛋白質(zhì)、脂肪、維生素等）。設(shè)市面上現(xiàn)有這3種營(yíng)養(yǎng)物，其分別含有各種營(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)養(yǎng)物營(yíng)養(yǎng)成分甲乙丙至少需要的營(yíng)養(yǎng)成分?jǐn)?shù)量A462080B11265C10370D21735450價(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ù)量分別為，則根據(jù)題意可得如下線性規(guī)劃模型：9、某公司生產(chǎn)的產(chǎn)品A，B，C和D都要經(jīng)過(guò)下列工序：刨、立銑、鉆孔和裝配。已知每單位產(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)品對(duì)利潤(rùn)貢獻(xiàn)及本月最少銷售需要單位如下：產(chǎn)品最少銷售需要單位元/單位A1002B6003C5001D4004問(wèn)該公司該如何安排生產(chǎn)使利潤(rùn)收入為最大？（只需建立模型）解：設(shè)生產(chǎn)四種產(chǎn)品分別x1,x2,x3,x4單位則應(yīng)滿足的目標(biāo)函數(shù)為：maxz=2x1+3x2+x3+x4滿足的約束條件為：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ì)劃?？蜋C(jī)類型到達(dá)城市飛行費(fèi)用（元/次）飛行收入（元/次）飛行時(shí)間（h/d）大型A6000700080001000050007000100001800012510BCD中型A10002000400030004000600024820BCD小型A20003500600040005500800012619BCD解：設(shè)大型客機(jī)飛往A城的架次為x1A，中型客機(jī)飛往A城的架次為x2A，小型客機(jī)飛往A城的架次為x3A，其余依此類推。資源限制派出的大型客機(jī)架次不能超過(guò)10架，表示為同理班次約束飛往各城的班次要滿足非負(fù)性約束且為整數(shù)；（i=1,2,3;j=A,B,C,D）目標(biāo)函數(shù)為11、CRISP公司制造四種類型的小型飛機(jī)：AR1型（具有一個(gè)座位的飛機(jī)）、AR2型（具有兩個(gè)座位的飛機(jī)）、AR4型（具有四個(gè)座位的飛機(jī)）以及AR6型（具有六個(gè)座位的飛機(jī)）。AR1和AR2一般由私人飛行員購(gòu)買，而AR4和AR6一般由公司購(gòu)買，以便加強(qiáng)公司的飛行編隊(duì)。為了提高安全性，聯(lián)邦航空局（F.A.A）對(duì)小型飛機(jī)的制造做出了許多規(guī)定。一般的聯(lián)邦航空局制造規(guī)章和檢測(cè)是基于一個(gè)月進(jìn)度表進(jìn)行的，因此小型飛機(jī)的制造是以月為單位進(jìn)行的。表說(shuō)明了CRISP公司的有關(guān)飛機(jī)制造的重要信息。AR1AR2AR4AR6聯(lián)邦航空局的最大產(chǎn)量（每月生產(chǎn)的飛機(jī)數(shù)目）建造飛機(jī)所需要的時(shí)間（天）每架飛機(jī)所需要的生產(chǎn)經(jīng)理數(shù)目每架飛機(jī)的盈利貢獻(xiàn)（千美元）84162177184119210315112125CRISP公司下個(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è)表示下個(gè)月生產(chǎn)AR1型飛機(jī)的數(shù)目，表示AR2型，表示AR4型，表示AR6型目標(biāo)函數(shù)：約束條件：為整數(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元。原料N的單位購(gòu)入價(jià)為2元，上述生產(chǎn)費(fèi)用不包括工資在內(nèi)。3個(gè)車間每月最多有20萬(wàn)工時(shí)，每工時(shí)工資0.5元，每加工1單位N需要1.5工時(shí)，若A繼續(xù)加工，每單位需3工時(shí)，如B繼續(xù)加工，每單位需2工時(shí)。原料N每月最多能得到10萬(wàn)單位。問(wèn)如何安排生產(chǎn)，使工廠獲利最大？解：設(shè)為產(chǎn)品A的售出量；為A在第二車間加工后的售出量；表示產(chǎn)品B的售出量；表示B在第三車間加工后的售出量；為第一車間所用原材料的數(shù)量，則目標(biāo)函數(shù)為：約束條件：

化標(biāo)準(zhǔn)形式（5）1、將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式解：2、將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式解：3、將下列線性規(guī)劃變?yōu)樽畲笾禈?biāo)準(zhǔn)形。解：

圖解法（5）1、用圖解法求解下面線性規(guī)劃minz=－3x1+2x2解：可行解域?yàn)閍bcda，最優(yōu)解為b點(diǎn)。由方程組解出x1=11，x2=0∴X*==（11，0）T∴minz=－3×11+2×0=－332、用圖解法求解下面線性規(guī)劃minz=2x1+x2解：從上圖分析，可行解域?yàn)閍bcde，最優(yōu)解為e點(diǎn)。由方程組解出x1=5，x2=3∴X*==（5，3）T∴minz=Z*=2×5+3=133、已知線性規(guī)劃問(wèn)題如下：MaxZ=用圖解法求解，并寫出解的情況解：x26Z’4x2=42 Z’ x1 0246810 5x1+10x2=50 x1+x2=1由圖可知：解之得：則maxZ=2+3*4=144、用圖解法求解下面線性規(guī)劃問(wèn)題解：

5、用圖解法求解下面線性規(guī)劃問(wèn)題圖解如下：可知，目標(biāo)函數(shù)在B(4,2)處取得最大值，故原問(wèn)題的最優(yōu)解為，目標(biāo)函數(shù)最大值為。二、單純型法（15）1、用單純型法求解下面線性規(guī)劃問(wèn)題的解maxz=3x1+3x2+4x3s.t.解：加入松弛變量x4，x5，得到等效的標(biāo)準(zhǔn)模型：maxz=3x1+3x2+4x3+0x4+0x5s.t.列表計(jì)算如下：

CBXBb33400θLx1x2x3x4x50x44034（5）1080x566643012200000334↑004x383/54/511/5040/30x542（21/5）8/50－3/511012/516/544/503/5↑－1/50－4/504x3204/712/7－1/73x11018/210－1/75/2138324/745/71/70－3/70－5/7－1/7∴X*=（10，0，2，0，0）T∴maxz=3×10+4×2=382、用單純型法求解下面線性規(guī)劃問(wèn)題的解maxz=70x1+120x2s.t.解：加入松弛變量x3，x4，x5，得到等效的標(biāo)準(zhǔn)模型：maxz=70x1+120x2+0x3+0x4+0x5s.t.列表計(jì)算如下：CBXBb70120000θLx1x2x3x4x50x336094100900x420046010100/30x53003（10）001300000070120↑0000x324039/5010-2/5400/130x420（11/5）001-3/5100/11120x2303/101001/1010036120001234↑000－120x31860/11001－39/1119/1170x1100/111005/11-3/11120x2300/11010-3/222/11701200170/1130/11000-170/11－30/11∴X*=（，，，0，0）T∴maxz=70×+120×=3、用單純型法求解下面線性規(guī)劃問(wèn)題的解maxz=4x1+3x2s.t.解：加入松弛變量x3，x4，x5，得到等效的標(biāo)準(zhǔn)形式：maxz=4x1+3x2+0x3+0x4+0x5s.t.用表解形式的單純形法求解，列表計(jì)算如下：CBXBb43000θLx1x2x3x4x50x33000221003000/2=15000x4400052.50104000/5=8000x5500（1）0001500/1=500000004↑30000x320000210-22000/2=10000x415000（2.5）01-51500/2.5=6004x150010001——4000403↑00-40x3800001-0.8（2）800/2=4003x26000100.4-2——4x150010001500/1=5004301.2-2000-1.22↑0x5400000.5-0.413x21400011-0.404x110010-0.50.4046004310.4000-1-0.40據(jù)上表，X*=（100，1400，0，0，400）Tmaxz=4×100+3×1400=4604、用單純型法求解下面線性規(guī)劃問(wèn)題的解maxz=10x1+6x2+4x3s.t.解：加入松弛變量x4，x5，x6，得到等效的標(biāo)準(zhǔn)模型：maxz=10x1+6x2+4x3+0x4+0x5+0x6s.t.列表計(jì)算如下：CBXBb1064000θLx1x2x3x4x5x60x41001111001000x5600（10）45010600x630022600115000000010↑640000x4400（3/5）1/21－1/100200/310x16012/51/201/1001500x618006/550－1/51150104501002↑－10－106x2200/3015/65/3－1/6010x1100/3101/6－2/31/600x6100004－20110620/310/32/3000－8/3－10/3－2/30∴X*=（，，0，0，0，100）T∴maxz=10×+6×=5、用單純型法求解下面線性規(guī)劃問(wèn)題的解用單純形法求解，并指出問(wèn)題的解屬于哪一類。解：（1）、將原問(wèn)題劃為標(biāo)準(zhǔn)形得：=604-22000b060311100010[1]-120100402-220014-220004-22000b03004-51-304101-120100200[4]-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)解MaxZ=4*15-2*5=506、用單純形法求解下述LP問(wèn)題。解：引入松弛變量、，化為標(biāo)準(zhǔn)形式：構(gòu)造單純形表，計(jì)算如下：2.510001535105010[5]20122.5100090[19/5]1－3/545/192.5212/501/55000－1/2145/19015/19－3/192.520/1910－2/195/19000－1/2由單純形表，可得兩個(gè)最優(yōu)解、，所以兩點(diǎn)之間的所有解都是最優(yōu)解，即最優(yōu)解集合為：，其中。7、用單純形法解線性規(guī)劃問(wèn)題解：化為標(biāo)準(zhǔn)型列出單純形表Cj21000CBXBbx1x2x3x4x5000x3x4x5152450[6]152110001000145-Z021000020x3x1x5154101051/3[2/3]10001/6-1/60013123/2-Z-801/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2-Z-20000-1/4-1/2Z*=17/2,X*=(7/2,3/2,15/2,0,0)’8、用單純型法求解下面線性規(guī)劃問(wèn)題的解解：Cj11000CBXBbx1x2x3x4x5000x3x4x5224[1]-2-112111000100012-Z011000100x1x4x5266100-2-3-1121010001-Z-203-100把表格還原為線性方程令x3=0此時(shí)，若讓x2進(jìn)基，則會(huì)和基變量x1同時(shí)增加，使目標(biāo)函數(shù)值無(wú)限增長(zhǎng)，所以本題無(wú)界9、用單純型法求解下面線性規(guī)劃問(wèn)題的解Cj24000CBXBbx1x2x3x4x5000x3x4x584311020[1]10001000143-Z024000004x3x4x2243[1]10001100010-20124-Z-122000-4204x1x4x22231000011-10010-221-Z-2000-200204x1x5x24121000010-1/21/211/2-1/2010-Z-2000-200Z*=20,X*=(2,3,0,2,0)’Z*=20,X*=(4,2,0,0,1)’10、用單純型法求解下面線性規(guī)劃問(wèn)題的解解：列表如下Cj35000CBXBbx1x2x3x4x5000x3x4x5412181030[2]210001000169-Z035000050x3x2x546610[3]01010001/2-100143-Z-30300-5/20053x3x2x16220010101001/31/2-1/3-1/301/3-Z-20000-3/2-1X*=(2,6,6,0,0)’Z*=3611、用單純型法求解下面線性規(guī)劃問(wèn)題的解解：化為標(biāo)準(zhǔn)型單純型表如下：Cj21000CBXBbx1x2x3x4x5000x3x4x5152450[6]1521100010001–45Z021000020x3x1x5154101051/3[2/3]10001/6-1/60013123/2Z001/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2Z17/2000-1/4-1/2由些可得，問(wèn)題的最優(yōu)解為x1=7/2，x2=3/2，最優(yōu)值maxz=17/212、用大M法求解如下線性規(guī)劃模型：minz=5x1＋2x2＋4x3解：用大M法，先化為等效的標(biāo)準(zhǔn)模型：maxz/=－5x1－2x2－4x3s.t.增加人工變量x6、x7，得到：maxz/=－5x1－2x2－4x3－Mx6－Mx7s.t大M法單純形表求解過(guò)程如下：CBXBb－5－2－400－M－MθLx1x2x3x4x5x6x7－Mx64（3）12－10104/3－Mx7106350－1015/3－9M－4M－7MMM－M－M9M－5↑4M－27M－4－M－M00－5x14/311/32/3－1/301/30——－Mx72011（2）－1－211－5-M－5/3-M－10/3-2M+5/3M2M－5/3-M0M－1/3M－2/32M－5/3↑－M－3M+5/30－5x15/311/25/60－1/601/610/30x410（1/2）1/21－1/2－11/22－5－5/2－25/605/60－5/601/2↑1/60－5/6－M－M+5/6－5－2x12/3101/3－11/31－1/3x220112－1－21－－5－2－11/311/3－1－1/300－1/3－1－1/3－M+1－M+1/3∴x*=（，2，0，0，0）T最優(yōu)目標(biāo)函數(shù)值minz=－maxz/=－（－）=13、用大M法求解如下線性規(guī)劃模型：minz=540x1＋450x2＋720x3解：用大M法，先化為等效的標(biāo)準(zhǔn)模型：maxz/=－540x1－450x2－720x3s.t.增加人工變量x6、x7，得到：maxz/=－540x1－450x2－720x3－Mx6－Mx7s.t大M法單純形表求解過(guò)程如下：CBXBb－540－450－72000－M－MθLx1x2x3x4x5x6x7－Mx670359－101070/3－Mx730（9）530－10130/9=10/3－12M－10M－12MMM－M－M12M－540↑10M－45012M－720－M－M00－Mx660010/3（8）－11/31－1/360/8=2.5－540x110/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-540↑MM/3－600－M/3+60－720x315/205/121－1/81/241/8－1/2415/2/5/12=18－540x15/61（5/12）01/24－1/8－1/241/85/6/5/12=2－540－572－720－135/2475/12－135/2－75/20125↑0135/2－475/12135/2－M75/2－M－720－450x320/3－1011/61/61/6－1/6x2212/5101/10－3/10－1/103/10－5700－360－450－7207515－75－15－18000－75－1575－M15－M∴該對(duì)偶問(wèn)題的最優(yōu)解是x*=（0，2，，0，0）T最優(yōu)目標(biāo)函數(shù)值minz=－（－5700）=570014、用單純形法求解線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)形式有加入人工變量則為列出單純形表Cj－30100－M-MCBXBbx1x2x3x4x5x6x70-M-Mx4x6x74191-201[1]31-111000-10010001-Z10M-2M-34M10-M0000-Mx4x2x73163-2[6]0102-141001-13-11-3001-Z6M6M-304M+103M-4M000-3x4x2x103100101001/3[2/3]100-1/201/2-1/20-1/21/21/31/6-Z300303/2-M-3/2-M+1/2001x4x2x305/23/20-1/23/2010001100-1/2-1/43/41/21/4-3/4-1/21/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ì)算Cj－3－200MCBXBbx1x2x3x4x50Mx3x521223[1]4100-10123-Z-12M3M+34M+20-M0-2Mx2x5242-5101-40-101-Z4-4M-5M-10-4M-2-M0X*=(0,2,0,0,4)’Z*=4M-4說(shuō)明原問(wèn)題無(wú)解寫對(duì)偶問(wèn)題（10）寫出下列線性繪畫(huà)問(wèn)題的對(duì)偶問(wèn)題 解： 2、寫出下述線性規(guī)劃的對(duì)偶問(wèn)題解3、寫出下列線性規(guī)劃的對(duì)偶問(wèn)題解：4、寫出下列線性規(guī)劃的對(duì)偶問(wèn)題解

對(duì)偶性質(zhì)1、已知線性規(guī)劃問(wèn)題如下：MaxZ=已知該問(wèn)題的解為（2，4）利用對(duì)偶性質(zhì)寫出對(duì)偶問(wèn)題的最優(yōu)解。解：該問(wèn)題的對(duì)偶問(wèn)題為： 將X=（2，4）T代入原問(wèn)題可知：〉1為嚴(yán)格不等式，所以由對(duì)偶問(wèn)題性質(zhì)可知：解之得：所以Y=（1/5，0，1）TMinZ=142、已知線性規(guī)劃問(wèn)題 用圖解法求對(duì)偶問(wèn)題的解；利用(b)的結(jié)果及對(duì)偶性質(zhì)求原問(wèn)題解。答案：(對(duì)偶問(wèn)題的最優(yōu)解為；(依據(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ōu)值為。試用對(duì)偶理論找出原問(wèn)題的最優(yōu)解。解先寫出它的對(duì)偶問(wèn)題s.t.① ②③④⑤將的值代入約束條件，得②，③，④為嚴(yán)格不等式；設(shè)原問(wèn)題的最優(yōu)解為，由互補(bǔ)松弛性得。因；原問(wèn)題的兩個(gè)約束條件應(yīng)取等式，故有求解后得到；故原問(wèn)題的最優(yōu)解為；最優(yōu)值為。4、已知下列問(wèn)題的最優(yōu)解為X*=(1/7,11/7),用互補(bǔ)松弛定理求其對(duì)偶問(wèn)題的最優(yōu)解。解：第一步，寫出對(duì)偶問(wèn)題第二步，將LP，DP都化為標(biāo)準(zhǔn)型第三步：將最優(yōu)解代入標(biāo)準(zhǔn)型中，確定松弛變量取值第四步：利用互補(bǔ)松弛定理∴Y3*=0∴Y1S=0Y2S=0第五步：將Y3*=0Y1S=0Y2S=0代入約束條件則有∴對(duì)偶問(wèn)題的最優(yōu)解為Y*=(4/7,5/7,0)’5、已知線性規(guī)劃問(wèn)題：，試用對(duì)偶理論證明上述線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。證明：首先看到該問(wèn)題存在可行解，例如，而上述問(wèn)題的對(duì)偶問(wèn)題為：由第一約束條件可知對(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）用圖解法解得（3）由互補(bǔ)松弛性定理知道，又由解之，可得原問(wèn)題最優(yōu)解

對(duì)偶單純形法（15）1、用對(duì)偶單純形法解下列線性規(guī)劃問(wèn)題解：先化為標(biāo)準(zhǔn)型約束條件兩邊同乘(-1)列單純形表Cj－15－24－500CBXBbx1x2x3x4x500x4x5－2－10－5[-6]-2-1-11001-15-24-50045-240x2x51/3-1/30-5101/6[-2/3]-1/6-1/301-150-1-4033/212-24-5x2x31/41/2-5/415/21001-1/41/21/4-3/2-15/200-7/2-3/2X*=(0,1/4,1/2)’Y*=(7/2,3/2)2、用對(duì)偶單純形法解下列線性規(guī)劃問(wèn)題解：改寫為標(biāo)準(zhǔn)形式列單純形表如下：Cj－4－12－1800CBXBbx1x2x3x4x500x4x5－3－5－100[-2]-3-21001-4-12-1800690-12x4x2-35/2-1001[-3]1100-1/2-40-60-6421218-12x3x213/21/3-1/30110-1/31/30-1/2-200-2-6X*=(0,3/2,1)’Y*=(2,6)3、用對(duì)偶單純形法求解下面的問(wèn)題：解：令，則問(wèn)題可以標(biāo)準(zhǔn)化為：取為初始基，則是非基可行解，但，是對(duì)偶可行解，建立單純形表（見(jiàn)表4-1）計(jì)算結(jié)果如下：最優(yōu)解?；蜃顑?yōu)解。本例如果用單純形法計(jì)算，確定初始基可行解時(shí)，還需要引入兩個(gè)人工變量，計(jì)算量要多于對(duì)歐單純形法。表3-1：C備注-4-4L=2K=4-1-1L=1K=2-1/2-1/2L=2K=1或3靈敏度分析1、已知線性規(guī)劃的標(biāo)準(zhǔn)形式為其最優(yōu)單純形表如下Cj－12100CBXBbx1x2x3x4x520x2x56101310111101-Z-12-30-1-20問(wèn)：(1)當(dāng)C1由－1變?yōu)?時(shí)，求新問(wèn)題的最優(yōu)解(2)討論C2在什么范圍內(nèi)變化時(shí)，原有的最優(yōu)解仍是最優(yōu)解解：由表可知，C1是非基變量的價(jià)值系數(shù)，因此C1的改變只影響σ1可見(jiàn)最優(yōu)性準(zhǔn)則已不滿足，繼續(xù)迭代Cj42100CBXBbx1x2x3x4x520x2x56101[3]10111101610/3-Z-1220-1-2024x2x18/310/301102/31/32/31/3-1/31/3-Z-56/300-5/3-8/3-2/3(2)要使原最優(yōu)解仍為最優(yōu)解，只要在新的條件下滿足σ≤0成立，因?yàn)閤2是基變量，所以所有的σ值都將發(fā)生變化σ＝C-CBB-1A即則c2’≥1c2+△c2≥1△c2≥-1所以當(dāng)x2的系數(shù)△c2≥-1時(shí)，原最優(yōu)解仍能保持為最優(yōu)解。2．已知線性規(guī)劃問(wèn)題及其最優(yōu)單純形表Cj－1－14000CBXBbx1x2x3x4x5x6－104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2若右端列向量，求新問(wèn)題的最優(yōu)解。解：因?yàn)椋?小于0，因此繼續(xù)迭代Cj－1－14000CBXBbx1x2x3x4x5x6－104x1x5x3－152100-1/322/30011/301/3010[-2/3]11/3-Z-90-40-10-2σj/arj123004x6x5x33/27/23/2-3/23/21/21/23/21/2001-1/21/21/2010100-Z-6-3-30-200∴新問(wèn)題的最優(yōu)解為X*=(0,0,3/2,0,7/2,3/2)’Z*=63、已知線性規(guī)劃問(wèn)題及其最優(yōu)單純形表最優(yōu)單純形表如下：Cj23100CBXBbx1x2x3x4x523x1x2121001－124－1－11610/3-Z-800-3-5－1若p3由原來(lái)的，最優(yōu)解將如何改變？解：計(jì)算∴繼續(xù)迭代Cj23100CBXBbx1x2x3x4x523x1x21210011/15[7/30]4－1－111560/7-Z-8001/6-5－121x1x33/760/710-2/7-30/70130/7-30/7－9/7-30/71560/7-Z-66/70-5/70-30/7－12/7X*=(3/7,0,60/7,0,0)Z*=66/7(仍以例2為例)已知線性規(guī)劃問(wèn)題及其最優(yōu)單純形表Cj－1－14000CBXBbx1x2x3x4x5x6－104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2現(xiàn)增加一個(gè)新變量x7，且c7=3，p7=(3,1,-3)’，求新問(wèn)題的最優(yōu)解。解：由表知：∴∴繼續(xù)迭代Cj－1－140003CBXBbx1x2x3x4x5x6x7－104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3[3]-20-Z-170-40-10-26304x7x5x31/956/913/31/32/30-1/916/92/30011/92/91/3010-2/95/91/3100-Z-53/3-2-10/30-5/30-2/30∴X*=(0,0,13/3,0,56/9,0,1/9)’Z*=53/35．已知線性規(guī)劃問(wèn)題及其最優(yōu)單純形表Cj－1－14000CBXBbx1x2x3x4x5x6－104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2現(xiàn)增加新約束，求新問(wèn)題的最優(yōu)解。解：將原問(wèn)題的最優(yōu)解代入新增約束不滿足新增加的約束條件，因此引入松弛變量x7后，新增約束變?yōu)椋舆M(jìn)最優(yōu)表得：Cj－1－140000CBXBbx1x2x3x4x5x6x7－1040x1x5x3x71/3613/317100-3-1/322/3100161/301/300100-2/311/30[3]-201-Z-170-40-10-20－1040x1x5x3x71/3613/3-81000-1/322/3-400161/301/3-10100-2/311/3[-4]0001-Z-170-40-10-20111/2－1040x1x5x3x65/3411/3210001/311/3100101/2-1/41/41/401000001-1/61/41/12-1/4-Z-130-20-1/200-1/2∴X*=(5/3,0,11/3,0,4,2,0)’Z*=135、線性規(guī)劃問(wèn)題用單純形法求解得最終單純形表如下表所示。x1x2x3x4x5x1611110X51003111cj-zj0-3-1-20試說(shuō)明分別發(fā)生如下變化時(shí)，新的最優(yōu)解是什么？（1）目標(biāo)函數(shù)變?yōu)?；?）約束條件右端項(xiàng)由變?yōu)椋唬?）增添一個(gè)新的約束。解：（1）cj→23100θiCBxBbx1x2x3x4x52x161111020x5100[3]1110cj-zj01-1-202x18/3102/32/3-1/323X210/3011/31/31/30cj-zj00-4/3-7/3-1/3因?yàn)樗械臋z驗(yàn)數(shù)均小于等于零。故最優(yōu)解為（2）因?yàn)?。所以cj→2-1100θiCBxBbx1x2x3x4x52x13111100x5703111cj-zj0-3-1-20因?yàn)樗械臋z驗(yàn)數(shù)均小于等于零，故最優(yōu)解為（3）由于，所以原問(wèn)題的最優(yōu)解不是該問(wèn)題的最優(yōu)解。在約束條件左右兩端同時(shí)乘以“-1”，并加上松弛變量，得到cj→2-11000θiCBxBbx1x2x3x4x5x62x161111000x5100311100x6-210-2001cj-zj0-3-1-2002x161111000x5100311100x6-80-1[-3]-101cj-zj0-3-1-2002x110/312/302/301/30x522/308/302/311/31x38/301/311/30-1/3cj-zj0-8/30-5/30-1/3因?yàn)樗械臋z驗(yàn)數(shù)均小于等于零，故最優(yōu)解為

第三章運(yùn)輸問(wèn)題（15）1、安排一個(gè)使總運(yùn)費(fèi)最低的運(yùn)輸計(jì)劃，并求出最低運(yùn)費(fèi)。運(yùn) 銷地價(jià)運(yùn)價(jià)產(chǎn)產(chǎn)地產(chǎn)A1A2A3A4產(chǎn)量161110950210761470312881130需求量30405030要求：先用最小元素法求出一個(gè)初始方案，再用閉回路法，求檢驗(yàn)數(shù)。如果不是最優(yōu)，改進(jìn)為最優(yōu)。解：1）先用最小費(fèi)用法（最小元素法）求此問(wèn)題的初始基本可行解：地產(chǎn)地用費(fèi)銷地產(chǎn)地用費(fèi)銷A1A2A3A4Si16111095030××20210761470×2050×312881130×20×10dj30405030150150∴初始方案：Z=6×30+9×20+7×20+6×50+8×20+11×10=10702）用閉回路法，求檢驗(yàn)數(shù)：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷A1A2A3A4Si1611－510－595030××20210－37614－470×2050×312－488－11130×20×10dj30405030150150從上表可看出，所有檢驗(yàn)數(shù)≤0，已得最優(yōu)解?！嘣撝概蓡?wèn)題的最優(yōu)方案就是上面用“最小費(fèi)用法”求得的初始方案求出最小費(fèi)用Z=6×30+9×20+7×20+6×50+8×20+11×10=10702、給定下列運(yùn)輸問(wèn)題：（表中數(shù)據(jù)為產(chǎn)地Ai到銷地Bj的單位運(yùn)費(fèi)）B1B2B3B4siA1A2A312348765910119108015dj82212181）用最小費(fèi)用法求初始運(yùn)輸方案，并寫出相應(yīng)的總運(yùn)費(fèi)；（5分）2）用1）得到的基本可行解，繼續(xù)迭代求該問(wèn)題的最優(yōu)解。（10分）解：用“表上作業(yè)法”求解。1）先用最小費(fèi)用法（最小元素法）求此問(wèn)題的初始基本可行解：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA112341082××A2876520××218A391011930×2010×dj8221218606082B82B1B2A1218218B3B4A22010B2B3A3Z=1×8+2×2+6×2+5×18+10×20+11×10=4242）①用閉回路法，求檢驗(yàn)數(shù)：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA112304－21082××A28－47－26520××218A39010119130×2010×dj82212186060∵=1＞0，其余≤0∴選作為入基變量迭代調(diào)整。②用表上閉回路法進(jìn)行迭代調(diào)整：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA1123－14－31082××A28－37－16520××128A3901011－1930×20×10dj82212186060調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)≤0，已得最優(yōu)解?！嘧顑?yōu)方案為：882B1B2A1128128B3B4A22010B2B4A3最小運(yùn)費(fèi)Z=1×8+2×2+6×12+5×8+10×20+9×10=4143、下列是將產(chǎn)品從三個(gè)產(chǎn)地運(yùn)往四個(gè)銷地的運(yùn)輸費(fèi)用表。運(yùn) 銷運(yùn)價(jià)地價(jià)產(chǎn)產(chǎn)產(chǎn)地A1A2A3A4產(chǎn)量19129650273776036591150需求量40406020要求：⑴用最小費(fèi)用法建立運(yùn)輸計(jì)劃的初始方案；⑵用位勢(shì)法做最優(yōu)解檢驗(yàn)；⑶求最優(yōu)解和最優(yōu)方案的運(yùn)費(fèi)。解：⑴先用最小費(fèi)用法（最小元素法）求此問(wèn)題的初始基本可行解：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷A1A2A3A4Si19129650××30202737760×4020×3659115040×10×dj4040602016016030203020A3A41404010A1A334020A2A32初始方案總運(yùn)費(fèi)Z=9×30+6×20+3×40+7×20+6×40+9×10=980⑵按題目要求用位勢(shì)法，作最優(yōu)解檢驗(yàn)：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷A1A2A3A4ui190120960××3020277377－2－9×4020×36509110－740×10×Vj9121618所有檢驗(yàn)數(shù)如下：＝＝9－0－9＝0，＝＝12－0－12＝0，＝＝7－（－9）－9＝7，＝＝7－（－9）－18＝－2，＝＝5－（－7）－12＝0，＝＝11－（－7）－18＝0。⑶再用閉回路法求最優(yōu)解和最優(yōu)方案的運(yùn)費(fèi)，先檢驗(yàn)：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷A1A2A3A4Si19－312－79650××302027－3377－360×4020×3650911－55040×10×Dj40406020160160∵所有檢驗(yàn)數(shù)≤0，∴該方案已是最優(yōu)方案，不需要再調(diào)整。30203020A3A414010A1A334020A2A32最優(yōu)方案的運(yùn)費(fèi)Z=9×30+6×20+3×40+7×20+6×40+9×10=9804、給定下列運(yùn)輸問(wèn)題：（表中數(shù)據(jù)為產(chǎn)地Ai到銷地Bj的單位運(yùn)費(fèi)）B1B2B3B4siA1A2A32011

86

59

10

2

187

4

15

1015dj

33

12121）用最小費(fèi)用法求初始運(yùn)輸方案，并寫出相應(yīng)的總運(yùn)費(fèi)；（4分）2）用1）得到的基本可行解，繼續(xù)迭代求該問(wèn)題的最優(yōu)解。（10分）解：用“表上作業(yè)法”求解。1）先用最小費(fèi)用法（最小元素法）求此問(wèn)題的初始基本可行解：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA1201186532××A25910210×××10A31874115×1122Dj331212303032B32B1B2A11212B1212B2B4A3B310A2B4Z=20×3+11×2+2×10+7×1+4×12+1×2=1592）①用閉回路法，求檢驗(yàn)數(shù)：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA12011806－1532××A25129－110－5210×××10A318－274115×1122Dj3312123030∵=12＞0，其余≤0∴選作為入基變量迭代調(diào)整。②用表上閉回路法進(jìn)行迭代調(diào)整：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA12011812611523××A259－1310－152101××9A318－147－124115××123Dj3312123030再選作為入基變量迭代調(diào)整。地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA120－121186－15×32×A259－110－52103××7A318－14704115××105Dj3312123030調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)≤0，已得最優(yōu)解?！嘧顑?yōu)方案為：32B32B2B3A137B1B4A2105B3B4A3最小運(yùn)費(fèi)Z=11×3+8×2+5×3+2×7+4×10+1×5=1235、某百貨公司去外地采購(gòu)A、B、C、D四種規(guī)格的服裝，數(shù)量分別為A——1500套，B——2000套，C——3000套，D——3500套，有三個(gè)城市可供應(yīng)上述規(guī)格服裝，供應(yīng)數(shù)量為Ⅰ——2500套，Ⅱ——2500套，Ⅲ——5000套。由于這些城市的服裝質(zhì)量、運(yùn)價(jià)情況不一，運(yùn)輸成本（元/套）也不一樣，詳見(jiàn)下表：ABCDⅠ10567Ⅱ8276Ⅲ9348請(qǐng)幫助該公司確定一個(gè)成本最小的采購(gòu)方案。(用伏格爾法)（12分）解：用伏格爾法確定初始調(diào)運(yùn)方案為：ABCD供Ⅰ25002500Ⅱ20005002500Ⅲ150030005005000銷150020003000350011=2；12=-2；13=3；21=1；23=5；32=-1（5分）有ij0,所以需要調(diào)整為：ABCD供Ⅰ25002500Ⅱ150010002500Ⅲ150050030005000銷150020003000350011=1；12=2；13=2；21=0；23=4；34=1（5分）因?yàn)閕j0，所以為最優(yōu)方案。MinZ=2500*7+1500*2+1000*6+1500*9+500*3+3000*4=53500（2分）由于21=0所以在此閉回路上有無(wú)窮多最優(yōu)解。6已知某運(yùn)輸問(wèn)題如下（單位：百元/噸）：（12分）單位運(yùn)價(jià)銷地產(chǎn)地B1B2B3供應(yīng)量（噸）A137218A2581012A394515需求量（噸）161217求：（1）、使總運(yùn)費(fèi)最小的調(diào)運(yùn)方案和最小運(yùn)費(fèi)。(用伏格爾法)（10分）（2）、該問(wèn)題是否有多個(gè)最優(yōu)調(diào)運(yùn)方案？若沒(méi)有，說(shuō)明為什么；若有，請(qǐng)?jiān)偾蟪鲆粋€(gè)最優(yōu)調(diào)運(yùn)方案來(lái)。（2分）解：1）用伏格爾法確定初始調(diào)運(yùn)方案為：B1B2B3供A111718A21212A331215需16121712=9；22=0；23=6；33=-3（4分）有ij0,所以需要調(diào)整為：B1B2B3供A141418A21212A312315需16121712=6；22=5；23=6；31=3（4分）因?yàn)閕j0，所以為最優(yōu)方案。MinZ=3*4+2*14+12*5+12*4+3*5=163為唯一最優(yōu)解。（2分）7已知運(yùn)輸問(wèn)題的產(chǎn)銷平衡表與單位運(yùn)價(jià)表如下表所示。銷地甲乙丙丁產(chǎn)量A327650B752360C254525銷量60402015試用表上作業(yè)法求出最優(yōu)解。解：本問(wèn)題是產(chǎn)銷平衡問(wèn)題。根據(jù)最小元素法，初始可行解為：甲乙丙丁產(chǎn)量A104050B25201560C2525銷量60402015135采用位勢(shì)法，可得檢驗(yàn)數(shù)如下表所示（為了區(qū)別，檢驗(yàn)數(shù)用“括號(hào)里的數(shù)字”表示）甲乙丙丁產(chǎn)量UiA10（0）40（0）（9）（7）500B25(0)（-1）20(0)15(0)604C25(0)（4）（7）（7）25-1銷量60402015135Vj32-2-1因?yàn)椋˙，乙）的檢驗(yàn)數(shù)為-1，所以該初始可行解非最優(yōu)解。從空格（B，乙）出發(fā)的閉回路為（B，乙）——（B，甲）——（A，甲）——（A，乙）——（B，乙）。該閉回路的偶數(shù)頂點(diǎn)位于格（B，甲）和（A，乙），由于所以可得如下可行解甲乙丙丁產(chǎn)量UiA35（0）15（0）（8）（6）500B(1)25（0）20(0)15(0)603C25(0)（4）（6）（6）25-1銷量60402015135Vj32-10由于所有空格的檢驗(yàn)數(shù)均大于零。所以得到唯一最優(yōu)解。

匈牙利法（15）1、求解指派問(wèn)題，并求出最小費(fèi)用。Minz=（cij）4×4=解：用“匈牙利法”求解。效率矩陣表示為：行約簡(jiǎn)標(biāo)號(hào)列約簡(jiǎn)行約簡(jiǎn)標(biāo)號(hào)列約簡(jiǎn)至此已得最優(yōu)解：∴最小費(fèi)用W=8+17+16+19=602、有甲、乙、丙、丁四個(gè)人，要分別指派他們完成A、B、C、D四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示：ABCD甲21097乙154148丙13141611丁415139問(wèn)：應(yīng)該如何指派，才能使總的消耗時(shí)間為最少？解：用“匈牙利法”求解。效率矩陣表示為：行約簡(jiǎn)標(biāo)號(hào)列約簡(jiǎn)行約簡(jiǎn)標(biāo)號(hào)列約簡(jiǎn)√√√√至此已得最優(yōu)解：∴使總消耗時(shí)間為最少的分配任務(wù)方案為：甲→C，乙→B，丙→D，丁→A。此時(shí)總消耗時(shí)間W=9+4+11+4=283、一個(gè)公司經(jīng)理要分派4個(gè)推銷員去4個(gè)地區(qū)推銷某種商品。4個(gè)推銷員各有不同的經(jīng)驗(yàn)和能力，因而他們?cè)诿恳坏貐^(qū)能獲得的利潤(rùn)不同，其估計(jì)值如下表所示：D1D2D3D4甲35272837乙28342940丙35243233丁24322528問(wèn)：公司經(jīng)理應(yīng)怎樣分派4個(gè)推銷員才使總利潤(rùn)最大？解：用求極大值的“匈牙利法”求解。效率矩陣表示為：行約簡(jiǎn)M－C行約簡(jiǎn)M－CijM=40標(biāo)號(hào)列約簡(jiǎn)所畫(huà)（）0元素少于n（n＝4），未得到最優(yōu)解，需要繼續(xù)變換矩陣（求能覆蓋所有0元素的最少數(shù)直線集合）：標(biāo)號(hào)列約簡(jiǎn)√√√√√√標(biāo)號(hào)未被直線覆蓋的最小元素為cij=2,在未被直線覆蓋處減去2，在直線交叉處加上2。標(biāo)號(hào)∴得最優(yōu)解：∴使總利潤(rùn)為最大的分配任務(wù)方案為：甲→D1，乙→D4，丙→D3，丁→D2。此時(shí)總利潤(rùn)W=35+40+32+32=1394、求解系數(shù)矩陣的指派問(wèn)題解：先作等價(jià)變換如下現(xiàn)在已可看出，最優(yōu)指派為5、用匈牙利法求解下列的指派問(wèn)題，已知效率矩陣如下：。√√√解：→√√√由于得到了5個(gè)獨(dú)立零元素，故可得最優(yōu)指派方案。本題的最優(yōu)解為：。這樣可使目標(biāo)函數(shù)最小，為3+2+4+3+9=21。6、某5×5指派問(wèn)題效率矩陣如下，求解該指派問(wèn)題。解：對(duì)C進(jìn)行行、列變換，減去各行各列最小元素用圈0法對(duì)C1進(jìn)行行列檢驗(yàn)，得到對(duì)C2中所有不含圈0元素的行打√，如第5行對(duì)打√的行中，所有0元素所在列打√，如第1列對(duì)所有打√列中圈0元素所在行打√，如第3行重復(fù)上述(2),(3)步，直到不能進(jìn)一步打√為止對(duì)未打√的每一行劃一直線，如1，2，4行，對(duì)已打√的列劃一縱線，如第1列，即得到覆蓋當(dāng)前0元素的最少直線數(shù)。見(jiàn)C3第5步：對(duì)矩陣C3作進(jìn)一步變換，增加0元素在未被直線覆蓋過(guò)的元素中找出最小元素，將打√行的各元素減去這個(gè)最小元素，將打√列的各元素加上這個(gè)最小元素(以避免打√行中出現(xiàn)負(fù)元素)，這樣就增加了0元素的個(gè)數(shù)。對(duì)C3進(jìn)行變換，最小元素為2，對(duì)打√的第3，5行各元素都減去2，對(duì)打√的第1列各元素都加上2，得到矩陣C4令決策變量矩陣中x12=x24=x35=x43=x51=1,其余xij=0

隱枚舉法1、用隱枚舉法求解規(guī)模0－1規(guī)劃問(wèn)題解：由于本題過(guò)濾條件不好選，所以開(kāi)始不設(shè)過(guò)濾條件點(diǎn)過(guò)濾條件約束Z值(x2,x1,x4,x3)(4)(1)(2)(3)(0,0,0,0)×(0,0,0,1)√×(0,0,1,0)×(0,0,1,1)×(0,1,0,0)√×(0,1,0,1)√×(0,1,1,0)√×(0,1,1,1)√√√3(1,0,0,0)×(1,0,0,1)×(1,0,1,0)×(1,0,1,1)×(1,1,0,0)×(1,1,0,1)×(1,1,1,0)×(1,1,1,1)×此例的最優(yōu)解X*=(0,1,1,1)’minz=3

割平面法1、用割平面法解整數(shù)規(guī)劃問(wèn)題將原整數(shù)規(guī)劃問(wèn)題稱為原問(wèn)題A0，不考慮整數(shù)條件的伴隨規(guī)劃稱為問(wèn)題B0，用單純形法求解B0，得最優(yōu)單純形表Cj1100CBXBx1x2x3x411x2x17/43/401103/4-1/41/41/4-Z-5/200-1/2-1/2問(wèn)：原問(wèn)題的解是多少？解：x1=3/4,x2=7/4均不滿足整數(shù)條件，選x1，則含x1的約束方程為：將所選的約束方程中非基變量的系數(shù)及常數(shù)項(xiàng)進(jìn)行拆分處理。7/4=1+3/4-5/2=-3+1/21/4=0+1/4求割平面方程將割平面方程加到伴隨規(guī)劃的最終單純形表中，用對(duì)偶單純形法繼續(xù)求解Cj11000CBXBx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4[-3/4]1/41/4-1/4001-Z-5/200-1/2-1/202/32110x2x1x311101010000101/31/31-1/3-4/3-Z-2000-1/3-2/3X*=(1,1)’Z*=22、

圖和網(wǎng)絡(luò)分析1、求下圖中從v1到v3短路。解：令P(v1)=0，k=v1；T(vj)=+∞。當(dāng)k=v1時(shí)，T(v2)=P(v1)+1=1,λ(v2)=v1;T(v4=P(v1)+2=2,λ(v4=v1;所有T標(biāo)號(hào)中T(v2)最小，故P(v2)=T(v2)=1，k=v2。當(dāng)k=v2時(shí)，T(v3)=P(v2)+7=8,λ(v3)=v2;T(v6)=P(v2)+3=4,λ(v6)=v2;T(v4)<P(v2)+3，故v4的T標(biāo)號(hào)不變;所有T標(biāo)號(hào)中T(v4)最小，故P(v4)=T(v4)=2，k=v4。當(dāng)k=v4時(shí)，T(v6)==P(v3)+2，可不變;T(v5)=P(v3)+2=4,λ(v5)=v4;所有T標(biāo)號(hào)中T(v6)最小，故P(v6)=T(v6)=4，k=v6。當(dāng)k=v6時(shí)，T(v3)=P(v6)+3=7,λ(v3)=v6所有T標(biāo)號(hào)中T(v5)最小，故P(v5)=T(v5)=4，k=v5。當(dāng)k=v5時(shí)，T(v3)<P(v5)+6，故v3的T標(biāo)號(hào)不變;所有T標(biāo)號(hào)中T(v3)最小，故P(v3)=T(v3)=7。所有的點(diǎn)都具有P標(biāo)號(hào)，算法結(jié)束。從v1至v3的最短路為：v1→v2→v6→v3。2、電信公司要在15個(gè)城市之間鋪設(shè)光纜，這些城市的位置及相互之間的鋪設(shè)光纜的費(fèi)用如下圖所示。試求出一個(gè)連接在15個(gè)城市的鋪設(shè)方案，使得總費(fèi)用最小。解：費(fèi)用最小的鋪設(shè)方案對(duì)應(yīng)于光纜圖的最小支撐樹(shù)。求得最小支撐樹(shù)為：最小費(fèi)用為28。3、求出從vs到vt的最大流，弧旁的數(shù)字是弧的容量。解：以零流作為初始流，計(jì)算增廣鏈并調(diào)整流量，過(guò)程如下：可知，最大流量為5，最小截集為，其中，。

決策分析1、設(shè)三個(gè)備選投資方案的決策益損如下表：銷售狀態(tài)收益值(萬(wàn)元)可行方案銷路好銷路一般銷路差銷路極差A(yù)5025–25–45B7030–40–80C3015–5–10問(wèn)題：(1)試用最大最大決策標(biāo)準(zhǔn)選擇方案；(2)當(dāng)α取何值時(shí)，用現(xiàn)實(shí)主義決策標(biāo)準(zhǔn)和用最大最大決策標(biāo)準(zhǔn)選擇的方案相同?解：2、已知某企業(yè)有下表所示的情況，請(qǐng)選擇所用策略。表中效益值的單位為萬(wàn)元。效益自然狀態(tài)Sj及值aij概率P(Sj)策略diS1（產(chǎn)品銷路好）P(S1)=0.3S2（產(chǎn)品銷路一般）P(S2)=0.5S3（產(chǎn)品銷路差）P(S3)=0.2d1（按甲方案生產(chǎn)）402615d2（按乙方案生產(chǎn)）353020d3（按丙方案生產(chǎn)）302420請(qǐng)用決策樹(shù)來(lái)進(jìn)行決策。解：來(lái)說(shuō)明單級(jí)決策樹(shù)的畫(huà)法和最優(yōu)期望益損值準(zhǔn)則的決策方法。步驟如下：銷路好P(S1)=0.3△40d1=28銷路一般P(S2)=0.5△26銷路差P(S3)=0.2△1529.5\\d2=29.5銷路好P(S1)=0.3△35決選乙方案銷路一般P(S2)=0.5△30策銷路差P(S3)=0.2△20\\d3=25銷路好P(S1)=0.3△30銷路一般P(S2)=0.5△24銷路差P(S3)=0.2△203、公司有50000元多余資金，如用于某項(xiàng)投資，估計(jì)成功率為96%，成功時(shí)可獲利12%，若失敗，將喪失全部資金。如果把資金存入銀行，則可穩(wěn)得利息6%。為獲取更多情報(bào)，該公司可求助于咨詢服務(wù)，咨詢費(fèi)用為500元，但咨詢意見(jiàn)只能提供參考。該咨詢公司過(guò)去類似的200例咨詢意見(jiàn)實(shí)施結(jié)果如下表所示。實(shí)施結(jié)果咨詢意見(jiàn)投資成功投資失敗合計(jì)可以投資154次2次156次不宜投資2次6次44次合計(jì)192次8次200次問(wèn)：該公司是否值得求助于咨詢服務(wù)？應(yīng)如何安排多余資金？解：根據(jù)以上分析，可以完成決策樹(shù)的全部?jī)?nèi)容。見(jiàn)下圖：P（E1）=0.9637606000投資P（E2）=0.043760-50000不咨詢存銀行30004272P（E1∣T1）=0.9875272P（E2∣T1）=0.0136000咨詢5272投資-500004772T1存銀行3000