運(yùn)籌學(xué)復(fù)習(xí)資料

考試范圍第一章線性規(guī)劃及單純形法第二章對(duì)偶問題第三章運(yùn)輸問題第五章整數(shù)規(guī)劃第一章線性規(guī)劃及單純形法線性規(guī)劃問題的一般數(shù)學(xué)模型代數(shù)方程矩陣和向量的形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式上述模型的簡寫形式為：代數(shù)方程矩陣和向量的形式價(jià)值向量資源向量決策變量向量系數(shù)矩陣mn系數(shù)矩陣的列向量線性規(guī)劃問題的標(biāo)準(zhǔn)形式其中常數(shù)項(xiàng)標(biāo)準(zhǔn)化⑴若目標(biāo)函數(shù)為（2）若約束條件為不等式，分為兩種情況討論：加入松弛變量加入剩余變量（3）對(duì)于決策變量非負(fù)的要求，分為兩種情況討論：①非正變量②自由變量線性規(guī)劃問題的幾個(gè)重要性質(zhì)解的可能性：唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解；若線性規(guī)劃問題的可行解存在，則可行域是一個(gè)凸集；若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一一定是可行域的凸集的某個(gè)頂點(diǎn)。線性規(guī)劃圖解法適用于：2個(gè)決策變量線性規(guī)劃求解的單純形法解的幾個(gè)重要概念：最優(yōu)解、可行解、基解、基可行解、退化解解與解之間的關(guān)系退化解是不是基可行解？

非可行解可行基可行解解

基解線性規(guī)劃求解的單純形法基（B）：約束方程的m×n階系數(shù)矩陣A的秩為m，且m<n。則，B是A中mm階的滿秩子矩陣。（或：B由A中m個(gè)線性無關(guān)的列向量所組成）基的數(shù)目不超過基與解的對(duì)應(yīng)關(guān)系基解基可行基基可行解最優(yōu)基基最優(yōu)解線性規(guī)劃問題求解——單純形法代數(shù)法表格法線性規(guī)劃問題求解的步驟標(biāo)準(zhǔn)化；初始基可行解的確定最優(yōu)性檢驗(yàn)基變換進(jìn)基變量出基變量小結(jié)初始化最優(yōu)性檢驗(yàn)迭代（Iteration）最優(yōu)？yesSTOPno初始基可行解的確定當(dāng)前的基可行解是否最優(yōu)？包括三個(gè)步驟：1、確定進(jìn)基變量（進(jìn)基）2、確定出基變量（出基）3、對(duì)新基可行解的求解（高斯消元）單純形表的格式CjC1C2…Cn

θiCBXBbx1

x2….xn

C1

C2…Cmx1x2…xmb1b2…bma11a12…a1na21a22…a2n………am1am2…amnθ1θ2…θm

σjσ1σ2…σn迭代計(jì)算中每找出一個(gè)新的基可行解時(shí)，就重畫一張單純形表。含初始基可行解的單純形表稱初始單純形表，含最優(yōu)解的單純形表稱最終單純形表。如何求得B-1?見P157表格單純形法的計(jì)算步驟①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型②找出或構(gòu)造一個(gè)m階單位矩陣作為初始可行基，建立初始單純形表；③計(jì)算各非基變量xj的檢驗(yàn)數(shù)j=Cj-CBPj

′，若所有j≤0，則問題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下步；④在大于0的檢驗(yàn)數(shù)中，若某個(gè)k所對(duì)應(yīng)的系數(shù)列向量Pk′≤0，則此問題是無界解，停止計(jì)算，否則轉(zhuǎn)入下步；表格單純形法的計(jì)算步驟⑤換基：根據(jù)max{j｜j＞0}=k原則，確定xk為換入變量(進(jìn)基變量)（進(jìn)基）；確定xL為換出變量。建立新的單純形表，此時(shí)基變量中xk取代了xL的位置。(出基)⑥以aLk′為樞軸元素進(jìn)行迭代，把xk所對(duì)應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aLk′變?yōu)?，同列中其它元素為0，（高斯消元），轉(zhuǎn)第③步表格單純形法的幾種特殊情況（1）唯一最優(yōu)解在最終單純形表中所有非基變量j<0時(shí)，該線性規(guī)劃問題具有唯一解（2）無窮多最優(yōu)解在最終單純形表中，存在非基變量的檢驗(yàn)數(shù)j=0，則表明可以找到另一個(gè)頂點(diǎn)（基可行解）目標(biāo)函數(shù)值也達(dá)到最大。（讓這個(gè)非基變量進(jìn)基，繼續(xù)迭代，得另一個(gè)最優(yōu)解）表格單純形法的幾種特殊情況（3）無界解無出基變量：即，存在某個(gè)j>0，且Pj≤0（4）無可行解：采用人工變量法時(shí)，最終表中人工變量仍沒有置換出去人工變量法高斯變換中，如果資源列向量出現(xiàn)負(fù)數(shù)，則采用人工變量法。通過換基，最好使得人工變量成為非基變量。有兩種方法：大M法兩段法人工變量法——大M法兩段法人工變量法——兩段法大M法對(duì)偶單純形法對(duì)偶單純形法的優(yōu)點(diǎn)：無需人工變量思路：始終保持對(duì)偶問題可行。初始表原問題不可行，經(jīng)過變換，對(duì)偶問題和原問題均可行，從而得到最優(yōu)解。最優(yōu)性檢驗(yàn)標(biāo)準(zhǔn)：常數(shù)列是否都≥0對(duì)偶單純形法對(duì)偶單純形法的步驟：初始表檢驗(yàn)行≤0；常數(shù)列可以有<0確定出基變量確定進(jìn)基變量如果主行所有的a元素>0，說明原問題無可行解。第二章對(duì)偶問題原問題對(duì)偶問題3個(gè)約束2個(gè)變量2個(gè)約束3個(gè)變量原問題對(duì)偶問題一般規(guī)律≤≤...≤maxmin≥對(duì)偶問題原問題≥≥對(duì)稱形式的對(duì)偶問題非對(duì)稱形式的對(duì)偶問題

原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）對(duì)偶問題的基本性質(zhì)1、對(duì)稱性：對(duì)偶問題的對(duì)偶是原問題2、弱對(duì)偶性：原問題的目標(biāo)值是對(duì)偶問題目標(biāo)值的下界；對(duì)偶問題的目標(biāo)值是原問題目標(biāo)值的上界（P）無界＝>（D）無可行解；（D）無界＝>（P）無可行解；（P）可行而（D）不可行＝>（P）無界；（D）可行而（P）不可行＝>（D）無界。PD最優(yōu)無界不可行最優(yōu)不可行無界原問題（P）與對(duì)偶問題（D）解的關(guān)系對(duì)偶問題的基本性質(zhì)3、最優(yōu)性如果，原問題的目標(biāo)值=對(duì)偶問題目標(biāo)值則，此解既是原問題的最優(yōu)解，也是對(duì)偶問題的最優(yōu)解4、對(duì)偶性（強(qiáng)對(duì)偶性）若原問題有最優(yōu)解，則對(duì)偶問題一定具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等對(duì)偶問題的基本性質(zhì)5、互補(bǔ)松弛性在線性規(guī)劃問題的最優(yōu)解中：

如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值非零，則該約束條件取嚴(yán)格等式；

反之，如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定是零。松

緊（等式）緊松對(duì)偶問題的基本性質(zhì)6、單純形表上基解對(duì)應(yīng)關(guān)系當(dāng)采用單純形法求LP問題時(shí)，迭代的每一步在得到原問題的一個(gè)基本可行解的同時(shí)，檢驗(yàn)行上同時(shí)得到對(duì)偶問題的一個(gè)基解。對(duì)應(yīng)關(guān)系為：原問題對(duì)偶問題決策變量剩余變量松弛變量決策變量解的經(jīng)濟(jì)學(xué)解釋——影子價(jià)格1、影子價(jià)格是一種邊際價(jià)格2、反映資源的稀缺程度一般說對(duì)線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及到資源的最有效利用解的經(jīng)濟(jì)學(xué)解釋——影子價(jià)格3、檢驗(yàn)數(shù)的經(jīng)濟(jì)意義—第j種產(chǎn)品的產(chǎn)值—生產(chǎn)第j中產(chǎn)品所消耗各項(xiàng)資源的影子價(jià)格的總和。（即隱含成本）可見，產(chǎn)品產(chǎn)值>隱含成本可生產(chǎn)該產(chǎn)品；否則，不安排生產(chǎn)?！獧z驗(yàn)數(shù)的經(jīng)濟(jì)意義靈敏度分析研究內(nèi)容：

研究線性規(guī)劃中，的變化，增加變量以及增加約束條件對(duì)最優(yōu)解的影響。研究方法：圖解法對(duì)偶理論分析僅適用于含2個(gè)變量的線性規(guī)劃問題在單純形表中進(jìn)行分析研究的目的：最優(yōu)性不變，及其條件最優(yōu)性改變，用原始單純形法，找出新最優(yōu)解要求：對(duì)單純形法思路的理解非常透徹，計(jì)算非常熟練第三章運(yùn)輸問題標(biāo)準(zhǔn)型（產(chǎn)銷平衡）運(yùn)輸問題的數(shù)學(xué)模型平衡運(yùn)輸問題必有可行解，也必有最優(yōu)解

銷地產(chǎn)地產(chǎn)量銷量運(yùn)價(jià)表運(yùn)輸問題約束條件的系數(shù)矩陣運(yùn)輸問題是一個(gè)具有m×n個(gè)變量和n+m個(gè)等型約束的線性規(guī)劃問題約束條件的系數(shù)矩陣是：n+m行，m×n列運(yùn)輸問題約束方程組的系數(shù)矩陣是一個(gè)只有0和1兩個(gè)數(shù)值的稀疏矩陣，其中1的總數(shù)為2×m×n個(gè)約束條件系數(shù)矩陣的每一列有兩個(gè)非零元素，這對(duì)應(yīng)于每一個(gè)變量在前m個(gè)約束方程中出現(xiàn)一次，在后n個(gè)約束方程中也出現(xiàn)一次約束條件系數(shù)矩陣的秩是m+n-1。即運(yùn)輸問題的基變量總數(shù)是m+n-1系數(shù)矩陣的列向量表示即：表上作業(yè)法來求解運(yùn)輸問題計(jì)算步驟：1、給出初始方案2、檢驗(yàn)是否最優(yōu)3、調(diào)整調(diào)運(yùn)方案,Goto2確定初始可行解的方法最小元素法西北角法沃格爾(Vogel)法解的最優(yōu)性檢驗(yàn)的方法1閉回路法2對(duì)偶變量法，也稱為位勢(shì)法解的改進(jìn)（用閉回路法調(diào)整）選擇進(jìn)基變量的原則：即選擇非基變量中檢驗(yàn)數(shù)最小的一個(gè)進(jìn)基。在進(jìn)基格點(diǎn)所對(duì)應(yīng)的閉回路上，定義頂點(diǎn)的序號(hào)：自進(jìn)基格點(diǎn)起選定一個(gè)方向（比如順時(shí)針方向），依次為第一格、第二格、…在奇數(shù)格點(diǎn)上增加調(diào)整量，在偶數(shù)格點(diǎn)上減少調(diào)整量。調(diào)整量取閉回路上的最小值運(yùn)輸問題，解的可能性多重解若在最優(yōu)解中，某個(gè)非基變量的檢驗(yàn)數(shù)為零退化解基變量取值為0產(chǎn)銷不平衡的運(yùn)輸問題若產(chǎn)大于銷，增加一個(gè)假想的銷地若銷大于產(chǎn)，增加一個(gè)虛擬的產(chǎn)地相應(yīng)的運(yùn)價(jià)設(shè)為0第五章整數(shù)規(guī)劃整數(shù)規(guī)劃問題的類型求解整數(shù)規(guī)劃的方法整數(shù)規(guī)劃問題的類型純整數(shù)線性規(guī)劃混合整數(shù)線性規(guī)劃0-1型線性規(guī)劃求解整數(shù)規(guī)劃的方法分支定界法割平面法分支定界法分支松弛問題的最優(yōu)解不符合整數(shù)要求，構(gòu)造兩個(gè)約束條件從而形成兩個(gè)分枝，即兩個(gè)后續(xù)問題。定界若某個(gè)分支的解滿足整數(shù)約束，那么他的目標(biāo)值可作為后續(xù)分支的過濾條件（以提高搜索效率），把這個(gè)叫做“定界”對(duì)于最大值問題，“下界”割平面法增設(shè)一個(gè)新的約束條件（割平面方程）割平面約束的構(gòu)造選擇具有最大分?jǐn)?shù)部分的非整分量所在行構(gòu)造割平面約束割平面約束的構(gòu)造方法Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4j00-1/4-1/40-1型整數(shù)規(guī)劃0-1型整數(shù)規(guī)劃模型的構(gòu)造0-1型整數(shù)規(guī)劃的解法0-1型整數(shù)規(guī)劃模型的構(gòu)造互斥問題固定費(fèi)用問題工件排序問題一些典型的技巧肯定的決策否定的決策0-1邏輯變量一般取值互斥問題的大M法（Mx）否定的決策肯定的決策一些典型的技巧利用0-1變量構(gòu)造任意整數(shù)一些典型的技巧互斥問題X1+x2=1決策變量的互斥約束方程的互斥一般地，若需要從p個(gè)約束條件中恰好選擇q個(gè)約束條件，則可用引入p個(gè)0-1向量若選擇第i個(gè)約束條件若不選擇第i個(gè)約束條件那么，約束條件組就可用達(dá)到這個(gè)目的。因?yàn)樯鲜黾s束條件組保證了在p個(gè)0-1變量中有p-q個(gè)為1，q個(gè)為0。凡取0值的yi對(duì)應(yīng)的約束條件即為原約束條件，而取1的yi對(duì)應(yīng)的約束條件無效。0-1型整數(shù)規(guī)劃的解法隱枚舉法例求解0-1整數(shù)規(guī)劃解求解過程可以列表表示(x1,x2,x3)Z值約束條件（abcd）過濾條件(0,0,0)0√√√√Z≥0(0,0,1)5√√√√Z≥5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8√√√√Z≥8abcd(x1,x2,x3)Z值約束條件（abcd）過濾條件(1,1,0)1(1,1,1)6接上表所以，最優(yōu)解（x1,x2,x3）T=(1,0,1)T,maxZ=8由于采用上述算法，實(shí)際只作了20次運(yùn)算。指派問題指派問題模型的構(gòu)造