運籌學判斷題word文檔良心出品

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

2、點達到最優(yōu)值（可行解集有界非空時，有可行解，有最優(yōu)解，則至少有一個基本最優(yōu)解）若線性規(guī)劃有三個基本最優(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（人工變量作用就是一個中介作業(yè)，通過它來找到初始基本可行 解）凡能用大M法求解也一定可用兩階段法求解V（大M法和兩階段法沒有本質(zhì)區(qū)別）兩階段法中第一階段問題必有最優(yōu)解V（第一階段中，線性規(guī)劃的可行域是封閉有界的，必然有最優(yōu)解）兩階

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

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

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

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

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

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

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

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