【文章內(nèi)容簡介】 1．線性規(guī)劃問題具有對偶性，即對于任何一個求最大值的線性規(guī)劃問題，都有一個求 最小值 /極小值 的線性規(guī)劃問題與之對應(yīng)，反之亦然。 2．在一對對偶問題中，原問題的約束條件的右端常數(shù)是對偶問題的 目標(biāo)函數(shù)系數(shù) 。 3．如果原問題的某個變量無約束，則對偶問題中對應(yīng)的約束條件應(yīng)為 等式 _。 4．對偶 問題的對偶問題是 原問題 _。 5．若原問題可行，但目標(biāo)函數(shù)無界，則對偶問題 不可行 。 6．若某種資源的影子價格等于 k。在其他條件不變的情況下 (假設(shè)原問題的最佳基不變 )，當(dāng)該種資源增加 3 個單位時。 相應(yīng)的目標(biāo)函數(shù)值將增加 3k 。 7．線性規(guī)劃問題的最優(yōu)基為 B，基變量的目標(biāo)系數(shù)為 CB，則其對偶問題的最優(yōu)解 Y﹡ = CBB－ 1。 8．若 X﹡ 和 Y﹡ 分別是線性規(guī)劃的原問題和對偶問題的最優(yōu) 解，則有 CX﹡ = Y﹡ b。 9．若 X、 Y 分別是線性規(guī)劃的原問題和對偶問題的可行解，則 有 CX≤ Yb。 10．若 X﹡ 和 Y﹡ 分別是線性規(guī)劃的原問題 和對偶問題的最優(yōu)解，則有 CX﹡ =Y*b。 11．設(shè)線性規(guī)劃的原問題為 maxZ=CX， Ax≤b ， X≥0 ，則 其對偶問題為 min=Yb YA≥ c Y≥ 0_。 12．影子價格實(shí)際上是與原問題各約束條件相聯(lián)系的 對偶變量 的數(shù)量表現(xiàn)。 13．線性規(guī)劃的原問題的約束條件系數(shù)矩陣為 A，則其對 偶問題的約束條件系數(shù)矩陣為 AT 。 14．在對偶單純形法迭代中，若某 bi0，且所有的 aij≥0( j=1， 2， ? n)，則原問題 _無解 。 二、單選題 1．線性規(guī)劃原問題的目標(biāo)函數(shù)為求極小值型，若其某個 變量小于等于 0，則其 對偶問題約束條件為 A 形式。 A． “≥” B ．“≤” C， “” D． “=” 2．設(shè) X 、 Y 分別是標(biāo)準(zhǔn)形式的原問題與對偶問題的可行 解 ,則 C 。 3．對偶單純形法的迭代是從 _ A_開始的。 A．正則解 B．最優(yōu)解 C．可行解 D．基本解 4．如果 z。是某標(biāo)準(zhǔn)型線性規(guī)劃問題的最優(yōu)目標(biāo)函數(shù)值， 則其對偶問題的最優(yōu)目標(biāo)函數(shù)值 w﹡ A。 A． W﹡ =Z﹡ B． W﹡ ≠Z ﹡ C． W﹡ ≤Z ﹡ D． W﹡ ≥Z ﹡ 5．如果某種資源的影子價格大于其市場價格，則說明 _ B A．該資源過剩 B．該資源稀缺 C．企業(yè)應(yīng)盡快處理該資源 D．企業(yè)應(yīng)充分利用該資源，開僻新的生產(chǎn)途徑 三、多選題 1．在一對對偶問題中，可能存在的情況是 ABC。 A．一個問題有可行解，另一個問題無可行解 B．兩個問題都有可行解 C．兩個問題都無可行解 D．一個問題無界，另一個問題可行 2．下列說法 錯誤 的是 B 。 A．任何線性規(guī)劃問題都有一個與之對應(yīng)的對偶問題 B．對偶問題無可行解時 ，其原問題的目標(biāo)函數(shù)無界。 C．若原問題為 maxZ=CX， AX≤b ， X≥0 ，則對偶問題為 minW=Yb， YA≥C ， Y≥ 0。 D．若原問題有可行解，但目標(biāo)函數(shù)無界，其對偶問題無可行解。 3．如線性規(guī)劃的原問題為求極大值型，則下列關(guān)于原問 題與對偶問題的關(guān)系中正確的是 BCDE。 A 原問題的約束條件 “≥” ，對應(yīng)的對偶變量 “≥ 0” B 原問題的約束條件為 “=” ，對應(yīng)的對偶變量為自由變量 C．原問題的變量 “≥ 0” ，對應(yīng)的對偶約束 “≥” D ．原問題的 變量“≤ O” 對應(yīng)的對偶約束“≤”E ．原問題的變量無符號限制，對應(yīng)的對偶約束 “=” 4．一對互為對偶的問題存在最優(yōu)解，則在其最優(yōu)點(diǎn)處有 BD A．若某個變量取值為 0，則對應(yīng)的對偶約束為嚴(yán)格的不等式 B．若某個變量取值為正，則相應(yīng)的對偶約束必為等式 C．若某個約束為等式，則相應(yīng)的對偶變?nèi)≈禐檎?D．若某個約束為嚴(yán)格的不等式，則相應(yīng)的對偶變量取值為 0 E．若某個約束為等式，則相應(yīng)的對偶變量取值為 0 5．下列有關(guān) 對偶單純形法的說法正確的是 ABCD。 A．在迭代過程中應(yīng)先選出基變量，再選進(jìn)基變量 B．當(dāng)?shù)械玫降慕鉂M足原始可行性條 件時，即得到最優(yōu)解 C．初始單純形表中填列的是一個正則解 D．初始解不需要滿足可行性 E．初始解必須是可行的。 6．根據(jù)對偶理論，在求解線性規(guī)劃的原問題時，可以得到 以下結(jié)論 ACD。 A． 對偶問題的解 B．市場上的稀缺情況 C．影子價格 D．資源的購銷決策 E．資源的市場價格 7．在下列線性規(guī)劃問題中， CE 采用求其對偶問題的 方法，單純形迭代的步驟一般會減少。 四、名詞、簡答題 對偶可行基：凡滿足條件 δ =CCBB1A≤ 0 的基 B 稱為對偶可行基。 .對稱的對偶問題：設(shè)原始線性規(guī)劃問題為 maxZ=CX AX≤ b X ≥ 0 稱線性規(guī)劃問題 minW=Yb YA≥ C Y≥ 0 為其對偶問題。又稱它們?yōu)橐粚ΨQ的對偶問題。 影子價格：對偶變量 Yi表示與原問題的第 i 個約束條件相對應(yīng)的資源的影子價格，在數(shù)量上表現(xiàn)為，當(dāng)該約束條件的右端常數(shù)增加一個單位時（假設(shè)原問題的最優(yōu)解不變 ），原問題目標(biāo)函數(shù)最優(yōu)值增加的數(shù)量。 4．影子價格在經(jīng)濟(jì)管理中 的 作用。 （ 1）指出企業(yè)內(nèi)部挖潛的方向；（ 2）為資源的購銷決策提供依據(jù)；（ 3）分析現(xiàn)有產(chǎn)品價格變動時資源緊缺情況的影響；（ 4）分析資源節(jié)約所帶來的收益；（ 5）決定某項(xiàng)新產(chǎn)品是否應(yīng)投產(chǎn)。 5．線性規(guī)劃對偶問題可以采用 哪些 方法求解 ？ （ 1）用單純形法解對偶問題；（ 2）由原問題的最優(yōu)單純形表得到；（ 3）由原問題的最優(yōu)解利用互補(bǔ)松弛定理求得；（ 4）由 Y*=CBB1 求得，其中 B 為原問題的最優(yōu)基 一對對偶問題可能出現(xiàn)的情形： ，且二者相等； ，則另一個問題具有無可行解； 。 五、寫出下列線性規(guī)劃問題的對偶問題 1． minZ=2x1+2x2+4x3 六、已知線性規(guī)劃問題 應(yīng)用對偶理論證明該問題最優(yōu)解的目標(biāo)函數(shù)值不大于 25 七、已知線性規(guī)劃問題 maxZ=2x1+x2+5x3+6x4 其對偶問題的最優(yōu)解為 Yl﹡ =4， Y2﹡ =1， 試應(yīng)用對偶問題 的性質(zhì)求原問題的最優(yōu)解。 七、用對偶單純形法求解下列線性規(guī)劃問題： 八、已知線性規(guī)劃問題 (1) 寫出其對偶問題 (2)已知原問題最優(yōu)解為 X﹡ =(2， 2， 4， 0)T，試根據(jù)對偶 理論，直接求出對偶問題的最優(yōu)解。 W* = 16 第五章 線性規(guī)劃的靈敏度分析 一、填空題 靈敏度分析研究的是線性規(guī)劃模型的 原始、最優(yōu)解 數(shù)據(jù)變化對產(chǎn)生的 影響。 在線性規(guī)劃的靈敏度分析中，我們主要用到的性質(zhì)是 _可行性，正則性 。 3．在靈敏度分析中，某個非基變量的目標(biāo)系數(shù)的改變，將引起 該非基變量自身 的檢驗(yàn)數(shù)的變化。 4．如果某基變量的目標(biāo)系數(shù)的變化范圍超過其靈敏度分析容許的變化范圍，則此基變量應(yīng) 出基 。 5．約束常數(shù) b；的變化，不會引起解的 正則性 的變化。 6．在某線性規(guī)劃問題中，已知某資源的影子價格為 Y1，相應(yīng)的約束常數(shù) b1，在靈敏度容許變動范圍內(nèi)發(fā)生Δ b1的變化，則新 的最優(yōu)解對應(yīng)的最優(yōu)目標(biāo)函數(shù)值是 Z*+yi△ b (設(shè)原最優(yōu)目標(biāo)函數(shù)值為 Z﹡ ) 7．若某約束常 數(shù) bi的變化超過其容許變動范圍，為求得新的最優(yōu)解，需在原最優(yōu)單純形表的基礎(chǔ)上運(yùn)用 對偶單純形法 求解。 8．已知線性規(guī)劃問題，最優(yōu)基為 B，目標(biāo)系數(shù)為 CB，若新增變 量 xt，目標(biāo)系數(shù)為 ct，系數(shù)列向量為 Pt，則當(dāng) Ct≤ CBB－ 1Pt 時， xt不能 進(jìn)入基底。 9．如果線性規(guī)劃的原問題增加一個約束條件，相當(dāng)于其對偶問題增加一個 變量 。 若某線性規(guī)劃問題增加一個新的約束條件，在其最優(yōu)單純形表中將表現(xiàn)為增加 一行，一列 。 11．線性規(guī)劃靈敏度分析應(yīng)在 最優(yōu)單純形表 的基礎(chǔ)上，分析系數(shù) 變化對最優(yōu)解產(chǎn)生的影響 12．在某生產(chǎn)規(guī)劃問 題的線性規(guī)劃模型中，變量 xj的目標(biāo) 系數(shù) Cj代表該變量所對應(yīng)的產(chǎn)品的利潤，則當(dāng)某一非基變量 的目標(biāo)系數(shù)發(fā)生 增大 變化時，其有可能進(jìn)入基底。 二、單選題 1．若線性規(guī)劃問題最優(yōu)基中某個基變量的目標(biāo)系數(shù)發(fā)生 變化，則 C。 A．該基變量的檢驗(yàn)數(shù)發(fā)生變化 B．其他基變量的檢驗(yàn)數(shù)發(fā)生變化 C．所有非基變量的檢驗(yàn)數(shù)發(fā)生變化D．所有變量的檢驗(yàn)數(shù)都發(fā)生變化 2．線性 規(guī)劃靈敏度分析的主要功能是分析線性規(guī)劃參數(shù)變化對 D 的影響。 A．正則性 B．可行性 C．可行解 D．最優(yōu)解 3．在線性規(guī)劃的各項(xiàng)敏感性分析中，一定會引起最優(yōu)目 標(biāo)函數(shù)值發(fā)生變化的是 B。 A．目標(biāo)系數(shù) cj的變化 B．約束常數(shù)項(xiàng) bi變化 C．增加新的變量 D．增加新約束 4．在線性規(guī)劃問題的各種靈敏度分析中， B_的變化 不能引起最優(yōu)解的正則性變化。 A．目標(biāo)系數(shù) B．約束常數(shù) C．技術(shù)系數(shù) D．增加新的變量 E．增加新的約束條件 5．對于標(biāo)準(zhǔn)型的線性規(guī)劃問題，下列說法 錯誤 的是 C A．在新增變量的靈敏度分析中，若新變量可以進(jìn)入基底，則目標(biāo)函數(shù)將會得到進(jìn)一步改善。 B．在增加新約束條件的靈敏度分析中，新的最優(yōu)目標(biāo)函數(shù)值不可能增加。 C．當(dāng)某個約束常數(shù) bk增加時，目標(biāo)函數(shù)值一定增加。 D．某基變量的目標(biāo)系數(shù)增大 ，目標(biāo)