PAGE共2頁(yè)，第4頁(yè)2014年招收攻讀碩士學(xué)位研究生入學(xué)考試試卷科目代碼：855科目名稱：線性規(guī)劃適用專業(yè)名稱：管理科學(xué)與工程考生注意：請(qǐng)將答案寫在答題紙上，寫在本題簽及草紙上無效?？荚嚭蟊绢}簽同答題紙一并交回。一.判斷題.正確的劃√,否則劃×(每小題3分,共15分).1.若S1和S2都是凸集，則集合也是凸集.2.在圖是一棵樹的充要條件是G不含圈，且恰有條邊.3.在圖中，偶點(diǎn)的個(gè)數(shù)為偶數(shù)，奇點(diǎn)的個(gè)數(shù)為奇數(shù).4.在網(wǎng)絡(luò)中，最大流的流量不會(huì)超過任一截的容量.5.若線性規(guī)劃的原問題存在可行解，則其對(duì)偶問題也一定存在可行解.二.解答下列線性規(guī)劃問題(共35分)：1.(10分)用圖解法求解下列線性規(guī)劃問題:2.(10分)寫出下列線性規(guī)劃問題的對(duì)偶問題:3.(15分)對(duì)于下列線性規(guī)劃問題:（1）求出所有基解;（2）指出哪些解是基本可行解;（3）指出哪個(gè)解是最優(yōu)解.三.計(jì)算下列各題（共35分）:1.(15分)求下圖從到各點(diǎn)的最短路2.(20分)在下圖所示的網(wǎng)絡(luò)中，弧旁的數(shù)字為.(1)求此網(wǎng)絡(luò)的最大流.(2)求一個(gè)最小截集及對(duì)應(yīng)的容量.四.(25分)用二階段法求解下列線性規(guī)劃問題:五.(25分)某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，每種產(chǎn)品要經(jīng)過A、B、C三個(gè)車間進(jìn)行加工。每種單位產(chǎn)品所需工時(shí)及各車間每天可用工時(shí)分別如下表所示.產(chǎn)品Ⅰ所需臺(tái)時(shí)產(chǎn)品Ⅱ所需臺(tái)時(shí)每天可用臺(tái)時(shí)A車間1040B車間02120C車間32180每單位A需1噸原料，利潤(rùn)為20萬(wàn)元；每單位B需6噸原料，利潤(rùn)為50萬(wàn)元，每天所用原料只能供應(yīng)360噸；問如何安排生產(chǎn)使得獲得利潤(rùn)最大？六.(15分)設(shè)有線性規(guī)劃問題P和D為（P）（D）其中都是大于零的實(shí)數(shù)，說明這兩個(gè)問題的最優(yōu)解及最優(yōu)值之間的關(guān)系。2013年招收攻讀碩士學(xué)位研究生入學(xué)考試試卷代碼：857科目名稱：線性規(guī)劃適用專業(yè)名稱：管理科學(xué)與工程考生注意：請(qǐng)將答案寫在答題紙上，寫在本題簽及草紙上無效?？荚嚭蟊绢}簽同答題紙一并交回。一.判斷題.正確的劃√,錯(cuò)誤的劃×(每小題3分,共15分).1.若S1和S2是凸集，則集合也是凸集.2.在圖中，所有點(diǎn)的次之和是邊數(shù)的2倍.3.在圖中，奇點(diǎn)的個(gè)數(shù)為偶數(shù).4.在網(wǎng)絡(luò)中，任何一截的容量都不會(huì)超過任一可行流的流量.5.若線性規(guī)劃問題存在最優(yōu)解，則必存在最優(yōu)基本可行解.二.解答下列線性規(guī)劃問題(共35分)：1.(10分)用圖解法求解下列線性規(guī)劃問題:2.(10分)寫出下列線性規(guī)劃問題的對(duì)偶問題:3.(15分)對(duì)于下列線性規(guī)劃問題:（1）求出所有基解;（2）指出哪些解是基本可行解;（3）指出哪個(gè)解是最優(yōu)解.三.計(jì)算下列各題（共35分）:1.(15分)求下圖從到各點(diǎn)的最短路2.(20分)在下圖所示的網(wǎng)絡(luò)中，弧旁的數(shù)字為.(1)求此網(wǎng)絡(luò)的最大流.(2)求一個(gè)最小截集及對(duì)應(yīng)的容量.四.(25分)用二階段法求解下列線性規(guī)劃問題:五.(25分)某廠生產(chǎn)A、B兩種產(chǎn)品，每種產(chǎn)品都要在車間1、2加工。每種單位產(chǎn)品所需工時(shí)及車間1、2每天可用工時(shí)分別如下表所示.A所需工時(shí)（小時(shí)）B所需工時(shí)（小時(shí)）每天可用工時(shí)（小時(shí)）車間112160車間20.53/860每單位A需1噸原料，利潤(rùn)為1000元；每單位B需6噸原料，利潤(rùn)為4000元，每天所用原料只能供應(yīng)360噸；問如何安排生產(chǎn)使得