第1章 線性規(guī)劃基本模型

趙明霞山西大學(xué)經(jīng)濟與管理學(xué)院管理運籌學(xué)

——模型與方法第1章線性規(guī)劃基本模型1.1線性規(guī)劃的實用模型1.2線性規(guī)劃的一般模型1.3線性規(guī)劃的圖解法1.4標準形線性規(guī)劃的解2023/2/321.1線性規(guī)劃的實用模型2023/2/33線性規(guī)劃(LP,LinearProgramming)的組成：目標函數(shù)opt（optimize）maxz(f)或minz(f)約束條件s.t.(subjectto)滿足于決策變量用符號來表示可控制的因素資源分配模型產(chǎn)品配套模型下料模型配料模型2023/2/34例1.0某工廠在計劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表：問題：工廠應(yīng)分別生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠獲利最多？線性規(guī)劃模型：maxf=50x1+100x2

s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥02023/2/35線性規(guī)劃建模過程1.理解要解決的問題，明確目標和條件；2.定義決策變量（x1，x2，…

，xn

），每一組值表示一個方案；3.用決策變量的線性函數(shù)形式寫出目標函數(shù)，確定最大化或最小化目標；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件2023/2/36資源分配模型2023/2/37例1-1.某工廠要安排甲、乙兩種產(chǎn)品分別在車間A、B生產(chǎn)，然后都在C車間裝配。生產(chǎn)數(shù)據(jù)如下表：問題：工廠應(yīng)分別生產(chǎn)多少單位甲、乙產(chǎn)品？解：設(shè)變量（單位）2023/2/382023/2/39

例1.1某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下：

設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員?2023/2/310

解：設(shè)xi

表示第i班次時開始上班的司機和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。minx1+x2+x3+x4+x5+x6

s.t.x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥02023/2/311另解：設(shè)xi

(i=1,2,…,6)表示第1班次至第6班次開始休息的人數(shù),這樣我們建立如下的數(shù)學(xué)模型。minx1+x2+x3+x4+x5+x6s.t.x2+x3≥60x3+x4≥70

x4+x5≥60

x5+x6≥50

x6+x1≥20x1+x2≥30x1,x2,x3,x4,x5,x6≥02023/2/312

例1.2某公司面臨一個是外包協(xié)作還是自行生產(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é)作各應(yīng)多少件？2023/2/3132023/2/314解：設(shè)x1,x2,x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5

分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(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≥02023/2/315例1.3永久機械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過A、B兩道工序加工。假設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成A工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成B工序。Ⅰ可在A、B的任何規(guī)格的設(shè)備上加工；Ⅱ可在任意規(guī)格的A設(shè)備上加工，但對B工序，只能在B1設(shè)備上加工；Ⅲ只能在A2與B2設(shè)備上加工；數(shù)據(jù)如下表。問：為使該廠獲得最大利潤，應(yīng)如何制定產(chǎn)品加工方案？2023/2/3162023/2/317解：設(shè)xijk

表示第i種產(chǎn)品，在第j種工序上的第k種設(shè)備上加工的數(shù)量。maxf=0.75x111+0.79x112-0.36x121-0.44x122-0.35x123

+1.15x211+1.38x212-0.48x221+1.94x312-1.21x322s.t.5x111+10x211≤6000（設(shè)備A1

）

7x112+9x212+12x312≤10000（設(shè)備A2

）

6x121+8x221≤4000（設(shè)備B1

）

4x122+11x322≤7000（設(shè)備B2

）

7x123≤4000（設(shè)備B3

）

x111+x112=x121+x122+x123（Ⅰ產(chǎn)品在A、B工序加工的數(shù)量相等）

x211+x212=x221

（Ⅱ產(chǎn)品在A、B工序加工的數(shù)量相等）

x312=x322

（Ⅲ產(chǎn)品在A、B工序加工的數(shù)量相等）

xijk≥0,i=1,2,3;j=1,2;k=1,2,3產(chǎn)品配套模型例1-2.某廠生產(chǎn)一種部件，由3個A零件和5個B零件配套組裝成品。該廠有甲、乙、丙三種機床可加工A、B兩種零件，數(shù)據(jù)見下表。則應(yīng)如何安排生產(chǎn)？2023/2/3182023/2/319解：設(shè)xij為i機床生產(chǎn)j零件的件數(shù)下料模型例1-3.某項管網(wǎng)工程，要用某一口徑的管材，其原材長5m，但用材的長度、數(shù)量不盡相同，見下表。應(yīng)如何下料才能耗材最??？2023/2/3202023/2/32112345A(2.6)10100B(1.8)02101C(1.1)21042余0.20.30.60.61.02023/2/322解：設(shè)xi為按方案i下料的根數(shù)2023/2/323注意：在建立此類型數(shù)學(xué)模型時，約束條件用大于等于號比用等于號要好。因為有時在套用一些下料方案時可能會多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號，這一方案就不是可行解了。配料模型例1-4.某食品廠擬用A，B兩種緊俏原料和一種普通原料C，加工制作甲、乙、丙三種食品。如表所示。應(yīng)如何為三種食品配料？2023/2/3242023/2/325解：設(shè)xij為i食品含原料j的量(kg)2023/2/3261.2線性規(guī)劃的一般模型通式2023/2/3272023/2/328解的概念可行解滿足約束條件的解2023/2/329

最優(yōu)解是目標值最優(yōu)的可行解2023/2/330標準形M12023/2/331M22023/2/332M3

可以看出，線性規(guī)劃的標準形式有如下特點：目標最大化；（注：無要求，但為了單純形表的統(tǒng)一解法，作最大化統(tǒng)一；亦可統(tǒng)一為最小化）約束為等式；決策變量均非負；右端項（常數(shù)項）非負。對于各種非標準形式的線性規(guī)劃問題，我們總可以通過變換將其轉(zhuǎn)化為標準形式。2023/2/333線性規(guī)劃的標準化1.極小化目標函數(shù)的問題：設(shè)目標函數(shù)為

minf=c1x1+c2x2+…+cnxn

(可以)令z

＝-f

，則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即

maxz=-c1x1-c2x2-…-cnxn

但必須注意，盡管以上兩個問題的最優(yōu)解相同，但它們最優(yōu)解的目標函數(shù)值卻相差一個符號，即

minf＝-maxz2023/2/3342、約束條件不是等式的問題：約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

可以引進一個新的松弛變量xn+1

，使它等于約束右邊與左邊之差xn+1=bi–(ai1x1+ai2x2+…+ainxn)顯然，

xn+1也具有非負約束，即xn+1

≥0，這時新的約束條件成為ai1x1+ai2x2+…+ainxn+

xn+1

=bi2023/2/335約束條件為

ai1x1+ai2x2+…+ainxn≥bi

時，類似地令剩余變量

xn+1

=(ai1x1+ai2x2+…+ainxn)-bi

顯然，

xn+1也具有非負約束，即xn+1≥0，這時新的約束條件成為ai1x1+ai2x2+…+ainxn-

xn+1

=bi2023/2/3362023/2/337

為了使約束由不等式成為等式而引進的變量xn+1,當不等式為“小于等于≤”稱為“松弛變量”；當不等式為“大于等于≥”時稱為時“剩余變量”。

如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標準形式時，必須對各個約束引進不同的變量。2023/2/3383.右端項有負值的問題：在標準形式中，要求右端項必須每一個分量非負。當某一個右端項系數(shù)為負時，如bi<0，則把該等式約束兩端同時乘以-1，得到：-ai1x1-ai2x2-…-ainxn=-bi4、變量無符號限制的問題：在標準形式中，必須每一個變量均有非負約束。當某一個變量xj沒有非負約束時，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用兩個非負變量之差來表示一個無符號限制的變量，當然xj的符號取決于xj’和xj”的大小。例1-6將以下線性規(guī)劃問題轉(zhuǎn)化為標準形式

minz=2x1-x2+3x3-x4s.t.2x1+x2-3x3+x4≤33x1-2x2+x3-x4≥2-x1-3x2+2x3-x4≥-1x2≤0,x3≥0

2023/2/3392023/2/340線性規(guī)劃的典式標準形為典式的充要條件：系數(shù)矩陣中存在一個滿秩單位陣。典式標準形是單純形法的唯一必要前提。2023/2/341線性規(guī)劃問題的求解方法一般有兩種方法圖解法單純形法兩個變量、直角坐標三個變量、立體坐標適用于任意變量、但需將一般形式變成典式1.3線性規(guī)劃的圖解法2023/2/342例1-7唯一解2023/2/343無界解無可行解無窮多解重要結(jié)論：如果線性規(guī)劃有最優(yōu)解，則一定有一個可行域的頂點對應(yīng)一個最優(yōu)解；無窮多個最優(yōu)解。若將例1-7中的目標函數(shù)變?yōu)閙axz=2x1+3x2，則線段BC上的所有點都代表了最優(yōu)解；無界解。即可行域的范圍延伸到無窮遠，目標函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯，忽略了一些必要的約束條件；無可行解。若在例1-7的數(shù)學(xué)模型中再增加一個約束條件x1+x2≥10，則可行域為空域，不存在滿足約束條件的解，當然也就不存在最優(yōu)解了。2023/2/3442023/2/345可行解：滿足約束條件和非負條件的決策變量的一組取值?？尚薪饧核锌尚薪獾募??？尚杏颍篖P問題可行解集構(gòu)成n維空間的區(qū)域，可以表示為：最優(yōu)解:使目標函數(shù)達到最優(yōu)值的可行解。最優(yōu)值：最優(yōu)解對應(yīng)目標函數(shù)的取值。求解LP問題:求出問題的最優(yōu)解和最優(yōu)值。1.4

標準形線性規(guī)劃的解基本概念基本性質(zhì)2023/2/346基本概念

基本解基（矩陣）基變量最優(yōu)基本解基本可行解最優(yōu)基本解可行基、最優(yōu)基退化基本（可行）解凸性凸組合凸集極點2023/2/3472023/2/348基本解的概念只適用于標準形線性規(guī)劃例1-1在加上松弛變量之后我們可得到標準形如下：max3x1+2x2(1-4a)s.t.x1+x3=6

2x2+x4=8

(1-4b)

2x1+3x2+x5=18xj≥0（j=1,2,3,4,5）(1-4c)基本解2023/2/349它的系數(shù)矩陣aj為系數(shù)矩陣A第j列的向量。A的秩R(A)=3<5,A的秩小于此方程組(1-4b)的變量的個數(shù)，方程組(1-4b)有無窮多解。其中，單位陣為該線性規(guī)劃問題中的一個基。a3,a4,a5為基向量，a1,a2為非基向量；x3,x4,x5為基變量，x1,x2為非基變量。令x1=x2=0,可得x3=6,x4=8,x5=18,得方程組(1-4b)的一個特解

為該線性規(guī)劃的一個基本解。設(shè)是滿秩陣，且R(A)=m<n，系數(shù)陣則有：設(shè)B為A的一個m階子矩陣，若,則B為方程組(1-5b)或線性規(guī)劃（1-5）的一個基矩陣，簡稱一個基。設(shè)基矩陣則B中m個向量a1,a2,…,am為基向量，其余n-m個向量為非基向量。x1,x2,…,xm為（以B為基的）基變量，其余為（以B為基的）非基變量。所有基變量構(gòu)成的向量XB為基變矢，所有非基變量構(gòu)成的向量XN為非基變矢。2023/2/350(1-5c)(1-5a)(1-5b)令XN=0，則BXB=b，得特解為一個以B為基的基本解，簡稱基本解?；究尚薪猓杭仁腔窘?，又是可行解。滿足非負性約束的基本解。例1-1中，以為基的基本解為基本可行解。另有為基本解，但不是基本可行解。為基本可行解。最優(yōu)基本解：使目標值最優(yōu)的基本可行解?？尚谢夯究尚薪鈱?yīng)的基。最優(yōu)基：最優(yōu)基本解對應(yīng)的基。退化基本（可行）解：基本（可行）解中，有一個或多個基變量取值為0。2023/2/351凸組合：