生物數(shù)學(xué)－線性規(guī)劃

生物數(shù)學(xué)一線性規(guī)劃

第一章線性規(guī)劃的數(shù)學(xué)模型

一'線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

在工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、財(cái)貿(mào)工作等各項(xiàng)經(jīng)濟(jì)活動(dòng)中，必須提高經(jīng)濟(jì)效

益，做到耗費(fèi)較少的人力物力財(cái)力，創(chuàng)造出較多的經(jīng)濟(jì)價(jià)值。

提高經(jīng)濟(jì)效益可以通過(guò)兩種途徑：一是技術(shù)方面的各種改進(jìn)，例如工業(yè)生

產(chǎn)上改善工藝，使用新的設(shè)備和新型原材料等。二是生產(chǎn)組織和計(jì)劃的改進(jìn)，

即合理安排人力物力資源，合理組織生產(chǎn)過(guò)程，在條件不變的情況下，統(tǒng)籌安

排，使總的經(jīng)濟(jì)效益最好。后者就是運(yùn)籌學(xué)研究的主要內(nèi)容。

運(yùn)籌學(xué)有規(guī)劃論、排隊(duì)論、對(duì)策論等許多分支。線性規(guī)劃是其中的一個(gè)重

要分支。早在20世紀(jì)30年代末就有人從運(yùn)輸?shù)葐?wèn)題開(kāi)始研究它。它在運(yùn)籌學(xué)

中是研究較早、發(fā)展較快、應(yīng)用較廣、比較成熟的一個(gè)分支。它研究的問(wèn)題主

要有兩類：一是一項(xiàng)任務(wù)確定后，如何統(tǒng)籌安排，盡量做到用最少的人力物力

資源去完成這一任務(wù)。二是已有一定數(shù)量的人力物力資源，如何安排使用它們,

使得完成任務(wù)最多。其實(shí)這兩類問(wèn)題是一個(gè)問(wèn)題的兩個(gè)方面，就是所謂尋求整

個(gè)問(wèn)題的某個(gè)整體指標(biāo)最優(yōu)的問(wèn)題。在經(jīng)濟(jì)領(lǐng)域里，這種問(wèn)題很多。

（-）運(yùn)輸問(wèn)題

在某一地區(qū)內(nèi)，有某種產(chǎn)品的產(chǎn)地與銷地各若干個(gè)，把這種產(chǎn)品從各個(gè)產(chǎn)

地調(diào)運(yùn)到各個(gè)銷地，調(diào)運(yùn)方案可以很多，應(yīng)如何調(diào)運(yùn)，才能使總的運(yùn)費(fèi)或運(yùn)輸

量（即總的運(yùn)行噸公里數(shù)）最少。

（-）生產(chǎn)的組織與計(jì)劃問(wèn)題

一個(gè)工廠或車間有各種不同類型的車床各若干臺(tái)，各種不同車床生產(chǎn)各種

零件的效率不同，在一個(gè)生產(chǎn)周期，應(yīng)如何安排個(gè)車床的生產(chǎn)時(shí)間，使得成套

的產(chǎn)品總量最大。類似的還有勞動(dòng)力的安排等問(wèn)題。

（三）合理下料問(wèn)題

在加工中需要將某類條材或板材下不同規(guī)格的毛坯，各種毛坯的數(shù)量也可

能不同，應(yīng)如何選取合適的裁法，使毛坯數(shù)量符合要求，并且使總料頭最少（即

所用原材料最少）。

（四）配料問(wèn)題

在食品、化工、冶煉等企業(yè)，常常用幾種原料，制成達(dá)到含有一定成分的

產(chǎn)品，而這些不同原料價(jià)格不同，應(yīng)如何決定配料的方案，才能使生產(chǎn)的產(chǎn)品

所含成分合乎要求，而產(chǎn)品的成本最低。

（五）布局問(wèn)題

各種作物在不同土壤上單位面積產(chǎn)量不一樣，如何合理安排各種作物在各

種土壤上的種植面積，達(dá)到因地制宜，在完成種植計(jì)劃的前提下，使總產(chǎn)量最

多。這是作物布局問(wèn)題。將某幾個(gè)地方出產(chǎn)的原料，集中到某幾個(gè)地方加工成

成品，然后再運(yùn)到某幾個(gè)成品需要地。有些地方可能既是原料出產(chǎn)地，又是產(chǎn)

品需要地，也是成品加工地。因各地間運(yùn)費(fèi)不同，成品加工費(fèi)不同，設(shè)廠條件

不同，應(yīng)在什么地方設(shè)廠，規(guī)模多大，才能滿足成品需要地的需要，又使費(fèi)用

（包括運(yùn)費(fèi)、加工費(fèi)）最低。這是工廠布局問(wèn)題。

（六）分派問(wèn)題

〃件工作分派給〃人去做，每人做一件工作，而各人對(duì)做各種工作的效率不

同，問(wèn)應(yīng)如何合理分派，才能使完成全部工作的總工時(shí)最少。類似的問(wèn)題還有

作物的種植安排、機(jī)床加工零件任務(wù)的分配問(wèn)題等。

數(shù)學(xué)模型是描述實(shí)際問(wèn)題共性的抽象的數(shù)學(xué)形式。對(duì)數(shù)學(xué)模型的研究，有

助于我們認(rèn)識(shí)這類問(wèn)題的性質(zhì)和尋求它的一般解法?，F(xiàn)在首先介紹幾個(gè)典型的

實(shí)際問(wèn)題。

（-）運(yùn)輸問(wèn)題

例1設(shè)有兩個(gè)磚廠4,4，其產(chǎn)量分別為23萬(wàn)塊和27萬(wàn)塊，生產(chǎn)的磚全

部銷往片,坊,鳥(niǎo)三個(gè)工地。其需要量分別為17萬(wàn)塊、18萬(wàn)塊和15萬(wàn)塊。自各

產(chǎn)地到各銷地的運(yùn)價(jià)如表1T。問(wèn)應(yīng)如何調(diào)運(yùn)，才使總運(yùn)費(fèi)最低？

表17

自產(chǎn)地到銷地的運(yùn)價(jià)產(chǎn)量

銷地（工地）

（萬(wàn)塊）

與B2B3

產(chǎn)幕A50607023

地二&6011016027

銷量（萬(wàn)塊）171815

解設(shè)沏表示由成廠4?運(yùn)往工地均糖的數(shù)量（單位：萬(wàn)塊）（i=l,2；j=l,

2,3）,例如xii表示由糖廠4運(yùn)往工地所病的數(shù)量等等?，F(xiàn)列表如下（見(jiàn)表

1-2）

表1-2

工地

BiB2B3產(chǎn)量

AiXI1X12X1323

27

A2X21X22X23

銷量17181550

磚廠4運(yùn)往工地耳，與，々病的數(shù)量之和等于A,的產(chǎn)量；工地用接收磚廠

4,4磚的數(shù)量之和等于劣的需求量。于是有

xn+x12+x13=23

%2i+%22+%23=27

約束條件?X”+%21=17

Xn+%22=18

x13+x23=15

x..>0(z=l,2;產(chǎn)1,2,3)

顯然，可行的調(diào)運(yùn)方案很多，我們的目的是尋找運(yùn)費(fèi)最低的調(diào)運(yùn)方案，即

求一組變量F,占2，七3，孫，122，%23的值，使其滿足約束條件，并使運(yùn)價(jià)函數(shù)

s=50x”+60看2+70/3+60X21+110x22+160x23

達(dá)到最小。

一般地，設(shè)某種物資有m個(gè)產(chǎn)地Ai,A2,……，Am；聯(lián)合供應(yīng)n個(gè)銷地

B1,比,……，Bno各產(chǎn)地產(chǎn)量（單位：噸）、各銷地銷量（單位：噸）、各產(chǎn)

地至各銷地單位運(yùn)價(jià)（單位：元/噸）如表1-3所示。問(wèn)應(yīng)如何調(diào)運(yùn)，才使總運(yùn)

費(fèi)最少？

表1-3

銷地

產(chǎn)地^BiBi…Bn產(chǎn)量（噸）

AiC11C12?**C\na\

AiC21C22C2nai

??????

AmCm\Cm2"■"Cmndm

銷量（噸）bi歷…bn

表中：的表示產(chǎn).地4的產(chǎn)量（1=1,2,…，m）；

歷表示銷地用的銷量（產(chǎn)1,2,…，〃）；

◎表示4與4間的單位運(yùn)價(jià)（元/噸）（?=1,2,?,,,m；j=l,2,,,,,

n)o

m〃

解假定產(chǎn)銷平衡（即設(shè)殉表示由產(chǎn)地4-運(yùn)往銷地用的物

，'=1>1

資數(shù)（，=1,2,…，機(jī)；;=1,2,…，〃）。那么上述運(yùn)輸問(wèn)題的數(shù)學(xué)模型為：

求一組變量?jī)桑?=1,2,…，m；j=l,2,…，閥）的值，使它滿足約束條

件

/+%+…+%“=q

+%+…+Xmn=am

Xll+X21+…+七"1=4

x12+x21+-■-+xm2=b2

Xln+X2n+---+X,nn="

Xy>0（i=l,2---,m;j=1,2,

并使目標(biāo)函數(shù)S=C\\X\\+Cl1Xn+---+CmnXmn的值最小。

利用連加號(hào)（Z）,上述模型可以寫為：求一組變量沏值，使?jié)M足約束條件

=q（，=l,2,…,加）

7=1

（產(chǎn)地4發(fā)到各銷地的發(fā)量總和等于4的產(chǎn)量）

m

<工了小可好=1,2,…,n）

i=l

（各產(chǎn)地發(fā)到銷地鳥(niǎo)的發(fā)量總和等于4的銷量）

Xy20（，=1,2…，孫）=1,2,…川

（調(diào)運(yùn)量不能為負(fù)數(shù)）

〃m

并且使目標(biāo)函數(shù)s工好的值最?。傔\(yùn)費(fèi)最少）。

尸1i=l

如果沒(méi)有產(chǎn)銷平衡這一限制，當(dāng)產(chǎn)大于銷時(shí)（即這一問(wèn)題的

i=li=l

數(shù)學(xué)模型應(yīng)為：求一組變量沏（，=1,2,…，m；j=l,2,…，n）的值，使它

滿足約束條件

X*<4Z,.（Z

（產(chǎn)地4發(fā)到各銷地的發(fā)量總和不超過(guò)4的產(chǎn)量）

<WX=bj（j=1,2,…,n）

Z=1

（各產(chǎn)地發(fā)到銷地坊的發(fā)量總和等于4的銷量）

0（，=1,2…,加"=1,2,）

（調(diào)運(yùn)量不能為負(fù)數(shù)）

〃m

并且使目標(biāo)函數(shù)的值最?。傔\(yùn)費(fèi)最少）。

j=li=l

（二）布局問(wèn)題

1.作物布局

某生產(chǎn)隊(duì)要在〃塊地31,&,…，B”上,種植加種作物Ai,A2,…，Amo各

塊土地畝數(shù)、各種作物計(jì)劃播種面積及各種作物在各塊地上的畝產(chǎn)量（單位：

公斤）如表1-4所示，問(wèn)應(yīng)如何合理安排種植計(jì)劃，才能使總產(chǎn)量最多（這里

假定即，即計(jì)劃播種總面積等于土地面積）。

1=11=1

表1一4

土地

作物BiB2…Bn播種面積

AiC11C12C\na\

AiC21C22C2nai

AmCmlCm2CmnClm

土地畝數(shù)biZ?2bn

表中：的表示作物A?的播種面積（i=l,2,???,m）；

力表示土地5?的畝數(shù)（j=l,2,…,n）；

◎表示在土地為上種植作物4的畝產(chǎn)量（i=l,2,…,m；7=1,2,…,

n）o

解設(shè)沏為土地為種植作物4?的畝數(shù)（z=L2,…,m；j=l,2,…,〃）,

那么作物布局問(wèn)題的數(shù)學(xué)模型為：

求一組變量殉?（i=l,2,…，m；j=l,2,…，〃）的值，使它滿足約束條

件

（z=l,2,---,m）

j=i.

（在各地塊上種植作物a的總畝數(shù)等于a的計(jì)劃播種數(shù)）

jn_

J=1

（在土地4上種植各種作物的總畝數(shù)等于用的面積）

Xy20（，=1,2…,〃2"=1,2,…

、（種植數(shù)不能為負(fù)數(shù)）

〃m

并且使目標(biāo)函數(shù)的值最大（總產(chǎn)量最多）。

j=l日

這一數(shù)學(xué)模型和前面運(yùn)輸問(wèn)題的數(shù)學(xué)模型相同，具有這樣數(shù)學(xué)模型的問(wèn)題

還有機(jī)床加工零件的問(wèn)題（見(jiàn)習(xí)題一第2題）等。我們稱這類問(wèn)題為康-希問(wèn)題，

或統(tǒng)稱為運(yùn)輸問(wèn)題。

2.工廠布局問(wèn)題

設(shè)有〃個(gè)地區(qū)Ai,Ai,An,在某一個(gè)計(jì)劃期內(nèi)，At生產(chǎn)某種原料由噸,

同時(shí)需要用這種原料加工的某種產(chǎn)品加噸（i=l,2,…，〃），已知左噸原料可

制造1噸該產(chǎn)品。設(shè)這n個(gè)地區(qū)所產(chǎn)原料的總數(shù)恰好能生產(chǎn)各地區(qū)所需該產(chǎn)品

的總數(shù),即。另外已知在4?設(shè)廠加工該產(chǎn)品的加工費(fèi)為每噸4元。

i=li=l

在A設(shè)廠生產(chǎn)該產(chǎn)品的數(shù)量最多為a噸，最少為力噸（7=1,2,…，n）。從4

運(yùn)原料或產(chǎn)品到4;（工戶1,2,???,n）每噸為,元，問(wèn)應(yīng)在何地設(shè)廠、生產(chǎn)

多少該產(chǎn)品，才能既滿足需要，又使生產(chǎn)費(fèi)用（包括原料和產(chǎn)品運(yùn)費(fèi)、產(chǎn)品加

工費(fèi)）最少？

解設(shè)沏表示由4運(yùn)到4的原料數(shù)（單位：噸）（i,j=l,2,…，n）,其

中廣i時(shí)，表示A留用數(shù)；為表示由4運(yùn)到4的成品數(shù)（單位：噸）（i,j=l,

2,…，力,其中產(chǎn)z?時(shí)，表示4留用數(shù)；z,表示4設(shè)廠的年產(chǎn)成品數(shù)（單位：

噸）（i=l,2,,,,,〃）。它們之間的關(guān)系如表1-5所示。

表1-5

生產(chǎn)加

???生產(chǎn)成

AiA2An原料X

品數(shù)

數(shù)費(fèi)

XIIX12Xin

力Wzi

???

AiC11C12C\naid\

Wei

ynyi2yin

X21X22X2n

flWzz

???

AiC21C22C2n6Z2di

We2

y2iy22yin

Xn\Xn2Xnn

fn^Zn

???

AnCnlCn2CnnClndn

yniyn2ynn

需成

bibi???bn

品數(shù)

需原

kzikZ2???kZn

料數(shù)

根據(jù)題意，得數(shù)學(xué)模型如下：

求一組變量回、yij>zi（i,j=l,2,…，n）的值，使它滿足約束條件

￡%=<7,.（z=1,2,???,?）

7=1

（從A運(yùn)往各地原料總數(shù)以及a的留用數(shù)等于a的原料產(chǎn)量）

n

Z/=kZj（J=1,2,…,n）

i=l

（從各地運(yùn)往&的原料總數(shù)以及4的留用數(shù)等于在A設(shè)廠所需原料數(shù)）

Z%=z,a=i,2,…

7=1

<（由人運(yùn)往各地的成品總數(shù)以及人的留用數(shù)等于a的產(chǎn)品數(shù)）

?為=bj（j=1,2,…,n）

i=l

（從各地運(yùn)到&的成品數(shù)以及4的留用數(shù)等于4所需成品數(shù)）

/.<z;<e;（z=l,2---,n）

（在4生產(chǎn)的成品數(shù)必須何至4之間）

%-0，y,j-°，z,2o

、（調(diào)運(yùn)原料數(shù)，調(diào)運(yùn)成品數(shù)，生產(chǎn)成品數(shù)都不能為負(fù)數(shù)）

并且使目標(biāo)函數(shù)8=22與（/+先）+Z"，的值最?。ㄉa(chǎn)總費(fèi)用最少）。

i=lj=lz=l

（三）分派問(wèn)題

設(shè)有〃件工作Bi,B?,…,3"分派給〃人Ai,A2,…，4去做，每人只做

一件工作，且每件工作只分派一個(gè)去做。設(shè)A完成5的工時(shí)為0解,/=1,2,…,〃）。

問(wèn)應(yīng)如何分派才使完成全部工作的總工時(shí)最少。

解設(shè)xij為Bj分'派給Ai的情況：Bj分派給Ai時(shí)xij=1；不分派給4-時(shí)xij=Q

（，,）=1,2,…那末這一問(wèn)題的數(shù)學(xué)模型為：求一組變量芍（，,）=1,2,…,〃）的

值，使它滿足約束條件

G=l,2,???,?）

i=\

（每件工作只分派一人去做）

n

（z=l,2,???,?）

j=i

（每人只做一件工作）

%=0或1（z,j=1,2,???,?）

（每人對(duì)每件工作只有做與不做兩種情況）

并且使目標(biāo)函數(shù)s=產(chǎn)了的值最小。

*1>1

分派問(wèn)題是運(yùn)輸問(wèn)題的特例。因?yàn)樽兞科阒蝗?和1,所以又稱它為0-1

規(guī)劃問(wèn)題。

（四）生產(chǎn)組織與計(jì)劃問(wèn)題

（1）設(shè)某車間用機(jī)床Ai,A2,,,,,A”生產(chǎn)由31,及，…，￡這〃個(gè)不同

零件構(gòu)成的機(jī)器。如果每架機(jī)器需要各種零件的數(shù)目成比例才1：42：…：4〃；

機(jī)床A生產(chǎn)零件均的效率（每日生產(chǎn)零件數(shù)）為。心問(wèn)應(yīng)如何分配機(jī)床負(fù)荷,

才使生產(chǎn)的機(jī)器最多。

解設(shè)出為機(jī)床4生產(chǎn)零件用的時(shí)間（單位：日）（z=l,2,j=l,2,---,n）o

這一問(wèn)題的數(shù)學(xué)模型為：

n

￡4=l（z

>i

（機(jī)床4生產(chǎn)各種零件時(shí)間總和應(yīng)等1）

ZCilXil:ZCi2Xi2:“?:Z

C加X(jué)加=4：4：,??：4

i=lz=li=l

約束條件mmm

ZQ￡Ci2Xi2CinXin

即上L-i=l--------=5

4%24,

（各機(jī)床一天生產(chǎn)各種零件總數(shù)，應(yīng)成已定比例）

Xy>0（z=l,2,???,/?!；;=1,2,????）

（生產(chǎn)零件時(shí)間不能為負(fù)數(shù)）

m

>,cilxi]

并且使目標(biāo)函數(shù)S=——的值最大。

4

特別地，當(dāng)?。?2：…：4”=1：1：…：1（即每架機(jī)器需要各種零件數(shù)目

相同）時(shí)，它的數(shù)學(xué)模型為：

求一組變量沏（i=l,2,…附；）=1,2,…，”）的值，使它滿足約束條件

Z%=1（，=1,2，加）

7=1

mmm

Cx

<Z=Ei2n=..?=￡Cinxin

i=li=li=l

X）>O（z=l,2,???,/?;J=1,2,???,?）

m

并且使目標(biāo)函數(shù)S=的值最大。

i=l

（2）設(shè)用機(jī)種原料Al,Al,,,,,Amt可以生產(chǎn)〃種產(chǎn)品31,B2,…Bn。

現(xiàn)有原料數(shù)、每單位產(chǎn)品所需原料數(shù)，及每單位產(chǎn)品可得利潤(rùn)數(shù)如表1-6所示。

問(wèn)應(yīng)如何組織生產(chǎn)才能使利潤(rùn)最大？

表1-6

單位\產(chǎn)

產(chǎn)品\品

所需\BiB2…Bn現(xiàn)有原料

原料

AiC11cn…Clna\

A2C21C22C2n02

AmCmlCm2■■,Cmndm

單位產(chǎn)品可得利潤(rùn)bibibn

解設(shè)為為生產(chǎn)產(chǎn)品用（產(chǎn)1,2,…，〃）的計(jì)劃數(shù)。這一問(wèn)題的數(shù)學(xué)模型為:

求一組變量芍（/=1,2,…的值，使它滿足約束條件

EC/<tz,.（z=1,2,??■,/?）

J=I

（生產(chǎn)各種產(chǎn)品所需原料a的總數(shù)不能超過(guò)a現(xiàn)有數(shù)4）

Xj20（7=1,2,…,九）

（各種產(chǎn)品計(jì)劃生產(chǎn)數(shù)不能為負(fù)數(shù)）

并且使目標(biāo)函數(shù)s=的值最大（總利潤(rùn)最多）。

7=1

（3）某工廠用機(jī)床Al,A2,…A”加工零件31,B2,…B”在一個(gè)生產(chǎn)周

期，各機(jī)床只能工作的機(jī)時(shí)、工廠必須完成各零件加工數(shù)、各機(jī)床加工每個(gè)零

件的時(shí)間（單位：機(jī)時(shí)/個(gè)）和加工每個(gè)零件的成本（單位：元/個(gè)）如表1-7和

表1-8所示。問(wèn)在這個(gè)生產(chǎn)周期，怎樣安排各機(jī)床的生產(chǎn)任務(wù)，才能既完成加

工任務(wù)，又使總的加工成本最低。

表1-7

加工\零

每個(gè)\件

在一周期能

零件的、BiBi…Bn

工作的機(jī)時(shí)

機(jī)床

AiC11C12.…Clnai

A2C21C22"■Clnai

AmCmlCm2?,。CmnClm

必須加工零件數(shù)b\bi...bn

表1-8

加工\零

每個(gè)\件

―一零件的\BiBi…Bn

機(jī)床

Aidudn???d\n

Aichidn???d2n

::…

Amdmldm2???dmn

解設(shè)%為機(jī)床4?在一生產(chǎn)周期加工零件5?的個(gè)數(shù)（7=1,2,…,加；尸1,2,…,

〃）。這一問(wèn)題的數(shù)學(xué)模型為：

求一組變量％1（7=1,2,…，m；）=1,2,…的值，使它滿足約束條件

EjjXij<<2,.（z=1,2,???,?）

j=l

（機(jī)床4加工各零件總機(jī)時(shí)不能超過(guò)4能工作機(jī)時(shí)）

_n

E%?耳行=1,2,…,n）

i=l

（各機(jī)床加工零件用的總數(shù)不能少于4需要數(shù)）

/20,整數(shù)"=1,2,…，%j=1,2,…,n）

（加工零件個(gè)數(shù)不能為負(fù)數(shù)、分?jǐn)?shù)）

nm

并且使目標(biāo)函數(shù)s=￡￡%Xy的值最?。庸た偝杀咀钌伲?。

尸12

（五）合理下料問(wèn)題

設(shè)用某原材料（條材或板材）下零件毛坯Ai,A2,…,4,。根據(jù)過(guò)去經(jīng)驗(yàn)在

一件原料上有B2,…幾種不同的下料方式，每種下料方式可得各種毛坯個(gè)

數(shù)及每種零件需要量如表1-9所示。問(wèn)應(yīng)怎樣安排下料方式，使得既能滿足需

要，用的原材料又最少。

表1-9

各方式\下料

下的\方式

零件\BlBl…Bn零件需要量

零件名稱

AiCllC12…c\na\

AiC21C22???C2nai

.??

AmCm\Cm2CmnClm

解設(shè)用鳥(niǎo)種方式下料的原材料數(shù)芍，則這一問(wèn)題的數(shù)學(xué)模型為:

ECa>ai(z=1,2,???,/?)

j=i

約束條件<（所下的a零件總數(shù)不能少于生）

勺20,整數(shù)（J=1,2,

（各種方式下料的原材料數(shù)不能是負(fù)數(shù),分?jǐn)?shù)）

并且使目標(biāo)函數(shù)5=￡為的值最?。ㄋ迷牧狭可伲?。

>1

（六）配料問(wèn)題

設(shè)用〃種原料31,及，…3"制成具有機(jī)種成分Al,A2,…Am的產(chǎn)品，其

所含各成分需要量分別不低于ai,z,…，碗。各種原料的單價(jià)、各種原料所含

成分的數(shù)量如表1-10所示。問(wèn)應(yīng)如何配料，才使產(chǎn)品成本最低。

表1-10

一單位原\原

料所含成\料產(chǎn)品所含

分的\BiB2…Bn成分需要

量

原料所含成分茗

AiC11C12.一C\nai

AiC21C22??,C2nai

AmCmlCm2°,■CmnClm

單價(jià)bibi…bn

解設(shè)需原料均為為單位（j=l,2,-,n）o這一問(wèn)題的數(shù)學(xué)模型為：

求一組變量芍0=1,2,…，”）的值，使它滿足

?

EjjXjNq（i=1,2,…,m）

j=i

<（所有各種原料所含成分4的總數(shù)應(yīng)不少于產(chǎn)品對(duì)A需要量可）

Xj20（7=1,2,…M

（所取原料不能為負(fù)數(shù)）

并且使目標(biāo)函數(shù)5=之“]）的值最?。óa(chǎn)品成本最低）。

7=1

線性規(guī)劃問(wèn)題數(shù)學(xué)模型的一般形式，是求一組變量玉,乙,…,X”，使其滿足:

an%1+anx2+---+alnxn〈仇（或=或24）

。2（或=%，或2%）

a2lxi+a22x2+---+a2nxn<

約束條件<....................................

。加%+金2%+?-?+amnx?<bm（或=bm,或24,）

Xj>0（j=1,2,…

并使目標(biāo)函數(shù)s=GX]+c2x2+…+達(dá)到最?。ɑ蜃畲螅?。

為討論和計(jì)算方便，作如下規(guī)定：

1.如果約束條件中第k個(gè)式子為aklxr+ak2x2+???+aknxn<bk,則人為地

添加變量xn+k>0，使之成為akxxx+ak2x2+…+aknxn+xn+k=4。

如果約束條件中第廠個(gè)式子為明內(nèi)+的2》2+…+?！卞?b’,則人為地添加

變量xn+r>0，使之成為arixx+ar2x2+…+amxn-xn+r=br。

通過(guò)這種方法，使所有的約束條件都變成等式。稱x用，5+，為松弛變量。

2.如果問(wèn)題是使目標(biāo)函數(shù)5=0臼+°2%2+-一+*/達(dá)到最大，則化為使目

標(biāo)函數(shù)s'=—s=-c2x2----cnxn達(dá)到最小。

3.如果某變量與沒(méi)有非負(fù)限制，則引進(jìn)變量X：20,x"j?6,令Xj=x[-x"j,

代入約束條件和目標(biāo)函數(shù)中，化為對(duì)全部變量都有非負(fù)限制。

這樣，可以把線性規(guī)劃問(wèn)題寫成如下標(biāo)準(zhǔn)形式：

mins=c/i+c2x2H-----hcnxn

r

allx1+al2x2+---+alnxn=bx

。21匹+。22尤2+…+。2/“=偽

<....................................

。加七+4“2%+”,+。,“"尤”=或

Xj>0(j=1,2,???,?)

C=(q,02,…，％)，則可將標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題(1)簡(jiǎn)記為

mins=ex

Ax=b(2)

<x>0

向量與（IV/為矩陣A的第/個(gè)列向量，稱為變量與對(duì)應(yīng)的系數(shù)列向量。

二,幾個(gè)基本概念

對(duì)于給定的實(shí)際問(wèn)題，首先是要建立線性規(guī)劃問(wèn)題的數(shù)學(xué)模型（1）,其次

是求問(wèn)題的最優(yōu)解。我們不主張進(jìn)行手工求解的大量訓(xùn)練，僅要求大家理解單

純形方法的基本思想，具體計(jì)算通過(guò)計(jì)算機(jī)來(lái)實(shí)現(xiàn)。這里，先給出如下幾個(gè)基

本概念。

1.如果x°=（#...引）'滿足約束條件，即有Ax°=6,x°20,則稱

為可行解。

2.如果可行解（向量）x°=0,或x°的非零分量對(duì)應(yīng)的系數(shù)列向量線性無(wú)

關(guān)，則稱x°為基礎(chǔ)可行解。

3.使目標(biāo)函數(shù)取最小值的可行解稱為最優(yōu)解。

4.使目標(biāo)函數(shù)取最小值的基礎(chǔ)可行解稱為基礎(chǔ)最優(yōu)解。

習(xí)題一

寫出下列問(wèn)題的數(shù)學(xué)形式：

1.有兩個(gè)煤廠A、B,每月分別進(jìn)煤60噸、100噸。它們擔(dān)負(fù)供應(yīng)三個(gè)居民區(qū)用煤任

務(wù)。這三個(gè)居民區(qū)每月需用煤分別為45噸、75噸、40噸。A廠離這三居民區(qū)分別為10

公里、5公里、6公里，8廠離這三居民區(qū)分別為4公里、8公里、15公里。問(wèn)這兩煤廠如

何分配供煤，才使運(yùn)輸量最小。

2.某車間用機(jī)床4,A2,4加工零件和星分別為50個(gè)和70個(gè)；各機(jī)床必須加

工出零件數(shù)：Ai為40個(gè)，4為35個(gè)，4為45個(gè)；各種機(jī)床加工各種零件加工費(fèi)（單位:

元/個(gè)）如表1-11所示。問(wèn)如何分配這三臺(tái)機(jī)床加工這兩種零件的任務(wù)，才使總的加工費(fèi)

最少。

表1-11

每個(gè)零件\

加工費(fèi)（元/個(gè)小

Bi82

機(jī)

Ai0.40.3

A20.30.5

A30.20.2

3.設(shè)有某種原料產(chǎn)地4,A2,小，把這種原料經(jīng)過(guò)加工，制成成品，再運(yùn)往銷地。

假設(shè)用4噸原料可制成1噸成品。產(chǎn)地4年產(chǎn)原料30萬(wàn)噸，同時(shí)需要成品7萬(wàn)噸。產(chǎn)地

人2年產(chǎn)原料26萬(wàn)噸，同時(shí)需要成品13萬(wàn)噸。產(chǎn)地4年產(chǎn)原料24萬(wàn)噸，不需成品。4與

A2間距離150公里，Al與A3間距離100公里，A2與4間距離200公里。又知原料運(yùn)費(fèi)為

0.3萬(wàn)元/萬(wàn)噸公里，成品運(yùn)費(fèi)為0.25萬(wàn)元/萬(wàn)噸公里。且知在4開(kāi)設(shè)加工廠加工費(fèi)為0.55

萬(wàn)元/萬(wàn)噸，在4為04萬(wàn)元/萬(wàn)噸，在4為0.3萬(wàn)元/萬(wàn)噸。因條件限制，在4設(shè)廠規(guī)模

不能超過(guò)年產(chǎn)成品5萬(wàn)噸，4和4可以不限制。問(wèn)應(yīng)在何地設(shè)廠，生產(chǎn)多少成品，才能

使生產(chǎn)費(fèi)用（包括原料運(yùn)費(fèi)、成品運(yùn)費(fèi)、加工費(fèi)等）最小。

4.某木器廠生產(chǎn)圓桌和衣柜兩種產(chǎn)品?，F(xiàn)有兩種材料，第一種有72立方米，第二種有

56立方米。假設(shè)生產(chǎn)每種產(chǎn)品都需要用兩種木料。生產(chǎn)一個(gè)圓桌和一個(gè)衣柜所需木料如表

1-12所示。每生產(chǎn)一個(gè)圓桌可獲得潤(rùn)6元；生產(chǎn)一個(gè)衣柜可獲利潤(rùn)10元。木器廠在現(xiàn)有

木料條件下，圓桌和衣柜應(yīng)各生產(chǎn)多少，才使獲得利潤(rùn)最多。

表12

木料（單位：立方米）

產(chǎn)品

第一種第二種

圓桌0.180.08

衣柜0.090.28

5.現(xiàn)有三種機(jī)床，生產(chǎn)某種產(chǎn)品的兩種零件。產(chǎn)品需要這兩種零件的數(shù)目相同。各

機(jī)床生產(chǎn)兩種零件的日產(chǎn)量如表1-13所示。問(wèn)應(yīng)如何組織生產(chǎn)，使總產(chǎn)量最大。

表1-13

機(jī)床日產(chǎn)量'

T

BB2B3

零件jj――

Ai301518

A2204050

6.某班有男同學(xué)30人，女同學(xué)20人，星期天準(zhǔn)備去植樹(shù)。根據(jù)經(jīng)驗(yàn)，一天男同學(xué)

平均每人挖坑20個(gè)，或栽樹(shù)30棵，或給25棵樹(shù)澆水，女同學(xué)平均每人挖坑10個(gè)，或栽

樹(shù)20棵，或給15棵樹(shù)澆水。問(wèn)應(yīng)怎樣安排才能使植樹(shù)（包括挖坑、栽樹(shù)、澆水）最多。

7.某鋼廠兩個(gè)煉鋼爐同時(shí)各用一種方法煉鋼。第一種煉法每爐用a小時(shí)；第二種用b

小時(shí)（包括清爐時(shí)間）。假定這兩種煉法每爐出鋼都是上公斤，而煉1公斤鋼的平均燃料

費(fèi)第一法為,"元，第二法為〃元。若要求在c小時(shí)內(nèi)煉鋼公斤數(shù)不少于d,問(wèn)應(yīng)怎樣分配

兩種煉法的任務(wù)，才使燃料費(fèi)用最少。

8.用長(zhǎng)度為500厘米的條材，截成長(zhǎng)度分別為98厘米和78厘米兩種毛坯。要求共

截出長(zhǎng)98厘米的毛坯10000根，78厘米的20000根。問(wèn)怎樣截法，才使所用的原材料最

少。

9.某養(yǎng)雞場(chǎng)有1萬(wàn)只雞，用動(dòng)物飼料和谷類飼料混合喂養(yǎng)。每天每只雞平均吃混合

飼料0.5公斤。其中動(dòng)物飼料占的比例不得少于1/5。動(dòng)物飼料每公斤0.9元；谷類飼料每

公斤0.28元。飼料公司每周只保證供應(yīng)谷類飼料50000公斤。問(wèn)飼料應(yīng)怎樣混合，才使成

本最低。

10.某商店制訂某產(chǎn)品7—12月進(jìn)貨售貨計(jì)劃。已知商店倉(cāng)庫(kù)容量不得超過(guò)500件，

6月底已存貨200件，以后每月初進(jìn)貨一次。假設(shè)各月份某商品買進(jìn)、售出單價(jià)如表1-14

所示。問(wèn)各月進(jìn)貨售貨各多少，才能使總收入最多？

表1-14

月789101112

買進(jìn)（元/件）282425272323

售出（元/件）292426282225

11.設(shè)有"種飼料，各含機(jī)種營(yíng)養(yǎng)成分。每只雞每天需要各營(yíng)養(yǎng)成分的數(shù)量、各種飼

料的單價(jià)，以及各種飼料所含營(yíng)養(yǎng)成分如表1-15所示。問(wèn)應(yīng)如何配合飼料，才能既滿足雞

的營(yíng)養(yǎng)需要，又使成本又最低。

表1-15

飼料所含\

一^數(shù)量、^料

BiB?…Bn營(yíng)需要量

營(yíng)嬴

...C］八

AiCllC1241

A2C21C22***C2n

AmCmiCm2?0°Cmn

飼料單價(jià)b\歷

12.在〃塊土地上種植“種作物。每塊土地只種一種作物且每種作物只在一塊土地上

種植。其數(shù)據(jù)如表1-16所示。問(wèn)應(yīng)如何制訂種植計(jì)劃，才使總產(chǎn)值最多。

表1-16

每塊土地種植\

起”的產(chǎn)曉

BiBn

作物

AiC\\C12C\n

人2C21C22…C2n

?

CnlCn2…Cmn

第二章單純形方法

一'單純形表的構(gòu)造

仍討論標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題（1）。這里，假定A為行滿秩矩陣，即K（A）=根。

記A=憶，舄，…，Pn],稱A的m個(gè)線性無(wú)關(guān)的列向量構(gòu)成的矩陣

B=\Pit，P”,…,4J為線性規(guī)劃問(wèn)題的的一個(gè)基。顯然，基8是加階非奇異矩

陣。一個(gè)線性規(guī)劃問(wèn)題可能有不止一個(gè)的基。

在理論研究部分，為討論方便，不妨設(shè)8是由4的前加列組成，即

B=[Pp%…，Pm]>并記N=R+1，PQ…，Pn]>于是A=?N]o相應(yīng)地,

令4=（七，X2,…，4）'=（七"+1，七〃+2,…，％）'Q=（。，,2,…，7）'

=(c,“+l，C,,+2,…，％)，貝1有工=

稱乙為基向量，4的加個(gè)分量為基變量；而為非基向量，標(biāo)的〃-加個(gè)

分量為非基變量。根據(jù)上述討論得到：

o[5,N]Xb=b

_XN_

Ax=b<QBXB+NXN=b（3）

l

oxB=B~b-B'NXN

XCNX

CBB~A-C=CBB~'[B,7V]-[B,C]=[°，CBB~N-CN](4)

1l(4)

將s=cx與CBB-AX=cBBb兩邊相加，并應(yīng)用式的結(jié)論，得

s=[1

cBB~b-(CBB~A-C)X

xXB(5)

=cBB~b-\p,CBB~N-cN]

_XN_

ll

=cBB-b-(cBB-N-cN)xN

由(3)式知

/B=8"即X=KB-lb

(6)

0

滿足條件約束A尤=匕。稱（6）為對(duì)應(yīng)于基B的基礎(chǔ)解，但它不一定是可行解

（并非有XB=B"20），更難以是最優(yōu)解。

按第一章給出的定義，若（6）是可行解，則它為基礎(chǔ)可行解；若（6）是

最優(yōu)解，則它為基礎(chǔ)最優(yōu)解。

可以證明：若線性規(guī)劃問(wèn)題（1）存在可行解，則一定存在（6）式所表達(dá)

的可行解；若其存在最優(yōu)解，則一定存在（6）式所表達(dá)的最優(yōu)解。

用單純形方法求解線性規(guī)劃問(wèn)題時(shí)，總是?。?）式所表達(dá)的解；求解的過(guò)

程是不斷調(diào)整基8,使解（6）成為最優(yōu)解。稱使解（6）為最優(yōu)解的基8為最

優(yōu)基。

不論取什么樣的解，（5）式總是成立的。由（5）式的最后一個(gè)等號(hào)可知，

解（6）對(duì)應(yīng)的目標(biāo)函數(shù)值為5=。理「力，且有

1.當(dāng)金5一％—c〉0時(shí)，適當(dāng)取了之0可使（CBB-M—c）x〉O,從而

rXl

s=CBBb-{CBBA-c）x<CBBb

此時(shí)，（6）式表達(dá)的解不是最優(yōu)解；

2.當(dāng)CB3-A-C<0時(shí)，無(wú)論取什么樣的解尤之。都有

lXl

s=cBBb-{CBBA-c）x>CBBb

若解（6）還滿足非負(fù)約束，即XB=K42。，則其是最優(yōu)解。

鑒于金氏必-。在最優(yōu)解判別中的重要作用，稱之為檢驗(yàn)數(shù)或判別數(shù)。由

⑷式看出，基變量的檢驗(yàn)數(shù)為零，非基變量的檢驗(yàn)數(shù)表示為金"卬-。、。綜

上所述，基礎(chǔ)解（6）是最優(yōu)解的充分必要條件為：

x=B~'b>0,、

JRB（7）

1

CBBA-c<Q

由于

5-ex=0s+（CBlA-c）x=CB'b

<<^>VBB

ll

、Ax=bIB~Ax=B~b

「1cQA-心

若將S看成是一個(gè)變量，則（8）式是一個(gè)關(guān)于〃+1個(gè)變量5,毛,々,…，斗的線性

方程組。對(duì)比模型（2）與（8）式容易發(fā)現(xiàn)：解線性規(guī)劃問(wèn)題（2）,實(shí)質(zhì)上是

求線性方程組（8）的使變量s取最小值的解。

方程組（8）的增廣矩陣為

1CBlA-cCBlb

BB(9)

0ll

BABb(m+1)x(n+2)

單純形方法要求解方程組（8）時(shí)不進(jìn)行“第一行與其他行交換，第一行乘以非

零常數(shù)加到其他行”的變換，則矩陣（9）的第一列始終不變，即在第一個(gè)方程

中s的系數(shù)始終為1,其余方程中s的系數(shù)始終為0。因此，在解方程組的過(guò)程

中，矩陣（9）的第一列是不必要的。習(xí)慣上，將增廣矩陣（9）的第二、三兩

列構(gòu)成如下的單純形表：

boo???瓦"

CB'bCB1A-cbn仇”

T(B)=BB(10)

l[

BbBA(m+1)x(n+1)

bmob,nlbmn

由方程組由）知,單純形表（10）對(duì)應(yīng)著線性方程組

s

+di尤i+再+…+bOnxn=bm

印14+42々+…+屋/=bw

bx+bx+---+bx=b

2li2222nn20