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

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

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

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

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

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

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

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

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

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

運籌學有規(guī)劃論、排隊論、對策論等許多分支。線性規(guī)劃是其中的一個重

要分支。早在20世紀30年代末就有人從運輸?shù)葐栴}開始研究它。它在運籌學

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

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

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

使得完成任務最多。其實這兩類問題是一個問題的兩個方面，就是所謂尋求整

個問題的某個整體指標最優(yōu)的問題。在經(jīng)濟領域里，這種問題很多。

（-）運輸問題

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

地調運到各個銷地，調運方案可以很多，應如何調運，才能使總的運費或運輸

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

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

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

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

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

（三）合理下料問題

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

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

所用原材料最少）。

（四）配料問題

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

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

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

（五）布局問題

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

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

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

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

品需要地，也是成品加工地。因各地間運費不同，成品加工費不同，設廠條件

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

（包括運費、加工費）最低。這是工廠布局問題。

（六）分派問題

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

同，問應如何合理分派，才能使完成全部工作的總工時最少。類似的問題還有

作物的種植安排、機床加工零件任務的分配問題等。

數(shù)學模型是描述實際問題共性的抽象的數(shù)學形式。對數(shù)學模型的研究，有

助于我們認識這類問題的性質和尋求它的一般解法。現(xiàn)在首先介紹幾個典型的

實際問題。

（-）運輸問題

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

部銷往片,坊,鳥三個工地。其需要量分別為17萬塊、18萬塊和15萬塊。自各

產(chǎn)地到各銷地的運價如表1T。問應如何調運，才使總運費最低？

表17

自產(chǎn)地到銷地的運價產(chǎn)量

銷地（工地）

（萬塊）

與B2B3

產(chǎn)幕A50607023

地二&6011016027

銷量（萬塊）171815

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

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

1-2）

表1-2

工地

BiB2B3產(chǎn)量

AiXI1X12X1323

27

A2X21X22X23

銷量17181550

磚廠4運往工地耳，與，々病的數(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)

顯然，可行的調運方案很多，我們的目的是尋找運費最低的調運方案，即

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

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

達到最小。

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

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

地至各銷地單位運價（單位：元/噸）如表1-3所示。問應如何調運，才使總運

費最少？

表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間的單位運價（元/噸）（?=1,2,?,,,m；j=l,2,,,,,

n)o

m〃

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

，'=1>1

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

求一組變量兩（1=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,

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

利用連加號（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ā)到銷地鳥的發(fā)量總和等于4的銷量）

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

（調運量不能為負數(shù)）

〃m

并且使目標函數(shù)s工好的值最?。傔\費最少）。

尸1i=l

如果沒有產(chǎn)銷平衡這一限制，當產(chǎn)大于銷時（即這一問題的

i=li=l

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

滿足約束條件

X*<4Z,.（Z

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

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

Z=1

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

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

（調運量不能為負數(shù)）

〃m

并且使目標函數(shù)的值最?。傔\費最少）。

j=li=l

（二）布局問題

1.作物布局

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

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

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

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

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

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

那么作物布局問題的數(shù)學模型為：

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

件

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

j=i.

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

jn_

J=1

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

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

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

〃m

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

j=l日

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

還有機床加工零件的問題（見習題一第2題）等。我們稱這類問題為康-希問題，

或統(tǒng)稱為運輸問題。

2.工廠布局問題

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

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

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

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

i=li=l

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

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

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

工費）最少？

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

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

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

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

表1-5

生產(chǎn)加

???生產(chǎn)成

AiA2An原料X

品數(shù)

數(shù)費

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ù)學模型如下：

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

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

7=1

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

n

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

i=l

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

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

7=1

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

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

i=l

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

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

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

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

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

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

i=lj=lz=l

（三）分派問題

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

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

問應如何分派才使完成全部工作的總工時最少。

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

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

值，使它滿足約束條件

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

i=\

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

n

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

j=i

（每人只做一件工作）

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

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

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

*1>1

分派問題是運輸問題的特例。因為變量沏只取0和1,所以又稱它為0-1

規(guī)劃問題。

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

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

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

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

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

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

這一問題的數(shù)學模型為：

n

￡4=l（z

>i

（機床4生產(chǎn)各種零件時間總和應等1）

ZCilXil:ZCi2Xi2:“?:Z

C加X加=4：4：,??：4

i=lz=li=l

約束條件mmm

ZQ￡Ci2Xi2CinXin

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

4%24,

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

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

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

m

>,cilxi]

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

4

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

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

求一組變量沏（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

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

i=l

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

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

問應如何組織生產(chǎn)才能使利潤最大？

表1-6

單位\產(chǎn)

產(chǎn)品\品

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

原料

AiC11cn…Clna\

A2C21C22C2n02

AmCmlCm2■■,Cmndm

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

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

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

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

J=I

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

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

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

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

7=1

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

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

件的時間（單位：機時/個）和加工每個零件的成本（單位：元/個）如表1-7和

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

工任務，又使總的加工成本最低。

表1-7

加工\零

每個\件

在一周期能

零件的、BiBi…Bn

工作的機時

機床

AiC11C12.…Clnai

A2C21C22"■Clnai

AmCmlCm2?,。CmnClm

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

表1-8

加工\零

每個\件

―一零件的\BiBi…Bn

機床

Aidudn???d\n

Aichidn???d2n

::…

Amdmldm2???dmn

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

〃）。這一問題的數(shù)學模型為：

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

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

j=l

（機床4加工各零件總機時不能超過4能工作機時）

_n

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

i=l

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

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

（加工零件個數(shù)不能為負數(shù)、分數(shù)）

nm

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

尸12

（五）合理下料問題

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

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

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

要，用的原材料又最少。

表1-9

各方式\下料

下的\方式

零件\BlBl…Bn零件需要量

零件名稱

AiCllC12…c\na\

AiC21C22???C2nai

.??

AmCm\Cm2CmnClm

解設用鳥種方式下料的原材料數(shù)芍，則這一問題的數(shù)學模型為:

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

j=i

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

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

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

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

>1

（六）配料問題

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

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

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

表1-10

一單位原\原

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

分的\BiB2…Bn成分需要

量

原料所含成分茗

AiC11C12.一C\nai

AiC21C22??,C2nai

AmCmlCm2°,■CmnClm

單價bibi…bn

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

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

?

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

j=i

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

Xj20（7=1,2,…M

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

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

7=1

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

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

。2（或=%，或2%）

a2lxi+a22x2+---+a2nxn<

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

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

Xj>0（j=1,2,…

并使目標函數(shù)s=GX]+c2x2+…+達到最?。ɑ蜃畲螅?/p>

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

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

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

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

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

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

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

標函數(shù)s'=—s=-c2x2----cnxn達到最小。

3.如果某變量與沒有非負限制，則引進變量X：20,x"j?6,令Xj=x[-x"j,

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

這樣，可以把線性規(guī)劃問題寫成如下標準形式：

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

r

allx1+al2x2+---+alnxn=bx

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

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

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

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

C=(q,02,…，％)，則可將標準線性規(guī)劃問題(1)簡記為

mins=ex

Ax=b(2)

<x>0

向量與（IV/為矩陣A的第/個列向量，稱為變量與對應的系數(shù)列向量。

二,幾個基本概念

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

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

純形方法的基本思想，具體計算通過計算機來實現(xiàn)。這里，先給出如下幾個基

本概念。

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

為可行解。

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

關，則稱x°為基礎可行解。

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

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

習題一

寫出下列問題的數(shù)學形式：

1.有兩個煤廠A、B,每月分別進煤60噸、100噸。它們擔負供應三個居民區(qū)用煤任

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

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

何分配供煤，才使運輸量最小。

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

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

元/個）如表1-11所示。問如何分配這三臺機床加工這兩種零件的任務，才使總的加工費

最少。

表1-11

每個零件\

加工費（元/個小

Bi82

機

Ai0.40.3

A20.30.5

A30.20.2

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

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

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

A2間距離150公里，Al與A3間距離100公里，A2與4間距離200公里。又知原料運費為

0.3萬元/萬噸公里，成品運費為0.25萬元/萬噸公里。且知在4開設加工廠加工費為0.55

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

不能超過年產(chǎn)成品5萬噸，4和4可以不限制。問應在何地設廠，生產(chǎn)多少成品，才能

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

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

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

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

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

表12

木料（單位：立方米）

產(chǎn)品

第一種第二種

圓桌0.180.08

衣柜0.090.28

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

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

表1-13

機床日產(chǎn)量'

T

BB2B3

零件jj――

Ai301518

A2204050

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

平均每人挖坑20個，或栽樹30棵，或給25棵樹澆水，女同學平均每人挖坑10個，或栽

樹20棵，或給15棵樹澆水。問應怎樣安排才能使植樹（包括挖坑、栽樹、澆水）最多。

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

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

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

兩種煉法的任務，才使燃料費用最少。

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

截出長98厘米的毛坯10000根，78厘米的20000根。問怎樣截法，才使所用的原材料最

少。

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

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

公斤0.28元。飼料公司每周只保證供應谷類飼料50000公斤。問飼料應怎樣混合，才使成

本最低。

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

6月底已存貨200件，以后每月初進貨一次。假設各月份某商品買進、售出單價如表1-14

所示。問各月進貨售貨各多少，才能使總收入最多？

表1-14

月789101112

買進（元/件）282425272323

售出（元/件）292426282225

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

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

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

表1-15

飼料所含\

一^數(shù)量、^料

BiB?…Bn營需要量

營嬴

...C］八

AiCllC1241

A2C21C22***C2n

AmCmiCm2?0°Cmn

飼料單價b\歷

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

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

表1-16

每塊土地種植\

起”的產(chǎn)曉

BiBn

作物

AiC\\C12C\n

人2C21C22…C2n

?

CnlCn2…Cmn

第二章單純形方法

一'單純形表的構造

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

記A=憶，舄，…，Pn],稱A的m個線性無關的列向量構成的矩陣

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

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

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

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

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

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

稱乙為基向量，4的加個分量為基變量；而為非基向量，標的〃-加個

分量為非基變量。根據(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兩邊相加，并應用式的結論，得

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）為對應于基B的基礎解，但它不一定是可行解

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

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

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

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

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

用單純形方法求解線性規(guī)劃問題時，總是取（6）式所表達的解；求解的過

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

優(yōu)基。

不論取什么樣的解，（5）式總是成立的。由（5）式的最后一個等號可知，

解（6）對應的目標函數(shù)值為5=。理「力，且有

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

rXl

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

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

2.當CB3-A-C<0時，無論取什么樣的解尤之。都有

lXl

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

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

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

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

上所述，基礎解（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看成是一個變量，則（8）式是一個關于〃+1個變量5,毛,々,…，斗的線性

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

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

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

1CBlA-cCBlb

BB(9)

0ll

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

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

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

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

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

列構成如下的單純形表：

boo???瓦"

CB'bCB1A-cbn仇”

T(B)=BB(10)

l[

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

bmob,nlbmn

由方程組由）知,單純形表（10）對應著線性方程組

s

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

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

bx+bx+---+bx=b

2li2222nn20