生物数学－线性规划

生物数学一线性规划

第一章线性规划的数学模型

一'线性规划问题的数学模型

在工农业生产、交通运输、财贸工作等各项经济活动中，必须提高经济效

益，做到耗费较少的人力物力财力，创造出较多的经济价值。

提高经济效益可以通过两种途径：一是技术方面的各种改进，例如工业生

产上改善工艺，使用新的设备和新型原材料等。二是生产组织和计划的改进，

即合理安排人力物力资源，合理组织生产过程，在条件不变的情况下，统筹安

排，使总的经济效益最好。后者就是运筹学研究的主要内容。

运筹学有规划论、排队论、对策论等许多分支。线性规划是其中的一个重

要分支。早在20世纪30年代末就有人从运输等问题开始研究它。它在运筹学

中是研究较早、发展较快、应用较广、比较成熟的一个分支。它研究的问题主

要有两类：一是一项任务确定后，如何统筹安排，尽量做到用最少的人力物力

资源去完成这一任务。二是已有一定数量的人力物力资源，如何安排使用它们,

使得完成任务最多。其实这两类问题是一个问题的两个方面，就是所谓寻求整

个问题的某个整体指标最优的问题。在经济领域里，这种问题很多。

（-）运输问题

在某一地区内，有某种产品的产地与销地各若干个，把这种产品从各个产

地调运到各个销地，调运方案可以很多，应如何调运，才能使总的运费或运输

量（即总的运行吨公里数）最少。

（-）生产的组织与计划问题

一个工厂或车间有各种不同类型的车床各若干台，各种不同车床生产各种

零件的效率不同，在一个生产周期，应如何安排个车床的生产时间，使得成套

的产品总量最大。类似的还有劳动力的安排等问题。

（三）合理下料问题

在加工中需要将某类条材或板材下不同规格的毛坯，各种毛坯的数量也可

能不同，应如何选取合适的裁法，使毛坯数量符合要求，并且使总料头最少（即

所用原材料最少）。

（四）配料问题

在食品、化工、冶炼等企业，常常用几种原料，制成达到含有一定成分的

产品，而这些不同原料价格不同，应如何决定配料的方案，才能使生产的产品

所含成分合乎要求，而产品的成本最低。

（五）布局问题

各种作物在不同土壤上单位面积产量不一样，如何合理安排各种作物在各

种土壤上的种植面积，达到因地制宜，在完成种植计划的前提下，使总产量最

多。这是作物布局问题。将某几个地方出产的原料，集中到某几个地方加工成

成品，然后再运到某几个成品需要地。有些地方可能既是原料出产地，又是产

品需要地，也是成品加工地。因各地间运费不同，成品加工费不同，设厂条件

不同，应在什么地方设厂，规模多大，才能满足成品需要地的需要，又使费用

（包括运费、加工费）最低。这是工厂布局问题。

（六）分派问题

〃件工作分派给〃人去做，每人做一件工作，而各人对做各种工作的效率不

同，问应如何合理分派，才能使完成全部工作的总工时最少。类似的问题还有

作物的种植安排、机床加工零件任务的分配问题等。

数学模型是描述实际问题共性的抽象的数学形式。对数学模型的研究，有

助于我们认识这类问题的性质和寻求它的一般解法。现在首先介绍几个典型的

实际问题。

（-）运输问题

例1设有两个砖厂4,4，其产量分别为23万块和27万块，生产的砖全

部销往片,坊,鸟三个工地。其需要量分别为17万块、18万块和15万块。自各

产地到各销地的运价如表1T。问应如何调运，才使总运费最低？

表17

自产地到销地的运价产量

销地（工地）

（万块）

与B2B3

产幕A50607023

地二&6011016027

销量（万块）171815

解设沏表示由成厂4•运往工地均糖的数量（单位：万块）（i=l,2；j=l,

2,3）,例如xii表示由糖厂4运往工地所病的数量等等。现列表如下（见表

1-2）

表1-2

工地

BiB2B3产量

AiXI1X12X1323

27

A2X21X22X23

销量17181550

砖厂4运往工地耳，与，々病的数量之和等于A,的产量；工地用接收砖厂

4,4砖的数量之和等于劣的需求量。于是有

xn+x12+x13=23

%2i+%22+%23=27

约束条件・X”+%21=17

Xn+%22=18

x13+x23=15

x..>0(z=l,2;产1,2,3)

显然，可行的调运方案很多，我们的目的是寻找运费最低的调运方案，即

求一组变量F,占2，七3，孙，122，%23的值，使其满足约束条件，并使运价函数

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

达到最小。

一般地，设某种物资有m个产地Ai,A2,……，Am；联合供应n个销地

B1,比,……，Bno各产地产量（单位：吨）、各销地销量（单位：吨）、各产

地至各销地单位运价（单位：元/吨）如表1-3所示。问应如何调运，才使总运

费最少？

表1-3

销地

产地^BiBi…Bn产量（吨）

AiC11C12•**C\na\

AiC21C22C2nai

••・•••

AmCm\Cm2"■"Cmndm

销量（吨）bi历…bn

表中：的表示产.地4的产量（1=1,2,…，m）；

历表示销地用的销量（产1,2,…，〃）；

◎表示4与4间的单位运价（元/吨）（«=1,2,•,,,m；j=l,2,,,,,

n)o

m〃

解假定产销平衡（即设殉表示由产地4-运往销地用的物

，'=1>1

资数（，=1,2,…，机；;=1,2,…，〃）。那么上述运输问题的数学模型为：

求一组变量两（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,

并使目标函数S=C\\X\\+Cl1Xn+---+CmnXmn的值最小。

利用连加号（Z）,上述模型可以写为：求一组变量沏值，使满足约束条件

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

7=1

（产地4发到各销地的发量总和等于4的产量）

m

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

i=l

（各产地发到销地鸟的发量总和等于4的销量）

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

（调运量不能为负数）

〃m

并且使目标函数s工好的值最小（总运费最少）。

尸1i=l

如果没有产销平衡这一限制，当产大于销时（即这一问题的

i=li=l

数学模型应为：求一组变量沏（，=1,2,…，m；j=l,2,…，n）的值，使它

满足约束条件

X*<4Z,.（Z

（产地4发到各销地的发量总和不超过4的产量）

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

Z=1

（各产地发到销地坊的发量总和等于4的销量）

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

（调运量不能为负数）

〃m

并且使目标函数的值最小（总运费最少）。

j=li=l

（二）布局问题

1.作物布局

某生产队要在〃块地31,&,…，B”上,种植加种作物Ai,A2,…，Amo各

块土地亩数、各种作物计划播种面积及各种作物在各块地上的亩产量（单位：

公斤）如表1-4所示，问应如何合理安排种植计划，才能使总产量最多（这里

假定即，即计划播种总面积等于土地面积）。

1=11=1

表1一4

土地

作物BiB2…Bn播种面积

AiC11C12C\na\

AiC21C22C2nai

AmCmlCm2CmnClm

土地亩数biZ?2bn

表中：的表示作物A•的播种面积（i=l,2,•••,m）；

力表示土地5•的亩数（j=l,2,…,n）；

◎表示在土地为上种植作物4的亩产量（i=l,2,…,m；7=1,2,…,

n）o

解设沏为土地为种植作物4•的亩数（z=L2,…,m；j=l,2,…,〃）,

那么作物布局问题的数学模型为：

求一组变量殉•（i=l,2,…，m；j=l,2,…，〃）的值，使它满足约束条

件

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

j=i.

（在各地块上种植作物a的总亩数等于a的计划播种数）

jn_

J=1

（在土地4上种植各种作物的总亩数等于用的面积）

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

、（种植数不能为负数）

〃m

并且使目标函数的值最大（总产量最多）。

j=l日

这一数学模型和前面运输问题的数学模型相同，具有这样数学模型的问题

还有机床加工零件的问题（见习题一第2题）等。我们称这类问题为康-希问题，

或统称为运输问题。

2.工厂布局问题

设有〃个地区Ai,Ai,An,在某一个计划期内，At生产某种原料由吨,

同时需要用这种原料加工的某种产品加吨（i=l,2,…，〃），已知左吨原料可

制造1吨该产品。设这n个地区所产原料的总数恰好能生产各地区所需该产品

的总数,即。另外已知在4•设厂加工该产品的加工费为每吨4元。

i=li=l

在A设厂生产该产品的数量最多为a吨，最少为力吨（7=1,2,…，n）。从4

运原料或产品到4;（工户1,2,•••,n）每吨为,元，问应在何地设厂、生产

多少该产品，才能既满足需要，又使生产费用（包括原料和产品运费、产品加

工费）最少？

解设沏表示由4运到4的原料数（单位：吨）（i,j=l,2,…，n）,其

中广i时，表示A留用数；为表示由4运到4的成品数（单位：吨）（i,j=l,

2,…，力,其中产z・时，表示4留用数；z,表示4设厂的年产成品数（单位：

吨）（i=l,2,,,,,〃）。它们之间的关系如表1-5所示。

表1-5

生产加

・・・生产成

AiA2An原料X

品数

数费

XIIX12Xin

力Wzi

・・・

AiC11C12C\naid\

Wei

ynyi2yin

X21X22X2n

flWzz

・・・

AiC21C22C2n6Z2di

We2

y2iy22yin

Xn\Xn2Xnn

fn^Zn

・・・

AnCnlCn2CnnClndn

yniyn2ynn

需成

bibi・・・bn

品数

需原

kzikZ2・・・kZn

料数

根据题意，得数学模型如下：

求一组变量回、yij>zi（i,j=l,2,…，n）的值，使它满足约束条件

£%=<7,.（z=1,2,•••,«）

7=1

（从A运往各地原料总数以及a的留用数等于a的原料产量）

n

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

i=l

（从各地运往&的原料总数以及4的留用数等于在A设厂所需原料数）

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

7=1

<（由人运往各地的成品总数以及人的留用数等于a的产品数）

♦为=bj（j=1,2,…,n）

i=l

（从各地运到&的成品数以及4的留用数等于4所需成品数）

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

（在4生产的成品数必须何至4之间）

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

、（调运原料数，调运成品数，生产成品数都不能为负数）

并且使目标函数8=22与（/+先）+Z"，的值最小（生产总费用最少）。

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,…那末这一问题的数学模型为：求一组变量芍（，,）=1,2,…,〃）的

值，使它满足约束条件

G=l,2,•••,«）

i=\

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

n

（z=l,2,•••,«）

j=i

（每人只做一件工作）

%=0或1（z,j=1,2,•••,«）

（每人对每件工作只有做与不做两种情况）

并且使目标函数s=产了的值最小。

*1>1

分派问题是运输问题的特例。因为变量沏只取0和1,所以又称它为0-1

规划问题。

（四）生产组织与计划问题

（1）设某车间用机床Ai,A2,,,,,A”生产由31,及，…，£这〃个不同

零件构成的机器。如果每架机器需要各种零件的数目成比例才1：42：…：4〃；

机床A生产零件均的效率（每日生产零件数）为。心问应如何分配机床负荷,

才使生产的机器最多。

解设出为机床4生产零件用的时间（单位：日）（z=l,2,j=l,2,---,n）o

这一问题的数学模型为：

n

£4=l（z

>i

（机床4生产各种零件时间总和应等1）

ZCilXil:ZCi2Xi2:“•:Z

C加X加=4：4：,•・：4

i=lz=li=l

约束条件mmm

ZQ£Ci2Xi2CinXin

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

4%24,

（各机床一天生产各种零件总数，应成已定比例）

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

（生产零件时间不能为负数）

m

>,cilxi]

并且使目标函数S=——的值最大。

4

特别地，当小：42：…：4”=1：1：…：1（即每架机器需要各种零件数目

相同）时，它的数学模型为：

求一组变量沏（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

并且使目标函数S=的值最大。

i=l

（2）设用机种原料Al,Al,,,,,Amt可以生产〃种产品31,B2,…Bn。

现有原料数、每单位产品所需原料数，及每单位产品可得利润数如表1-6所示。

问应如何组织生产才能使利润最大？

表1-6

单位\产

产品\品

所需\BiB2…Bn现有原料

原料

AiC11cn…Clna\

A2C21C22C2n02

AmCmlCm2■■,Cmndm

单位产品可得利润bibibn

解设为为生产产品用（产1,2,…，〃）的计划数。这一问题的数学模型为:

求一组变量芍（/=1,2,…的值，使它满足约束条件

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

J=I

（生产各种产品所需原料a的总数不能超过a现有数4）

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

（各种产品计划生产数不能为负数）

并且使目标函数s=的值最大（总利润最多）。

7=1

（3）某工厂用机床Al,A2,…A”加工零件31,B2,…B”在一个生产周

期，各机床只能工作的机时、工厂必须完成各零件加工数、各机床加工每个零

件的时间（单位：机时/个）和加工每个零件的成本（单位：元/个）如表1-7和

表1-8所示。问在这个生产周期，怎样安排各机床的生产任务，才能既完成加

工任务，又使总的加工成本最低。

表1-7

加工\零

每个\件

在一周期能

零件的、BiBi…Bn

工作的机时

机床

AiC11C12.…Clnai

A2C21C22"■Clnai

AmCmlCm2•,。CmnClm

必须加工零件数b\bi...bn

表1-8

加工\零

每个\件

―一零件的\BiBi…Bn

机床

Aidudn・・・d\n

Aichidn・・・d2n

::…

Amdmldm2・・・dmn

解设%为机床4•在一生产周期加工零件5•的个数（7=1,2,…,加；尸1,2,…,

〃）。这一问题的数学模型为：

求一组变量％1（7=1,2,…，m；）=1,2,…的值，使它满足约束条件

EjjXij<<2,.（z=1,2,•••,«）

j=l

（机床4加工各零件总机时不能超过4能工作机时）

_n

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

i=l

（各机床加工零件用的总数不能少于4需要数）

/20,整数"=1,2,…，%j=1,2,…,n）

（加工零件个数不能为负数、分数）

nm

并且使目标函数s=££%Xy的值最小（加工总成本最少）。

尸12

（五）合理下料问题

设用某原材料（条材或板材）下零件毛坯Ai,A2,…,4,。根据过去经验在

一件原料上有B2,…几种不同的下料方式，每种下料方式可得各种毛坯个

数及每种零件需要量如表1-9所示。问应怎样安排下料方式，使得既能满足需

要，用的原材料又最少。

表1-9

各方式\下料

下的\方式

零件\BlBl…Bn零件需要量

零件名称

AiCllC12…c\na\

AiC21C22•・・C2nai

.♦・

AmCm\Cm2CmnClm

解设用鸟种方式下料的原材料数芍，则这一问题的数学模型为:

ECa>ai(z=1,2,•••,/«)

j=i

约束条件<（所下的a零件总数不能少于生）

勺20,整数（J=1,2,

（各种方式下料的原材料数不能是负数,分数）

并且使目标函数5=£为的值最小（所用原材料量少）。

>1

（六）配料问题

设用〃种原料31,及，…3"制成具有机种成分Al,A2,…Am的产品，其

所含各成分需要量分别不低于ai,z,…，碗。各种原料的单价、各种原料所含

成分的数量如表1-10所示。问应如何配料，才使产品成本最低。

表1-10

一单位原\原

料所含成\料产品所含

分的\BiB2…Bn成分需要

量

原料所含成分茗

AiC11C12.一C\nai

AiC21C22••,C2nai

AmCmlCm2°,■CmnClm

单价bibi…bn

解设需原料均为为单位（j=l,2,-,n）o这一问题的数学模型为：

求一组变量芍0=1,2,…，”）的值，使它满足

♦

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

j=i

<（所有各种原料所含成分4的总数应不少于产品对A需要量可）

Xj20（7=1,2,…M

（所取原料不能为负数）

并且使目标函数5=之“]）的值最小（产品成本最低）。

7=1

线性规划问题数学模型的一般形式，是求一组变量玉,乙,…,X”，使其满足:

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

。2（或=%，或2%）

a2lxi+a22x2+---+a2nxn<

约束条件<....................................

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

Xj>0（j=1,2,…

并使目标函数s=GX]+c2x2+…+达到最小（或最大）。

为讨论和计算方便，作如下规定：

1.如果约束条件中第k个式子为aklxr+ak2x2+•••+aknxn<bk,则人为地

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

如果约束条件中第厂个式子为明内+的2》2+…+。”尻2b’,则人为地添加

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

通过这种方法，使所有的约束条件都变成等式。称x用，5+，为松弛变量。

2.如果问题是使目标函数5=0臼+°2%2+-一+*/达到最大，则化为使目

标函数s'=—s=-c2x2----cnxn达到最小。

3.如果某变量与没有非负限制，则引进变量X：20,x"j»6,令Xj=x[-x"j,

代入约束条件和目标函数中，化为对全部变量都有非负限制。

这样，可以把线性规划问题写成如下标准形式：

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

r

allx1+al2x2+---+alnxn=bx

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

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

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

Xj>0(j=1,2,•••,«)

C=(q,02,…，％)，则可将标准线性规划问题(1)简记为

mins=ex

Ax=b(2)

<x>0

向量与（IV/为矩阵A的第/个列向量，称为变量与对应的系数列向量。

二,几个基本概念

对于给定的实际问题，首先是要建立线性规划问题的数学模型（1）,其次

是求问题的最优解。我们不主张进行手工求解的大量训练，仅要求大家理解单

纯形方法的基本思想，具体计算通过计算机来实现。这里，先给出如下几个基

本概念。

1.如果x°=（#...引）'满足约束条件，即有Ax°=6,x°20,则称

为可行解。

2.如果可行解（向量）x°=0,或x°的非零分量对应的系数列向量线性无

关，则称x°为基础可行解。

3.使目标函数取最小值的可行解称为最优解。

4.使目标函数取最小值的基础可行解称为基础最优解。

习题一

写出下列问题的数学形式：

1.有两个煤厂A、B,每月分别进煤60吨、100吨。它们担负供应三个居民区用煤任

务。这三个居民区每月需用煤分别为45吨、75吨、40吨。A厂离这三居民区分别为10

公里、5公里、6公里，8厂离这三居民区分别为4公里、8公里、15公里。问这两煤厂如

何分配供煤，才使运输量最小。

2.某车间用机床4,A2,4加工零件和星分别为50个和70个；各机床必须加

工出零件数：Ai为40个，4为35个，4为45个；各种机床加工各种零件加工费（单位:

元/个）如表1-11所示。问如何分配这三台机床加工这两种零件的任务，才使总的加工费

最少。

表1-11

每个零件\

加工费（元/个小

Bi82

机

Ai0.40.3

A20.30.5

A30.20.2

3.设有某种原料产地4,A2,小，把这种原料经过加工，制成成品，再运往销地。

假设用4吨原料可制成1吨成品。产地4年产原料30万吨，同时需要成品7万吨。产地

人2年产原料26万吨，同时需要成品13万吨。产地4年产原料24万吨，不需成品。4与

A2间距离150公里，Al与A3间距离100公里，A2与4间距离200公里。又知原料运费为

0.3万元/万吨公里，成品运费为0.25万元/万吨公里。且知在4开设加工厂加工费为0.55

万元/万吨，在4为04万元/万吨，在4为0.3万元/万吨。因条件限制，在4设厂规模

不能超过年产成品5万吨，4和4可以不限制。问应在何地设厂，生产多少成品，才能

使生产费用（包括原料运费、成品运费、加工费等）最小。

4.某木器厂生产圆桌和衣柜两种产品。现有两种材料，第一种有72立方米，第二种有

56立方米。假设生产每种产品都需要用两种木料。生产一个圆桌和一个衣柜所需木料如表

1-12所示。每生产一个圆桌可获得润6元；生产一个衣柜可获利润10元。木器厂在现有

木料条件下，圆桌和衣柜应各生产多少，才使获得利润最多。

表12

木料（单位：立方米）

产品

第一种第二种

圆桌0.180.08

衣柜0.090.28

5.现有三种机床，生产某种产品的两种零件。产品需要这两种零件的数目相同。各

机床生产两种零件的日产量如表1-13所示。问应如何组织生产，使总产量最大。

表1-13

机床日产量'

T

BB2B3

零件jj――

Ai301518

A2204050

6.某班有男同学30人，女同学20人，星期天准备去植树。根据经验，一天男同学

平均每人挖坑20个，或栽树30棵，或给25棵树浇水，女同学平均每人挖坑10个，或栽

树20棵，或给15棵树浇水。问应怎样安排才能使植树（包括挖坑、栽树、浇水）最多。

7.某钢厂两个炼钢炉同时各用一种方法炼钢。第一种炼法每炉用a小时；第二种用b

小时（包括清炉时间）。假定这两种炼法每炉出钢都是上公斤，而炼1公斤钢的平均燃料

费第一法为,"元，第二法为〃元。若要求在c小时内炼钢公斤数不少于d,问应怎样分配

两种炼法的任务，才使燃料费用最少。

8.用长度为500厘米的条材，截成长度分别为98厘米和78厘米两种毛坯。要求共

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

少。

9.某养鸡场有1万只鸡，用动物饲料和谷类饲料混合喂养。每天每只鸡平均吃混合

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

公斤0.28元。饲料公司每周只保证供应谷类饲料50000公斤。问饲料应怎样混合，才使成

本最低。

10.某商店制订某产品7—12月进货售货计划。已知商店仓库容量不得超过500件，

6月底已存货200件，以后每月初进货一次。假设各月份某商品买进、售出单价如表1-14

所示。问各月进货售货各多少，才能使总收入最多？

表1-14

月789101112

买进（元/件）282425272323

售出（元/件）292426282225

11.设有"种饲料，各含机种营养成分。每只鸡每天需要各营养成分的数量、各种饲

料的单价，以及各种饲料所含营养成分如表1-15所示。问应如何配合饲料，才能既满足鸡

的营养需要，又使成本又最低。

表1-15

饲料所含\

一^数量、^料

BiB?…Bn营需要量

营嬴

...C］八

AiCllC1241

A2C21C22***C2n

AmCmiCm2•0°Cmn

饲料单价b\历

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

种植。其数据如表1-16所示。问应如何制订种植计划，才使总产值最多。

表1-16

每块土地种植\

起”的产晓

BiBn

作物

AiC\\C12C\n

人2C21C22…C2n

•

CnlCn2…Cmn

第二章单纯形方法

一'单纯形表的构造

仍讨论标准线性规划问题（1）。这里，假定A为行满秩矩阵，即K（A）=根。

记A=忆，舄，…，Pn],称A的m个线性无关的列向量构成的矩阵

B=\Pit，P”,…,4J为线性规划问题的的一个基。显然，基8是加阶非奇异矩

阵。一个线性规划问题可能有不止一个的基。

在理论研究部分，为讨论方便，不妨设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的加个分量为基变量；而为非基向量，标的〃-加个

分量为非基变量。根据上述讨论得到：

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），更难以是最优解。

按第一章给出的定义，若（6）是可行解，则它为基础可行解；若（6）是

最优解，则它为基础最优解。

可以证明：若线性规划问题（1）存在可行解，则一定存在（6）式所表达

的可行解；若其存在最优解，则一定存在（6）式所表达的最优解。

用单纯形方法求解线性规划问题时，总是取（6）式所表达的解；求解的过

程是不断调整基8,使解（6）成为最优解。称使解（6）为最优解的基8为最

优基。

不论取什么样的解，（5）式总是成立的。由（5）式的最后一个等号可知，

解（6）对应的目标函数值为5=。理「力，且有

1.当金5一％—c〉0时，适当取了之0可使（CBB-M—c）x〉O,从而

rXl

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

此时，（6）式表达的解不是最优解；

2.当CB3-A-C<0时，无论取什么样的解尤之。都有

lXl

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

若解（6）还满足非负约束，即XB=K42。，则其是最优解。

鉴于金氏必-。在最优解判别中的重要作用，称之为检验数或判别数。由

⑷式看出，基变量的检验数为零，非基变量的检验数表示为金"卬-。、。综

上所述，基础解（6）是最优解的充分必要条件为：

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）式容易发现：解线性规划问题（2）,实质上是

求线性方程组（8）的使变量s取最小值的解。

方程组（8）的增广矩阵为

1CBlA-cCBlb

BB(9)

0ll

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

单纯形方法要求解方程组（8）时不进行“第一行与其他行交换，第一行乘以非

零常数加到其他行”的变换，则矩阵（9）的第一列始终不变，即在第一个方程

中s的系数始终为1,其余方程中s的系数始终为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