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

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

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

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

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

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

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