線性規(guī)劃模型

1、線性規(guī)劃模型,y,2、找出問題中所有的限制或約束，寫出未知變量的線性方程組或線性不等式組；,一、線性規(guī)劃模型,1、找出待定的未知變量（又稱為決策變量決策者自己可以控制的變量），并且用符號(hào)表示；,3、找出模型的目標(biāo)函數(shù)：是以函數(shù)形式表示的決策者追求的目標(biāo)寫出未知變量的線性方程或線性不等式,（一）建立線性規(guī)劃模型有三個(gè)基本步驟：,例 （配料問題）某鑄造廠生產(chǎn)鑄件，每件需要20千克鉛，24千克銅和30千克鐵。現(xiàn)有四種礦石可供選購，它們每10千克含有成分的質(zhì)量（千克）和價(jià)格（元）如圖。問：對(duì)每個(gè)鑄件來說，每種礦石各應(yīng)該選購多少，可以使總費(fèi)用最少？試建立數(shù)學(xué)模型。,分析和建立模型,（1）確定決策變量：設(shè)

2、 為第i種礦石的選取的數(shù)量（單位10kg） ；,（3）確定約束條件：選定的四種礦石的數(shù)量應(yīng)該滿足鑄件對(duì)三種成分的需求量，并且礦石數(shù)量應(yīng)該是非負(fù)的，即,每件需要20千克鉛，24千克銅和30千克鐵,綜合以上分析，得到配料問題的數(shù)學(xué)模型為：,受約束于,（二）線性規(guī)劃模型的結(jié)構(gòu)具有如下特性,（1）目標(biāo)函數(shù)是決策變量 的線性函數(shù)；,（2）約束條件是決策變量 的線性等式或不等式；,具有以上結(jié)構(gòu)特點(diǎn)的模型就是線性規(guī)劃模型，記為LP（Linear Programming），具有以下一般形式：,（三）線性規(guī)劃的標(biāo)準(zhǔn)模型,由于目標(biāo)函數(shù)既可以是實(shí)現(xiàn)最大化，也可以是實(shí)現(xiàn)最小化，約束條件可以是等式，也可以是不等式，決策

3、變量為非負(fù)或不受限制，這么復(fù)雜的情況，一定會(huì)給模型的求解帶來不便，為此引入標(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ù)為最大化類型（有的書上為最小化）；,1、如果目標(biāo)函數(shù)為最小化問題，則將目標(biāo)函數(shù)兩邊乘以“-1”；,2、如果約束方程右端為負(fù)，在該方程兩端同乘以 “-1”；,如果所建的模型不符合標(biāo)準(zhǔn)形式，則可以用適當(dāng)方法化為標(biāo)準(zhǔn)形式，主要有：,3、如果約束為 “ ”，則可以增加一個(gè)變量 ，在左端加上 ，這種變量稱為剩余變量；,4、如果約束為 “ ”，則可以增加一個(gè)變量 ，

4、在右 端加上 ，這種變量要求非負(fù)，在線性規(guī)劃中均稱為松馳變量；,5、如果某決策變量 無符號(hào)限制，則將每個(gè) 換成,例：將下列線性規(guī)劃模型化為標(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ī)劃問題的解及單純形法（解法）,5、基：約束方程組 的系數(shù)矩陣為 階的矩陣 則稱A的任意一個(gè) 階的非奇異子矩陣B為線性規(guī)劃的一個(gè)基。,6、基向量：組成基B的列向量 稱為 基向量。,7、基變量：基向量 對(duì)應(yīng)的變量 稱為基變量，基變量以外的變量稱為非基

5、變量。,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，稱為基本解。,1、基本思想：首先找出一個(gè)基可行解，然后根據(jù)某種最優(yōu)性準(zhǔn)則判斷該解是否為最優(yōu)，如果最優(yōu)，則結(jié)束；否則利用某種迭代規(guī)則尋找下一個(gè)基可行解，并且使下一個(gè)基可行解的目標(biāo)函數(shù)值有所改變，反復(fù)多次，直到找出最優(yōu)解，或判斷出原問題無最優(yōu)解。,（二）單純形法,為了確定初始基可行解，需要先找出初始可行基。其方法是：觀察約束方程組系數(shù)矩陣 ，若其中有子塊為m階單位矩陣 ，則

6、可將其選為初始可行基；否則，可采用所謂人工變量法尋找初始可行基。,（1）、確定初始基可行解并且計(jì)算相應(yīng)的目標(biāo)函數(shù)值,2、計(jì)算步驟（3步）,若 的前m列為單位陣（作為基），則約束方程 可化為,令非基變量 即得初始基可行解。,將方程組（1）代入目標(biāo)函數(shù),故對(duì)應(yīng)于基可行解 的目標(biāo)函數(shù)值 ，于是原線性規(guī)劃模型等價(jià)于,此等價(jià)模型稱為原線性規(guī)劃的典式，其中 稱為基本可行解 的檢驗(yàn)數(shù),（2）、根據(jù)檢驗(yàn)數(shù) 進(jìn)行最優(yōu)性檢驗(yàn)與解的判斷。,定理：若線性規(guī)劃的基可行解 對(duì)應(yīng)的典式為（1）并且檢驗(yàn)數(shù)為,、 當(dāng)存在某個(gè)檢驗(yàn)數(shù) 時(shí)，并且典式（1）中所有 時(shí)，線性規(guī)劃無有限最優(yōu)解。,則 、 當(dāng) 時(shí)， 是線性規(guī)劃的有限最優(yōu)解；

7、,、 當(dāng)存在檢驗(yàn)數(shù) 且典式（1）中有些 ，這時(shí)采用迭代法實(shí)現(xiàn)基可行解的轉(zhuǎn)移。,當(dāng)初始基可行解 不是最優(yōu)解，并且不能判別無有限最優(yōu)解時(shí)，需要另找一個(gè)基可行解，并使相應(yīng)目標(biāo)函數(shù)值增大，（即要對(duì)原可行基換一個(gè)列向量）。為此需要確定進(jìn)基變量和出基變量的規(guī)則。,（3） 通過換基迭代，實(shí)現(xiàn)基可行解的轉(zhuǎn)移,出基變量的規(guī)則：,為了使得目標(biāo)函數(shù)值增加得較快，進(jìn)基變量 的取值使得目標(biāo)函數(shù)值盡可能的大，出基變量取哪一個(gè)，通過 準(zhǔn)則來確定。,準(zhǔn)則,反復(fù)進(jìn)行以上步驟，即可獲得線性規(guī)劃的最優(yōu)解，或判斷出該線性規(guī)劃無有限最優(yōu)解。,其中 對(duì)應(yīng)的系數(shù)。 稱為主元素（又稱為中心元素），主元素所在行的基變量 ，就是要確定的出基變量

8、。,單純形表：單純形法的求解過程實(shí)際上是在一系列表格上進(jìn)行的。從這些表格上可以得到基本可行解、檢驗(yàn)數(shù)等信息。這些表格稱為單純形表。每個(gè)表相當(dāng)于一個(gè)矩陣，每次迭代就是對(duì)矩陣進(jìn)行初等行變換。,例：求解線性規(guī)劃問題的最優(yōu)解,解：（1）構(gòu)造初始單純單純形表（第1、4、5列構(gòu)成的矩陣可逆）所以可取,為初始基可行解。因目標(biāo)函數(shù) 不是典式 ，故將 代入目標(biāo)函數(shù)z，整理得 （典式） 其中，6為 的目標(biāo)函數(shù)值，此時(shí)可以列出單純形表（如圖）。,（2）迭代求新的基可行解及其檢驗(yàn)數(shù),從上表格中可以看出，檢驗(yàn)數(shù) 大于0，不滿足最優(yōu)性準(zhǔn)則，須迭代求新解。取最大的檢驗(yàn)數(shù) 對(duì)應(yīng)的變量 為進(jìn)基變量。它取代誰呢？再由 準(zhǔn)則，用表

9、格最右側(cè)元素分別與表格中 所在列的各元素去比，求最小值,最小值4對(duì)應(yīng)表格中基變量為 ，故 為出基變量，元素 為中心元素。,開始迭代，將 所在列元素變?yōu)閱挝幌蛄浚瑱z驗(yàn)數(shù)行也參加變換。同時(shí)將表格左側(cè)列中基變量 換成 得表（把x3所在的元素化為1，然后再把其它行的元素化為零）,令 得第二個(gè)基可行解,表格的右下角說明，當(dāng)前的目標(biāo)值為 14，目標(biāo)值增量為8，另外上面的表格中仍然有 仍然需要迭代求新解。,繼續(xù)迭代,取 為進(jìn)基變量，并且用上表格最右端列元素比上 所在列相應(yīng)元素，計(jì)算,最小比值對(duì)應(yīng)上表中基變量 所在的行，故 為出基變量 ，中心元素為 ，同上述方法可知 為進(jìn)基變量，于是得到下面的表格,表格的右下

10、角說明，當(dāng)前的目標(biāo)值為 14.5，目標(biāo)值增量為0.5，,下面利用LINGO軟件求解,LINGO9.0,LINGO初始界面,LINGO程序,LINGO程序運(yùn)行,變量數(shù)量,變量總數(shù),非線性變量數(shù),整數(shù)變量數(shù),約束數(shù)量,約束總數(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)框,當(dāng)前約束不滿足的總量（不是不滿足的約束的個(gè)數(shù)）實(shí)數(shù)時(shí)該值為0,到目前為止迭代次數(shù),使用的特殊求解程序,擴(kuò)展的求解器狀態(tài)框（求解程序）狀態(tài)框,到目前為止找到的可行解的最佳目標(biāo)函數(shù)值,目標(biāo)函數(shù)值的界,特殊求解程序當(dāng)前運(yùn)行

11、步數(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型問題）,例1 加工奶制品的生產(chǎn)計(jì)劃,問題：一奶制品加工廠用牛奶生產(chǎn)A1，A2兩種奶制品，1桶牛奶可以在甲類設(shè)備上用12小時(shí)加工成3公斤A1，或者在乙類設(shè)備上用8小時(shí)加工成4公斤A2。根據(jù)市場需求，生產(chǎn)的A1，A2全部能夠售出，且每公斤A1獲利24元，每公斤A2獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動(dòng)時(shí)間為480小時(shí)，并

12、且甲類設(shè)備每天至多能加工100公斤A1，乙類設(shè)備的加工能力沒有限制。試為該廠制訂一個(gè)生產(chǎn)計(jì)劃，使每天獲利最大？并且進(jìn)一步討論以下3個(gè)問題：,1）若有35元可以買到1桶牛奶，應(yīng)否作這項(xiàng)投資？若投資，每天最多購買多少桶牛奶？ 2）若可以聘用臨時(shí)工人增加勞動(dòng)時(shí)間，付給臨時(shí)工人的工資最多是每小時(shí)幾元？ 3）由于市場需求變化，每公斤A1的獲利增加到30元，應(yīng)否改變生產(chǎn)計(jì)劃？,問題分析：這個(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é)式子表

13、示出來，就得到相應(yīng)的數(shù)學(xué)模型。,決策變量：設(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;,勞動(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=0 x2=0 ；,數(shù)學(xué)模型：,給出最優(yōu)的單純形表中目標(biāo)函數(shù)

14、行變量對(duì)應(yīng)的系數(shù)（即各個(gè)變量的檢驗(yàn)數(shù)，基變量為0，非基變量對(duì)應(yīng)的值表示當(dāng)該非基變量增加一個(gè)單位時(shí)目標(biāo)函數(shù)減少的量（對(duì)max型問題）,約束條件的右段通常看作資源，一般稱“資源”剩余為零的約束為緊約束（有效約束）；目標(biāo)函數(shù)看作“效益”成為緊約束的資源一旦增加，“效益必然跟著增加”,LINDO6.1,LINDO程序,靈敏性分析嗎,表示單純形法在兩次迭代后得到最優(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型問題）,

15、松弛或剩余（給出約束對(duì)應(yīng)的松弛變量的值。第2、3行松弛變量為0，說明兩個(gè)約束都是緊約束）,給出影子價(jià)格的值,表示用單純形法進(jìn)行了兩次迭代,目標(biāo)函數(shù)的系數(shù)和約束條件右端項(xiàng)在什么范圍變化時(shí)，最優(yōu)基保持不變,目標(biāo)函數(shù)中系數(shù)變化的范圍,最優(yōu)基：基本最優(yōu)解對(duì)應(yīng)的基。,目標(biāo)函數(shù)中變量當(dāng)前的系數(shù),目標(biāo)函數(shù)的系數(shù)允許增加的幅度，最優(yōu)基保持不變,目標(biāo)函數(shù)的系數(shù)允許減少的幅度，最優(yōu)基保持不變,約束條件中當(dāng)前的右端項(xiàng)最優(yōu)基保持不變,約束條件中當(dāng)前的右端項(xiàng)允許變化的范圍，最優(yōu)基保持不變,約束條件中右端項(xiàng)允許增加的幅度最優(yōu)基保持不變,約束條件中右端項(xiàng)允許減少的幅度，最優(yōu)基保持不變,INFINITY表示正無窮大,問題：例

16、1給出的A1、A2兩類奶制品的生產(chǎ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ì)劃，使每天的凈利潤最大，并且討論以下問題：,例2 奶制品的生產(chǎn)銷售計(jì)劃,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ì)劃有無影響？若

17、每公斤B1的獲利下降10%，計(jì)劃應(yīng)該變化嗎？,教材P83例奶制品的生產(chǎn)銷售計(jì)劃程序,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ī)劃模型。但如直接對(duì)線性規(guī)劃問題最優(yōu)解取整往往得不到整數(shù) 規(guī)劃的最優(yōu)解。因?yàn)閷?duì)線性規(guī)劃問題最優(yōu)解取整以后，有時(shí)會(huì)破壞原問題的約束條件，但解卻

18、不是最優(yōu)解。下面介紹對(duì)于純整數(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ù)條件解這兩個(gè)后繼問題；,（6） 在現(xiàn)有并且還未分解出各后繼問題的各可行解中，選擇目標(biāo)函數(shù)值為最優(yōu)的問題，重新稱該問題為B，轉(zhuǎn)（3）。,首先不考慮整數(shù)的條件，求解線性規(guī)劃，得最優(yōu)解：,任意選擇非整數(shù)解變量。如 ，由于 ，問題的解要求整

19、數(shù)，所以分出兩個(gè)約束。 從而把原問題分成兩個(gè)子問題：,對(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ù)要求，所以,所以添加條件 把（S1）分解成兩個(gè)后繼問題（S11）和（S12）。依次類推得到最優(yōu)解或判斷無最優(yōu)解。,上述思想是分支定界的理論，但在利用數(shù)學(xué)軟件求解時(shí)可以省去。,上述整數(shù)線性規(guī)劃模型的LINGO程序,問題1. 如何下料最節(jié)省 ?,例 鋼管下料,問題2. 客戶增加需求：,節(jié)省的標(biāo)準(zhǔn)是什么？,由于采用不同

20、切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)??？,按照客戶需要在一根原料鋼管上安排切割的一種組合。,切割模式,合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸,合理切割模式,鋼管下料問題1：,為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。?2. 所用原料鋼管總根數(shù)最少,兩種標(biāo)準(zhǔn),1. 原料鋼管剩余總余量最小,xi 表示按第i 種模式切割的原料鋼管根數(shù)(i=1,2,7),決策變量,目標(biāo)1（總余量）,按模式2切割12根,按模式5切割15根，余料27米,最優(yōu)解：x2=12, x5=15,其余為0； 最優(yōu)值：27。,相應(yīng)的LINGO程序,目標(biāo)2（

21、總根數(shù)）,約束條件不變,最優(yōu)解：x2=15, x5=5, x7=5, 其余為0； 最優(yōu)值：25。,xi 為整數(shù),相應(yīng)的LINGO程序,鋼管下料問題2,對(duì)大規(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ù)量,目標(biāo)函數(shù)（總根數(shù)）,約束條件,模式合理：每根余料不超過3米,上述問題屬

22、于整數(shù)非線性規(guī)劃模型，模型求解比較困難，為此再引入適當(dāng)?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)計(jì)劃：對(duì)每根原料鋼管 模式1：切割成50根4米鋼管，需13根； 模式2：切割成10根5米和20根6米鋼管，需10根； 模式3：切割成15根8米鋼管，需8根。 原料鋼管總根數(shù)上界：13+10+8=31,模式排列順序可任定,LINGO程序,LINGO求解整數(shù)非線性規(guī)劃模型,Local optimal soluti

23、on found at iteration: 12211 Objective value: 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.000000 1.000000 R11 3.000000 0.000000 R12 2.000000 0.000000 R13 0.000000 0.000000 R21 0.000000 0.000000 R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000

24、R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.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小時(shí)，每只易拉罐利潤0.10元，原料余料損失0.001

25、元 / cm2（不能裝配的罐身、蓋、底也是余料）,如何安排每周生產(chǎn)？,罐身高10cm，上蓋、下底直徑均5cm。,模式1: 正方形的邊長24cm,問題分析,計(jì)算各種模式下的余料損失,上、下底直徑d=5cm，罐身高h(yuǎn)=10cm。,模式1 余料損失 242-10d2/4 - dh=222.6 cm2,問題分析,目標(biāo):易拉罐利潤扣除原料余料損失后的凈利潤最大,約束：每周工作時(shí)間不超過40小時(shí)； 原料數(shù)量：規(guī)格1（模式1 3）5萬張， 規(guī)格2（模式4）2萬張； 罐身和底、蓋的配套組裝 。,注意：不能裝配的罐身、上下底也是余料,決策變量,xi 按照第i 種模式的生產(chǎn)張數(shù)(i=1,2,3,4)； y1 一周生產(chǎn)的易拉罐個(gè)數(shù)； y2 不配套的罐身個(gè)數(shù)； y3 不配套的底、蓋個(gè)數(shù)。,每只易拉罐利潤0.10元，余料損失0.001元 / cm2,罐身面積dh=157.1 cm2 ，底蓋面積d2/4=19.6 cm2,目標(biāo)函數(shù),約束條件,原料約束,約束條件,配套約束,雖然xi和y1，y2，y3應(yīng)是整數(shù)，但是因生產(chǎn)量很大，可以把它們看成實(shí)數(shù)，從而用線性規(guī)劃模型處理 。,將所有決策變量擴(kuò)大10000倍（xi