線(xiàn)性規(guī)劃中的若干問(wèn)題

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

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

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

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

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

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

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

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