離散優(yōu)化數(shù)學(xué)建模

離散優(yōu)化數(shù)學(xué)建模第1頁，課件共102頁，創(chuàng)作于2023年2月2008年B題高等教育學(xué)費(fèi)標(biāo)準(zhǔn)探討請你們根據(jù)中國國情，收集諸如國家生均撥款、培養(yǎng)費(fèi)用、家庭收入等相關(guān)數(shù)據(jù)，并據(jù)此通過數(shù)學(xué)建模的方法，就幾類學(xué)?；?qū)I(yè)的學(xué)費(fèi)標(biāo)準(zhǔn)進(jìn)行定量分析，得出明確、有說服力的結(jié)論。數(shù)據(jù)的收集和分析是你們建模分析的基礎(chǔ)和重要組成部分。你們的論文必須觀點(diǎn)鮮明、分析有據(jù)、結(jié)論明確。最后，根據(jù)你們建模分析的結(jié)果，給有關(guān)部門寫一份報(bào)告，提出具體建議。第2頁，課件共102頁，創(chuàng)作于2023年2月

3.試題向大規(guī)模數(shù)據(jù)處理方向發(fā)展:從05年開始，基本上每年都有一大數(shù)據(jù)量的賽題；數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性：數(shù)據(jù)的真實(shí)性，數(shù)據(jù)的海量性，數(shù)據(jù)的不完備性，數(shù)據(jù)的冗余性4.求解算法和各類現(xiàn)代算法的融合；如：11B

5.實(shí)用性：問題和數(shù)據(jù)來自于實(shí)際，解決方法切合于實(shí)際，模型和結(jié)果可以應(yīng)用于實(shí)際。6.即時(shí)性：國內(nèi)外的大事，社會的熱點(diǎn)，生活的焦點(diǎn)，近期發(fā)生和即將發(fā)生被關(guān)注的問題。第3頁，課件共102頁，創(chuàng)作于2023年2月拿到賽題后大家需要思考的問題題目屬于哪種類型：連續(xù)的、離散的需要解決什么問題:最優(yōu)化方案、預(yù)測模型、最短路徑等等；將問題分解?？梢杂媚男┫嚓P(guān)模型、算法求解、需要什么數(shù)學(xué)工具。第4頁，課件共102頁，創(chuàng)作于2023年2月1、數(shù)學(xué)建模的過程(2)整個數(shù)學(xué)建模過程應(yīng)當(dāng)由三個階段：

1.建立模型：實(shí)際問題→數(shù)學(xué)問題；2.數(shù)學(xué)解答：數(shù)學(xué)問題→數(shù)學(xué)解；3.模型檢驗(yàn)：數(shù)學(xué)解→實(shí)際問題的解決。(1)流程圖模型應(yīng)用問題分析模型假設(shè)建立模型模型求解模型分析模型檢驗(yàn)第5頁，課件共102頁，創(chuàng)作于2023年2月解決問題涉及到的計(jì)算軟件分析重要的是參賽選手具備編程計(jì)算、計(jì)算機(jī)仿真、模擬能力。賽題常用的計(jì)算軟件：Matlab,SPSS，EXCEL等第6頁，課件共102頁，創(chuàng)作于2023年2月參考網(wǎng)站[1]全國大學(xué)生數(shù)學(xué)建模競賽網(wǎng)：[2]數(shù)學(xué)中國網(wǎng)站

[3]中國數(shù)學(xué)建模網(wǎng)站：

第7頁，課件共102頁，創(chuàng)作于2023年2月

從問題的解決方法上分析

涉及到的數(shù)學(xué)建模方法：

幾何理論、組合概率、統(tǒng)計(jì)(回歸)分析;優(yōu)化方法（規(guī)劃）、圖論與網(wǎng)絡(luò)優(yōu)化、層次分析;差分方法、微分方程、模糊數(shù)學(xué)、隨機(jī)決策、多目標(biāo)決策;插值與擬合、灰色系統(tǒng)理論、神經(jīng)網(wǎng)絡(luò)、時(shí)間序列;綜合評價(jià)、機(jī)理分析等方法;第8頁，課件共102頁，創(chuàng)作于2023年2月

用的最多的方法是優(yōu)化方法和概率統(tǒng)計(jì)用到優(yōu)化方法的共有26個題，其中整數(shù)規(guī)劃4個，線性規(guī)劃7個，非線性規(guī)劃14個,多目標(biāo)規(guī)劃6個。

用到概率統(tǒng)計(jì)方法的有21個題，平均每年至少有一個題目用到概率統(tǒng)計(jì)的方法。

用到圖論與網(wǎng)絡(luò)優(yōu)化方法的問題有6個；用到層次分析方法的問題有３個；第9頁，課件共102頁，創(chuàng)作于2023年2月

用到插值擬合的問題有6個；

用灰色系統(tǒng)理論的4個;

用到時(shí)間序列分析的至少2個;

用到綜合評價(jià)方法的至少3個；

大部分題目都可以用兩種以上的方法來解決,即綜合性較強(qiáng)的題目有26個第10頁，課件共102頁，創(chuàng)作于2023年2月最優(yōu)化概論從數(shù)學(xué)意義上說，最優(yōu)化方法是一種求極值的方法，即在一組約束為等式或不等式的條件下，使系統(tǒng)的目標(biāo)函數(shù)達(dá)到極值，即最大值或最小值。從經(jīng)濟(jì)意義上說，是在一定的人力、物力和財(cái)力資源條件下，使經(jīng)濟(jì)效果達(dá)到最大（如產(chǎn)值、利潤），或者在完成規(guī)定的生產(chǎn)或經(jīng)濟(jì)任務(wù)下，使投入的人力、物力和財(cái)力等資源為最少。第11頁，課件共102頁，創(chuàng)作于2023年2月一、最優(yōu)化概念所有類似的這種課題統(tǒng)稱為最優(yōu)化問題，研究解決這些問題的科學(xué)一般就總稱之為最優(yōu)化理論和方法另外也可用學(xué)術(shù)味更濃的名稱：“運(yùn)籌學(xué)”。由于最優(yōu)化問題背景十分廣泛，涉及的知識不盡相同，學(xué)科分枝很多，因此這個學(xué)科名下到底包含哪些分枝，其說法也不一致。比較公認(rèn)的是：“規(guī)劃論”（包括線性和非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、多目標(biāo)規(guī)劃和隨機(jī)規(guī)劃等），“組合最優(yōu)化”，“對策論”及“最優(yōu)控制”等等。第12頁，課件共102頁，創(chuàng)作于2023年2月數(shù)學(xué)建模競賽中的優(yōu)化問題2000B鋼管訂購和運(yùn)輸問題—組合優(yōu)化2001B公交車優(yōu)化調(diào)度—圖論2002B彩票中的數(shù)學(xué)—決策分析2003B露天礦生產(chǎn)的車輛安排問題—離散優(yōu)化2004A奧運(yùn)會臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)問題—圖論2005BDVD在線租賃—離散優(yōu)化2006A出版社的資源配置問題—決策分析第13頁，課件共102頁，創(chuàng)作于2023年2月07B乘公交，看奧運(yùn)—圖論整數(shù)規(guī)劃08B高等教育學(xué)費(fèi)探討—層次分析法多目標(biāo)優(yōu)化09B眼科病床的合理安排—動態(tài)規(guī)劃10B上海世博會經(jīng)濟(jì)影響力定量評估—決策分析11B交巡警服務(wù)平臺的設(shè)置與調(diào)度—圖論多目標(biāo)規(guī)劃12B太陽能小屋的設(shè)計(jì)—離散優(yōu)化13A

車道被占用對城市道路通行能力的影響

—離散優(yōu)化第14頁，課件共102頁，創(chuàng)作于2023年2月從數(shù)學(xué)上來看，所謂最優(yōu)化問題可以概括為這樣一種數(shù)學(xué)模型：給定一個“函數(shù)”，F(xiàn)(X)，以及“自變量”X應(yīng)滿足的一定條件，求X為怎樣的值時(shí)，F(xiàn)(X)取得其最大值或最小值。通常，稱F(X)為“目標(biāo)函數(shù)”，X應(yīng)滿足的條件為“約束條件”。約束條件一般用一個集合D表示為：X∈D。求目標(biāo)函數(shù)F(X)在約束條件X∈D下的最小值或最大值問題，就是一般最優(yōu)問題的數(shù)學(xué)模型．第15頁，課件共102頁，創(chuàng)作于2023年2月無約束最優(yōu)化問題目標(biāo)函數(shù)二、最優(yōu)化問題的一般形式約束最優(yōu)化問題約束函數(shù)最優(yōu)解；最優(yōu)值第16頁，課件共102頁，創(chuàng)作于2023年2月三、最優(yōu)化問題分類分類1：無約束最優(yōu)化約束最優(yōu)化

非線性規(guī)劃：目標(biāo)函數(shù)與約束函數(shù)中至少有一個是變量x的非線性函數(shù)；

線性規(guī)劃：目標(biāo)函數(shù)與約束函數(shù)均為線性函數(shù)；分類2：線性規(guī)劃非線性規(guī)劃第17頁，課件共102頁，創(chuàng)作于2023年2月三、最優(yōu)化問題分類分類3（根據(jù)決策變量、目標(biāo)函數(shù)和要求不同）整數(shù)規(guī)劃動態(tài)規(guī)劃網(wǎng)絡(luò)規(guī)劃隨機(jī)規(guī)劃多目標(biāo)規(guī)劃第18頁，課件共102頁，創(chuàng)作于2023年2月三、最優(yōu)化問題分類函數(shù)最優(yōu)化組合最優(yōu)化分類４函數(shù)最優(yōu)化：決策變量是一定區(qū)間內(nèi)的連續(xù)變量．組合最優(yōu)化：決策變量是離散狀態(tài)，同時(shí)可行域是由有限個點(diǎn)組成的集合第19頁，課件共102頁，創(chuàng)作于2023年2月最優(yōu)化方法解決問題的步驟（1）確定變量，寫出目標(biāo)函數(shù)和有關(guān)約束條件，建立數(shù)學(xué)模型。（2）分析模型，搞清它屬于運(yùn)籌學(xué)哪一分枝，選擇合適的最優(yōu)化方法；（3）編程求解；盡量利用現(xiàn)有的數(shù)學(xué)軟件或最優(yōu)化軟件，比如Matlab，Mathematica，Lindo，Lingo等，來計(jì)算。（4）最優(yōu)解的驗(yàn)證和實(shí)施。第20頁，課件共102頁，創(chuàng)作于2023年2月Chapter1線性規(guī)劃

(LinearProgramming)LP的數(shù)學(xué)模型LP模型的應(yīng)用本章主要內(nèi)容：第21頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型1.規(guī)劃問題生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題：（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤最大.）第22頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型例1某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)總的利潤最大？設(shè)備產(chǎn)品ABCD利潤（元）甲21402乙22043有效臺時(shí)1281612第23頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12第24頁，課件共102頁，創(chuàng)作于2023年2月

這是一個典型的利潤最大化的生產(chǎn)計(jì)劃問題。其中，“Max”是英文單詞“Maximize”的縮寫，含義為“最大化”；“s.t.”是“subjectto”的縮寫，表示“滿足于…”。因此，上述模型的含義是：在給定條件限制下，求使目標(biāo)函數(shù)z

達(dá)到最大的x1,x2

的取值。第25頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型2.線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問題的目標(biāo)函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性不等式或等式。

怎樣辨別一個模型是線性規(guī)劃模型？

第26頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型目標(biāo)函數(shù)：約束條件：3.線性規(guī)劃數(shù)學(xué)模型的一般形式簡寫為：第27頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型矩陣形式：其中：第28頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型3.線性規(guī)劃問題的標(biāo)準(zhǔn)形式特點(diǎn)：(1)目標(biāo)函數(shù)求最大值。(2)約束條件都為等式方程，且右端常數(shù)項(xiàng)bi都大于或等于零(3)決策變量xj為非負(fù)。第29頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型（2）如何化標(biāo)準(zhǔn)形式目標(biāo)函數(shù)的轉(zhuǎn)換如果是求極小值即，則可將目標(biāo)函數(shù)乘以(-1)，可化為求極大值問題。也就是：令，可得到上式。即

若存在取值無約束的變量,可令其中：變量的變換第30頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。稱為松弛變量稱為剩余變量變量的變換可令第31頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型4.線性規(guī)劃問題的解線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組中找出一個解，使目標(biāo)函數(shù)(1)達(dá)到最大值。第32頁，課件共102頁，創(chuàng)作于2023年2月線性規(guī)劃問題的數(shù)學(xué)模型

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域。

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。線性規(guī)劃解的情況：有唯一最優(yōu)解；有無窮多最優(yōu)解；無界解；無可行解

第33頁，課件共102頁，創(chuàng)作于2023年2月

建立線性規(guī)劃模型的過程可以分為四個步驟：(1)設(shè)立決策變量；(2)明確所有的約束條件并用決策變量的線性等式或不等式表示出來；(3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極小（Min）；(4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。求解方法：用MATLAB軟件直接求解。第34頁，課件共102頁，創(chuàng)作于2023年2月Chapter2運(yùn)輸問題

(TransportationProblem)運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸問題的應(yīng)用本章主要內(nèi)容：第35頁，課件共102頁，創(chuàng)作于2023年2月1.運(yùn)輸問題模型及有關(guān)概念問題的提出一般的運(yùn)輸問題就是要解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運(yùn)到若干個銷地，在每個產(chǎn)地的供應(yīng)量與每個銷地的需求量已知，并知道各地之間的運(yùn)輸單價(jià)的前提下，如何確定一個使得總的運(yùn)輸費(fèi)用最小的方案。第36頁，課件共102頁，創(chuàng)作于2023年2月運(yùn)輸問題的數(shù)學(xué)模型例2.1某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1,B2,B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？B1B2B3產(chǎn)量A1646200A2655300銷量150150200第37頁，課件共102頁，創(chuàng)作于2023年2月運(yùn)輸問題的數(shù)學(xué)模型解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量＝500

設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）第38頁，課件共102頁，創(chuàng)作于2023年2月運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸問題的一般形式：產(chǎn)銷平衡A1、A2、…、Am表示某物資的m個產(chǎn)地；B1、B2、…、Bn表示某物質(zhì)的n個銷地；ai表示產(chǎn)地Ai的產(chǎn)量；bj表示銷地Bj的銷量；cij表示把物資從產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)。設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列一般運(yùn)輸量問題的模型：第39頁，課件共102頁，創(chuàng)作于2023年2月運(yùn)輸問題的數(shù)學(xué)模型變化：1）有時(shí)目標(biāo)函數(shù)為求最大值。如求利潤最大或營業(yè)額最大；2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)，在模型中直接加入約束條件（等式或不等式約束)；3）產(chǎn)銷不平衡時(shí)，可加入假想的產(chǎn)地（銷大于產(chǎn)時(shí)）或銷地（產(chǎn)大于銷時(shí)）。第40頁，課件共102頁，創(chuàng)作于2023年2月運(yùn)輸問題的應(yīng)用產(chǎn)銷不平衡的運(yùn)輸問題 當(dāng)總產(chǎn)量與總銷量不相等時(shí),稱為不平衡運(yùn)輸問題.這類運(yùn)輸問題在實(shí)際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。當(dāng)產(chǎn)大于銷時(shí)，即：數(shù)學(xué)模型為：第41頁，課件共102頁，創(chuàng)作于2023年2月運(yùn)輸問題的應(yīng)用由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，假設(shè)該倉庫為一個虛擬銷地Bn+1，bn+1作為一個虛設(shè)銷地Bn+1的銷量(即庫存量)。各產(chǎn)地Ai到Bn+1的運(yùn)價(jià)為零，即Ci,n+1=0,（i=1，…，m）。則平衡問題的數(shù)學(xué)模型為：第42頁，課件共102頁，創(chuàng)作于2023年2月運(yùn)輸問題的應(yīng)用當(dāng)銷大于產(chǎn)時(shí)，即：數(shù)學(xué)模型為：由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時(shí)虛設(shè)一個產(chǎn)地Am+1，產(chǎn)量為：第43頁，課件共102頁，創(chuàng)作于2023年2月運(yùn)輸問題的應(yīng)用銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為：具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行Am+1，運(yùn)價(jià)為零。產(chǎn)量為am+1即可。第44頁，課件共102頁，創(chuàng)作于2023年2月Chapter3整數(shù)規(guī)劃

(IntegerProgramming)整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用指配問題與匈牙利法本章主要內(nèi)容：第45頁，課件共102頁，創(chuàng)作于2023年2月引言

整數(shù)規(guī)劃是規(guī)劃論中近幾十年才發(fā)展起來的一個重要分支，主要是由于經(jīng)濟(jì)管理中的大量問題在抽象成模型時(shí)，人們發(fā)現(xiàn)許多量具有不可分割性，因此當(dāng)它們被作為變量引入到規(guī)劃中時(shí)，常要求滿足取整條件.如生產(chǎn)計(jì)劃中，生產(chǎn)機(jī)器多少臺(整數(shù))；人力資源管理中，招聘員工多少人(整數(shù))；運(yùn)輸問題中，從一個港口到另一個港口的集裝箱調(diào)運(yùn)數(shù)量(整數(shù))；另外，運(yùn)作管理中的決策問題：如工廠選址、人員的工作指派、設(shè)備購置和配置等.第46頁，課件共102頁，創(chuàng)作于2023年2月一輛車最大裝載重量為7噸，容量為12立方米。現(xiàn)有兩種物品，每種物品數(shù)量無限。各種物品每件的體積、重量、價(jià)格如下表：物品1物品2體積（立方米/件）34重量（噸/件）42價(jià)值（萬元/件）43求這輛車中裝入每種物品各多少件，使物品總價(jià)值最高。背包問題第47頁，課件共102頁，創(chuàng)作于2023年2月設(shè)三種物品的件數(shù)各為x1，x2件，總價(jià)值為zmaxz=4x1+3x2s.t.3x1+4x2≤124x1+2x2≤7x1，x2≥0，x1，x2為整數(shù)第48頁，課件共102頁，創(chuàng)作于2023年2月整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃（簡稱：IP） 要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛問題是一個線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式：第49頁，課件共102頁，創(chuàng)作于2023年2月整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃問題的種類：純整數(shù)規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)規(guī)劃?；旌险麛?shù)規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)規(guī)劃。0-1型整數(shù)規(guī)劃：決策變量只能取值0或1的整數(shù)規(guī)劃。第50頁，課件共102頁，創(chuàng)作于2023年2月整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃問題解的特征：整數(shù)規(guī)劃問題的可行解集合是它松弛問題可行解集合的一個子集，任意兩個可行解的凸組合不一定滿足整數(shù)約束條件，因而不一定仍為可行解。整數(shù)規(guī)劃問題的可行解一定是它的松弛問題的可行解（反之不一定），但其最優(yōu)解的目標(biāo)函數(shù)值不會優(yōu)于后者最優(yōu)解的目標(biāo)函數(shù)值。第51頁，課件共102頁，創(chuàng)作于2023年2月0-1整數(shù)規(guī)劃

0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量僅取值0或者1，我們通常稱為0-1變量或邏輯變量.在實(shí)踐中，許多問題只回答是或否.例如，對某個項(xiàng)目是否投資，對某個應(yīng)聘者是否聘用，對某種新產(chǎn)品是否研發(fā)等，這類問題都可以用0-1變量來描繪.第52頁，課件共102頁，創(chuàng)作于2023年2月整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃問題的求解方法：分支定界法和割平面法匈牙利法（指派問題）求解整數(shù)規(guī)劃模型的數(shù)學(xué)軟件有：Lindo,Lingo和Matlab,其中Lindo和Lingo是專業(yè)的優(yōu)化軟件.第53頁，課件共102頁，創(chuàng)作于2023年2月指派問題AssignmentProblem

在生活中經(jīng)常遇到這樣的問題，某單位需完成n項(xiàng)任務(wù)，恰好有n個人可以承擔(dān)這些任務(wù).一項(xiàng)任務(wù)只能由一個人完成，一個人只能完成一項(xiàng)任務(wù)。由于每人的專長不同，每個人完成各項(xiàng)任務(wù)的效率不同.于是產(chǎn)生應(yīng)指派哪個人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高(或所需總時(shí)間最小，費(fèi)用最低）。第54頁，課件共102頁，創(chuàng)作于2023年2月指派問題指派問題的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式： 設(shè)n個人被分配去做n件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j件工作的時(shí)間或費(fèi)用為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問應(yīng)如何分配才能使總效率最高？設(shè)決策變量第55頁，課件共102頁，創(chuàng)作于2023年2月指派問題的數(shù)學(xué)模型為：第56頁，課件共102頁，創(chuàng)作于2023年2月整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用例2指派問題：人事部門欲安排四人到四個不同崗位工作，每個崗位一個人。經(jīng)考核四人在不同崗位的成績（百分制）如表所示，如何安排他們的工作使總成績最好。工作人員ABCD甲85927390乙95877895丙82837990丁86908088第57頁，課件共102頁，創(chuàng)作于2023年2月整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用設(shè)數(shù)學(xué)模型如下：要求每人做一項(xiàng)工作，約束條件為：第58頁，課件共102頁，創(chuàng)作于2023年2月整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用每項(xiàng)工作只能安排一人，約束條件為：變量約束：對于指派問題等0-1整數(shù)規(guī)劃問題，可以直接利用Matlab的函數(shù)bintprog進(jìn)行求解。第59頁，課件共102頁，創(chuàng)作于2023年2月多目標(biāo)規(guī)劃模型

在許多實(shí)際問題中，衡量一個方案的好壞標(biāo)準(zhǔn)往往不止一個，例如設(shè)計(jì)一個導(dǎo)彈，既要射程最遠(yuǎn)，又要燃料最省，還要精度最高.這一類問題統(tǒng)稱為多目標(biāo)最優(yōu)化問題或多目標(biāo)規(guī)劃問題.我們先來看一個生產(chǎn)計(jì)劃的例子.第60頁，課件共102頁，創(chuàng)作于2023年2月第61頁，課件共102頁，創(chuàng)作于2023年2月第62頁，課件共102頁，創(chuàng)作于2023年2月第63頁，課件共102頁，創(chuàng)作于2023年2月第64頁，課件共102頁，創(chuàng)作于2023年2月第65頁，課件共102頁，創(chuàng)作于2023年2月第66頁，課件共102頁，創(chuàng)作于2023年2月第67頁，課件共102頁，創(chuàng)作于2023年2月第68頁，課件共102頁，創(chuàng)作于2023年2月第69頁，課件共102頁，創(chuàng)作于2023年2月Chapter4圖與網(wǎng)絡(luò)分析

(GraphTheoryandNetworkAnalysis)圖的基本概念與模型樹與圖的最小樹最短路問題網(wǎng)絡(luò)的最大流本章主要內(nèi)容：第70頁，課件共102頁，創(chuàng)作于2023年2月近代圖論的歷史可追溯到18世紀(jì)的七橋問題—穿過K?nigsberg城的七座橋，要求每座橋通過一次且僅通過一次。這就是著名的“哥尼斯堡7橋”難題。Euler1736年證明了不可能存在這樣的路線。圖的基本概念與模型K?nigsberg橋?qū)?yīng)的圖第71頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對象之間的關(guān)系。一般情況下圖中點(diǎn)的相對位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的。圖的定義： 若用點(diǎn)表示研究的對象，用邊表示這些對象之間的聯(lián)系，則圖G可以定義為點(diǎn)和邊的集合，記作：其中:V——點(diǎn)集E——邊集※圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個點(diǎn)以及哪些點(diǎn)之間有連線。第72頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個人群中，對相互認(rèn)識這個關(guān)系我們可以用圖來表示。第73頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型定義:圖中的點(diǎn)用v表示，邊用e表示。對每條邊可用它所連接的點(diǎn)表示，記作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5端點(diǎn),關(guān)聯(lián)邊,相鄰若有邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。第74頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型環(huán),多重邊,簡單圖如果邊e的兩個端點(diǎn)相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個點(diǎn)之間多于一條，稱為多重邊，如右圖中的e4和e5，對無環(huán)、無多重邊的圖稱作簡單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5第75頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)與某一個點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的次（也叫做度），記作d(vi)。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱作偶點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次:一個圖的次等于各點(diǎn)的次之和。第76頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型鏈，圈，連通圖圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對任意vi,t-1和vit均相鄰稱為鏈。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起點(diǎn)與終點(diǎn)重合的鏈稱作圈。如果每一對頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱圖不連通。第77頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型二部圖（偶圖）圖G=(V,E)的點(diǎn)集V可以分為兩各非空子集X，Y，集X∪Y=V,X∩Y=?,使得同一集合中任意兩個頂點(diǎn)均不相鄰，稱這樣的圖為偶圖。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明顯為二部圖，(b)也是二部圖，但不明顯，改畫為(c)時(shí)可以清楚看出。第78頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型子圖，部分圖(支撐子圖)圖G1={V1、E1}和圖G2={V2，E2}如果有稱G1是G2的一個子圖。若有，則稱G1是G2的一個部分圖(支撐子圖)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G圖）第79頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型網(wǎng)絡(luò)（賦權(quán)圖）設(shè)圖G＝（V，E），對G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán),賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費(fèi)用、通過能力(容量)等等。端點(diǎn)無序的賦權(quán)圖稱為無向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。①②③④⑤⑥910201571419256第80頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型出次與入次有向圖中，以vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次，用d+(vi)表示；以vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi的入次，用表示d-(vi)；vi點(diǎn)的出次和入次之和就是該點(diǎn)的次。※有向圖中，所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。第81頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型圖的模型應(yīng)用例6.1有甲,乙,丙,丁,戊,己6名運(yùn)動員報(bào)名參加A,B,C,D,E,F6個項(xiàng)目的比賽。下表中打√的是各運(yùn)動員報(bào)告參加的比賽項(xiàng)目。問6個項(xiàng)目的比賽順序應(yīng)如何安排，做到每名運(yùn)動員都不連續(xù)地參加兩項(xiàng)比賽。ABCDEF甲√√乙√√√丙√√丁√√戊√√√己√√√第82頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型解：用圖來建模。把比賽項(xiàng)目作為研究對象，用點(diǎn)表示。如果2個項(xiàng)目有同一名運(yùn)動員參加，在代表這兩個項(xiàng)目的點(diǎn)之間連一條線，可得下圖。ABCDEF在圖中找到一個點(diǎn)序列，使得依次排列的兩點(diǎn)不相鄰，即能滿足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A第83頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型圖的矩陣描述：如何在計(jì)算機(jī)中存儲一個圖呢？現(xiàn)在已有很多存儲的方法，但最基本的方法就是采用矩陣來表示一個圖，圖的矩陣表示也根據(jù)所關(guān)心的問題不同而有：鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。1.鄰接矩陣 對于圖G=（V，E），|V|=n，|E|=m，有n

n階方矩陣A=(aij)n

n，其中第84頁，課件共102頁，創(chuàng)作于2023年2月圖的基本概念與模型v5v1v2v3v4v64332256437例6.2下圖所表示的圖可以構(gòu)造鄰接矩陣A如下第85頁，課件共102頁，創(chuàng)作于2023年2月對于賦權(quán)圖G=(V,E),其中邊有權(quán),構(gòu)造矩陣B=(bij)n

n

其中：圖的基本概念與模型2.關(guān)聯(lián)矩陣對于圖G=(V,E),|V|=n,|E|=m,有m

n階矩陣M=(mij)m

n，其中:3.權(quán)矩陣第86頁，課件共102頁，創(chuàng)作于2023年2月樹與圖的最小樹樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖。在自然和社會領(lǐng)域應(yīng)用極為廣泛。例6.2乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。ABCDEFGH運(yùn)動員第87頁，課件共102頁，創(chuàng)作于2023年2月樹與圖的最小樹例6.3某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。廠長人事科財(cái)務(wù)科總工程師生產(chǎn)副廠長經(jīng)營副廠長開發(fā)科技術(shù)科生產(chǎn)科設(shè)備科供應(yīng)科銷售科檢驗(yàn)科動力科第88頁，課件共102頁，創(chuàng)作于2023年2月樹與圖的最小樹樹：無圈的連通圖即為樹性質(zhì)1：任何樹中必存在次為1的點(diǎn)。性質(zhì)2：n個頂點(diǎn)的樹必有n-1條邊。性質(zhì)3：樹中任意兩個頂點(diǎn)之間，恰有且僅有一條鏈。性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)5：樹無回圈，但不相鄰的兩個點(diǎn)之間加一條邊，恰得到一個圈。v1v2v3v4v5v6第89頁，課件共102頁，創(chuàng)作于2023年2月最短路問題問題描述： 就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路.

有些問題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。第90頁，課件共102頁，創(chuàng)作于2023年2月最短路問題求最短路有兩種算法:狄克斯屈拉(Dijkstra)標(biāo)號算法逐次逼近算法第91頁，課件共102頁，創(chuàng)作于2023年2月最短路問題狄克斯屈拉(Dijkstra)標(biāo)號算法的基本思路：若序列{vs,v1…..vn-1,vn}是從vs到vt間的最短路，則序列{vs,v1…..vn-1}必為從vs到vn-1的最短路。 假定v1→v2→v3→v4是v1→v4的最短路，則v1→v2→v3一定是v1→v3的最短路，v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v5第92頁，課件共102頁，創(chuàng)作于2023年2月最短路問題求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點(diǎn)是vs,終點(diǎn)是vt,以vi為起點(diǎn)vj為終點(diǎn)的弧記為(i,j)

距離為dijP標(biāo)號(點(diǎn)標(biāo)號)：b(j)—起點(diǎn)vs到點(diǎn)vj的最短路長；T標(biāo)號(邊標(biāo)號)：k(i,j)=b(i)+dij，步驟：1.令起點(diǎn)的標(biāo)號；b(s)＝0。2.找出所有vi已標(biāo)號vj未標(biāo)號的弧集合B={(i,j)}如果這樣的弧不存在或vt已標(biāo)號則計(jì)算結(jié)束；3.計(jì)算集合B中弧k(i，j)=b(i)+dij的標(biāo)號4.選一個點(diǎn)標(biāo)號在終點(diǎn)vl處標(biāo)號b(l),返回到第2步。第93頁，課件共102頁，創(chuàng)作于2023年2月最短路問題例6.5求下圖v1到v7的最短路長及最短路線①②③④⑤⑥⑦86252353421057086225441114751071211v7已標(biāo)號，計(jì)算結(jié)束。從v1到v7的最短路長是11,最短路線：v1→v4→v6

→v7P標(biāo)號T標(biāo)號第94頁，課件共102頁，創(chuàng)作于2023年2月網(wǎng)絡(luò)的最大流基本概念：1.容量網(wǎng)絡(luò)：隊(duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個最大的通過能力，稱為該弧的容量，簡記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個發(fā)點(diǎn)(也稱源點(diǎn)，記為s)和一個收點(diǎn)(也稱匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其他點(diǎn)稱為中間點(diǎn)。s①②③④t4844122679第95頁，課件