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

運(yùn)籌學(xué)試題庫 一、多項(xiàng)選擇題1、下面命題正確的是()。A、線性規(guī)劃的標(biāo)準(zhǔn)型右端項(xiàng)非零；B、線性規(guī)劃的標(biāo)準(zhǔn)型目C、線性規(guī)劃的標(biāo)準(zhǔn)型有等式或不等式約束；D、線性規(guī)劃的標(biāo)準(zhǔn)型變2、下面命題不正確的是()。BC、線性規(guī)劃有可行解則有最優(yōu)解；D、線性規(guī)劃的最優(yōu)值至多有3、設(shè)線性規(guī)劃問題(P)，它的對(duì)偶問題(D)，那么()。A、若(P)求最大則(D)求最??；B、(P)、(D)均有可行解則都C、若(P)的約束均為等式，則(D)的所有變量均無非負(fù)限制；D、(P)和(D)互為對(duì)偶。4、課程中討論的運(yùn)輸問題有基本特點(diǎn)()。AB、一定是物品運(yùn)輸?shù)膯栴}；CD目標(biāo)極小。5、線性規(guī)劃的標(biāo)準(zhǔn)型有特點(diǎn)()。B6、下面命題不正確的是()。C、線性規(guī)劃一定有可行解；D、線性規(guī)劃的最優(yōu)值至多有7、線性規(guī)劃模型有特點(diǎn)()。8、下面命題正確的是()。A、線性規(guī)劃的最優(yōu)解是基本可行解；B、基本可行解一定是最優(yōu)；C、線性規(guī)劃一定有可行解；D、線性規(guī)劃的最優(yōu)值至多有9、一個(gè)線性規(guī)劃問題(P)與它的對(duì)偶問題(D)有關(guān)系()。A、(P)有可行解則(D)有最優(yōu)解；B、(P)、(D)均有可行解則都C、(P)可行(D)無解，則(P)無有限最優(yōu)解；D、(P)(D)互為10、運(yùn)輸問題的基本可行解有特點(diǎn)()。二、簡答題(1)微分學(xué)求極值的方法為什么不適用于線性規(guī)劃的求解(2)線性規(guī)劃的標(biāo)準(zhǔn)形有哪些限制如何把一般的線性規(guī)劃化為標(biāo)準(zhǔn)形式(3)圖解法主要步驟是什么從中可以看出線性規(guī)劃最優(yōu)解有那些特點(diǎn)(4)什么是線性規(guī)劃的可行解，基本解，基可行解引入基本解和基可行解有什么作用(5)對(duì)于任意基可行解，為什么必須把目標(biāo)函數(shù)用非基變量表示出來什么是檢驗(yàn)數(shù)它有什么作用如何計(jì)算檢驗(yàn)數(shù)(6)確定換出變量的法則是什么違背這一法則，會(huì)發(fā)生什么問題(7)如何進(jìn)行換基迭代運(yùn)算(8)大M法與兩階段法的要點(diǎn)是什么兩者有什么共同點(diǎn)有什么區(qū)別(9)松弛變量與人工變量有什么區(qū)別試從定義和處理方式兩方面分析。(10)如何判定線性規(guī)劃有唯一最優(yōu)解，無窮多最優(yōu)解和無最優(yōu)解為什么(11)如何在以B為基的單純形表中，找出B－1該表是怎樣由初始表得到的(12)對(duì)偶問題的構(gòu)成要素之間，有哪些對(duì)應(yīng)規(guī)律(13)如何從原問題最優(yōu)表中，直接找到對(duì)偶最優(yōu)解(14)敘述互補(bǔ)松弛定理及其經(jīng)濟(jì)意義。(15)什么是資源的影子價(jià)格它在經(jīng)濟(jì)管理中有什么作用(16)對(duì)偶單純形法有哪些操作要點(diǎn)它與單純形法有哪些相同，哪些地方有區(qū)別(17)靈敏度分析主要討論什么問題分析的基本思路是什么四種基本情況的分析要點(diǎn)是什么三、模型建立題(1)某廠生產(chǎn)A，B，C三種產(chǎn)品，每件產(chǎn)品消耗的原料和設(shè)備臺(tái)資資源數(shù)量產(chǎn)品ABC原原料單耗機(jī)時(shí)單耗利潤000056332試制定使總利潤最大的模型。井位中確定5個(gè)鉆井探油，使總的鉆井費(fèi)用最小。若10個(gè)井位的代號(hào)為s,s,ss，相應(yīng)的鉆井123101210 178 ②選擇了s或s就不能選s，或反過來也一樣；345③在s,s,s,s中最多只能選兩個(gè)；試建立這個(gè)問題的整數(shù)規(guī)劃模5678(3)某市為方便學(xué)生上學(xué)，擬在新建的居民小區(qū)增設(shè)若干所小學(xué)。已知備選校址代號(hào)及其能覆蓋的居民小區(qū)編號(hào)如表3–2所示，問為覆蓋所有小區(qū)至少應(yīng)建多少所小學(xué)，要求建模并求解。備選備選校址代號(hào)覆蓋的居民小區(qū)編號(hào)(4)一貨船，有效載重量為24噸，可運(yùn)輸貨物重量及運(yùn)費(fèi)收入如費(fèi)收入最多的運(yùn)輸方案。貨貨物123456重量(噸)5987收入(萬1元)44357(5)運(yùn)籌學(xué)中著名的旅行商販(貨朗擔(dān))問題可以敘述如下：某旅行商販從某一城市出發(fā)，到其他幾個(gè)城市推銷商品，規(guī)定每個(gè)城市均的距離為d問商販應(yīng)選擇一條什么樣的路線順序旅行，使總的旅程最ij短。試對(duì)此問題建立整數(shù)規(guī)劃模型。四、計(jì)算及分析應(yīng)用題(1)某公司打算利用具有下列成分(見表4-1)的合金配制一種新合合金品種12345含鉛%含鋅%含錫%單價(jià)(元/kg)如何安排配方，使成本最低(2)某醫(yī)院每天各時(shí)間段至少需要配備護(hù)理人員數(shù)量見表4-26:00－10:0010:00－14:0014:00－18:0018:00－22:0022:00－2:002:00－6:00最少人數(shù)班次1234562假定每人上班后連續(xù)工作8小時(shí)，試建立使總?cè)藬?shù)最少的計(jì)劃安排2(3)某工地需要30套三角架，其結(jié)構(gòu)尺寸如圖4-1所示。倉庫現(xiàn)有長6.5米的鋼材。如何下料，使消耗的鋼材最少333(4)用圖解法求下列線性規(guī)劃的最優(yōu)解：12xxx|4x1+3x21.5|-x1+x25122x(5)把下列線性規(guī)劃化為標(biāo)準(zhǔn)形式：12312(x+x-x1(x+2x8|2x1+x-x34-2|-1x+2x1xx束10,x約束123412(6)求出下列線性規(guī)劃的所有基本解，并指出其中的基可行解和12(x+x=48|12x3+x=12j(7)求下列線性規(guī)劃的解：(1)12(2x8|1x6(3)12|x|x,|12 (x+2x4|x, 23|xx2+2x3101231-1236(8)利用大M法或兩階段法求解下列線性規(guī)劃：(1)()212123xxxxx|x1x21|2x1+x234123(3)()412min(3)()4xxx(9)對(duì)于問題(AX=b〈X0121245ccj22CXbxxxxxxBB123456x5212-12x21-11-2x14-1a8σj-1(1)把表中缺少的項(xiàng)目填上適當(dāng)?shù)臄?shù)或式子。(2)要使上表成為最優(yōu)表，a應(yīng)滿足什么條件(3)何時(shí)有無窮多最優(yōu)解(4)何時(shí)無最優(yōu)解(5)何時(shí)應(yīng)以x替換x(11)已知某線性規(guī)劃的初始單純形表和最終單純形表如表4-3，請(qǐng)把表中空白處的數(shù)字填上，并指出最優(yōu)基B及B－1。x21cjXBx42x130x410x500x601x31CB0bxxxx25100-1-1/2010-2x5x6σjx4x1x2σj0002121000(12).某個(gè)線性規(guī)劃的最終表是表4-4004-1/2-1/2-1/2-1/205-1/2bcjXBx1x2x3σj-2x300101x201000x11000CB01-2145123(2)求初始表。寫出下列線性規(guī)劃的對(duì)偶問題：23|-1x+x-34x>11231234jjijij|111122133461112233|1111221331|x2x1|1111221331(1)寫出它的對(duì)偶問題；(2)引入松弛變量，化為標(biāo)準(zhǔn)形式，再寫出對(duì)偶問題；(3)引入人工變量，把問題化為等價(jià)模型：11223367|xx22233572再寫出它的對(duì)偶問題。試說明上面三個(gè)對(duì)偶問題是完全一致的。由此，可以得出什么樣的一般結(jié)論(15)利用對(duì)偶理論說明下列線性規(guī)劃無最優(yōu)解：123(x+x+x412345兩個(gè)約束條件為≤型。ccjCXbxxxxxBB12345x3010x11-1/20-1/6σj0-40-4-2(1)求價(jià)值系數(shù)c和原線性規(guī)劃；j(2)寫出原問題的對(duì)偶問題；(3)由表4-5求對(duì)偶最優(yōu)解。(17)已知線性規(guī)劃問題1234(x+2x+x3jj(1)寫出對(duì)偶問題；(2)已知原問題的最優(yōu)解為X*=(1，1，2，0)T，求對(duì)偶問題的最(18)已知線性規(guī)劃xx123xxx33(1)寫出對(duì)偶問題；(2)求對(duì)偶問題最優(yōu)解。(19)設(shè)線性規(guī)劃問題jj〈ijji12m線性規(guī)劃 maxz=c jjj=1(2)(2)與(1)是等價(jià)的，兩者有相同的最優(yōu)解，請(qǐng)說明(2.)的m種資12m(20).已知線性規(guī)劃1234(2x+2x+x-x31234(1)寫出對(duì)偶問題，用圖解法求最優(yōu)解；(2)利用對(duì)偶原理求原問題最優(yōu)解。23(x+x+x6ccjXBx1x5σj1x311-1-1x213-30x411-22x11000x5010b6CB20(1)x的系數(shù)c在何范圍內(nèi)變化，最優(yōu)解不變?nèi)鬰=3，求新的最22(2)b在何范圍內(nèi)變化，最優(yōu)基不變?nèi)鏱=3，求新的最優(yōu)解；11(3)增加新約束－x+2x≥2，求新的最優(yōu)解；13耗耗定料AB產(chǎn)品價(jià)格原料數(shù)量5丙555產(chǎn)額341634消原(1)建立使總產(chǎn)值最大的線性規(guī)劃模型；(2)求最優(yōu)解，并指出原料A，B的影子價(jià)格；(3)產(chǎn)品甲的價(jià)格在什么范圍內(nèi)變化，最優(yōu)解不變(5)已知原料B的市場價(jià)為單位，可以隨時(shí)購買，而原料A市場無貨。問該廠是否應(yīng)購買B，購進(jìn)多少為宜新的最優(yōu)計(jì)劃是什么(6)由于某種原因，該廠決定暫停甲產(chǎn)品的生產(chǎn)，試重新制定最1212(x4(5x15|12x12|6x+2x224+t12(24)用分支定界法求解下列整數(shù)規(guī)劃問題22(951(951(25)用割平面法求解下列整數(shù)規(guī)劃問題123121212312xxxx12345 |||| ||||12345(27)用匈牙利法求解下列指派問題，已知效率矩陣分別如下：912)||| (9|||||8744222269739755(28)已知下列五名運(yùn)動(dòng)員各種泳姿的運(yùn)動(dòng)成績(各為50米)如表4-8所示，請(qǐng)問如何從中選擇一個(gè)參加200米混合泳的接力隊(duì)，使預(yù)期單位：秒趙趙錢張王周仰泳蛙泳蝶泳(29)分配甲、乙、丙、丁四個(gè)人去完成五項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)時(shí)間如表4-9所示。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個(gè)人可兼完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)。試確定總花費(fèi)時(shí)間為最少的指人人任務(wù)丙丁BDEAC(30)從甲、乙、丙、丁、戊五個(gè)人中挑選四人完成四項(xiàng)工作。已知每人完成各項(xiàng)工作的時(shí)間如表4-10所示。規(guī)定每項(xiàng)工作只能由一個(gè)人單獨(dú)去完成，每個(gè)人最多承擔(dān)一項(xiàng)任務(wù)。又假定對(duì)甲必須保證分配一如何分配工作，使完成四項(xiàng)工作總的花費(fèi)時(shí)間最少。作作工人戊丁丙9VV9VV1V15253276948234(31)求下列網(wǎng)絡(luò)圖從起點(diǎn)到終點(diǎn)的最短路線及長度。CCCCD3BD3B20A333334B134B10C94EGFFB94EGFFB323323588EGCA588EGC64648EGF68DEGF68(32).用破圈法和避圈法求下圖的最小生成樹VV121VVVVV4895486535(5(2V(33)求下列各圖的最小生成樹4454436(1)31246381713(34)寫出下面各圖中的頂點(diǎn)數(shù)、邊數(shù)及頂點(diǎn)的次數(shù)，哪些是簡單VV1V2VV1VVV65V3V1VVV323V4VV45(35)用標(biāo)號(hào)法求圖4—2中從v到各頂點(diǎn)的最短距離1V2263V25V375213V25V8V93743V64143VV747V8(36)已知8個(gè)村鎮(zhèn)，相互間距離如下表所示,已知1號(hào)村鎮(zhèn)離水來，應(yīng)如何鋪設(shè)使輸水管道最短(為便于管理和維修，水管要求在各村鎮(zhèn)處分開)。各村鎮(zhèn)間距離(單位：千米)到到2345678從1234567(37)用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流.V18469816Vt238334352V3tV52V3t135543554(38)求下列網(wǎng)絡(luò)的最小費(fèi)用最大流.括號(hào)內(nèi)的兩個(gè)數(shù)字,前一個(gè)是單位流量的費(fèi)用,后一個(gè)是該弧的流量.(2,3VV(2,3VVV1t1VtVt(2)A42中所示的中國郵遞員問題(A點(diǎn)是郵局所在地)32422323222544121和T可接收10個(gè)和25個(gè)單位，求最大流，邊上的數(shù)為c。2ijS1S2v1T2v2d2daf556f5563g(a)63g(a)63b82ee(b35a(b35cgc4(c)4工工序abcdefgh緊前工序－－－acdd,bf,g,e工工序abcdefgh緊前工序－－aaa,bccef52433336454f工序工時(shí)