運(yùn)籌學(xué)練習(xí)題

運(yùn)籌學(xué)練習(xí)題填空題1.運(yùn)輸問題中，當(dāng)總供應(yīng)量小于總需求量時(shí)，求解時(shí)需虛設(shè)一個(gè)點(diǎn)，此點(diǎn)的供應(yīng)量(或需求量)應(yīng)為。2．線性規(guī)劃中，任何基對(duì)應(yīng)的決策變量稱為。整數(shù)規(guī)劃(是或不是)線性規(guī)劃。3．用單純法求解目標(biāo)函數(shù)是最大化的線性規(guī)劃問題時(shí)，為一基本可行解，有一個(gè)檢驗(yàn)數(shù)，并且對(duì)其中是其的系數(shù)向量，那么該線性規(guī)劃問題具有解，若所有的檢驗(yàn)數(shù)非正，且存在某個(gè)非基變量的檢驗(yàn)數(shù)為零，則線性規(guī)劃問題有解。4．在用圖論解決問題時(shí)，常用表示研究的對(duì)象，對(duì)象之間的關(guān)系用表示。5．在雙代號(hào)網(wǎng)絡(luò)圖中，虛工作只表示相鄰工作之間的，不占用。6．用對(duì)偶單純型法求解線性規(guī)劃問題時(shí)，得到了檢驗(yàn)數(shù)為則對(duì)偶問題的最優(yōu)解為，假若此原問題為無界解，則其對(duì)偶問題可行解（存在或不存在）。7．在資源受限制時(shí)，時(shí)間與資源優(yōu)化的方法之一，是先將有限的資源從活動(dòng)調(diào)往活動(dòng)，以便均衡地使用資源8.決策分析的基本原則為，系統(tǒng)原則，,信息對(duì)稱、準(zhǔn)全原則.9在一個(gè)工廠中，有一個(gè)廠址選擇的決策，這屬于，生產(chǎn)品合格標(biāo)準(zhǔn)選擇屬于。10.決策的一般過程為目標(biāo)確定，，，方案選優(yōu)，決策。11.在決策中，人們只知道可能的情況是什么，但不知道各情況出現(xiàn)的可能性大小，有一個(gè)實(shí)力相對(duì)來說很小的企業(yè)，它應(yīng)該采取原則。如果知道了各情況的可能性，這屬于。12在決策中，，，損益函數(shù)是決策的三要素。13有4個(gè)人要做4件事，每人做而且只能做一件事，現(xiàn)得到了最優(yōu)指派方案，則最小可以用條線覆蓋所有的0元素，此指派問題有個(gè)獨(dú)立0元素。14在一個(gè)求最小值得運(yùn)輸問題中，有4個(gè)銷售地，5個(gè)生產(chǎn)地，則系數(shù)矩陣中有個(gè)獨(dú)立行向量，如果檢驗(yàn)數(shù)有9個(gè)大于0，其他三個(gè)x1,x2,x3為-5，-2，-3，則變?yōu)榛兞康氖恰?5在存儲(chǔ)問題中，人員外出采購等的費(fèi)用屬于，停工待料的損失屬于。16在網(wǎng)絡(luò)流中，與鏈同向的弧稱為，在增廣鏈上，與鏈同向的弧是。17用閉合回路法尋求改進(jìn)運(yùn)輸方案時(shí)，首先應(yīng)對(duì)每一空格求出

和

。18在用單純形法的計(jì)算極大值過程中，如果，并且存在，則可以判定線性規(guī)劃問題存在無窮多最優(yōu)解。19在用人工變量法求得最優(yōu)解中含有人工變量非0，則原問題，若兩階段法中第一階段的目標(biāo)函數(shù)值為0，則原問題。20現(xiàn)有一求最小值的線性規(guī)劃問題，有m個(gè)等式約束，n個(gè)小于0的變量，則對(duì)偶問題有m個(gè)，n個(gè)。二選擇題1．在線性規(guī)劃模型中，沒有非負(fù)約束的變量稱為()。A．多余變量B．松弛變量C．自由變量D．人工變量2．在雙代號(hào)網(wǎng)絡(luò)圖中，下列敘述正確的是()。A．可以有兩個(gè)起始點(diǎn)B．可以出現(xiàn)回路C．可以有兩個(gè)終點(diǎn)D．相鄰結(jié)點(diǎn)只能有一條連線3．對(duì)于m個(gè)發(fā)點(diǎn)、n個(gè)收點(diǎn)的運(yùn)輸問題，敘述錯(cuò)誤的是(

)。A．該問題的系數(shù)矩陣有m+n行B．該問題的系數(shù)矩陣的秩必為m+n-1

C．該問題的系數(shù)矩陣有m×n列

D．該問題的最優(yōu)解必唯一4．在動(dòng)態(tài)規(guī)劃中，如果某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這階段以前各狀態(tài)點(diǎn)的影響，這個(gè)性質(zhì)稱為：()。A.動(dòng)態(tài)性B.階段性C.無后效性D.優(yōu)先性5．在樹圖中，()不正確。A.若樹T有n個(gè)點(diǎn)，則其邊數(shù)為n-1B.樹中若多出一邊，必出現(xiàn)圈C.樹中點(diǎn)與點(diǎn)可以不連通D.樹中若除去一邊，必不連通6.對(duì)有m個(gè)產(chǎn)地n個(gè)銷地的運(yùn)輸問題，有下列命題①任意一個(gè)運(yùn)輸問題都有最優(yōu)解，②產(chǎn)量與銷量均為整數(shù)時(shí)必有整數(shù)最優(yōu)解，③m+n-1個(gè)變量構(gòu)成基變量的充要條件是它不包含任何閉回路，④表上作業(yè)法的條件是產(chǎn)銷平衡問題，其中正確的個(gè)數(shù)為()A.1B.2C.3D.47．下列哪項(xiàng)不屬于按決策性質(zhì)的重要性分類A序貫分類B戰(zhàn)略決策C執(zhí)行決策D管理控制8下列哪些條件可得出線性規(guī)劃問題無可行解①可行域無界②用大M法求解時(shí)，最優(yōu)解中還有非零的人工變量，③兩階段法中第一階段目標(biāo)函數(shù)值大于0④非基變量變?yōu)榛兞繒r(shí)，其列向量分量非正，A②③④B①②③C①②④D①③④9.瞬時(shí)供貨且允許缺貨的經(jīng)濟(jì)批量模型中，若訂貨費(fèi)，存儲(chǔ)費(fèi)和缺貨費(fèi)同時(shí)增加n倍，則經(jīng)濟(jì)訂貨批量A.為原來的C為原來的倍，D不變10在相同的單位時(shí)間內(nèi)，允許缺貨的訂貨次數(shù)比不允許缺貨時(shí)的訂貨次數(shù)A．一樣多B多C少D無法確定11某個(gè)常數(shù)b波動(dòng)，最優(yōu)表中引起變化的有ABCD12目標(biāo)函數(shù)為求最大值，為保持最優(yōu)基不變，的波動(dòng)值可由解不等式（）求得ABCD13原問題與對(duì)偶問題都有可行解，則A原問題有最優(yōu)解，對(duì)偶問題可能沒有最優(yōu)解B原問題與對(duì)偶問題可能都沒有最優(yōu)解C可能一個(gè)有最優(yōu)解，另一個(gè)有無界解D兩個(gè)問題都有最優(yōu)解14下列說法正確的是A截集是子圖B截量等于截集中弧的流量之和C截量不小于最大流D截量不超過最大流15在目標(biāo)函數(shù)求最大值的對(duì)偶單純形法中，如果在某一步迭代過程中出現(xiàn)了基變量某一分量小于0,其他都大于0，其對(duì)應(yīng)系數(shù)行向量全是正數(shù)，所有檢驗(yàn)數(shù)小于0，則A原問題有可行解B原問題沒有可行解C對(duì)偶問題沒有可行解D對(duì)偶問題可能有無界解16允許缺貨，備貨時(shí)間短的存儲(chǔ)模型屬于At0存儲(chǔ)策略B（s,S）策略C（t,s,S）策略D其他策略17下列屬于生產(chǎn)費(fèi)的是A手續(xù)費(fèi)B貨物的成本費(fèi)C材料費(fèi)與加工費(fèi)D繳納的罰款18在網(wǎng)絡(luò)計(jì)劃圖中的時(shí)間-費(fèi)用優(yōu)化中，下列哪一項(xiàng)是間接費(fèi)用A公司電話費(fèi)B項(xiàng)目使用的材料費(fèi)C工人的工資D購買大型設(shè)備的費(fèi)用19下列說法哪一個(gè)是正確的A次序列（3，2，4，1，0）的點(diǎn)不能構(gòu)成一個(gè)圖；B對(duì)偶問題最優(yōu)解是原問題檢驗(yàn)數(shù)的相反數(shù)；C運(yùn)輸問題與指派問題都有最優(yōu)解；D在圖論中求最短路的Dijkstra算法可以廣泛使用。20對(duì)偶單純形法的最小比值規(guī)則是為了保證A使原問題可行B使對(duì)偶問題保持可行C逐步消除原問題的不可行性D逐步消除對(duì)偶問題的不可行性21目標(biāo)函數(shù)的含義是A第一和第二目標(biāo)恰好到達(dá)目標(biāo)值，第三目標(biāo)不超過目標(biāo)值B第一、第二、第三目標(biāo)同時(shí)不超過目標(biāo)值C首先第一和第二目標(biāo)同時(shí)不超過目標(biāo)值，然后第三目標(biāo)不超過目標(biāo)值D首先第一和第二目標(biāo)同時(shí)不低于目標(biāo)值，然后第三目標(biāo)不低于目標(biāo)值三計(jì)算題1.已知線性規(guī)劃問題MAXZ=2X1+4X2+X3+X4X1+3X2+X4<=82X1+X2<=6X2+X3+X4<=6X1+X2+X3<=9X1、X2、X3、X4>=0（1）寫出其對(duì)偶問題；（2）已知原問題最優(yōu)解為X=（2，2，4，0）試根據(jù)對(duì)偶理論，直接求出對(duì)偶問題的最優(yōu)解。2．有四個(gè)工人，要分別指派他們完成四項(xiàng)不同的工作，即每人只做一件事，每件事只由一人做。每人做各項(xiàng)工作所需成本如下，問應(yīng)如何指派工作，才能使他們的總成本最小？單位：百元。工作所需成本工人ABCD甲10743乙95610丙4131411丁75343.下表給出了工序的正常、應(yīng)急的時(shí)間和成本工序緊前工序時(shí)間（天）成本時(shí)間的最大縮量（天）應(yīng)急增加成本（萬元/天）正常應(yīng)急正常應(yīng)急ABCDEFG-AAB、CDCE、F151212107413111410161310850651001208089609040524560608432324325103153512（1）繪制網(wǎng)絡(luò)圖，按正常時(shí)間計(jì)算完成項(xiàng)目的總成本和工期；（2）按應(yīng)急時(shí)間計(jì)算完成項(xiàng)目的總成本和工期；（3）按應(yīng)急時(shí)間的項(xiàng)目完工期，調(diào)整計(jì)劃使總成本最低;(4)已知項(xiàng)目縮短一天額外獲得獎(jiǎng)金4萬元，減少間接費(fèi)用2.5萬元，求總成本最低的項(xiàng)目完工期4S、A、B、C、D、E、T代表七個(gè)村鎮(zhèn)，它們之間的連線表明各村現(xiàn)有道路交通情況，連線旁的數(shù)字代表村和村之間的距離，要求沿圖中道路架設(shè)電線，使各村鎮(zhèn)全部通上電?，F(xiàn)知架線成本為10000元/公里，問應(yīng)如何架線，使總的架線成本為最小？（單位：公里）（10分）AA227TDBS555TDBS17EC413EC45.若一求極大線性規(guī)劃問題的某步單純形表為Cj23000b基變量x1x2x3x4x52x11010-1/220x400-41283x201001/43Zj2320-1/413Cj-Zj00-201/4該表是否為最優(yōu)單純形表?若是，請(qǐng)說明理由。若不是，則繼續(xù)迭代直至達(dá)到其單純形終表，并寫出該問題的最優(yōu)解。6．某地方書店希望訂購最新出版的圖書，根據(jù)以往經(jīng)驗(yàn)，新書的銷售量可能是50,100,150,200。假定每本新書訂購價(jià)為4元，銷售價(jià)為6元，剩書的處理價(jià)為2元。（1）分別用悲觀法、樂觀法及等可能法就該書店應(yīng)訂購的新書做決策；（2）建立后悔值矩陣，用后悔值法決定應(yīng)訂購的新書數(shù)；（3）書店根據(jù)以往的統(tǒng)計(jì)資料新書銷售的規(guī)律見下表，分別用期望值法與后悔值法決定訂購數(shù)量；（4）如果某市場(chǎng)調(diào)查部門能幫助書店調(diào)查銷售量的確切數(shù)字，該書店愿意付出多大的調(diào)查費(fèi)用。需求數(shù)50100150200比例（%）204030107某企業(yè)每月生產(chǎn)某零件的生產(chǎn)量為800件，該零件月需求量為500件，每次準(zhǔn)備成本為50元，每件存儲(chǔ)費(fèi)為10元，缺貨費(fèi)為8元，求最優(yōu)生產(chǎn)批量與生產(chǎn)周期8教材P431.69P993.410下表是某項(xiàng)作業(yè)的明細(xì)表，解答表后問題工序緊前工序工序時(shí)間工序緊前工序工序時(shí)間A--6GAB10B--9HEF12CA13IDH8DC5JI17EC16KDHG20FA.B12LG25求工序H，K的工作總時(shí)差與工作自由時(shí)差求出項(xiàng)目的完工時(shí)間。11某工廠正在考慮明年還是現(xiàn)在擴(kuò)大生產(chǎn)規(guī)模。由于可能出現(xiàn)的市場(chǎng)需求情況不一樣，預(yù)期利潤也不同，已知市場(chǎng)需求的概率及不同方案時(shí)的預(yù)期利潤如下表所示。對(duì)該廠來說損失1萬元效用值為0，獲利10萬元為1，對(duì)以下事件效用值無差別：（1）肯定得8萬元或以0.9的概率得10萬和0.1的概率失去1萬；（2）肯定得6萬或0.8概率得10萬和0.2失去1萬元；（3）肯定得1萬或以0.25概率得10萬和0.75概率失去1萬。（a）建立效用值表（b）分別根據(jù)實(shí)際盈利額和效用值按期望值法確定最優(yōu)決策12一軟件公司需要在自主開發(fā)一種會(huì)計(jì)軟件和接受委托進(jìn)行辦公自動(dòng)化軟件開發(fā)二者之間進(jìn)行抉擇。若自主開發(fā)，根據(jù)過去的開發(fā)經(jīng)驗(yàn)，開發(fā)一個(gè)會(huì)計(jì)軟件需要投資20萬元。若開發(fā)得成功（功能好于市場(chǎng)上已存在的任何類似產(chǎn)品）的概率為20%，能以100萬元的價(jià)格賣給一個(gè)大的軟件公司；若比較成功（好于部分市場(chǎng)產(chǎn)品）的概率為60%，則價(jià)格降為50萬元；若不成功（概率20%），則公司無法賣出該產(chǎn)品。公司若決策接受委托開發(fā)軟件，則可獲得20萬元的軟件開發(fā)費(fèi)。該軟件公司還可以出2萬元聘請(qǐng)一個(gè)咨詢公司就該產(chǎn)品的開發(fā)問題進(jìn)行咨詢，根據(jù)以往統(tǒng)計(jì)，該咨詢公司準(zhǔn)確性的概率如下表所示P(咨詢意見|成功狀態(tài))成功狀態(tài)很成功成功不成功咨詢意見可以自主開發(fā)不可自主開發(fā)0.90.50.60.10.50.4（1）畫出完整的決策樹，并根據(jù)最大期望值方法找出最優(yōu)決策路線；（2）是否請(qǐng)咨詢公司進(jìn)行咨詢，其咨詢意見的樣本信息期望值是多少？13某食品公司考慮是否參加為某運(yùn)動(dòng)會(huì)服務(wù)的投標(biāo)，以取得飲料或面包二者之間的供應(yīng)特許權(quán)。二者中任何一項(xiàng)投標(biāo)被接受的概率為40%。公司的獲利情況取決于天氣。若獲得的是飲料供應(yīng)特許權(quán)，則當(dāng)晴天時(shí)可獲利2000元；雨天時(shí)要損失2000元。若獲得的是面包供應(yīng)特許權(quán)，則不論天氣如何，都可獲利1000元。已知天氣晴好的可能性為70%。問：（1）公司是否可參加投標(biāo)？若參加，為哪一項(xiàng)投標(biāo)？（2）若再假定飲料投標(biāo)，公司可選擇供應(yīng)冷飲或咖啡。如供應(yīng)冷飲，則晴天可獲利2000元，雨天損失2000元；若供應(yīng)咖啡，則雨天可獲利2000元，晴天1000元，公司是否應(yīng)參加投標(biāo)？參加哪一項(xiàng)投標(biāo)？14某項(xiàng)工作有五個(gè)崗位，甲、乙、丙、丁、戊5人去操作，由于每人專長不同，各個(gè)工人在不同崗位上生產(chǎn)效率不一樣，具體見下表（件/分鐘），問如何分配，使這項(xiàng)工作的效率最高？IIIIIIIVV甲乙丙丁戊234173425625341523253762415（1）求下圖各點(diǎn)間的最短路（2）若從點(diǎn)1到點(diǎn)8分別有貨物100，150，80,90,120,115,140，80噸需要集中在一起存儲(chǔ)，問應(yīng)存儲(chǔ)中心建在何處恰當(dāng)？112354678101010561314547459四建模題1某醫(yī)藥公司現(xiàn)有兩個(gè)制藥廠A1和A2，三個(gè)銷售點(diǎn)B1、B2和B3。由于供不應(yīng)求，公司打算由兩個(gè)擬建的制藥廠A3和A4中選擇一個(gè)來興建新廠。新廠投產(chǎn)后，估計(jì)每月的固定成本：A3是100萬元，A4是120萬元。各銷售點(diǎn)每月藥品需求量、各制藥廠每月藥品產(chǎn)量和每箱藥品運(yùn)費(fèi)見下。在兩個(gè)擬建的制藥廠中，應(yīng)當(dāng)選擇哪個(gè)，使總成本最低（建立數(shù)學(xué)模型）？制藥廠產(chǎn)量(萬箱/月)運(yùn)資(元/箱)B1B2B3A150323A2701058A3201310A420453銷售點(diǎn)需求量（萬箱/月）B150B260B3302一個(gè)農(nóng)民需要決定在他的20畝菜地與30畝小麥地中使用肥料，農(nóng)業(yè)技術(shù)員通過對(duì)土壤的分析已經(jīng)建議每畝菜地最少需要施6千克氮，2千克磷和1.5千克鉀，每畝小麥地最少需要施8千克氮、1千克