線性規(guī)劃模型課件

線性規(guī)劃模型

y線性規(guī)劃模型y2、找出問題中所有的限制或約束，寫出未知變量的線性方程組或線性不等式組；一、線性規(guī)劃模型1、找出待定的未知變量（又稱為決策變量——決策者自己可以控制的變量），并且用符號(hào)表示；3、找出模型的目標(biāo)函數(shù)：是以函數(shù)形式表示的決策者追求的目標(biāo)寫出未知變量的線性方程或線性不等式（一）建立線性規(guī)劃模型有三個(gè)基本步驟：2、找出問題中所有的限制或約束，寫出未知變量的線性方

例（配料問題）某鑄造廠生產(chǎn)鑄件，每件需要20千克鉛，24千克銅和30千克鐵?，F(xiàn)有四種礦石可供選購(gòu)，它們每10千克含有成分的質(zhì)量（千克）和價(jià)格（元）如圖。問：對(duì)每個(gè)鑄件來說，每種礦石各應(yīng)該選購(gòu)多少，可以使總費(fèi)用最少？試建立數(shù)學(xué)模型。例（配料問題）某鑄造廠生產(chǎn)鑄件，每件需要20千克鉛線性規(guī)劃模型ppt課件分析和建立模型

（1）確定決策變量：設(shè)為第i種礦石的選取的數(shù)量（單位10kg）；

（2）確定目標(biāo)函數(shù)：目標(biāo)應(yīng)該是使得總費(fèi)用最小，即達(dá)到最?。环治龊徒⒛Ｐ停?）確定決策變量：設(shè)（3）確定約束條件：選定的四種礦石的數(shù)量應(yīng)該滿足鑄件對(duì)三種成分的需求量，并且礦石數(shù)量應(yīng)該是非負(fù)的，即每件需要20千克鉛，24千克銅和30千克鐵（3）確定約束條件：選定的四種礦石的數(shù)量應(yīng)該滿足鑄件對(duì)綜合以上分析，得到配料問題的數(shù)學(xué)模型為：受約束于綜合以上分析，得到配料問題的數(shù)學(xué)模型為：受約束于（二）線性規(guī)劃模型的結(jié)構(gòu)具有如下特性（1）目標(biāo)函數(shù)是決策變量的線性函數(shù)；（2）約束條件是決策變量的線性等式或不等式；（二）線性規(guī)劃模型的結(jié)構(gòu)具有如下特性（1）目標(biāo)函數(shù)是決具有以上結(jié)構(gòu)特點(diǎn)的模型就是線性規(guī)劃模型，記為L(zhǎng)P（LinearProgramming），具有以下一般形式：具有以上結(jié)構(gòu)特點(diǎn)的模型就是線性規(guī)劃模型，記為L(zhǎng)P（L（三）線性規(guī)劃的標(biāo)準(zhǔn)模型

由于目標(biāo)函數(shù)既可以是實(shí)現(xiàn)最大化，也可以是實(shí)現(xiàn)最小化，約束條件可以是等式，也可以是不等式，決策變量為非負(fù)或不受限制，這么復(fù)雜的情況，一定會(huì)給模型的求解帶來不便，為此引入標(biāo)準(zhǔn)形式（三）線性規(guī)劃的標(biāo)準(zhǔn)模型由于目標(biāo)函數(shù)既可以是實(shí)現(xiàn)最標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式

（四）線性規(guī)劃數(shù)學(xué)模型標(biāo)準(zhǔn)形式的特點(diǎn)2、約束條件均為線性；3、決策變量及方程右端非負(fù)。線性規(guī)劃數(shù)學(xué)模型標(biāo)準(zhǔn)形式可以有向量形式表示：1、目標(biāo)函數(shù)為最大化類型（有的書上為最小化）；（四）線性規(guī)劃數(shù)學(xué)模型標(biāo)準(zhǔn)形式的特點(diǎn)2、

1、如果目標(biāo)函數(shù)為最小化問題，則將目標(biāo)函數(shù)兩邊乘以“-1”；2、如果約束方程右端為負(fù)，在該方程兩端同乘以“-1”；

如果所建的模型不符合標(biāo)準(zhǔn)形式，則可以用適當(dāng)方法化為標(biāo)準(zhǔn)形式，主要有：3、如果約束為“≥”，則可以增加一個(gè)變量，在左端加上，這種變量稱為剩余變量；1、如果目標(biāo)函數(shù)為最小化問題，則將目標(biāo)函4、如果約束為“≤”，則可以增加一個(gè)變量，在右端加上，這種變量要求非負(fù)，在線性規(guī)劃中均稱為松馳變量；5、如果某決策變量無(wú)符號(hào)限制，則將每個(gè)換成

4、如果約束為“≤”，則可以增加一個(gè)變量例：將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式例：將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式化成標(biāo)準(zhǔn)形式為：化成標(biāo)準(zhǔn)形式為：（一）基本概念：1、可行解：所有滿足約束條件的解。2、可行域：所有可行解組成的集合。4、最優(yōu)值：對(duì)應(yīng)于最優(yōu)解的目標(biāo)函數(shù)值。3、最優(yōu)解：使得目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解。二、線性規(guī)劃問題的解及單純形法（解法）（一）基本概念：1、可行解：所有滿足約束條件5、基：約束方程組的系數(shù)矩陣為階的矩陣則稱A的任意一個(gè)階的非奇異子矩陣B為線性規(guī)劃的一個(gè)基。6、基向量：組成基B的列向量

稱為基向量。7、基變量：基向量對(duì)應(yīng)的變量稱為基變量，基變量以外的變量稱為非基變量。5、基：約束方程組的系數(shù)矩陣為9、基可行解：滿足非負(fù)條件的基本解。10、可行基：基可行解對(duì)應(yīng)的基。11、基本最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的基可行解。12、最優(yōu)基：基本最優(yōu)解對(duì)應(yīng)的基。8、基本解：在中，令非基變量全部為0，求出的一個(gè)解X，稱為基本解。9、基可行解：滿足非負(fù)條件

1、基本思想：首先找出一個(gè)基可行解，然后根據(jù)某種最優(yōu)性準(zhǔn)則判斷該解是否為最優(yōu)，如果最優(yōu)，則結(jié)束；否則利用某種迭代規(guī)則尋找下一個(gè)基可行解，并且使下一個(gè)基可行解的目標(biāo)函數(shù)值有所改變，反復(fù)多次，直到找出最優(yōu)解，或判斷出原問題無(wú)最優(yōu)解。（二）單純形法1、基本思想：首先找出一個(gè)基可行解，然后根據(jù)某種最

為了確定初始基可行解，需要先找出初始可行基。其方法是：觀察約束方程組系數(shù)矩陣，若其中有子塊為m階單位矩陣，則可將其選為初始可行基；否則，可采用所謂人工變量法尋找初始可行基。

（1）、確定初始基可行解并且計(jì)算相應(yīng)的目標(biāo)函數(shù)值2、計(jì)算步驟（3步）為了確定初始基可行解，需要先找出初始可行基若的前m列為單位陣（作為基），則約束方程可化為

為基變量，為非基變量若的前m列為單位陣（作為基），則約束方程令非基變量即得初始基可行解。將方程組（1）代入目標(biāo)函數(shù)令非基變量即得初始故對(duì)應(yīng)于基可行解的目標(biāo)函數(shù)值，于是原線性規(guī)劃模型等價(jià)于故對(duì)應(yīng)于基可行解的目標(biāo)函數(shù)值，于是原此等價(jià)模型稱為原線性規(guī)劃的典式，其中稱為基本可行解的檢驗(yàn)數(shù)此等價(jià)模型稱為原線性規(guī)劃的典式，其中

（2）、根據(jù)檢驗(yàn)數(shù)進(jìn)行最優(yōu)性檢驗(yàn)與解的判斷。

定理：若線性規(guī)劃的基可行解對(duì)應(yīng)的典式為（1）并且檢驗(yàn)數(shù)為（2）、根據(jù)檢驗(yàn)數(shù)②、當(dāng)存在某個(gè)檢驗(yàn)數(shù)時(shí)，并且典式（1）中所有時(shí)，線性規(guī)劃無(wú)有限最優(yōu)解。

則①、當(dāng)時(shí)，是線性規(guī)劃的有限最優(yōu)解；③、當(dāng)存在檢驗(yàn)數(shù)且典式（1）中有些，這時(shí)采用迭代法實(shí)現(xiàn)基可行解的轉(zhuǎn)移。②、當(dāng)存在某個(gè)檢驗(yàn)數(shù)當(dāng)初始基可行解不是最優(yōu)解，并且不能判別無(wú)有限最優(yōu)解時(shí)，需要另找一個(gè)基可行解，并使相應(yīng)目標(biāo)函數(shù)值增大，（即要對(duì)原可行基換一個(gè)列向量）。為此需要確定進(jìn)基變量和出基變量的規(guī)則。（3）通過換基迭代，實(shí)現(xiàn)基可行解的轉(zhuǎn)移當(dāng)初始基可行解不是最優(yōu)解，并且不能判別無(wú)有限最

①進(jìn)基變量的規(guī)則：當(dāng)某個(gè)時(shí)，增加可以使得目標(biāo)函數(shù)值增加，故將作為進(jìn)基變量。當(dāng)有兩個(gè)以上的時(shí)，一般選擇最大對(duì)應(yīng)的變量為進(jìn)基變量①進(jìn)基變量的規(guī)則：當(dāng)某個(gè)時(shí)，增加

②出基變量的規(guī)則：為了使得目標(biāo)函數(shù)值增加得較快，進(jìn)基變量的取值使得目標(biāo)函數(shù)值盡可能的大，出基變量取哪一個(gè)，通過準(zhǔn)則來確定。

準(zhǔn)則②出基變量的規(guī)則：為了使得目標(biāo)函數(shù)值增加得較快，進(jìn)基反復(fù)進(jìn)行以上步驟，即可獲得線性規(guī)劃的最優(yōu)解，或判斷出該線性規(guī)劃無(wú)有限最優(yōu)解。其中對(duì)應(yīng)的系數(shù)。稱為主元素（又稱為中心元素），主元素所在行的基變量，就是要確定的出基變量。反復(fù)進(jìn)行以上步驟，即可獲得線性規(guī)劃的最優(yōu)解，或判斷出

單純形表：?jiǎn)渭冃畏ǖ那蠼膺^程實(shí)際上是在一系列表格上進(jìn)行的。從這些表格上可以得到基本可行解、檢驗(yàn)數(shù)等信息。這些表格稱為單純形表。每個(gè)表相當(dāng)于一個(gè)矩陣，每次迭代就是對(duì)矩陣進(jìn)行初等行變換。單純形表：?jiǎn)渭冃畏ǖ那蠼膺^程實(shí)際上是在一系列表格上進(jìn)

例：求解線性規(guī)劃問題的最優(yōu)解例：求解線性規(guī)劃問題的最優(yōu)解解：（1）構(gòu)造初始單純單純形表（第1、4、5列構(gòu)成的矩陣可逆）所以可取為初始基可行解。因目標(biāo)函數(shù)不是典式，故將代入目標(biāo)函數(shù)z，整理得（典式）其中，6為的目標(biāo)函數(shù)值，此時(shí)可以列出單純形表（如圖）。解：（1）構(gòu)造初始單純單純形表（第1、4、5列構(gòu)成的線性規(guī)劃模型ppt課件（2）迭代求新的基可行解及其檢驗(yàn)數(shù)從上表格中可以看出，檢驗(yàn)數(shù)大于0，不滿足最優(yōu)性準(zhǔn)則，須迭代求新解。取最大的檢驗(yàn)數(shù)對(duì)應(yīng)的變量為進(jìn)基變量。它取代誰(shuí)呢？再由準(zhǔn)則，用表格最右側(cè)元素分別與表格中所在列的各元素去比，求最小值（2）迭代求新的基可行解及其檢驗(yàn)數(shù)從上表格中可以看出最小值4對(duì)應(yīng)表格中基變量為，故為出基變量，元素為中心元素。

開始迭代，將所在列元素變?yōu)閱挝幌蛄?，檢驗(yàn)數(shù)行也參加變換。同時(shí)將表格左側(cè)列中基變量換成得表（把x3所在的元素化為1，然后再把其它行的元素化為零）最小值4對(duì)應(yīng)表格中基變量為，故為線性規(guī)劃模型ppt課件令得第二個(gè)基可行解表格的右下角說明，當(dāng)前的目標(biāo)值為14，目標(biāo)值增量為8，另外上面的表格中仍然有仍然需要迭代求新解。令繼續(xù)迭代

取為進(jìn)基變量，并且用上表格最右端列元素比上所在列相應(yīng)元素，計(jì)算最小比值對(duì)應(yīng)上表中基變量所在的行，故為出基變量，中心元素為，同上述方法可知為進(jìn)基變量，于是得到下面的表格

表格的右下角說明，當(dāng)前的目標(biāo)值為14.5，目標(biāo)值增量為0.5，繼續(xù)迭代取為進(jìn)基變量，并且用上表格最右端列元表格3中檢驗(yàn)數(shù)，故得最優(yōu)解為：最優(yōu)值為：14.5表格3中檢驗(yàn)數(shù)，故得最優(yōu)解為：最優(yōu)值下面利用LINGO軟件求解下面利用LINGO軟件求解LINGO9.0LINGO9.0LINGO初始界面LINGO初始界面LINGO程序LINGO程序LINGO程序運(yùn)行LINGO程序運(yùn)行線性規(guī)劃模型ppt課件變量數(shù)量變量總數(shù)非線性變量數(shù)整數(shù)變量數(shù)變量數(shù)量變量總數(shù)非線性變量數(shù)整數(shù)變量數(shù)約束數(shù)量約束總數(shù)非線性約束個(gè)數(shù)約束數(shù)量約束總數(shù)非線性約束個(gè)數(shù)非零系數(shù)數(shù)量總數(shù)非線性項(xiàng)的系數(shù)個(gè)數(shù)非零系數(shù)數(shù)量總數(shù)非線性項(xiàng)的系數(shù)個(gè)數(shù)內(nèi)存使用量求解花費(fèi)的時(shí)間當(dāng)前模型的類型當(dāng)前解的狀態(tài)當(dāng)前解的目標(biāo)函數(shù)值求解器（求解程序）狀態(tài)框內(nèi)存使用量求解花費(fèi)的時(shí)間當(dāng)前模型的類型當(dāng)前解的狀態(tài)當(dāng)前解的目當(dāng)前約束不滿足的總量（不是不滿足的約束的個(gè)數(shù)）實(shí)數(shù)時(shí)該值為0到目前為止迭代次數(shù)當(dāng)前約束不滿足的總量（不是不滿足的約束的個(gè)數(shù)）實(shí)數(shù)時(shí)該值為0使用的特殊求解程序擴(kuò)展的求解器狀態(tài)框（求解程序）狀態(tài)框到目前為止找到的可行解的最佳目標(biāo)函數(shù)值使用的特殊求解程序擴(kuò)展的求解器狀態(tài)框（求解程序）狀態(tài)框到目前目標(biāo)函數(shù)值的界特殊求解程序當(dāng)前運(yùn)行步數(shù)有效步數(shù)刷新本界面的時(shí)間間隔（秒）目標(biāo)函數(shù)值的界特殊求解程序當(dāng)前運(yùn)行步數(shù)有效步數(shù)刷新本界面的時(shí)目標(biāo)函數(shù)值求解迭代次數(shù)決策變量非基變量基變量給出最優(yōu)的單純形表中目標(biāo)函數(shù)行變量對(duì)應(yīng)的系數(shù)（即各個(gè)變量的檢驗(yàn)數(shù)，基變量為0，非基變量對(duì)應(yīng)的值表示當(dāng)該非基變量增加一個(gè)單位時(shí)目標(biāo)函數(shù)減少的量（對(duì)max型問題））目標(biāo)函數(shù)值求解迭代次數(shù)決策變量非基變量基變量給出最優(yōu)的單純形例1加工奶制品的生產(chǎn)計(jì)劃問題：一奶制品加工廠用牛奶生產(chǎn)A1，A2兩種奶制品，1桶牛奶可以在甲類設(shè)備上用12小時(shí)加工成3公斤A1，或者在乙類設(shè)備上用8小時(shí)加工成4公斤A2。根據(jù)市場(chǎng)需求，生產(chǎn)的A1，A2全部能夠售出，且每公斤A1獲利24元，每公斤A2獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動(dòng)時(shí)間為480小時(shí)，并且甲類設(shè)備每天至多能加工100公斤A1，乙類設(shè)備的加工能力沒有限制。試為該廠制訂一個(gè)生產(chǎn)計(jì)劃，使每天獲利最大？并且進(jìn)一步討論以下3個(gè)問題：例1加工奶制品的生產(chǎn)計(jì)劃問題：一奶制品加工廠用牛奶生產(chǎn)A1

1）若有35元可以買到1桶牛奶，應(yīng)否作這項(xiàng)投資？若投資，每天最多購(gòu)買多少桶牛奶？2）若可以聘用臨時(shí)工人增加勞動(dòng)時(shí)間，付給臨時(shí)工人的工資最多是每小時(shí)幾元？3）由于市場(chǎng)需求變化，每公斤A1的獲利增加到30元，應(yīng)否改變生產(chǎn)計(jì)劃？1）若有35元可以買到1桶牛奶，應(yīng)否作這項(xiàng)投資？若投問題分析：這個(gè)優(yōu)化問題的目標(biāo)是使每天的獲利最大，要作的決策是生產(chǎn)計(jì)劃，即每天用多少桶牛奶生產(chǎn)A1，用多少桶牛奶生產(chǎn)A2，決策受3個(gè)條件的限制：原料（牛奶）供應(yīng)，勞動(dòng)時(shí)間、甲類設(shè)備的加工能力。將決策變量、目標(biāo)函數(shù)和約束條件用數(shù)學(xué)式子表示出來，就得到相應(yīng)的數(shù)學(xué)模型。問題分析：這個(gè)優(yōu)化問題的目標(biāo)是使每天的獲利最大，要作的決策是決策變量：設(shè)每天用x1桶牛奶生產(chǎn)A1，用x2桶牛奶生產(chǎn)A2。目標(biāo)函數(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;決策變量：設(shè)每天用x1桶牛奶生產(chǎn)A1，用x2桶牛奶生產(chǎn)勞動(dòng)時(shí)間生產(chǎn)A1，A2的原料總加工時(shí)間不得超過每天正式工人總的勞動(dòng)時(shí)間，即12*x1+8*x2<=480；設(shè)備能力A1的產(chǎn)量不得超過甲類設(shè)備的加工能力，即3*x1<=100；非負(fù)約束x1>=0x2>=0；勞動(dòng)時(shí)間生產(chǎn)A1，A2的原料總加工時(shí)間不得超過每數(shù)學(xué)模型：數(shù)學(xué)模型：線性規(guī)劃模型ppt課件給出最優(yōu)的單純形表中目標(biāo)函數(shù)行變量對(duì)應(yīng)的系數(shù)（即各個(gè)變量的檢驗(yàn)數(shù)，基變量為0，非基變量對(duì)應(yīng)的值表示當(dāng)該非基變量增加一個(gè)單位時(shí)目標(biāo)函數(shù)減少的量（對(duì)max型問題））約束條件的右段通?？醋髻Y源，一般稱“資源”剩余為零的約束為緊約束（有效約束）；目標(biāo)函數(shù)看作“效益”成為緊約束的資源一旦增加，“效益必然跟著增加”給出最優(yōu)的單純形表中目標(biāo)函數(shù)行變量對(duì)應(yīng)的系數(shù)（即各個(gè)變量的檢線性規(guī)劃模型ppt課件線性規(guī)劃模型ppt課件LINDO6.1LINDO6.1LINDO程序LINDO程序線性規(guī)劃模型ppt課件靈敏性分析嗎靈敏性分析嗎表示單純形法在兩次迭代后得到最優(yōu)解表示最優(yōu)目標(biāo)值為3360（在LINDO中目標(biāo)函數(shù)所在的行總是被認(rèn)為是第一行）給出最優(yōu)的單純形表中目標(biāo)函數(shù)行變量對(duì)應(yīng)的系數(shù)（即各個(gè)變量的檢驗(yàn)數(shù)，基變量為0，非基變量對(duì)應(yīng)的值表示當(dāng)該非基變量增加一個(gè)單位時(shí)目標(biāo)函數(shù)減少的量（對(duì)max型問題））表示單純形法在兩次迭代后得到最優(yōu)解表示最優(yōu)目標(biāo)值為3360（松弛或剩余（給出約束對(duì)應(yīng)的松弛變量的值。第2、3行松弛變量為0，說明兩個(gè)約束都是緊約束）給出影子價(jià)格的值松弛或剩余（給出約束對(duì)應(yīng)的松弛變量的值。第2、3行松弛變量為表示用單純形法進(jìn)行了兩次迭代目標(biāo)函數(shù)的系數(shù)和約束條件右端項(xiàng)在什么范圍變化時(shí)，最優(yōu)基保持不變目標(biāo)函數(shù)中系數(shù)變化的范圍最優(yōu)基：基本最優(yōu)解對(duì)應(yīng)的基。表示用單純形法進(jìn)行了兩次迭代目標(biāo)函數(shù)的系數(shù)和約束條件右端項(xiàng)在目標(biāo)函數(shù)中變量當(dāng)前的系數(shù)目標(biāo)函數(shù)的系數(shù)允許增加的幅度，最優(yōu)基保持不變目標(biāo)函數(shù)的系數(shù)允許減少的幅度，最優(yōu)基保持不變目標(biāo)函數(shù)中變量當(dāng)前的系數(shù)目標(biāo)函數(shù)的系數(shù)允許增加的幅度，最優(yōu)基約束條件中當(dāng)前的右端項(xiàng)最優(yōu)基保持不變約束條件中當(dāng)前的右端項(xiàng)允許變化的范圍，最優(yōu)基保持不變約束條件中右端項(xiàng)允許增加的幅度最優(yōu)基保持不變約束條件中當(dāng)前的右端項(xiàng)最優(yōu)基保持不變約束條件中當(dāng)前的右端項(xiàng)允約束條件中右端項(xiàng)允許減少的幅度，最優(yōu)基保持不變INFINITY表示正無(wú)窮大約束條件中右端項(xiàng)允許減少的幅度，最優(yōu)基保持不變INFINIT問題：例1給出的A1、A2兩類奶制品的生產(chǎn)條件、利潤(rùn)，及工廠的資源限制全都不變。為了增加工廠的利潤(rùn)，開發(fā)了奶制品的深加工技術(shù)：用2個(gè)時(shí)間和3元加工費(fèi)，可將1公斤A1加工成0.8公斤高級(jí)奶制品B1，也可以將1公斤A2加工成0.75公斤高級(jí)奶制品B2，每公斤B1能獲利44元，每公斤B2能獲利32元。試為該廠制訂一個(gè)生產(chǎn)銷售計(jì)劃，使每天的凈利潤(rùn)最大，并且討論以下問題：例2奶制品的生產(chǎn)銷售計(jì)劃問題：例1給出的A1、A2兩類奶制品的生產(chǎn)條件、利潤(rùn)，及工廠1）：若投資30元可以增加供應(yīng)1桶牛奶，投資3元可以增加1小時(shí)勞動(dòng)時(shí)間，應(yīng)否作這項(xiàng)投資？如每天投資150元，可以賺回多少？2）：每公斤高級(jí)奶制品B1、B2的獲利經(jīng)常有10%的波動(dòng)，對(duì)制訂的生產(chǎn)銷售計(jì)劃有無(wú)影響？若每公斤B1的獲利下降10%，計(jì)劃應(yīng)該變化嗎？1）：若投資30元可以增加供應(yīng)1桶牛奶，投資3元可以增加1小教材P83例奶制品的生產(chǎn)銷售計(jì)劃程序LINGO程序教材P83例奶制品的生產(chǎn)銷售計(jì)劃程序LINGO程序線性規(guī)劃模型ppt課件LINDO程序LINDO程序線性規(guī)劃模型ppt課件三、整數(shù)線性規(guī)劃模型

變量取整數(shù)的線性規(guī)劃稱為整數(shù)線性規(guī)劃，簡(jiǎn)稱整數(shù)線性規(guī)劃，記為IP。整數(shù)規(guī)劃分為純整數(shù)線性規(guī)劃，記為PILP；混合整數(shù)規(guī)劃，記為MILP整數(shù)規(guī)劃的特殊情況是0-1規(guī)劃，其變量只取0或者11、整數(shù)規(guī)劃模型及分枝定界法三、整數(shù)線性規(guī)劃模型變量取整數(shù)的線性規(guī)由于整數(shù)規(guī)劃模型比線性規(guī)劃模型增加了取整的條件，所以一種自然的想法是利用線性規(guī)劃的方法求解整數(shù)規(guī)劃模型。但如直接對(duì)線性規(guī)劃問題最優(yōu)解取整往往得不到整數(shù)規(guī)劃的最優(yōu)解。因?yàn)閷?duì)線性規(guī)劃問題最優(yōu)解取整以后，有時(shí)會(huì)破壞原問題的約束條件，但解卻不是最優(yōu)解。下面介紹對(duì)于純整數(shù)和混合整數(shù)規(guī)劃都適用的分枝定界法由于整數(shù)規(guī)劃模型比線性規(guī)劃模型增加了取整的條分枝定界法的一般步驟：（1）稱原整數(shù)規(guī)劃問題為A；不考慮整數(shù)條件，相應(yīng)的線性規(guī)劃問題為B；（2）解問題B，如問題B無(wú)可行解，則停止，原問題A也無(wú)可行解；（3）如求得問題B的最優(yōu)解，檢查它是否符合整數(shù)條件，如果滿足整數(shù)條件，它就是問題A的最優(yōu)解；如不滿足整數(shù)條件，轉(zhuǎn)下一步；分枝定界法的一般步驟：（1）稱原整數(shù)規(guī)劃問題為（4）在問題B的解中，任意選一不符合整數(shù)條件的變量，假設(shè)的值為，則作兩個(gè)后繼問題：它們是對(duì)問題B的約束條件。（4）在問題B的解中，任意選一不符合整數(shù)條件的（5）不考慮整數(shù)條件解這兩個(gè)后繼問題；（6）在現(xiàn)有并且還未分解出各后繼問題的各可行解中，選擇目標(biāo)函數(shù)值為最優(yōu)的問題，重新稱該問題為B，轉(zhuǎn)（3）。（5）不考慮整數(shù)條件解這兩個(gè)后繼問題；例：設(shè)有整數(shù)規(guī)劃模型為整數(shù)例：設(shè)有整數(shù)規(guī)劃模型為整數(shù)首先不考慮整數(shù)的條件，求解線性規(guī)劃，得最優(yōu)解：任意選擇非整數(shù)解變量。如，由于，問題的解要求整數(shù)，所以分出兩個(gè)約束。從而把原問題分成兩個(gè)子問題：首先不考慮整數(shù)的條件，求解線性規(guī)劃，得最優(yōu)解：?jiǎn)栴}S1：為整數(shù)問題S1：為整數(shù)問題S2為整數(shù)問題S2為整數(shù)對(duì)子問題S1、S2，不考慮整數(shù)條件，得最優(yōu)解這兩個(gè)仍然不滿足整數(shù)的要求。所以繼續(xù)對(duì)（S1）和（S2）分解。由于（S1）的最優(yōu)值Z=349.000比，（S2）的最優(yōu)值Z=341.390大，所以先對(duì)（S1）進(jìn)行分解。由于不滿足整數(shù)要求，所以對(duì)子問題S1、S2，不考慮整數(shù)條件，得最優(yōu)解所以添加條件把（S1）分解成兩個(gè)后繼問題（S11）和（S12）。依次類推得到最優(yōu)解或判斷無(wú)最優(yōu)解。上述思想是分支定界的理論，但在利用數(shù)學(xué)軟件求解時(shí)可以省去。所以添加條件上述整數(shù)線性規(guī)劃模型的LINGO程序上述整數(shù)線性規(guī)劃模型的LINGO程序線性規(guī)劃模型ppt課件問題1.如何下料最節(jié)省?例鋼管下料問題2.客戶增加需求：原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)??？5米10根問題1.如何下料最節(jié)省?例鋼管下料問題2.客按照客戶需要在一根原料鋼管上安排切割的一種組合。切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根按照客戶需要在一根原料鋼管上安排切割的一種組合。切割模式余合理切割模式模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問題1：合理切割模式模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。?.所用原料鋼管總根數(shù)最少兩種標(biāo)準(zhǔn)1.原料鋼管剩余總余量最小為滿足客戶需要，按照哪些種合理模式，每種模式切割多少xi表示按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)決策變量

模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015xi表示按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7目標(biāo)1（總余量）按模式2切割12根,按模式5切割15根，余料27米最優(yōu)解：x2=12,x5=15,其余為0；最優(yōu)值：27。約束條件整數(shù)約束：xi為整數(shù)目標(biāo)1（總余量）按模式2切割12根,按模式5切割15根，余料相應(yīng)的LINGO程序相應(yīng)的LINGO程序線性規(guī)劃模型ppt課件目標(biāo)2（總根數(shù)）約束條件不變最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。xi為整數(shù)目標(biāo)2（總根數(shù)）約束條件不變最優(yōu)解：x2=15,x5=當(dāng)余料沒有用處時(shí)，通常以總根數(shù)最少為目標(biāo)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米雖余料增加8米，但減少了2根與目標(biāo)1的結(jié)果“共切割27根，余料27米”相比當(dāng)余料沒有用處時(shí)，通常以總根數(shù)最少為目標(biāo)按模式2切割15根相應(yīng)的LINGO程序相應(yīng)的LINGO程序線性規(guī)劃模型ppt課件鋼管下料問題2對(duì)大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過3種?，F(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復(fù)雜。鋼管下料問題2對(duì)大規(guī)模問題，用模型的約束條件界定合理模式增加決策變量

xi表示按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)r1i,r2i,r3i,r4i表示第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長(zhǎng)的鋼管的數(shù)量決策變量xi表示按第i種模式切割的原料鋼管根數(shù)(i=1目標(biāo)函數(shù)（總根數(shù)）約束條件目標(biāo)函數(shù)（總根數(shù)）約束條件模式合理：每根余料不超過3米上述問題屬于整數(shù)非線性規(guī)劃模型，模型求解比較困難，為此再引入適當(dāng)?shù)募s束條件：整數(shù)約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數(shù)模式合理：每根余料不超過3米上述問題屬于整數(shù)非線性規(guī)增加約束，縮小可行域，便于求解由于每根原料鋼管長(zhǎng)19米原料鋼管總根數(shù)下界：需求：4米50根，5米10根，6米20根，8米15根增加約束，縮小可行域，便于求解由于每根原料鋼管長(zhǎng)19米原料鋼特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式1：切割成50根4米鋼管，需13根；模式2：切割成10根5米和20根6米鋼管，需10根；模式3：切割成15根8米鋼管，需8根。原料鋼管總根數(shù)上界：13+10+8=31模式排列順序可任定特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式排列順序可任定LINGO程序LINGO程序線性規(guī)劃模型ppt課件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根。LINGO求解整數(shù)非線性規(guī)劃模型Localoptimal板材規(guī)格2：長(zhǎng)方形，32

28cm，2萬(wàn)張。例

易拉罐下料模式1：1.5秒模式2：2秒模式3：1秒模式4：3秒板材規(guī)格1：正方形，邊長(zhǎng)24cm，5萬(wàn)張。板材規(guī)格2：長(zhǎng)方形，3228cm，2萬(wàn)張。例易拉罐下料模每周工作40小時(shí)，每只易拉罐利潤(rùn)0.10元，原料余料損失0.001元/cm2（不能裝配的罐身、蓋、底也是余料）如何安排每周生產(chǎn)？上蓋下底罐身罐身高10cm，上蓋、下底直徑均5cm。每周工作40小時(shí)，每只易拉罐利潤(rùn)0.10元，原料余料模式1:正方形的邊長(zhǎng)24cm問題分析計(jì)算各種模式下的余料損失上、下底直徑d=5cm，罐身高h(yuǎn)=10cm。

模式1余料損失242-10

d2/4-dh=222.6cm2模式1:正方形的邊長(zhǎng)24cm問題分析計(jì)算各種模式下的余料

罐身個(gè)數(shù)底、蓋個(gè)數(shù)余料損失（cm2）沖壓時(shí)間（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53

罐身個(gè)數(shù)底、蓋余料損失沖壓時(shí)間（秒）模式1110222.6問題分析目標(biāo):易拉罐利潤(rùn)扣除原料余料損失后的凈利潤(rùn)最大

約束：每周工作時(shí)間不超過40小時(shí)；原料數(shù)量：規(guī)格1（模式1~3）5萬(wàn)張，規(guī)格2（模式4）2萬(wàn)張；罐身和底、蓋的配套組裝。注意：不能裝配的罐身、上下底也是余料問題分析目標(biāo):易拉罐利潤(rùn)扣除原料余料損失后的凈利潤(rùn)最大約決策變量

xi~按照第i種模式的生產(chǎn)張數(shù)(i=1,2,3,4)；y1~一周生產(chǎn)的易拉罐個(gè)數(shù)；y2~不配套的罐身個(gè)數(shù)；y3~不配套的底、蓋個(gè)數(shù)。

決策變量xi~按照第i種模式的生產(chǎn)張數(shù)(i=1,2,產(chǎn)量余料時(shí)間x1222.61.5x2183.32x3261.81x4169.53每只易拉罐利潤(rùn)0.10元，余料損失0.001元/cm2罐身面積dh=157.1cm2，底蓋面積d2/4=19.6cm2產(chǎn)量余料時(shí)間x1222.61.5x2183.32x3261.目標(biāo)函數(shù)

約束條件

原料約束時(shí)間約束(40小時(shí))目標(biāo)函數(shù)約束條件原料約束時(shí)間約束(40小時(shí))約束條件

配套約束罐身底、蓋1102401645產(chǎn)量x1x2x3x4雖然xi和y1，y2，y3應(yīng)是整數(shù)，但是因生產(chǎn)量很大，可以把它們看成實(shí)數(shù)，從而用線性規(guī)劃模型處理。約束條件配套約束罐身底、蓋1102401645產(chǎn)量x1x將所有決策變量擴(kuò)大10000倍（xi萬(wàn)張，yi萬(wàn)件）

警告信息：“數(shù)據(jù)之間的數(shù)量級(jí)差別太大，建議進(jìn)行預(yù)處理，縮小數(shù)據(jù)之間的差別”將所有決策變量擴(kuò)大10000倍（xi萬(wàn)張，yi萬(wàn)件）模式2生產(chǎn)40125張，模式3生產(chǎn)3750張，模式4生產(chǎn)20000張，共產(chǎn)易拉罐160250個(gè)(罐身和底、蓋無(wú)剩余)，凈利潤(rùn)為4298元OBJECTIVEFUNCTIONVALUE1)0.4298337VARIABLEVALUEREDUCEDCOSTY116.0250000.000000X10.00