線性規(guī)劃模型,y,2、找出問題中所有的限制或約束，寫出未知變量的線性方程組或線性不等式組；,一、線性規(guī)劃模型,1、找出待定的未知變量（又稱為決策變量決策者自己可以控制的變量），并且用符號表示；,3、找出模型的目標函數(shù)：是以函數(shù)形式表示的決策者追求的目標寫出未知變量的線性方程或線性不等式,（一）建立線性規(guī)劃模型有三個基本步驟：,例（配料問題）某鑄造廠生產(chǎn)鑄件，每件需要20千克鉛，24千克銅和30千克鐵?，F(xiàn)有四種礦石可供選購，它們每10千克含有成分的質(zhì)量（千克）和價格（元）如圖。問：對每個鑄件來說，每種礦石各應(yīng)該選購多少，可以使總費用最少？試建立數(shù)學(xué)模型。,分析和建立模型,（1）確定決策變量：設(shè)為第i種礦石的選取的數(shù)量（單位10kg）；,（3）確定約束條件：選定的四種礦石的數(shù)量應(yīng)該滿足鑄件對三種成分的需求量，并且礦石數(shù)量應(yīng)該是非負的，即,每件需要20千克鉛，24千克銅和30千克鐵,綜合以上分析，得到配料問題的數(shù)學(xué)模型為：,受約束于,（二）線性規(guī)劃模型的結(jié)構(gòu)具有如下特性,（1）目標函數(shù)是決策變量的線性函數(shù)；,（2）約束條件是決策變量的線性等式或不等式；,具有以上結(jié)構(gòu)特點的模型就是線性規(guī)劃模型，記為LP（LinearProgramming），具有以下一般形式：,（三）線性規(guī)劃的標準模型,由于目標函數(shù)既可以是實現(xiàn)最大化，也可以是實現(xiàn)最小化，約束條件可以是等式，也可以是不等式，決策變量為非負或不受限制，這么復(fù)雜的情況，一定會給模型的求解帶來不便，為此引入標準形式,標準形式,（四）線性規(guī)劃數(shù)學(xué)模型標準形式的特點,2、約束條件均為線性；,3、決策變量及方程右端非負。,線性規(guī)劃數(shù)學(xué)模型標準形式可以有向量形式表示：,1、目標函數(shù)為最大化類型（有的書上為最小化）；,1、如果目標函數(shù)為最小化問題，則將目標函數(shù)兩邊乘以“-1”；,2、如果約束方程右端為負，在該方程兩端同乘以“-1”；,如果所建的模型不符合標準形式，則可以用適當方法化為標準形式，主要有：,3、如果約束為“”，則可以增加一個變量，在左端加上，這種變量稱為剩余變量；,4、如果約束為“”，則可以增加一個變量，在右端加上，這種變量要求非負，在線性規(guī)劃中均稱為松馳變量；,5、如果某決策變量無符號限制，則將每個換成,例：將下列線性規(guī)劃模型化為標準形式,化成標準形式為：,（一）基本概念：,1、可行解：所有滿足約束條件的解。,2、可行域：所有可行解組成的集合。,4、最優(yōu)值：對應(yīng)于最優(yōu)解的目標函數(shù)值。,3、最優(yōu)解：使得目標函數(shù)達到最優(yōu)值的可行解。,二、線性規(guī)劃問題的解及單純形法（解法）,5、基：約束方程組的系數(shù)矩陣為階的矩陣則稱A的任意一個階的非奇異子矩陣B為線性規(guī)劃的一個基。,6、基向量：組成基B的列向量稱為基向量。,7、基變量：基向量對應(yīng)的變量稱為基變量，基變量以外的變量稱為非基變量。,9、基可行解：滿足非負條件的基本解。,10、可行基：基可行解對應(yīng)的基。,11、基本最優(yōu)解：使目標函數(shù)達到最大值的基可行解。,12、最優(yōu)基：基本最優(yōu)解對應(yīng)的基。,8、基本解：在中，令非基變量全部為0，求出的一個解X，稱為基本解。,1、基本思想：首先找出一個基可行解，然后根據(jù)某種最優(yōu)性準則判斷該解是否為最優(yōu)，如果最優(yōu)，則結(jié)束；否則利用某種迭代規(guī)則尋找下一個基可行解，并且使下一個基可行解的目標函數(shù)值有所改變，反復(fù)多次，直到找出最優(yōu)解，或判斷出原問題無最優(yōu)解。,（二）單純形法,為了確定初始基可行解，需要先找出初始可行基。其方法是：觀察約束方程組系數(shù)矩陣，若其中有子塊為m階單位矩陣，則可將其選為初始可行基；否則，可采用所謂人工變量法尋找初始可行基。,（1）、確定初始基可行解并且計算相應(yīng)的目標函數(shù)值,2、計算步驟（3步）,若的前m列為單位陣（作為基），則約束方程可化為,令非基變量即得初始基可行解。,將方程組（1）代入目標函數(shù),故對應(yīng)于基可行解的目標函數(shù)值，于是原線性規(guī)劃模型等價于,此等價模型稱為原線性規(guī)劃的典式，其中稱為基本可行解的檢驗數(shù),（2）、根據(jù)檢驗數(shù)進行最優(yōu)性檢驗與解的判斷。,定理：若線性規(guī)劃的基可行解對應(yīng)的典式為（1）并且檢驗數(shù)為,、當存在某個檢驗數(shù)時，并且典式（1）中所有時，線性規(guī)劃無有限最優(yōu)解。,則、當時，是線性規(guī)劃的有限最優(yōu)解；,、當存在檢驗數(shù)且典式（1）中有些，這時采用迭代法實現(xiàn)基可行解的轉(zhuǎn)移。,當初始基可行解不是最優(yōu)解，并且不能判別無有限最優(yōu)解時，需要另找一個基可行解，并使相應(yīng)目標函數(shù)值增大，（即要對原可行基換一個列向量）。為此需要確定進基變量和出基變量的規(guī)則。,（3）通過換基迭代，實現(xiàn)基可行解的轉(zhuǎn)移,出基變量的規(guī)則：,為了使得目標函數(shù)值增加得較快，進基變量的取值使得目標函數(shù)值盡可能的大，出基變量取哪一個，通過準則來確定。,準則,反復(fù)進行以上步驟，即可獲得線性規(guī)劃的最優(yōu)解，或判斷出該線性規(guī)劃無有限最優(yōu)解。,其中對應(yīng)的系數(shù)。稱為主元素（又稱為中心元素），主元素所在行的基變量，就是要確定的出基變量。,單純形表：單純形法的求解過程實際上是在一系列表格上進行的。從這些表格上可以得到基本可行解、檢驗數(shù)等信息。這些表格稱為單純形表。每個表相當于一個矩陣，每次迭代就是對矩陣進行初等行變換。,例：求解線性規(guī)劃問題的最優(yōu)解,解：（1）構(gòu)造初始單純單純形表（第1、4、5列構(gòu)成的矩陣可逆）所以可取,為初始基可行解。因目標函數(shù)不是典式，故將代入目標函數(shù)z，整理得（典式）其中，6為的目標函數(shù)值，此時可以列出單純形表（如圖）。,（2）迭代求新的基可行解及其檢驗數(shù),從上表格中可以看出，檢驗數(shù)大于0，不滿足最優(yōu)性準則，須迭代求新解。取最大的檢驗數(shù)對應(yīng)的變量為進基變量。它取代誰呢？再由準則，用表格最右側(cè)元素分別與表格中所在列的各元素去比，求最小值,最小值4對應(yīng)表格中基變量為，故為出基變量，元素為中心元素。,開始迭代，將所在列元素變?yōu)閱挝幌蛄浚瑱z驗數(shù)行也參加變換。同時將表格左側(cè)列中基變量換成得表（把x3所在的元素化為1，然后再把其它行的元素化為零）,令得第二個基可行解,表格的右下角說明，當前的目標值為14，目標值增量為8，另外上面的表格中仍然有仍然需要迭代求新解。,繼續(xù)迭代,取為進基變量，并且用上表格最右端列元素比上所在列相應(yīng)元素，計算,最小比值對應(yīng)上表中基變量所在的行，故為出基變量，中心元素為，同上述方法可知為進基變量，于是得到下面的表格,表格的右下角說明，當前的目標值為14.5，目標值增量為0.5，,下面利用LINGO軟件求解,LINGO9.0,LINGO初始界面,LINGO程序,LINGO程序運行,變量數(shù)量,變量總數(shù),非線性變量數(shù),整數(shù)變量數(shù),約束數(shù)量,約束總數(shù),非線性約束個數(shù),非零系數(shù)數(shù)量,總數(shù),非線性項的系數(shù)個數(shù),內(nèi)存使用量,求解花費的時間,當前模型的類型,當前解的狀態(tài),當前解的目標函數(shù)值,求解器（求解程序）狀態(tài)框,當前約束不滿足的總量（不是不滿足的約束的個數(shù)）實數(shù)時該值為0,到目前為止迭代次數(shù),使用的特殊求解程序,擴展的求解器狀態(tài)框（求解程序）狀態(tài)框,到目前為止找到的可行解的最佳目標函數(shù)值,目標函數(shù)值的界,特殊求解程序當前運行步數(shù),有效步數(shù),刷新本界面的時間間隔（秒）,目標函數(shù)值,求解迭代次數(shù),決策變量,非基變量,基變量,給出最優(yōu)的單純形表中目標函數(shù)行變量對應(yīng)的系數(shù)（即各個變量的檢驗數(shù)，基變量為0，非基變量對應(yīng)的值表示當該非基變量增加一個單位時目標函數(shù)減少的量（對max型問題）,例1加工奶制品的生產(chǎn)計劃,問題：一奶制品加工廠用牛奶生產(chǎn)A1，A2兩種奶制品，1桶牛奶可以在甲類設(shè)備上用12小時加工成3公斤A1，或者在乙類設(shè)備上用8小時加工成4公斤A2。根據(jù)市場需求，生產(chǎn)的A1，A2全部能夠售出，且每公斤A1獲利24元，每公斤A2獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動時間為480小時，并且甲類設(shè)備每天至多能加工100公斤A1，乙類設(shè)備的加工能力沒有限制。試為該廠制訂一個生產(chǎn)計劃，使每天獲利最大？并且進一步討論以下3個問題：,1）若有35元可以買到1桶牛奶，應(yīng)否作這項投資？若投資，每天最多購買多少桶牛奶？2）若可以聘用臨時工人增加勞動時間，付給臨時工人的工資最多是每小時幾元？3）由于市場需求變化，每公斤A1的獲利增加到30元，應(yīng)否改變生產(chǎn)計劃？,問題分析：這個優(yōu)化問題的目標是使每天的獲利最大，要作的決策是生產(chǎn)計劃，即每天用多少桶牛奶生產(chǎn)A1，用多少桶牛奶生產(chǎn)A2，決策受3個條件的限制：原料（牛奶）供應(yīng)，勞動時間、甲類設(shè)備的加工能力。將決策變量、目標函數(shù)和約束條件用數(shù)學(xué)式子表示出來，就得到相應(yīng)的數(shù)學(xué)模型。,決策變量：設(shè)每天用x1桶牛奶生產(chǎn)A1，用x2桶牛奶生產(chǎn)A2。,目標函數(shù)：設(shè)每天獲利為z元，x1桶牛奶生產(chǎn)3x1公斤A1，獲利24*3x1，x2桶牛奶生產(chǎn)4x2公斤A2，獲利16*4x2，所以z=72*x1+64*x2。,約束條件：原料供應(yīng)生產(chǎn)A1，A2的原料總量不得超過每天的供應(yīng)，即x1+x2=50;,勞動時間生產(chǎn)A1，A2的原料總加工時間不得超過每天正式工人總的勞動時間，即12*x1+8*x2=0；,數(shù)學(xué)模型：,給出最優(yōu)的單純形表中目標函數(shù)行變量對應(yīng)的系數(shù)（即各個變量的檢驗數(shù)，基變量為0，非基變量對應(yīng)的值表示當該非基變量增加一個單位時目標函數(shù)減少的量（對max型問題）,約束條件的右段通常看作資源，一般稱“資源”剩余為零的約束為緊約束（有效約束）；目標函數(shù)看作“效益”成為緊約束的資源一旦增加，“效益必然跟著增加”,LINDO6.1,LINDO程序,靈敏性分析嗎,表示單純形法在兩次迭代后得到最優(yōu)解,表示最優(yōu)目標值為3360（在LINDO中目標函數(shù)所在的行總是被認為是第一行）,給出最優(yōu)的單純形表中目標函數(shù)行變量對應(yīng)的系數(shù)（即各個變量的檢驗數(shù)，基變量為0，非基變量對應(yīng)的值表示當該非基變量增加一個單位時目標函數(shù)減少的量（對max型問題）,松弛或剩余（給出約束對應(yīng)的松弛變量的值。第2、3行松弛變量為0，說明兩個約束都是緊約束）,給出影子價格的值,表示用單純形法進行了兩次迭代,目標函數(shù)的系數(shù)和約束條件右端項在什么范圍變化時，最優(yōu)基保持不變,目標函數(shù)中系數(shù)變化的范圍,最優(yōu)基：基本最優(yōu)解對應(yīng)的基。,目標函數(shù)中變量當前的系數(shù),目標函數(shù)的系數(shù)允許增加的幅度，最優(yōu)基保持不變,目標函數(shù)的系數(shù)允許減少的幅度，最優(yōu)基保持不變,約束條件中當前的右端項最優(yōu)基保持不變,約束條件中當前的右端項允許變化的范圍，最優(yōu)基保持不變,約束條件中右端項允許增加的幅度最優(yōu)基保持不變,約束條件中右端項允許減少的幅度，最優(yōu)基保持不變,INFINITY表示正無窮大,問題：例1給出的A1、A2兩類奶制品的生產(chǎn)條件、利潤，及工廠的資源限制全都不變。為了增加工廠的利潤，開發(fā)了奶制品的深加工技術(shù)：用2個時間和3元加工費，可將1公斤A1加工成0.8公斤高級奶制品B1，也可以將1公斤A2加工成0.75公斤高級奶制品B2，每公斤B1能獲利44元，每公斤B2能獲利32元。試為該廠制訂一個生產(chǎn)銷售計劃，使每天的凈利潤最大，并且討論以下問題：,例2奶制品的生產(chǎn)銷售計劃,1）：若投資30元可以增加供應(yīng)1桶牛奶，投資3元可以增加1小時勞動時間，應(yīng)否作這項投資？如每天投資150元，可以賺回多少？2）：每公斤高級奶制品B1、B2的獲利經(jīng)常有10%的波動，對制訂的生產(chǎn)銷售計劃有無影響？若每公斤B1的獲利下降10%，計劃應(yīng)該變化嗎？,教材P83例奶制品的生產(chǎn)銷售計劃程序,LINGO程序,LINDO程序,三、整數(shù)線性規(guī)劃模型,變量取整數(shù)的線性規(guī)劃稱為整數(shù)線性規(guī)劃，簡稱整數(shù)線性規(guī)劃，記為IP。,整數(shù)規(guī)劃分為純整數(shù)線性規(guī)劃，記為PILP；混合整數(shù)規(guī)劃，記為MILP,整數(shù)規(guī)劃的特殊情況是0-1規(guī)劃，其變量只取0或者1,1、整數(shù)規(guī)劃模型及分枝定界法,由于整數(shù)規(guī)劃模型比線性規(guī)劃模型增加了取整的條件，所以一種自然的想法是利用線性規(guī)劃的方法求解整數(shù)規(guī)劃模型。但如直接對線性規(guī)劃問題最優(yōu)解取整往往得不到整數(shù)規(guī)劃的最優(yōu)解。因為對線性規(guī)劃問題最優(yōu)解取整以后，有時會破壞原問題的約束條件，但解卻不是最優(yōu)解。下面介紹對于純整數(shù)和混合整數(shù)規(guī)劃都適用的分枝定界法,分枝定界法的一般步驟：,（1）稱原整數(shù)規(guī)劃問題為A；不考慮整數(shù)條件，相應(yīng)的線性規(guī)劃問題為B；,（2）解問題B，如問題B無可行解，則停止，原問題A也無可行解；,（3）如求得問題B的最優(yōu)解，檢查它是否符合整數(shù)條件，如果滿足整數(shù)條件，它就是問題A的最優(yōu)解；如不滿足整數(shù)條件，轉(zhuǎn)下一步；,（5）不考慮整數(shù)條件解這兩個后繼問題；,（6）在現(xiàn)有并且還未分解出各后繼問題的各可行解中，選擇目標函數(shù)值為最優(yōu)的問題，重新稱該問題為B，轉(zhuǎn)（3）。,首先不考慮整數(shù)的條件，求解線性規(guī)劃，得最優(yōu)解：,任意選擇非整數(shù)解變量。如，由于，問題的解要求整數(shù)，所以分出兩個約束。從而把原問題分成兩個子問題：,對子問題S1、S2，不考慮整數(shù)條件，得最優(yōu)解,這兩個仍然不滿足整數(shù)的要求。所以繼續(xù)對（S1）和（S2）分解。由于（S1）的最優(yōu)值Z=349.000比，（S2）的最優(yōu)值Z=341.390大，所以先對（S1）進行分解。由于不滿足整數(shù)要求，所以,所以添加條件把（S1）分解成兩個后繼問題（S11）和（S12）。依次類推得到最優(yōu)解或判斷無最優(yōu)解。,上述思想是分支定界的理論，但在利用數(shù)學(xué)軟件求解時可以省去。,上述整數(shù)線性規(guī)劃模型的LINGO程序,問題1.如何下料最節(jié)省?,例鋼管下料,問題2.客戶增加需求：,節(jié)省的標準是什么？,由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)省？,按照客戶需要在一根原料鋼管上安排切割的一種組合。,切割模式,合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸,合理切割模式,鋼管下料問題1：,為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)省？,2.所用原料鋼管總根數(shù)最少,兩種標準,1.原料鋼管剩余總余量最小,xi表示按第i種模式切割的原料鋼管根數(shù)(i=1,2,7),決策變量,目標1（總余量）,按模式2切割12根,按模式5切割15根，余料27米,最優(yōu)解：x2=12,x5=15,其余為0；最優(yōu)值：27。,相應(yīng)的LINGO程序,目標2（總根數(shù)）,約束條件不變,最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。,xi為整數(shù),相應(yīng)的LINGO程序,鋼管下料問題2,對大規(guī)模問題，用模型的約束條件界定合理模式,增加一種需求：5米10根；切割模式不超過3種。,現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復(fù)雜。,決策變量,xi表示按第i種模式切割的原料鋼管根數(shù)(i=1,2,3),r1i,r2i,r3i,r4i表示第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長的鋼管的數(shù)量,目標函數(shù)（總根數(shù)）,約束條件,模式合理：每根余料不超過3米,上述問題屬于整數(shù)非線性規(guī)劃模型，模型求解比較困難，為此再引入適當?shù)募s束條件：,整數(shù)約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數(shù),增加約束，縮小可行域，便于求解,由于每根原料鋼管長19米原料鋼管總根數(shù)下界：,需求：4米50根，5米10根，6米20根，8米15根,特殊生產(chǎn)計劃：對每根原料鋼管模式1：切割成50根4米鋼管，需13根；模式2：切割成10根5米和20根6米鋼管，需10根；模式3：切割成15根8米鋼管，需8根。原料鋼管總根數(shù)上界：13+10+8=31,模式排列順序可任定,LINGO程序,LINGO求解整數(shù)非線性規(guī)劃模型,Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000,模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數(shù)為28根。,板材規(guī)格2：長方形，3228cm，2萬張。,例易拉罐下料,板材規(guī)格1：正方形，邊長24cm，5萬張。,每周工作40小時，每只易拉罐利潤0.10元，原料余料損失0.001元/cm2（不能裝配的罐身、蓋、底也是余料）,如何安排每周生產(chǎn)？,罐身高10cm，上蓋、下底直徑均5cm。,模式1:正方形的邊長24cm,問題分析,計算各種模式下的余料損失,上、下底直徑d=5cm，罐身高h=10cm。,模式1余料損失242-10d2/4-dh=222.6cm2,問題分析,目標:易拉罐利潤扣除原料余料損失后的凈利潤最大,約束：每周工作時間不超過40小時；原料數(shù)量：規(guī)格1（模式13）5萬張，規(guī)格2（模式4）2萬張；罐身和底、蓋的配套組裝。,注意：不能裝配的罐身、上下底也是余料,決策變量,xi按照第i種模式的生產(chǎn)張數(shù)(i=1,2,3,4)；y1一周生產(chǎn)的易拉罐個數(shù)；y2不配套的罐身個數(shù)；y3不配套的底、蓋個數(shù)。,每只易拉罐利潤0.10元，余料損失0.001元/cm2,罐身面積dh=157.1cm2，底蓋面積d2/4=19.6cm2,目標函數(shù),約束條件,原料約束,約束條件,配套約束,雖然xi和y1，y2，y3應(yīng)是整數(shù)，但是因生產(chǎn)量很大，可以把它們看成實數(shù)，從而用線性規(guī)劃模型處理。,將所有決策變量擴大1