規(guī)劃問題的基本概念專題培訓課件

規(guī)劃問題的基本概念推薦參考書胡運權(quán).運籌學教程.清華大學出版社.1998韓伯棠.管理運籌學.高等教育出版社.2010謝金星等.優(yōu)化建模與Lindo/Lingo軟件.清華大學出版社.2005譚永基等.經(jīng)濟管理數(shù)學模型案例教程.高教出版社.2013譚永基.數(shù)學模型.復旦大學出版社.2005姜啟源.數(shù)學模型.高等教育出版社.2010但靜.數(shù)學建模與數(shù)學實驗.高等教育出版社.2003姜啟源等.大學數(shù)學實驗.清華大學出版社.2004[美]JoeZhu著.數(shù)據(jù)包絡分析.科學出版社.2016謝中華.Matlab統(tǒng)計分析與應用：40個案例分析.北航出版社.2010規(guī)劃問題及其模型

在工程技術(shù)、經(jīng)濟管理、科學研究等領(lǐng)域中，決策者要求在滿足一系列條件要求下，求材料最省、重量最輕、成本最低、時間最短、路程最短、利潤最大、誤差最小、產(chǎn)量最大等等，都稱為優(yōu)化問題。習慣上，上述的最省、最輕、最低、最短、最大等統(tǒng)稱最優(yōu)。

對于給定的優(yōu)化問題，決策者根據(jù)問題的背景知識或試驗數(shù)據(jù)，將問題進一步簡化，用一系列數(shù)學符號(變量)來代替問題所涉及的各種已知或未知要素，用這些符號的函數(shù)等式或者不等式來反映客觀條件或約束，并用這些符號的函數(shù)來反映決策者的訴求（欲望或目標），這樣的約束和訴求就構(gòu)成了相應問題的規(guī)劃模型。一、兩個案例案例1

（生產(chǎn)決策問題）

（一個線性規(guī)劃模型）案例2

（路燈照度問題）

（一個非線性規(guī)劃問題）

通過兩個案例，學習規(guī)劃模型的建立必要步驟以及書寫的規(guī)范格式。

某工廠在計劃期內(nèi)要安排I、II兩種產(chǎn)品生產(chǎn)。生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時、A，B兩種原材料的消耗、資源的限制以及單件產(chǎn)品利潤如表1-1所示表1-1問工廠應分別生產(chǎn)多少單位產(chǎn)品I和產(chǎn)品II，才能獲利最多？III資源限制設(shè)備原料A原料B11300臺時21400kg01250kg利潤（元）50100案例1生產(chǎn)決策問題（一個簡單的線性規(guī)劃問題）【問題分析]】（1）這是一個生產(chǎn)決策問題，決策者的目標是生產(chǎn)利潤最大（2）與利潤有關(guān)的是產(chǎn)品的銷售量與售價（或單位利潤）；（3）生產(chǎn)產(chǎn)品就要消耗資源（這與產(chǎn)量有關(guān)），而各種資源又受到客觀限制。經(jīng)驗：收入與銷售量有關(guān)，而資源的消耗量與產(chǎn)品的產(chǎn)量有關(guān)。【問題假設(shè)】

（1）產(chǎn)品I的產(chǎn)量等于銷售量；（2）產(chǎn)品II的產(chǎn)量等于銷售量?！痉栐O(shè)置】x1

產(chǎn)品I的一個周期的產(chǎn)量（單位：件）；x2

產(chǎn)品II的一個周期的產(chǎn)量（單位：件）；z工廠一個周期內(nèi)的總利潤（單位：元）。（其中，x1,x2稱為決策變量）III資源限制設(shè)備原料A原料B11300臺時21400kg01250kg利潤（元）50100【建立模型】工廠一個生產(chǎn)周期的總利潤x1x2生產(chǎn)資料約束（設(shè)備限時）（原料A限量）（原料B限量）資源的實際消耗資源的擁有量限制III資源限制設(shè)備原料A原料B11300臺時21400kg01250kg利潤（元）50100其它約束：因為x1和x2都是產(chǎn)品的產(chǎn)量，所以，從數(shù)學意義上，有廠家的訴求：一個周期內(nèi)利潤z越大越好！(maxz)

以上分析，將生產(chǎn)過程的未知要素（產(chǎn)品產(chǎn)量）用x1,x2表示，各種客觀約束都表達為x1,x2的函數(shù)不等式，廠家的訴求（利潤）也是x1,x2的函數(shù)表達式，將這些數(shù)學結(jié)構(gòu)寫在一起，就是這個規(guī)劃問題的數(shù)學模型：

這個規(guī)劃模型，如果拋開這個問題的背景，就是求在五個約束條件下，一次函數(shù)z=50x1+100x2的最大值，這是一個純數(shù)學意義上的極大值問題?！緮?shù)學模型】目標函數(shù)條件約束變量約束約束Subjectto受約束于，滿足于

雖然有些問題的數(shù)學結(jié)構(gòu)很難用數(shù)學式子來表達，但習慣上我們稱決策變量、約束條件、目標函數(shù)為規(guī)劃問題的三要素。這個問題的目標和約束都是決策變量的一次表達式，稱為線性規(guī)劃。決策變量案例2路燈照度問題(一個非線性規(guī)劃問題）

如圖2-1所示，在一條s=20m寬的道路兩側(cè)，分別安裝了一只2kw和一只3kw的路燈，它們離地面的高度分別為h1=5m和h2=6m。（1）在漆黑的夜晚，當兩只路燈開啟時，兩只路燈連線路面上最暗的點和最亮的點在哪里？（2）如果3kw路燈的高度可以在3m到9m之間變化，如何求得路面上最暗和最亮的點的位置？（3）如果兩只路燈的高度均可以在3m到9m之間變化，結(jié)果將如何？圖2-1osxP1P2h1h2r1r2【問題分析】經(jīng)驗：（物理學背景知識）

光源點P1在點x處的照度（照亮強度）I1，I1與功率P1成正例，與距離r1的平方成反比，與照射角度α1的正弦成正比。即其中，k為比例系數(shù)，同時也是平衡量綱（單位）的量。圖2-1osxP1P2h1h2r1r2圖2-1osxP1P2h1h2r1r2【問題假設(shè)】（1）p1,p2都可以看成點光源；（2）p1,p2在x的照度可以疊加（求和）；【符號設(shè)置】（符號設(shè)置如有圖2-1所示）I:某點處的照度（亮度）；I1：燈P1在該點處的照度；I2：燈P2在該點處的照度；（3）光源只來至兩盞燈。s:街道寬；

p1,p2:兩個光源的功率；h1,h2:兩盞燈的高度；

r1,r2:兩盞路燈到x的距離；

x:街道某點的坐標，介于0和s之間；

α1,

α2:光線的入射角。圖2-1osxP1P2h1h2r1r2兩只燈在點x處的照度為其中，變量之間的關(guān)系【建立模型】問題(1)：燈高度不變，求路面照度最弱最強的位置x。數(shù)學模型1s.t.也可以化簡為代入已知參數(shù)，模型簡化為即求一元函數(shù)I(x)在[0，20]上的最大值與最小值。問題(2)：當3kw的燈的高度在3m到9m之間變化時，路面的最暗和最亮點。數(shù)學模型2

即求二元函數(shù)I(x,h2)在所給矩形閉區(qū)域上的最大值與最小值。問題(3)：兩只燈的高度都在3m到9m之間變化時，求路面的最暗和最亮點。數(shù)學模型3即求三元函數(shù)I(x,h1,h2)在所給條件下的上的最大值與最小值。

像這種目標函數(shù)或者約束條件是決策變量的非一次（非線性）的規(guī)劃模型，稱為非線性規(guī)劃模型。二、規(guī)劃問題解的概念1、線性規(guī)劃解的概念

通過具體的例子，學習線性規(guī)劃問題的可行解、可行域、最優(yōu)解等概念；通過圖解法了解線性規(guī)劃解的情況；2、非線性規(guī)劃解的概念

通過具體的例子，學習非線性規(guī)劃的可行解、可行域、局部最優(yōu)解、全局最優(yōu)解等概念；通過例子了解非線性規(guī)劃求解的特點；3、小結(jié)

對比線性規(guī)劃和非線性規(guī)劃的圖解法，總結(jié)兩種規(guī)劃解的不同點（局部和全局）和相同點（迭代法）。1、線性規(guī)劃解的概念1.1線性規(guī)劃的可行解

若x1,x2滿足條件[1]~[4],則稱向量為線性規(guī)劃問題的一個可行解。[1][2][3][4]例如其中x(1),x(2)為可行解，而x(3),x(4)不是可行解。所有可行解構(gòu)成的集合稱為該線性規(guī)劃的可行域。

在例1中，若存在x*=[x1*,x2*]T,對D中任何x=[x1,x2]T，都有稱x*為該線性規(guī)劃的最優(yōu)解（使目標函數(shù)最大或最小的可行解）。1.2線性規(guī)劃的可行域1.3線性規(guī)劃的最優(yōu)解1.4可行解、可行域、最優(yōu)解的幾何意義可以用圖解法求解兩個決策變量的線性規(guī)劃問題。例3用圖解法求解如下線性規(guī)劃問題解圖解法步驟：（1）用x1，x2分別表示橫坐標和縱坐標，并根據(jù)x1,x2>=0，繪制坐標系；（2）圖示各個約束條件所表達的基線及其變化方向；（3）由滿足所有條件的點（可行解）構(gòu)成的集合（區(qū)域）就是可行域，（4）圖示目標函數(shù)的基線，并由變量的變化方向確定基線的平移方向，最后確定最優(yōu)解；x1x205x2=156x1+2x2=24x1+x2=5Q1Q2Q3Q4可行區(qū)域Dx2=z-2x1使得目標函數(shù)最大的點Q2(3.5,1.5)Q2對應的點就是線性規(guī)劃問題的唯一最優(yōu)解：x*=[x1*=3.5,x2*=1.5]T。

例4用圖解法觀察下述問題的最優(yōu)解情況x1x205x2=156x1+2x2=24x1+x2=5Q1Q2Q3Q4x2+x1=0可以看出，Q2Q3上的點全是最優(yōu)解。即問題有無窮多最優(yōu)解。

例5判斷如下線性規(guī)劃的解情況X2=3x1x20x2+x1=0可以看出，在可行域內(nèi)，當可行解變化時，目標函數(shù)可以無限增大。即問題為無界解。例6

判斷如右線性規(guī)劃問題的解情況可以看出，該問題兩個約束矛盾，無可行解。

綜上所述，對于線性規(guī)劃問題，其結(jié)果不外乎下面幾種情況：（1）有最優(yōu)解：唯一最優(yōu)解或無窮多最優(yōu)解，且最優(yōu)解一定在可行域某頂點達到；（2）無界解；（3）無可行解。

在實際的線性規(guī)劃模型的計算中，如果遇到（2）情況，說明漏掉了重要的約束；如果遇到（3）情況，說明問題有約束沖突，檢查約束條件，一般采取如下策略：要么留下主要約束，去掉與之矛盾的次要的約束；要么承認矛盾的合理性，采用多目標規(guī)劃。

在建立規(guī)劃模型時，若目標函數(shù)如例2中決策變量或者約束方程（不等式）中某些變量為非一次（不是線性），則稱建立的數(shù)學模型為非線性規(guī)劃模型。[5]2、非線性規(guī)劃解的概念模型[5]為非線性規(guī)劃的標準模型(目標最小化，所有約束都是大于等于)，很多優(yōu)化理論的推導和優(yōu)化程序的編譯都是按照這種模式展開）。[6]模型[6]稱為無約束優(yōu)化。默認[7]模型[7]稱為二次規(guī)劃(目標是決策變量的二次型，約束都是決策變量的線性約束，它的很多性質(zhì)跟線性規(guī)劃類似)。2.1可行集（可行域）給定非線性規(guī)劃問題[5][10][11][12]2.1.1可行解若x1,x2滿足條件[10],[11],[12]，則稱向量x=[x1,x2]T為非線規(guī)劃[5]的可行解。[10][11][12]例如：其中x(1),x(4)不是此問題的可行解，而x(2),x(3)是規(guī)劃問題[5]的可行解。2.1.2可行集（可行域）稱為非線性規(guī)劃問題[5]的可行集（域）。例8利用圖解法，求解如下非線性規(guī)劃問題【問題分析】:決策變量為x=(x1,x2)T。目標函數(shù)表示決策變量ｘ=(x1,x2)T到點(2,1)T的距離的平方（體現(xiàn)為以(2,1)為圓心的圓周半徑變化）；第一個約束是一條拋物線（開口朝左,x1為橫軸）；第二個約束為一次不等式；同時決策變量非負。（注意等號）解以x1和x2分別為橫軸和縱軸，建立直角坐標系，如圖2-2：（1）繪制約束曲線；（2）標出可行域：x1x20(右上)2.5(在拋物線上)ABCD拋物線段ABCD為可行域；圖2-2x1x20(右上)2.512ABCD如圖2-2（續(xù)）（3）繪制目標函數(shù)曲線該問題的目標是在拋物線段ABCD上找一個點，使得這個點到(2,1)T的距離的平方最?。ň嚯x本身也是最小）。這樣的點位于以(2,1)T為圓心的圓周上。由圖示可知，點D到(2,1)T的距離最小。即D(4,1)T就是拋物線段ABCD上到點(2,1)T距離平方最小的點。2.2非線性規(guī)劃的解的概念2.2.1局部極?。O大）點如右圖所示，點B(2.9104,4.3275)T比附近的其它點對應的目標函數(shù)值都小，稱為局部極小點，對應的目標值f(B)為局部極小值；點C(6.25,2.5)T對應的目標函數(shù)值比附近的其它目標函數(shù)值都大，稱為局部極大點，對應的目標函數(shù)f(C)稱為局部極大值。

因為拋物線段ABCD上，B左右的點到(2,1)T的距離都大于B到(2,1)T的距離；C左右的點到(2,1)T的距離都小于C到(2,1)T的距離。2.2.2全局最?。ㄗ畲螅c如右圖所示，點D(4,1)T到(2,1)T的距離小于拋物線段ABCD上其它任何點到(2,1)T的距離，稱點D為此規(guī)劃的全局最小值點，f(D)稱為全局最小值。點A(0,5)T到點(2,1)T的距離大于拋物線段ABCD上任何點到(2,1)T的距離，稱點A為全局最大值點，f(A)稱為全局最大值。3.1、線性規(guī)劃求解的特點例3的圖解法截圖3、線性規(guī)劃與非線性規(guī)劃最優(yōu)解求解的根本區(qū)別例4圖解法截圖線性規(guī)劃最優(yōu)解的特點：（1）線性規(guī)劃的可行域都是直線段圍成的（凸）多邊形區(qū)域；（2）只要線性規(guī)劃存在最優(yōu)解（不管是唯一最優(yōu)解還是無窮多最優(yōu)解），就一定會在邊界的頂點處到達；（3）尋找線性規(guī)劃最優(yōu)解的原理：【單純形法】步驟1：在OQ1Q2Q3Q4O邊界上，任取一個頂點，比如O點，計算O的目標函數(shù)值，比較O與相鄰的頂點Q1和Q4對應的的目標函數(shù)值，如果O點的目標函數(shù)值最大（最大化目標），O就是最優(yōu)解；步驟2：如果存在相鄰點對應的目標函數(shù)值比O點對應的目標函數(shù)值大（比如Q1)，用Q1點代替剛才的O點，重復步驟1，直到某個點對應的目標函數(shù)值比相鄰的點對應的目標函數(shù)值都大。對線性規(guī)劃解的全局性：對于線性規(guī)劃問題，得到的任何一個最優(yōu)解都是全局最優(yōu)解。3.2、非線性規(guī)劃求解的特點例8圖解法截圖非線性規(guī)劃求解原理和線性規(guī)劃求解原理大致都用迭代法。步驟1：如右圖所示，在可行域ABCD拋物線段上任取一個初始點O（有風險），比如這個初始點選在AB之間的某點；步驟2：從O點分別試著朝A和朝B方向走，比較哪個方向會讓目標函數(shù)減?。ㄗ钚』繕耍绻卸鄠€方向，就選取目標函數(shù)減小最快的方向），就準備朝那個方向邁出步伐；步驟3：確定了朝B方向目標函數(shù)會減小，就朝B方向跨出最大一步，到達步伐的終點O1；步驟4：用O1替代O點，重復步驟1~3，直到?jīng)]有方向可走為止。非線性規(guī)劃迭代法計算的風險：尋找最小（或最大）依賴于初始點。比如剛才的迭代初始值選在AB之間，就會將B點誤作為全局最小值點。規(guī)避這種風險的方法除了從迭代方法上作改進，就是多選幾個初始點計算，然后比較每次計算的最優(yōu)解，再選取你認為最合適的一個點為全局最優(yōu)解。（例如：設(shè)wifi信號源在(2,1)T，你拿著手機在ABCD段上找離信號源最近的點）三、按照決策變量要求識別規(guī)劃模型1、整數(shù)規(guī)劃模型

部分決策變量要求取整數(shù)，這個要求人能識別，智能機器能識別，同時要求軟件能識別；2、0-1規(guī)劃

對于“是”與“非”的選擇問題，多用0-1變量來實現(xiàn)，同樣要求人、機器、軟件都能識別；3、通過案例學習，了解不同變量之間的交叉約束的線性約束表達。1、整數(shù)規(guī)劃模型例9貨物托運問題（一般整數(shù)規(guī)劃）

某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤以及托運限制如表1-2貨物每件體積/英尺3每件重量/100kg每件利潤/百元甲19542乙273403托運限制1365140表1-2

且甲種貨物最多托運4件，問兩種貨物各托運多少件，可獲利最大?！締栴}假設(shè)】（1）甲乙兩種貨物不可分割，即按整數(shù)計件；（2）甲乙兩貨物的體積可以直接相加（軟體積）。比如水的體積，就是所占空間的體積（軟體積）；碎石的體積就比所占空間的體積?。ㄓ搀w積）?！痉栐O(shè)置】x1

甲貨物裝運的件數(shù)；x2

乙貨物裝運的件數(shù)；z一次運輸?shù)睦麧櫍▎挝唬喊僭窘⒛Ｐ汀扛鶕?jù)問題描述，則總利潤為【問題分析】（此問題已高度簡化，[問題分析]略去）運輸體積約束運輸重量約束貨物要求約束貨物分割要求x1,x2要求取整數(shù)；非負約束【數(shù)學模型】x1,x2取整（或x1,x2∈Z）線性規(guī)劃整數(shù)線性規(guī)劃

這種要求所有決策變量的線性規(guī)劃就稱為線性整數(shù)規(guī)劃；要求部分變量取整的稱為混合線性整數(shù)規(guī)劃。例10投資場所的選擇（一般0-1規(guī)劃）

某公司計劃在市區(qū)的東、南、西、北四個區(qū)建立銷售門面。擬議中有10個位置Ai(i=1,2,…,10)可供選擇，考慮到各個地區(qū)居民消費水平以及居民的居住密度，規(guī)定：在東區(qū)A1,A2,A3三個點中至少選擇兩個；在西區(qū)A4,A5兩個點中至少選擇一個；在南區(qū)A6,A7兩個點中至少選擇一個；在北區(qū)A8,A9,A10三個點中至少選擇2個。Ai各個點的設(shè)備投資以及每年可獲利潤由于地點不同都不一樣，預測情況如下表A1A2A3A4A5A6A7A8A9A10投資額10012015080709080140160180利潤36405022203025485861

另外，投資總額不能超過720萬元，問應該選擇哪幾家銷售點，可使得年利潤為最大？【問題分析】

根據(jù)問題的敘述，每個點最多建立一個銷售網(wǎng)點，若設(shè)xi為第i小區(qū)建立的銷售網(wǎng)點數(shù)，則在第i個點建立銷售網(wǎng)點在第i個點不建銷售網(wǎng)點i=1,2,…,10這樣的0-1決策變量，有如下性質(zhì)：

即對每個點xi來說，要么取0，要么取1，這樣的變量就稱為0-1變量，因此，變量也可以設(shè)成（1）xi+xj=1：xi和xj有且只有一個取1，另外一個取0；（2）xi+xj<=1：xi和xj最一個多取1；（3）xi+xj>=1：xi和xj至少一個取1；（4）kxj：要么取k，要么取0；（5）x1+x2+…+xm=p(p<=m)：m個中恰好取p個；（6）x1+x2+…+xm<=p：m個中至多取p個；（7）x1+x2+…+xm>=p：m個中至少取p個；（8）xi>=xj：若第j個被選中，則第i個也被選中。思考：xi+xj>=xk表達的意思？？？【問題假設(shè)】（1）每個點最多建立一個門面。【符號設(shè)置】xi

點Ai建立的門面數(shù)，i=1,2,…,10，其中z表示年總利潤。根據(jù)問題敘述，總利潤為總投資額約束【建立模型】選擇約束：東區(qū)A1,A2,A3三個點至少選擇兩個:西區(qū)A4,A5兩個點至少選擇一個：南區(qū)A6,A7兩個點至少選擇一個：北區(qū)A8,A9,A10三個點至少選擇兩個：變量約束：【數(shù)學模型】s.t.

像這種決策變量只取0和1的線性規(guī)劃，稱為0-1線性規(guī)劃，屬于特殊的整數(shù)線性規(guī)劃，在實際問題中應用廣泛。軟件也能識別??！例11固定成本問題(變量交叉約束）

高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設(shè)備，制造一個容器的各種資源的數(shù)量如表1-3所示表1-3資源小號容器中號容器大號容器金屬板/t勞動力/（人/月）機器設(shè)備/（臺/月）221432843

不考慮固定費用，每種容器出售一只的利潤分別為4萬元，5萬元，6萬元，可使用的金屬板有500t，勞動力有300人/月，機器有100臺/月。

此外，只要生產(chǎn)，不管每種容器的制造數(shù)量是多少，都要支付一筆固定的費用，小號為100萬元，中號為150萬元，大號為200萬元。現(xiàn)在要制定一個月生產(chǎn)計劃，使