運(yùn)籌學(xué)基礎(chǔ)-線性規(guī)劃(方法)

第一章線性規(guī)劃及單純形法本章主要內(nèi)容

線性規(guī)劃概述緒論一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型線性規(guī)劃問(wèn)題的圖解法線性規(guī)劃的基本定理單純形法用計(jì)算機(jī)軟件求解線性規(guī)劃問(wèn)題線性規(guī)劃的應(yīng)用舉例2【開(kāi)篇案例】某旅行社為了迎接旅游黃金周的到來(lái)，對(duì)一日游導(dǎo)游人員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如表所示。為了保證導(dǎo)游充分休息，導(dǎo)游每周工作5天，休息兩天，并要求休息的兩天是連續(xù)的。問(wèn)應(yīng)該如何安排導(dǎo)游人員的作息，既滿足工作需要，又使配備的導(dǎo)游人數(shù)最少？一、人力資源分配的問(wèn)題線性規(guī)劃時(shí)間所需導(dǎo)游人數(shù)星期日40星期一34星期二32星期三35星期四28星期五46星期六423【開(kāi)篇案例】明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過(guò)鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如右表。問(wèn)：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？二、生產(chǎn)計(jì)劃的問(wèn)題線性規(guī)劃4【開(kāi)篇案例】某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如右表。問(wèn)：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？三、配料問(wèn)題線性規(guī)劃5【開(kāi)篇案例】某部門現(xiàn)有資金200萬(wàn)元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項(xiàng)目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不超過(guò)30萬(wàn)元；項(xiàng)目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過(guò)80萬(wàn)元；項(xiàng)目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過(guò)100萬(wàn)元；四、投資問(wèn)題問(wèn)：a.應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b.應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在330萬(wàn)元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最??？線性規(guī)劃6歸納上述研究的主要內(nèi)容：

（2）計(jì)劃任務(wù)確定的情況舊：如何統(tǒng)籌安排，精心籌劃，用最少的資源來(lái)實(shí)現(xiàn)。這方面的問(wèn)題涉及到系統(tǒng)的投入和求極小值問(wèn)題（1）資源確定的情況下：如何合理利用、合理規(guī)劃，使得完成的任務(wù)最大。這方面的問(wèn)題涉及到系統(tǒng)的產(chǎn)出和求最大值問(wèn)題研究和應(yīng)用的內(nèi)容是實(shí)現(xiàn)系統(tǒng)的投入產(chǎn)出的問(wèn)題，就是用最少的勞力和物力消耗，獲利更多更好的社會(huì)需求產(chǎn)品。此項(xiàng)研究即為規(guī)劃問(wèn)題線性規(guī)劃7

線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。自1947年美國(guó)數(shù)學(xué)家丹捷格（G.B.Dantzig）提出了求解線性規(guī)劃問(wèn)題的方法——單純形法之后，線性規(guī)劃在理論上趨于成熟，在實(shí)際中的應(yīng)用日益廣泛與深入。特別是在能用計(jì)算機(jī)來(lái)處理成千上萬(wàn)個(gè)約束條件和變量的大規(guī)模線性規(guī)劃問(wèn)題之后，它的適用領(lǐng)域更廣泛了。線性規(guī)劃概述

線性規(guī)劃是一種合理利用資源、合理調(diào)配資源的應(yīng)用數(shù)學(xué)方法。其中：規(guī)劃就是利用某種數(shù)學(xué)方法使得有效資源的運(yùn)用最優(yōu)化；線性就是用來(lái)描述就是之間關(guān)系的函數(shù)是線性函數(shù)。線性規(guī)劃8在生產(chǎn)管理和經(jīng)濟(jì)活動(dòng)中經(jīng)常提出這樣一類問(wèn)題，即如何合理地利用有限的人力、物力、財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果。

在管理中一些典型的線性規(guī)劃應(yīng)用主要包括：

合理利用線材問(wèn)題：如何下料使用材最少

配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)

投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大

產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，使獲利最大

勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要

運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小問(wèn)題：如何建立線性規(guī)劃模型？線性規(guī)劃

盈虧平衡問(wèn)題：掌握企業(yè)盈虧界限，合理安排生產(chǎn)能力9【引例】生產(chǎn)計(jì)劃的問(wèn)題某企業(yè)生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品。這兩種產(chǎn)品都要分別在A、B、C、D四各不同設(shè)備上加工。生產(chǎn)每件產(chǎn)品Ⅰ需占用各設(shè)備為2、1、4、0小時(shí)，生產(chǎn)每件產(chǎn)品Ⅱ需占用各設(shè)備為2、2、0、4小時(shí)，各設(shè)備用于生產(chǎn)這兩種產(chǎn)品的能力分別為12、8、16、12小時(shí)，又知生產(chǎn)一件產(chǎn)品Ⅰ獲得2元，生產(chǎn)Ⅱ獲得3元，問(wèn)如何安排生產(chǎn)，使總的利潤(rùn)最大?！?.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

則該問(wèn)題的數(shù)學(xué)模型表示為

maxZ=

2x1+3x22x1+2x2≤12

x1+2x2≤84x1≤164x2≤12x1≥0,x2≥0設(shè)生產(chǎn)Ⅰ、Ⅱ產(chǎn)品為x1、x2件問(wèn)題：建立線性規(guī)劃模型要考慮的關(guān)鍵要素？線性規(guī)劃10一、線性規(guī)劃問(wèn)題的三大要素決策變量

是指實(shí)際系統(tǒng)或決策問(wèn)題中有待確定的因素，是系統(tǒng)中的可控因素。如生產(chǎn)Ⅰ、Ⅱ產(chǎn)品為x1、x2件，

x1、x2

即為決策變量

決策變量的取值范圍。如此題的

x1≥0、x2≥

0約束條件

任何問(wèn)題都是限定在一定的條件下求解，把各種限制條件表示為一組等式或不等式，稱之為約束條件。如設(shè)備能力、原材料數(shù)量等

是決策者對(duì)決策問(wèn)題目標(biāo)的數(shù)學(xué)描述。如時(shí)間最省、利潤(rùn)最大、成本最低。此題是利潤(rùn)最大

maxZ=

2x1+3x2

約束條件是決策方案可行的保障。

約束條件的基本類型：大于等于“≥”、等于“＝”、小于等于“≤”目標(biāo)函數(shù)

目標(biāo)函數(shù)應(yīng)該是決策變量的線性函數(shù)。

有的目標(biāo)要實(shí)現(xiàn)最大，有的則要求最小。

線性規(guī)劃11二、線性規(guī)劃模型的構(gòu)建線性規(guī)劃建模步驟：明確問(wèn)題，確定目標(biāo)，列出約束條件；

收集資料，確立模型；模型求解與檢驗(yàn)

優(yōu)化后的分析其中：最為困難的是建模線性規(guī)劃12【例1】生產(chǎn)計(jì)劃問(wèn)題線性規(guī)劃某企業(yè)生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品。這兩種產(chǎn)品都要分別在A、B、C、D四各不同設(shè)備上加工。生產(chǎn)每件產(chǎn)品Ⅰ需占用各設(shè)備為2、1、4、0小時(shí)，生產(chǎn)每件產(chǎn)品Ⅱ需占用各設(shè)備為2、2、0、4小時(shí)，各設(shè)備用于生產(chǎn)這兩種產(chǎn)品的能力分別為12、8、16、12小時(shí)，又知生產(chǎn)一件產(chǎn)品Ⅰ獲得2元，生產(chǎn)Ⅱ獲得3元，問(wèn)如何安排生產(chǎn)，使總的利潤(rùn)最大。13建立模型：(1)決策變量

要決策的問(wèn)題是兩種產(chǎn)品的產(chǎn)量，因此有兩個(gè)決策變量：設(shè)x1為產(chǎn)品Ⅰ產(chǎn)量，x2為產(chǎn)品Ⅱ產(chǎn)量。

生產(chǎn)單位產(chǎn)品Ⅰ需占用各設(shè)備A為2工時(shí)，生產(chǎn)單位產(chǎn)品Ⅱ需占用各設(shè)備A為2工時(shí)，A設(shè)備的能力總量限制為12工時(shí)，則A設(shè)備能力約束條件表述為：

(2)約束條件

生產(chǎn)這兩種產(chǎn)品受到現(xiàn)有生產(chǎn)能力的制約，用量不能突破。

2x1+2x2

≤12

同理，B、C、D設(shè)備的能力約束條件為

x1+2x2

≤84x1≤16線性規(guī)劃4x2≤1214

(3)目標(biāo)函數(shù)

目標(biāo)是利潤(rùn)最大化，用Z表示利潤(rùn)，則

(4)非負(fù)約束:

產(chǎn)品Ⅰ、Ⅱ的產(chǎn)量不應(yīng)是負(fù)數(shù)，否則沒(méi)有實(shí)際意義，這個(gè)要求表述為

則該問(wèn)題的數(shù)學(xué)模型表示為maxZ=2x1+3x2

x1

≥0，x2

≥0

目標(biāo)函數(shù)約束條件線性規(guī)劃

maxZ=

2x1+3x22x1+2x2≤12

x1+2x2≤84x1≤164x2≤12x1≥0,x2≥015【例2】運(yùn)輸問(wèn)題

某名牌飲料在國(guó)內(nèi)有三個(gè)生產(chǎn)廠，分布在城市A1、A2,A3,其一級(jí)承銷商有4個(gè)，分布在城市B1、B2、B3、B4，已知各廠的產(chǎn)量、各承銷商的銷售量及從Ai到Bj的每噸飲料運(yùn)費(fèi)為Cij，為發(fā)揮集團(tuán)優(yōu)勢(shì)，公司要統(tǒng)一籌劃運(yùn)銷問(wèn)題，求運(yùn)費(fèi)最小的調(diào)運(yùn)方案。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3632575843297523銷量2314線性規(guī)劃16建立模型：(1)決策變量:設(shè)從Ai到Bj的運(yùn)輸量為xij，

(2)目標(biāo)函數(shù):則運(yùn)費(fèi)最小的目標(biāo)函數(shù)為

minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34供應(yīng)平衡條件(3)約束條件:產(chǎn)量之和等于銷量之和,故要滿足x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3銷售平衡條件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4條件非負(fù)性約束xij≥0(i=1,2,3；j=1,2,3,4)632575843297線性規(guī)劃17【例3】營(yíng)養(yǎng)問(wèn)題

某養(yǎng)雞場(chǎng)所用的混合飼料是由n種配料組成。要求這種混合飼料必須含有m種不同的營(yíng)養(yǎng)成份，而且要求每單位混合飼料中第i種營(yíng)養(yǎng)成份的含量不能低于bi(i=1,2,…,m）。已知第i種營(yíng)養(yǎng)成份在每單位的第j種配料中的含量為aij,j=1,2,…,n，每單位的第j種配料的價(jià)格為cj

。現(xiàn)在要求在保證營(yíng)養(yǎng)條件的前提下，應(yīng)采用何種配方，使混合飼料的成本最小.配料營(yíng)養(yǎng)成份B1B2

…Bn含量A1A2…Ama11a12

…a1na21a22…a2nam1am2…amnb1b2bm單價(jià)c1c2…

cn線性規(guī)劃18建立模型：MinZ=c1x1+c2x2+…+cnxn設(shè)xj

表示在單位混合飼料中，第j種配料的含量（j=1,2,…,n）則有如下的數(shù)學(xué)模型：配料營(yíng)養(yǎng)成份B1B2

…Bn含量A1A2…Ama11a12

…a1na21a22…a2nam1am2…amnb1b2bm價(jià)格c1c2…

cna11x1+a12x2+…+a1nxn≥

b1a21x1+a22x2+…+a2nxn≥

b2……am1x1+am2x2+…+amnxn≥

bmx1≥0,x2≥0,…,xn≥0線性規(guī)劃19【例4】污水處理問(wèn)題

例靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬(wàn)m3，兩工廠之間有一條流量為每天200萬(wàn)m3的支流（見(jiàn)圖）。第一化工廠每天排放污水2萬(wàn)m3，第二化工廠每天排放污水1.4萬(wàn)m3。污水從工廠1流到工廠2前會(huì)有20%自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應(yīng)不大于0.2%。而工廠1和工廠2處理污水的成本分別為1000元/m3和800元/m3。問(wèn)兩工廠各應(yīng)處理多少污水才能使處理污水的總費(fèi)用最低？

設(shè)工廠1和工廠2每天分別處理污水x1和x2萬(wàn)m3，則有：Minz=1000x1+800x2(2-x1)/500≤0.002[0.8(2-x1)+1.4-x2]/700≤0.002x1≤2,x2≤1.4x1,x2≥0線性規(guī)劃20思考：人力資源分配問(wèn)題的建模問(wèn)題：如何建立該問(wèn)題的線性規(guī)劃模型?線性規(guī)劃某旅行社為了迎接旅游黃金周的到來(lái)，對(duì)一日游導(dǎo)游人員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如表所示。為了保證導(dǎo)游充分休息，導(dǎo)游每周工作5天，休息兩天，并要求休息的兩天是連續(xù)的。問(wèn)應(yīng)該如何安排導(dǎo)游人員的作息，既滿足工作需要，又使配備的導(dǎo)游人數(shù)最少？時(shí)間所需導(dǎo)游人數(shù)星期日40星期一34星期二32星期三35星期四28星期五46星期六4221【答案】線性規(guī)劃設(shè)周日、周一、周二、周三、周四、周五、周六開(kāi)始工作的導(dǎo)游人員數(shù)分別x1、x2、x3、x4、x5、x6、x7，所需的導(dǎo)游人員數(shù)為z。則有：時(shí)間所需導(dǎo)游人數(shù)星期日40星期一34星期二32星期三35星期四28星期五46星期六4222思考：生產(chǎn)計(jì)劃問(wèn)題的建模明興公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過(guò)鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如右表。問(wèn)：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？設(shè)：自己鑄造甲、乙、丙為x1、x2、x3；外購(gòu)甲、乙為x4、x5問(wèn)題：如何建立該問(wèn)題的線性規(guī)劃模型線性規(guī)劃23【答案】

解：設(shè)x1,x2,x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5分別為由外協(xié)鑄造再由本公司機(jī)加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤(rùn)：利潤(rùn)=售價(jià)-各成本之和

可得到xi（i=1,2,3,4,5）的利潤(rùn)分別為15、10、7、13、9元。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Max15x1+10x2+7x3+13x4+9x5

約束條件：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0線性規(guī)劃24思考：配料問(wèn)題的建模某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如右表。問(wèn)：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？設(shè)xij表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。問(wèn)題：如何建立該問(wèn)題的線性規(guī)劃模型原料1原料2原料3甲x11x12x13乙x21x22x23丙x31x32x33線性規(guī)劃25【答案】

解：設(shè)xij分別表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮：目標(biāo)函數(shù)：利潤(rùn)最大，利潤(rùn)=收入-原料支出約束條件：規(guī)格要求4個(gè)；供應(yīng)量限制3個(gè)。線性規(guī)劃目標(biāo)函數(shù)：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）-0.25x11+0.75x12-0.25x13≤0（原材料2不超過(guò)25%）0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）-0.5x21+0.5x22-0.5x23≤0（原材料2不超過(guò)50%）

x11+x21+x31≤100(供應(yīng)量限制）

x12+x22+x32≤100(供應(yīng)量限制）

x13+x23+x33≤60(供應(yīng)量限制）xij≥0,i=1,2,3;j=1,2,326思考：投資問(wèn)題的建模某部門現(xiàn)有資金200萬(wàn)元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項(xiàng)目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不超過(guò)30萬(wàn)元；項(xiàng)目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過(guò)80萬(wàn)元；項(xiàng)目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過(guò)100萬(wàn)元；問(wèn)：a.應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b.應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在330萬(wàn)元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最??？設(shè)xij(i=1～5，j=1～4)表示第i年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項(xiàng)目的金額。問(wèn)題：如何建立該問(wèn)題的線性規(guī)劃模型線性規(guī)劃27小結(jié)：線性規(guī)劃模型三大要素決策變量

每個(gè)問(wèn)題都用一組決策變量(x1,x2,···,xn)表示某一方案,這組未知數(shù)的值就代表一個(gè)具體的方案。

約束條件

存在一定的限制條件(稱為約束條件),這些條件都可以用關(guān)于決策變量的一組線性等式或不等式來(lái)表示。

都有一個(gè)目標(biāo)要求,并且這個(gè)目標(biāo)可表示為這組決策變量的線性函數(shù)(稱為目標(biāo)函數(shù)),按研究問(wèn)題的不同,要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。目標(biāo)函數(shù)滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。線性規(guī)劃28三、線性規(guī)劃一般模型的代數(shù)表達(dá)式max(min)Z=c1x1+c2x2+…+cnxn

問(wèn)題：線性規(guī)劃如何求解？a11x1+a12x2+…+a1nxn≤(或＝,≥)b1a21x1+a22x2+…+a2nxn≤(或＝,≥)b2……………am1x1+am2x2+…+amnxn≤(或＝,≥)bmx1,x2,…,xn≥(≤)0線性規(guī)劃線性規(guī)劃的求解方法圖解法單純形法公式法29§1.2線性規(guī)劃問(wèn)題的圖解法

對(duì)于簡(jiǎn)單的線性規(guī)劃問(wèn)題(只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題)，我們通過(guò)圖解法可以對(duì)它進(jìn)行求解。

圖解法即是用圖示的方法來(lái)求解線性規(guī)劃問(wèn)題。圖解法簡(jiǎn)單直觀，有助于了解線性規(guī)劃問(wèn)題求解的基本原理。

一個(gè)二維的線性規(guī)劃問(wèn)題，可以在平面圖上求解，三維的線性規(guī)劃則要在立體圖上求解，這就比較麻煩，而維數(shù)再高以后就不能圖示了。

線性規(guī)劃30線性規(guī)劃圖解法基本步驟：1、建立直角坐標(biāo)系；2、確定可行域；可行域——約束條件所構(gòu)成的區(qū)域3、圖示目標(biāo)函數(shù)；4、最優(yōu)解的確定。最優(yōu)解——可行域中使目標(biāo)函數(shù)值達(dá)到最優(yōu)的點(diǎn)

31一、圖解法的基本步驟

滿足所有約束條件的解叫可行解，解的集合稱之為可行域。即所有約束條件共同圍成的區(qū)域。1、可行域的確定例1的數(shù)學(xué)模型為：x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D

五邊形OABCD內(nèi)(含邊界)的任意一點(diǎn)(x1，x2)都是滿足所有約束條件的一個(gè)解，稱之可行解。maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0線性規(guī)劃322、最優(yōu)解的確定

確定x1、x2希望目標(biāo)函數(shù)

Z=

3x1+5x2達(dá)到最大，圖形中Z=

3x1+5x2代表以Z為參數(shù)的一族平行線，即等值線。

等值線：位于同一直線上的點(diǎn)的目標(biāo)函數(shù)值相同。

Z=3x1+5x2＝0x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)D最優(yōu)解：可行解中使目標(biāo)函數(shù)最優(yōu)(極大或極小)的解

本題中：滿足目標(biāo)函數(shù)最大的極點(diǎn)是離原點(diǎn)距離最遠(yuǎn)的點(diǎn)(4,6)Z=3x1+5x2＝24Z=3x1+5x2＝30Z=39Z=42線性規(guī)劃最優(yōu)解（4，6）maxZ=4233二、解的幾種可能性唯一最優(yōu)解：只有一個(gè)最優(yōu)點(diǎn)。如上題的最優(yōu)解（4,6）

多重最優(yōu)解：無(wú)窮多個(gè)最優(yōu)解。若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則它們連線上的每一點(diǎn)都是最優(yōu)解。x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D如例1的數(shù)學(xué)模型變?yōu)?/p>

maxZ=

3x1+4x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.Z=24Z=36Z=12線性規(guī)劃線段BC上所有的點(diǎn)都是最優(yōu)解34

例如

maxZ=

3x1+2x2-2x1+x2≤2x1-3x2≤3x1≥0,x2≥0-2x1+x2=2x1-3x2=3x2123-1x1123-1Z=6Z=12S.t.無(wú)界解：線性規(guī)劃線性規(guī)劃問(wèn)題的可行域無(wú)界，使目標(biāo)函數(shù)無(wú)限增大而無(wú)界。（缺乏必要的約束條件）可行域無(wú)邊界35

無(wú)解：線性規(guī)劃若約束條件相互矛盾，則可行域?yàn)榭占?。例?/p>

maxZ=

3x1+2x2x1+x2

≤1x1+2x2≥3x1≥0,x2≥0x1+x2=1x1+2x2=3x212-1x1123-1S.t.可行域?yàn)榭占?6【例】求最大值問(wèn)題數(shù)學(xué)模型為：

四邊形OBQC內(nèi)(含邊界)的任意一點(diǎn)(x1，x2)都是滿足所有約束條件的一個(gè)解，稱之可行解。maxZ=

8x1+6x24x1+2x2≤602x1+4x2≤482x1+3x2≤36x1≥0,x2≥02x1+3x2

=36x1x2510510150C(0,12)4x1+2x2

=602x1+4x2

=48B(15,0)Z=126Q(13.5,3)結(jié)論：在Q(13.5,3)處利潤(rùn)最大為126，Q(13.5,3)為最優(yōu)解線性規(guī)劃最優(yōu)解為（13.5,3）maxZ=12637【例】求最小值問(wèn)題設(shè)有某林場(chǎng)需配制某種滅蟲藥水500公斤，該藥水系由甲與乙兩種藥水混合而成。甲種藥水每公斤5元，乙種藥水每公斤8元。按照兩種藥水的化學(xué)性質(zhì)，在混合時(shí)，500公斤混合藥水中含甲種藥水最多不能超過(guò)400公斤，含乙種藥水最少不能少于200公斤。問(wèn)如何配制可使該藥水配制成本最低？.

minZ=

5x1+8x2x1≤400x2≥200x1+x2=500x1≥0,x2≥0則數(shù)學(xué)模型為：設(shè)：500公斤混合藥水中，甲種藥水x1公斤，乙種藥水x2公斤線性規(guī)劃38求解：線性規(guī)劃數(shù)學(xué)模型為：

線段BC上的任意一點(diǎn)(x1，x2)都是滿足所有約束條件的一個(gè)解，稱之可行解。

minZ=

5x1+8x2x1≤400x2≥200x1+x2=500x1≥0,x2≥0結(jié)論：等成本線往右下移，成本越來(lái)越小，A(300,200)成本為最小Z=5x1+8x2

=4000Z=3100x2

=200x1+x2

=500x1x2102004000B(0,500)100300500x1

=400100200300400CA最優(yōu)解為（300,200）minZ=310039練習(xí)題：用圖解法求解下列問(wèn)題－x＋2y≤2x＋2y≤6x－y≤3x＋3y≥3x≥0,y

≥01.約束條件為：（1）maxZ=

4x+y畫出可行域圖形，求下面幾種情況下的最優(yōu)解（2）minZ=

2x-3y（3）maxZ=2x-3y（4）maxZ=x+2y線性規(guī)劃40練習(xí)題：求解－x＋2y≤2x＋2y≤6x－y≤3x＋3y≥3x≥0,y

≥0（1）maxZ=

4x+y求下面幾種情況下的最優(yōu)解（2）minZ=

2x-3y（4）maxZ=

x+2y（3）maxZ=

2x-3yx+3y=3－x+2y=2x－y

=3x1x2161234523x+2y=6(2,2)(4,1)(3,0)(0,1)Z=4x+y=1Z=10Z=12Z=17Z=-3Z=-2Z=5Z=6最優(yōu)解x=4,y=1maxZ=

17最優(yōu)解x=0,y=1minZ=

-3Z=2x+y=1Z=3Z=6有無(wú)窮多最優(yōu)解maxZ=

6最優(yōu)解x=3,y=0maxZ=

6線性規(guī)劃41§1.3線性規(guī)劃解的基本定理線性規(guī)劃

多于兩個(gè)決策變量的線性規(guī)劃問(wèn)題已經(jīng)不能用圖解法求解，因此需要尋求新的求解方法。由于線性規(guī)劃問(wèn)題的數(shù)學(xué)模型有各種不同的形式，比如

目標(biāo)函數(shù)有極大化和極小化；

約束條件有“≤”、“≥”和“＝”三種情況；

決策變量一般有非負(fù)性要求，有的則沒(méi)有。

為了求解方便，特規(guī)定一種線性規(guī)劃的標(biāo)準(zhǔn)形式，非標(biāo)準(zhǔn)型可以轉(zhuǎn)化為標(biāo)準(zhǔn)型計(jì)算。42一、線性規(guī)劃的標(biāo)準(zhǔn)形式的轉(zhuǎn)換方法線性規(guī)劃（一）線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式為：

目標(biāo)函數(shù)最大化

約束條件為等式，

右端常數(shù)項(xiàng)

bi≥0

決策變量非負(fù)

maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥043線性規(guī)劃標(biāo)準(zhǔn)型的表達(dá)方式有代數(shù)式、矩陣式兩種：（二）標(biāo)準(zhǔn)型的表達(dá)方式

1、代數(shù)式maxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0簡(jiǎn)記maxZ=cjxjaijxj＝bi

(i=1,2,…,m)xj≥0(j=1,2,…,n)線性規(guī)劃44

2、矩陣式簡(jiǎn)化為maxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0線性規(guī)劃45（三）非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型轉(zhuǎn)化如目標(biāo)函數(shù)極小化問(wèn)題：通過(guò)變量代換劃為標(biāo)準(zhǔn)型只需將等式兩端乘以-1即變?yōu)闃O大化問(wèn)題。因?yàn)閙inZ=–max(–Z)=CTX，令Z′=-Z，則maxZ′=–CTXminZ=CTX如約束條件中右端常數(shù)項(xiàng)非正：通過(guò)方程兩端同乘“－1”如約束條件為不等式：通過(guò)增加變量來(lái)劃為標(biāo)準(zhǔn)型

當(dāng)約束方程為“≤”時(shí)，左端加入一個(gè)非負(fù)的松弛變量，就把不等式變成了等式；如4X1＋2X2

≤60→4X1＋2X2

＋X3

=60

當(dāng)約束條件為“≥”時(shí)，不等式左端減去一個(gè)非負(fù)的剩余變量(也可稱松弛變量)。如X1＋X2

≥20→X1＋X2

－X3

=20

如決策變量xk沒(méi)有非負(fù)性要求：通過(guò)變量代換實(shí)現(xiàn)

令xk=xk‘－xk〃，其中令xk′，xk〃≥0，用xk′、xk〃取代模型中xk線性規(guī)劃46【例1】試將如下線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型例1的標(biāo)準(zhǔn)型

maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.maxZ=

3x1+5x2+0x3

x1+x3=82x2≤123x1+4x2≤36x1,x2,x3

≥0maxZ=

3x1+5x2+0x3+

0x4

x1+x3=8

2x2+x4=12

3x1+4x2≤36x1,x2,x3,x4≥0maxZ=

3x1+5x2+0x3+

0x4+0x5

x1+x3=8

2x2+x4=12

3x1+4x2+x5=36x1,x2,x3,x4,x5≥0maxZ=

3x1+5x2+0x3+

0x4+0x5

x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0需要化為標(biāo)準(zhǔn)型引進(jìn)一松馳變量x3線性規(guī)劃引進(jìn)一松馳變量x4引進(jìn)一松馳變量x547【例2】試將如下線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型minZ=

x1+2x2-3x3x1+2x2-x3≤52x1+3x2-x3≥6

-x1-x2-x3≥-2x1≥0,x3≤0S.t.例2的標(biāo)準(zhǔn)化minZ=

x1+2x2+3x3′x1+2x2+x3

′≤52x1+3x2+x3

′≥6

-x1-x2+x3

′≥-2x1≥0,x3′≥0

minZ=

x1+2(x2′-x2〃

)

+3x3′x1+2(x2′-x2〃

)

+x3

′≤52x1+3(x2′-x2〃

)+x3

′≥6

-x1-(x2′-x2〃

)

+x3

′≥-2x1,

x2′,x2〃,x3′≥0

minZ=

x1+2(x2′-x2〃

)

+3x3′x1+2(x2′-x2〃

)

+x3

′≤52x1+3(x2′-x2〃

)+x3

′≥6

x1+(x2′-x2〃

)

-x3

′≤2x1,

x2′,x2〃,x3′≥0

maxZ′=-x1-2(x2′-x2〃

)

-3x3′+0x4

x1+2(x2′-x2〃

)

+x3

′+x4=52x1+3(x2′-x2〃

)+x3

′≥6

x1+(x2′-x2〃

)

-x3

′≤2x1,

x2′,x2〃,x3′,x4≥0

maxZ′=-

x1-2(x2′-x2〃

)

-3x3′

+0x4+0x5

x1+2(x2′-x2〃

)

+x3

′+x4=5

2x1+3(x2′-x2〃

)+x3

′-x5=6

x1+(x2′-x2〃

)

-x3

′≤2x1,

x2′,x2〃,x3′,x4,x5≥0

maxZ′=-x1-2(x2′-x2〃

)

-3x3′+0x4+0x5+0x6

x1+2(x2′-x2〃

)

+x3

′+x4=5

2x1+3(x2′-x2〃

)+x3

′-x5=6

x1+(x2′-x2〃

)

-x3

′+x6=2x1,

x2′,x2〃,x3′,x4,x5,x6≥0

maxZ′=-

x1-2(x2′-x2〃

)

-3x3′x1+2(x2′-x2〃

)

+x3

′≤5

2x1+3(x2′-x2〃

)+x3

′≥6

x1+(x2′-x2〃

)

-x3

′≤2x1,

x2′,x2〃,x3′≥0

maxZ′=-x1-2(x2′-x2〃

)

-3x3′+0x4+0x5+0x6

x1+2(x2′-x2〃

)

+x3

′+x4=52x1+3(x2′-x2〃

)+x3

′-x5=6

x1+(x2′-x2〃

)

-x3

′+x6=2x1,

x2′,x2〃,x3′,x4,x5,x6≥0

需要化為標(biāo)準(zhǔn)型令－x3＝x3’令-Z＝Z’線性規(guī)劃無(wú)約束，令引進(jìn)變量x4x5x6兩端同時(shí)乘以-148【例3】試將如下線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型例3的標(biāo)準(zhǔn)型為：

需要化為標(biāo)準(zhǔn)型線性規(guī)劃49練習(xí)：試將如下線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型（1）maxZ=-x1+3

x3+4

x42x1+4

x2+x3-2

x4≤13

6x1+x3+8

x4≥50-x1+4

x2-5

x3-3

x4=-10xi≥0,i=1,2,3,4S.t.（2）minZ=

6

x1+7

x2-

x33x1+2

x2-x3≤10

x2+x3≤15x1≥3x2≥2x1,

x2≥0，x3無(wú)限制S.t.線性規(guī)劃50【答案】（1）maxZ=-x1+3

x3+4

x4+0

x5+0

x62x1+4

x2+x3-2

x4+

x5

=13

6x1+x3+8

x4-x6

=50

x1-4

x2+5

x3+3

x4=10xi≥0,i=1,2,3,4,5,6S.t.（1）maxZ=-x1+3

x3+4

x42x1+4

x2+x3-2

x4≤13

6x1+x3+8

x4≥50-x1+4

x2-5

x3-3

x4=-10xi≥0,i=1,2,3,4S.t.線性規(guī)劃51【答案】（2）maxZ’=

-6

x1-7

x2+

x’3－x’’3

+0x4+0x5+0x6+0x73x1+2

x2-x’3+x’’3

+x4

=10

x2+x’3－x’’3+x5

=15x1-x6

=3x2-

x7=2x1,

x2,

x’3,x’’3,

x4,

x5,

x6,

x7≥0S.t.（2）minZ=

6

x1+7

x2-

x33x1+2

x2-x3≤10

x2+x3≤15x1≥3x2≥2x1,

x2≥0，x3無(wú)限制S.t.線性規(guī)劃52二、線性規(guī)劃解的概念

在討論線性規(guī)劃問(wèn)題的求解之前,先要了解線性規(guī)劃問(wèn)題的解的概念。由前面討論可知線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為：

求解線性規(guī)劃問(wèn)題就是從滿足約束條件(2)、(3)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)（1）達(dá)到最大值。

若設(shè)矩陣A的秩R(A)=m；根據(jù)線性代數(shù)定理可知，當(dāng)R(A)=m＜n，則方程組有無(wú)窮多個(gè)解，這也正是線性規(guī)劃尋求最優(yōu)解的余地所在。線性規(guī)劃53關(guān)于標(biāo)準(zhǔn)型解的若干基本概念可行解與非可行解滿足約束條件（2）和非負(fù)條件（3）的解

X

稱為可行解，約束方程的解空間可行解非可行解最優(yōu)解：使目標(biāo)函數(shù)(1)達(dá)到最大的可行解稱為最優(yōu)解可行解組成的集合叫做可行域問(wèn)題是可行解有無(wú)窮多個(gè)滿足約束條件（2）但不滿足非負(fù)條件（3）的解X稱為非可行解線性規(guī)劃54

線性規(guī)劃對(duì)于標(biāo)準(zhǔn)型設(shè)約束方程組的系數(shù)矩陣為A=(P1,P2,…,Pn)，A的秩為m，則約束方程有無(wú)窮解時(shí)，R(A)=m＜n基：A中任意m個(gè)線性無(wú)關(guān)的列所構(gòu)成的矩陣稱為該標(biāo)準(zhǔn)型的一個(gè)基?；蛄浚築=（P1,P2,…,Pm），|B|0為該標(biāo)準(zhǔn)型的一個(gè)基，則稱P1,P2,…,Pm為基向量。基變量與非基變量

基變量：與基向量對(duì)應(yīng)的變量稱為基變量，記為XB=(x1,x2,…,xm

)T;

非基變量：其余的變量稱為非基變量，記為XN=(xm+1,xm+2,…,xn

)T

。則有X=XB+XN

最多有個(gè)基55

基解令非基變量

XN=0，求得基變量XB的值而得到的解稱為基本解(基解)基可行解基解X

的非零分量都0

時(shí)，稱為基可行解，否則為基非可行解基解基可行解（最多有）最多有種基解基解個(gè)數(shù)：線性規(guī)劃基解是有限的基可行解是有限的56【例】線性規(guī)劃模型的基解演示求解x3=-2x1-x2+10x4=-x1-x2+8x5=-x2+7如果選擇基變量x3,x4,x5，則非基變量是x1,x2令非基變量x1=x2=0，得到x3=10，x4=8，x5=7。則此解為基可行解：X0=(0,0,10,8,7)TR(A)=3例1的標(biāo)準(zhǔn)型為得基解X=(0,0,10,8,7)T

因分量均大于0maxZ=

6x1+4x2+0x3+0x4+0x52x1+x2

+x3=10

x1+x2+x4=8x2+x5=7x1,x2,x3,x4,x5≥0線性規(guī)劃這只為其中一個(gè)基可行解57

全部基解求解舉例maxZ=

6x1+4x2+0x3+0x4+0x52x1+x2

+x3=10

x1+x2+x4=8x2+x5=7x1,x2,x3,x4,x5≥0線性規(guī)劃58

線性規(guī)劃三、線性規(guī)劃解的基本定理1、預(yù)備知識(shí)：凸集和頂點(diǎn)凸集：如果集合C中任意兩個(gè)點(diǎn)X1、X2，其連線上的所有點(diǎn)也都是集合C中的點(diǎn)，稱C為凸集。頂點(diǎn)：假設(shè)K是凸集，XK，若X不能用不同的兩個(gè)點(diǎn)X1、X2的線性組合表示為X3=X1+(1-)X2(0<<1)，則稱K為凸集K的一個(gè)頂點(diǎn)（或極點(diǎn)）。都是頂點(diǎn)59

線性規(guī)劃若線性規(guī)劃問(wèn)題存在可行域，則其可行域一定是凸集。

定理2：

線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)可行域的頂點(diǎn)。

定理3：若可行域有界，線性規(guī)劃的目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)。x1x248123690ABC(4,6)D定理1：2、線性規(guī)劃解的基本定理60四、線性規(guī)劃的解題思路線性規(guī)劃

線性規(guī)劃問(wèn)題可以有無(wú)數(shù)個(gè)可行解，而有限個(gè)頂點(diǎn)對(duì)應(yīng)的解都是基可行解，最優(yōu)解只可能在頂點(diǎn)(基可行解)上達(dá)到，故只要在有限個(gè)基可行解中尋求最優(yōu)解即可。方法是：從一個(gè)頂點(diǎn)出發(fā)找到一個(gè)可行基，得到一組基可行解，拿目標(biāo)函數(shù)做尺度衡量一下看是否最優(yōu)。如若不是，則向鄰近的頂點(diǎn)轉(zhuǎn)移，換一個(gè)基再行求解、檢驗(yàn)，如此迭代循環(huán)目標(biāo)值逐步改善，直至求得最優(yōu)解。61五、線性規(guī)劃單純形法的解題流程線性規(guī)劃確定初試基礎(chǔ)可行解求最優(yōu)解的目標(biāo)函數(shù)值確定改善方向求新的基礎(chǔ)可行解檢查是否為最優(yōu)解？是否62六、線性規(guī)劃解題工具—單純形表格及其格式線性規(guī)劃CjC1…Cn-mCjn-m+1…Cn比值CBXBbx1…Xn-mXn-m+1…xnCn-m+1Xn-m+1b1a11…A1n-m1…01Cn-m+2Xn-m+2b2a21…A2n-m0…02………………………Cnxnbmam1…Amn-m0…1m檢驗(yàn)數(shù)j-Z1…n-mn-m+1…nmaxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bm63§1.4線性規(guī)劃的求解方法——單純形法

單純形法(SimplexMethod)是美國(guó)人丹捷格(G.Dantzig)1947年創(chuàng)建的這種方法簡(jiǎn)捷、規(guī)范，是舉世公認(rèn)的解決線性規(guī)劃問(wèn)題行之有效的方法。單純形法的表現(xiàn)形式：表格法矩陣法－改良的單純形法單純形法的矩陣計(jì)算線性規(guī)劃64初始單純形表的構(gòu)建方法Cj比值CBXBb檢驗(yàn)數(shù)j檢驗(yàn)數(shù)s：初始時(shí)是目標(biāo)函數(shù)的系數(shù)（隨基的調(diào)整變化）變量符號(hào)基變量符號(hào)（隨基的調(diào)整變化）基變量在目標(biāo)函數(shù)中的系數(shù)（變化）約束方程的常數(shù)項(xiàng)約束方程的變量系數(shù)檢驗(yàn)方法：有一個(gè)檢驗(yàn)數(shù)sj>=0，此時(shí)基解不是最優(yōu)；所有檢驗(yàn)數(shù)sj<0，此時(shí)基解為最優(yōu)目標(biāo)函數(shù)的系數(shù)初始值為0線性規(guī)劃65一、表格單純形法的計(jì)算步驟maxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000maxZ=3x1+5x2+0x3+0x4+0x5

x1+x3

=82x2+x4

=123x1+4x2+x5=36

標(biāo)準(zhǔn)型取基變量為x3,x4,x5，1、建立初始單純形表——確定初始基變量則非基變量為x1,x2線性規(guī)劃662、求初始基可行解并進(jìn)行最優(yōu)性檢驗(yàn)Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000

令非基變量x1=0，x2=0，找到一個(gè)初始基可行解：

x1=0，x2=0，x3=8，x4=12，x5=36，

σj＞0，（因?yàn)閦=3x1+5x2+0x3+0x4+0x5)可求基可行解的狀態(tài)即X0=(0,0,8,12,36)T此時(shí)利潤(rùn)Z=0此解不是最優(yōu)線性規(guī)劃67初始基可行解圖示Z=3x1+5x2＝0x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)DX0=(0,0,8,12,36)T說(shuō)明：一個(gè)可行解就是一個(gè)生產(chǎn)方案，上述方案表明兩種產(chǎn)品都不生產(chǎn)x1=0，x2=0，利潤(rùn)Z=0。線性規(guī)劃683、尋找另一基可行解Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9交叉元素稱為主元首先確定進(jìn)基變量再確定出基變量線性規(guī)劃69檢驗(yàn)數(shù)j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9令x1=0，x4=0，σ1=3＞0，此解不是最優(yōu)迭代可求基可行解的狀態(tài)即得基可行解X1=(0,6,8,0,12)T此時(shí)-Z＝-30，