運(yùn)籌學(xué) 1-4 線性規(guī)劃的應(yīng)用課件

1.4線性規(guī)劃的應(yīng)用

一、使用線性規(guī)劃方法處理實(shí)際問題

必須具備的條件(建模條件)：優(yōu)化條件---問題的目標(biāo)有極大化或極小化的要求,而且能用決策變量的線性函數(shù)來表示。選擇條件---有多種可供選擇的可行方案，以便從中選取最優(yōu)方案。3）限制條件---達(dá)到目標(biāo)的條件是有一定限制的（比如，資源的供應(yīng)量有限度等），而且這些限制可以用決策變量的線性等式或線性不等式表示出來。此外，描述問題的決策變量相互之間應(yīng)有一定的聯(lián)系，有可能建立數(shù)學(xué)關(guān)系，即這些變量之間是內(nèi)部相關(guān)的。第三步：明確目標(biāo)要求，并用決策變量的線性函數(shù)來表示，確定對函數(shù)是取極大還是取極小的要求。決策變量的非負(fù)要求可以根據(jù)問題的實(shí)際意義加以確定。

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

三、經(jīng)濟(jì)管理領(lǐng)域中

幾類典型的LP問題

經(jīng)濟(jì)管理領(lǐng)域中有大量的實(shí)際問題可以歸結(jié)為線性規(guī)劃問題來研究，這些問題背景不同，表現(xiàn)各異，但數(shù)學(xué)模型卻有著完全相同的形式。

盡可能多地掌握一些典型的模型不僅有助于深刻理解線性規(guī)劃本身的理論和方法，而且有利于靈活地處理千差萬別的實(shí)際問題，提高解決實(shí)際問題的能力。（一）

生產(chǎn)組織與計(jì)劃問題1.產(chǎn)品計(jì)劃問題2.產(chǎn)品配套問題1、產(chǎn)品計(jì)劃問題

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

一般的產(chǎn)品計(jì)劃問題舉例

例1-8：某工廠生產(chǎn)A、B兩種產(chǎn)品，均需經(jīng)過兩道工序，每生產(chǎn)一噸產(chǎn)品A需要經(jīng)第一道工序加工2小時(shí)，第二道工序加工3小時(shí)；每生產(chǎn)一噸產(chǎn)品B需要經(jīng)第一道工序加工3小時(shí)，第二道工序加工4小時(shí)。可供利用的第一道工序?yàn)?2小時(shí)，第二道工序?yàn)?4小時(shí)。

生產(chǎn)產(chǎn)品B的同時(shí)產(chǎn)出副產(chǎn)品C，每生產(chǎn)一噸產(chǎn)品B，可同時(shí)得到2噸產(chǎn)品C而毋需外加任何費(fèi)用；副產(chǎn)品C一部分可以盈利，剩下的只能報(bào)廢。

信息整理：利潤與產(chǎn)量的關(guān)系圖：

數(shù)學(xué)模型：

設(shè)：x1——產(chǎn)品A的產(chǎn)量，x2——產(chǎn)品B的產(chǎn)量，x3——產(chǎn)品C的銷售量，x4——產(chǎn)品C的報(bào)廢量。依題意，可得2、產(chǎn)品配套問題

例1-9

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

例1-9有關(guān)信息表其中：xij表示第i個(gè)車間生產(chǎn)第j個(gè)零件的時(shí)間

注意——Z是非線性表達(dá)式！

于是得到該問題的LP模型為：該LP求解可得：解決這類問題一般有兩個(gè)步驟：

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

例1-10某廠接受了一批加工定貨，客戶要求加工100套鋼架，每套由長2.9米、2.1米和1.5米的圓鋼各一根組成。現(xiàn)在僅有一批長7.4米的棒料毛坯，問應(yīng)如何下料，使所用的棒料根數(shù)最少？排列下料方案思路圖

設(shè)xi為按第i種方案下料的棒料根數(shù)，建立LP模型如下：（三）

合理配料問題

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

營養(yǎng)問題已知數(shù)據(jù)表

設(shè)x1、x2分別為甲、乙兩種食品的采購量，則購買兩種食品的總費(fèi)用為Z=1.2x1+1.9x2，依題意可列出下面的線性規(guī)劃：

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

&運(yùn)動員集訓(xùn)隊(duì)食譜設(shè)計(jì)；

&幼兒園、醫(yī)院等特殊群體的營養(yǎng)配餐；&機(jī)關(guān)、學(xué)校、企業(yè)等企事業(yè)單位團(tuán)體伙食設(shè)計(jì)；&家庭食譜設(shè)計(jì)；課程設(shè)計(jì)選題建議：為所在班級同學(xué)設(shè)計(jì)不同要求的食譜對不同對象的營養(yǎng)要求——從營養(yǎng)學(xué)資料和通過醫(yī)生咨詢得到；各種食品的價(jià)格——通過不同季節(jié)的市場調(diào)查獲?。灰恍┨厥庖?，比如飲食習(xí)慣、偏好等——可通過適當(dāng)處理，轉(zhuǎn)化為約束條件加入模型；資料獲取渠道及特殊要求的處理建議：

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

已知各種原料的購進(jìn)價(jià)1公斤分別為:0.314(玉米)、054(豆餅)、0.22（麥麩）、1.20（魚粉）、0.40（骨粉）、0.50（雞促進(jìn)素）元。

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

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

（四）

運(yùn)輸問題運(yùn)輸問題大體上可以分為四種類型：

1、產(chǎn)銷平衡的運(yùn)輸問題（也稱物資調(diào)運(yùn)問題）

2、產(chǎn)銷不平衡的運(yùn)輸問題

3、作物布局問題

一般提法是：在若干塊土地上種植若干種作物，已知各塊土地的面積、作物計(jì)劃播種面積及單產(chǎn)，問如何安排種植計(jì)劃，使總產(chǎn)量最高？

4、工廠布局問題

一般提法；設(shè)有n個(gè)原料產(chǎn)地A1、A2、…、An生產(chǎn)某種原料分別為ai個(gè)單位，同時(shí)又分別需要成品bi個(gè)單位（i=1，2，…n），而一個(gè)單位成品需c個(gè)單位原料制成。若在Ai地設(shè)加工廠，則產(chǎn)品加工費(fèi)用為di元/單位，在Ai地設(shè)廠對生產(chǎn)規(guī)劃有一定的限制——生產(chǎn)成品的數(shù)量最多為li個(gè)單位，最少為fi個(gè)單位。原料的單位運(yùn)價(jià)及成品的單位運(yùn)價(jià)均為已知，問應(yīng)在何地設(shè)廠、生產(chǎn)多少成品才能既滿足需要又使生產(chǎn)費(fèi)用（包括原料和成品運(yùn)費(fèi)、成品加工費(fèi)）最??？例1-13某油田通過輸油管道向港口輸送原油，中間有4個(gè)泵站，每段管道上的輸送能力如圖所示，已知泵站沒有儲存能力，求這個(gè)系統(tǒng)的最大輸送能力。（五）最大流量問題泵站4泵站3油田S泵站2泵站1碼頭t512

4811

67

10設(shè)從各點(diǎn)往其它點(diǎn)的輸送量如下表所示

出發(fā)點(diǎn)

到達(dá)點(diǎn)

輸送量SS泵站1泵站1泵站2泵站2泵站3泵站3泵站4泵站1泵站2泵站3碼頭t泵站3泵站4泵站4碼頭t碼頭tx1x2x3x4x5x6x7x8x9依題意：目標(biāo)函數(shù)為輸送原油的總量；約束條件有兩