《運(yùn)籌學(xué)》試題及答案

第二章線性規(guī)劃的基本概念

一、填空題

1.線性規(guī)劃問(wèn)題是求一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問(wèn)題。

2.圖解法適用于含有兩仝變量的線性規(guī)劃問(wèn)題。

3.線性規(guī)劃問(wèn)題的可行解是指滿足所有約束條件的解。

4.在線性規(guī)劃問(wèn)題的基本解中，所有的非基變量等于雯。

5.在線性規(guī)劃問(wèn)題中，基可行解的非零分量所對(duì)應(yīng)的列向量線性無(wú)關(guān)

6.若線性規(guī)劃問(wèn)題有最優(yōu)解，則最優(yōu)解一定可以在可行域的頂點(diǎn)（極點(diǎn)）達(dá)

到。

7.線性規(guī)劃問(wèn)題有可行解，則必有基可行解。

8.如果線性規(guī)劃問(wèn)題存在目標(biāo)函數(shù)為有限值的最優(yōu)解，求解時(shí)只需在其基可

在虬的集合中進(jìn)行搜索即可得到最優(yōu)解。

9.滿足韭負(fù)條件的基本解稱為基本可行解。

10.在將線性規(guī)劃問(wèn)題的一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，引入的松馳數(shù)量在目標(biāo)

函數(shù)中的系數(shù)為委。

H.將線性規(guī)劃模型化成標(biāo)準(zhǔn)形式時(shí)，y的約束條件要在不等式a端加

入松弛變量。

12.線性規(guī)劃模型包括決策（可控）變量，約束條件，目標(biāo)函數(shù)三個(gè)要素。

13.線性規(guī)劃問(wèn)題可分為目標(biāo)函數(shù)求極大值和極小值兩類。

14.線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式中，約束條件取笠式，目標(biāo)函數(shù)求極大值,而所

有變量必須非負(fù)。

15.線性規(guī)劃問(wèn)題的基可行解與可行域頂點(diǎn)的關(guān)系是頂點(diǎn)多于基可行解

16.在用圖解法求解線性規(guī)劃問(wèn)題時(shí)，如果取得極值的等值線與可行域的一段

邊界重合，則這段邊界上的一切點(diǎn)都是最優(yōu)解。

17.求解線性規(guī)劃問(wèn)題可能的結(jié)果有無(wú)解，有唯一最優(yōu)解，有無(wú)窮多個(gè)最優(yōu)解。

18.如果某個(gè)約束條件是“W”情形，若化為標(biāo)準(zhǔn)形式，需要引入一松弛變量。

19.如果某個(gè)變量尤為自由變量，則應(yīng)引進(jìn)兩個(gè)非負(fù)變量X；,X；,同時(shí)令左

=X/-Xjo

20.表達(dá)線性規(guī)劃的簡(jiǎn)式中目標(biāo)函數(shù)為max(min)Z=Zc“Xw

21..(2.1P5))線性規(guī)劃一般表達(dá)式中，a-表示該元素位置在i行j列。

二、單選題

1.如果一個(gè)線性規(guī)劃問(wèn)題有n個(gè)變量，m個(gè)約束方程(m〈n),系數(shù)矩陣的數(shù)為

m,則基可行解的個(gè)數(shù)最為」一

A.m個(gè)B.n個(gè)C.C?,nD.。個(gè)

2.下列圖形中陰影部分構(gòu)成的集合是凸集的是

CO<D>

3.線性規(guī)劃模型不包括下列D要素。

A.目標(biāo)函數(shù)B.約束條件C.決策變量D.狀態(tài)

變量

4.線性規(guī)劃模型中增加一個(gè)約束條件，可行域的范圍一般將_B一。

A.增大B.縮小C.不變D.不定

5.若針對(duì)實(shí)際問(wèn)題建立的線性規(guī)劃模型的解是無(wú)界的，不可能的原因是B_。

A.出現(xiàn)矛盾的條件B.缺乏必要的條件C.有多余的條件

D.有相同的條件

6.在下列線性規(guī)劃問(wèn)題的基本解中，屬于基可行解的是衛(wèi)

A.(―1,0,0)TB.(1,0,3,0)TC.(-4,0,0,3尸D.(0,

—1,0,5)T

7.關(guān)于線性規(guī)劃模型的可行域，下面_B_的敘述正確。

A.可行域內(nèi)必有無(wú)窮多個(gè)點(diǎn)B.可行域必有界C.可行域內(nèi)必然包括原點(diǎn)

D.可行域必是凸的

8.下列關(guān)于可行解，基本解，基可行解的說(shuō)法錯(cuò)誤的是一D_.

A.可行解中包含基可行解B.可行解與基本解之間無(wú)

交集

C.線性規(guī)劃問(wèn)題有可行解必有基可行解D.滿足非負(fù)約束條件的基

本解為基可行解

非可行解

9.線性規(guī)劃問(wèn)題有可行解，則A

A必有基可行解B必有唯一最優(yōu)解C無(wú)基可行解D無(wú)

唯一最優(yōu)解

10.線性規(guī)劃問(wèn)題有可行解且凸多邊形無(wú)界，這時(shí)J

A沒(méi)有無(wú)界解B沒(méi)有可行解C有無(wú)界解D有

有限最優(yōu)解

11.若目標(biāo)函數(shù)為求max,一個(gè)基可行解比另一個(gè)基可行解更好的標(biāo)志是.A

A使Z更大B使Z更小C絕對(duì)值更大DZ

絕對(duì)值更小

12.如果線性規(guī)劃問(wèn)題有可行解，那么該解必須滿足D

A所有約束條件B變量取值非負(fù)C所有等式要求D所有不

等式要求

13.如果線性規(guī)劃問(wèn)題存在目標(biāo)函數(shù)為有限值的最優(yōu)解，求解時(shí)只需在上集合

中進(jìn)行搜索即可得到最優(yōu)解。

A基B基本解C基可行解D可行域

14.線性規(guī)劃問(wèn)題是針對(duì)D求極值問(wèn)題.

A約束B決策變量C秩D目標(biāo)函數(shù)

15如果第K個(gè)約束條件是“W”情形，若化為標(biāo)準(zhǔn)形式，需要B

A左邊增加一個(gè)變量B右邊增加一個(gè)變量C左邊減去一個(gè)變量D右邊減

去一個(gè)變量

16.若某個(gè)bkWO,化為標(biāo)準(zhǔn)形式時(shí)原不等式D

A不變B左端乘負(fù)1C右端乘負(fù)1D兩

邊乘負(fù)1

17.為化為標(biāo)準(zhǔn)形式而引入的松弛變量在目標(biāo)函數(shù)中的系數(shù)應(yīng)為

A0B1C2D3

12.若線性規(guī)劃問(wèn)題沒(méi)有可行解，可行解集是空集，則此問(wèn)題B

A沒(méi)有無(wú)窮多最優(yōu)解B沒(méi)有最優(yōu)解C有無(wú)界解D有無(wú)界解

三、多選題

1.在線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式中，不可能存在的變量是

A.可控變量B.松馳變量c.剩余變量D.人工變量

2.下列選項(xiàng)中符合線性規(guī)劃模型標(biāo)準(zhǔn)形式要求的有BCD

A.目標(biāo)函數(shù)求極小值B.右端常數(shù)非負(fù)C.變量非負(fù)D.約束條件為等式E.約

束條件為“W”的不等式

3.某線性規(guī)劃問(wèn)題，n個(gè)變量，m個(gè)約束方程，系數(shù)矩陣的秩為m(m<n)則下列

說(shuō)法正確的是ABDE。

A.基可行解的非零分量的個(gè)數(shù)不大于mB.基本解的個(gè)數(shù)不會(huì)超過(guò)仁”個(gè)C.該

問(wèn)題不會(huì)出現(xiàn)退化現(xiàn)象D.基可行解的個(gè)數(shù)不超過(guò)基本解的個(gè)數(shù)E.該問(wèn)題的基

是一個(gè)mXm階方陣

4.若線性規(guī)劃問(wèn)題的可行域是無(wú)界的，則該問(wèn)題可能ABCD

A.無(wú)有限最優(yōu)解B.有有限最優(yōu)解C.有唯一最優(yōu)解D.有無(wú)窮多個(gè)最優(yōu)

解E.有有限多個(gè)最優(yōu)解

5.判斷下列數(shù)學(xué)模型，哪些為線性規(guī)劃模型(模型中a.b.c為常數(shù)；0為可取

某一常數(shù)值的參變量，x,Y為變量)ACDE

4

ArmiZ??7xt

>8B.Hqx,

a.1.5江\內(nèi)嗎匕t,2,-tn)

a.

L&AO.(j=1

C.minZ=SajXj2+Sb：y：2

i-lj?l'1

2

fxj+yj<Ci

IN，力為自由變量（i=l,2,…，m,j=l,2,…，m,）

D.maxZ=ScjXj

（2——+一g=1,2，…m）

S.t.'E

,%206=1,2,…n）

E.maxZ=ZK/CK

ntn

ZK=SSOik

s?t?Y自一。=-]（i=l,…,m）

k?1

=1,2,…n;k=l,2…，m）

6.下列模型中，屬于線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式的是ACD

A.maxZ=x+4xB.maxZ=5x+2x

l212C.minZ=5x^X2D.maxZ=6x1+4x2

Qxi-2xW23xI+8x2=4

-10X2=202%+x2=l

S.t.<X]+X2）2S,t]X[+X2=T

s.tJxl+x2^-28.1.9^+4\2=1.5

yo|x”x，0展》0

xHx2>0

7.下列說(shuō)法錯(cuò)誤的有一ABD_。

A.基本解是大于零的解B.極點(diǎn)與基解---對(duì)應(yīng)

C.線性規(guī)劃問(wèn)題的最優(yōu)解是唯一的D.滿足約束條件的解就是線性規(guī)劃的可

行解

8.在線性規(guī)劃的一般表達(dá)式中，變量x”為ABE

A大于等于0B小于等于0C大于0D小于0E等于0

9.在線性規(guī)劃的一般表達(dá)式中，線性約束的表現(xiàn)有CDE

A<B>CWDNE=

10.若某線性規(guī)劃問(wèn)題有無(wú)界解，應(yīng)滿足的條件有AD

APk<0B非基變量檢驗(yàn)數(shù)為零C基變量中沒(méi)有人工變量D6d>0

E所有5￡0

11.在線性規(guī)劃問(wèn)題中a23表示AE

Ai=2Bi=3Ci=5Dj=2Ej=3

43.線性規(guī)劃問(wèn)題若有最優(yōu)解，則最優(yōu)解AD

A定在其可行域頂點(diǎn)達(dá)到B只有一個(gè)C會(huì)有無(wú)窮多個(gè)D唯一或無(wú)

窮多個(gè)E其值為0

42.線性規(guī)劃模型包括的要素有旦區(qū)

A.目標(biāo)函數(shù)B.約束條件C.決策變量D狀態(tài)變量E環(huán)境

變量

四、名詞

1基：在線性規(guī)劃問(wèn)題中，約束方程組的系數(shù)矩陣A的任意一個(gè)mXm階的非奇

異子方陣B,稱為線性規(guī)劃問(wèn)題的一個(gè)基。

2、線性規(guī)劃問(wèn)題：就是求一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問(wèn)題。

3.可行解：在線性規(guī)劃問(wèn)題中，凡滿足所有約束條件的解稱為線性規(guī)劃問(wèn)題可行

解

4、行域：線性規(guī)劃問(wèn)題的可行解集合。

5、本解：在線性約束方程組中，對(duì)于選定的基B令所有的非基變量等于零，得

到的解，稱為線性規(guī)劃問(wèn)題的一個(gè)基本解。

6.、圖解法：對(duì)于只有兩個(gè)變量的線性規(guī)劃問(wèn)題，可以用在平面上作圖的方法來(lái)

求解，這種方法稱為圖解法。

7、本可行解：在線性規(guī)劃問(wèn)題中，滿足非負(fù)約束條件的基本解稱為基本可行解。

8、模型是一件實(shí)際事物或?qū)嶋H情況的代表或抽象，它根據(jù)因果顯示出行動(dòng)與反

映的關(guān)系和客觀事物的內(nèi)在聯(lián)系。

四、把下列線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)形式：

1.minZ=5xi-2x2

Xf+yx2<4

S.t.<-X]+X24-2

2x243

Xi,吃>0

/、甜；MQ/N，=才，十ZQ

g

壬

Ni+-y^c2+=4

$j一孫一了4=2

2JC2+壬=3

>0(J=1,2,3,4,5)

2、minZ=2xi-x2+2x3

-Xi+X2+X3=4

s.t.J-Xi+x2-X3<6

晨14O,X2,O,X3無(wú)約束

Z

2.令N1=-=X3一壬"，化為標(biāo)準(zhǔn)型為

XZ

majc^=211'+%-23+2x3^

仔1'++工3'一=4

x

5?￡?1+Z2一力3'+3+Z4=6

bJ,12，13‘，了3'，了4NO

3.maxZ=2xt+x2+3x3+人

Xi+X2+X3+々&7

2x—3X+5X=-8

s.t.<t2、3

X]-2X3+2々

Xi,X3)0,X2W0,X4無(wú)約束

zz

3.令x2=-x2?x4—14”化為標(biāo)準(zhǔn)型

,

majcZ"=2xt-x2'^3x3+-x4*

Xi-X2+X3+X4-X4+X5=/

Z

—2JCX—3X2_5JC3=8

S.2.《

x

i—2X3+2x4，—2x4“一改=I

巧N0(J=l,2,…，8)

五、按各題要求。建立線性規(guī)劃數(shù)學(xué)模型

1、某工廠生產(chǎn)A、B、C三種產(chǎn)品，每種產(chǎn)品的原材料消耗量、機(jī)械臺(tái)時(shí)消耗量

以及這些資源的限量，單位產(chǎn)品的利潤(rùn)如下表所示：

單位、產(chǎn)品

ABC資源限量

資鏟7^

原材料1.01.54.02000

機(jī)械臺(tái)時(shí)2.01.21.01000

單位利潤(rùn)101412

根據(jù)客戶訂貨，三種產(chǎn)品的最低月需要量分別為200,250和100件，最大月

銷售量分別為250,280和120件。月銷售分別為250,280和120件。問(wèn)如

何安排生產(chǎn)計(jì)劃，使總利潤(rùn)最大。

五：1.設(shè)勺、必、工3分別代表三種產(chǎn)品的產(chǎn)量，則線性規(guī)則模

型為

maxZ=10xj+14必+12必

+

W+1.5J241342000

2zj+1.212+為41000

2004々4250

2504叫4280

1004小4120

工1，小,13

2、某建筑工地有一批長(zhǎng)度為10米的相同型號(hào)的鋼筋，今要截成長(zhǎng)度為3米的鋼

筋90根，長(zhǎng)度為4米的鋼筋60根，問(wèn)怎樣下料，才能使所使用的原材料最??？

2.將10米長(zhǎng)的鋼筋截為3米長(zhǎng)和4米長(zhǎng)，共有以下幾種

下料方式：

I,nin

3米023

4米210

設(shè)4,孫，壬分別表示采用I、n、ui種下料方式的鋼筋

數(shù)，則線性規(guī)則模型可寫成：

minZ=+x2+x3

2工z+3X3)90

s.E.y2xi+以)60

1，12，13°

1.某運(yùn)輸公司在春運(yùn)期間需要24小時(shí)晝夜加班工作，需要的人員數(shù)量如下

表所示：

起運(yùn)時(shí)間服務(wù)員數(shù)

2—64

6—108

10-1410

14—187

18—2212

22—24

每個(gè)工作人員連續(xù)工作八小時(shí)，且在時(shí)段開始時(shí)上班，問(wèn)如何安排，使得既滿足

以上要求，又使上班人數(shù)最少？

3.設(shè)在第，時(shí)段上班的人數(shù)為丐(,=1,2,…，6),則線性

規(guī)劃模型為

_6_

minZ=＞：xi

N]+N6N4

了1+工2'8

JC2+13=10

$.￡.v/3+JC4N7

x4+JC5N12

Xj+》4

力N0(j=1?2,???,6)

第三章線性規(guī)劃的基本方法

一、填空題

1.線性規(guī)劃的代數(shù)解法主要利用了代數(shù)消去法的原理，實(shí)現(xiàn)基可行解的轉(zhuǎn)換,

尋找最優(yōu)解。

2.標(biāo)準(zhǔn)形線性規(guī)劃典式的目標(biāo)函數(shù)的矩陣形式是maxZ=CBBTb+(CN—gB

N)XRO

3.對(duì)于目標(biāo)函數(shù)極大值型的線性規(guī)劃問(wèn)題，用單純型法求解時(shí)，當(dāng)基變量檢

驗(yàn)數(shù)6,W0時(shí),當(dāng)前解為最優(yōu)解。

4.用大M法求目標(biāo)函數(shù)為極大值的線性規(guī)劃問(wèn)題時(shí)，引入的人工變量在目標(biāo)函

數(shù)中的系數(shù)應(yīng)為一M。

5.在單純形迭代中，可以根據(jù)最終表中人工變量不為零判斷線性規(guī)劃問(wèn)題無(wú)解。

6.在線性規(guī)劃典式中，所有基變量的目標(biāo)系數(shù)為。。

7.當(dāng)線性規(guī)劃問(wèn)題的系數(shù)矩陣中不存在現(xiàn)成的可行基時(shí)，一般可以加入人工變

量構(gòu)造可行基。

8.在單純形迭代中，選出基變量時(shí)應(yīng)遵循最小比值0法則。

9.線性規(guī)劃典式的特點(diǎn)是基為單位矩陣，基變量的目標(biāo)函數(shù)系數(shù)為0。

10.對(duì)于目標(biāo)函數(shù)求極大值線性規(guī)劃問(wèn)題在非基變量的檢驗(yàn)數(shù)全部6jWO、問(wèn)題

無(wú)界時(shí)，問(wèn)題無(wú)解時(shí)情況下,單純形迭代應(yīng)停止。

11.在單純形迭代過(guò)程中，若有某個(gè)3k>0對(duì)應(yīng)的非基變量Xk的系數(shù)列向量Pj

W0時(shí),則此問(wèn)題是無(wú)界的。

12.在線性規(guī)劃問(wèn)題的典式中，基變量的系數(shù)列向量為單位列向量

13.對(duì)于求極小值而言，人工變量在目標(biāo)函數(shù)中的系數(shù)應(yīng)取T

14.(單純形法解基的形成來(lái)源共有三種

15.在大M法中，M表示充分大正數(shù)。

二、單選題

1.線性規(guī)劃問(wèn)題Q

■艮"ZYM將麻髀酚-我就解卻行HMM

AZWB.Z,XZTc.rccryD.Z?與②)‘無(wú)關(guān)

2.在單純形迭代中，出基變量在緊接著的下一次迭代中更立即進(jìn)入基底。

A.會(huì)B.不會(huì)C.有可能D.不一定

3.在單純形法計(jì)算中，如不按最小比值原則選取換出變量，則在下一個(gè)解中且。

A.不影響解的可行性B.至少有一個(gè)基變量的值為負(fù)C.找不到出基變量D.找

不到進(jìn)基變量

4.用單純形法求解極大化線性規(guī)劃問(wèn)題中，若某非基變量檢驗(yàn)數(shù)為零，而其他

非基變量檢驗(yàn)數(shù)全部＜0,則說(shuō)明本問(wèn)題旦。

A.有惟一最優(yōu)解B.有多重最優(yōu)解C.無(wú)界D.無(wú)解

5.線性規(guī)劃問(wèn)題maxZ=CX,AX=b,X20中，選定基B,變量Xk的系數(shù)列向量為

R,則在關(guān)于基B的典式中，凡的系數(shù)列向量為3

T

A.BRB.BPKC.PKBD.B'PK

6.下列說(shuō)法錯(cuò)誤的是且

A.圖解法與單純形法從幾何理解上是一致的B.在單純形迭代

中，進(jìn)基變量可以任選

C.在單純形迭代中，出基變量必須按最小比值法則選取D.人工變量離開

基底后，不會(huì)再進(jìn)基

7.單純形法當(dāng)中，入基變量的確定應(yīng)選擇檢驗(yàn)數(shù)

A絕對(duì)值最大B絕對(duì)值最小C正值最大D

負(fù)值最小

8.在單純形表的終表中，若若非基變量的檢驗(yàn)數(shù)有0,那么最優(yōu)解

A不存在B唯一C無(wú)窮多D無(wú)

窮大

9.若在單純形法迭代中，有兩個(gè)Q值相等，當(dāng)分別取這兩個(gè)不同的變量為入基變

量時(shí)，獲得的結(jié)果將是上

A先優(yōu)后劣B先劣后優(yōu)C相同D會(huì)隨目標(biāo)

函數(shù)而改變

10.若某個(gè)約束方程中含有系數(shù)列向量為單位向量的變量，則該約束方程不必再

引入」

A松弛變量B剩余變量C人工變量D自由變

旦

里

11.在線性規(guī)劃問(wèn)題的典式中，基變量的系數(shù)列向量為旦

A單位陣B非單位陣C單位行向量D單位列向量

12.在約束方程中引入人工變量的目的是D

A體現(xiàn)變量的多樣性B變不等式為等式C使目標(biāo)函數(shù)為最優(yōu)D形成

一個(gè)單位陣

13.出基變量的含義是旦

A該變量取值不變B該變量取值增大C由0值上升為某值D由某

值下降為0

14.在我們所使用的教材中對(duì)單純形目標(biāo)函數(shù)的討論都是針對(duì)」情況而言的。

AminBmaxCmin+maxDmin,max任

選

15.求目標(biāo)函數(shù)為極大的線性規(guī)劃問(wèn)題時(shí)，若全部非基變量的檢驗(yàn)數(shù)W0,且基變

量中有人工變量時(shí)該問(wèn)題有B

A無(wú)界解B無(wú)可行解C唯一最優(yōu)解D無(wú)窮多最優(yōu)解

三、多選題

1.對(duì)取值無(wú)約束的變量xjo通常令Xj=x「-x"j,其中x/20,xj20,

在用單純形法求得的最優(yōu)解中，可能出現(xiàn)的是ABC

A.x>x>0BQWC厚金。叫加利

2.線性規(guī)劃問(wèn)題maxZ=Xi+CX2

JaxI+2x?=8

“凡一…其中4<C<6,—lWaW3,10Wb〈⑵則當(dāng)BC時(shí),該問(wèn)題的

最優(yōu)目標(biāo)函數(shù)值分別達(dá)到上界或下界。

A.c=6a=~lb=10B.c=6a=-lb=12C.c=4a=3b=12D.c=4

a=3b=12E.c=6a=3b=12

3.設(shè)X⑴，X⑵是用單純形法求得的某一線性規(guī)劃問(wèn)題的最優(yōu)解，則說(shuō)明ACDE。

A.此問(wèn)題有無(wú)窮多最優(yōu)解B.該問(wèn)題是退化問(wèn)題C.此問(wèn)題的全部

最優(yōu)解可表示為入X⑴+(1一入)X⑵，其中0W入D.X(1),X⑵是兩個(gè)基可行解

E.X”>,X⑵的基變量個(gè)數(shù)相同

4.某線性規(guī)劃問(wèn)題，含有n個(gè)變量，m個(gè)約束方程，(m<n),系數(shù)矩陣的秩為m,

則ABDoA.該問(wèn)題的典式不超過(guò)Cj個(gè)B.基可行解中的基變量的個(gè)數(shù)為m個(gè)

C.該問(wèn)題一定存在可行解D.該問(wèn)題的基至多有C『=l個(gè)E.該問(wèn)題有111個(gè)基

可行解

5.單純形法中，在進(jìn)行換基運(yùn)算時(shí)，應(yīng)ACDE。A.先選取進(jìn)基變量，再選取出

基變量B.先選出基變量，再選進(jìn)基變量C.進(jìn)基變量的系數(shù)列向量應(yīng)化為單位

向量D.旋轉(zhuǎn)變換時(shí)采用的矩陣的初等行變換E.出基變量的選取是根據(jù)最小比

值法則

6.從一張單純形表中可以看出的內(nèi)容有ABCE。A.一個(gè)基可行解B.當(dāng)前解

是否為最優(yōu)解C.線性規(guī)劃問(wèn)題是否出現(xiàn)退化D.線性規(guī)劃問(wèn)題的最優(yōu)解E.線

性規(guī)劃問(wèn)題是否無(wú)界

7.單純形表迭代停止的條件為（AB）

A所有"均小于等于0B所有"均小于等于0且有詠忘0C所有

aik>0D所有bWO

8.下列解中可能成為最優(yōu)解的有（ABCDE）

A基可行解B迭代一次的改進(jìn)解C迭代兩次的改進(jìn)解D迭代三

次的改進(jìn)解

E所有檢驗(yàn)數(shù)均小于等于0且解中無(wú)人工變量

9、若某線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解，應(yīng)滿足的條件有（BCE）

APk<PQB非基變量檢驗(yàn)數(shù)為零C基變量中沒(méi)有人工變量D6j<0

E所有5￡0

10.下列解中可能成為最優(yōu)解的有（ABCDE）

A基可行解B迭代一次的改進(jìn)解C迭代兩

次的改進(jìn)解

D迭代三次的改進(jìn)解E所有檢驗(yàn)數(shù)均小于等于0且解中無(wú)人工變量

四、名詞、簡(jiǎn)答

1、人造初始可行基：當(dāng)我們無(wú)法從一個(gè)標(biāo)準(zhǔn)的線性規(guī)劃問(wèn)題中找到一個(gè)m階單

位矩陣時(shí)，通常在約束方程中引入人工變量，而在系數(shù)矩陣中湊成一個(gè)m階單

位矩陣，進(jìn)而形成的一個(gè)初始可行基稱為人造初始可行基。

2、單純形法解題的基本思路？可行域的一個(gè)基本可行解開始，轉(zhuǎn)移到另一個(gè)

基本可行解，并且使目標(biāo)函數(shù)值逐步得到改善，直到最后球場(chǎng)最優(yōu)解或判定原問(wèn)

題無(wú)解。

五、分別用圖解法和單純形法求解下列線性規(guī)劃問(wèn)題.并對(duì)照指出單純形迭代的

每一步相當(dāng)于圖解法可行域中的哪一個(gè)頂點(diǎn)。

2.maxZ=2x+x

1.maxZ=10xi+5x2t2

，5xi415

3xi+4x249

6xi+2x?《24

s.t.5x]+2x?48s.t.<

Xi+X2&5

Xj,X2)0

Xj,x2>0

h瞥：

2門".r$?

-E九。9")

九/XcA*t??

3專他漏

卜力,T

I-L人M，八“4。?為必料

六、用單純形法求解下列線性規(guī)劃問(wèn)題：

2.Mini=-2MlMm

3xi+x]?

x(-X,2x,<10

"IX)+Xj-X|<20

x(,Xj,Xj>0

七、用大M法求解下列線性規(guī)劃問(wèn)題。并指出問(wèn)題的解屬于哪一類。

1.r*.xZ=4xi+5X+x

232.maxZ=%+2x2+3x3-x4

3xi+2x?+X3>18X]+2x2+3xj=15

2XJ+X?&42x1+x2+5XB=20

5.t.A.

s,’X|+2X2+Xj+x4=10

X[+x2-xs=5

JS>O(j=1.2,3)七?。6=1,….4)

f%

及以y-+*At

XI+K■*—劣M+K7—b

XjC}-A「

”b/o-x^lO

K，KaK與RyKnXp>

/二《X&b>

一AKXc-/*Mq/一，，o二

OX4,戲一二S二'>_

X)*r

4E+4j~w^r/一0￡°_

—-..---“---

-*>1X，/cXO-if)~f9匚

?z^,ooO'dO

4X,o2^

O處一/oo一一0Z-

。一NJe>—Mf-5l—”>oW2■ff*'至口_

'X3/dO—f~—ff-O

《K’a/OoO/iXO

W必/音」o--'O---//_~~0^~~__/

___________iGOf-/-上“&c

環(huán)天8w。，n3與K"4K年關(guān)一心逐坤?的-J

x,+3K335

?x=).

/3—/——x-y

X?Kn-XyKu右

—S又￡/夕/o2-，。/O

——?2,/MO0?

-/X，/p/(A)//o0

-NJdYfl夕x/f+Z00。

-Al夕0?=>d?—/，o

一XKG"o——Qo/

dXd夕

W；A4O至'^i+d—aXOc

一A4XruO0<5)—1?f

K,/<=?OB-%0

°，—。一片

..仃-00_F—2O_~7

3X?%00'—右K

4K，，。二率一發(fā)汨

°f°/玲，

---------------J__二^}_O。O——?一/—A1

X*o.o-0)T.

八、下表為用單純形法計(jì)算時(shí)某一步的表格。已知該線性規(guī)劃的目標(biāo)函數(shù)為

maxZ=5x,+3x2,約束形式為“W”，X：“X,為松馳變量.表中解代入目標(biāo)函數(shù)后

得Z=10

XiX2x3x?

-10b-11,g

x：(2C011/5

X,Ade01

(1)求表中a?g的值(2)表中給出的解是否為最優(yōu)解？

(1)a=2b=0c=0d=le=4/5f=0g=-5(2)表中給出的解為最

優(yōu)解,

第四章線性規(guī)劃的對(duì)偶理論

一、填空題

1.線性規(guī)劃問(wèn)題具有對(duì)偶性，即對(duì)于任何一個(gè)求最大值的線性規(guī)

劃問(wèn)題，都有一個(gè)求最小值/極小值的線性規(guī)劃問(wèn)題與之對(duì)應(yīng),反之亦然。

2.在一對(duì)對(duì)偶問(wèn)題中，原問(wèn)題的約束條件的右端常數(shù)是對(duì)偶問(wèn)題的目標(biāo)函數(shù)系

數(shù)。

3.如果原問(wèn)題的某個(gè)變量無(wú)約束，則對(duì)偶問(wèn)題中對(duì)應(yīng)的約束條件應(yīng)為等式一。

4.對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題_。

5.若原問(wèn)題可行，但目標(biāo)函數(shù)無(wú)界，則對(duì)偶問(wèn)題不可行。

6.若某種資源的影子價(jià)格等于k。在其他條件不變的情況下(假設(shè)原問(wèn)題的最佳

基不變)，當(dāng)該種資源增加3個(gè)單位時(shí)。相應(yīng)的目標(biāo)函數(shù)值將增加3k0

7.線性規(guī)劃問(wèn)題的最優(yōu)基為B,基變量的目標(biāo)系數(shù)為CB,則其對(duì)偶問(wèn)題的最優(yōu)

解Y*=CBB-lo

8.若X*和Y*分別是線性規(guī)劃的原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解，則有CX*=Y*

bo

9.若X、Y分別是線性規(guī)劃的原問(wèn)題和對(duì)偶問(wèn)題的可行解，則有CXWYb。

10.若X*和Y*分別是線性規(guī)劃的原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解，則有CX*=Y*bo

11.設(shè)線性規(guī)劃的原問(wèn)題為maxZ=CX,AxWb,X20,則其對(duì)偶問(wèn)題為min=Yb

YA2cY20_。

12.影子價(jià)格實(shí)際上是與原問(wèn)題各約束條件相聯(lián)系的對(duì)偶變量的數(shù)量表現(xiàn)。

13.線性規(guī)劃的原問(wèn)題的約束條件系數(shù)矩陣為A,則其對(duì)偶問(wèn)題的約束條件系

數(shù)矩陣為AT。

14.在對(duì)偶單純形法迭代中,若某bi<0,且所有的aij20(j=l,2,…n),則

原問(wèn)題_無(wú)解。

二、單選題

1.線性規(guī)劃原問(wèn)題的目標(biāo)函數(shù)為求極小值型，若其某個(gè)變量小于等于0,則其

對(duì)偶問(wèn)題約束條件為A形式。

A.“2"B.“W"C,D.“=”

2.設(shè)V、歹分別是標(biāo)準(zhǔn)形式的原問(wèn)題與對(duì)偶問(wèn)題的可行解，則Co

A.CX>7bB.CX=ybC.CX<ybD.CX^yb

3.對(duì)偶單純形法的迭代是從一八_開始的。

A.正則解B.最優(yōu)解C.可行解D.基本解

4.如果z。是某標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題的最優(yōu)目標(biāo)函數(shù)值，則其對(duì)偶問(wèn)題的最優(yōu)

目標(biāo)函數(shù)值w*A。

A.W*=Z*B.W*WZ*C.W*WZ*D.W*

2z*

5.如果某種資源的影子價(jià)格大于其市場(chǎng)價(jià)格，則說(shuō)明_B

A.該資源過(guò)剩B.該資源稀缺C.企業(yè)應(yīng)盡快處理該資源D.企業(yè)應(yīng)充分利用該

資源，開僻新的生產(chǎn)途徑

三、多選題

1.在一對(duì)對(duì)偶問(wèn)題中，可能存在的情況是ABC。

A.一個(gè)問(wèn)題有可行解，另一個(gè)問(wèn)題無(wú)可行解B.兩個(gè)問(wèn)題都有可行解

C.兩個(gè)問(wèn)題都無(wú)可行解D.一個(gè)問(wèn)題無(wú)界，另一個(gè)問(wèn)

題可行

2.下列說(shuō)法錯(cuò)誤的是B。

A.任何線性規(guī)劃問(wèn)題都有一個(gè)與之對(duì)應(yīng)的對(duì)偶問(wèn)題B.對(duì)偶問(wèn)題無(wú)可行解時(shí)，

其原問(wèn)題的目標(biāo)函數(shù)無(wú)界。C.若原問(wèn)題為maxZ=CX,AXWb,X20,則對(duì)偶

問(wèn)題為minW=Yb,YA2C,Y20。D.若原問(wèn)題有可行解，但目標(biāo)函數(shù)無(wú)界，

其對(duì)偶問(wèn)題無(wú)可行解。

3.如線性規(guī)劃的原問(wèn)題為求極大值型，則下列關(guān)于原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系中

正確的是BCDE。

A原問(wèn)題的約束條件“2”，對(duì)應(yīng)的對(duì)偶變量“20”B原問(wèn)題的約束條件為

“=”，對(duì)應(yīng)的對(duì)偶變量為自由變量C.原問(wèn)題的變量“20”，對(duì)應(yīng)的對(duì)偶

約束“2"D.原問(wèn)題的變量“WO”對(duì)應(yīng)的對(duì)偶約束“W"E.原問(wèn)題的變

量無(wú)符號(hào)限制，對(duì)應(yīng)的對(duì)偶約束

4.一對(duì)互為對(duì)偶的問(wèn)題存在最優(yōu)解，則在其最優(yōu)點(diǎn)處有BD

A.若某個(gè)變量取值為0,則對(duì)應(yīng)的對(duì)偶約束為嚴(yán)格的不等式B.若某個(gè)變量取值

為正，則相應(yīng)的對(duì)偶約束必為等式C.若某個(gè)約束為等式，則相應(yīng)的對(duì)偶變

取值為正D.若某個(gè)約束為嚴(yán)格的不等式，則相應(yīng)的對(duì)偶變量取值為0E.若

某個(gè)約束為等式，則相應(yīng)的對(duì)偶變量取值為0

5.下列有關(guān)對(duì)偶單純形法的說(shuō)法正確的是ABCD。

A.在迭代過(guò)程中應(yīng)先選出基變量，再選進(jìn)基變量B.當(dāng)?shù)械玫降慕鉂M足原

始可行性條件時(shí)，即得到最優(yōu)解C.初始單純形表中填列的是一個(gè)正則解

D.初始解不需要滿足可行性E.初始解必須是可行的。

6.根據(jù)對(duì)偶理論，在求解線性規(guī)劃的原問(wèn)題時(shí)，可以得到以下結(jié)論ACD。

A.maxZ=2xt+4x2+x3+C.rnaxZ=3xi+2x

天盤L情況C能平價(jià)感2

對(duì)偶3XE.資源

xt+2+%48-Xi+2X44

B.maxZ=X]+x22

2x,+X246

-X|+x2+x3&23x[+2x?&14

s.tSx+x,+

7.左2s.V的步驟一

s.K.2X[+x2-X3<1Xj-x2<3

x,4-x2+Xj^9

x,>0(j=l,2,3,4)X1,x2,x3>0X],X?>0

D.minZ=3xt+2x2+x3E.maxZ=4xi+10x2

X,+X2+X3<63xi+6應(yīng)45

x,-Xs>4X[+3xz&2

Srx-x>3s.n7.

232xi+5x?&4

X],x2,x3>0,x2>0

四、名詞、簡(jiǎn)答題

1、對(duì)偶可行基：凡滿足條件6=C-C“BTAW0的基B稱為對(duì)偶可行基。

2、.對(duì)稱的對(duì)偶問(wèn)題：設(shè)原始線性規(guī)劃問(wèn)題為ipxZ=CXs.tAXWb

tXNO

稱線性規(guī)劃問(wèn)題minW=Ybrs.tYA2C

tY20為其對(duì)偶問(wèn)題。又稱它

們?yōu)橐粚?duì)對(duì)稱的對(duì)偶問(wèn)題。

3、影子價(jià)格：對(duì)偶變量Yi表示與原問(wèn)題的第i個(gè)約束條件相對(duì)應(yīng)的資源的影子

價(jià)格，在數(shù)量上表現(xiàn)為，當(dāng)該約束條件的右端常數(shù)增加一個(gè)單位時(shí)（假設(shè)原問(wèn)題

的最優(yōu)解不變），原問(wèn)題目標(biāo)函數(shù)最優(yōu)值增加的數(shù)量。

4.影子價(jià)格在經(jīng)濟(jì)管理中的作用。（1）指出企業(yè)內(nèi)部挖潛的方向；（2）為資源

的購(gòu)銷決策提供依據(jù)；（3）分析現(xiàn)有產(chǎn)品價(jià)格變動(dòng)時(shí)資源緊缺情況的影響；（4）

分析資源節(jié)約所帶來(lái)的收益；（5）決定某項(xiàng)新產(chǎn)品是否應(yīng)投產(chǎn)。

5.線性規(guī)劃對(duì)偶問(wèn)題可以采用哪些方法求解？（1）用單純形法解對(duì)偶問(wèn)題；（2）

由原問(wèn)題的最優(yōu)單純形表得到；（3）由原問(wèn)題的最優(yōu)解利用互補(bǔ)松弛定理求得;

（4）由Y*=CBB”求得，其中B為原問(wèn)題的最優(yōu)基

6、一對(duì)對(duì)偶問(wèn)題可能出現(xiàn)的情形：1.原問(wèn)題和對(duì)偶問(wèn)題都有最優(yōu)解，且二者相

等；2.一個(gè)問(wèn)題具有無(wú)界解，則另一個(gè)問(wèn)題具有無(wú)可行解；3.原問(wèn)題和對(duì)偶問(wèn)題

都無(wú)可行解。

五、寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題

1.minZ=2xi+2x2+4x;i

3.minZ=SScjXjj

2.maxZ=2x,-&+3x)+&i-u-i

2x[+3x,-5x>2

sXi-2x,+X)?5x?<5Sxi=a)(i=l,2,—,m)

i-i

3x,-Xj+7x>V37x+x工-3x,=-4

1sV2>4=1))0=1,2,—n)

X)+4$+6x、45小丁-x,+2gal

無(wú)符號(hào)限制

Xi.x,,x}>0X]?x?.Xj>O(i=1,2,…，m,j=1,2,…n)

2.turnW=5y,-4力?力3.maxW=2aM+26M

44?i?1?■1

2V+3力?力42ivi7yi>i>2

-2“+力?-1%+V,4c,

3為■比?4力%2

*7%?力》3

-”】?7力?6的44s.t/％,匕無(wú)符號(hào)約束

5“?2力=】

力沌力④小電

加③0?》無(wú)符4微創(chuàng)，力40(i==1,—,n)

六、已知線性規(guī)劃問(wèn)題

maxZ=4xi+7xz+2x3

Xi+2xz+X3&IO

s,r2xi+3X2+3x3410

Xi,x2,x3>0應(yīng)用對(duì)偶理論證明該問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值

不大于25

正明：解向》1對(duì)儒何11為：

minW=10”+10〉,

>1+2”.4

2yi*3?>7

‘''"+3s32

”5>。

經(jīng)觀*町博對(duì)例同胭