運籌學(xué)試題庫

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