衛(wèi)生管理運(yùn)籌學(xué)

OperationalResearchonHealthManagement第二章

線性規(guī)劃Chapter2：LinearProgramming醫(yī)院管理教研室薛迪第二章

線性規(guī)劃

Chapter2：LinearProgramming第一節(jié)

線性規(guī)劃問題及其數(shù)學(xué)模型

ProblemandModelofLP

第二節(jié)

線性規(guī)劃問題的圖解法

GraphicalSolutionofLPProblems第三節(jié)單純形法SimplexMethod

第四節(jié)應(yīng)用實(shí)例Applications第一節(jié)

線性規(guī)劃問題及其數(shù)學(xué)模型

ProblemandModelofLP一、

線性規(guī)劃問題的數(shù)學(xué)模型

ModelofLP

二、

線性規(guī)劃問題的結(jié)構(gòu)特征

CharacteristicsofLP三、線性規(guī)劃問題的標(biāo)準(zhǔn)形式

StandardFormofLP第二節(jié)

線性規(guī)劃問題的圖解法

GraphicalSolutionofLPProblems一、

線性規(guī)劃問題解的基本概念

BasicConceptsoftheSolutionsofLP二、兩個變量的線性規(guī)劃問題的圖解法

GraphicalSolutionofTwo-VariableLP三、線性規(guī)劃問題解的特點(diǎn)

CharacteristicsofthesolutionsofLP第三節(jié)

單純形法

SimplexMethod

一、

單純形法的基本原理

BasicPrinciples二、

單純形法解

SimplexMethod三、

大M法

BigMMethod第四節(jié)

應(yīng)用實(shí)例

Applications一、

護(hù)士配備問題

NurseArrangement二、診療問題

ClinicalTreatment三、合理用料問題

RationalUseofMaterials第一節(jié)

線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃研究的對象大體可分為兩大類：一類是在現(xiàn)有的人、財(cái)、物等資源的條件下，研究如何合理地計(jì)劃、安排，可使得某一目標(biāo)達(dá)到最大，如產(chǎn)量、利潤目標(biāo)等。另一類是在任務(wù)確定后，如何計(jì)劃、安排，使用最低限度的人、財(cái)?shù)荣Y源，去實(shí)現(xiàn)該任務(wù)，如使生產(chǎn)成本、費(fèi)用最小等。一、線性規(guī)劃問題的數(shù)學(xué)模型

[例1]

某制藥廠用甲、乙兩臺機(jī)器生產(chǎn)A、B兩種藥物。每種藥物要經(jīng)過兩道工序，在甲機(jī)器上攪拌，在乙機(jī)器上包裝。已知在未來兩周內(nèi)，甲、乙兩臺機(jī)器的使用時間分別不得超過40小時和30小時，生產(chǎn)每公斤藥物所需的加工時間如下表2-1所示。如果生產(chǎn)每公斤藥物A的利潤是30元，B是25元，試問，如何安排這兩周的生產(chǎn)，能使工廠利潤最大？藥物甲機(jī)器加工時間（小時）乙機(jī)器加工時間（小時）A23B42表2-1[例2]

用三種原料B1、B2、B3配制某種食品，要求該食品中蛋白質(zhì)、脂肪、糖、維生素的含量不低于15、20、25、30單位。以上三種原料的單價及每單位原料所含各種成份的數(shù)量，如下表2-2所示。問應(yīng)如何配制該食品，使所需成本最低？

營養(yǎng)成份原料

食品中營養(yǎng)成份的最低需要量（單位）B1B2B3蛋白質(zhì)（單位/斤）56815脂肪（單位/斤）34620糖（單位/斤）85425維生素（單位/斤）1012830原料單價（元/斤）202530

表2-2[例3]某藥品公司要求銷售部經(jīng)理制定一個廣告計(jì)劃。該經(jīng)理選擇了三種廣告方法：電視、廣播電臺和報(bào)紙。據(jù)調(diào)查各種廣告的費(fèi)用如下：在地方電視臺下午播放1.5分鐘要1000元，晚上要2000元。該經(jīng)理決定在電視上作廣告至少兩次，但不多于四次。在地方報(bào)紙上作半頁廣告費(fèi)用是300元，一頁要1000元。在廣播電臺上作廣告的價格是，白天每半分鐘600元，晚上每半分鐘400元。公司限制用電臺作廣告的次數(shù)，白天最多不超過5次，晚上不超過3次。根據(jù)該經(jīng)理所獲得的資料估計(jì)，在下午觀看電視廣告節(jié)目的大約有40000人，晚上有90000人?？慈請?bào)的人大約有60000人，并估計(jì)其中1/2的人看整頁的廣告，1/3的人看半頁的廣告。廣播電臺的聽眾白天有40000人，晚上有30000人。問在計(jì)劃用經(jīng)費(fèi)10000元的情況下，該經(jīng)理應(yīng)如何安排才能使盡量多的人能看到廣告？二、線性規(guī)劃問題的結(jié)構(gòu)特征1．都有一組未知變量（x1，x2，…，xn）代表某一方案，它們?nèi)〔煌姆秦?fù)值，代表不同的具體方案。2．都有一個目標(biāo)要求，實(shí)現(xiàn)極大或極小。目標(biāo)函數(shù)要用未知變量的線性函數(shù)表示。3．未知變量受到一組約束條件的限制，這些約束條件用一組線性等式或不等式表示。正是由于目標(biāo)函數(shù)和約束條件都是未知變量的線性函數(shù)，所以我們把這類問題稱為線性規(guī)劃問題。線性規(guī)劃問題的一般形式：目標(biāo)函數(shù)Max（Min）Z=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤（=，≥）b1

a21x1+a22x2+…+a2nxn≤（=，≥）b2

…………am1x1+am2x2+…+amnxn≤（=，≥）bm

x1，x2，…，xn≥0c1x1+c2x2+…+cnxn稱為目標(biāo)函數(shù)，cj稱為成本或利潤系數(shù)；aij稱為約束條件中未知變量的系數(shù)；bi稱為限定系數(shù)。

三、線性規(guī)劃問題的標(biāo)準(zhǔn)形式（一）線性規(guī)劃問題的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)MaxZ=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

…………am1x1+am2x2+…+amnxn=bm

x1，x2，…，xn≥0bi≥0（i=1，2，…，m）式中，cj稱為成本或利潤系數(shù)；aij稱為未知變量的系數(shù)；bi稱為限定系數(shù)。標(biāo)準(zhǔn)形式的主要特點(diǎn)是：①目標(biāo)函數(shù)最大化；②所有的約束條件由等式表示；③所有的變量和每一約束條件右端的常數(shù)項(xiàng)均為非負(fù)值。（二）書寫形式1.簡縮形式目標(biāo)函數(shù)

s.t.i=1，2，…，mj=1，2，…，ni=1，2，…，m2.矩陣形式

MaxZ=CXs.t.AX=bX≥0b≥0其中，C=（c1，c2，…,cn）

a11a12

…a1na21a22

…a2nA=………………am1am2

…amnx1b10x2b20X=…b=…0=…xnbm0這里C為成本或利潤向量，X為決策向量，A為系數(shù)矩陣（或稱約束矩陣），b為限定向量（或稱右端向量），條件X≥0稱為非負(fù)約束。（三）標(biāo)準(zhǔn)形式的轉(zhuǎn)化1．目標(biāo)函數(shù)的轉(zhuǎn)換若MinZ=，只須令-Z=Z′，即有

MaxZ′=Max(-Z)=Max2．約束條件的轉(zhuǎn)換

“≤”形式的不等式，則可在“≤”的左端加入非負(fù)的松弛變量(SlackVariable)，把原“≤”形式的不等式變?yōu)榈仁?/p>

“≥”形式的不等式，則可在“≥”號的左端減去一個非負(fù)的剩余變量(ExcessVariable)（也可稱松弛變量），把不等式改為等式。例如前面例1中線性規(guī)劃問題為：MaxZ=30x1+25x2s.t.2x1+4x2≤403x1+2x2≤30x1,x2≥0標(biāo)準(zhǔn)形式可寫為：MaxZ=30x1+25x2s.t.2x1+4x2＋x3=403x1+2x2+x4=30x1,x2,x3,x4≥0式中x3，x4為松弛變量。例2中線性規(guī)劃MinZ=20x1+25x2+30x3

s.t.5x1+6x2+8x3≥153x1+4x2+6x3≥208x1+5x2+4x3≥2510x1+12x2+8x3≥30x1，x2，x3≥0標(biāo)準(zhǔn)形式可寫成：MaxZˊ=-20x1-25x2-30x3s.t.5x1+6x2+8x3-x4=153x1+4x2+6x3-x5=208x1+5x2+4x3-x6=2510x1+12x2+8x3-x7=30x1，x2，…,x7≥0式中Z＝-Zˊ，x4～x7為剩余變量（也可稱松弛變量）。3．變量的非負(fù)轉(zhuǎn)換若變量Xk取正值或負(fù)值都可以，這時為了滿足標(biāo)準(zhǔn)形式對變量的非負(fù)要求，可令xk＝xk′－xk″，其中，xk′≥0，xk″≥0。第二節(jié)線性規(guī)劃問題的圖解法一、線性規(guī)劃問題解的基本概念設(shè)線性規(guī)劃問題的標(biāo)準(zhǔn)形式為：

s.t.i=1,2,…,mj=1,2,…,ni=1,2,…,m1．可行解(FeasibleSolutions)

滿足約束條件的解X＝（x1,x2,…，xn）T,稱為線性規(guī)劃問題的可行解。所有可行解的集合稱為可行域(FeasibleRegion)。2．最優(yōu)解(OptimalSolutions)

滿足目標(biāo)函數(shù)式的可行解，稱為線性規(guī)劃問題的最優(yōu)解。3．最優(yōu)值(OptimalZ-Value)

對應(yīng)于最優(yōu)解的目標(biāo)函數(shù)之值，稱為最優(yōu)值。二、兩個變量的線性規(guī)劃問題的圖解法[例4]以上一節(jié)例1為例，

MaxZ=30x1+25x2s.t.2x1+4x2≤403x1+2x2≤30x1，x2≥0解：第一步建立平面直角坐標(biāo)系第二步求滿足約束條件的可行解區(qū)域第三步作目標(biāo)函數(shù)的等值線簇，確定目標(biāo)函數(shù)值增加方向。第四步從可行解區(qū)內(nèi)找滿足目標(biāo)函數(shù)的最優(yōu)解。

X*＝(57.5)T，Z*=337.5。[例5]用圖解法解線性規(guī)劃：MaxZ=x1+2x2

s.t.x1+2x2≤10x1+x2≥1x1≥0x2≥0x2≤4[例6]解下列線性規(guī)劃：

MaxZ＝3x1+12x2s.t.10x1-8x2≤80x1，x2≥0三、線性規(guī)劃問題解的特點(diǎn)1.可行域總是凸多邊形；2．如果一個線性規(guī)劃問題確實(shí)存在唯一的最優(yōu)解，那么它必定可在其可行域的一個頂點(diǎn)上達(dá)到；3．如果一個線性規(guī)劃問題存在多重最優(yōu)解，那么至少在其可行域有兩個相鄰的頂點(diǎn)所對應(yīng)的目標(biāo)函數(shù)值相等，且達(dá)到最大值（或最小值）。4．如果可行域中一個頂點(diǎn)的目標(biāo)函數(shù)值比其相鄰頂點(diǎn)的目標(biāo)函數(shù)值要好的話，那么它就比其他所有頂點(diǎn)的目標(biāo)函數(shù)值都要好，或者說它就是一個最優(yōu)解。第三節(jié)單純形法

一、單純形法的基本原理（一）典型方程組

i＝1，2，…，m2-1++2-2

……………+1

如果在一個線性方程組中的每一個方程中都有系數(shù)為1，并且不再出現(xiàn)在其它方程的一個未知量，則此方程組稱為典型方程組。初等行運(yùn)算，可以用來求取同解方程組：

——用一個正數(shù)或負(fù)數(shù)乘組中的任一方程

——將方程組中的任一方程兩邊同乘一個常數(shù)（正、負(fù)或零），分別加到另一方程的兩邊（二）基本變量如果變量xj在某一方程中系數(shù)為1，而在其它一切方程中的系數(shù)為零，則稱xj為該方程中的基本變量(BasicVariable)。否則為非基本變量(NonbasicVarible)?；咀兞康膫€數(shù)為線性無關(guān)的方程的個數(shù)。事實(shí)上，n個變量中任意的m個都可能作為基本變量，因此由排列組合知識可知，基本變量的組數(shù)為個，n為未知變量的個數(shù)，m為線性無關(guān)的方程的個數(shù)。（三）基本解在典型方程中，設(shè)非基本變量為零，求解基本變量得到的解，稱為基本解?；窘獾膫€數(shù)為個。（四）基本可行解基本變量為非負(fù)的一組基本解稱為基本可行解，基本可行解的個數(shù)最多不超過個。例如，x1+x2-x3+2x4＝3①2x1+x2-3x4＝1②

施行初等變換，可以得到：

x1+x3-5x4＝-2⑤x2-2x3+7x4＝5④若令x2和x4為基本變量，通過初等變換，方程組①和②可變換為：

1.4x1+x2-0.6x3

＝2.2⑤-0.2x1-0.2x3+x4＝0.4④（五）單純形法的原理理論上已經(jīng)證明，線性規(guī)劃的基本可行解與可行域的頂點(diǎn)是一對一的。這就決定了線性規(guī)劃可行域的頂點(diǎn)個數(shù)最多也不超過個。如果線性規(guī)劃有最優(yōu)解，一定可以在可行域的某個頂點(diǎn)處達(dá)到因此，單純形法的基本思路是：根據(jù)問題的標(biāo)準(zhǔn)形式，從可行域中的一個基本可行解（一個頂點(diǎn)）開始，轉(zhuǎn)換到另一個基本可行解（頂點(diǎn)），并且使目標(biāo)函數(shù)的值逐步增大；當(dāng)目標(biāo)函數(shù)達(dá)到最大值時，問題就得到了最優(yōu)解。在用單純形法求解線性規(guī)劃問題時，應(yīng)考慮的問題：1．建立初始基本可行解在用單純形法求解時，首先應(yīng)將線性規(guī)劃問題以標(biāo)準(zhǔn)形式表達(dá)、約束條件以典型方程組表示，確定初始基本可行解：

X（0）＝2．最優(yōu)性檢驗(yàn)

j=1，2，…，n

為變量xj的檢驗(yàn)數(shù)。（1）最優(yōu)解判別若X（0）＝為基本可行解，且對一切j=1,2,…,n有≤0，則X（0）為最優(yōu)解。（2）無有限最優(yōu)解判別若X（0）＝為一基本可行解，有一個>0，且對一切i=1,2,…,m有βik≤0（βik為約束條件方程中的系數(shù)，k＝1，2，…，n），那么該線性規(guī)劃問題無有限最優(yōu)解（或稱無最優(yōu)解）。Zj=CB·Pj

事實(shí)上，應(yīng)用向量的乘法，可以將檢驗(yàn)數(shù)的求法表示得簡明一些。令cj表示目標(biāo)函數(shù)中變量的系數(shù)，CB表示基本變量在目標(biāo)函數(shù)中的系數(shù)行向量，Pj表示變量在典型方程中的系數(shù)列向量，則

j=1,2,…,n2-8基本變量的檢驗(yàn)數(shù)總等于0。目標(biāo)函數(shù)值Z＝CB·b

3．基本可行解的改進(jìn)若初始基本可行解X（0）不是最優(yōu)解及不能判別無最優(yōu)解時，需找一個新的基本可行解。具體方法是：首先確定進(jìn)基變量，再確定出基變量。

進(jìn)基變量的確定：檢驗(yàn)數(shù)表示當(dāng)變量增加1個單位時，目標(biāo)函數(shù)的增加量；其經(jīng)濟(jì)意義表示相對利潤。當(dāng)

>0時，說明非基本變量增加1個單位，目標(biāo)函數(shù)可以增加，即現(xiàn)在的函數(shù)值不是最優(yōu)，還能增加。這時要將某個非基本變量換到基本變量中去（稱為進(jìn)基變量）。為了使目標(biāo)函數(shù)值增長最快，所以應(yīng)選擇值最大的一項(xiàng)所對應(yīng)的非基本變量進(jìn)基。

Max（||>0）＝則對應(yīng)的為進(jìn)基變量。進(jìn)基變量所在的列（k）稱為樞列。

出基變量的確定：當(dāng)進(jìn)基變量確定后（假設(shè)是進(jìn)基變量），出基變量的選定是應(yīng)用“最小比值規(guī)則”。即用此時的各約束方程右端的常數(shù)項(xiàng)（非負(fù)數(shù)）與相應(yīng)方程中的正系數(shù)βik相比，并選取最小商值的基本變量為出基變量（將由基本變量變?yōu)榉腔咀兞浚?。出基變量所在的行（l）稱為樞行。樞行與樞列交點(diǎn)處的元素（βlk）稱為樞元。然后通過初等變換，將約束條件轉(zhuǎn)為關(guān)于新的基本變量的典型方程組，并求得新的基本可行解。對于新的基本可行解可再進(jìn)行上述的最優(yōu)性檢驗(yàn)。二、單純形法解第一步：找出初始基本可行解，建立初始單純形表第二步：檢驗(yàn)對應(yīng)于非基本變量的檢驗(yàn)數(shù)，若對所有的≤0（j＝1，2，…，n），則已得到最優(yōu)解，計(jì)算最優(yōu)值，即可結(jié)束。否則，轉(zhuǎn)入下一步。第三步：在所有>0中，若有一個對應(yīng)的系數(shù)列向量，即對i＝1，2，…，m均有βik≤0，則此問題無解，停止計(jì)算。否則轉(zhuǎn)入下一步。第四步：根據(jù)Max（||>0）＝，確定為進(jìn)基變量，再依據(jù)“最小比值規(guī)則”（）確定為出基變量。第五步：實(shí)施以樞元素為中心的初等變換，得到新的單純形表，重復(fù)第二步…，一直到?jīng)]有新的非基本變量可以改善目標(biāo)函數(shù)為止。[例7]現(xiàn)以本章第一節(jié)的例1來說明單純形法的表上作業(yè)方法。MaxZ=30x1+25x2s.t.2x1+4x2≤403x1+2x2≤30x1≥0x2≥0

表2-3xj為規(guī)劃中出現(xiàn)的變量；cj

為變量xj在目標(biāo)函數(shù)中的系數(shù)；XB為基本變量；CB為基本變量在目標(biāo)函數(shù)中的系數(shù)；

2410為典型方程組中變量的系數(shù)；

3201b為典型方程組右端常數(shù)項(xiàng)（非負(fù)值）；θ為確定出基變量的商值，（>0）；為變量的檢驗(yàn)數(shù)，；Z為此時目標(biāo)函數(shù)值Z＝CB·b。[例8]用單純形法求解下列規(guī)劃問題MinZ＝3x1+x2+x3+x4s.t.-2x1+2x2+x3=43x1+x2+x4=6x1，x2，x3，x4≥0

實(shí)際上，也可直接用單純形表求解極小化問題。若對所有的≥0（j＝1，2，…，n），則已得到最優(yōu)解；所有<0中，若有一個對應(yīng)xk的系數(shù)列向量，即對i＝1，2，…，m均有βik≤0，則此問題無解；在選擇進(jìn)基變量時，應(yīng)當(dāng)選擇檢驗(yàn)數(shù)為負(fù)值且絕對值最大的變量進(jìn)基。

線性規(guī)劃問題的單純形法求解中，還會遇到如下問題：1．最終產(chǎn)生最優(yōu)值的單純形表中，某一非基本變量xk的檢驗(yàn)數(shù)＝0，意味著有多重最優(yōu)解。2．當(dāng)樞列（進(jìn)基變量所在列）中的每一項(xiàng)系數(shù)不是0就是負(fù)值時，說明有無界解。3．在選取進(jìn)基變量時，有二個及二個以上變量的檢驗(yàn)數(shù)具有相同的最大正值（極小化問題為相同的最小負(fù)值），這時可任選其中一個變量進(jìn)基。4．計(jì)算θ值時，出現(xiàn)相同的最小比值，此時有可能出現(xiàn)退化的基本可行解，即至少有一個基本變量為零。三、大M法（一）人工變量法人工變量沒有實(shí)際意義，只是一種形式的存在，本質(zhì)上應(yīng)當(dāng)?shù)扔诹?。（二）大M法求解[例9]用大M法求解下列問題。MaxZ=3x1+5x2s.t.x1≤42x2≤123x1+2x2=18x1，x2≥0

值得注意的是：在用大M法求解時，如果得到人工變量不為零的最優(yōu)解，則說明原問題不可行，即原問題無解。另外，若極小比值相等，則人工變量先出基。

解的情況有：有最優(yōu)解唯一最優(yōu)解多重最優(yōu)解無最優(yōu)解（無解）無有限最優(yōu)解（無界解）無可行解第四節(jié)應(yīng)用實(shí)例一、護(hù)士配備問題 某醫(yī)院每天至少需要下列數(shù)量的護(hù)士：班次時間護(hù)士數(shù)

1上午6時－上午10時602上午10時－下午2時703下午2時－下午6時604下午6時－晚10時505晚10時－凌晨2時206凌晨2時－上午6時30

每班的護(hù)士在值班開始時向病房報(bào)到，連續(xù)工作八小時。試問：為滿足每班所需要的護(hù)士數(shù)，醫(yī)院最少應(yīng)雇傭多少護(hù)士？請列出線性規(guī)劃問題的數(shù)學(xué)模型。解：設(shè)x1表示第1班次向病房報(bào)到的護(hù)士數(shù)；

x2表示第2班次向病房報(bào)到的護(hù)士數(shù)；

x3表示第3班次向病房報(bào)到的護(hù)士數(shù)；

x4表示第4班次向病房報(bào)到的護(hù)士數(shù)；

x5表示第5班次向病房報(bào)到的護(hù)士數(shù)；

x6表示第6班次向病房報(bào)到的護(hù)士數(shù)。

則有MinZ=

s.t.x6+x1≥60x1+x2≥70x2+x3≥60