IntroductiontoSystemsEngineering

石英

武漢理工大學自動化學院E-mail:

a_laly@163.com系統(tǒng)工程概論教學內(nèi)容第一章

緒論

（1學時）

第二章系統(tǒng)分析與系統(tǒng)建模（3學時）

第三章最優(yōu)化技術（24學時）

第四章

系統(tǒng)優(yōu)化（2學時）

第五章

決策分析（2學時）

系統(tǒng)工程概論第三章最優(yōu)化技術§3-1最優(yōu)化技術的基本概念

§3-2線性規(guī)劃§3-3整數(shù)規(guī)劃§3-4非線性規(guī)劃§3-5動態(tài)規(guī)劃§3-6圖與網(wǎng)絡

E-mail:a_laly@163.com

武漢理工大學自動化學院石英§3-1最優(yōu)化技術的基本概念BasicConceptoftheOptimizationTechnology1.數(shù)學模型的建立

TheCreationoftheMathematicalModel2.最優(yōu)化問題的分類

TheSortoftheOptimizationProblem3.最優(yōu)化問題的解決方法

TheSolutionoftheOptimizationProblem系統(tǒng)工程概論分類建模解決方法E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念最優(yōu)化技術是研究和解決最優(yōu)化問題的一門科學，它研究和解決如何從一切可能的方案中尋找最優(yōu)的方案。也就是說，最優(yōu)化技術是研究和解決如何將最優(yōu)化問題表示為數(shù)學模型以及如何根據(jù)數(shù)學模型盡快求出其最優(yōu)解的兩大問題。一般而言，用最優(yōu)化方法解決實際工程問題可分為三步進行：

(1)

根據(jù)所提出的最優(yōu)化問題，建立最優(yōu)化問題的數(shù)學模型，確定變量，列出約束條件和目標函數(shù)(指標函數(shù)或性能指標);

(2)

對所建立的模型進行具體分析和研究，選擇適當?shù)淖顑?yōu)化求解方法;

(3)

根據(jù)最優(yōu)化方法的算法列出程序框圖和編寫語言程序，用計算機求出最優(yōu)解，并對算法的收斂性、通用性、簡便性、計算效率及誤差等作出評價。

最優(yōu)化方法是采用計算機進行尋優(yōu)的方法。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法所謂最優(yōu)化問題，就是尋找一個最優(yōu)化控制方案或最優(yōu)化控制規(guī)律，使所研究的對象(或系統(tǒng))能最優(yōu)地達到預期的目標。例如，在恒溫的自動控制過程中，如果出現(xiàn)干擾而產(chǎn)生偏差，則用什么辦法最快地消除偏差致使系統(tǒng)恢復原來的平衡狀態(tài)?再如，在雷達高炮隨動系統(tǒng)中，當發(fā)現(xiàn)敵機后，如何以最快的速度跟蹤目標而將敵機擊落?又如，在控制發(fā)射N級火箭時，如何規(guī)劃各級火箭的質(zhì)量致使火箭的總質(zhì)量為最小?總之，最優(yōu)化問題的中心課題，就是依據(jù)各種不同的研究對象以及人們預期要達到的目的，尋找出一個最優(yōu)控制規(guī)律或設計出一個最優(yōu)控制方案或最優(yōu)控制系統(tǒng)。

系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法一、數(shù)學模型的建立

用最優(yōu)化方法解決實際工程問題的第一步，就是要建立表達最優(yōu)化問題的數(shù)學模型，其中包括了確定變量、列出約束條件和建立目標函數(shù)等三個主要內(nèi)容。

例[3-1]人造衛(wèi)星姿勢控制問題

人造衛(wèi)星姿勢控制的示意圖如3-1-1。圖中，用A和B表示的兩組斜對稱配置的小噴嘴對成對工作，小噴嘴噴出燃料時產(chǎn)生的反作用力可以使衛(wèi)星旋轉(zhuǎn)并進入要求的姿態(tài)。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法llAABBF/2F/2質(zhì)心基準θ圖3-1-1人造衛(wèi)星姿態(tài)控制示意圖t0時刻，衛(wèi)星偏離要求的基準姿態(tài)θ(t0)角度，且正以角度繼續(xù)偏離。從t0時刻起加上控制力u(t)，使衛(wèi)星在最短時間里回復到所要求的姿態(tài)。以tf表示終端時刻，則要求有θ(tf)=0和且tf

－t0為最小。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法作用在衛(wèi)星體上的力矩表達式為：2×F/2×l=Fl在力矩的作用下，衛(wèi)星體產(chǎn)生的角速度為：Jm為衛(wèi)星體繞質(zhì)心的轉(zhuǎn)動慣量。令控制力選擇狀態(tài)變量x1(t)=θ(t),，則有

系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法寫成向量形式：系統(tǒng)初始狀態(tài)為：系統(tǒng)終端狀態(tài)為：系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法由于小噴嘴可以產(chǎn)生的最大反作用力是有限的，所以控制力u(t)有限，其絕對值不大于某個數(shù)值，即：式中，Um為某個正數(shù)。根據(jù)題意

J＝tf

－t0應為最小。目標函數(shù)約束條件(1)

要求在姿勢控制過程中所消耗的燃料為最少，

J=∫tft0|u(t)|dt

(2)

要求在姿勢控制過程中不但所消耗的燃料為最少，而且還要兼顧到所需要的時間為最短，

J=∫tft0[ρ+|u(t)|]dt

ρ為權系數(shù)，它的大小表示了燃料和時間的相對重要性。若要求動作快、時間短，則要加大ρ;若強調(diào)節(jié)省燃料，則要減小ρ。

人造衛(wèi)星姿勢控制的最優(yōu)化問題，就是如何選擇滿足的容許控制，使所建立的目標函數(shù)取極小值。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法最優(yōu)化問題的數(shù)學描述，應包括以下幾方面的內(nèi)容:

(1)

受控制動態(tài)系統(tǒng)的數(shù)學模型，即滿足系統(tǒng)動力學特性的系統(tǒng)狀態(tài)方程；

(2)

動態(tài)系統(tǒng)的初態(tài)和終態(tài)，即狀態(tài)方程的邊界條件；

(3)

目標函數(shù)(又稱性能指標或性能函數(shù)或目標泛函等)，它是一個衡量“控制作用”效果的性能指標；

(4)

容許控制的集合。每一個實際的控制問題，控制向量u(t)都有一個規(guī)定的取值范圍。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法二、最優(yōu)化問題的分類

(1)

無約束與有約束最優(yōu)化問題

如果控制變量的取值范圍不受限制，則為無約束的最優(yōu)化問題，求無約束函數(shù)的極值時，問題的最優(yōu)解即為目標函數(shù)的極值。約束條件可分為等式約束條件和不等式約束條件。等式約束條件上各點稱為可行解，等式約束曲線表示可行解域。滿足不等式約束條件的區(qū)域范圍稱為解的可行域，在該域內(nèi)的解稱為可行解，而可行解的數(shù)目會有無限多個，其中必有一個為最優(yōu)解。系統(tǒng)工程概論分類建模解決方法E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念(2)

確定性和隨機性最優(yōu)化問題

在確定性最優(yōu)問題中，每個變量的取值是確定的，可知的。在隨機性最優(yōu)問題中，某些變量的取值是不確定的，但可根據(jù)大量的實驗統(tǒng)計，知道變量取某值服從一定的概率分布規(guī)律，這稱為隨機規(guī)劃。

(3)

線性和非線性最優(yōu)化問題

如果目標函數(shù)和所有的約束條件式均為線性，則稱為線行最優(yōu)化問題或線性規(guī)劃問題。如果目標函數(shù)或約束式(即使只是部分約束式)中任一個是變量的非線性函數(shù)，則稱為非線性最優(yōu)化問題或非線性規(guī)劃問題。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法(4)

靜態(tài)和動態(tài)最優(yōu)化問題

如果最優(yōu)化問題的解不隨時間t的變化而變化，則稱為靜態(tài)最優(yōu)化(參數(shù)最優(yōu)化)問題。如果最優(yōu)化問題的解隨時間t的變化而變化，即變量是時間t的函數(shù)，則稱為動態(tài)最優(yōu)化(最優(yōu)控制)問題，解決靜態(tài)最優(yōu)化問題可以采用線性規(guī)劃和非線性規(guī)劃方法，而解決動態(tài)最優(yōu)化問題則采用動態(tài)規(guī)劃或最大值原理。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念分類建模解決方法三、最優(yōu)化問題的求解方法

最有化問題的求解方法大致可分成四類:

(1)

間接法(又稱解析法)

對于目標函數(shù)及約束條件性具有簡單而明確的數(shù)學解析表達式的最優(yōu)化問題，通常可采用間接法(解析法)來解決，其求解方法是先按照函數(shù)極值的必要條件，用數(shù)學分析方法(一般用求導數(shù)方法或變分方法)求出其解析解，然后按照充分條件或問題的實際物理意義間接地確定最優(yōu)解。系統(tǒng)工程概論分類建模解決方法E-mail:a_laly@163.com

武漢理工大學自動化學院石英最優(yōu)化技術的基本概念(2)

直接法(數(shù)值解法)

直接法的基本思想，就是用直接搜索方法經(jīng)過一系列的迭代以產(chǎn)生點的序列(簡稱點列)，使之逐步接近到最優(yōu)點。直接法常常是根據(jù)經(jīng)驗或試驗而得到的。

(3)

以解析法為基礎的數(shù)值解法

以梯度法為基礎的一種直接法，它是一種解析與數(shù)值計算結合的方法。

(4)

圖與網(wǎng)絡方法

這種方法是以網(wǎng)絡作為數(shù)學模型，用圖論方法進行搜索的尋優(yōu)方法。

系統(tǒng)工程概論最優(yōu)化技術的基本概念分類建模解決方法TheEndofOptimizationTechnology系統(tǒng)工程概論第三章最優(yōu)化技術§3-1最優(yōu)化技術的基本概念

§3-2線性規(guī)劃§3-3整數(shù)規(guī)劃§3-4非線性規(guī)劃§3-5動態(tài)規(guī)劃§3-6圖與網(wǎng)絡

E-mail:a_laly@163.com

武漢理工大學自動化學院石英§3-2線性規(guī)劃LinearProgramming1.LP的數(shù)學模型

MathematicalModelofLP2.圖解法

GraphicalMethod3.標準型

NormalizedFormofLP4.單純形法

SimplexMethod5.人工變量法

ArtificialVariableMethod6.附錄：LP常用詞匯線性規(guī)劃（LinearProgramming縮寫為LP）是運籌學的重要分支之一，在實際中應用得較廣泛，其方法也較成熟，借助計算機，使得計算更方便，應用領域更廣泛和深入。

線性規(guī)劃通常解決下列兩類問題

（1）當任務或目標確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設備、原標材料、人工、時間等）去完成確定的任務或目標；

（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多、利潤最大。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法§3-2-1LP的數(shù)學模型產(chǎn)品設備甲乙丙設備能力（小時）A31220B22415C40116D03512利潤（元/件）435【例3.2.1】某企業(yè)計劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不同的設備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設備上加工所需要的臺時如表1-1所示，已知各設備在計劃期內(nèi)的能力分別為20、15、16、12小時；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為4、3、5元。企業(yè)決策者應如何安排生產(chǎn)計劃，使企業(yè)在計劃期內(nèi)總的利潤收入最大？系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法【解】設x1、x2、x3

分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學模型為：系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法線性規(guī)劃的數(shù)學模型由決策變量Decisionvariables

目標函數(shù)Objectivefunction及約束條件Constraints構成。稱為三個要素。其特征是：1．解決問題的目標函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；2．解決問題的約束條件是一組多個決策變量的線性不等式或等式。怎樣辨別一個模型是線性規(guī)劃模型？系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法一般地，假設線性規(guī)劃數(shù)學模型中，有m個約束，有n個決策變量xj,j=1,2…,n，目標函數(shù)的變量系數(shù)用cj表示,

cj稱為價值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示,

bi稱為資源限量。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法線性規(guī)劃數(shù)學模型的一般表達式可寫成：系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法在實際中一般xj≥0,但有時xj≤0或xj無符號限制。為了書寫方便，上式也可寫成系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃目標函數(shù)約束條件LP的數(shù)學模型標準型圖解法單純形法人工變量法系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法1.什么是線性規(guī)劃?2.線性規(guī)劃數(shù)學模型的組成及其特征。3.線性規(guī)劃數(shù)學模型的一般表達式。圖解法的步驟：1.求可行解集合。分別求出滿足每個約束包括變量非負要求的區(qū)域，其交集就是可行解集合，或稱為可行域；2.繪制目標函數(shù)圖形。先過原點作一條矢量指向點（C1,C2)，矢量的方向就是目標函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標函數(shù)圖形；系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法§3-2-2圖解法3.求最優(yōu)解。依據(jù)目標函數(shù)求最大或最小移動目標函數(shù)直線，直線與可行域相交的點對應的坐標就是最優(yōu)解。一般地，將目標函數(shù)直線放在可行域中，求最大時直線沿著矢量方向移動，求最小時沿著矢量的反方向移動。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法x1x2O1020304010203040(3,4)(15,10)最優(yōu)解X=(15,10)最優(yōu)值Z=85maxZ=3x1+4x2例3.2.2動畫演示246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5(3,1)min

Z=x1+2x2例3.2.3動畫演示246x1x2246有無窮多個最優(yōu)解即具有多重解,通解為X（2）＝（3,1）X（1）＝（1,3）0≤α≤1當α=0.5時Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)minZ=5x1+5x2例3.2.4動畫演示246x1x2246無界解(無最優(yōu)解)maxZ=x1+2x2例3.2.5動畫演示x1x2O10203040102030405050無可行解即無最優(yōu)解maxZ=3x1+4x2例3.2.6動畫演示由以上例題可知，線性規(guī)劃的解有4種形式：1.有唯一最優(yōu)解(例3.2.2例3.2.3)2.有多重解(例3.2.4)3.有無界解(例3.2.5)4.無可行解(例3.2.6)

1、2情形為有最優(yōu)解，3、4情形為無最優(yōu)解1.通過圖解法了解線性規(guī)劃有幾種解的形式2.作圖的關鍵有三點(1)可行解區(qū)域要畫正確(2)目標函數(shù)增加的方向不能畫錯(3)目標函數(shù)的直線怎樣平行移動作業(yè)：P79T1,4系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法在用單純法求解線性規(guī)劃問題時，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標準形式。線性規(guī)劃問題的標準型為1．目標函數(shù)求最大值；2．約束條件都為等式方程；3．變量xj為非負；4．常數(shù)bi都大于或等于零。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法§3-2-3線性規(guī)劃的標準型maxZ=c1x1+c2x2+…+cnxn系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法或用矩陣形式:或?qū)懗上铝行问剑合到y(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法其中:通常X記為：

。稱Ａ為約束方程的系數(shù)矩陣，m是約束方程的個數(shù)，n是決策變量的個數(shù)，一般情況m≤n，且r(Ａ)＝m。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法【例3.2.7】將下列線性規(guī)劃化為標準型【解】(1)因為x3無符號要求，即x3取正值也可取負值，標準型中要求變量非負，所以令系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法(2)第一個約束條件是“≤”號，在“≤”左端加入松馳變量x4，x4≥0，化為等式；(3)第二個約束條件是“≥”號，在“≥”號左端減去剩余變量（也稱松馳變量）x5，x5≥0。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法(4)第三個約束條件是≤號且常數(shù)項為負數(shù)，因此在≤左邊加入松馳變量x6，x6≥0，同時兩邊乘以－1。(5)目標函數(shù)是最小值，為了化為求最大值，令Z′=－Z,得到maxZ′=－Z，即當Z達到最小值時Z′達到最大值，反之亦然。

系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法綜合起來得到下列標準型:系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法當某個變量xj≤0時,令x‘j=－xj.當某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如約束

將其化為兩個不等式

再加入松馳變量化為等式。

系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法1.如何化標準形式？可以對照四條標準逐一判斷！標準形式是人為定義的，目標函數(shù)可以是求最小值。2.圖解法時不必化為標準型。3.單純形法求解時一定要化為標準型。作業(yè)：P793系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法單純形算法的基本思路是:根據(jù)問題的標準型,從可行域中某個基可行解(頂點)開始,轉(zhuǎn)換到另一個基可行解(頂點),并使得每次的轉(zhuǎn)換,目標函數(shù)值均有所改善,最終達到最大值時就得到最優(yōu)解。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法§3-2-4單純形法單純形計算方法(SimplexMethod)是先求出一個初始基可行解并判斷它是否最優(yōu)，若不是最優(yōu)，再換一個基可行解并判斷，直到得出最優(yōu)解或無最優(yōu)解。它是一種逐步逼近最優(yōu)解的迭代方法。當系數(shù)矩陣A中可以觀察得到一個可行基時（通常是一個單位矩陣或m個線性無關的單位向量組成的矩陣），可以通過解線性方程組求得基本可行解。【例3.2.8】用單純形法求下列線性規(guī)劃的最優(yōu)解系統(tǒng)工程概論線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法E-mail:a_laly@163.com

武漢理工大學自動化學院石英【解】化為標準型，加入松馳變量x3、x4則標準型為系數(shù)矩陣r（B1）=2，B1是一個初始基,x3、x4為基變量，x1、x2為非基變量，令x1=0、x2=0由約束方程知x3=40、x4=30得到初始基本可行解X(1)=(0,0,40,30)T

系統(tǒng)工程概論線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法E-mail:a_laly@163.com

武漢理工大學自動化學院石英以上得到的一組基可行解是不是最優(yōu)解，可以從目標函數(shù)中的系數(shù)看出。目標函數(shù)Z=3x1+4x2中x1的系數(shù)大于零，如果x1為一正數(shù)，則Z的值就會增大，同樣若x2不為零為一正數(shù)，也能使Z的值增大；因此只要目標函數(shù)中非基變量的系數(shù)大于零，那么目標函數(shù)就沒有達到最大值，即沒有找到最優(yōu)解，判別線性規(guī)劃問題是否達到最優(yōu)解的數(shù)稱為檢驗數(shù)，記作λj,j=1,2…,n。本例中λ1=3,λ2=4,λ3=0,λ4=0.參看表3-1（a）。

最優(yōu)解判斷標準當所有檢驗數(shù)λj≤0（j=1，…，n）時，基本可行解為最優(yōu)解。當目標函數(shù)中有基變量xi時，利用約束條件將目標函數(shù)中的xi消去即可求出檢驗數(shù)。系統(tǒng)工程概論線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法E-mail:a_laly@163.com

武漢理工大學自動化學院石英進基列出基行bi/ai2，ai2>0θi表3-1(a)XBx1x2x3x4bx3211040x4130130λj3400

(b)x3x4λj

(c)x1

x2

λj

基變量11018001/301/3105/31－1/330405/30－4/330103/5－1/51801－1/52/5400－1－1將3化為1乘以1/3后得到LP的數(shù)學模型標準型圖解法單純形法人工變量法動畫演示單純形法全過程的計算，可以用列表的方法計算更為簡潔，這種表格稱為單純形表（表3-1）。計算說明：1.求初始基可行解，列出初始單純形表，求出檢驗數(shù)。其中基變量的檢驗數(shù)必為零；2.判斷：（a）若λj≤０（j＝１，２，…，n）得到最優(yōu)解；（b）某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。（c）若存在λk>0且aik(i=1,…,m)不全非正，則進行換基；系統(tǒng)工程概論線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法E-mail:a_laly@163.com

武漢理工大學自動化學院石英3.換基：（a）設λk>0,xk為進基變量，求最小比值：第Ｌ個比值最小，選最小比值對應行的基變量為出基變量，若有相同最小比值，則任選一個。aLk為主元素；(b）求新的基可行解：用初等行變換方法將aik

化為1,k列其它元素化為零（包括檢驗數(shù)行）得到新的可行基及基本可行解，再判斷是否得到最優(yōu)解。系統(tǒng)工程概論線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法E-mail:a_laly@163.com

武漢理工大學自動化學院石英【例3.2.9】用單純形法求解【解】將數(shù)學模型化為標準形式：不難看出x4、x5可作為初始基變量，單純法計算結果如表3-2所示。系統(tǒng)工程概論線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法E-mail:a_laly@163.com

武漢理工大學自動化學院石英表3-2Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

1/3150120301713751/30－90－2－2025601017/31/31250128/9－1/92/335/300－98/9－1/9－7/3線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法動畫演示

前面討論了在標準型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法§3-2-5人工變量法【例3.2.10】用大M法解下列線性規(guī)劃系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法【解】首先將數(shù)學模型化為標準形式式中x4，x5為松弛變量，x5可作為一個基變量，第一、三約束中分別加入人工變量，x6、，x7，目標函數(shù)中加入―Mx6―Mx7一項，得到人工變量單純形法數(shù)學模型再用前面介紹的單純形法求解，見下表。

系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法線性規(guī)劃

Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－2121－1000101000014101→λj3－2M2+M－1+2M↑－M000

－M0－1x6x5x3－6－3253－2001－100010001

3→81λj5－6M5M↑0－M00

20－1x2x5x3－6/53/5－2/5100001－1/53/5－2/5010

3/531/5→11/5λj5↑0000

23－1x2x1x301010000111025/32/3

1331/319/3λj000－5－25/3

系統(tǒng)工程概論LP的數(shù)學模型標準型圖解法單純形法人工變量法（1）初始表中的檢驗數(shù)有兩種算法，第一種算法是利用第一、三約束將x6、x7的表達式代入目標涵數(shù)消去x6和x7，得到用非基變量表達的目標函數(shù)，其系數(shù)就是檢驗數(shù)；第二種算法是利用公式計算，如（2）M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法（3）在第二張中x7已出基，故沒有計算第七列的數(shù)值，同理，第三、四張表中x6、x7都已出基，故第六、七列沒有計算；（4）第三、四張表中的基變量沒有人工變量x6、x7，因而檢驗數(shù)中不含M；（5）可以看出，人工變量是幫助我們尋求原問題的可行基，第三張表就找到了原問題的一組基變量x2、x5、x3，此時人工變量就可以從模型中退出，也說明原規(guī)劃有可行解，但不能肯定有最優(yōu)解。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法【例3.2.11】求解線性規(guī)劃

【解】加入松馳變量x3、x4化為標準型系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法在第二個方程中加入人工變量x5，目標函數(shù)中加上Mx5一項，得到系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法用單純形法計算如下表所示。Cj5－800MbCBXBx1x2x3x4x50Mx3x53※11－2100－1016→4λj5－M↑－8+2M0M0

5MX1x5101/3－7/31/3－1/30－10122λj0－29/3+7/3M－5/3+1/3MM0

表中λj≥0，j=1，2，…，5，從而得到最優(yōu)解X=（2，0，0，0，2），Z=10+2M。但最優(yōu)解中含有人工變量x5≠0說明這個解是偽最優(yōu)解，是不可行的，因此原問題無可行解。系統(tǒng)工程概論LP的數(shù)學模型標準型圖解法單純形法人工變量法解的判斷唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線性規(guī)劃具有唯一最優(yōu)解。多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線性規(guī)劃具有多重最優(yōu)解。無界解的判斷:某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。無可行解的判斷：當用大M單純形法計算得到最優(yōu)解并且存在Ri>0時，則表明原線性規(guī)劃無可行解。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英LP的數(shù)學模型標準型圖解法單純形法人工變量法線性規(guī)劃線性規(guī)劃常用詞匯線性規(guī)劃Linearprogramming數(shù)學模型Mathematicalmodel決策變量Decisionvariable約束條件Constraint目標函數(shù)Objectivefunction圖解法graphicalmethod可行域feasibleregion可行解feasiblesolution最優(yōu)解optimalsolution非可行解infeasiblesolution斜率slopeofaline系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法取...最大值,最大化maximize最小化minimize變量variable基basis基變量basisvariable松弛變量slackvariable人工變量artificialvariable進基變量enteringvariable出基變量leavingvariable無界解unboundsolution機會成本Opportunitycost系數(shù)coefficient迭代iteration系統(tǒng)工程概論線性規(guī)劃LP的數(shù)學模型標準型圖解法單純形法人工變量法線性規(guī)劃常用詞匯TheEndofLP系統(tǒng)工程概論第三章最優(yōu)化技術§3-1最優(yōu)化技術的基本概念

§3-2線性規(guī)劃§3-3整數(shù)規(guī)劃§3-4非線性規(guī)劃§3-5動態(tài)規(guī)劃§3-6圖與網(wǎng)絡

E-mail:a_laly@163.com

武漢理工大學自動化學院石英1.整數(shù)規(guī)劃數(shù)學模型MathematicalModelof

IP2.分枝定界法BranchandBoundMethod3.0－1規(guī)劃

BinaryIntegerProgramming4.指派問題

AssignmentProblem§3-3整數(shù)規(guī)劃IntegerProgramming一個規(guī)劃問題中要求部分或全部決策變量是整數(shù)，則這個規(guī)劃稱為整數(shù)規(guī)劃。當要求全部變量取整數(shù)值的，稱為純整數(shù)規(guī)劃；只要求一部分變量取整數(shù)值的，稱為混合整數(shù)規(guī)劃。如果模型是線性的，稱為整數(shù)線性規(guī)劃。本章只討論整數(shù)線性規(guī)劃。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃§3-3-1整數(shù)規(guī)劃的數(shù)學模型IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題很多實際規(guī)劃問題都屬于整數(shù)規(guī)劃問題.例如1.變量是人數(shù)、機器設備臺數(shù)或產(chǎn)品件數(shù)等都要求是整數(shù)2.對某一個項目要不要投資的決策問題，可選用一個邏輯變量x，當x=1表示投資，x=0表示不投資；3.人員的合理安排問題，當變量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。邏輯變量也是只允許取整數(shù)值的一類變量。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題【例3.3.1】某人有一背包可以裝10公斤重、0.025m3的物品。他準備用來裝甲、乙兩種物品，每件物品的重量、體積和價值如表3-3-1-所示。問兩種物品各裝多少件，所裝物品的總價值最大？表3-3-1物品重量（公斤/每件）體積（m3/每件）價值(元/每件)甲乙1.20.80.0020.002543系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題【解】設甲、乙兩種物品各裝x1、x2件，則數(shù)學模型為：(3.3.1)系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃如果不考慮x1、x2取整數(shù)的約束（稱為（3.3.1）的松弛問題），線性規(guī)劃的可行域如圖3-3-1中的陰影部分所示。IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題圖3-3-1系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題用圖解法求得點B為最優(yōu)解：X＝(3.57，7.14)，Z＝35.7。由于x1，x2必須取整數(shù)值，實際上整數(shù)規(guī)劃問題的可行解集只是圖中可行域內(nèi)的那些整數(shù)點。用湊整法來解時需要比較四種組合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）雖屬可行解，但代入目標函數(shù)得Z=33,并非最優(yōu)。實際上問題的最優(yōu)解是（5，5），Z=35。即兩種物品各裝5件，總價值35元。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題由圖3-3-1知，點（5，5）不是可行域的頂點，直接用圖解法或單純形法都無法求出整數(shù)規(guī)劃問題的最優(yōu)解，因此求解整數(shù)規(guī)劃問題的最優(yōu)解需要采用其它特殊方法。還有些問題用線性規(guī)劃數(shù)學模型無法描述，但可以通過設置邏輯變量建立起整數(shù)規(guī)劃的數(shù)學模型。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題【例3.3.2】在例3.3.1中，假設此人還有一只旅行箱，最大載重量為12公斤，其體積是0.02m3。背包和旅行箱只能選擇其一，建立下列幾種情形的數(shù)學模型，使所裝物品價值最大。（1）

所裝物品不變；（2）如果選擇旅行箱，載重量和體積的約束為系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題解：此問題可以建立兩個整數(shù)規(guī)劃模型，但用一個模型描述更簡單。引入0－1變量（或稱邏輯變量）yi，令i=1,2分別是采用背包及旅行箱裝載。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題(1)由于所裝物品不變，式(3.3.1)約束左邊不變，整數(shù)規(guī)劃數(shù)學模型為(2)由于不同載體所裝物品不一樣，數(shù)學模型為系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題旅行箱y2，重量背包y1，重量背包y1，體積旅行箱y2，體積式中M為充分大的正數(shù)。從上式可知，當使用背包時(y1=1，y2=0)，式(b)和(d)是多余的；當使用旅行箱時(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令：同樣可以討論對于有m個條件互相排斥、有m（≤m、≥m）個條件起作用的情形。系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃如果問題的所有變量取0或1，此問題稱為0－1整數(shù)規(guī)劃問題，簡稱0－1規(guī)劃。IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃【例3.3.3】指派問題或分配問題。人事部門欲安排四人到四個不同崗位工作，每個崗位一個人。經(jīng)考核四人在不同崗位的成績（百分制）如表3-3-2所示，如何安排他們的工作使總成績最好。表3-3-2工作人員ABCD甲85927390乙95877895丙82837990丁86908088IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃【解】此工作分配問題可以采用枚舉法求解，即將所有分配方案求出，總分最大的方案就是最優(yōu)解。本例的方案有4！＝4×3×2×1＝24種，當人數(shù)和工作數(shù)較多時，方案數(shù)是人數(shù)的階乘，計算量非常大。用0－1規(guī)劃模型求解此類分配問題顯得非常簡單。設IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃數(shù)學模型如下：目標函數(shù)為要求每人做一項工作，約束條件為IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題每項工作只能安排一人，約束條件為變量約束：

系統(tǒng)工程概論E-mail:a_laly@163.com

武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題1.線性整數(shù)規(guī)劃模型的特征2.什么是純（混合）整數(shù)規(guī)劃3.0－1規(guī)劃模型的應用4.指派模型的特征及其應用系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題分枝定界法的步驟：

1.求整數(shù)規(guī)劃的松弛問題最優(yōu)解；2.

若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解，否則轉(zhuǎn)下一步；3.任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束xi≤[xi]及xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界；系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃§3-3-2分枝定界法IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題分枝定界法的步驟：4.

檢查所有分枝的解及目標函數(shù)值，若某分枝的解是整數(shù)并且目標函數(shù)值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計算，若還存在非整數(shù)解并且目標值大于（max）整數(shù)解的目標值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題【例3.3.4】用分枝定界法求解例3.3.1【解】先求對應的松弛問題（記為LP0）：用圖解法得到最優(yōu)解X＝（3.57,7.14）,Z0=35.7,如下圖所示。系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題1010松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC1010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②動畫演示1010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②動畫演示1010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP3動畫演示盡管LP1的解中x1不為整數(shù)，但Z5>Z因此LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。上述分枝過程可用下圖表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5無可行解x2≥7動畫演示1.理解分枝與定界的含義2.選擇合適的“枝”生“枝”3.掌握何時停止生“枝”4.掌握混合整數(shù)規(guī)劃的分枝定界法求解整數(shù)規(guī)劃的方法還有割平面法。作業(yè)：教材P134T5.2系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題什么是0-1規(guī)劃？以一個工程項目投資分配問題為例。有n個工程，每項工程建成后的經(jīng)濟效益為cj，各項工程的投資、資源都是有限的，如何確定哪些項目應該建設，以使總的經(jīng)濟效益最大。數(shù)學模型如下：系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題§3-3-30-1規(guī)劃求解0－1整數(shù)規(guī)劃的隱枚舉法(ImplicitEnumerationMethod)隱枚舉法的步驟：1.找出任意一可行解，目標函數(shù)值為Z0；2.

原問題求最大值時，則增加一個約束當求最小值時，上式改為小于等于約束；(*)系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題列出所有可能解，對每個可能解先檢驗式（*），若滿足再檢驗其它約束，若不滿足式（*），則認為不可行，若所有約束都滿足，則認為此解是可行解，求出目標值；目標函數(shù)值最大（最小）的解就是最優(yōu)解。系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題【例3.3.5】用隱枚舉法求下列0－1整數(shù)規(guī)劃的最優(yōu)解【解】容易求得X＝(1,0,0)是一可行解，Z0＝6。加一個約束(0)由于3個變量每個變量取0或1，共有8種組合，用列表的方法檢驗每種組合解是否可行解，滿足約束打上記號“√”，不滿足約束打上記號“×”，計算如表3-3-3所示。系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型0-1規(guī)劃指派問題分枝定界法表3-3-3變量組合約束(0)約束(1)約束(2)約束(3)Z（0，0，0）

（0，0，1）

（0，1，0）

（0，1，1）

（1，0，0）（1，0，1）（1，1，0）

（1，1，1）

由表3-3-3知，X＝（1，0，1）是最優(yōu)解，最優(yōu)值Z＝9。××××√√√√6√√√√9√√××√E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題動畫演示系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題§3-3-4指派問題指派問題，顧名思義，就是將“任務”指派給“人”。假定每個人只能分擔一個任務，每個任務只能分給一個人，這就是指派問題。1.指派問題的數(shù)學模型系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題可見，指派問題是0-1規(guī)劃的一種特例。2.指派問題的求解方法：匈牙利算法匈牙利算法是匈牙利數(shù)學家克尼格（Konig）證明了下面兩個基本定理，為計算分配問題奠定了基礎。因此，基于這兩個定理基礎上建立起來的解分配問題的計算方法被稱為匈牙利法。假設問題求最小值，m個人恰好做m項工作，第i個人做第j項工作的效率為cij，效率矩陣為[cij]。系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題【定理3.1】如果從分配問題效率矩陣[cij]的每一行元素中分別減去（或加上）一個常數(shù)ui（被稱為該行的位勢），從每一列分別減去（或加上）一個常數(shù)vj（稱為該列的位勢），得到一個新的效率矩陣[bij]，若其中bij=cij－ui－vj,則[bij]的最優(yōu)解等價于[cij]的最優(yōu)解。這里cij、bij均非負。【定理3.2】若矩陣A的元素可分成“0”與非“0”兩部分，則覆蓋“0”元素的最少直線數(shù)等于位于不同行不同列的“0”元素（稱為獨立元素）的最大個數(shù)。系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題如果最少直線數(shù)等于m，則存在m個獨立的“0”元素，令這些零元素對應的xij等于1，其余變量等于0，得到最優(yōu)解。定理3.1告訴我們?nèi)绾螌⑿时碇械脑剞D(zhuǎn)換為有零元素，定理3.2告訴我們效率表中有多少個獨立的“0”元素。【例3.3.6】已知四人分別完成四項工作所需時間如下表，求最優(yōu)分配方案。系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題【解】最優(yōu)分配方案是怎樣安排四人的工作，使得完成工作總時間最少，是求最小值問題。第一步：找出效率矩陣每行的最小元素，并分別從每行中減去最小元素，有Min3408第二步：找出矩陣每列的最小元素，再分別從每列中減去，有Min系統(tǒng)工程概論IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題第三步：用最少的直線覆蓋所有“0”，得第四步：這里直線數(shù)等于3（等于4時停止運算），要進行下一輪計算。（1）從矩陣未被直線覆蓋的數(shù)字中找出一個最小的數(shù)k，表中k＝3。(2)直線相交處的元素加上k，未被直線覆蓋的元素減去k，被直線覆蓋而沒有相交的元素不變，得到下列矩陣系統(tǒng)工程概論IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題整數(shù)規(guī)劃可以分解為兩個步驟：在1、2、4行（未被直線覆蓋）減3，然后在3、4列（被直線覆蓋）加3，根據(jù)定理1，與原矩陣等價。或者1、2列減3，第3行加3。回到第三步:用最少的直線覆蓋所有“0”，得未被直線覆蓋元素中最小元素k=2,直線相交處的元素加上2，未被直線覆蓋的元素減去2，被直線覆蓋而沒有相交的元素不變，得到下列矩陣系統(tǒng)工程概論IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題畫線，最少直線數(shù)等于4。第五步：最優(yōu)分配最優(yōu)解：最優(yōu)值Z＝73＋87＋82＋88＝330×××系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題獨立元素0代表了最優(yōu)指派。它們應該盡量分散，覆蓋所有行或者所有列3.求最大值的指派問題匈牙利法的條件是：模型求最小值、效率cij≥0令則與的最優(yōu)解相同。設C=(cij)m×m

對應的模型是求最大值將其變換為求最小值系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題【例】某人事部門擬招聘4人任職4項工作，對他們綜合考評的得分如下表(滿分100分)，如何安排工作使總分最多。【解】M＝95，令系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模型分枝定界法0-1規(guī)劃指派問題用匈牙利法求解：最優(yōu)解：即甲安排做第二項工作、乙做第一項、丙做第四項、丁做第三項。總分為：Z＝92＋95＋90＋80＝357系統(tǒng)工程概論E-mail:a_laly@163.com武漢理工大學自動化學院石英整數(shù)規(guī)劃IP的數(shù)學模