運籌學(xué)判斷題

判斷題VVXX一、線性規(guī)劃TOC\o"1-5"\h\z假設(shè)線性規(guī)劃存在最優(yōu)解則一定存在基本最優(yōu)解V（假設(shè)存在唯一最優(yōu)解，則最優(yōu)解為最優(yōu)基本可行解〔一個角頂〕，假設(shè)存在多重最優(yōu)解〔由多個角頂?shù)耐菇M合來表示）假設(shè)線性規(guī)劃為無界解則其可行域無界V〔可行域封閉有界則必然存在最優(yōu)解〕可行解一定是基本解X〔基本概念〕基本解可能是可行解V〔基本概念〕線性規(guī)劃的可行域無界則具有無界解X〔有可能最優(yōu)解，假設(shè)函數(shù)的梯度方向朝向封閉的方向，則有最優(yōu)解〕最優(yōu)解不一定是基本最優(yōu)解V〔在多重最優(yōu)解里，最優(yōu)解也可以是基本最優(yōu)解的凸組合〕x.的檢驗數(shù)表示變量Xj增加一個單位時目標(biāo)函數(shù)值的改變量V〔檢驗數(shù)的含義，檢驗函數(shù)的變化率〕可行解集有界非空時,則在極點上至少有一點到達(dá)最優(yōu)值V〔可行解集有界非空時，有可行解，有最優(yōu)解，則至少有一個基本最優(yōu)解〕假設(shè)線性規(guī)劃有三個基本最優(yōu)解X（i）、X（2）、X（3），則X=aX（i）+（1-a）X（3）及X=%X（i）+a2X（2）+a3X（3）均為最優(yōu)解，其中°^毋WL知吟的乏°并且=1Vi〔一般凸組合為X=a1X（i）+a2X（2）+a3X（3），假設(shè)a3=0，則有X=aX（i）+（1-a）X（3）〕TOC\o"1-5"\h\z任何線性規(guī)劃總可用大M單純形法求解V〔人工變量作用就是一個中介作業(yè)，通過它來找到初始基本可行解〕凡能用大M法求解也一定可用兩階段法求解V〔大M法和兩階段法沒有本質(zhì)區(qū)別〕兩階段法中第一階段問題必有最優(yōu)解V〔第一階段中，線性規(guī)劃的可行域是封閉有界的，必然有最優(yōu)解〕兩階段法中第一階段問題最優(yōu)解中基變量全部非人工變量則原問題有最優(yōu)解X〔只能說有可行解，也有可能是無界解〕任何變量一旦出基就不會再進(jìn)基X人工變量一旦出基就不會再進(jìn)基V〔這個是算法的一個思想，目標(biāo)函數(shù)已經(jīng)決定了〕普通單純形法比值規(guī)則失效說明問題無界V將檢驗數(shù)表示為X=C仍-1A—C的形式，則求極大值問題時基可行解是最優(yōu)解的充要條件是X>0V〔各種情況下最優(yōu)性判斷條件〕當(dāng)最優(yōu)解中存在為零的基變量時，則線性規(guī)劃具有多重最優(yōu)解X〔退化解的概念，多重最優(yōu)解和非基變量的檢驗數(shù)有關(guān)〕當(dāng)最優(yōu)解中存在為零的非基變量時，則線性規(guī)劃具唯一最優(yōu)解X可行解集不一定是凸集X將檢驗數(shù)表示為的形式，則求極小值問題時，基可行解為最優(yōu)解當(dāng)TOC\o"1-5"\h\z且僅當(dāng)入盧0,j=1,2,...,nV假設(shè)線性規(guī)劃存在基本解則也一定存在基本解可行解X線性規(guī)劃的基本可行解只有有限多個V在基本可行解中基變量一定不為零XmaxZ=3x+x—4x12x+5x+xl<50<x—x+10x>10cx>0,x>0,x>0TOC\o"1-5"\h\zI123是一個線性規(guī)劃數(shù)學(xué)模型X二對偶規(guī)劃任何線性規(guī)劃都存在一個對應(yīng)的對偶線性規(guī)劃V原問題（極大值）第i個約束是“N”約束，則對偶變量“N0X互為對偶問題，或者同時都有最優(yōu)解，或者同時都無最優(yōu)解V對偶問題有可行解，則原問題也有可行解X原問題有多重解，對偶問題也有多重解X在以下6?10中，設(shè)X*、Y*分別(mmz=w=|K4<CJ>0)的可行解則有CX*WY*bXCX*是W的下界X當(dāng)X*、Y*為最優(yōu)解時，CX*=Y*b；V當(dāng)CX*=Y*b時，有Y*Xs+YsX*=0成立VX*為最優(yōu)解且B是最優(yōu)基時，則Y*=CbB-1是最優(yōu)解V對偶問題有可行解，原問題無可行解，則對偶問題具有無界解V原問題無最優(yōu)解，則對偶問題無可行解X對偶問題不可行，原問題無界解X原問題與對偶問題都可行，則都有最優(yōu)解V原問題具有無界解，則對偶問題不可行V假設(shè)某種資源影子價格為零，則該資源一定有剩余X原問題可行對偶問題不可行時，可用對偶單純形法計算X對偶單純法換基時是先確定出基變量，再確定進(jìn)基變量V對偶單純法是直接解對偶問題的一種方法X對偶單純形法比值失效說明原問題具有無界解X在最優(yōu)解不變的前提下，基變量目標(biāo)系數(shù)c的變化范圍可由式

max■=—1>0卜<羸己苴mm*—1^<0JRJJ"確定d在最優(yōu)基不變的前提下，常數(shù)br的變化范圍可由式確定，其中"日為最優(yōu)基B的逆矩陣月T第r列減少一約束，目標(biāo)值不會比原來變差增加一個變量，目標(biāo)值不會比原來變好當(dāng)b.在允許的最大范圍內(nèi)變化時，最優(yōu)解不變?nèi)?、整?shù)規(guī)劃整數(shù)規(guī)劃的最優(yōu)解是先求相應(yīng)的線性規(guī)劃的最優(yōu)解然后取整得到X部分變量要求是整數(shù)的規(guī)劃問題稱為純整數(shù)規(guī)劃求最大值問題的目標(biāo)函數(shù)值是各分枝函數(shù)值的上界求最小值問題的目標(biāo)函數(shù)值是各分枝函數(shù)值的下界變量取0或1的規(guī)劃是整數(shù)規(guī)劃d整數(shù)規(guī)劃的可行解集合是離散型集合0—1規(guī)劃的變量有n個，則有2n個可行解6x1+5x2>10>15或20中的一個值，表達(dá)為一般線性約束條件是6x1+5x2>10j1+15j2+20j3,y1+y2+y3=1,y1>y2、y3=0或正偏差變量大于等于零，負(fù)偏差變量小于等于零系統(tǒng)約束中沒有正負(fù)偏差變量目標(biāo)約束含有正負(fù)偏差變量一對正負(fù)偏差變量至少一個大于零一對正負(fù)偏差變量至少一個等于零要求至少到達(dá)目標(biāo)值的目標(biāo)函數(shù)是要求不超過目標(biāo)值的目標(biāo)函數(shù)是minZ=d-目標(biāo)規(guī)劃沒有系統(tǒng)約束時，不一定存在滿意解超出目標(biāo)值的差值稱為正偏差d未到達(dá)目標(biāo)的差值稱為負(fù)偏差d五、運輸與指派問題運輸問題中用位勢法求得的檢驗數(shù)不唯一平衡運輸問題一定有最優(yōu)解不平衡運輸問題不一定有最優(yōu)解產(chǎn)地數(shù)為3,銷地數(shù)為4的平衡運輸問題有7個基變量Xm+n—1個變量組構(gòu)成一組基變量的充要條件是它們不包含閉回路dd高莫雷〔R.E.Gomory〕約束是將可行域中一部分非整數(shù)解切割掉d隱枚舉法是將所有變量取0、1的組合逐個代入約束條件試算的方法尋找可行解XmaxZ=d+四、目標(biāo)規(guī)劃TOC\o"1-5"\h\z運輸問題的檢驗數(shù)就是其對偶變量X運輸問題的檢驗數(shù)就是對偶問題的松馳變量運輸問題的位勢就是其對偶變量d不包含任何閉回路的變量組必有孤立點d含有孤立點的變量組一定不含閉回路X用一個常數(shù)k加到運價矩陣C的某列的所有元素上，則最優(yōu)解不變d令虛設(shè)的產(chǎn)地或銷地對應(yīng)的運價為一任意大于零的常數(shù)c(c>0),則最優(yōu)解不變d假設(shè)運輸問題的供應(yīng)量與需求量為整數(shù)，則一定可以得到整數(shù)最優(yōu)解d按最小元素法求得運輸問題的初始方案，從任一非基格出發(fā)都存在唯一一個閉回路d運輸問題中運價表的每一個元素都分別乘于一個常數(shù)則最優(yōu)解不變d運輸問題中運價表的每一個元素都分別加上一個常數(shù)則最優(yōu)解不變d17.5個產(chǎn)地6個銷地的平衡運輸問題有11個變量X18.5個產(chǎn)地6個銷地的平衡運輸問題有30個變量d5個產(chǎn)地6個銷地的銷大于產(chǎn)的運輸問題有11個基變量d產(chǎn)地數(shù)為3銷地數(shù)為4的平衡運輸中，變量組｛x11,x13,x22,x33,x34｝可作為一組基變量X六、網(wǎng)絡(luò)模型容量不超過流量X最大流問題是找一條從起點到終點的路，使得通過這條路的流量最大X容量C..是弧〔i，j〕的最大通過能力d流量匕；是弧〔.，.〕的實際通過量d可行流是最大流的充要條件是不存在發(fā)點到收點的增廣鏈d截量等于截集中弧的流量之和X任意可行流量不超過任意截量d任意可行流量不小于任意截量XTOC\o"1-5"\h\z存在增廣鏈說明還沒有得到最大流量d存在增廣鏈說明已得到最大流X找增廣鏈的目的是：是否存在一條從發(fā)點到收點的路，使得可以增加這條路的流量d狄克斯屈拉算法是求最大流的一種標(biāo)號算法X破圈法是：任取一圈，去掉圈中最長邊，直到無圈d避圈法〔加邊法〕是：去掉圖中所有邊，從最短邊開始添加，加邊的過程中不能形成圈，直到連通〔n—1條邊〕d連通圖一定有支撐樹dP是一條增廣鏈，則后向弧上滿足流量fN0XP是一條增廣鏈，則前向弧上滿足流量f..WC.X可行流的流量等于每條弧上的流量之和X最大流量等于最大流X最小截集等于最大流量X七、網(wǎng)絡(luò)計劃網(wǎng)絡(luò)計劃中的總工期是網(wǎng)絡(luò)圖中的最短路的長度X緊前工序是前道工序d后續(xù)工序是緊后工序X虛工序不需要資源，是用來表達(dá)工序之間的銜接關(guān)系的虛設(shè)活動d正偏差變量大于等于零，負(fù)偏差變量小于等于零系統(tǒng)約束中沒有正負(fù)偏差變量目標(biāo)約束含有正負(fù)偏差變量一對正負(fù)偏差變量至少一個大于零一對正負(fù)偏差變量至少一個等于零要求至少到達(dá)目標(biāo)值的目標(biāo)函數(shù)是要求不超過目標(biāo)值的目標(biāo)函數(shù)是minZ=d-目標(biāo)規(guī)劃沒有系統(tǒng)約束時，不一定存在滿意解超出目標(biāo)值的差值稱為正偏差d未到達(dá)目標(biāo)的差值稱為負(fù)偏差d五、運輸與指派問題運輸問題中用位勢法求得的檢驗數(shù)不唯一平衡運輸問題一定有最優(yōu)解不平衡運輸問題不一定有最優(yōu)解產(chǎn)地數(shù)為3,銷地數(shù)為4的平衡運輸問題有7個基變量Xm+n—1個變量組構(gòu)成一組基變量的充要條件是它們不包含閉回路dmaxZ=d+TOC\o"1-5"\h\zA完工后B才能開始，稱A是B的緊后工序X單時差為零的工序稱為關(guān)鍵工序X關(guān)鍵路線是由關(guān)鍵工序組成的一條從網(wǎng)絡(luò)圖的起點到終點的有向路V關(guān)鍵路線一定存在V關(guān)鍵路線存在且唯一X計劃網(wǎng)絡(luò)圖允許有多個始點和終點X事件z?的最遲時間Tl〔i〕是指以事件i為完工事件的工序最早可能結(jié)束時間X事件i的最早時間Te〔i〕是以事件i為開工事件的工序最早可能開工時間V工序〔i,j〕的事件i與j的大小關(guān)系是i<jV間接成本與工程的完工期成正比V直接成本與工程的完工期成正比X上（7）二七（i）XnLsR0/）一上v18.孩V19頊（很）=心。頂—&（ij）X20.R??j)=&F&j)-弓(』)fV1線性規(guī)劃2對偶問題3整數(shù)規(guī)劃4目標(biāo)規(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=”對”17=”錯”18=”錯”18=”對”19=”錯”19=”錯”20=”錯”20=”錯”21=”對”21=”對”22=”錯”22=”錯”23=”對”23=”對”24=”錯”24=”錯”25=”錯”25=”錯”

5運輸問題=”錯”=”對”=”錯”=”錯”5=”對”=”錯”=”對”=”對”9=”