線性規(guī)劃中的若干問題

例一、生產(chǎn)安排模型：用白紙坯生產(chǎn)原稿紙，日記本，練習(xí)本，所需要的白紙坯，勞動力，以及產(chǎn)生的利潤資料如下：一捆原稿紙，一扎日記本，一箱練習(xí)本分別消耗白紙坯10/3,40/3,80/3kg；勞動力的工作效率分別是為每人每月可生產(chǎn)30捆原稿紙，或可生產(chǎn)30扎日記本，或可生產(chǎn)30箱練習(xí)本；而每捆原稿紙可獲利2元，每扎日記本可獲利3元，每箱練習(xí)本可獲利1元，企業(yè)有工人100人，每月供應(yīng)白紙坯30000kg，問企業(yè)每月應(yīng)該怎樣安排生產(chǎn)可獲利最大？線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第1頁!解：1、確定決策變量：設(shè)x1,x2,x3為每月生產(chǎn)原稿紙，日記本，練習(xí)本的生產(chǎn)量；2、明確目標(biāo)函數(shù)：獲利最大，即求目標(biāo)函數(shù)總利潤2x1+3x2+x3的最大值；3、所滿足的約束條件：勞動力限制：白紙坯限制：基本要求：x1,x2,x3≥0；具體模型為s.t線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第2頁!運輸問題是一類特殊的線性規(guī)劃模型，該模型的建立最初用于解決一個部門的運輸網(wǎng)絡(luò)所要求的最經(jīng)濟的運輸路線和產(chǎn)品的調(diào)配問題，并取得了成功。然而，在實際問題的應(yīng)用中，除運輸問題外，許多非運輸問題的實際問題一樣可以建立其相應(yīng)的運輸問題模型，并由此而求出其最優(yōu)解。下面以“產(chǎn)銷平衡模型”對運輸問題進(jìn)行一下簡單的概括和描述：設(shè)某產(chǎn)品產(chǎn)自m個地方，在n個地方銷售，且i產(chǎn)地的產(chǎn)量為ai，在j地的銷售量為bj，假設(shè)產(chǎn)銷平衡，即（總產(chǎn)量=總銷量）個地方，在個地方銷售，且產(chǎn)地的產(chǎn)量為，在地的銷售量為；假設(shè)產(chǎn)銷平衡，即（總產(chǎn)量）（總銷量）。若從產(chǎn)地到銷售地的單位運價為例二、運輸問題

線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第3頁!若從i產(chǎn)地到j(luò)銷售地的單位運價為cij，問如何組織運輸才能使總的運輸費為最?。?此為產(chǎn)銷平衡類型)解：1、確定決策變量：設(shè)xij表示從i產(chǎn)地銷往j銷售地的銷售量；共有m×n個決策變量。2、明確目標(biāo)函數(shù)：總運輸費最小，即求的最小值；

3、所滿足的約束條件：產(chǎn)量限制和銷量限制：(i產(chǎn)地的產(chǎn)品量等于分銷給n個地方的銷量總和）(j地的接收量等于m個產(chǎn)地銷往j地的銷量總和）線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第4頁!比如：下表給出某運輸問題的產(chǎn)銷平衡表與單位運價表，求其最佳運輸方案。（只需要建立模型即可）銷地產(chǎn)地123產(chǎn)量（噸）120元/噸24元/噸5元/噸8230元/噸22元/噸22元/噸7銷量（噸）456共15線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第5頁!生產(chǎn)能力（臺）單位成本（萬元）一季度2510.8二季度3511.1三季度3011.0四季度1011.3而1，2，3，4季度末的合同需求為10、15、25、20臺；（只需要建立模型即可）提示：設(shè)xij為第i季度生產(chǎn)的柴油機在第j季度交貨的臺數(shù)。線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第6頁!品的數(shù)目，例如，車間1每天至多生產(chǎn)某產(chǎn)品6件，若安排1/3天時間去生產(chǎn)，則至多可以產(chǎn)出2件。決策變量共有個。如果令，則表示每天全廠生產(chǎn)i種產(chǎn)品的總數(shù)目。此時取值為非負(fù)整數(shù)。2、明確目標(biāo)函數(shù)：令Z表示一天生產(chǎn)的成套產(chǎn)品數(shù)，即求Z的最大值；3、所滿足的約束條件：配套限制：（全天生產(chǎn)i種產(chǎn)品的總數(shù)目不小于配套所需要的i種產(chǎn)品數(shù)，共有m個不等式）；線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第7頁!比如設(shè)有A、B、C三個車間要生產(chǎn)甲、乙、丙三種零件，下表數(shù)據(jù)表示各車間在一天內(nèi)至多生產(chǎn)的零件數(shù)目，假設(shè)2件甲零件、1件乙零件和3件丙零件配成一套，問如何安排生產(chǎn)才能使三個車間生產(chǎn)出的成套零件最多？（只需要建立模型即可）車間零件ABC甲101510乙111714丙131221線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第8頁!解：1、確定決策變量：令共有個決策變量。2、明確目標(biāo)函數(shù)：總成本最?。ɑ蚩偸找孀畲螅?。3、所滿足的約束條件：一人一件限制：一件一人限制：其中線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第9頁!例、某公司員工甲，乙，丙，丁。由于四人各自技術(shù)特點的不同，他們完成A,B,C,D四種工作所帶來的效益（單位：千元）如下表所示，應(yīng)指派何人完成何種工作，能使總的效益最大？（建立這個問題的線性規(guī)劃模型，不求解）ABCD甲149415乙117910丙134105丁1791513線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第10頁!例五、下料問題

“下料問題(cuttingstockproblem)”是把相同形狀的一些原材料分割加工成若干個不同規(guī)格大小的零件的問題，此類問題在工程技術(shù)和工業(yè)生產(chǎn)中有著重要和廣泛的應(yīng)用.這里的“實用下料問題”則是在某企業(yè)的實際條件限制下的單一材料的下料問題。

線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第11頁!問題分析對于下料問題首先要確定采用哪些切割模式。所謂切割模式，是指按照顧客要求的長度在原料鋼管上安排切割的一種組合。例如，我們可以將19m的鋼管切割成3根長4m的鋼管，余料為7m；或者將長19m的鋼管切割成長4m、6m和8m的鋼管各1根，余料為1m。顯然，可行的切割模式是很多的。其次，應(yīng)當(dāng)明確哪些切割模式是合理的。合理的切割模式通常還假設(shè)余料不應(yīng)大于或等于客戶需要鋼管的最小尺寸。線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第12頁!表3鋼管下料問題1）的合理切割模式模式4m鋼管根數(shù)6m鋼管根數(shù)8m鋼管根數(shù)余料/m14003231013201341203511116030170023線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第13頁!2)同問題1）一樣，只使用合理的切割模式，其余料不應(yīng)大于3m（因為客戶需要的鋼管最小尺寸為4m，而本題中參數(shù)都是整數(shù)）。由于不同切割模式不能超過3種，可以用xi表示按照第i種模式（i=1,2,3）切割的原料鋼管的根數(shù)。又設(shè)使用第i種切割模式下每根原料鋼管生產(chǎn)長4m、5m、6m和8m的鋼管數(shù)量分別為r1i，r2i，r3i，r4i。僅以使用的原料總根數(shù)最少為目標(biāo)，即目標(biāo)函數(shù)Min=x1+x2+x3滿足客戶需求的約束條件為r11·x1+r12·x2+r13·x3≥50(8)r21·x1+r22·x2+r23·x3≥10(9)r31·x1+r32·x2+r33·x3≥20(10)r41·x1+r42·x2+r43·x3≥15(11)線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第14頁!基本要求：xij≥0，i=1,2,…,m；j=1,2,…,n。于是可得模型s.t線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第15頁!下面看一個產(chǎn)銷不平衡的例子某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如下表。如果生產(chǎn)出來的柴油機當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護(hù)等費用0.15萬元。試求在完成合同（即每個季度的產(chǎn)量不少于合同訂貨量，供大于求）的情況下，使該廠全年生產(chǎn)總費用為最小的決策方案。線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第16頁!例三、

生產(chǎn)配套問題設(shè)有n個車間要生產(chǎn)m種產(chǎn)品，第j車間每天生產(chǎn)

第i種產(chǎn)品至多aij件（假設(shè)以一天為制定生產(chǎn)計劃的時間單位，則aij表示j車間全天只生產(chǎn)第i種產(chǎn)品而不生產(chǎn)其他產(chǎn)品時的最大產(chǎn)量），假設(shè)這m種產(chǎn)品第i種產(chǎn)品需要bi件配成一套，問如何安排生產(chǎn)任務(wù)才能使產(chǎn)出的成套產(chǎn)品最多？注：以一天為制定生產(chǎn)計劃的時間單位解：1,確定決策變量：因為主要是對一天的時間進(jìn)行分配，使哪一段時間生產(chǎn)哪種產(chǎn)品。所以令Xij表示j車間安排用于生產(chǎn)i種產(chǎn)品的時間（占全天的比例），那么aij·xij表示j車間每天生產(chǎn)i種產(chǎn)線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第17頁!時間限制：xij表示j車間安排用于生產(chǎn)i種產(chǎn)品的時間，因為要生產(chǎn)m種產(chǎn)品，所以j車間一天的時間被分成了m份，故共有n個不等式?；疽螅喝绻詙ij為決策變量，則yij取值為非負(fù)整數(shù)，模型為目標(biāo)函數(shù)線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第18頁!例四指派問題（也稱0——1規(guī)劃）設(shè)有n項任務(wù)要分給n個人去完成，一人只能完成一項，由于每個人的專長不同，故完成不同任務(wù)所需要的成本（或收益）也不同，若第i個人完成第j項任務(wù)的成本（或收益）為cij，問題是如何分派這些任務(wù)（哪一個人去完成哪一項任務(wù)），才能使總成本最?。ɑ蚩偸找孀畲螅窟@個問題似乎不知道什么是決策變量，但我們可以人為量化。線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第19頁!模型為

目標(biāo)函數(shù)約束為線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第20頁!運籌學(xué)不平衡指派問題有12345項工作，分配給甲。乙。丙。丁四個人完成，每個人完成時間如下：12345甲12981517乙2018132512丙2410182613丁1315101916由于工作數(shù)多于人數(shù)故考慮：每個工人僅能完成一項工作，問如何安排工作使總的工作時間最短？假如工作4必須完成，則又該如何指派使總的工作時間最短？線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第21頁!鋼管切割問題：某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出，從鋼管廠進(jìn)貨時所得到的鋼管都是19M。（1）現(xiàn)有一客戶需要50根4M，20根6M和15根8M的鋼管，應(yīng)如何下料最節(jié)??？（2）零售商如果采用不同的切割模式太多，將會導(dǎo)致生產(chǎn)過程復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外該客戶需要（1）種的三種鋼管外，還需要10根5M的鋼管，該如何下料最節(jié)??？線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第22頁!例如，將長19m的鋼管切割成3根4m的鋼管是可行的，但余料為7m，可進(jìn)一步將7m的余料切割成4m鋼管（余料為3m），或者將7m的余料切割成6m鋼管（余料為1m）。經(jīng)過簡單的計算可知，問題1）的合理切割模式一共有7種，如表3所示：于是問題化為在滿足客戶需要的條件下，按照哪幾種合理的模式，每種模式切割多少根原料鋼管最為節(jié)省。而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)，一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最少。下面將對這兩個目標(biāo)分別討論。線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第23頁!模型問題1）用xi表示按照表3第i種模式（i=1,2,…,7）切割的原料鋼管的根數(shù)，若以切割后剩余的總余料量最小為目標(biāo)，則按照表3最后一列可得模型一：目標(biāo)函數(shù)總余料最少min=3x1+x2+3x3+3x4+x5+x6+3x7(1)約束條件為客戶的需求，按照表3應(yīng)有4x1+3x2+2x3+x4+x5≥50(3)x2+2x4+x5+3x6≥20(4)x3+x5+2x7≥15(5)其中決策變量根數(shù)xi顯然應(yīng)當(dāng)是非負(fù)整數(shù)若以切割原料鋼管的總根數(shù)最少為目標(biāo)，則模型二：總根數(shù)Min=x1+x2+x3+x4+x5+x6+x7(2)約束條件為客戶的需求，與上面一樣，不變。線性規(guī)劃中的若干問題共25頁，您現(xiàn)在瀏覽的是第24頁!每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過19m，也不能少于16m（余料不能大