運(yùn)籌學(xué)OperationsResearchChapter1線性規(guī)劃LinearProgramming1.LP的數(shù)學(xué)模型

MathematicalModelofLP2.圖解法

GraphicalMethod3.標(biāo)準(zhǔn)型NormalizedFormofLP4.基本概念BasicConcepts5.單純形法

SimplexMethod6.人工變量法

ArtificialVariableMethod7.計(jì)算公式CalculateFormula4/8/2025線性規(guī)劃（LinearProgramming縮寫為LP）是運(yùn)籌學(xué)的重要分支之一，在實(shí)際中應(yīng)用得較廣泛，其方法也較成熟，借助計(jì)算機(jī)，使得計(jì)算更方便，應(yīng)用領(lǐng)域更廣泛和深入。

線性規(guī)劃通常解決下列兩類問題

（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)；

（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤最大.

4/8/2025產(chǎn)品設(shè)備甲乙丙設(shè)備能力（小時(shí)）A31220B22415C

40116D

03512

利潤（元/件）

435【例1.1】某企業(yè)計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別要在A、B、C、D、四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如表1-1所示，已知各設(shè)備在計(jì)劃期內(nèi)的能力分別為20、15、16、12小時(shí)；每生產(chǎn)一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為4、3、5元。企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)在計(jì)劃期內(nèi)總的利潤收入最大？4/8/2025【解】設(shè)x1、x2、x3

分別為甲、乙、丙三種產(chǎn)品的產(chǎn)量數(shù)學(xué)模型為：4/8/2025線性規(guī)劃的數(shù)學(xué)模型由決策變量

Decisionvariables

目標(biāo)函數(shù)Objectivefunction及約束條件Constraints構(gòu)成。稱為三個(gè)要素。其特征是：1．解決問題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；2．解決問題的約束條件是一組多個(gè)決策變量的線性不等式或等式。怎樣辨別一個(gè)模型是線性規(guī)劃模型？4/8/2025

200萬m3500萬m3工廠2：【例1.2】河流1：每天流量500萬m3；河流2：每天流量200萬m3,水質(zhì)要求：污水含量≤0.2%2萬m31.4萬m3污水從工廠1流向工廠2有20%可以凈化

處理污水成本：工廠11000元/萬m3；工廠2800元/萬m3

問兩個(gè)工廠每天各處理多少污水總成本最少？工廠1：【解】設(shè)x1

、x2分別為工廠1、2每天處理的污水量（萬m3），則4/8/2025數(shù)學(xué)模型為：4/8/2025【例1.3】下料問題，某一機(jī)床需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是2.9，2.1,1.5（m），這些軸需要用同一種圓鋼來做，圓鋼長度為7.4m。現(xiàn)在要制造100臺(tái)機(jī)床，最少要用多少圓鋼來生產(chǎn)這些軸？【解】第一步：設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1,y2,y3,則切割方式可用不等式2.9y1+2.1y2+1.5y3≤7.4表示，求這個(gè)不等式關(guān)于y1，y2，y3的非負(fù)整數(shù)解。例如y1=2,y2=0則y3只能為1，余料為0.1。象這樣的非負(fù)整數(shù)解共有8組，也就是有8種下料方式，如表1-2所示。第二步：建立線性規(guī)劃數(shù)學(xué)模型。設(shè)xj(j=1,2…,8)為第j種下料方案所用圓鋼的根數(shù)。則數(shù)學(xué)模型為4/8/2025

方案規(guī)格12345678需求量y1(2.9m)21110000100y2(2.1m)02103210100y3(1.5m)101302341000.10.30.901.10.20.81.42.9y1+2.1y2+1.5y3≤7.4表1－2minz=x1+x2+x3+x4+x5+x6+x7+x82x1+x2+x3+x4

1002x2+x3+3x5+2x6+x7

100x1+x3+3x4+2x6+3x7+4x8

100xj

0,j=1,2,…,84/8/2025最優(yōu)下料方案為：第一種方案用料10根，第二種方案50根，第四種方案30根，總余料為16m。用§1.5的單純形法求得最優(yōu)解為x1=10,x2=50,x4=30，其余x為零，即第一種方案用料10根，第二種方案用50根，第四種方案用30根，共計(jì)用料90根。如果要求余料最少，則目標(biāo)函數(shù)及約束條件為：minz=0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x82x1+x2+x3+x4=1002x2+x3+3x5+2x6+x7=100x1+x3+3x4+2x6+3x7+4x8=100xj

0,j=1,2,…,84/8/2025注意：1.余料不能超過最短毛坯的長度；2.最好將毛坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的；不能遺漏了方案。3.在實(shí)際中，如果毛坯規(guī)格較多，毛坯的長度又很短的方案可能很多，甚至有幾千個(gè)方案，這時(shí)用人工計(jì)算幾乎是不可能的，即使計(jì)算機(jī)也有可能溢出。當(dāng)碰到這種情況時(shí)，可以給余料確定一個(gè)臨界值μ，當(dāng)某方案的余料大于μ時(shí)馬上舍去這種方案，從而減少占用計(jì)算機(jī)內(nèi)存，也簡化了后面的數(shù)學(xué)模型。

4/8/2025【例1.4】配料問題。某一合金公司同一科研單位簽訂一項(xiàng)包含有四種金屬的合金訂購單，要求的成分規(guī)格是：金屬A不少于23%，金屬B不多于15%，金屬C不多于4%，金屬D要界于35%~65%之間，不允許有其他成分。合金公司擬從六種不同級(jí)別的礦石中進(jìn)行冶煉，每種礦物的成分含量和價(jià)格如表1-3所示。礦石雜質(zhì)在治煉過程中廢棄，現(xiàn)要求也每噸合金成本最低的礦物數(shù)量。假設(shè)礦石在冶煉過程中，金屬含量沒有發(fā)生變化。4/8/2025金屬礦石

A%B%C%D%雜質(zhì)％費(fèi)用（元/t）1251010253023240003030203201003040184015520601052020040202768515175512表1－34/8/2025【解】設(shè)xj（j=1,2…，6）是第j種礦石數(shù)量，目標(biāo)函數(shù)是總成本最少，得到下列線性規(guī)劃模型minZ=23x1+20x2+18x3+10x4+27x5+12x64/8/2025解：設(shè)x1為第一年的投資;x2為

第一年的保留資金x1+x2=100【例1.5】投資問題。某投資公司在第一年有100萬元資金，每年都有如下的投資方案可供考慮采納：“假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的50%，那么到第三年就可回收第一年投入資金的一倍金額。”投資公司要設(shè)法決定最優(yōu)的投資策略使第六年所掌握的資金最多。第二年：x3為第二年新的投資；x4：第二年的保留資金；4/8/2025第三年：x5為新的投資；x6：第三年的保留資金；第四年：新的投資x7；第四年的保留資金x8；第五年：x9為第五年的保留資金：第五年不再進(jìn)行新的投資，因?yàn)檫@筆投資要到第七年才能回收。約束條件保證每年滿足如下的關(guān)系：追加投資金額+新投資金額+保留資金=可利用的資金總額4/8/2025用單純形法解得：X＝（22.64，72.36，58.54，0，26.02，0，104.06，0，0）’。Z＝208.12。到第六年實(shí)有資金總額為x9+2x7，整理后得到下列線性規(guī)劃模型maxZ=2x7+x9

4/8/2025即：第一年投資22.64元;第二年新投資58.54元;第三年新投資26.02元;第四年新投資104.06元;第六年末有資金208.12萬元。一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中，有m個(gè)約束，有n個(gè)決策變量xj,j=1,2…,n，目標(biāo)函數(shù)的變量系數(shù)用cj表示,

cj稱為價(jià)值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi表示