實(shí)用運(yùn)籌學(xué)習(xí)題選詳解復(fù)習(xí)過(guò)程

1、實(shí)用運(yùn)籌學(xué)習(xí)題選詳解精品資料運(yùn)籌學(xué)判斷題一、第1章線性規(guī)劃的基本理論及其應(yīng)用1、線性規(guī)劃問(wèn)題的可行解集不一定是凸集。（X）2、若線性規(guī)劃無(wú)最優(yōu)解則其可行域無(wú)界。（X）3、線性規(guī)劃具有惟一的最優(yōu)解是指最優(yōu)表中非基變量檢驗(yàn)數(shù)全部非零。（V）4、線性規(guī)劃問(wèn)題的每一個(gè)基本可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)。（V）5、若線性規(guī)劃模型的可行域非空有界，則其頂點(diǎn)中必存在最優(yōu)解。（V）6線性規(guī)劃問(wèn)題的大M法中，M是負(fù)無(wú)窮大。（X）7、單純形法計(jì)算中，若不按最小比值原則選取換出變量，則在下一個(gè)解中至少 有一個(gè)基變量為負(fù)。（V）8、對(duì)于線性規(guī)劃問(wèn)題的基本可行解，若大于零的基變量數(shù)小于約束條件數(shù)，則 解是退化的。（V）。9

2、、一旦一個(gè)人工變量在迭代過(guò)程中變?yōu)榉腔兞亢?，則該變量及相應(yīng)列的數(shù)字 可以從單純性表中刪除，且這樣做不影響計(jì)算結(jié)果。（V）10、線性規(guī)劃的目標(biāo)函數(shù)中系數(shù)最大的變量在最優(yōu)解中總是取正值。（X）11、對(duì)一個(gè)有n個(gè)變量，m個(gè)約束的標(biāo)準(zhǔn)型的線性規(guī)劃問(wèn)題，其可行域的頂點(diǎn)恰好為個(gè)Cm 0（X）12、線性規(guī)劃解的退化問(wèn)題就是表明有多個(gè)最優(yōu)解。（X）13、如果一個(gè)線性規(guī)劃問(wèn)題有兩個(gè)不同的最優(yōu)解，則它有無(wú)窮多個(gè)最優(yōu)解。（V）14、單純型法解線性規(guī)劃問(wèn)題時(shí)值為 0的變量未必是非基變量。（V）15、任何線性規(guī)劃問(wèn)題度存在并具有唯一的對(duì)偶問(wèn)題。（V）16、對(duì)偶問(wèn)題的對(duì)偶問(wèn)題一定是原問(wèn)題。（V）17、根據(jù)對(duì)偶問(wèn)題的性質(zhì)

3、，當(dāng)原問(wèn)題為無(wú)界解時(shí)，其對(duì)偶問(wèn)題無(wú)可行解；反之，當(dāng)對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題為無(wú)界解。（X）18、若原問(wèn)題有可行解，則其對(duì)偶問(wèn)題也一定有可行解。（X）19、若原問(wèn)題無(wú)可行解，其對(duì)偶問(wèn)題也一定無(wú)可行解。（X）20、若原問(wèn)題有最優(yōu)解，其對(duì)偶問(wèn)題也一定有最優(yōu)解。（V）21、 已知yi*為線性規(guī)劃的對(duì)偶問(wèn)題的最優(yōu)解，若 y* 0 ,說(shuō)明在最優(yōu)生產(chǎn)計(jì)劃 中，第i種資源一定有剩余。（X）22、原問(wèn)題具有無(wú)界解，則對(duì)偶問(wèn)題不可行。（V）23、互為對(duì)偶問(wèn)題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無(wú)最優(yōu)解。（V）24、某公司根據(jù)產(chǎn)品最優(yōu)生產(chǎn)計(jì)劃，若原材料的影子價(jià)格大于它的市場(chǎng)價(jià)格， 則可購(gòu)進(jìn)原材料擴(kuò)大生產(chǎn)。（V）25

4、、對(duì)于線性規(guī)劃問(wèn)題，已知原問(wèn)題基本解不可行，對(duì)偶問(wèn)題基本解可行，可 采用對(duì)偶單純形法求解。（V）26、 原問(wèn)題（極小值）第i個(gè)約束是“ ”約束，則對(duì)偶變量yi 0 0（V）27、線性規(guī)劃問(wèn)題的原單純形解法，可以看作是保持原問(wèn)題基本解可行，通過(guò) 迭代計(jì)算，逐步將對(duì)偶問(wèn)題的基本解從不可行轉(zhuǎn)化為可行的過(guò)程。（V）*28、運(yùn)輸問(wèn)題不能化為最小費(fèi)用流問(wèn)題來(lái)解決。（X）29、運(yùn)輸問(wèn)題一定有最優(yōu)解。（V）30、若運(yùn)輸問(wèn)題的可行解退化，貝U存在等于零的數(shù)字格。（V）31、運(yùn)輸問(wèn)題是特殊的線性規(guī)劃問(wèn)題，表上作業(yè)法也是特殊形式的單純形法。32、按最小元素法（或伏格爾法）給出的初始基可行解，從每一空格出發(fā)可以 找出

5、，而且僅能找出唯一閉合回路。（V）33、如果運(yùn)輸問(wèn)題單位運(yùn)價(jià)表的某一行（或某一列）元素分別乘上一個(gè)常數(shù)k，調(diào)運(yùn)方案將不會(huì)發(fā)生變化。（X）34、如果運(yùn)輸問(wèn)題單位運(yùn)價(jià)表的某一行（或某一列）元素分別加上一個(gè)常數(shù)k，調(diào)運(yùn)方案將不會(huì)發(fā)生變化。（V）35、 如果運(yùn)輸問(wèn)題單位運(yùn)價(jià)表的全部元素分別乘上一個(gè)常數(shù)k k 0，調(diào)運(yùn)方 案將不會(huì)發(fā)生變化。（V）36、運(yùn)輸問(wèn)題獨(dú)立約束條件數(shù) m n 1個(gè)，變量數(shù)是mn個(gè)，于是基變量數(shù)為 mn m n 個(gè)。（X）37、整數(shù)規(guī)劃解的目標(biāo)函數(shù)值一般優(yōu)于其相應(yīng)的線性規(guī)劃問(wèn)題的解的目標(biāo)函數(shù) 值。（X）38、一個(gè)整數(shù)規(guī)劃問(wèn)題如果存在兩個(gè)以上的最優(yōu)解，則該問(wèn)題一定有無(wú)窮多最 優(yōu)解&#

6、176;（x）39、分支定界法在需要分支時(shí)必須滿足：一是分支后的各子問(wèn)題必須容易求解；二是各子問(wèn)題解的集合必須覆蓋原問(wèn)題的解 °（V）40、整數(shù)規(guī)劃的最優(yōu)解是先求相應(yīng)的線性規(guī)劃的最優(yōu)解然后取整得到。（X）41、用分支定界法求解一個(gè)極大化的整數(shù)規(guī)劃問(wèn)題時(shí)，任何一個(gè)可行解的目標(biāo) 函數(shù)值是該問(wèn)題的下界。（V）42、用分支定界法求解一個(gè)極大化的整數(shù)規(guī)劃問(wèn)題，當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解 時(shí)。通?？扇稳∑渲幸粋€(gè)作為下界值，再進(jìn)行比較剪枝。（X）（V）僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝5精品資料43、求最大值的整數(shù)規(guī)劃問(wèn)題中，其松弛問(wèn)題的最優(yōu)解是整數(shù)規(guī)劃問(wèn)題最優(yōu)解 的上界。（V）44、匈牙利算

7、法是對(duì)指派問(wèn)題求最小值的一種求解方法。（V）45、指派問(wèn)題效率矩陣的每個(gè)元素分別乘上一個(gè)常數(shù) k，將不影響最優(yōu)指派方 案。（X）46、指派問(wèn)題數(shù)學(xué)模型的形式同運(yùn)輸問(wèn)題十分相似，故也可以用表上作業(yè)法求解。（V）47、匈牙利算法是對(duì)指派問(wèn)題求最小值的一種求解方法。（V）48、應(yīng)用匈牙利算法求解工作指派問(wèn)題時(shí)，對(duì)不打勾的行和打鉤的列畫(huà)橫線。（V）49、求解效率最大的指派問(wèn)題，可以用指派矩陣的最小元素減去該矩陣的各元素，得到新的指派矩陣，再用匈牙利算法求解。（X）1、圖論中的圖不僅反映了研究對(duì)象之間的關(guān)系，而且是真實(shí)圖形的寫(xiě)照，因而 對(duì)圖中點(diǎn)與點(diǎn)的相對(duì)位置、點(diǎn)與點(diǎn)的連線的長(zhǎng)短曲直等都要嚴(yán)格注意。（X）

8、2、連通圖G的部分樹(shù)是取圖G的點(diǎn)和G的所有邊組成的樹(shù)。（X）3、在有向圖中，鏈和路是一回事。（X）4、連通圖一定有支撐樹(shù)。（V）5、避圈法（加邊法）是：去掉圖中所有邊，從最短邊開(kāi)始添加，加邊的過(guò)程中 不能形成圈，直到有n條邊（n為圖中的點(diǎn)數(shù)）°（X）&應(yīng)用矩陣法計(jì)算網(wǎng)絡(luò)最小支撐樹(shù)問(wèn)題，應(yīng)當(dāng)在所有記有 T的行里沒(méi)有劃去的 元素中尋找最小元素。（V）7、用避圈法得到的最小樹(shù)是惟一的，但破圈法得到的則不是。（X）8、最小生成樹(shù)的Kruskal算法，每次迭代是將剩下邊集中的最小權(quán)邊加入樹(shù) 中。（X）9、Dijkstra算法和Ford算法均要求邊的權(quán)重非負(fù)。（2?）°（X）1

9、0、Dijkstra算法可用于正權(quán)網(wǎng)絡(luò)也可用于負(fù)權(quán)網(wǎng)絡(luò)。（X）11、Dijkstra算法可用于求解有負(fù)權(quán)的網(wǎng)絡(luò)最短路問(wèn)題。（X）12、Dijkstra算法可用于求解最短路中的所有情形。（X）13、Dijkstra算法是求最大流的一種標(biāo)號(hào)算法。（X）14、在最短路問(wèn)題中，發(fā)點(diǎn)到收點(diǎn)的最短路長(zhǎng)是惟一的。（V）15、求圖的最小支撐樹(shù)以及求圖中一點(diǎn)到另一點(diǎn)的最短路問(wèn)題，都可以歸結(jié)為 求解整數(shù)規(guī)劃問(wèn)題。（V）16、只有一個(gè)奇點(diǎn)的連通圖是歐拉圖。（X）17、在任何網(wǎng)絡(luò)流中，零流總是一個(gè)可行流。（V）18、在最大流問(wèn)題中，最大流是惟一的。（X）19、最大流問(wèn)題是找一條從發(fā)點(diǎn)到收點(diǎn)的路，使得通過(guò)這條路的流量最

10、大。（X）20、 容量Cij是弧i, j的實(shí)際通過(guò)量。（X）21、可行流是最大流的充要條件是不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈。（V）22、一個(gè)具有多個(gè)發(fā)點(diǎn)和多個(gè)收點(diǎn)地求網(wǎng)絡(luò)最大流的問(wèn)題一定可以轉(zhuǎn)化為具有 單個(gè)發(fā)點(diǎn)和單個(gè)收點(diǎn)地求網(wǎng)絡(luò)最大流問(wèn)題。（V）23、形成增廣鏈的條件是對(duì)于正向弧必須滿足 fj 0 o （X）24、可行流的流量等于每條弧上的流量之和。（X）25、最大流量等于最大流。（X）26、求網(wǎng)絡(luò)最大流的問(wèn)題可歸結(jié)為求解一個(gè)線性規(guī)劃模型。（V）27、若已求得網(wǎng)絡(luò)最大流，已標(biāo)號(hào)節(jié)點(diǎn)的集合和未標(biāo)號(hào)節(jié)點(diǎn)的集合給出了網(wǎng)絡(luò) 的最小割集。（V）28、網(wǎng)絡(luò)最大流等于該網(wǎng)絡(luò)最大割容量。（X）29、割集中弧的流量之

11、和稱為割量。（X）30、最小割集等于最大流量。（X）31、任意可行流得流量不超過(guò)任意割量。（V）32、若已給網(wǎng)絡(luò)的一個(gè)最小費(fèi)用可行流，它的最小費(fèi)用增廣鏈對(duì)應(yīng)于長(zhǎng)度網(wǎng)絡(luò)（賦權(quán)圖）的最短路。（V）33、總時(shí)差為零的各項(xiàng)作業(yè)所組成的路線即為關(guān)鍵路線。（V）34、工程網(wǎng)絡(luò)圖中關(guān)鍵路線是最長(zhǎng)路線。（V）35、網(wǎng)絡(luò)規(guī)劃中，工作的機(jī)動(dòng)時(shí)間或富余時(shí)間叫做時(shí)差，分為總時(shí)差和單時(shí) 差。（V）36、以同一節(jié)點(diǎn)為開(kāi)始事件的各項(xiàng)作業(yè)的最早開(kāi)始時(shí)間相同。（V）37、以同一節(jié)點(diǎn)為結(jié)束事件的各項(xiàng)作業(yè)的最遲結(jié)束時(shí)間相同。（V）38、節(jié)點(diǎn)的最早開(kāi)始時(shí)間與最遲完成時(shí)間兩兩相同所組成的路線是關(guān)鍵路線。（X）39、優(yōu)化網(wǎng)絡(luò)圖計(jì)劃，保證

12、資源的最優(yōu)配置和工期的按時(shí)完成，通常根據(jù)工作 的時(shí)差，采用非關(guān)鍵路線上的工作開(kāi)始時(shí)間來(lái)實(shí)現(xiàn)。（V）40、采取應(yīng)急措施，往往不但縮短了工期環(huán)可以減少工程總費(fèi)用。（X）41、工程網(wǎng)絡(luò)圖中，只能有一個(gè)開(kāi)始節(jié)點(diǎn)，但可以有多個(gè)結(jié)束節(jié)點(diǎn)。（X）僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝7精品資料42、工程網(wǎng)絡(luò)圖中，事項(xiàng)只表示某項(xiàng)工作結(jié)束的狀態(tài)。（X）43、工程網(wǎng)絡(luò)圖可以有幾個(gè)初始事項(xiàng)，但不可以有幾個(gè)最終事項(xiàng)。（X）44、虛活動(dòng)的作業(yè)時(shí)間等于零。（V）45、在網(wǎng)絡(luò)圖得關(guān)鍵路線上，總時(shí)差等于零。（V）1、矩陣對(duì)策中，如果最優(yōu)解要求一個(gè)局中人采取純策略，則另一個(gè)局中人也必須采取純策略。（X）2、任何矩陣對(duì)策一定

13、存在混合策路意義下的解，并可以通過(guò)求解兩個(gè)互為對(duì)偶的線性規(guī)劃問(wèn)題得到。（V）3、對(duì)策模型的三要素：局中人、策略、贏得函數(shù)。（V）4、 在兩人零和對(duì)策支付矩陣的某一行（或某一列）上加上一個(gè)常數(shù)k，將不影 響對(duì)策雙方各自的最優(yōu)策略。（X）5、 二人零和對(duì)策支付矩陣的所有元素乘上一個(gè)常數(shù)k，將不影響對(duì)策雙方各自 的最優(yōu)策略。（V）6應(yīng)對(duì)災(zāi)害天氣制定預(yù)案的策略，同制訂對(duì)一場(chǎng)可能發(fā)生的軍事沖突的策略，具有相同的性質(zhì)和過(guò)程。（X）7、如果在任一“局勢(shì)”中，全體局中人的“得失”相加總是等于零，這個(gè)對(duì)策就叫 做“零和對(duì)策” °（V）8、任何一個(gè)給定的矩陣對(duì)策 G 一定有解（在混合擴(kuò)充中的解）

14、6;（V）9、一個(gè)矩陣對(duì)策問(wèn)題的贏得矩陣 A aj，一定有不等式max min aij min maxaij 0（X）1 3210、 已知某對(duì)策問(wèn)題的贏得函數(shù)矩陣為 5 2 3，所以它是純策略對(duì)策問(wèn)2 43題。（X）11、二人零和有限對(duì)策問(wèn)題中，對(duì)局雙方的贏得函數(shù)值互為相反數(shù)。（V）12、最優(yōu)純策略中，mpxminay min maxa,a為局中人贏得函數(shù)中的元素。（V）運(yùn)籌學(xué)實(shí)用教程解答題、第1章線性規(guī)劃的基本理論及其應(yīng)用max z 3x1 2x22x-i4x2221（ 1.3.1）、用圖解法解線性規(guī)劃問(wèn)題x14x210(答案:s.t2 x-i4x27X13x21x1, x20max z 2

15、1;x5,x2 3 )線性規(guī)劃圖解法20 I1.115 僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝11-2011111024681012x=(0:0.1:12)：y1=(22-2*x)/4;y2=2*x-7;y3=(x+10)/4;y4=(x-1)/3;z1=(1-3*x)/2;z2=(4-3*x)/2;z3=(8-3*x)/2;z4=(12-3*x)/2;'b-plot(x,y1, 'g：',x,y2,'g:',x,y3,'g：',x,y4,'g:',x,z1,'b-',x,z2,',x,z3,

16、'b-',x,z4,'b-');title('?D?1? i ?a ');精品資料max z 2x1 x2x2102x1 5x2602 (1.3.2)、用圖解法解線性規(guī)劃問(wèn)題1(答案:s.t x1 x2183x-i x244x1, x20僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝11x=(0:0.1:15)'y1=10;y2=(60-2*x)/5;y3=18-x;y4=44-3*x;z1=1-2*x;z2=4-2*x;z3=8-2*x;z4=12-2*x;'b-plot(x,y1, 'g:',x,y2,'g

17、:',x,y3,'g:',x,y4,'g:',x,z1,'b-',x,z2,',x,z3,'b-',x,z4,'b-');title('?D?1? i ?a ');精品資料僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝23max z 3 2x23 （1.3.3）、用圖解法解線性規(guī)劃問(wèn)題x13s.t x1x20（答案：可行域無(wú)界,x1, x20無(wú)最優(yōu)解）0.552線性規(guī)劃圖解法x1=3-3x1+2x2=1 -3x1+2x2=4（圖形是matlab結(jié)合幾何畫(huà)板繪制出來(lái)的）max z 3%

18、2x24（ 1.3.4）、用圖解法解線性規(guī)劃問(wèn)題x1x21s.t2x1 2x2 4（答案：無(wú)可行域，無(wú)最x1, x?0優(yōu)解）（圖形是matlab結(jié)合幾何畫(huà)板繪制出來(lái)的）max z 4x1 3x23% 2x265 （1.3.5）、用圖解法解線性規(guī)劃問(wèn)題1（答案：可行域無(wú)界,s.t x1 3x2 18x1, x20無(wú)最優(yōu)解）線性規(guī)劃圖解法x=(0:0.1:3)'y1=(6+3*x)/2;y2=(18+x)/3;z1=(12-4*x)/3;z2=(20-4*x)/3;plot(x,y1, 'g：',x,y2,'g:',x,z1,'b-',x,z

19、2,'b-');title('?D?1? i ?a ');(圖形是matlab結(jié)合幾何畫(huà)板繪制出來(lái)的)maxz 2x1 3x26 (1.3.6)、用圖解法解線性規(guī)劃問(wèn)題4x116s.t x1 2x28(答案:max z 14“4, x22)x=(0:0.1:9)'y1=(8-x)/2;z1=(12-2*x)/3;z2=(20-2*x)/3;plot(x,y1, 'g:',x,z1,'b-',x,z2,'b-');title('?D?1? i ?a ');線性規(guī)劃圖解注(圖形是matlab結(jié)合

20、幾何畫(huà)板繪制出來(lái)的)max z7 (1.4.1)、用單純形法計(jì)算X22x,st X13x,2x1 x2105x260x218x244x1, x20(答案：maxz 31“ 13, x2 5 ,松弛變量x3詳解：弓I進(jìn) 松弛變量X3,X4,X5,X6，標(biāo)準(zhǔn)化模型為5,X49,X5X60 )max z2x1X2X2X3102x-i5x2X460s.tx1X2X5183x_jX2X644X1,X2,X3,X4,X5,X60建立初始單純形表并作基的變換如下,XX1X2X3X4X5X6bthitac210000X3001100010X402601006060/2=30X501100101818/ 仁18

21、X603100014444/3 最??！zj00000 d00Zj-cj2-10000先找負(fù)的絕對(duì)值最大的定入X300110001010X40013/3010-2/392/392/13X5002/3001-1/310/35最?。《?岀X1211/3000 d1/344/344zj22/30002/388/3下一行+cjZj-cj01/30002/3先找負(fù)的絕對(duì)值最大的定入X300010-3/21/25X40000113/23/29X2101003/2-1/25X121000-1/21/213zj21001/21/231下一行+cjZj-cj00001/2 n1/2最優(yōu)性判別，得知最優(yōu)解5n從表中

22、得答案，maxz 31;x19, X5X60 013, X25 ,松弛變量Xgmaxz4x13x26X33為X23X330st 2為3x?3x340X1,X2,X3010, x320/3)8 (142)、用單純形法計(jì)算maxz詳解：引進(jìn)松弛變量X4, X5，標(biāo)準(zhǔn)化模型為3x1 st 2x1X23x23x23x33x36X3X4Xi,X2,X3,X4,X5X5030040(答案：maxz 70; x10,x2建立初始單純形表并作基的變換如下,XX1X2X3X4X5bthitac43600X40313103030/3=10,最小出 基X50223014040/3>10zj000000Zj-c

23、j-4-3-6 丁00先找負(fù)的絕對(duì)值最大的定入X3611/311/301030X50-110-111010,最小出基zj6262060下一行+cjZj-cj2-1020先找負(fù)的絕對(duì)值最大的定入X364/3012/3-1/320/3X23-110-1110zj5361170下一行+cjZj-cj10011最優(yōu)性判別，得知最優(yōu)解從表中得答案，maxz 70;論0X10, X320/3min z2x1X25x3X4X425X1X2X3X4206x3s.t 4x159 (143)、現(xiàn)有單純形法問(wèn)題2 2x2 3x3 2x430x1,x2, x30, x4無(wú)非負(fù)要求max( z)2為x2 5x3 x4

24、x4 Xt 0 x5X1X4X4X525X2X3X4x4 x620(答案:mx6 0 x7 mx8 0 x9 o x0 mx“(1)化為標(biāo)準(zhǔn)型；(2)列出初始單純型表4* st2x26x3X7X 53x32x42X4Xg302x23x32x42x4 X10X11 2xi,x2,x3,x4,x4,x5,x6,x7,x5,xg,xio,xi1 0XX1X2X3X41X42X5X6X7X8X9X10X11bc-2-151-10-M0-M00-MX503001-1100000025X6M1111-1010000020X8M4060000-110005X900232-2000010030X11M0232

25、-200000-112zj5M3M10M-3M3M0-MM-M0M-M27MZj-cj5M+23M+1-1UIVI-5-3IVI-1-3IVI+1IM0M0)maxz 60x1 50x2% 2x24010 (1.6.1.1)求線性規(guī)劃2為X26的對(duì)偶問(wèn)題(答案:s.tx1 x225x1, x20min w 40y1 6y2 25y3y 2y2 y360)st 2y1 y2 y3 50Y1，Y2, Y30maxz2428x24為6x24811( 1.6.1.2)、求線性規(guī)劃s.tx19的對(duì)偶問(wèn)題（答案:X27x1,x20min w 48y19y2 7y34y1 y224)st 6y1 y328y

26、2, y30, y1無(wú)非負(fù)要求min z 2x1 x2 6x3 x43x1 x42512（ 161.3）、求線性規(guī)劃s.tX1 X2 x3 X44x1 6x3520的對(duì)偶問(wèn)題（答案:2 2x2 3x3 2x430x1, x2, x30, &無(wú)非負(fù)要求min z2x1X26X3X43x1X425X1x2 x3 x 20st4x16X352x23x32x42繼而得max w25y1 20y2 5y3 2y4 30 y52x2 3x3 2x430x!，x2, x3 0,x4無(wú)非負(fù)要求3y1 y2 4y32Y2 2y4 2y51y2 6y3 3y4 3%6Y1 y2 2y4 2y51%”3，丫

27、450, y2無(wú)非負(fù)要求min f 6x1 4x2x 2x2413 (161.4)、求線性規(guī)劃的對(duì)偶問(wèn)題(答案:s.t 2x1 x22x1,x20maxw 4y1 2y2* 2y26)st 2*1 *24*1,*2 0min f 5x1 3x22x. 3x2614 (161.5)、求線性規(guī)劃2 的對(duì)偶問(wèn)題(答案:s.t 3x1 6x24X1,X20maxw 6y14y22% y25st 3y1 6y23)y1,y2 0minz20x110x215( 162)、用對(duì)偶單純型法解5%6(答案:st2x12x?8xxmax z45; %1嚴(yán)10X2、5x. x? 6詳解：轉(zhuǎn)化為5%s.t 2x1 2

28、x28s.t2x1N ,x20為必max(z)20x110x2得到標(biāo)準(zhǔn)化模型為5x1XX36st2x12x2 X48min z 20x1max( z)X1,)<2,X3,X40020x110x2x26、，引入松弛變量X3M4 ,2x2800 x30 x4建立初始對(duì)偶單純形表并作基的變換如下,XX1X2X3：X4bc-20-100X30-5-110-6先取負(fù)的最大的 b值所在，確定 換出X40-2-201-8精品資料zj0ro0ro0Zj-cj201000thita|20/-2|10/-2| I再找比值的絕對(duì)值最小的定入X30-401r-1/2-2先取負(fù)的最大的 b值所在，確定 換出X2-

29、10110-1/24zj-101-1001 5下行加cjZj-cj10005-40thita|-10/4|I-5/0.5|再找比值的絕對(duì)值最小的定入X1-2010-1/4r 1/81/2已經(jīng)全為正了， 說(shuō)明基解已可行X2-10011/4-5/83.5zj-20-105/2；3.75下行加cjZj-cj005/23.75-45依判據(jù)，得最優(yōu)解11從表中看出 max z45; x1, x2 3 , minz 4522max z 2% x2 x33x1 2x2 2x31516 (163)、現(xiàn)有線性規(guī)劃問(wèn)題： X2 X33，用單純形法求最優(yōu)s.tx1 x2 x34石，必 0解和資源1、資源2、資源3的

30、影子價(jià)格。(答案：最優(yōu)解x 21,24,0,0,7 T資源1、資源2、資源3的影子價(jià)格1,1,0)maxz2為 x2x3max z 2x1X2X33x12x2 2x3 153為 2x22x315詳解：x2 x33轉(zhuǎn)化為X1X2X3 3，引入松弛變量s.ts.tX2X34x1x2X34加2必0X1,X2,X30maxz2x1 x2 x332x2 2x3x415x4 , x5, x6 ，得到標(biāo)準(zhǔn)化模型為%X2X3X53。s.tJ JX2X3x4X1,X2,X3,X4,xs,x60建立初始單純形表并作基的變換如下,XX1X2X3X4X5 X6bthitac2-11000X403-221001515/

31、3=5X50-1110103X601-1100144/仁4最??！定出基變量zj000000Zj-cj21-1000先找負(fù)的絕對(duì)值最大的定入基變量X4001-110-333/仁3最?。《ǔ龌兞縓5000201 117X121-110014zj2-22002下行加cj定入基變量Zj-cj0-1100 128先找負(fù)的絕對(duì)值最大X2-101-110-33X5000201177/仁7最??！定出基變 量X1210010-27zj2-1110-1下行加cj定入基變量Zj-cj00010-111先找負(fù)的絕對(duì)值最大X2-101513024X600020117X1210412021zj2-13110下行加cjZ

32、j-cj00211018判定最優(yōu)解從表中看出x21,24,0,0,7 T,maxz 18，由表的最后一行，可得資源1、資源2、資源3的影子價(jià)格分別為1,1,017（ 1.6.4）、現(xiàn)有線性規(guī)劃問(wèn)題:min z2x14x26x32x1x2%102x22x312，（ 1）用單純形法求s.t2x2X340僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝31解該問(wèn)題;（2）用對(duì)偶單純形法求解該問(wèn)題（答案：x 6,2,0 T,z 20min( z)2x14X26x3 MX52xjx2x3X5X410（1）花2x22X3X612st2x2X3xX74X1, x2,X3,Xs,X8, X4,Xs,X70Mx8 0

33、 X4 x6 x7用單純性法迭代;18( 1.6.5)、求解線性規(guī)劃丄3x2X23(答案：s.tX1X23X1,X20Tx 2,1,7,0,0 ,z 55)minz 20x1 15x2max(z)20x1 15x22x1 x252x1X25詳解：3X1 2x2 3轉(zhuǎn)化為3x12x23，s.ts.tx1 x2 3X1X23x1 ,x20X1,X20max( z)2015x2 0x32x1X2X35X3,X4, X5，得到標(biāo)準(zhǔn)化模型為3ct2x2 x43Ol LX2X530Xi，X2，X3，X4，X引入松弛變量0x4 0x5min( z)2x-| 4x26X30 X4X5x2x1 x2(2)X1

34、2x2st2x2 X3X32x3X410X6X5412用對(duì)偶單純性法迭代)Xi, X2,X3, X4,X5, X6min z 20x12x1 x215x25建立初始對(duì)偶單純形表并作基的變換如下,XX1X2X3X4X5bc-20-15000X30-2-1100-5先取負(fù)的最大的 b值所在，確定 換出X40-320103X50-1-1001-3zj°0000下行加cjZi-ci20150000thita再找比值的絕對(duì)值|20/ (-2) |=10，|15/ (-1)|=15最小的定入X：X1X2X3X4X5bc-20-15000X1011/2-1/2005/2先取負(fù)的最 大的b值所 在，

35、確定換 出X4097/2-3/2h021/2X500-1/2-1/201-1/2zj-20-1010：00下行加cjzj-ci0510：00-50thita再找比值的絕對(duì)值|5/（-1/2）|=10，|10/（-1）1=20最小的定入XX1X2X3X4X5bc-20-15000X1010-1o12全正，基解X400o-5177可行X200110-21zj-20-155010下行加cjZj-cj：o05o10-55 1判定最優(yōu)從表中看出最優(yōu)解為 x 2,1,7,0,0T,z 55mi nz 10捲 8x2 7x319（ 1.6.6）、用對(duì)偶單純型法解2為x24（答案：Stx1x2X33X1,X2

36、,X30x 1,2,0 T ,z 26)min z 10為 8x27X3maxz10x1 8x27X3，“2x1 x? 42為x24詳解：12轉(zhuǎn)化為，引入松弛變量s.t % x2 x33s.tX-!X2X33為冬必 0N，X2，X30max( z)10為8x27x30x4 OX5滄,X5，得到標(biāo)準(zhǔn)化模型為2x1X2X44。s.t為X2X3X53X1,X2，X3,X4，X50建立初始對(duì)偶單純形表并作基的變換如下,XX1X2X3X4X5bc-1O-8-7OOX3O-2-1O1O-4先取負(fù)的最大的X4O-1-1-1O1-3b值所在，確定 換出cj -ZjP-1O-8-7OOOthita再找比值的-1

37、0/( -2)=5，-8/（-1）=8最小的定入X1-1Op1/2O-1/2O2先取負(fù)的最大的X4OO-1/2-1-1/21-1b值所在，確定 換出cj -ZjO-3-75O20thita再找比值的-3/(-1/2)=6，-7/(-1)=7,-5/（ -1/2）=1O最小的定入X1-1Op1/2O-1/2O2全正，基解可行X2-8Lo12h-22cj -ZjOO-1-2-626判別數(shù)非正，確認(rèn)最 優(yōu)從而得最優(yōu)解x 1,2,0 丁，z 26min w 3 3x22x 3x21820 (167)用對(duì)偶單純型法解 X2 2(答案:st捲 3x210x20x 4,2,4 T , w 16)min w3

38、x1 3x2max( w)3x1 3x22x13x2 182x13x218詳解：X1X22 轉(zhuǎn)化為X1X22，引入松弛變量X3,X4,X5，s.ts.tX13x210X13x210X1,X20X1,X20max( z)3x13x20X30x4 0x52為3x2 x318得到標(biāo)準(zhǔn)化模型為X1X2X42。stX13x2 X510X1，X2,X3，X4,X50建立初始對(duì)偶單純形表并作基的變換如下,XX1X2X3X4X5bc1-3-301 00X302310018先取負(fù)的最大的 b值所在，確定 換出X40I1010 J-2X50-1-3001-10cj -Zj-3-30000thita再找比值的-3/

39、（-1）=3，-3/（ -3）=1最小的定入X30101018先取負(fù)的最大的 b值所在，確定 換出X40-4/30011/3-16/3X2-31/3100-1/310/3ci -Zj2000：-110thita再找比值的-2/（ -4/3）=3/2最小的定入X300013/45/44全正，基解可行X1-3100-3/4-1/44X2-30101/4-1/42cj -Zj-2000-110判別數(shù)非正，確認(rèn)最 優(yōu)thita再找比值的-2/（ -4/3）=3/2最小的定入從表中看出，最優(yōu)解為X 4,2,4 t,w 161 （4.2.1）、某市舉行1990年世界杯6強(qiáng)（A、B、C、D、E、F）聯(lián)賽。競(jìng)

40、賽采取循環(huán)制，每天安排三場(chǎng)比賽。同一個(gè)隊(duì)一天之內(nèi)只安排一場(chǎng)，要求競(jìng)賽在5天之內(nèi)賽完，請(qǐng)用圖的方法表示 6個(gè)隊(duì)之間的聯(lián)賽，和競(jìng)賽日程安排，并指 出每個(gè)圖是什么類型的圖，各日程安排圖與聯(lián)賽圖是什么關(guān)系。（答案：GA：FG2G3FCA.«BG4FACEG5，G是完全圖，GgGGG為非連通圖，且都是G的子圖）精品資料V101011V2101012 (4.2.2)、寫(xiě) V301011出右圖的關(guān)聯(lián)矩陣和相關(guān)矩陣V410100V4e3V3V5 11100（答案：列都對(duì)應(yīng)頂點(diǎn),0 110 0 0e5 0 10 0 1e6 0 0 1 0 1V410100v511100100V101011110V21

41、0101010，相關(guān)矩陣為v301011 )e2 01e3 0 0關(guān)聯(lián)矩陣為e4 10僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝27e7 1 0 0 0 13 （423）、有甲乙丙丁戊己6名運(yùn)動(dòng)員報(bào)名參加ABCDEF6個(gè)項(xiàng)目的比賽。下表中打“V”的是各運(yùn)動(dòng)員報(bào)名參加的比賽項(xiàng)目（表4-1）。問(wèn)：6個(gè)項(xiàng)目比賽順序如何安排，做到每名運(yùn)動(dòng)員不連續(xù)參加兩項(xiàng)比賽?ABCDEF甲VV乙VVV丙VV丁VV戊VV己VV（答案:有人同時(shí)參加則連線，方案一 ACBFED，方案二AFBCDE，條任意兩點(diǎn)不相關(guān)序列）4（ 424）、出席某處國(guó)際學(xué)術(shù)報(bào)告會(huì)的 6個(gè)成員ABCDEF被分在一組。他們 的情況是：A會(huì)講漢語(yǔ)、

42、法語(yǔ)和日語(yǔ)；B會(huì)講德語(yǔ)、俄語(yǔ)和日語(yǔ)；C會(huì)講英 語(yǔ)、法語(yǔ)；D會(huì)講漢語(yǔ)和西班牙語(yǔ)；E會(huì)講英語(yǔ)和德語(yǔ)；F會(huì)講俄語(yǔ)和西班牙 語(yǔ)。怎么把他們安排在一張圓桌旁坐下，使得每個(gè)人能和他兩旁的人交談？（答案:F俄漢德 西A日 cB找一條漢密頓回路ACEBFDA）5（4.2.5）、圖 G=（V，E）是連通圖，且e E。證明：e屬于每一棵生成樹(shù)的充要條件是e為G的割集。（答案：都用反證法。充分性： e屬于每一棵生成樹(shù)，若e不為G的割集（反設(shè)）。則G-e必連通，則G-e中必存在生成樹(shù)T， 因?yàn)門也是G的生成樹(shù)，但T不包含e,導(dǎo)致矛盾。必要性：設(shè)e不為G的割 集(反設(shè))。若G有生成樹(shù)T,則T+e包含回路。刪去e后連通，即與e屬于 每棵生成樹(shù)矛盾，反設(shè)不成立。)6(426)、已知圖得結(jié)點(diǎn)集V=a,b,c,d，以及圖G和圖D的邊集合分別為E(G)=(a,a),(a,b),(b,c),(a,c); E(D)= <a,b>,<a,c>,<c,d>,<c,a>,<c,b>。試作圖 G 和圖D，寫(xiě)出個(gè)結(jié)點(diǎn)的度數(shù)，回答圖G、圖D是簡(jiǎn)單圖還