《運(yùn)籌學(xué)》考試大綱

1、運(yùn)籌學(xué)考試大綱一、考查目標(biāo)1.一般簡(jiǎn)單線性規(guī)劃問(wèn)題建模。線性規(guī)劃的非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型，單純形法的基本步驟與計(jì)算。2.原問(wèn)題與對(duì)偶問(wèn)題間的相互轉(zhuǎn)化關(guān)系，對(duì)偶單純形法的基本步驟與計(jì)算。掌握靈敏度分析過(guò)程，對(duì)偶理論中互補(bǔ)松弛性原理的應(yīng)用。3.應(yīng)用表上作業(yè)法求解運(yùn)輸問(wèn)題的最優(yōu)調(diào)運(yùn)方案。用Vogel法求初始調(diào)運(yùn)方案，用位勢(shì)法判別方案是否最優(yōu)（即：位勢(shì)法檢驗(yàn)），用閉回路法對(duì)方案進(jìn)行調(diào)整。4.求解整數(shù)規(guī)劃的分枝界定法的基本思想，掌握指派問(wèn)題的匈牙利算法。5.樹(shù)的基本性質(zhì)。利用標(biāo)號(hào)法確定給定賦權(quán)網(wǎng)絡(luò)有向圖的最大流量，應(yīng)用Dijkstra方法計(jì)算最短路徑。6. 網(wǎng)絡(luò)計(jì)劃圖的繪制規(guī)則，能夠根據(jù)工程明細(xì)表（包含緊

2、前工序和緊后工序）繪制網(wǎng)絡(luò)圖，時(shí)間參數(shù)的計(jì)算和關(guān)鍵路線的確定過(guò)程。7.不確定性決策的決策準(zhǔn)則。掌握決策樹(shù)的繪制及決策方案的確定。二、考查內(nèi)容（一）線性規(guī)劃及單純形法1. 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型掌握：建立線性規(guī)劃模型需要具備的三個(gè)條件及其數(shù)學(xué)模型的三種形式。重點(diǎn)掌握：將線性規(guī)劃的非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型。線性規(guī)劃標(biāo)準(zhǔn)型式的定義；非標(biāo)準(zhǔn)型標(biāo)準(zhǔn)化的處理方法；2. 單純形法重點(diǎn)掌握：正確列出線性規(guī)劃問(wèn)題模型的初始單純形表，求出初始基可行解，進(jìn)行最優(yōu)性檢驗(yàn)（確定換入基變量、換出基變量、計(jì)算檢驗(yàn)數(shù)）經(jīng)過(guò)迭代計(jì)算直到求出最終單純形表。3. 線性規(guī)劃問(wèn)題建模掌握：能夠針對(duì)簡(jiǎn)單的線性規(guī)劃問(wèn)題建立相應(yīng)的模型。（二）

3、線性規(guī)劃的對(duì)偶理論與靈敏度分析1. 單純形法的矩陣描述掌握：用矩陣方式描述初始單純形表與最終單純形表的推導(dǎo)過(guò)程。重點(diǎn)掌握：用基矩陣的逆矩陣表示初始單純形表與最終單純形表中當(dāng)前解及各系數(shù)矩陣的推導(dǎo)公式。2. 線性規(guī)劃對(duì)偶理論結(jié)合原問(wèn)題與對(duì)偶問(wèn)題間的相互轉(zhuǎn)化關(guān)系，能夠根據(jù)原問(wèn)題寫(xiě)出對(duì)應(yīng)的對(duì)偶問(wèn)題；了解互補(bǔ)松馳性定理的敘述并掌握其應(yīng)用。重點(diǎn)掌握：對(duì)偶單純形法的計(jì)算過(guò)程。3靈敏度分析重點(diǎn)掌握：熟悉Cj、bi、aij 等參數(shù)變化時(shí)，進(jìn)行解的靈敏度分析，最終能夠正確求出線性規(guī)劃問(wèn)題的最優(yōu)解。掌握：增加新變量、新約束的靈敏度分析與求解；（三）運(yùn)輸問(wèn)題1.運(yùn)輸問(wèn)題的數(shù)學(xué)模型了解：產(chǎn)銷平衡問(wèn)題的運(yùn)輸問(wèn)題數(shù)學(xué)模型

4、及系數(shù)矩陣的特點(diǎn)；對(duì)應(yīng)其對(duì)偶問(wèn)題及對(duì)偶變量（行、列位勢(shì)）。2.表上作業(yè)法能熟練地應(yīng)用表上作業(yè)法求解運(yùn)輸問(wèn)題的最優(yōu)調(diào)運(yùn)方案。重點(diǎn)掌握：用位勢(shì)法判別當(dāng)前方案是否最優(yōu)（即：位勢(shì)法檢驗(yàn)）、閉合回路的調(diào)整及最優(yōu)解的求解。（四）整數(shù)規(guī)劃1.整數(shù)規(guī)劃問(wèn)題的分枝定界法掌握：求解整數(shù)規(guī)劃的分枝界定法的基本思想。2.指派問(wèn)題掌握：指派問(wèn)題的數(shù)學(xué)模型。重點(diǎn)掌握：指派問(wèn)題的匈牙利解法（包括：人數(shù)與事件數(shù)相等或不等的指派問(wèn)題，其它類型可一般了解）。（五）圖與網(wǎng)絡(luò)分析1.圖的基本概念及樹(shù)的基本性質(zhì)了解：樹(shù)的基本性質(zhì)。2.最短路問(wèn)題 重點(diǎn)掌握：應(yīng)用Dijkstra方法計(jì)算給定網(wǎng)絡(luò)的最短路徑。3.網(wǎng)絡(luò)最大流問(wèn)題重點(diǎn)掌握：利用標(biāo)號(hào)法確定給定賦權(quán)網(wǎng)絡(luò)有向圖的最大流量，能夠確定網(wǎng)絡(luò)圖的最小割集。（六）網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃圖繪制及時(shí)間參數(shù)計(jì)算掌握：網(wǎng)絡(luò)計(jì)劃圖的繪制規(guī)則，時(shí)間參數(shù)的計(jì)算過(guò)程。重點(diǎn)掌握：能夠根據(jù)給定的項(xiàng)目計(jì)劃表，正確繪制網(wǎng)絡(luò)計(jì)劃圖，結(jié)合時(shí)