PART04線性規(guī)劃的應用線性規(guī)劃的應用一、使用線性規(guī)劃方法處理實際問題必須具備的條件

(建模條件)：1、優(yōu)化條件---問題的目標有極大化或極小化的要求,而且能用決策變量的線性函數(shù)來表示。2、選擇條件---有多種可供選擇的可行方案，以便從中選取最優(yōu)方案。3、限制條件---達到目標的條件是有一定限制的（比如，資源的供應量有限度等），而且這些限制可以用決策變量的線性等式或線性不等式表示出來。此外，描述問題的決策變量相互之間應有一定的聯(lián)系，有可能建立數(shù)學關系，即這些變量之間是內(nèi)部相關的。線性規(guī)劃的應用二、建模步驟：

第一步：設置要求解的決策變量。決策變量選取得當，不僅能順利地建立模型而且能方便地求解，否則很可能事倍功半。

第二步：找出所有的限制，即約束條件，并用決策變量的線性方程或線性不等式來表示。當限制條件多，背景比較復雜時，可以采用圖示或表格形式列出所有的已知數(shù)據(jù)和信息，以避免“遺漏”或“重復”所造成的錯誤。

第三步：明確目標要求，并用決策變量的線性函數(shù)來表示，確定對函數(shù)是取極大還是取極小的要求。決策變量的非負要求可以根據(jù)問題的實際意義加以確定。

討論：這三步的順序可以顛倒嗎？

為什么？線性規(guī)劃的應用

三、經(jīng)濟管理領域中幾類典型的LP問題

經(jīng)濟管理領域中有大量的實際問題可以歸結(jié)為線性規(guī)劃問題來研究，這些問題背景不同，表現(xiàn)各異，但數(shù)學模型卻有著完全相同的形式。盡可能多地掌握一些典型的模型不僅有助于深刻理解線性規(guī)劃本身的理論和方法，而且有利于靈活地處理千差萬別的實際問題，提高解決實際問題的能力。線性規(guī)劃的應用（一）

生產(chǎn)組織與計劃問題1.

產(chǎn)品計劃問題2.

產(chǎn)品配套問題線性規(guī)劃的應用1、產(chǎn)品計劃問題

問題的一般提法：用若干種原材料（資源）生產(chǎn)某幾種產(chǎn)品，原材料（或資源）供應有一定限制，要求制定一個產(chǎn)品生產(chǎn)計劃，使其在一定數(shù)量的資源限制條件下能得到最大的收益。線性規(guī)劃的應用

如果用，

單位產(chǎn)品所需資源數(shù)（如原材料、人力、時間等）、所得利潤及可供應的資源總量已知，如表所示，問應如何組織生產(chǎn)才能使利潤最大？線性規(guī)劃的應用線性規(guī)劃的應用設出產(chǎn)品的計劃數(shù)，可列出這類問題的數(shù)學模型如下：

線性規(guī)劃的應用一般的產(chǎn)品計劃問題舉例

例1-7某工廠生產(chǎn)A、B兩種產(chǎn)品，均需經(jīng)過兩道工序，每生產(chǎn)一噸產(chǎn)品A需要經(jīng)第一道工序加工2小時，第二道工序加工3小時；每生產(chǎn)一噸產(chǎn)品B需要經(jīng)第一道工序加工3小時，第二道工序加工4小時?？晒├玫牡谝坏拦ば驗?2小時，第二道工序為24小時。生產(chǎn)產(chǎn)品B的同時產(chǎn)出副產(chǎn)品C，每生產(chǎn)一噸產(chǎn)品B，可同時得到2噸產(chǎn)品C而毋需外加任何費用；副產(chǎn)品C一部分可以盈利，剩下的只能報廢。出售產(chǎn)品A每噸能盈利400元、產(chǎn)品B每噸能盈利1000元，每銷售一噸副產(chǎn)品C能盈利300元，而剩余要報廢的則每噸損失200元。經(jīng)市場預測，在計劃期內(nèi)產(chǎn)品C最大銷量為5噸。試列出線性規(guī)劃模型，決定A、B兩種產(chǎn)品的產(chǎn)量，使工廠總的利潤最大。線性規(guī)劃的應用

信息整理：線性規(guī)劃的應用線性規(guī)劃的應用數(shù)學模型：設：x1——產(chǎn)品A的產(chǎn)量，x2——產(chǎn)品B的產(chǎn)量，x3——產(chǎn)品C的銷售量，x4——產(chǎn)品C的報廢量。依題意，可得線性規(guī)劃的應用2、產(chǎn)品配套問題

例1-8

某產(chǎn)品由兩個零件I和三個零件II組成，每個零件均可由三個車間各自生產(chǎn)，但各車間的生產(chǎn)效率和總工時限制各不相同，表中給出了有關信息。試確定各車間生產(chǎn)每種零件的工作時間，使生產(chǎn)產(chǎn)品的件數(shù)最多。

線性規(guī)劃的應用線性規(guī)劃的應用例1-8有關信息表處理：線性規(guī)劃的應用于是得到該問題的LP模型為：線性規(guī)劃的應用

(二)

合理下料問題在加工業(yè)中，經(jīng)常遇到這類問題。

問題的一般提法是：已知某種尺寸的棒料或板材，需要將其切割成一定數(shù)量既定規(guī)格的幾種零件毛坯，問應如何選取合理的下料方法，使得既滿足對截出毛坯的數(shù)量要求，又使所用的原材料最少（或廢料最少）？線性規(guī)劃的應用解決這類問題一般有兩個步驟：

步驟一、按照一定的思路設法列出所有的排料方案（也稱下料方案或排料圖），當方案很多，甚至無法一一列出時，通常應先確定一些篩選原則，把明顯不合理的方案刪除，僅僅考慮剩余的為數(shù)不太多的方案；步驟二、設xi表示按第ｉ種方案下料的棒料根數(shù)（或板材塊數(shù)）i=1,2,…,n，按照問題的要求建立LP模型。線性規(guī)劃的應用例1-9

某廠接受了一批加工定貨，客戶要求加工100套鋼架，每套由長2.9米、2.1米和1.5米的圓鋼各一根組成?，F(xiàn)在僅有一批長7.4米的棒料毛坯，問應如何下料，使所用的棒料根數(shù)最少？線性規(guī)劃的應用

最簡單的處理方法：從一根棒料上截取2.9米、2.1米和1.5米的棒料各一根，正好配成一套鋼架，100套鋼架總共需要100根棒料毛坯。每根棒料毛坯剩下0.9米的料頭,100根毛坯總共剩90米料頭。

——這是最好的辦法嗎？合理套裁肯定會有更好的效果。先設法列出所有的下料方案，思路如圖。線性規(guī)劃的應用排列下料方案思路圖

線性規(guī)劃的應用

設xi為按第i種方案下料的棒料根數(shù)，建立LP模型如下：線性規(guī)劃的應用

（三）

合理配料問題

問題的一般提法：由多種原料配置成含有m種成分的產(chǎn)品，已知產(chǎn)品中所含各成分的需要量及每種原料的價格，同時知道各種原料中所含m種成分的數(shù)量，要求給出使產(chǎn)品成本最低的配料方案。如：伙食問題（也稱營養(yǎng)問題）、飼料配比問題、化工產(chǎn)品中的混合問題等都屬于這類問題。

線性規(guī)劃的應用例1-10營養(yǎng)問題

要求制定既經(jīng)濟又合乎健康標準的食譜。一個簡單的例子：現(xiàn)準備采購甲、乙兩種食品，表中給出了已知價格及相關的營養(yǎng)成分。最右欄給出了按營養(yǎng)學標準每人每天的最低需要量。問應如何采購食品才能在保證營養(yǎng)要求的前提下花費最省？線性規(guī)劃的應用

營養(yǎng)問題已知數(shù)據(jù)表線性規(guī)劃的應用

線性規(guī)劃的應用

營養(yǎng)問題適用范圍：

&

運動員集訓隊食譜設計；

&

幼兒園、醫(yī)院等特殊群體的營養(yǎng)配餐；

&

機關、學校、企業(yè)等企事業(yè)單位團體伙食設計；

&家庭食譜設計；線性規(guī)劃的應用

對不同對象的營養(yǎng)要求——從營養(yǎng)學資料和通過醫(yī)生咨詢得到；

各種食品的價格——通過不同季節(jié)的市場調(diào)查獲取；

一些特殊要求，比如飲食習慣、偏好等——可通過適當處理，轉(zhuǎn)化為約束條件加入模型；資料獲取渠道及特殊要求的處理建議：線性規(guī)劃的應用

例1-11（飼料配比問題）某配合飼料廠生產(chǎn)以雞飼料為主的配合飼料，現(xiàn)準備研制一種新的肉用仔雞專用飼料，所用原料的營養(yǎng)成分和飼養(yǎng)標準見下表，希望這種新飼料能滿足肉用仔雞的喂養(yǎng)需要又使總成本盡可能低，應如何設計配比方案？線性規(guī)劃的應用線性規(guī)劃的應用

已知各種原料的購進價1公斤分別為:0.314(玉米)、054(豆餅)、0.22（麥麩）、1.20（魚粉）、0.40（骨粉）、0.50（雞促進素）元。線性規(guī)劃的應用

設每100公斤飼料中配給的玉米、豆餅、麥麩、魚粉、骨粉、雞促進素分別為x1、x2、x3、x4、x5、x6公斤，則飼料配比即為x1：x2：x3：x4：x5：x6；于是，可建立下面的線性規(guī)劃：線性規(guī)劃的應用

是否可以將約束條件兩邊分別擴大一個倍數(shù)再進行計算？

線性規(guī)劃的應用（四）

運輸問題運輸問題大體上可以分為四種類型：1、產(chǎn)銷平衡的運輸問題（也稱物資調(diào)運問題）2、產(chǎn)銷不平衡的運輸問題3、作物布局問題4、工廠布局問題線性規(guī)劃的應用類型1：產(chǎn)銷平衡的運輸問題（物資調(diào)運問題）線性規(guī)劃的應用

線性規(guī)劃的應用線性規(guī)劃的應用

線性規(guī)劃的應用

可得運輸問題的數(shù)學模型如下：

類型2：產(chǎn)銷不平衡的運輸問題線性規(guī)劃的應用對于產(chǎn)銷不平衡的運輸問題，可以通過將其轉(zhuǎn)化為一個產(chǎn)銷平衡的運輸問題來求解。當供大于求時，可以增加一個虛擬銷地，供不應求時則增加一個虛擬產(chǎn)地，對應的運距（或運價）均設為零，然后應用表上作業(yè)法求出最優(yōu)調(diào)運方案。類型3：作物布局問題一般提法是：在若干塊土地上種植若干種作物，已知各塊土地的面積、作物計劃播種面積及單產(chǎn)，問如何安排種植計劃，使總產(chǎn)量最高？類型4：工廠布局問題線性規(guī)劃的應用

作物布局問題和工廠布局問題表面上看和運輸問題沒有聯(lián)系，但從建立的線性規(guī)劃模型來看則完全類似，所以上述幾類問題均歸結(jié)為“運輸問題”。線性規(guī)劃的應用線性規(guī)劃的應用例1-12甲、乙兩個煤礦供應A、B、C三個城市用煤，各煤礦產(chǎn)量及各城市需煤量、各煤礦到各城市的運輸距離見下表，求使總運輸量最少的調(diào)運方案。線性規(guī)劃的應用

線性規(guī)劃的應用根據(jù)本題中的煤礦日產(chǎn)量約束城市需求約束，以及總運輸成本最小的目標可得該問題的數(shù)學模型如下：例1-13

某油田通過輸油管道向港口輸送原油，中間有4個泵站，每段管道上的輸送能力如圖所示，已知泵站沒有儲存能力，求這個系統(tǒng)的最大輸送能力。（五）最大流量問題線性規(guī)劃的應用泵站4泵站3油田S泵站2泵站1碼頭t512

481167

10線性規(guī)劃的應用

設從各點往其它點的輸送量如下表所示

出發(fā)點

到達點

輸送量SS泵站1泵站1泵站2泵站2泵站3泵站3泵站4泵站1泵站2泵站3碼頭t泵站3泵站4泵站4碼頭t碼頭tx1x2x3x4x5x6x7x8x9線性規(guī)劃的應用依題意：目標函數(shù)為輸送原油的總量；約束條件有兩類:一類是管道上的流量約束；另一類是每個中間泵站上的平衡約束，即中間泵站上的原油流入量和流出量相等根據(jù)上述分析建立線性規(guī)劃模型如下：線性規(guī)劃的應用1號泵站平衡約束2號泵站平衡約束3號泵站平衡約束4號泵站平衡約束相應弧上的約束線性規(guī)劃的應用（1）排班問題六、其他類型的問題線性規(guī)劃的應用例1-14某快遞公司新設了一個快遞分揀部，處理每天送達和外寄的快遞件，現(xiàn)需要招聘一批職工來操作機器進行分揀工作。該公司由以往的統(tǒng)計數(shù)據(jù)分析與經(jīng)驗預測得到每個時間段到達的快件數(shù)如下表所示：時段到達快件數(shù)量時段到達快件數(shù)量10點前500014點-16點800010點-12點700016點-18點750012點-14點800018點-20點6000線性規(guī)劃的應用已知該分揀部共有11臺機器，每臺機器的分揀速度為500件/小時，每臺機器各需要配一名職工。分揀部一部分為正式職工，上班時間分別為10-18點、12-20點、14點-22點，每人每天工資200元；另一部分是臨時工（非正式職工），每天上班6小時，分別為12-18點、14-20點、16-22點，每天工資120元，職工上班的班次時間段如下表所示?？旒幚淼囊?guī)則是從每個整點起可處理該整點前到達的快件數(shù)，因快件有時間性要求，凡是12點前到達的快件必須在16點以前處理完；16點以前到達的，必須在18點以前處理完；全部快件在當天22點以前處理完。問該分揀部要完成快件處理任務，應設多少名正式職工與臨時工，并使總的工資支出為最少。時段到達快件數(shù)量時段到達快件數(shù)量10點前500014點-16點800010點-12點700016點-18點750012點-14點800018點-20點6000線性規(guī)劃的應用

正式職工上班時間臨時工上班時間10-18點12-20點14點-22點12-18點14-20點16-22點10點前

10點-12點1

12點-14點11

1

14點-16點11111

16點-18點11111118點-20點

11

1120點-22點

1

1各時段工作人員值班表線性規(guī)劃的應用其中，約束（1）-（5）表示各個時段內(nèi)，投入兩類職工的數(shù)量和可處理的該時間段前到達的快件數(shù)，約束（6）-（8）為題目中對于快件處理時限的要求，約束（9）表示由于分揀機器的限制而導致的投入員工數(shù)量的限