6、
A．無有限最優(yōu)解B．有有限最優(yōu)解C．有唯一最優(yōu)解D．有無窮多個最優(yōu)解E．有有限多個最優(yōu)解
5．下列說法錯誤的有_ABC_。
A． 基本解是大于零的解 B．極點與基解一一對應
C．線性規(guī)劃問題的最優(yōu)解是唯一的 D．滿足約束條件的解就是線性規(guī)劃的可行解
6.線性規(guī)劃問題若有最優(yōu)解，則最優(yōu)解 AD
A定在其可行域頂點達到 B只有一個 C會有無窮多個 D 唯一或無窮多個 E其值為0
四、名詞解釋
1基：在線性規(guī)劃問題中，約束方程組的系數(shù)矩陣A的任意一個m×m階的非奇異子方陣B，稱為線性規(guī)劃問題的一個基。
2、線性規(guī)劃問題：就是求一
7、個線性目標函數(shù)在一組線性約束條件下的極值問題。
3 .可行解：在線性規(guī)劃問題中，凡滿足所有約束條件的解稱為線性規(guī)劃問題可行解
4、可行域：線性規(guī)劃問題的可行解集合。
5、基本解：在線性約束方程組中，對于選定的基B令所有的非基變量等于零，得到的解，稱為線性規(guī)劃問題的一個基本解。
6.、基本可行解：在線性規(guī)劃問題中，滿足非負約束條件的基本解稱為基本可行解。
線性規(guī)劃的基本方法
一、填空題
1．對于目標函數(shù)極大值型的線性規(guī)劃問題，用單純型法求解時，當基變量檢驗數(shù)為0,非基變量檢驗數(shù)δj_≤_0時，當前解為最優(yōu)解。
2．用大M法求目標函數(shù)為極大值的線性規(guī)劃問題時，引入的人工變量在
8、目標函數(shù)中的系數(shù)應為－M。
3．在單純形迭代中，可以根據(jù)最終_表中人工變量不為零判斷線性規(guī)劃問題無解。
4．當線性規(guī)劃問題的系數(shù)矩陣中不存在現(xiàn)成的可行基時，一般可以加入人工變量構(gòu)造可行基。
5．在單純形迭代中，選出基變量時應遵循最小比值θ法則。
6．在單純形迭代過程中，若有某個δk>0對應的非基變量xk的系數(shù)列向量Pk_≤0_時，則此問題是無界的。
7.在大M法中，M表示充分大正數(shù)。
二、單選題
1．在單純形迭代中，出基變量在緊接著的下一次迭代中B立即進入基。
A．會 B．不會 C．有可能 D．不一定
2．在單純形法計算中，如不按最小比值原則選取
9、換出變量，則在下一個解中B。
A．不影響解的可行性B．至少有一個基變量的值為負C．找不到出基變量D．找不到進基變量
3．用單純形法求解極大化線性規(guī)劃問題中，在最優(yōu)單純形表中若某非基變量檢驗數(shù)為零，而其他非基變量檢驗數(shù)全部<0，則說明本問題B 。
A．有惟一最優(yōu)解 B．有多重最優(yōu)解 C．無界 D．無解
4．下列說法錯誤的是B
A． 圖解法與單純形法從幾何理解上是一致的 B．在單純形迭代中，進基變量可以任選
C．在單純形迭代中，出基變量必須按最小比值法則選取 D．人工變量離開基底后，不會再進基
5.單純形法當中，入基變量的確定應選擇檢
10、驗數(shù) C
A絕對值最大 B絕對值最小 C 正值最大 D 負值最小
6.在線性規(guī)劃問題的典式中，基變量的系數(shù)列向量為 D
A 單位陣 B非單位陣 C單位行向量 D單位列向量
7.在約束方程中引入人工變量的目的是 D
A 體現(xiàn)變量的多樣性 B 變不等式為等式 C 使目標函數(shù)為最優(yōu) D 形成一個單位陣
8.求目標函數(shù)為極大的線性規(guī)劃問題時，若全部非基變量的檢驗數(shù)≤O，且基變量中有人工變量時該問題有 B
A無界解 B無可行解 C 唯一最優(yōu)解
11、 D無窮多最優(yōu)解
三、多選題
1． 對取值無約束的變量xj。通常令xj=xj’- x”j，其中xj’≥0，xj”≥0，在用單純形法求得的最優(yōu)解中，可能出現(xiàn)的是ABC
2．設(shè)X(1)，X(2)是用單純形法求得的某一線性規(guī)劃問題的最優(yōu)解，則說明ACDE。
A．此問題有無窮多最優(yōu)解 B．該問題是退化問題 C．此問題的全部最優(yōu)解可表示為λX(1)+(1一λ)X(2)，其中0≤λ≤1 D．X(1)，X(2)是兩個基可行解E．X(1)，X(2)的基變量個數(shù)相同
3．單純形法中，在進行換基運算時，應ACDE。A．先選取進基變量，再選取出基變量B．先選出基變量，再選進基
12、變量C．進基變量的系數(shù)列向量應化為單位向量 D．旋轉(zhuǎn)變換時采用的矩陣的初等行變換E．出基變量的選取是根據(jù)最小比值法則
6．從一張單純形表中可以看出的內(nèi)容有ABCE。A．一個基可行解B．當前解是否為最優(yōu)解C．線性規(guī)劃問題是否出現(xiàn)退化D．線性規(guī)劃問題的最優(yōu)解E．線性規(guī)劃問題是否無界
四、名詞、簡答
1、人造初始可行基：當我們無法從一個標準的線性規(guī)劃問題中找到一個m階單位矩陣時，通常在約束方程中引入人工變量，而在系數(shù)矩陣中湊成一個m階單位矩陣，進而形成的一個初始可行基稱為人造初始可行基。
2、單純形法解題的基本思路？ 可行域的一個基本可行解開始，轉(zhuǎn)移到另一個基本可行解，并且使目標函數(shù)值
13、逐步得到改善，直到最后球場最優(yōu)解或判定原問題無解。
線性規(guī)劃的對偶理論
一、填空題
1．線性規(guī)劃問題具有對偶性，即對于任何一個求最大值的線性規(guī)劃問題，都有一個求最小值/極小值的線性規(guī)劃問題與之對應，反之亦然。
2．在一對對偶問題中，原問題的約束條件的右端常數(shù)是對偶問題的目標函數(shù)系數(shù)。
3．如果原問題的某個變量無約束，則對偶問題中對應的約束條件應為等式_。
4．對偶問題的對偶問題是原問題_。
5．若原問題可行，但目標函數(shù)無界，則對偶問題不可行。
6．線性規(guī)劃問題的最優(yōu)基為B，基變量的目標系數(shù)為CB，則其對偶問題的最優(yōu)解
Y﹡= CBB－1。
7．若X﹡和Y﹡分別是線性
14、規(guī)劃的原問題和對偶問題的最優(yōu)解，則有CX﹡= Y﹡b。
8．若X、Y分別是線性規(guī)劃的原問題和對偶問題的可行解，則有CX≤Yb。
9．若X﹡和Y﹡分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有CX﹡=Y*b。
10．設(shè)線性規(guī)劃的原問題為maxZ=CX，Ax≤b，X≥0，則其對偶問題為min=Yb YA≥c Y≥0_。
二、單選題
1．線性規(guī)劃原問題的目標函數(shù)為求極小值型，若其某個變量小于等于0，則其對偶問題約束條件為A形式。
A．“≥” B．“≤” C，“>” D．“=”
2．設(shè)、分別是標準形式的原問題與對偶問題的可行解,則 C 。
3．如果z。是某標準
15、型線性規(guī)劃問題的最優(yōu)目標函數(shù)值，則其對偶問題的最優(yōu)目標函數(shù)值w﹡A。
A．W﹡=Z﹡ B．W﹡≠Z﹡ C．W﹡≤Z﹡ D．W﹡≥Z﹡
4．如果某種資源的影子價格大于其市場價格，則說明_ B
A．該資源過剩B．該資源稀缺 C．企業(yè)應盡快處理該資源D．企業(yè)應充分利用該資源，開僻新的生產(chǎn)途徑
三、多選題
1．在一對對偶問題中，可能存在的情況是ABC。
A．一個問題有可行解，另一個問題無可行解 B．兩個問題都有可行解
C．兩個問題都無可行解 D．一個問題無界，另一個問題可行
2．
16、下列說法錯誤的是B 。
A．任何線性規(guī)劃問題都有一個與之對應的對偶問題B．對偶問題無可行解時，其原問題的目標函數(shù)無界。C．若原問題為maxZ=CX，AX≤b，X≥0，則對偶問題為minW=Yb，YA≥C，Y≥0。D．若原問題有可行解，但目標函數(shù)無界，其對偶問題無可行解。
3．如線性規(guī)劃的原問題為求極大值型，則下列關(guān)于原問題與對偶問題的關(guān)系中正確的是BCDE。
A原問題的約束條件“≥”，對應的對偶變量“≥0” B原問題的約束條件為“=”，對應的對偶變量為自由變量 C．原問題的變量“≥0”，對應的對偶約束“≥” D．原問題的變量“≤O”對應的對偶約束“≤”E．原問題的變量無符號限制，對應的對
17、偶約束“=”
4．一對互為對偶的問題存在最優(yōu)解，則在其最優(yōu)點處有BD
A．若某個變量取值為0，則對應的對偶約束為嚴格的不等式B．若某個變量取值為正，則相應的對偶約束必為等式C．若某個約束為等式，則相應的對偶變?nèi)≈禐檎鼶．若某個約束為嚴格的不等式，則相應的對偶變量取值為0 E．若某個約束為等式，則相應的對偶變量取值為0
四、名詞、簡答題
1、.對稱的對偶問題：設(shè)原始線性規(guī)劃問題為maxZ=CX s.t AX≤b X ≥0
稱線性規(guī)劃問題minW=Yb s.t YA≥C Y≥0 為其對偶問題。又稱它們?yōu)橐粚ΨQ的對偶問題。
2、影
18、子價格：對偶變量Yi表示與原問題的第i個約束條件相對應的資源的影子價格，在數(shù)量上表現(xiàn)為，當該約束條件的右端常數(shù)增加一個單位時（假設(shè)原問題的最優(yōu)解不變），原問題目標函數(shù)最優(yōu)值增加的數(shù)量。
3、一對對偶問題可能出現(xiàn)的情形：1.原問題和對偶問題都有最優(yōu)解，且二者相等；2.一個問題具有無界解，則另一個問題具有無可行解；3.原問題和對偶問題都無可行解。
線性規(guī)劃的靈敏度分析
一、填空題
1、在靈敏度分析中，某個非基變量的目標系數(shù)的改變，將引起該非基變量自身的檢驗數(shù)的變化。
2．如果某基變量的目標系數(shù)的變化范圍超過其靈敏度分析容許的變化范圍，則此基變量應出基。
3．若某約束常數(shù)bi的變化
19、超過其容許變動范圍，為求得新的最優(yōu)解，需在原最優(yōu)單純形表的基礎(chǔ)上運用對偶單純形法求解。
4.如果線性規(guī)劃的原問題增加一個約束條件，相當于其對偶問題增加一個變量。
5.若某線性規(guī)劃問題增加一個新的約束條件，在其最優(yōu)單純形表中將表現(xiàn)為增加一行，一列。
二、單選題
1．若線性規(guī)劃問題最優(yōu)基中某個基變量的目標系數(shù)發(fā)生變化，則C。
A．該基變量的檢驗數(shù)發(fā)生變化B．其他基變量的檢驗數(shù)發(fā)生變化C．所有非基變量的檢驗數(shù)發(fā)生變化D．所有變量的檢驗數(shù)都發(fā)生變化
2．在線性規(guī)劃的各項敏感性分析中，一定會引起最優(yōu)目標函數(shù)值發(fā)生變化的是B。
A．目標系數(shù)cj的變化B．約束常數(shù)項bi變化C．增加新的變量 D
20、．增加新約束
三、多選題
1．在靈敏度分析中，我們可以直接從最優(yōu)單純形表中獲得的有效信息有ABCE。
A．最優(yōu)基B的逆B-1 B．最優(yōu)解與最優(yōu)目標函數(shù)值 C．各變量的檢驗數(shù)
D．對偶問題的解 E．各列向量
3．線性規(guī)劃問題的各項系數(shù)發(fā)生變化，下列不能引起最優(yōu)解的可行性變化的是ABC_。
A．非基變量的目標系數(shù)變化 B．基變量的目標系數(shù)變化C．增加新的變量D，增加新的約束條件
四、名詞、簡答題
1.靈敏度分析：研究線性規(guī)劃模型的原始數(shù)據(jù)變化對最優(yōu)解產(chǎn)生的影響
運輸問題
一、填空題
1． 物資調(diào)運問題中，有m個供應地，Al，A2…，Am，
21、Aj的供應量為ai(i=1，2…，m)，n個需求地B1，B2，…Bn，B的需求量為bj(j=1，2，…，n)，則供需平衡條件為 =
2．物資調(diào)運方案的最優(yōu)性判別準則是：當全部檢驗數(shù)非負時，當前的方案一定是最優(yōu)方案。
3．可以作為表上作業(yè)法的初始調(diào)運方案的填有數(shù)字的方格數(shù)應為m+n－1個(設(shè)問題中含有m個供應地和n個需求地)
4．若調(diào)運方案中的某一空格的檢驗數(shù)為1，則在該空格的閉回路上調(diào)整單位運置而使運費增加1。
5．調(diào)運方案的調(diào)整是要在檢驗數(shù)出現(xiàn)負值的點為頂點所對應的閉回路內(nèi)進行運量的調(diào)整。
6．按照表上作業(yè)法給出的初始調(diào)運方案，從每一空格出發(fā)可以找到且僅能找到_1條閉回路
7．
22、在運輸問題中，單位運價為Cij位勢分別用ui，Vj表示，則在基變量處有cij Cij=ui+Vj 。
8、供大于求的、供不應求的不平衡運輸問題，分別是指_＞的運輸問題、_＜的運輸問題。
10．在表上作業(yè)法所得到的調(diào)運方案中，從某空格出發(fā)的閉回路的轉(zhuǎn)角點所對應的變量必為基變量。
11．在某運輸問題的調(diào)運方案中，點(2，2)的檢驗數(shù)為負值，(調(diào)運方案為表所示)則相應的調(diào)整量應為300_。
I
Ⅱ
Ⅲ
Ⅳ
A
300
100
300
B
400
C
600
300
12.若某運輸問題初始方案的檢驗數(shù)中只有一個負值：－2，則這個－2的含
23、義是該檢驗數(shù)所在格單位調(diào)整量。
13.運輸問題的初始方案中的基變量取值為正。
14在編制初始方案調(diào)運方案及調(diào)整中，如出現(xiàn)退化，則某一個或多個點處應填入數(shù)字0
二、單選題
1、在表上作業(yè)法求解運輸問題中，非基變量的檢驗數(shù)D。
A．大于0 B．小于0 C．等于0 D．以上三種都可能
2.運輸問題的初始方案中，沒有分配運量的格所對應的變量為 B
A基變量 B 非基變量 C 松弛變量 D 剩余變量
3.表上作業(yè)法中初始方案均為 A
A 可行解 B 非可行解 C 待
24、改進解 D 最優(yōu)解
4.閉回路是一條封閉折線，每一條邊都是 D
A 水平 B 垂直 C水平＋垂直 D水平或垂直
5.運輸問題中分配運量的格所對應的變量為 A
A基變量 B 非基變量 C 松弛變量 D 剩余變量
6.所有物資調(diào)運問題，應用表上作業(yè)法最后均能找到一個 D
A 可行解 B 非可行解 C 待改進解 D 最優(yōu)解
7.一般講，在給出的初始調(diào)運方案中，最接近最優(yōu)解的是 C
25、
A 西北角法 B 最小元素法 C 差值法 D 位勢法
8.在運輸問題中，調(diào)整對象的確定應選擇 C
A 檢驗數(shù)為負 B檢驗數(shù)為正 C檢驗數(shù)為負且絕對值最大 D檢驗數(shù)為負且絕對值最小
9.運輸問題中，調(diào)運方案的調(diào)整應在檢驗數(shù)為 C 負值的點所在的閉回路內(nèi)進行。
A 任意值 B最大值 C絕對值最大 D絕對值最小
10.表上作業(yè)法的基本思想和步驟與單純形法類似，因而初始調(diào)運方案的給出就相當于找到一個 C
A 基
26、B 可行解 C 初始基本可行解 D最優(yōu)解
11平衡運輸問題即是指m個供應地的總供應量 D n個需求地的總需求量。
A 大于 B 大于等于 C小于 D 等于
三、多選題
1．下列說法正確的是ABD。
A．表上作業(yè)法也是從尋找初始基可行解開始的 B．當一個調(diào)運方案的檢驗數(shù)全部為正值時，當前方案一定是最佳方案C．最小元素法所求得的運輸?shù)倪\量是最小的 D．表上作業(yè)法中一張供需平衡表對應一個基可行解
四、名詞
1、 平衡運輸問題：m個供應地的供應量等于n個需求地的總需求量，這樣的運輸問題稱平衡運輸問題。
2、不平衡運輸問題：m個
27、供應地的供應量不等于n個需求地的總需求量，這樣的運輸問題稱不平衡運輸問題。
整數(shù)規(guī)劃
一、填空題
1．用分枝定界法求極大化的整數(shù)規(guī)劃問題時，任何一個可行解的目標函數(shù)值是該問題目標函數(shù)值的下界。
2．在分枝定界法中，若選Xr=4／3進行分支，則構(gòu)造的約束條件應為X1≤1，X1≥2。
3．已知整數(shù)規(guī)劃問題P0，其相應的松馳問題記為P0’，若問題P0’無可行解，則問題P。無可行解。
4．在0 - 1整數(shù)規(guī)劃中變量的取值可能是_0或1。
5．對于一個有n項任務需要有n個人去完成的分配問題，其 解中取值為1的變量數(shù)為n個。
6．分枝定界法和割平面法的基礎(chǔ)都是用_線性規(guī)劃方法求解整數(shù)
28、規(guī)劃。
7．若在對某整數(shù)規(guī)劃問題的松馳問題進行求解時，得到最優(yōu)單純形表中，由X。所在行得X1+1／7x3+2／7x5=13／7，則以X1行為源行的割平面方程為_－X3－X5≤0_。
8.求解分配問題的專門方法是匈牙利法。
9．在應用匈牙利法求解分配問題時，最終求得的分配元應是獨立零元素_。
10.分枝定界法一般每次分枝數(shù)量為2個.
二、單選題
1．整數(shù)規(guī)劃問題中，變量的取值可能是D。
A．整數(shù)B．0或1C．大于零的非整數(shù)D．以上三種都可能
2．在下列整數(shù)規(guī)劃問題中，分枝定界法和割平面法都可以采用的是A 。
A．純整數(shù)規(guī)劃B．混合整數(shù)規(guī)劃C．0—1規(guī)劃D．線性規(guī)劃
29、
3．下列方法中用于求解分配問題的是D_。
A．單純形表B．分枝定界法C．表上作業(yè)法D．匈牙利法
三、多項選擇
1．下列說明不正確的是ABC。
A．求解整數(shù)規(guī)劃可以采用求解其相應的松馳問題，然后對其非整數(shù)值的解四舍五入的方法得到整數(shù)解。B．用分枝定界法求解一個極大化的整數(shù)規(guī)劃問題，當?shù)玫蕉嘤谝粋€可行解時，通常任取其中一個作為下界。C．用割平面法求解整數(shù)規(guī)劃時，構(gòu)造的割平面可能割去一些不屬于最優(yōu)解的整數(shù)解。D．用割平面法求解整數(shù)規(guī)劃問題時，必須首先將原問題的非整數(shù)的約束系數(shù)及右端常數(shù)化為整數(shù)。
2．在求解整數(shù)規(guī)劃問題時，可能出現(xiàn)的是ABC。
A．唯一最優(yōu)解B．無可行解 C．多重最
30、佳解D．無窮多個最優(yōu)解
3．關(guān)于分配問題的下列說法正確的是_ ABD。
A．分配問題是一個高度退化的運輸問題B．可以用表上作業(yè)法求解分配問題 C．從分配問題的效益矩陣中逐行取其最小元素，可得到最優(yōu)分配方案D．匈牙利法所能求解的分配問題，要求規(guī)定一個人只能完成一件工作，同時一件工作也只給一個人做。
4.整數(shù)規(guī)劃類型包括（ CDE ）
A 線性規(guī)劃 B 非線性規(guī)劃 C 純整數(shù)規(guī)劃 D 混合整數(shù)規(guī)劃 E 0—1規(guī)劃
三、名詞
1、純整數(shù)規(guī)劃：如果要求所有的決策變量都取整數(shù)，這樣的問題成為純整數(shù)規(guī)劃問題。
2、0—1規(guī)劃問題：在線性規(guī)劃問題中，如果要求所有的決
31、策變量只能取0或1，這樣的問題稱為0—1規(guī)劃。
3、混合整數(shù)規(guī)劃：在線性規(guī)劃問題中，如果要求部分決策變量取整數(shù)，則稱該問題為混合整數(shù)規(guī)劃。
圖與網(wǎng)絡分析
一、填空題
1．任一樹中的邊數(shù)必定是它的頂點數(shù)減1。
2．最小樹問題就是在網(wǎng)絡圖中，找出若干條邊，連接所有結(jié)點，而且連接的總長度最小。
3．18、求支撐樹有 破圈 法和 避圈 法兩種方法。
二、單選題
1、關(guān)于圖論中圖的概念，以下敘述(B)正確。
A圖中的有向邊表示研究對象，結(jié)點表示銜接關(guān)系。 B圖中的點表示研究對象，邊表示點與點之間的關(guān)系。C圖中任意兩點之間必有邊。 D圖的邊數(shù)必定等于點數(shù)減
32、1。
2．關(guān)于樹的概念，以下敘述(B)正確。
A樹中的點數(shù)等于邊數(shù)減1 B連通無圈的圖必定是樹 C含n個點的樹是唯一的 D任一樹中，去掉一條邊仍為樹。
3．一個連通圖中的最小樹(B)，其權(quán)(A)。
A是唯一確定的 B可能不唯一 C可能不存在 D一定有多個。
4．關(guān)于最大流量問題，以下敘述(D)正確。
A一個容量網(wǎng)絡的最大流是唯一確定的B達到最大流的方案是唯一的C當用標號法求最大流時，可能得到不同的最大流方案D當最大流方案不唯一時，得到的最大流量亦可能不相同。
5．圖論中的圖，以下敘述(C)不正確。
A．圖論中點表示研究對象，邊或有向邊表
33、示研究對象之間的特定關(guān)系。B．圖論中的圖，用點與點的相互位置，邊的長短曲直來表示研究對象的相互關(guān)系。C．圖論中的邊表示研究對象，點表示研究對象之間的特定關(guān)系。 D．圖論中的圖，可以改變點與點的相互位置。只要不改變點與點的連接關(guān)系。
6．關(guān)于最小樹，以下敘述(B)正確。
A．最小樹是一個網(wǎng)絡中連通所有點而邊數(shù)最少的圖B．最小樹是一個網(wǎng)絡中連通所有的點，而權(quán)數(shù)最少的圖C．一個網(wǎng)絡中的最大權(quán)邊必不包含在其最小樹內(nèi)D．一個網(wǎng)絡的最小樹一般是不唯一的。
7．關(guān)于可行流，以下敘述(A)不正確。
A．可行流的流量大于零而小于容量限制條件B．在網(wǎng)絡的任一中間點，可行流滿足流人量=流出量。C．各條
34、有向邊上的流量均為零的流是一個可行流D．可行流的流量小于容量限制條件而大于或等于零。
三、多選題
1．關(guān)于圖論中圖的概念，以下敘述(123)正確。
(1)圖中的邊可以是有向邊，也可以是無向邊 (2)圖中的各條邊上可以標注權(quán)。(3)結(jié)點數(shù)等于邊數(shù)的連通圖必含圈(4)結(jié)點數(shù)等于邊數(shù)的圖必連通。
2．關(guān)于樹的概念，以下敘述(123)正確。
1)樹中的邊數(shù)等于點數(shù)減1(2)樹中再添一條邊后必含圈。(3)樹中刪去一條邊后必不連通(4)樹中兩點之間的通路可能不唯一。
3．從連通圖中生成樹，以下敘述(134)正確。
(1)任一連通圖必有支撐樹 (2)任一連通圖生成的支撐樹必唯一(3)在支撐樹中
35、再增加一條邊后必含圈(4)任一連通圖生成的各個支撐樹其邊數(shù)必相同
4．在下圖中，(abcd)不是根據(jù)(a)生成的支撐樹。
5．從賦權(quán)連通圖中生成最小樹，以下敘述(124)不正確。
(1)任一連通圖生成的各個最小樹，其總長度必相等(2)任一連通圖生成的各個最小樹，其邊數(shù)必相等。(3)任一連通圖中具有最小權(quán)的邊必包含在生成的最小樹上。(4)最小樹中可能包括連通圖中的最大權(quán)邊。
6．從起點到終點的最短路線，以下敘述(123)不正確。
1)從起點出發(fā)的最小權(quán)有向邊必含在最短路線中。 (2)整個圖中權(quán)最小的有向邊必包含在最短路線中。(3)整個圖中權(quán)最大的有向邊可能含在最短路線中 (4)從起
36、點到終點的最短路線是唯一的。
7．關(guān)于帶收發(fā)點的容量網(wǎng)絡中從發(fā)點到收點的一條增廣路，以下敘述( 123)不正確。
(1)增廣路上的有向邊的方向必須是從發(fā)點指向收點的(2)增廣路上的有向邊，必須都是不飽和邊 (3)增廣路上不能有零流邊(4)增廣路上與發(fā)點到收點方向一致的有向邊不能是飽和邊，相反方向的有向邊不能是零流邊
8．關(guān)于樹，以下敘述(ABCE)正確。
A．樹是連通、無圈的圖B．任一樹，添加一條邊便含圈C．任一樹的邊數(shù)等于點數(shù)減1。D．任一樹的點數(shù)等于邊數(shù)減1E．任一樹，去掉_條邊便不連通。
9．關(guān)于最短路，以下敘述(ACDE)不正確。
A從起點出發(fā)到終點的最短路是唯一的。
37、B．從起點出發(fā)到終點的最短路不一定是唯一的，但其最短路線的長度是確定的。C．從起點出發(fā)的有向邊中的最小權(quán)邊，一定包含在起點到終點的最短路上D．從起點出發(fā)的有向邊中的最大權(quán)邊，一定不包含在起點到終點的最短路上。 E．整個網(wǎng)絡的最大權(quán)邊的一定不包含在從起點到終點的最短路線上。
10．關(guān)于增廣路，以下敘述(BC )正確。
A．增廣路是一條從發(fā)點到收點的有向路，這條路上各條邊的方向必一致。B．增廣路是一條從發(fā)點到收點的有向路，這條路上各條邊的方向可不一致。C．增廣路上與發(fā)點到收點方向一致的邊必須是非飽和邊，方向相反的邊必須是流量大于零的邊。D．增廣路上與發(fā)點到收點方向一致的邊必須是流量小于容量的
38、邊，方向相反的邊必須是流量等于零的邊。E．增廣路上與發(fā)點到收點方向一致的邊必須是流量為零的邊，方向相反的邊必須是流量大于零的邊。
四、名詞解釋
1、樹:在圖論中，具有連通和不含圈特點的圖稱為樹。
2．權(quán)：在圖中，邊旁標注的數(shù)字稱為權(quán)。
3．網(wǎng)絡：在圖論中，給邊或有向邊賦了權(quán)的圖稱為網(wǎng)絡
4．最大流問題：最大流問題是指在網(wǎng)絡圖中，在單位時間內(nèi)，從發(fā)點到收點的最大流量
5．最大流問題中流量：最大流問題中流量是指單位時間的發(fā)點的流出量或收點的流入量。
6．容量：最大流問題中，每條有向邊單位時間的最大通過能力稱為容量
7．飽合邊：容量與流量相等的有向邊稱為飽合邊。
8零流邊：流量為零
39、的有向邊稱為零流邊
9.生成樹：若樹T是無向圖G的生成樹，則稱T是G 的生成樹。.。
計算題（答案參考課件）
1．圖解法求線性規(guī)劃問題。
2．利用對偶理論求解線性規(guī)劃問題。
已知原問題的最優(yōu)解為X* =（），Z=12 試求對偶問題的最優(yōu)解。
3．靈敏度分析（學會單純型法和對偶單純型法的計算）
某企業(yè)利用三種資源生產(chǎn)兩種產(chǎn)品的最優(yōu)計劃問題歸結(jié)為下列線性規(guī)劃
已知最優(yōu)表如下。
（1）確定x2的系數(shù)c2的變化范圍，使原最優(yōu)解保持最優(yōu)；
（2）若c2=6，求新的最優(yōu)計劃。
（3）b3在什么范圍內(nèi)變化，原最優(yōu)基不變？
（4）若b3=55，求出新的最優(yōu)解
40、。
（5）設(shè)企業(yè)研制了一種新產(chǎn)品，對三種資源的消耗系數(shù)列向量以P6表示，
P6= 。問它的價值系數(shù)c6符合什么條件才必須安排它的生產(chǎn)？設(shè)c6=3，新的最優(yōu)生產(chǎn)計劃是什么？
（6）假設(shè)還要考慮一個新的資源約束：4x1+2x2≤150，新的最優(yōu)生產(chǎn)計劃是什么？
cj
5
4
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
0
x3
25
0
0
1
2
-5
5
x1
35
1
0
0
1
-1
4
x2
10
0
1
0
-1
2
0
0
0
-1
-3
4．指派問題
有
41、一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務，可使總時間最少？
5．產(chǎn)銷平衡運輸問題
已知某運輸問題的資料如下表所示，試求出最優(yōu)運輸方案。
任務
人員
A
B
C
D
甲
6
7
11
2
乙
4
5
9
8
丙
3
1
10
4
丁
5
9
8
2
B1
B2
B3
B4
發(fā)量
A1
2
6
5
3
15
A2
1
3
2
1
12
A3
3
2
7
4
13
收量
10
13
12
5
6．最短路問題
求下圖從v1到v6的最短路。
v1
v2
v3
v4
v6
v5
3
5
2
2
4
2
4
2
1
應用題（只寫規(guī)劃，不用求解）
書P44例13，例14
P121-126 例3，例4，例5，例6
第一章課件最后一部分的線性規(guī)劃建模
《運籌學復習題》word版
