運(yùn)籌學(xué)判斷題

判斷題VVXX一、線(xiàn)性規(guī)劃TOC\o"1-5"\h\z假設(shè)線(xiàn)性規(guī)劃存在最優(yōu)解則一定存在基本最優(yōu)解V（假設(shè)存在唯一最優(yōu)解，則最優(yōu)解為最優(yōu)基本可行解〔一個(gè)角頂〕，假設(shè)存在多重最優(yōu)解〔由多個(gè)角頂?shù)耐菇M合來(lái)表示）假設(shè)線(xiàn)性規(guī)劃為無(wú)界解則其可行域無(wú)界V〔可行域封閉有界則必然存在最優(yōu)解〕可行解一定是基本解X〔基本概念〕基本解可能是可行解V〔基本概念〕線(xiàn)性規(guī)劃的可行域無(wú)界則具有無(wú)界解X〔有可能最優(yōu)解，假設(shè)函數(shù)的梯度方向朝向封閉的方向，則有最優(yōu)解〕最優(yōu)解不一定是基本最優(yōu)解V〔在多重最優(yōu)解里，最優(yōu)解也可以是基本最優(yōu)解的凸組合〕x.的檢驗(yàn)數(shù)表示變量Xj增加一個(gè)單位時(shí)目標(biāo)函數(shù)值的改變量V〔檢驗(yàn)數(shù)的含義，檢驗(yàn)函數(shù)的變化率〕可行解集有界非空時(shí),則在極點(diǎn)上至少有一點(diǎn)到達(dá)最優(yōu)值V〔可行解集有界非空時(shí)，有可行解，有最優(yōu)解，則至少有一個(gè)基本最優(yōu)解〕假設(shè)線(xiàn)性規(guī)劃有三個(gè)基本最優(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任何線(xiàn)性規(guī)劃總可用大M單純形法求解V〔人工變量作用就是一個(gè)中介作業(yè)，通過(guò)它來(lái)找到初始基本可行解〕凡能用大M法求解也一定可用兩階段法求解V〔大M法和兩階段法沒(méi)有本質(zhì)區(qū)別〕兩階段法中第一階段問(wèn)題必有最優(yōu)解V〔第一階段中，線(xiàn)性規(guī)劃的可行域是封閉有界的，必然有最優(yōu)解〕兩階段法中第一階段問(wèn)題最優(yōu)解中基變量全部非人工變量則原問(wèn)題有最優(yōu)解X〔只能說(shuō)有可行解，也有可能是無(wú)界解〕任何變量一旦出基就不會(huì)再進(jìn)基X人工變量一旦出基就不會(huì)再進(jìn)基V〔這個(gè)是算法的一個(gè)思想，目標(biāo)函數(shù)已經(jīng)決定了〕普通單純形法比值規(guī)則失效說(shuō)明問(wèn)題無(wú)界V將檢驗(yàn)數(shù)表示為X=C仍-1A—C的形式，則求極大值問(wèn)題時(shí)基可行解是最優(yōu)解的充要條件是X>0V〔各種情況下最優(yōu)性判斷條件〕當(dāng)最優(yōu)解中存在為零的基變量時(shí)，則線(xiàn)性規(guī)劃具有多重最優(yōu)解X〔退化解的概念，多重最優(yōu)解和非基變量的檢驗(yàn)數(shù)有關(guān)〕當(dāng)最優(yōu)解中存在為零的非基變量時(shí)，則線(xiàn)性規(guī)劃具唯一最優(yōu)解X可行解集不一定是凸集X將檢驗(yàn)數(shù)表示為的形式，則求極小值問(wèn)題時(shí)，基可行解為最優(yōu)解當(dāng)TOC\o"1-5"\h\z且僅當(dāng)入盧0,j=1,2,...,nV假設(shè)線(xiàn)性規(guī)劃存在基本解則也一定存在基本解可行解X線(xiàn)性規(guī)劃的基本可行解只有有限多個(gè)V在基本可行解中基變量一定不為零XmaxZ=3x+x—4x12x+5x+xl<50<x—x+10x>10cx>0,x>0,x>0TOC\o"1-5"\h\zI123是一個(gè)線(xiàn)性規(guī)劃數(shù)學(xué)模型X二對(duì)偶規(guī)劃任何線(xiàn)性規(guī)劃都存在一個(gè)對(duì)應(yīng)的對(duì)偶線(xiàn)性規(guī)劃V原問(wèn)題（極大值）第i個(gè)約束是“N”約束，則對(duì)偶變量“N0X互為對(duì)偶問(wèn)題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無(wú)最優(yōu)解V對(duì)偶問(wèn)題有可行解，則原問(wèn)題也有可行解X原問(wèn)題有多重解，對(duì)偶問(wèn)題也有多重解X在以下6?10中，設(shè)X*、Y*分別(mmz=w=|K4<CJ>0)的可行解則有CX*WY*bXCX*是W的下界X當(dāng)X*、Y*為最優(yōu)解時(shí)，CX*=Y*b；V當(dāng)CX*=Y*b時(shí)，有Y*Xs+YsX*=0成立VX*為最優(yōu)解且B是最優(yōu)基時(shí)，則Y*=CbB-1是最優(yōu)解V對(duì)偶問(wèn)題有可行解，原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題具有無(wú)界解V原問(wèn)題無(wú)最優(yōu)解，則對(duì)偶問(wèn)題無(wú)可行解X對(duì)偶問(wèn)題不可行，原問(wèn)題無(wú)界解X原問(wèn)題與對(duì)偶問(wèn)題都可行，則都有最優(yōu)解V原問(wèn)題具有無(wú)界解，則對(duì)偶問(wèn)題不可行V假設(shè)某種資源影子價(jià)格為零，則該資源一定有剩余X原問(wèn)題可行對(duì)偶問(wèn)題不可行時(shí)，可用對(duì)偶單純形法計(jì)算X對(duì)偶單純法換基時(shí)是先確定出基變量，再確定進(jìn)基變量V對(duì)偶單純法是直接解對(duì)偶問(wèn)題的一種方法X對(duì)偶單純形法比值失效說(shuō)明原問(wèn)題具有無(wú)界解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)值不會(huì)比原來(lái)變差增加一個(gè)變量，目標(biāo)值不會(huì)比原來(lái)變好當(dāng)b.在允許的最大范圍內(nèi)變化時(shí)，最優(yōu)解不變?nèi)?、整?shù)規(guī)劃整數(shù)規(guī)劃的最優(yōu)解是先求相應(yīng)的線(xiàn)性規(guī)劃的最優(yōu)解然后取整得到X部分變量要求是整數(shù)的規(guī)劃問(wèn)題稱(chēng)為純整數(shù)規(guī)劃求最大值問(wèn)題的目標(biāo)函數(shù)值是各分枝函數(shù)值的上界求最小值問(wèn)題的目標(biāo)函數(shù)值是各分枝函數(shù)值的下界變量取0或1的規(guī)劃是整數(shù)規(guī)劃d整數(shù)規(guī)劃的可行解集合是離散型集合0—1規(guī)劃的變量有n個(gè)，則有2n個(gè)可行解6x1+5x2>10>15或20中的一個(gè)值，表達(dá)為一般線(xiàn)性約束條件是6x1+5x2>10j1+15j2+20j3,y1+y2+y3=1,y1>y2、y3=0或正偏差變量大于等于零，負(fù)偏差變量小于等于零系統(tǒng)約束中沒(méi)有正負(fù)偏差變量目標(biāo)約束含有正負(fù)偏差變量一對(duì)正負(fù)偏差變量至少一個(gè)大于零一對(duì)正負(fù)偏差變量至少一個(gè)等于零要求至少到達(dá)目標(biāo)值的目標(biāo)函數(shù)是要求不超過(guò)目標(biāo)值的目標(biāo)函數(shù)是minZ=d-目標(biāo)規(guī)劃沒(méi)有系統(tǒng)約束時(shí)，不一定存在滿(mǎn)意解超出目標(biāo)值的差值稱(chēng)為正偏差d未到達(dá)目標(biāo)的差值稱(chēng)為負(fù)偏差d五、運(yùn)輸與指派問(wèn)題運(yùn)輸問(wèn)題中用位勢(shì)法求得的檢驗(yàn)數(shù)不唯一平衡運(yùn)輸問(wèn)題一定有最優(yōu)解不平衡運(yùn)輸問(wèn)題不一定有最優(yōu)解產(chǎn)地?cái)?shù)為3,銷(xiāo)地?cái)?shù)為4的平衡運(yùn)輸問(wèn)題有7個(gè)基變量Xm+n—1個(gè)變量組構(gòu)成一組基變量的充要條件是它們不包含閉回路dd高莫雷〔R.E.Gomory〕約束是將可行域中一部分非整數(shù)解切割掉d隱枚舉法是將所有變量取0、1的組合逐個(gè)代入約束條件試算的方法尋找可行解XmaxZ=d+四、目標(biāo)規(guī)劃TOC\o"1-5"\h\z運(yùn)輸問(wèn)題的檢驗(yàn)數(shù)就是其對(duì)偶變量X運(yùn)輸問(wèn)題的檢驗(yàn)數(shù)就是對(duì)偶問(wèn)題的松馳變量運(yùn)輸問(wèn)題的位勢(shì)就是其對(duì)偶變量d不包含任何閉回路的變量組必有孤立點(diǎn)d含有孤立點(diǎn)的變量組一定不含閉回路X用一個(gè)常數(shù)k加到運(yùn)價(jià)矩陣C的某列的所有元素上，則最優(yōu)解不變d令虛設(shè)的產(chǎn)地或銷(xiāo)地對(duì)應(yīng)的運(yùn)價(jià)為一任意大于零的常數(shù)c(c>0),則最優(yōu)解不變d假設(shè)運(yùn)輸問(wèn)題的供應(yīng)量與需求量為整數(shù)，則一定可以得到整數(shù)最優(yōu)解d按最小元素法求得運(yùn)輸問(wèn)題的初始方案，從任一非基格出發(fā)都存在唯一一個(gè)閉回路d運(yùn)輸問(wèn)題中運(yùn)價(jià)表的每一個(gè)元素都分別乘于一個(gè)常數(shù)則最優(yōu)解不變d運(yùn)輸問(wèn)題中運(yùn)價(jià)表的每一個(gè)元素都分別加上一個(gè)常數(shù)則最優(yōu)解不變d17.5個(gè)產(chǎn)地6個(gè)銷(xiāo)地的平衡運(yùn)輸問(wèn)題有11個(gè)變量X18.5個(gè)產(chǎn)地6個(gè)銷(xiāo)地的平衡運(yùn)輸問(wèn)題有30個(gè)變量d5個(gè)產(chǎn)地6個(gè)銷(xiāo)地的銷(xiāo)大于產(chǎn)的運(yùn)輸問(wèn)題有11個(gè)基變量d產(chǎn)地?cái)?shù)為3銷(xiāo)地?cái)?shù)為4的平衡運(yùn)輸中，變量組｛x11,x13,x22,x33,x34｝可作為一組基變量X六、網(wǎng)絡(luò)模型容量不超過(guò)流量X最大流問(wèn)題是找一條從起點(diǎn)到終點(diǎn)的路，使得通過(guò)這條路的流量最大X容量C..是弧〔i，j〕的最大通過(guò)能力d流量匕；是弧〔.，.〕的實(shí)際通過(guò)量d可行流是最大流的充要條件是不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈d截量等于截集中弧的流量之和X任意可行流量不超過(guò)任意截量d任意可行流量不小于任意截量XTOC\o"1-5"\h\z存在增廣鏈說(shuō)明還沒(méi)有得到最大流量d存在增廣鏈說(shuō)明已得到最大流X找增廣鏈的目的是：是否存在一條從發(fā)點(diǎn)到收點(diǎn)的路，使得可以增加這條路的流量d狄克斯屈拉算法是求最大流的一種標(biāo)號(hào)算法X破圈法是：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈d避圈法〔加邊法〕是：去掉圖中所有邊，從最短邊開(kāi)始添加，加邊的過(guò)程中不能形成圈，直到連通〔n—1條邊〕d連通圖一定有支撐樹(shù)dP是一條增廣鏈，則后向弧上滿(mǎn)足流量fN0XP是一條增廣鏈，則前向弧上滿(mǎn)足流量f..WC.X可行流的流量等于每條弧上的流量之和X最大流量等于最大流X最小截集等于最大流量X七、網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃中的總工期是網(wǎng)絡(luò)圖中的最短路的長(zhǎng)度X緊前工序是前道工序d后續(xù)工序是緊后工序X虛工序不需要資源，是用來(lái)表達(dá)工序之間的銜接關(guān)系的虛設(shè)活動(dòng)d正偏差變量大于等于零，負(fù)偏差變量小于等于零系統(tǒng)約束中沒(méi)有正負(fù)偏差變量目標(biāo)約束含有正負(fù)偏差變量一對(duì)正負(fù)偏差變量至少一個(gè)大于零一對(duì)正負(fù)偏差變量至少一個(gè)等于零要求至少到達(dá)目標(biāo)值的目標(biāo)函數(shù)是要求不超過(guò)目標(biāo)值的目標(biāo)函數(shù)是minZ=d-目標(biāo)規(guī)劃沒(méi)有系統(tǒng)約束時(shí)，不一定存在滿(mǎn)意解超出目標(biāo)值的差值稱(chēng)為正偏差d未到達(dá)目標(biāo)的差值稱(chēng)為負(fù)偏差d五、運(yùn)輸與指派問(wèn)題運(yùn)輸問(wèn)題中用位勢(shì)法求得的檢驗(yàn)數(shù)不唯一平衡運(yùn)輸問(wèn)題一定有最優(yōu)解不平衡運(yùn)輸問(wèn)題不一定有最優(yōu)解產(chǎn)地?cái)?shù)為3,銷(xiāo)地?cái)?shù)為4的平衡運(yùn)輸問(wèn)題有7個(gè)基變量Xm+n—1個(gè)變量組構(gòu)成一組基變量的充要條件是它們不包含閉回路dmaxZ=d+TOC\o"1-5"\h\zA完工后B才能開(kāi)始，稱(chēng)A是B的緊后工序X單時(shí)差為零的工序稱(chēng)為關(guān)鍵工序X關(guān)鍵路線(xiàn)是由關(guān)鍵工序組成的一條從網(wǎng)絡(luò)圖的起點(diǎn)到終點(diǎn)的有向路V關(guān)鍵路線(xiàn)一定存在V關(guān)鍵路線(xiàn)存在且唯一X計(jì)劃網(wǎng)絡(luò)圖允許有多個(gè)始點(diǎn)和終點(diǎn)X事件z?的最遲時(shí)間Tl〔i〕是指以事件i為完工事件的工序最早可能結(jié)束時(shí)間X事件i的最早時(shí)間Te〔i〕是以事件i為開(kāi)工事件的工序最早可能開(kāi)工時(shí)間V工序〔i,j〕的事件i與j的大小關(guān)系是i<jV間接成本與工程的完工期成正比V直接成本與工程的完工期成正比X上（7）二七（i）XnLsR0/）一上v18.孩V19頊（很）=心。頂—&（ij）X20.R??j)=&F&j)-弓(』)fV1線(xiàn)性規(guī)劃2對(duì)偶問(wèn)題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ì)”17=”錯(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)輸問(wèn)題=”錯(cuò)”=”對(duì)”=”錯(cuò)”=”錯(cuò)”5=”對(duì)”=”錯(cuò)”=”對(duì)”=”對(duì)”9=”