運(yùn)籌學(xué)期末復(fù)習(xí)題及答案

1、19、簡(jiǎn)述線(xiàn)性規(guī)劃模型主要參數(shù)（p11）（1）、價(jià)值系數(shù)：目標(biāo)函數(shù)中決策變量前的系數(shù)為價(jià)值系數(shù)（2）、技術(shù)系數(shù)：約束條件中決策變量前的系數(shù)（3）、約束條件右邊常數(shù)項(xiàng)15、簡(jiǎn)述線(xiàn)性規(guī)劃解幾種可能的結(jié)果（情形）（ppt第二章39或89頁(yè)）（1）.有唯一最優(yōu)解(單純形法中在求最大目標(biāo)函數(shù)的問(wèn)題時(shí)，對(duì)于某個(gè)基本可行解，所有δj≤0)（2）.無(wú)可行解，即可行域?yàn)榭沼?，不存在滿(mǎn)足約束條件的解，也就不存在最優(yōu)解了。（3）.無(wú)界解，即可行域的范圍延伸到

2、無(wú)窮遠(yuǎn)，目標(biāo)函數(shù)值可以無(wú)窮大或無(wú)窮小，一般來(lái)說(shuō)，這說(shuō)明模型有錯(cuò)，忽略了一些必要的約束條件（4）.無(wú)窮多個(gè)最優(yōu)解，則線(xiàn)段上的所有點(diǎn)都代表了最優(yōu)解（5）退化問(wèn)題，基變量有時(shí)存在兩個(gè)以上相同的最小比值，這樣在下一次迭代中就有一個(gè)或幾個(gè)基變量等于零，用圖解法無(wú)退化解1、簡(jiǎn)述單純形法的基本思路（p70）從可行域中某一個(gè)頂點(diǎn)開(kāi)始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是則再找另一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱(chēng)之為迭代，再判斷此點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂

3、點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線(xiàn)性規(guī)劃問(wèn)題無(wú)最優(yōu)解為止。17、簡(jiǎn)述線(xiàn)性規(guī)劃中添加人工變量的前提（p85）在系數(shù)矩陣中直接找不到初始可行解，進(jìn)而通過(guò)添加人工變量的方法來(lái)構(gòu)造初始可行基，得出初始基本可行解10、簡(jiǎn)述線(xiàn)性規(guī)劃對(duì)偶問(wèn)題的基本性質(zhì)（p122）（1）對(duì)稱(chēng)性（2）弱對(duì)偶性（3）強(qiáng)對(duì)偶性（4）最優(yōu)性（5）互補(bǔ)松弛型原函數(shù)與對(duì)偶問(wèn)題的關(guān)系1）求目標(biāo)函數(shù)最大值的線(xiàn)性規(guī)劃問(wèn)題中有n個(gè)變量m個(gè)約束條件，它的約束條件都是

4、小于等于不等式。而其對(duì)偶則是求目標(biāo)函數(shù)為最小值的線(xiàn)性規(guī)劃問(wèn)題，有m個(gè)變量n個(gè)約束條件，其約束條件都為大于等于不等式?！?。問(wèn)應(yīng)如何分配才能使總效率（時(shí)間或費(fèi)用）最高？12、簡(jiǎn)述分枝定界法的基本步驟分枝定界法是先求解整數(shù)規(guī)劃的線(xiàn)性規(guī)劃問(wèn)題。如果其最優(yōu)解不符合整數(shù)條件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應(yīng)的線(xiàn)性規(guī)劃的可行域分成子區(qū)域（稱(chēng)為分枝），再求解這些子區(qū)域上的線(xiàn)性規(guī)劃問(wèn)題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃

5、的最優(yōu)解?；舅悸罚?、先求出線(xiàn)性規(guī)劃的解2、確定整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z(mì)初始上界和下界z3、將一個(gè)線(xiàn)性規(guī)劃問(wèn)題分為兩枝，并求解4、修改最優(yōu)目標(biāo)函數(shù)上、下界5、比較與剪枝：各分枝的目標(biāo)函數(shù)值中，若有小于Z者，則剪掉此枝，表明此子問(wèn)題已經(jīng)探清，不必再分枝了否則繼續(xù)分枝。6、如此反復(fù)進(jìn)行，直到得到Z＝Z為止，即得最優(yōu)解X。6、簡(jiǎn)述目標(biāo)規(guī)劃的目標(biāo)函數(shù)主要類(lèi)型及其數(shù)學(xué)表達(dá)式。目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能取極小形式，即minz=f(dd)，共有如下三

6、種形式：（1）要求恰好等于目標(biāo)值，即希望決策值超過(guò)和不足目標(biāo)值的部分都盡可能小，因此由函數(shù)minz=f(dd)；（2），要求不超過(guò)目標(biāo)值，允許達(dá)不到目標(biāo)值，即希望決策值不超過(guò)目標(biāo)值，也希望d越小越好，因此有minz=f（d）(3)要求不低于目標(biāo)值，允許超過(guò)目標(biāo)值，即希望決策值不低于目標(biāo)值，也希望d越小越好，因此有minz=f(d).2、簡(jiǎn)述運(yùn)籌學(xué)中背包問(wèn)題的一般提法（p225）對(duì)于N種具有不同重量和不同價(jià)值的物品，在攜帶物品總重量限制的