線性規(guī)劃問題

線性規(guī)劃問題一、線性規(guī)劃問題的基本概念先看幾個典型實例例1生產(chǎn)計劃問題某工廠擁有a、b兩種原材料生產(chǎn)A、B兩種產(chǎn)品，現(xiàn)有設(shè)備使用限量為8臺時，已知每件產(chǎn)品的利潤、所需設(shè)備臺時及原材料的消耗如下表所示:-f 產(chǎn)品原材料AB質(zhì)材料總量a(kg)4016b(kg)0412利潤（萬元）23設(shè)備（臺）12試問：在計劃期內(nèi)應(yīng)如何安排計劃才能使工廠獲得的利潤最大?解設(shè)x「x2分別表示在計劃期內(nèi)產(chǎn)品A、B的產(chǎn)量，則所用設(shè)備的有效臺時必須滿足X]+2x2<8同樣，由原材料的限量，可以得到4xi<16,4x2<12因此，生產(chǎn)計劃就是滿足如下約束條件的一組變量x「％的值：約束條件乂xi+2x2<8,4x1<16，4x2<12，約束條件乂顯然，可行的生產(chǎn)計劃有限多個，現(xiàn)在問題就是要在很多個可行計劃中找一個利潤最大的，即求一組變量x「x2的值，使它滿足約束條件，并使目標(biāo)函數(shù)L=2x1+3x2的值最大（即利潤最大）例2資金分配問題某商店擁有100萬元資金，準(zhǔn)備經(jīng)營A、B、C三種商品，其中A商品有A「A2兩種型號，B商品有B「B2兩種型號，每種商品的利潤率如下表所示：商品ABCA1A2B1B2利潤率（%）7.310.36.47.54.5

在經(jīng)營中有以下限制：⑴經(jīng)營A或B的資金各自都不能超過總資金的50%;⑵經(jīng)營C的資金不能少于經(jīng)營B的資金的25%；⑶經(jīng)營A2的資金不能超過經(jīng)營A的總資金的60%；試問應(yīng)怎樣安排資金的使用才能使利潤最大？解設(shè)經(jīng)營A、A、B、B、C的資金分別為x，x,x,x，x（萬元），這一問1 2 1 2 1 2 3 4 5題的數(shù)學(xué)模型為求一組變量x「x2，...，x5的值，使它滿足廠x〔+x2+...+x5=100,xi+x2<50,x3+x4<50,025x3+0.25x4-x5<00.6xi-0.4x2>0,Ix_>0 （j=1,2,...,5）并使目標(biāo)函數(shù)L=0.073xi+0.103x2+0.064x4+0.075x4+0.045x5的值最大（利潤最大）上面我們建立了幾個實際問題的數(shù)學(xué)模型，雖然實際問題各不相同，但是它們的數(shù)學(xué)模型卻有相同的數(shù)學(xué)形式，這就是：表示約束條件的數(shù)學(xué)式子都是線性等式或線性不等式，表示問題最優(yōu)化指標(biāo)的目標(biāo)函數(shù)都是線性函數(shù)，因為約束條件和目標(biāo)函數(shù)都是線性的，所以把具有這種模型的問題稱為線性規(guī)劃問題。線性規(guī)劃問題的數(shù)學(xué)模型的一般形式是(1)(2)Max(Min)L=cx+cx+...+cx.(1)(2)11 22 nnax+ax+...+ax<b (或>b，或=b),、TOC\o"1-5"\h\z111 122 1nn 1 1 1ax+ax+...+ax<b (或>b，或=b),約束條件Y約束條件Yax+ax+...+ax<b(或>b，或=b)，m11m22 mnnm m mx.>（j=1，2，...，n）. （3）即求一組變量x.（j=1,2,...,n）的值，滿足約束條件，使目標(biāo)函數(shù)L的值最大（或最?。渲?，x1，x2（或最?。?，其中，x1，x2,變量的非負(fù)約束。滿足約束條件的一組變量的值稱為線性規(guī)劃問題的一個可行解，使目標(biāo)函數(shù)L取得取大值（或最小值）的可行解稱為最優(yōu)解，此時，目標(biāo)函數(shù)的值稱為最優(yōu)值，“s.t.”表示約束條件。例如，在例1中，若變量X]，X2取值為X]=1，x2=2時，它們滿足約束條件，因此x]=1，x2=2是該問題的一個可行解，此時目標(biāo)函數(shù)的值為8。求解線性規(guī)劃問題有不少現(xiàn)成的數(shù)學(xué)軟件，LINDO軟件就是其中之一，在LINDO6.1版本下打開，直接輸入數(shù)學(xué)模型，例如，輸入倒1的模型Max2X1+3X2s.t.X1+2X2<=84X1<=164X2<=12end注：LINDO中已規(guī)定所有決策變量均為非負(fù)，因此不必輸入約束條件中的非負(fù)約束條件，程序最后以“end”結(jié)束將文件存儲并命名后，選擇菜單“Solve”，得輸出OBJECTIVEFUNCTIONVALUE1）14.000000VARIABLE VALUE REDUCED COSTX1 4.000000X2 2.000000即，生產(chǎn)A產(chǎn)品4件、B產(chǎn)品2件，利潤為14萬元。例3工作選擇人員設(shè)有A、A、A、A四個人完成B、B、B、B四項工作，每人只做一件工作且1 2 3 4 1 2 3 4每件工作僅由一人擔(dān)任，Ai完成工作Bj所需時間為Ci_（i，j=1，2，3,4）（單位:天），如下表所示。1 ' "—B1B2B3B4A18131823A210141627A32102126A,14222628

試問應(yīng)指派哪個人去承擔(dān)哪件工作，才能使總的花費時間最少？這個問題與上述各例有所不同，上述各例所設(shè)的變量都是問題中所要求的數(shù)量，而這個例題中我們要引入的變量必須具有指定某人做某件工作，而其他人不能做該工作。數(shù)0、1就起到了這種作用，變量取1，說明該人做這件事，在總的花費時間中貢獻(xiàn)時間，變量取0表示不做這件事，從而在總的花費時間中不作出貢獻(xiàn)。解引入16個變量「1，當(dāng)指派Ai承擔(dān)工作B.時；ijI0，當(dāng)指派Ai不承擔(dān)工作B.時， ， ，，，由于每人只做一件工作，得 'X11+X12+X13+x14=1X21+X22+X23+X24=1X31+X32+X33+X34=1X41+X42+X43+X44=1由于每件工作僅由一個擔(dān)任，得X]]+X21+X31+X41=1X12+X22+X32+X42=1X13+X23+X33+X43=1X14+X24+X34+X44=1得線性規(guī)劃模型如下MinT=8X11+13X12+18X13+23X14+10x21+14X22+16X23+27x24+2x31+10X32+21X33+26X344NE4、i=lX+14x+22x+4NE4、i=lXx=1xj=1 i,j=1,2,3,4廣0或1這種線性規(guī)劃稱為0-1規(guī)劃，這類問題也稱為指派問題將模型輸入LINDOMIn8x11+13x12+18x13+23x14+10x21+14x22+16x23+27x24+2x31+10x32+21x33+26x34+14x41+22x42+26x43+28x44x11+x12+x13+x14=1x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1x13+c23+x33+x43=1x14+x24+x34+x44=1endint16注：int16表示16個變量全部為0-1變量求解得x=x=x=x=1,其余x=0,即A承擔(dān)工作B,A承擔(dān)工作B,A承擔(dān)12 23 31 44 ij 1 2 2 3 3工作B『A4承擔(dān)工作B4，花費的總時間最少為59天。例4汽車廠生產(chǎn)計劃一汽車廠生產(chǎn)小、中、大三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求、利潤以及每月工廠鋼材、勞動時間的現(xiàn)有量如下表所示，試制訂月生產(chǎn)計劃，使工廠的利潤最大。小型中型大型現(xiàn)有量鋼材（噸）1.535600勞動時間（小時）28025040060000利潤（萬元）234解設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x「x2、乂廠工廠的月利潤為L,在題目所給參數(shù)均不隨生產(chǎn)數(shù)量變化的假設(shè)下，立即可得線性規(guī)劃模型：MaxL=2x〔+3x2+4x3s.t 1.5x〔+3x2+5x3<600280x+250x+400x<60000求解得到輸出1x〔，x2，x3>023ORJECTIVEFUNCTIONVALUE1) 632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833） 0.000000 0.003226我們看到最優(yōu)解x1=64.516129,x2=167.741928,x3=0,出現(xiàn)小數(shù)，顯然不合適對于這個實際問題，變量x1，x2,X3只能取整數(shù)，，我們必須在上述所建立的線性規(guī)劃模型中增加約束條件'2 3x1，x2，x3為整數(shù)得來的線性規(guī)劃模型如下：MaxL=4x〔+3x2+2x3s.t 1.5x〔+3x2+5x<600280x1+25x2+400x<60000x>0,x>0,x>0x1，x2,x3均為整數(shù)附加了整數(shù)約束條件的線性規(guī)劃模型稱為整數(shù)規(guī)劃用LINDO直接求解，輸入文件：max2x1+3x2+4x3s.t1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3注：最后一行“gin3”是“3個變量均為整數(shù)”的說明語句。求解得到輸出（只列出需要的結(jié)果）：OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000最優(yōu)解為x1=64，x2=168,x3=0，最優(yōu)值為z=632,即問題要求的月生產(chǎn)計劃為生產(chǎn)小型車64輛、中型車168輛，不生產(chǎn)大型車。二、線性規(guī)劃問題舉例例1自來水輸送問題某市有甲、乙、丙、丁四個居民區(qū)，自來水由A，B，C三個水庫供應(yīng)，四個區(qū)每天必須得到保證的基本生活用水量分別為30，70，10，10千噸，但由于水源緊張，三個水庫每天最多只能分別供應(yīng)50,60,50千噸自來水，由于地理位置的差別，自來水公司從各水庫向各區(qū)送水所需付出的引水管理費不同（見下表，其中C水庫與丁區(qū)之間沒有輸水管道），其他管理費用都是450元/千噸，根據(jù)公司規(guī)定，各區(qū)用戶按照統(tǒng)一標(biāo)準(zhǔn)900元/千噸收費，此外，四個區(qū)都向公司申請了額外用水量，分別為每天50，70，20，40千噸，該公司應(yīng)如何分配供水量，才能獲利最多?引水管理費（元/千噸）甲乙丙丁A160130220170B140130190150C190200230/問題分析分配供水量就是安排從三個水庫向四個區(qū)送水的方案，目標(biāo)是獲利最多，而從題目給出的數(shù)據(jù)看，A，B，C三個水庫的供水量160千噸，不超過四個區(qū)的基本生活用水量與額外用水量之和300千噸，因而總能全部賣出并獲利，于是自來水公司每天的總收入是900x（50+60+50）=144000元，與送水方案無關(guān)，同樣，公司每天的其它管理費用450x（50+60+50）=72000元也與送水方案無關(guān)，所以，要使利潤最大，只需使引水管理費最小即可，另外，送水方案自然要受三個水庫的供應(yīng)量和四個區(qū)的需求量的限制。模型建立很明顯，決策變量為A，B，C三個水庫（i=1，2，3）分別向甲、乙、丙、丁四個區(qū)（j=1，2，3,4）的供水量，設(shè)水庫i向j區(qū)的日供水量為xi_，由于C水庫與丁區(qū)之間沒有輸水管道，即x34=0,因此只有11個決策變量。由上分析，問題的目標(biāo)可以從獲利最多轉(zhuǎn)化為引水管理費最少，于是有MinL=160x+130x+220x+170x+140x+130x+190x+150x+190x11 12 13 14 21 22 23 24 31+200x+230x約束條件有兩類：一類是水庫的供應(yīng)量限制，另一類是各區(qū)的需求量限制，由于供水量總能賣出并獲利，水庫的供應(yīng)量限制可以表示為x11+x12+x13+x=5014x+x+x+x=6021222324x+x+x=50313233考慮到各區(qū)的基本生活用水量與額外用水量，需求量限制可以表示為30<x+x21+x31<801170<x12+x22+x32<14010<x13+x23+x33<3010<x14+x24<50再加上決策變量的非負(fù)約束

模型求解將線性規(guī)劃模型輸入LINDO求解，得到如下輸出:OBJECTIVEFUNCTIONVALUE1)24400.00VARIABLEVALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000X2250.0000000.000000X230.00000020.000000X2410.0000000.000000X3140.0000000.000000X320.00000020.000000X3310.0000000.000000即，A水庫向乙區(qū)供水50千噸，B水庫向乙、丁區(qū)分別供水50、10千噸，C水庫向甲、丙區(qū)分別供水40、10千噸，引水管理費為24400元，利潤為144000-72000-24400=47600元例2混合泳接力隊的選拔問題某班準(zhǔn)備從5名游泳隊員中選擇4人組成接力隊，參加學(xué)校的4x100m混合泳接力比賽，5名隊員4種泳姿的百米平均成績?nèi)缦卤硭?，問?yīng)如何選拔隊員組成接力隊?甲乙丙丁戊蝶泳1，06〃857〃21，18〃1，10〃1，07〃4仰泳1，15〃61，06〃1，07〃81，14〃21，11〃蛙泳1，27〃1，06〃41，24〃61，09〃61，23〃8自由泳58〃653〃59〃457〃21，02〃4問題分析從5名隊員中選出4人組成接力隊，每人一種泳姿，且4人的泳姿各不相同，使接力隊的成績最好容易想到的一個辦法是窮舉法，組成接力隊的方案共有5!=120種，逐一計算并作比較，即可找出最優(yōu)方案，顯然這不是解決這類問題的好辦法，隨著問題規(guī)模的變大，窮舉法的計算量將是無法接受的?？梢杂?-1變量表示一個隊員是否入選接力隊，從而建立這個問題的0-1規(guī)

ci=1i=2i=3i=4 ~i=5j=166.857.2787067.4j=275.66667.874.271ci=1i=2i=3i=4 ~i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4記x..=1,否則記x.=0,劃模型，借助現(xiàn)成的數(shù)學(xué)軟件求解。模型建立與求解記甲乙丙丁戊分別為隊員i=1,2,3,4,5;記蝶泳、仰泳、蛙泳、自由泳分別為泳姿j=1，2,3,4記隊員i的第j種泳姿的百米最好成績?yōu)閏.(s),即有2,3,4x..第一，每人最多只能入選4種泳姿之一，即對于2,3,4x..第二，每種泳姿必須有1人而且只能有1人入選，即對于j=1第二，每種泳姿必須有1人而且只能有1人入選，即對于j=1有Xxij=1；當(dāng)隊員i入選泳姿j時，cx表示他(她)的成績，否則cx=0ijij ijij的成績可表示為Z=言言cijxij,這就是該問題的目標(biāo)函數(shù)。綜上，這個問題的0-1規(guī)劃模型可寫作MinL=S言c.x..s.txx..<1，2,3,4,于是接力隊言xij=1,j=1x={0i=1,2,3,4,52,3,41}并輸入LINDO：x13+58.6x14并輸入LINDO：x13+58.6x14將題目所給數(shù)據(jù)代人這一模型，MIN66.8x11+75.6x12+87+57.2x21+66x22+66.4x23+53x24+78x31+67.8x32+84.6x33+59.4x34+70x41+74.2x42+69.6x43+57.2x44+67.4x51+71x52+83.8x53+62.4x54s.tx11+x12+x13+x14<=1x21+x22+x23+x24<=1x31+x32+x33+x34<=1x41+x42+x43+x44<=1x11+x21+x31+x41+x51=1x12+x22+x32+x42+x52=1x13+x23+x33+x43+x53=1x14+x24+x34+x44+x54=1endint20求解得到結(jié)果為：x=x=x=x=1,其它變量為0,成績?yōu)?53.2〃=14 21 32 434，13〃2.即應(yīng)當(dāng)選派甲乙丙丁4人組成接力隊，分別參加自由泳、蝶泳、仰泳、蛙泳的比賽。例3選課策略某學(xué)校規(guī)定，運籌學(xué)專業(yè)的學(xué)生畢業(yè)時必須至少學(xué)習(xí)過兩門數(shù)學(xué)課，三門運籌學(xué)課和兩門計算機(jī)課，這些課程的編號、名稱、學(xué)分、所屬類別和先修課要求如下表所示，畢業(yè)時學(xué)生最少可以學(xué)習(xí)這些課程中的哪些課程。課程編號課程名稱學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)2線性代數(shù)4數(shù)學(xué)3最優(yōu)化方法4數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計算機(jī)計算機(jī)編程5應(yīng)用統(tǒng)計4數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)6計算機(jī)模擬3計算機(jī)；運籌學(xué)計算機(jī)編程7計算機(jī)編程2計算機(jī)8預(yù)測理論2運籌學(xué)應(yīng)用統(tǒng)計9數(shù)學(xué)實驗3運籌學(xué)；計算機(jī)微積分；線性代數(shù)模型建立用xi=1表示選修表中按編號順序的9門課程（xi=0表示不選；i=1，2...，9）問題的目標(biāo)為選修的課程總數(shù)最少，即 1MinZ=Sxi約束條件包括兩個方面：第一，每人最少要學(xué)習(xí)2門數(shù)學(xué)課、3門運籌學(xué)課和2門計算機(jī)課，根據(jù)表中對每門課程所屬類別的劃分，這一約束可以表示為x+x+x+x+x>2TOC\o"1-5"\h\z12 345x+x+x+x+x>35 689x+x+x+x>2第二，某些課程有先修課程的要求，例如“數(shù)據(jù)結(jié)構(gòu)”的先修課是“計算機(jī)編程”，這意味著如果x=1，必須x=1，這個條件可以表示為x<x（注意：x=07 4 7 4時對x7沒有限制）。“最優(yōu)化方法”的先修課是“微積分”和“線性代數(shù)”的條件可表為x<x,x<x,而這兩個不等式可以用一個約束表示為2x-x-x<0,這樣，3 1 3 2 3 1 2所有課程的先修課要求可表為如下的約束2x-x-x<0x4-x7<02x5—x1—x2<0x-x<0x8-x5<02x—x—x<0模型求解將0-1規(guī)劃模型輸入LINDO,求解得到結(jié)果為x=x=x=x=x=x=1，其它變量0,1 2 3 6 7 9對照課程編號，它們是微積分、線性代數(shù)，最優(yōu)化方法、計算機(jī)模擬、計算機(jī)編程、數(shù)學(xué)實驗，共6門課程，總學(xué)分為21。例4鋼管下料問題某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出，從鋼管廠進(jìn)貨時得到的原料鋼管都是19m?，F(xiàn)有一客戶需要50根4m、20根6m和15根8m的鋼管，應(yīng)如何下料最節(jié)省？問題分析首先，應(yīng)當(dāng)確定哪些切割模式是可行的，所謂一個切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合，例如：我們可以將19m的鋼管切割成3根4m的鋼管，余料為7m;或者將19m的鋼管切割成4m、6m和8m的鋼管各1根，余料為1m，顯然，可行的切割模式是很多的。其次，應(yīng)當(dāng)確定哪些切割模式是合理的，通常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸，例如：將19m的鋼管切割成3根4m的鋼管是可行的，但余料為7m，可以進(jìn)一步將7m的余料切割成4m鋼管（余料為3m），或者將7m的余料切割成6m鋼管（余料為1m）在這種合理性假設(shè)下，切割模式一共有7種，如下表所示。4m鋼管根數(shù)6m鋼管根數(shù)8m鋼管根數(shù)余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少根原料鋼管，最為節(jié)省，而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)：一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最少，下面將對這兩個目標(biāo)分別討論。模型建立用xi表示按照第i種模式(i=1，2，...，7)切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。以切割后剩余的總余料量最小為目標(biāo)，則由上表可得TOC\o"1-5"\h\zMinZ=3x+x+3x+3x+x+x+3x (1)1 1 2 3 4 5 6 7以切割原料鋼管的總根數(shù)量少為目標(biāo)，則有MinZ=x+x+x+