運(yùn)籌學(xué)判斷題word文檔良心出品

1、判斷題VVxx一、線性規(guī)劃若線性規(guī)劃存在最優(yōu)解則一定存在基本最優(yōu)解V（若存在唯一最優(yōu)解，則最優(yōu)解為最優(yōu)基本可行解（一個(gè)角頂）角，若存在多重最優(yōu)解（由多個(gè) 頂?shù)耐菇M合來(lái)表示）若線性規(guī)劃為無(wú)界解則其可行域無(wú)界（可行域封閉有界則必然存在最優(yōu)解）可行解一定是基本解 X（基本概念）基本解可能是可行解（基本概念）線性規(guī)劃的可行域無(wú)界則具有無(wú)界解（有可能最優(yōu)解，若函數(shù)的梯度方向朝向封閉的方向，則有最優(yōu)解）最優(yōu)解不一定是基本最優(yōu)解V（在多重最優(yōu)解里，最優(yōu)解也可以是基本最優(yōu)解的凸組合）X.的檢驗(yàn)數(shù)表示變量Xj增加一個(gè)單位時(shí)目標(biāo)函數(shù)值的改變量（檢驗(yàn)數(shù)的含義，檢驗(yàn)函數(shù)的變化率）可行解集有界非空時(shí)，則在極點(diǎn)上至少有一

2、點(diǎn)達(dá)到最優(yōu)值（可行解集有界非空時(shí)，有可行解，有最優(yōu)解，則至少有一個(gè)基本最優(yōu)解）若線性規(guī)劃有三個(gè)基本最優(yōu)解x”）、X、X，則x=ax （1-a X、及乂二水+ aX+ a3X（3）均為最優(yōu)解，其中0禺、兩0并且另 =1 V（一般凸組合 X=a.X+aX+aX，若a3=0，則有X=0 （+ TOC o 1-5 h z （1-a X）1 任何線性規(guī)劃總可用大M單純形法求解V（人工變量作用就是一個(gè)中介作業(yè)，通過它來(lái)找到初始基本可行 解）凡能用大M法求解也一定可用兩階段法求解V（大M法和兩階段法沒有本質(zhì)區(qū)別）兩階段法中第一階段問題必有最優(yōu)解V（第一階段中，線性規(guī)劃的可行域是封閉有界的，必然有最優(yōu)解）兩階

3、段法中第一階段問題最優(yōu)解中基變量全部非人工變量，則原問題有最優(yōu)解（只能說(shuō)有可行解，也有可能是無(wú)界解）任何變量一旦出基就不會(huì)再進(jìn)基人工變量一旦出基就不會(huì)再進(jìn)基（這個(gè)是算法的一個(gè)思想，目標(biāo)函數(shù)已經(jīng)決定了）普通單純形法比值規(guī)則失效說(shuō)明問題無(wú)界將檢驗(yàn)數(shù)表示為匚CBB-iA- C的形式，則求極大值問題時(shí)基可行 解是最優(yōu)解的充要條件是入0V（各種情況下最優(yōu)性判斷條件）當(dāng)最優(yōu)解中存在為零的基變量時(shí)，則線性規(guī)劃具有多重最優(yōu)解（退化解的概念，多重最優(yōu)解和非基變量的檢驗(yàn)數(shù)有關(guān)）當(dāng)最優(yōu)解中存在為零的非基變量時(shí)，則線性規(guī)劃具唯一最優(yōu)解可行解集不一定是凸集X21.將檢驗(yàn)數(shù)表示為21.將檢驗(yàn)數(shù)表示為的形式，則求極小值問題

4、時(shí)，基可行解為最優(yōu)解當(dāng)且僅當(dāng) /j。，j = 1,2, , n若線性規(guī)劃存在基本解則也一定存在基本解可行解線性規(guī)劃的基本可行解只有有限多個(gè)在基本可行解中基變量一定不為零maxZ =3 立 + xWx 口32x +5x +x I 蘭 50 +10 x 1023325* 0,X2 0,X3 0是一個(gè)線性規(guī)劃數(shù)學(xué)模型二對(duì)偶規(guī)劃任何線性規(guī)劃都存在一個(gè)對(duì)應(yīng)的對(duì)偶線性規(guī)劃原問題（極大值）第i個(gè)約束是約束，則對(duì)偶變量互為對(duì)偶問題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無(wú)最優(yōu)解問題有可行解，則原問題也有可行解X、原問題有多重解，對(duì)偶問題也有多重解在以下610中的可行解則有 CX* W Y*bCX*是w的下界當(dāng)X*、Y

5、*為最優(yōu)解CX =Y b；時(shí)，當(dāng) CX*=Y*b 時(shí)，有 丫 Xs+YsX =0 成立X為最優(yōu)解且B是最優(yōu)基時(shí)，則丫 =CbB 一1是最優(yōu)解對(duì)偶問題有可行解，原問題無(wú)可行解，則對(duì)偶問題具有無(wú)界解原問題無(wú)最優(yōu)解，則對(duì)偶問題無(wú)可行解對(duì)偶問題不可行，原問題無(wú)界解原問題與對(duì)偶問題都可行，則都有最優(yōu)解原問題具有無(wú)界解，則對(duì)偶問題不可行若某種資源影子價(jià)格為零，則該資源一定有剩余原問題可行對(duì)偶問題不可行時(shí)，可用對(duì)偶單純形法計(jì)算對(duì)偶單純法換基時(shí)是先確定出基變量，再確定進(jìn)基變量對(duì)偶單純法是直接解對(duì)偶問題的一種方法X失效說(shuō)明原問題具有無(wú)界解X、21.在最優(yōu)解不變的前提下，基變量目標(biāo)系數(shù)q的變化范圍可由式I，函.

6、比 10 15或20中的一個(gè)值，表達(dá)為一般線性約束條件是6Xi+5X210i+15y2+2Oy3,yi+y2+y3= 1, y1 y2、y3= 0 或 1 V高莫雷(R.E,Gomory )約束是將可行域中一部分非整數(shù)解切割掉隱枚舉法是將所有變量取0、1的組合逐個(gè)代入約束條件試算的方法尋找可行解四、目標(biāo)規(guī)劃不平衡運(yùn)輸問題不一定有最優(yōu)解八產(chǎn)地?cái)?shù)為3,銷地?cái)?shù)為4的平衡運(yùn)輸問題有7m + n - 1個(gè)變量組構(gòu)成一組基變量的充要條件是它們不包含閉回路運(yùn)輸問題的檢驗(yàn)數(shù)就是其對(duì)偶變量X運(yùn)輸問題的檢驗(yàn)數(shù)就是對(duì)偶問題的松馳變量運(yùn)輸問題的位勢(shì)就是其對(duì)偶變量不包含任何閉回路的變量組必有孤立點(diǎn)含有孤立點(diǎn)的變量組一定

7、不含閉回路用一個(gè)常數(shù)k加到運(yùn)價(jià)矩陣C的某列的所有元素上，則最優(yōu)解不變V令虛設(shè)的產(chǎn)地或銷地對(duì)應(yīng)的運(yùn)價(jià)為一任意大于零的常數(shù)c（c0），則最優(yōu)解不變V若運(yùn)輸問題的供給量與需求量為整數(shù)，則一定可以得到整數(shù)最優(yōu)解V 按最小元素法求得運(yùn)輸問題的初始方案，從任一非基格出發(fā)都存在唯個(gè)閉回路運(yùn)輸問題中運(yùn)價(jià)表的每一個(gè)元素都分別乘于一個(gè)常數(shù)，則最優(yōu)解不變 V運(yùn)輸問題中運(yùn)價(jià)表的每一個(gè)元素都分別加上一個(gè)常數(shù)，則最優(yōu)解不變V17.5個(gè)產(chǎn)地6個(gè)銷地的平衡運(yùn)輸問題有11個(gè)變量18.5個(gè)產(chǎn)地6個(gè)銷地的平衡運(yùn)輸問題有30個(gè)變量5個(gè)產(chǎn)地6個(gè)銷地的銷大于產(chǎn) 的運(yùn)輸問題有11個(gè)基變量V產(chǎn)地?cái)?shù)為3銷地?cái)?shù)為4的平衡運(yùn)輸中，變量組X 11,

8、X13,X22,X33,X34 ）可作為一組基變量X六、網(wǎng)絡(luò)模型容量不超過流量X使得通過這條路的流量最大VV發(fā)點(diǎn)到收點(diǎn)的增廣鏈V使得通過這條路的流量最大VV發(fā)點(diǎn)到收點(diǎn)的增廣鏈V發(fā)點(diǎn)到收點(diǎn)的路，使得可以增加這條路的流量容量qj是?。╥, j）的最大通過能力流量fij是?。╥, j）的實(shí)際通過量可行流是最大流的充要條件是不存在截量等于截集中弧的流量之和任意可行流量不超過任意截量任意可行流量不小于任意截量存在增廣鏈說(shuō)明還沒有得到最大流量 TOC o 1-5 h z 存在增廣鏈說(shuō)明已得到最大流X找增廣鏈的目的是：是否存在一條從V破圈法霓取一籍掉囂長(zhǎng)邊，直到無(wú)/v避圈法（加邊法）是：去掉圖中所有邊，從最

9、短邊開始添加，加邊的過程中不能形成圈， 直到連通（n 1條邊）V連通圖一定有支撐樹VP是一條增廣鏈，則后向弧上滿足流量f 0P是一條增廣鏈，則前向弧上滿足流量fijW Cij可行流的流量等于每條弧上的流量之和X最大流量等于最大流X最小截集等于最大流量七、網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃中的總工期是網(wǎng)絡(luò)圖中的最短路的長(zhǎng)度緊前工序是前道工序V后續(xù)工序是緊后工序X4.虛工序不需要資源，是用來(lái)表達(dá)工序之間的銜接關(guān)系的虛設(shè)活動(dòng)A完工后B才能開始，稱A是B的緊后工序X單時(shí)差為零的工序稱為關(guān)鍵工序X關(guān)鍵路線是由關(guān)鍵工序組成的一條從網(wǎng)絡(luò)圖的起點(diǎn)到終點(diǎn)的有向路關(guān)鍵路線一定存在V關(guān)鍵路線存在且唯一X計(jì)劃網(wǎng)絡(luò)圖允許有多個(gè)始點(diǎn)和終點(diǎn)

10、X事件i的最遲時(shí)間Tl (i)是指以事件i為完工事件的工序最早可能結(jié)束時(shí)間事件i的最早時(shí)間Te (i )是以事件i為開工事件的工序最早可能開工時(shí)間工序(i, j)的事件i與j的大小關(guān)系是間接成本與工程的完工期成正比直接成本與工程的完工期成正比1 曲 J)E0)如 iJAAO)詁RQjrSQJ-nHJ)19.V20.月(i, J) = (i j) - Z (i)1線性規(guī)劃2對(duì)偶問題3整數(shù)規(guī)劃4目標(biāo)規(guī)劃1二對(duì)”1=對(duì)”1= 錯(cuò)”1= 錯(cuò)”2二對(duì)”2=錯(cuò)”2 =錯(cuò)“2 =對(duì)“3 二錯(cuò)3 =對(duì)“3 =對(duì)“3 =對(duì)“4二對(duì)”4=錯(cuò)”4 =對(duì)“4 =錯(cuò)“5二錯(cuò)”5 =錯(cuò)“5 =對(duì)“5=對(duì)”6 二對(duì)“6=錯(cuò)”6=對(duì)”6 =錯(cuò)“7二對(duì)”7 =錯(cuò)“7 =錯(cuò)“7=錯(cuò)”8二對(duì)”8=對(duì)”8=對(duì)”8 =錯(cuò)“9 二對(duì)“9=對(duì)”9 =對(duì)“9 =對(duì)“10=對(duì)”10 =對(duì)“10=錯(cuò)10=對(duì)”11=對(duì)”11 =對(duì)“12 二對(duì)“12=錯(cuò)”13=錯(cuò)”13 =錯(cuò)14=錯(cuò)”14 =對(duì)“15=對(duì)”15 =對(duì)“16=對(duì)”16 =錯(cuò)17=對(duì)”仃二錯(cuò)18 二錯(cuò)“18=對(duì)”19=錯(cuò)”19 =錯(cuò)20 二錯(cuò)“20=錯(cuò)”21=對(duì)”21=對(duì)”22 二錯(cuò)“22 =錯(cuò)23=對(duì)”23=對(duì)”24 =錯(cuò)“24=錯(cuò)”25 =錯(cuò)“25=錯(cuò)”5運(yùn)輸問題二錯(cuò)