物流優(yōu)化技術(shù)課件-第3章35-線性規(guī)劃的應(yīng)用

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

必須具備的條件(建模條件)：優(yōu)化條件---問題的目標(biāo)有極大化或極小化的要求,而且能用決策變量的線性函數(shù)來表示。選擇條件---有多種可供選擇的可行方案，以便從中選取最優(yōu)方案。3.3線性規(guī)劃的應(yīng)用

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

3）限制條件---達(dá)到目標(biāo)的條件是有一定限制的（比如，資源的供應(yīng)量有限度等），而且這些限制可以用決策變量的線性等式或線性不等式表示出來。此外，描述問題的決策變量相互之間應(yīng)有一定的聯(lián)系，有可能建立數(shù)學(xué)關(guān)系，即這些變量之間是內(nèi)部相關(guān)的。3）限制條件---達(dá)到目標(biāo)的條件是有一定限制的（比如，資源的

二、建模步驟：

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

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

二、建模步驟：第一步：設(shè)置要求解的決策第三步：明確目標(biāo)要求，并用決策變量的線性函數(shù)來表示，確定對函數(shù)是取極大還是取極小的要求。決策變量的非負(fù)要求可以根據(jù)問題的實(shí)際意義加以確定。

三、管理領(lǐng)域中

幾類典型的LP問題第三步：明確目標(biāo)要求，并用決策變量的線性函數(shù)來表示，確定（一）

生產(chǎn)組織與計(jì)劃問題1.產(chǎn)品計(jì)劃問題2.產(chǎn)品配套問題3.人力資源問題（一）

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

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

如果用，

單位產(chǎn)品所需資源數(shù)（如原材料、人力、時(shí)間等）、所得利潤及可供應(yīng)的資源總量已知，根據(jù)有關(guān)信息，問應(yīng)如何組織生產(chǎn)才能使利潤最大？如果用產(chǎn)品計(jì)劃問題有關(guān)信息表

產(chǎn)品計(jì)劃問題有關(guān)信息表

設(shè)出產(chǎn)品的計(jì)劃數(shù)，可列出這類問題的數(shù)學(xué)模型如下：設(shè)出產(chǎn)品的計(jì)劃數(shù)，可列出這類問題的數(shù)學(xué)模型2、人力資源問題

例1-13某商場對一周內(nèi)客流量進(jìn)行統(tǒng)計(jì)分析，按照服務(wù)定額得知一周中每天售貨人員需求量

。若售貨員每周工作5天，休息2天，并要求休息時(shí)間是連續(xù)的，商場應(yīng)如何安排售貨人數(shù)，才能夠既滿足工作需要，又使配備的售貨人員最少？2、人力資源問題例1-13設(shè)：x為星期i開始休息的人數(shù)，星期日記為x7，則每一天工作的人數(shù)應(yīng)為下一日開始休息的人員直至由下一日算起的第5個(gè)工作日，亦即非當(dāng)日、前天休息的人員總和。設(shè)：x為星期i開始休息的人數(shù)，星期日記為x7，則每一天工作的物流優(yōu)化技術(shù)ppt課件-第3章33、產(chǎn)品配套問題

例3-9某產(chǎn)品由兩個(gè)零件I和三個(gè)零件II組成，每個(gè)零件均可由三個(gè)車間各自生產(chǎn)，但各車間的生產(chǎn)效率和總工時(shí)限制各不相同，根據(jù)有關(guān)信息，試確定各車間生產(chǎn)每種零件的工作時(shí)間，使生產(chǎn)產(chǎn)品的件數(shù)最多。3、產(chǎn)品配套問題例3-9例3-9有關(guān)信息表其中：xij表示第i個(gè)車間生產(chǎn)第j個(gè)零件的時(shí)間

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

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

理

①引入一個(gè)新變量Y，令Y=???íìtyü++++321156,216108min322212312111xxxxxx則目標(biāo)要求可以寫成：MaxZ=Y

②

把Y的表達(dá)式改寫成兩個(gè)不等式增添到約束條件中去

;321156,216108322212312111XXXYXXXY++￡++￡

處

理①引入一個(gè)新變量Y于是得到該問題的LP模型為：于是得到該問題的LP模型為：(二)

合理下料問題

在加工業(yè)中，經(jīng)常遇到這類問題。問題的一般提法是：已知某種尺寸的棒料或板材，需要將其切割成一定數(shù)量既定規(guī)格的幾種零件毛坯，問應(yīng)如何選取合理的下料方法，使得既滿足對截出毛坯的數(shù)量要求，又使所用的原材料最少（或廢料最少）？(二)

合理下料問題在加工解決這類問題一般有兩個(gè)步驟：

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

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

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

——這是最好的辦法嗎？合理套裁肯定會有更好的效果。先設(shè)法列出所有的下料方案，思路如圖。最簡單的處理方法：從一根棒料上截取2.9米、2.17.47.4

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

（三）

合理配料問題

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

（三）

合理配料問題例、營養(yǎng)問題

要求制定一個(gè)既經(jīng)濟(jì)又合乎健康標(biāo)準(zhǔn)的食譜

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

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

如何設(shè)置決策變量？營養(yǎng)問題已知數(shù)據(jù)表如何設(shè)置決策變量？

設(shè)x1、x2分別為甲、乙兩種食品的采購量，則購買兩種食品的總費(fèi)用為Z=1.2x1+1.9x2，依題意可列出下面的線性規(guī)劃：設(shè)x1、x2分別為甲、乙兩種食品的采購量，則購買兩作業(yè)某戰(zhàn)略轟炸機(jī)群奉命摧毀敵人軍事目標(biāo)。已知該目標(biāo)有四個(gè)要害部位，只要摧毀其中之一即可達(dá)到目的。為完成此項(xiàng)任務(wù)的汽油消耗量限制為48000升、重型炸彈48枚、輕型炸彈32枚。飛機(jī)攜帶重型炸彈