線性規(guī)劃期末試題及答案

1、 線性規(guī)劃試題 一單項選擇題（每小題2分，共20分） 1在有兩個變量的線性規(guī)劃問題中，若問題有唯一最優(yōu)解，則（ ） A.此最優(yōu)解一定在可行域的一個頂點上達到。 B.此最優(yōu)解一定在可行域的內(nèi)部達到。 C.此最優(yōu)解一定在可行域的一條直線段邊界上達到。D.此時可行域只有一個點。 2設(shè)有兩個變量的線性規(guī)劃模型的可行域的圖如下，若目標(biāo)函數(shù)只在點處達到最優(yōu)值，則此目標(biāo)函數(shù)可能是（ ） A.212xxz? B.2xz?C.215xxz? D.218xxz? 3.若線性規(guī)劃模型有可行解，則此線性規(guī)劃（ ） 基可行解必唯一?；尚薪庥袩o窮多個?；尚薪鈧€數(shù)必有限?；尚薪舛际亲顑?yōu)解。 4任何一個線性規(guī)劃模型的可

2、行解是（ ） A. 一個無界集合。B.是一個閉多面凸集。C.是一個空集。D.是一個無邊界的集合 5設(shè)有下面線性規(guī)劃問題有最優(yōu)解，則（ ） 0.min?XbAXtsCXf A. 此目標(biāo)函數(shù)在可行域上必有下界 B.此目標(biāo)函數(shù)在可行域上必有上界 C. 此目標(biāo)函數(shù)在可行域上必有上界和下界 D.此目標(biāo)函數(shù)在可行域上必?zé)o下界 6設(shè)有線性規(guī)劃模型 3213minxxxf? s.t. 4,3,2,1,07436326213214321?ixxxxxxxxxxi 則（ ）是一組對應(yīng)于基的基變量 A.21,xx B.321,xxx C.31,xx D.432,xxx 7設(shè)有線性規(guī)劃模型 0.max?XbAXtsC

3、Xf 則它的對偶線性規(guī)劃的目標(biāo)函數(shù)是（ ） A.CXg?max B. Cbg?min C.Ubg?min D.CXg?max 8設(shè)有兩個對偶的線性規(guī)劃問題的模型，下面說法正確的是（ ） A.一個模型有可行解且目標(biāo)函數(shù)在可行集上無界，另一個模型有可行解。 B.一個問題有可行解且目標(biāo)函數(shù)在可行集上有界，但另一個問題無可行解。 C.一個問題有可行解且目標(biāo)函數(shù)在可行集上無界，另一個模型無可行解。 D.兩個問題都有可行集，但目標(biāo)函數(shù)在可行集上都無界。 9下列有關(guān)運輸問題的陳述不正確的有（ ） A.對平衡的運輸問題來說，一定存在可行解。 B.對不平衡的運輸問題來說，可能不存在最優(yōu)解 C.若對一外運輸問題來

4、說存在最優(yōu)解，則可斷定此運輸問題一定是平衡運輸問題 D.若地一個運輸問題來說存在可行解，則可斷定此運輸問題一定是平衡運輸問題 10下列圖形不存在閉回路的有（ ） 二填空題（每小題2分，共20分） 11對于線性規(guī)劃模型， 的可行解稱為問題的最優(yōu)解。 12下列線性規(guī)劃模型 21minxxf? s.t. 0,0022212121?xxxxxx 的標(biāo)準(zhǔn)型是 。 13設(shè)有線性規(guī)劃模型 CXf?min s.t. jnjjpxAX?1（其中jp為矩陣A的第j列） 0?X (秩（A）=m=A的行數(shù)) 則 稱為基（陣）。 14設(shè)有線性規(guī)劃模型 CXf?min 1B 2B 3B 1A 2A 3A ),(,.211

5、mjnjjpppbpxAXts?為矩陣A的基陣。 0?X 稱為基可行解。 15設(shè)標(biāo)準(zhǔn)線性規(guī)劃模型非基變量的下標(biāo)集是R，典式中的目標(biāo)函數(shù)為jRjjxff?0min，則當(dāng)所有檢驗數(shù) 時，對應(yīng)的基可行解0X 為最優(yōu)解。 160X是線性規(guī)劃模型 0.min?XbAXtsCXf 的最優(yōu)基可行解，對應(yīng)的基陣為B，則?0U 是其對偶線性規(guī)劃模型的最優(yōu)解。 17設(shè)0X是線性規(guī)劃模型 0.min?XbAXtsCXf 的最優(yōu)基可行解，0U是其對偶線性規(guī)劃模型的最優(yōu)解，則0X與0U的關(guān)系是 。 18對于運輸問題的一個基可行解，設(shè)klx為一非基變量，并設(shè)從klx出發(fā)基變量為其余頂點的閉回路為： lpqpqpqpkqk

6、llllxxxxxx,21111? 還知，該閉回路上偶序頂點對應(yīng)運價及奇序頂點對應(yīng)的運價，則klx的對應(yīng)的檢驗數(shù)為 。 19設(shè)運輸問題的數(shù)據(jù)如下表： 用左上角法求得初始方案為 。 20已知：),(0010nxxx?是dxbAx?0,的基可行解，若 ， 則稱jx為相應(yīng)的第一類非基變量，若 ，則稱jx 為相應(yīng)的第二類非基變量。 三計算題（一）（每小題10分，共20分） 21設(shè)有兩個變量的線性規(guī)劃模型 s.t. 0,021272172max21212121?xxxxxxxxf 用圖解法求其最優(yōu)解。 22用單純形方法求解下列線性規(guī)劃問題。 2143minxxf? 1x 3x? =5 2x 4x? =2

7、 2143xx? 5x?=)5,4,3,2,1(,0?ixi 其中可選543,xxx為一組初始基變量。 四計算題（二）（15分） 23利用西北角法求下列運輸問題的初始方案 1B 2B 3B 4B 1A 11x 2 12x 9 13x 10 14x 7 9 2A 21x 1 22x 3 23x 4 24x 2 5 3A 31x 8 32x 4 33x 2 34 5 7 3 8 4 6 五應(yīng)用題（15分） 24建立下面問題的線性規(guī)劃模型（不要求求解） 有兩個水果生產(chǎn)基地A,B,往三個城市X,Y,Z調(diào)運水果，設(shè)A基地需要調(diào)運的水果有20噸，B基地需要調(diào)運的水果有11噸，設(shè)X,Y,Z三城需要水果的數(shù)量

8、分別是17噸，11噸，3噸，已知每噸運費如下表： 問如何安排調(diào)運，使得運費最少？ 六證明題（10分） 25應(yīng)用對偶理論證明下面線性規(guī)劃問題有最優(yōu)解。 2195maxxxZ? s.t. 0,02535162212121?xxxxxx 參考答案 一單項選擇題。 1A 2C 3C 4B 5A 6B,D 7C 8C 9B 10。 注：6。有兩個答案， 7。題中min應(yīng)改為max 10題有誤，沒有正確答案 二填空題： 11在可行域上使目標(biāo)函數(shù)達到最優(yōu)值（最大值或最小值） 12 S.t. 0,0,0,0022min4322142132121?xxxxxxxxxxxxxf 13矩陣A的任意一個m階非奇異子方陣 14因),(21mppp?為A的一個基陣，則方程bpxmjjj?1有唯一解00201,mxxx?，故0,0,002010?mxxxX為原(LP)的一個解，稱之為基解，若進一步還有00?X，則稱0X為(LP)的基可行解 15或非正0? 161?BCB 17bUCX00