運籌學基礎-線性規(guī)劃(方法)

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

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

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

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

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

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

合理利用線材問題：如何下料使用材最少

配料問題：在原料供應量的限制下如何獲取最大利潤

投資問題：從投資項目中選取方案，使投資回報最大

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

勞動力安排：用最少的勞動力來滿足工作的需要

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

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

則該問題的數(shù)學模型表示為

maxZ=

2x1+3x22x1+2x2≤12

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

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

x1、x2

即為決策變量

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

x1≥0、x2≥

0約束條件

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

是決策者對決策問題目標的數(shù)學描述。如時間最省、利潤最大、成本最低。此題是利潤最大

maxZ=

2x1+3x2

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

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

目標函數(shù)應該是決策變量的線性函數(shù)。

有的目標要實現(xiàn)最大，有的則要求最小。

線性規(guī)劃11二、線性規(guī)劃模型的構建線性規(guī)劃建模步驟：明確問題，確定目標，列出約束條件；

收集資料，確立模型；模型求解與檢驗

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

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

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

(2)約束條件

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

2x1+2x2

≤12

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

x1+2x2

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

(3)目標函數(shù)

目標是利潤最大化，用Z表示利潤，則

(4)非負約束:

產(chǎn)品Ⅰ、Ⅱ的產(chǎn)量不應是負數(shù)，否則沒有實際意義，這個要求表述為

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

x1

≥0，x2

≥0

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

maxZ=

2x1+3x22x1+2x2≤12

x1+2x2≤84x1≤164x2≤12x1≥0,x2≥015【例2】運輸問題

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

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

(2)目標函數(shù):則運費最小的目標函數(shù)為

minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34供應平衡條件(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條件非負性約束xij≥0(i=1,2,3；j=1,2,3,4)632575843297線性規(guī)劃17【例3】營養(yǎng)問題

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

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

…Bn含量A1A2…Ama11a12

…a1na21a22…a2nam1am2…amnb1b2bm單價c1c2…

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

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

…Bn含量A1A2…Ama11a12

…a1na21a22…a2nam1am2…amnb1b2bm價格c1c2…

cna11x1+a12x2+…+a1nxn≥

b1a21x1+a22x2+…+a2nxn≥

b2……am1x1+am2x2+…+amnxn≥

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

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

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

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

可得到xi（i=1,2,3,4,5）的利潤分別為15、10、7、13、9元。這樣我們建立如下的數(shù)學模型。目標函數(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思考：配料問題的建模某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如右表。問：該廠應如何安排生產(chǎn)，使利潤收入為最大？設xij表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。問題：如何建立該問題的線性規(guī)劃模型原料1原料2原料3甲x11x12x13乙x21x22x23丙x31x32x33線性規(guī)劃25【答案】

解：設xij分別表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學模型時，要考慮：目標函數(shù)：利潤最大，利潤=收入-原料支出約束條件：規(guī)格要求4個；供應量限制3個。線性規(guī)劃目標函數(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不超過25%）0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）-0.5x21+0.5x22-0.5x23≤0（原材料2不超過50%）

x11+x21+x31≤100(供應量限制）

x12+x22+x32≤100(供應量限制）

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

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

約束條件

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

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

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

對于簡單的線性規(guī)劃問題(只有兩個決策變量的線性規(guī)劃問題)，我們通過圖解法可以對它進行求解。

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

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

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

31一、圖解法的基本步驟

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

=36x1x248123690ABC(4,6)D

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

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

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

Z=

3x1+5x2達到最大，圖形中Z=

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

等值線：位于同一直線上的點的目標函數(shù)值相同。

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

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

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

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

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

maxZ=

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

例如

maxZ=

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

無解：線性規(guī)劃若約束條件相互矛盾，則可行域為空集。例如

maxZ=

3x1+2x2x1+x2

≤1x1+2x2≥3x1≥0,x2≥0x1+x2=1x1+2x2=3x212-1x1123-1S.t.可行域為空集36【例】求最大值問題數(shù)學模型為：

四邊形OBQC內(nèi)(含邊界)的任意一點(x1，x2)都是滿足所有約束條件的一個解，稱之可行解。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)結論：在Q(13.5,3)處利潤最大為126，Q(13.5,3)為最優(yōu)解線性規(guī)劃最優(yōu)解為（13.5,3）maxZ=12637【例】求最小值問題設有某林場需配制某種滅蟲藥水500公斤，該藥水系由甲與乙兩種藥水混合而成。甲種藥水每公斤5元，乙種藥水每公斤8元。按照兩種藥水的化學性質(zhì)，在混合時，500公斤混合藥水中含甲種藥水最多不能超過400公斤，含乙種藥水最少不能少于200公斤。問如何配制可使該藥水配制成本最低？.

minZ=

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

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

minZ=

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

=4000Z=3100x2

=200x1+x2

=500x1x2102004000B(0,500)100300500x1

=400100200300400CA最優(yōu)解為（300,200）minZ=310039練習題：用圖解法求解下列問題－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＋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有無窮多最優(yōu)解maxZ=

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

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

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

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

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

決策變量一般有非負性要求，有的則沒有。

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

目標函數(shù)最大化

約束條件為等式，

右端常數(shù)項

bi≥0

決策變量非負

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

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

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

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

2、矩陣式簡化為maxZ=c1x1+c2x2+…+cnxn

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

當約束方程為“≤”時，左端加入一個非負的松弛變量，就把不等式變成了等式；如4X1＋2X2

≤60→4X1＋2X2

＋X3

=60

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

≥20→X1＋X2

－X3

=20

如決策變量xk沒有非負性要求：通過變量代換實現(xiàn)

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

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需要化為標準型引進一松馳變量x3線性規(guī)劃引進一松馳變量x4引進一松馳變量x547【例2】試將如下線性規(guī)劃問題化成標準型minZ=

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

-x1-x2-x3≥-2x1≥0,x3≤0S.t.例2的標準化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

需要化為標準型令－x3＝x3’令-Z＝Z’線性規(guī)劃無約束，令引進變量x4x5x6兩端同時乘以-148【例3】試將如下線性規(guī)劃問題化成標準型例3的標準型為：

需要化為標準型線性規(guī)劃49練習：試將如下線性規(guī)劃問題化成標準型（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無限制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無限制S.t.線性規(guī)劃52二、線性規(guī)劃解的概念

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

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

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

X

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

線性規(guī)劃對于標準型設約束方程組的系數(shù)矩陣為A=(P1,P2,…,Pn)，A的秩為m，則約束方程有無窮解時，R(A)=m＜n基：A中任意m個線性無關的列所構成的矩陣稱為該標準型的一個基。基向量：B=（P1,P2,…,Pm），|B|0為該標準型的一個基，則稱P1,P2,…,Pm為基向量?；兞颗c非基變量

基變量：與基向量對應的變量稱為基變量，記為XB=(x1,x2,…,xm

)T;

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

)T

。則有X=XB+XN

最多有個基55

基解令非基變量

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

的非零分量都0

時，稱為基可行解，否則為基非可行解基解基可行解（最多有）最多有種基解基解個數(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的標準型為得基解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ī)劃這只為其中一個基可行解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、預備知識：凸集和頂點凸集：如果集合C中任意兩個點X1、X2，其連線上的所有點也都是集合C中的點，稱C為凸集。頂點：假設K是凸集，XK，若X不能用不同的兩個點X1、X2的線性組合表示為X3=X1+(1-)X2(0<<1)，則稱K為凸集K的一個頂點（或極點）。都是頂點59

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

定理2：

線性規(guī)劃問題的基可行解對應可行域的頂點。

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

線性規(guī)劃問題可以有無數(shù)個可行解，而有限個頂點對應的解都是基可行解，最優(yōu)解只可能在頂點(基可行解)上達到，故只要在有限個基可行解中尋求最優(yōu)解即可。方法是：從一個頂點出發(fā)找到一個可行基，得到一組基可行解，拿目標函數(shù)做尺度衡量一下看是否最優(yōu)。如若不是，則向鄰近的頂點轉(zhuǎn)移，換一個基再行求解、檢驗，如此迭代循環(huán)目標值逐步改善，直至求得最優(yōu)解。61五、線性規(guī)劃單純形法的解題流程線性規(guī)劃確定初試基礎可行解求最優(yōu)解的目標函數(shù)值確定改善方向求新的基礎可行解檢查是否為最優(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檢驗數(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)是美國人丹捷格(G.Dantzig)1947年創(chuàng)建的這種方法簡捷、規(guī)范，是舉世公認的解決線性規(guī)劃問題行之有效的方法。單純形法的表現(xiàn)形式：表格法矩陣法－改良的單純形法單純形法的矩陣計算線性規(guī)劃64初始單純形表的構建方法Cj比值CBXBb檢驗數(shù)j檢驗數(shù)s：初始時是目標函數(shù)的系數(shù)（隨基的調(diào)整變化）變量符號基變量符號（隨基的調(diào)整變化）基變量在目標函數(shù)中的系數(shù)（變化）約束方程的常數(shù)項約束方程的變量系數(shù)檢驗方法：有一個檢驗數(shù)sj>=0，此時基解不是最優(yōu)；所有檢驗數(shù)sj<0，此時基解為最優(yōu)目標函數(shù)的系數(shù)初始值為0線性規(guī)劃65一、表格單純形法的計算步驟maxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000maxZ=3x1+5x2+0x3+0x4+0x5

x1+x3

=82x2+x4

=123x1+4x2+x5=36

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

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

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

σj＞0，（因為z=3x1+5x2+0x3+0x4+0x5)可求基可行解的狀態(tài)即X0=(0,0,8,12,36)T此時利潤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說明：一個可行解就是一個生產(chǎn)方案，上述方案表明兩種產(chǎn)品都不生產(chǎn)x1=0，x2=0，利潤Z=0。線性規(guī)劃683、尋找另一基可行解Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9交叉元素稱為主元首先確定進基變量再確定出基變量線性規(guī)劃69檢驗數(shù)j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb檢驗數(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此時-Z＝-30，