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

1、運(yùn)籌學(xué)運(yùn)籌學(xué)復(fù)習(xí)復(fù)習(xí)第第1章章 緒論緒論用科學(xué)方法分析管理及工程問題，為決策提用科學(xué)方法分析管理及工程問題，為決策提供依據(jù)。供依據(jù)。目標(biāo)：在企業(yè)經(jīng)營內(nèi)外環(huán)境的限制下，實(shí)現(xiàn)目標(biāo)：在企業(yè)經(jīng)營內(nèi)外環(huán)境的限制下，實(shí)現(xiàn)資源效用最大。資源效用最大。組織中存組織中存在的問題在的問題定量分析定量分析定性分析定性分析評(píng)價(jià)與評(píng)估評(píng)價(jià)與評(píng)估決策決策第第2章章線性規(guī)劃及單純形法線性規(guī)劃及單純形法u一般線性規(guī)劃的數(shù)學(xué)模型一般線性規(guī)劃的數(shù)學(xué)模型u圖解法圖解法u單純形法單純形法u線性規(guī)劃的一般模型線性規(guī)劃的一般模型0.,),(.),(.),(.max(min)21221122222121112121112211nmnmmm

2、nnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz約束條件目標(biāo)函數(shù)u標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式0.,.max21221122222121112121112211nmnmmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz約束條件目標(biāo)函數(shù)I 可行解可行解I 可行域可行域I 最優(yōu)解最優(yōu)解I 基基I 基向量基向量I 非基向量非基向量I 基變量基變量I 非基變量非基變量I 基解基解I 基可行解基可行解 建立坐標(biāo)系建立坐標(biāo)系 找出可行域找出可行域 繪出目標(biāo)函數(shù)圖形繪出目標(biāo)函數(shù)圖形 求出最優(yōu)解求出最優(yōu)解u 圖解法步驟圖解法步驟 唯一最優(yōu)解唯一最優(yōu)解 無窮多最優(yōu)解無窮

3、多最優(yōu)解 無界解（或無最優(yōu)解）無界解（或無最優(yōu)解） 無可行解無可行解u線性規(guī)劃問題解的情況線性規(guī)劃問題解的情況凸集和頂點(diǎn)凸集和頂點(diǎn)z 線性規(guī)劃問題的線性規(guī)劃問題的基可行解基可行解X對(duì)應(yīng)線性對(duì)應(yīng)線性規(guī)劃問題規(guī)劃問題可行域（凸集）的頂點(diǎn)可行域（凸集）的頂點(diǎn)。z 若線性規(guī)劃問題有若線性規(guī)劃問題有最優(yōu)解最優(yōu)解，一定在一，一定在一某個(gè)某個(gè)頂點(diǎn)得到頂點(diǎn)得到。 單純形法步驟：單純形法步驟：K 確定初始基可行解；確定初始基可行解；K 從初始基可行解轉(zhuǎn)換為另一基可行解；從初始基可行解轉(zhuǎn)換為另一基可行解；K 最優(yōu)性檢驗(yàn)和判別。最優(yōu)性檢驗(yàn)和判別。1、線性規(guī)劃的標(biāo)準(zhǔn)形式、線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：目標(biāo)函數(shù)：約束條件

4、：約束條件：1 1221max.nnniiizc xc xc xc x11 11221121 1222221 12212. . .,.0nnnnmmmnnmna xa xa xba xa xa xbsta xaxa xbx xx目標(biāo)系數(shù)目標(biāo)系數(shù)決策決策變量變量技術(shù)技術(shù)系數(shù)系數(shù)右右端端項(xiàng)項(xiàng)I 1、min Z=CX max Z= -CXI 2、約束條件為約束條件為“” 轉(zhuǎn)換為轉(zhuǎn)換為“=”方法方法：I 在在s.t.中左端加上一個(gè)中左端加上一個(gè)“松弛變量松弛變量”，使，使“”變?yōu)樽優(yōu)椤?”。同時(shí)，在目標(biāo)函數(shù)中，令。同時(shí)，在目標(biāo)函數(shù)中，令松弛變量的目標(biāo)系數(shù)為松弛變量的目標(biāo)系數(shù)為0。I 3、約束條件為約束

5、條件為“”轉(zhuǎn)換為轉(zhuǎn)換為“=”方法：方法：I 在在s.t.中左端減去一個(gè)中左端減去一個(gè)“剩余變量剩余變量”，使，使“”變?yōu)樽優(yōu)椤?”。同時(shí)，在目標(biāo)函數(shù)中，令。同時(shí)，在目標(biāo)函數(shù)中，令剩余變量的目標(biāo)系數(shù)為剩余變量的目標(biāo)系數(shù)為0。2、非標(biāo)準(zhǔn)形式的標(biāo)準(zhǔn)化方法、非標(biāo)準(zhǔn)形式的標(biāo)準(zhǔn)化方法I 4、決策變量決策變量xi0 xj = - xiI 5、決策變量的符號(hào)不受限制決策變量的符號(hào)不受限制 xj = xj- xj， xj，xj 0. 2022-6-10143、圖解法、圖解法 對(duì)于只含有兩個(gè)變量的線性規(guī)劃問題，可通對(duì)于只含有兩個(gè)變量的線性規(guī)劃問題，可通過在平面上作圖的方法求解。其步驟如下：過在平面上作圖的方法求解

6、。其步驟如下： 建立平面直角坐標(biāo)系；建立平面直角坐標(biāo)系；圖示約束條件，找出可行域；圖示約束條件，找出可行域；圖示目標(biāo)函數(shù)，即為一條直線；圖示目標(biāo)函數(shù)，即為一條直線；將目標(biāo)函數(shù)直線沿其法線方向在可行域邊將目標(biāo)函數(shù)直線沿其法線方向在可行域邊界平移直至函數(shù)達(dá)到最優(yōu)值為止，目標(biāo)函數(shù)界平移直至函數(shù)達(dá)到最優(yōu)值為止，目標(biāo)函數(shù)達(dá)到最優(yōu)值的點(diǎn)就為最優(yōu)點(diǎn)。達(dá)到最優(yōu)值的點(diǎn)就為最優(yōu)點(diǎn)。4、單純形法的計(jì)算步驟單純形法的計(jì)算步驟R（1）將問題化為標(biāo)準(zhǔn)型；）將問題化為標(biāo)準(zhǔn)型；R（2）求出線性規(guī)劃的初始基可行解，列出初）求出線性規(guī)劃的初始基可行解，列出初始單純形表；始單純形表；R（3）進(jìn)行最優(yōu)性檢驗(yàn)：）進(jìn)行最優(yōu)性檢驗(yàn)： 如果

7、表中所有檢驗(yàn)如果表中所有檢驗(yàn)數(shù)數(shù) ，則表中的基可行解就是問題的最，則表中的基可行解就是問題的最優(yōu)解，計(jì)算停止。否則繼續(xù)下一步。優(yōu)解，計(jì)算停止。否則繼續(xù)下一步。0 s sjR（4）從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值）從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)值更大的基可行解，列出新的單純形表。更大的基可行解，列出新的單純形表。確定換入基的變量。選擇確定換入基的變量。選擇 ，對(duì)應(yīng)的變，對(duì)應(yīng)的變量量xj作為換入變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于作為換入變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于0 0時(shí)，一般選擇最大的一個(gè)檢驗(yàn)數(shù)，即：時(shí)，一般選擇最大的一個(gè)檢驗(yàn)數(shù)，即： 其對(duì)應(yīng)的其對(duì)應(yīng)的xk作為換入變量。作為換入變量。確定換出變量。根據(jù)

8、下式計(jì)算并選擇確定換出變量。根據(jù)下式計(jì)算并選擇，選，選最小的最小的對(duì)應(yīng)基變量作為換出變量。對(duì)應(yīng)基變量作為換出變量。0|max s ss s s sjjk 0minikikiLaab0 s sj 用換入變量用換入變量xk替換基變量中的換出變量，得到替換基變量中的換出變量，得到一個(gè)新的基。對(duì)應(yīng)新的基可以找出一個(gè)新的基一個(gè)新的基。對(duì)應(yīng)新的基可以找出一個(gè)新的基可行解，并相應(yīng)地可以畫出一個(gè)新的單純形表可行解，并相應(yīng)地可以畫出一個(gè)新的單純形表。R（5）重復(fù)（）重復(fù)（3）、（）、（4）步直到計(jì)算結(jié)束為止。）步直到計(jì)算結(jié)束為止。原問題原問題(對(duì)偶問題對(duì)偶問題)對(duì)偶問題對(duì)偶問題(原問題原問題)目標(biāo)函數(shù)目標(biāo)函數(shù)m

9、ax目標(biāo)函數(shù)目標(biāo)函數(shù)min約約束束條條件件m個(gè)個(gè)=m個(gè)個(gè)00無符號(hào)限制無符號(hào)限制變變量量變變量量n個(gè)個(gè)00無符號(hào)限制無符號(hào)限制n個(gè)個(gè)=約約束束條條件件資源系數(shù)資源系數(shù) b價(jià)值系數(shù)價(jià)值系數(shù) c系數(shù)矩陣系數(shù)矩陣A 價(jià)值系數(shù)價(jià)值系數(shù) b 資源系數(shù)資源系數(shù) c系數(shù)矩陣系數(shù)矩陣AT 對(duì)偶規(guī)則表對(duì)偶規(guī)則表對(duì)偶理論對(duì)偶理論：1 12211 121 21112 1222221122min( ).0(1,2,).mmmmmmnnmnmniWbyb yb ya ya ya yca ya ya ycDsta ya ya ycyim則其對(duì)偶問題的一般形式為則其對(duì)偶問題的一般形式為1 12 211 112 21121

10、122 2221 12 2max( ).0(1,2,).n nn nn nmmmn nmjZcxc xc xa xa xa xba xa xa xbPsta xa xa xbxjn對(duì)稱形式對(duì)稱形式的線性規(guī)劃的線性規(guī)劃原問題的一般形式為原問題的一般形式為對(duì)稱形式對(duì)偶問題對(duì)稱形式對(duì)偶問題一對(duì)對(duì)偶問題的關(guān)系，只能有下面三種情況之一：一對(duì)對(duì)偶問題的關(guān)系，只能有下面三種情況之一： 1. 都有最優(yōu)解；都有最優(yōu)解； 2.一個(gè)問題無界，則另一個(gè)問題無可行解；一個(gè)問題無界，則另一個(gè)問題無可行解； 3. 兩個(gè)都無可行解兩個(gè)都無可行解. 0. .)(maxXbAXtsPCXZ 0. .)(minYCYAtsDYbW

11、n 對(duì)偶規(guī)劃可以用線性規(guī)劃的單純形法求解。對(duì)偶規(guī)劃可以用線性規(guī)劃的單純形法求解。n由對(duì)偶原理可見，原問題與對(duì)偶問題之間有由對(duì)偶原理可見，原問題與對(duì)偶問題之間有緊密聯(lián)系，因此我們能夠通過求解原問題來找緊密聯(lián)系，因此我們能夠通過求解原問題來找出對(duì)偶問題的解，反之依然。出對(duì)偶問題的解，反之依然。n互補(bǔ)松弛條件就可以解決由原問題的最優(yōu)解互補(bǔ)松弛條件就可以解決由原問題的最優(yōu)解直接求出對(duì)偶問題的最優(yōu)解。直接求出對(duì)偶問題的最優(yōu)解。對(duì)偶問題解的求法對(duì)偶問題解的求法K對(duì)偶單純形法是對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本求解線性規(guī)劃的另一個(gè)基本方法方法，它是根據(jù)對(duì)偶原理和單純形法的原理，它是根據(jù)對(duì)偶原理和單純形法

12、的原理而設(shè)計(jì)出來的，因此稱為對(duì)偶單純形法。而設(shè)計(jì)出來的，因此稱為對(duì)偶單純形法。K不要簡單地將對(duì)偶單純形法理解為求解對(duì)偶不要簡單地將對(duì)偶單純形法理解為求解對(duì)偶問題的單純形法。問題的單純形法。ibjs原始單純形法原始單純形法對(duì)偶單純形法對(duì)偶單純形法前提條件前提條件所有所有 0所有所有 0最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)所有所有 0？所有所有 0？換入、出基換入、出基變量的確定變量的確定先確定換入基變量先確定換入基變量后確定換出基變量后確定換出基變量先確定換出基變量先確定換出基變量后確定換入基變量后確定換入基變量原始基本解原始基本解的進(jìn)化的進(jìn)化可行可行最優(yōu)最優(yōu)（對(duì)偶問題的解從（對(duì)偶問題的解從不可行到可行）不可行

13、到可行）非可行非可行可行（最優(yōu)）可行（最優(yōu)）（原問題的解從不可行（原問題的解從不可行到可行）到可行）ibjs第第4章章 運(yùn)輸問題運(yùn)輸問題1、運(yùn)輸問題的數(shù)學(xué)模型的建立；、運(yùn)輸問題的數(shù)學(xué)模型的建立；2、產(chǎn)銷平衡下運(yùn)輸問題的、產(chǎn)銷平衡下運(yùn)輸問題的基變量個(gè)數(shù)基變量個(gè)數(shù)與產(chǎn)地、與產(chǎn)地、銷地之間的關(guān)系（銷地之間的關(guān)系（m+n-1），即（），即（m+n-1）個(gè)獨(dú)）個(gè)獨(dú)立約束方程；立約束方程；3、約束方程都是等式。、約束方程都是等式。一、確定初始基可行解一、確定初始基可行解運(yùn)輸問題的初始方案的確定主要有：運(yùn)輸問題的初始方案的確定主要有：最小元素法最小元素法伏格爾法伏格爾法運(yùn)輸問題運(yùn)輸問題找出找出初始基可行解初

14、始基可行解，即在產(chǎn)銷平衡表，即在產(chǎn)銷平衡表上有（上有（m+n-1）個(gè)數(shù)字格。）個(gè)數(shù)字格。1、最小元素法的精髓最小元素法的精髓（就近供應(yīng)，從單位運(yùn)就近供應(yīng)，從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，依次類價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，依次類推，只到給出全部方案為止）；推，只到給出全部方案為止）；2、Vogel法的核心法的核心（最大差額處，優(yōu)先按最?。ㄗ畲蟛铑~處，優(yōu)先按最小運(yùn)價(jià)進(jìn)行調(diào)整）；運(yùn)價(jià)進(jìn)行調(diào)整）；3、位勢(shì)法求檢驗(yàn)數(shù)、閉回路法進(jìn)行調(diào)整位勢(shì)法求檢驗(yàn)數(shù)、閉回路法進(jìn)行調(diào)整；4、產(chǎn)銷不平衡時(shí)的調(diào)整方法。、產(chǎn)銷不平衡時(shí)的調(diào)整方法。第第5章章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃1、目標(biāo)規(guī)劃的組成與特點(diǎn)；、目標(biāo)規(guī)劃的組

15、成與特點(diǎn)；2、目標(biāo)規(guī)劃的模型（如何建立目標(biāo)函數(shù)、目標(biāo)規(guī)劃的模型（如何建立目標(biāo)函數(shù)、目標(biāo)約束建立等）；目標(biāo)約束建立等）；3、目標(biāo)函數(shù)中偏差變量的取舍目標(biāo)函數(shù)中偏差變量的取舍（利潤型目（利潤型目標(biāo)、成本型目標(biāo)和合同型目標(biāo)中偏差變量標(biāo)、成本型目標(biāo)和合同型目標(biāo)中偏差變量的取舍）；的取舍）；4、掌握、掌握目標(biāo)規(guī)劃應(yīng)用方法目標(biāo)規(guī)劃應(yīng)用方法（不用求解）。（不用求解）。1、目標(biāo)規(guī)劃的特點(diǎn)、目標(biāo)規(guī)劃的特點(diǎn) 約束一般包括約束一般包括目標(biāo)約束目標(biāo)約束、系統(tǒng)約束系統(tǒng)約束、非、非負(fù)約束三個(gè)部分；負(fù)約束三個(gè)部分； 最終目標(biāo)最終目標(biāo)轉(zhuǎn)換為求轉(zhuǎn)換為求偏離多個(gè)期望目標(biāo)值偏離多個(gè)期望目標(biāo)值的偏差和最小的偏差和最小； 目標(biāo)及約束仍

16、為目標(biāo)及約束仍為線性線性。（1）對(duì)于）對(duì)于利潤型目標(biāo)利潤型目標(biāo)，要求是可能實(shí)現(xiàn)值超，要求是可能實(shí)現(xiàn)值超過目標(biāo)值越多越好，即過目標(biāo)值越多越好，即d+越大越好，則在目標(biāo)越大越好，則在目標(biāo)函數(shù)中，函數(shù)中，不能對(duì)不能對(duì)d+求最小求最??；（2）對(duì)于）對(duì)于成本型目標(biāo)成本型目標(biāo)，要求可能實(shí)現(xiàn)值低于，要求可能實(shí)現(xiàn)值低于目標(biāo)值越多越好，即目標(biāo)值越多越好，即d-越大越好，則在目標(biāo)函越大越好，則在目標(biāo)函數(shù)中數(shù)中不能對(duì)不能對(duì)d-求最小求最??；（3）對(duì)于）對(duì)于合同型目標(biāo)合同型目標(biāo)，要求跟目標(biāo)保持一致，要求跟目標(biāo)保持一致，不超過也不短缺，即不超過也不短缺，即要求要求d+和和d-都最小都最小，則在則在目標(biāo)函數(shù)中應(yīng)將兩者綜合

17、考慮。目標(biāo)函數(shù)中應(yīng)將兩者綜合考慮。2、目標(biāo)函數(shù)中偏差變量的優(yōu)化、目標(biāo)函數(shù)中偏差變量的優(yōu)化第第6章章 整數(shù)規(guī)劃整數(shù)規(guī)劃I分支定界法分支定界法I割平面法割平面法I指派問題及匈牙利法指派問題及匈牙利法 分枝定界法分枝定界法：將原整數(shù)規(guī)劃問題分枝將原整數(shù)規(guī)劃問題分枝分分為兩個(gè)子規(guī)劃為兩個(gè)子規(guī)劃, ,再解子規(guī)劃的伴隨規(guī)劃再解子規(guī)劃的伴隨規(guī)劃通過求解一系列子規(guī)劃的伴隨規(guī)劃及不斷通過求解一系列子規(guī)劃的伴隨規(guī)劃及不斷地定界地定界。最后得到原整數(shù)規(guī)劃問題的整數(shù)。最后得到原整數(shù)規(guī)劃問題的整數(shù)最優(yōu)解。最優(yōu)解。K從從( (LP) )的最優(yōu)解中，任選一個(gè)不為整數(shù)的分的最優(yōu)解中，任選一個(gè)不為整數(shù)的分量量x xr,r, ,

18、將最優(yōu)單純形表中該行的系數(shù)將最優(yōu)單純形表中該行的系數(shù)arj和和 br分分解為解為整數(shù)部分和非負(fù)真分?jǐn)?shù)部分整數(shù)部分和非負(fù)真分?jǐn)?shù)部分之和，之和， 并以該行為源行，按作割平面方程。并以該行為源行，按作割平面方程。K將所得的割平面方程，作為一個(gè)新的約束條件將所得的割平面方程，作為一個(gè)新的約束條件置于最優(yōu)單純形表中同時(shí)增加一個(gè)單位列向量），置于最優(yōu)單純形表中同時(shí)增加一個(gè)單位列向量），用對(duì)偶單純形法求出新的最優(yōu)解用對(duì)偶單純形法求出新的最優(yōu)解。割平面法割平面法K匈牙利算法。匈牙利算法。K算法主要依據(jù)以下事實(shí)：如果將系數(shù)矩陣算法主要依據(jù)以下事實(shí)：如果將系數(shù)矩陣C=（Cij）中一行（或一列）的每一元素都中一行（

19、或一列）的每一元素都加上或減去同一個(gè)數(shù)，得到一個(gè)新矩陣加上或減去同一個(gè)數(shù)，得到一個(gè)新矩陣B=（bij），），則以則以C和和B為系數(shù)矩陣的指派問題為系數(shù)矩陣的指派問題具有相同的最優(yōu)指派。具有相同的最優(yōu)指派。K系系數(shù)矩陣中獨(dú)立數(shù)矩陣中獨(dú)立 0 元素的最多個(gè)數(shù)等于能元素的最多個(gè)數(shù)等于能覆蓋所有覆蓋所有 0 元素的最少直線數(shù)。元素的最少直線數(shù)。 指派問題指派問題Step 1、先對(duì)效率矩陣進(jìn)行列變換，使其各行各、先對(duì)效率矩陣進(jìn)行列變換，使其各行各列中都出現(xiàn)列中都出現(xiàn) 0 元素。元素。效率矩陣變換方法為：效率矩陣變換方法為：從效率矩陣從效率矩陣 C 的每行元素的每行元素中減去該行的最小元素中減去該行的最小

20、元素,得矩陣得矩陣 B ；從矩陣；從矩陣 B 中中每列元素中減去該列的最每列元素中減去該列的最小元素得矩陣小元素得矩陣 C1 。21097 2154148 413 14 16 11 11415 139 4C 0875110104235001195B min 0 0 5 01082511054230001145C Step 2、確定、確定C1中線性獨(dú)立的中線性獨(dú)立的0元素元素.從第一行開始，若該行只有一個(gè)從第一行開始，若該行只有一個(gè)0元素，就對(duì)這個(gè)元素，就對(duì)這個(gè)0元素元素加圈，然后劃去其所在列的其它加圈，然后劃去其所在列的其它0元素元素;若該行沒有其它若該行沒有其它0元素或有兩個(gè)以上元素或有兩個(gè)

21、以上0元素（已劃去的不計(jì)），轉(zhuǎn)下一行；元素（已劃去的不計(jì)），轉(zhuǎn)下一行；直到最后一行為止。直到最后一行為止。然后，從第一列開始，若該列只然后，從第一列開始，若該列只有一個(gè)有一個(gè)0元素，就對(duì)這個(gè)元素，就對(duì)這個(gè)0元素加元素加圈（同樣不考慮已劃的）圈（同樣不考慮已劃的）,再劃去再劃去其所在行的其它其所在行的其它0元素；若該列沒元素；若該列沒有有0元素或有兩個(gè)以上元素或有兩個(gè)以上0元素，則元素，則轉(zhuǎn)下列直到最后一列為止。轉(zhuǎn)下列直到最后一列為止。182511054230011 45C00重復(fù)上述步驟。重復(fù)上述步驟。上述步驟可能出現(xiàn)三種情況上述步驟可能出現(xiàn)三種情況情況一：矩陣每行都有一個(gè)打情況一：矩陣每行都

22、有一個(gè)打圈的圈的 0 元素。此時(shí)得到問題的元素。此時(shí)得到問題的最優(yōu)解。最優(yōu)解。情況二：有多于兩行或兩列存在兩個(gè)以上的未處理的情況二：有多于兩行或兩列存在兩個(gè)以上的未處理的 0 元素，即出現(xiàn)元素，即出現(xiàn) 0 元素的閉回路。此時(shí)，可從中任選一元素的閉回路。此時(shí)，可從中任選一個(gè)個(gè) 0元素加圈，劃掉其同行同列的元素加圈，劃掉其同行同列的 0 元素，再重復(fù)上述元素，再重復(fù)上述兩個(gè)步驟。兩個(gè)步驟。情況三：矩陣中所有情況三：矩陣中所有 0 元素或被加圈，或被劃去，而已元素或被加圈，或被劃去，而已加圈的加圈的 0 元素元素m小于矩陣的行數(shù)小于矩陣的行數(shù)n。即矩陣中至少存在有。即矩陣中至少存在有一行不含加圈的一

23、行不含加圈的 0 元素。轉(zhuǎn)步驟三。元素。轉(zhuǎn)步驟三。182511054230011 45C00Step 3 尋找能覆蓋尋找能覆蓋C1中所有中所有0元素的最小直線數(shù)元素的最小直線數(shù)(1)按照從上到下、從左到右的順序?qū)Π凑諒纳系较?、從左到右的順序?qū)1沒有加沒有加圈的圈的0元行打元行打號(hào)；號(hào)；(2)對(duì)已打?qū)σ汛蛱?hào)的行中未加圈號(hào)的行中未加圈0元的列打元的列打號(hào)；號(hào)；(3)對(duì)已打?qū)σ汛蛱?hào)的列中加圈號(hào)的列中加圈0元的行打元的行打號(hào)；號(hào)；(4)重復(fù)下去，直到找不出打重復(fù)下去，直到找不出打號(hào)的行、列為止。號(hào)的行、列為止。 (5)對(duì)沒打?qū)]打號(hào)的行劃一橫線，號(hào)的行劃一橫線，對(duì)打?qū)Υ蛱?hào)的列劃一縱線，這號(hào)的列劃一縱

24、線，這就是覆蓋矩陣就是覆蓋矩陣C1中所有中所有0元元素的最小直線數(shù)素的最小直線數(shù).182511054230011 45C00 Step 4、改進(jìn)、改進(jìn)C1(1)尋找尋找 C1 沒有被直線覆蓋的沒有被直線覆蓋的所有元素中的最小元素所有元素中的最小元素；例中例中= 2。(2)在已打在已打號(hào)的行中減去號(hào)的行中減去；(3)在已打在已打號(hào)的列中加上號(hào)的列中加上；得到一個(gè)新矩陣得到一個(gè)新矩陣 C2。 182511054230011 45C00 2C -2603-292301340054300用用 C2 代替代替 C1，返回步驟，返回步驟 2。即最優(yōu)分配方案：即最優(yōu)分配方案：00100100*0001100

25、0X 206031305443000923C 確定確定C2中線性獨(dú)立的中線性獨(dú)立的0元素元素.第第7章章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃1、熟悉關(guān)于動(dòng)態(tài)規(guī)劃的一些基本概念；、熟悉關(guān)于動(dòng)態(tài)規(guī)劃的一些基本概念；2、狀態(tài)轉(zhuǎn)移方程的建立方法；、狀態(tài)轉(zhuǎn)移方程的建立方法；3、動(dòng)態(tài)規(guī)劃的解題步驟；、動(dòng)態(tài)規(guī)劃的解題步驟；4、動(dòng)態(tài)規(guī)劃的求解方法動(dòng)態(tài)規(guī)劃的求解方法（確定型、逆序法，（確定型、逆序法，P169例例7-3之類）；之類）；第第8 8章章 圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò)圖的基本概念圖的基本概念樹和圖的最小支撐樹樹和圖的最小支撐樹最短路問題最短路問題網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題最小費(fèi)用最大流問題最小費(fèi)用最大流問題概念概念定義（前向弧和

26、后向?。┒x（前向弧和后向?。?在任意一頂點(diǎn)之在任意一頂點(diǎn)之處，凡離開處，凡離開vi的有向弧稱為的有向弧稱為vi的前向弧，凡的前向弧，凡進(jìn)入進(jìn)入vi的有向弧稱為的有向弧稱為vi的后向弧。的后向弧。稱有向弧稱有向弧a為為vi點(diǎn)的前向弧，點(diǎn)的前向弧， vj點(diǎn)的后向弧。點(diǎn)的后向弧。v0vnv2v1定義（道路或通路）定義（道路或通路）在任意一網(wǎng)絡(luò)中，凡從在任意一網(wǎng)絡(luò)中，凡從始點(diǎn)始點(diǎn)v0（發(fā)點(diǎn)）開始到終點(diǎn)（發(fā)點(diǎn)）開始到終點(diǎn)vn（收點(diǎn)）結(jié)束（收點(diǎn)）結(jié)束的一系列前向弧集合稱為道路。的一系列前向弧集合稱為道路。如果如果N表示某網(wǎng)絡(luò)中所有點(diǎn)的集合，將表示某網(wǎng)絡(luò)中所有點(diǎn)的集合，將N分成兩分成兩個(gè)子集個(gè)子集A與與A

27、，使得，使得發(fā)點(diǎn)發(fā)點(diǎn)v0在在A內(nèi)，收點(diǎn)內(nèi)，收點(diǎn)vn在在A 內(nèi)內(nèi)，則稱（則稱（A，A）為分離發(fā)點(diǎn)與收點(diǎn)的截集。）為分離發(fā)點(diǎn)與收點(diǎn)的截集。截集定義截集定義從從 A 中各頂點(diǎn)到中各頂點(diǎn)到 A中各頂點(diǎn)中各頂點(diǎn)全部容量之和全部容量之和稱稱為截集的容量（截量）。為截集的容量（截量）。截集的容量截集的容量v0vnv2v1a截集截集a a：v0v1，v0v2，v0vn截量截量: Ca=C01+C02+C0nv0vnv2v1截集截集v1vn，v2vn，v0vn截量截量: Cb=C1n+C2n+C0nv0vnv2v1dSS在截集在截集d中邊中邊v1v2是反向的，其容量視為零。是反向的，其容量視為零。截集截集：v0

28、v1，v1v2，v2v1，v2vn，v0vn截量：截量： Cd=C01+C21+ C2n+ C0n在將網(wǎng)絡(luò)分成發(fā)集與收集的所在將網(wǎng)絡(luò)分成發(fā)集與收集的所有分法中，容量最小的截集稱有分法中，容量最小的截集稱為最小截集。為最小截集。I如果鏈如果鏈滿足以下條件：滿足以下條件：（1）在?。ǎ┰诨。╲i,vj）+上，有上，有0fijcij， 即即+中的每一條弧是中的每一條弧是非飽和弧。非飽和弧。（2）在?。ǎ┰诨。╲i,vj）-上，有上，有0fij cij， 即即-中的每一條弧中的每一條弧是非零流弧是非零流弧。I則稱這樣的鏈為則稱這樣的鏈為增廣鏈增廣鏈 。增廣鏈增廣鏈練習(xí)題練習(xí)題K1、最早運(yùn)用運(yùn)籌學(xué)理論的

29、是（、最早運(yùn)用運(yùn)籌學(xué)理論的是（ ）KA 二次世界大戰(zhàn)期間，英國軍事部門將運(yùn)二次世界大戰(zhàn)期間，英國軍事部門將運(yùn)籌學(xué)運(yùn)用到軍事戰(zhàn)略部署；籌學(xué)運(yùn)用到軍事戰(zhàn)略部署；KB 美國最早將運(yùn)籌學(xué)運(yùn)用到農(nóng)業(yè)和人口規(guī)美國最早將運(yùn)籌學(xué)運(yùn)用到農(nóng)業(yè)和人口規(guī)劃問題上；劃問題上；KC 二次世界大戰(zhàn)期間，英國政府將運(yùn)籌學(xué)二次世界大戰(zhàn)期間，英國政府將運(yùn)籌學(xué)運(yùn)用到政府制定計(jì)劃；運(yùn)用到政府制定計(jì)劃；KD 50年代，運(yùn)籌學(xué)運(yùn)用到研究人口，能源，年代，運(yùn)籌學(xué)運(yùn)用到研究人口，能源，糧食，第三世界經(jīng)濟(jì)發(fā)展等問題上。糧食，第三世界經(jīng)濟(jì)發(fā)展等問題上。單項(xiàng)選擇題單項(xiàng)選擇題 K2、在產(chǎn)銷平衡運(yùn)輸問題中，設(shè)產(chǎn)地為個(gè)，在產(chǎn)銷平衡運(yùn)輸問題中，設(shè)產(chǎn)地為個(gè)

30、，銷地為個(gè)，那么基可行解中非零變量的個(gè)銷地為個(gè)，那么基可行解中非零變量的個(gè)數(shù)（數(shù)（ ）KA. 不能大于不能大于(m+n-1)； KB. 不能小于不能小于(m+n-1)； KC. 等于等于(m+n-1)；K D. 不確定。不確定。K3、在求解運(yùn)輸問題的過程中運(yùn)用到下列哪、在求解運(yùn)輸問題的過程中運(yùn)用到下列哪些方法（些方法（ ）KA 最小元素法最小元素法KB 位勢(shì)法位勢(shì)法KC 閉回路法閉回路法KD 伏格爾法伏格爾法KE 以上都是以上都是53 圖解法同單純形法雖然求解的形式不同，圖解法同單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。但從幾何上理解，兩者是一致的。 LP模型中增加一個(gè)約束條件

31、，可行域的范模型中增加一個(gè)約束條件，可行域的范圍一般將縮小，減少一個(gè)約束條件，可行圍一般將縮小，減少一個(gè)約束條件，可行域的范圍一般將擴(kuò)大。域的范圍一般將擴(kuò)大。 LP問題的每一個(gè)基解對(duì)應(yīng)可行域的一個(gè)頂問題的每一個(gè)基解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)。點(diǎn)。 如如LP問題存在最優(yōu)解，則最優(yōu)解一定對(duì)應(yīng)問題存在最優(yōu)解，則最優(yōu)解一定對(duì)應(yīng)可行域邊界上的一個(gè)點(diǎn)?？尚杏蜻吔缟系囊粋€(gè)點(diǎn)。 判斷下列說法是否正確判斷下列說法是否正確546. 任何任何LP問題存在并具有唯一的對(duì)偶問題。問題存在并具有唯一的對(duì)偶問題。 7. 對(duì)偶問題的對(duì)偶問題一定是原問題。對(duì)偶問題的對(duì)偶問題一定是原問題。8. 根據(jù)對(duì)偶問題的性質(zhì)，當(dāng)原問題為無界解根據(jù)

32、對(duì)偶問題的性質(zhì)，當(dāng)原問題為無界解時(shí)，其對(duì)偶問題無可行解，反之，當(dāng)對(duì)偶時(shí)，其對(duì)偶問題無可行解，反之，當(dāng)對(duì)偶問題無可行解問題無可行解時(shí)，其原問題具有無界解。時(shí)，其原問題具有無界解。5. 線性規(guī)劃問題的可行解如為最優(yōu)解，則線性規(guī)劃問題的可行解如為最優(yōu)解，則該可行解一定是基可行解；該可行解一定是基可行解；因?yàn)榛尚薪庖驗(yàn)榛尚薪饪尚薪??？尚薪狻?.運(yùn)輸問題數(shù)學(xué)模型的（運(yùn)輸問題數(shù)學(xué)模型的（m+n）個(gè)約束中）個(gè)約束中 最多只有（最多只有（m+n-1）個(gè)是獨(dú)立的。）個(gè)是獨(dú)立的。K10.產(chǎn)銷平衡的運(yùn)輸問題解的情況有四種：無可產(chǎn)銷平衡的運(yùn)輸問題解的情況有四種：無可行解；無界解；唯一最優(yōu)解；無窮多最優(yōu)解。行解；無

33、界解；唯一最優(yōu)解；無窮多最優(yōu)解。錯(cuò)錯(cuò) P102K11.運(yùn)輸問題的所有結(jié)構(gòu)約束條件都是等式約束。運(yùn)輸問題的所有結(jié)構(gòu)約束條件都是等式約束。對(duì)對(duì)填空題填空題 K1 1、用大、用大M法求解法求解Max型線性規(guī)劃時(shí)，人工型線性規(guī)劃時(shí)，人工變量在目標(biāo)中的系數(shù)均為變量在目標(biāo)中的系數(shù)均為 , ,若最優(yōu)解若最優(yōu)解的的 中含有人工變量，則原問題無中含有人工變量，則原問題無可行解?？尚薪?。（-M）基變量基變量K2、若某種資源的影子價(jià)格為零，則表明該種、若某種資源的影子價(jià)格為零，則表明該種資源資源 （應(yīng)該或不應(yīng)該）被買進(jìn)；又當(dāng)資（應(yīng)該或不應(yīng)該）被買進(jìn)；又當(dāng)資源的影子價(jià)格不為零時(shí)，說明該種資源消耗源的影子價(jià)格不為零時(shí)，

34、說明該種資源消耗 （完畢或剩余）（完畢或剩余）不應(yīng)該不應(yīng)該 完畢完畢K3、線性規(guī)劃原問題中的變量個(gè)數(shù)與其對(duì)偶問、線性規(guī)劃原問題中的變量個(gè)數(shù)與其對(duì)偶問題中的題中的 個(gè)數(shù)相等。因此，當(dāng)原問題增個(gè)數(shù)相等。因此，當(dāng)原問題增加一個(gè)變量時(shí)，對(duì)偶問題就增加一個(gè)加一個(gè)變量時(shí)，對(duì)偶問題就增加一個(gè) ，從而對(duì)偶可行域?qū)⒖赡茏儚亩鴮?duì)偶可行域?qū)⒖赡茏?(小還是大小還是大)。小小約束條件約束條件 約束條件約束條件K4、用表上作業(yè)法求解、用表上作業(yè)法求解m個(gè)產(chǎn)地個(gè)產(chǎn)地n個(gè)銷地的平衡運(yùn)個(gè)銷地的平衡運(yùn)輸問題，其方案表上數(shù)字格的個(gè)數(shù)為輸問題，其方案表上數(shù)字格的個(gè)數(shù)為 個(gè)；個(gè)；m+n-1K建立線性規(guī)劃模型（利潤最大或者成本最?。┙?/p>

35、立線性規(guī)劃模型（利潤最大或者成本最?。㎏線性規(guī)劃化為標(biāo)準(zhǔn)型線性規(guī)劃化為標(biāo)準(zhǔn)型K寫出問題的對(duì)偶規(guī)劃寫出問題的對(duì)偶規(guī)劃建立模型建立模型某人每天食用甲、乙兩種食物（如豬肉、雞蛋），某人每天食用甲、乙兩種食物（如豬肉、雞蛋），如表。問兩種食物各食用如表。問兩種食物各食用多少，才能既滿足需要、多少，才能既滿足需要、又使總費(fèi)用最??？又使總費(fèi)用最??？設(shè)：設(shè)：X1 、X2 表示甲、乙表示甲、乙種食物的用量。種食物的用量。 2 1.5原料單價(jià)原料單價(jià)1.007.5010.00 0.1 0.15 1.7 0.75 1.10 1.30A1A2A3 最最 低低需要量需要量 含含 食物食物 量量成分成分0,00.1030.110.150.775.070.100.115.010.05.12min2121212121xxxxxxxxxxZ甲甲 乙乙cj1018000cBxBbx1x2x3x4x50 x3170521000 x4100230100 x515015001-Z01018000cj1018000cBxBbx1x2x3x4x50 x3540/7001-23/711/710 x150/71005/7-3/718x2200/7010