第1章-线性规划模型

第一章线性规划模型

线性规划（LinearProgramming）是数学规划的•个重要组成部分，是最优化与运筹学理

论中的一个重要分支和常用的方法，是最优化理论的基础性内容。

第一节线性规划问题及其数学模型

一、问题的提出

在生产管理和经营活动中经常提出一类问题，即如何利用有限的人力、物力、财力等资源,

以便得到最好的经济效果。

例1生产计划问题

某工厂在计划期内要安排生产I、II的两种产品，已知生产单位产品所需的设备台时，A、

B两种原材料的消耗以及每件产品可获得的利润如下表所示。问应如何安排生产计划使该工厂

获利最多？

III资源限量

设备128（台时）

原材料A40I6(kg)

原材料B0412(kg)

单位产品利润（元）23

解：设司,马分别表示在计划期内生产产品I、II的产量。由于资源的限制，所以有:

机器设备的限制条件：%+2%W8

原材料A的限制条件：4玉<16（称为资源约束条件）

原材料B的限制条件：4X2<12

同时，产品I、II的产量不能是负数，所以有内之0,々20（称为变量的非负约束）。

显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的

目标是在不超过所有资源限量的条件下，如何确定产量占,占以得到最大的利润，即使目标函

数Z=2M+3±的值达到最大。

综上所述，该生产计划安排问题可用以下数学模型表示:

maxz=2x]+3x2

<8

x1+2X2

4x)<16

4^<12

X],>0

例2运输问题

某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保

证产销平衡的条件下，如何调运可使总运费最少？

\销地

价\

BlB2B3B4产量

Al5610360

A2419740

A3423860

销量30504040

解：(1)决策变量：设勺(，=1,2,3;/=1,2,3,4)为从产地，运到销地/的运量

34

(2)目标函数：息运费最小minz=

»=ij=\

(3)约束条件:

产量约束

X1+%2+工13+4=6()

x2i+x22+x234-x24=40

得+0+0+0=60

销展约束

Xu+x2l+Xj]=30

X

X12+X22+32=50

石3+啊+玉3=40

xl4+x24+芍=40

非负约束

aNO

模型为:

minz=ZZj/

f=lJ=1

X|1+X|2+%3+X|4=60

x21+x22+x23+x24=40

x3l+x32+X33+知=60

Xu+x21+x31=30

X|2+x22+Xi2=50

和+程+玉3=40

玉4+々4+0=40

x->0(z=l,2,3;j=l,2,3,4)

二、线性规划问题的模型

上述几例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大

或最小的问题。它们具有以下共同的特征。

（1）每个问题都可用一组决策变量区,々，…，当）表示某一方案，其具体的值就代表一个具体

方案。通常可根据决策变最所代表的事物特点，对变眼的取值加以约束，如非负约束。

（2）存在一组线性等式或不等式的约束条件。

（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标

函数实现最大化或最小化。

满足以卜二个条件的数学模型称为线性规划（I.P）问题的数学模型.其一般形式为：

max（或min）z=c}x]+c2x2+•••+ctlxtl

a\Kxi++…+即'与（=，2）4

alxx2+a22x2+•••+a2llxr＜（=,＞）b2

4nM2+%[/••+4nA＜（=，泅

内,当，…，％NO

或矩阵形式

max（或min）z=CX

AX＜（=＞）b

X＞0

或向量形式

max（或min）z=CX

»产户（=,之力

J=I

Xj＞0（J=1,2,...,/2）

其中C=CK2,…，C”），称为价值系数向量;

41%…4

tt2\%…%

••••••

am\am20,,am,i

称为技术系数矩阵（也称消耗系数矩阵）:b=（R也，…4）T称为资源限制向量;

X=区,占,…,X.）T称为决策变量向量。

三、建立线性规划模型的一般步骤:

（1）确定决策变量；

（2）确定目标函数；

（3）确定约束条件。

例3投资计划问题

某公司经调研分析知，在今后三年内有四种投资机会。第I种方案是在三年内每年年初投

资，年底可获利15%,并可将本金收回；第II种是在第一年的年初投资，第二年的年底可获利

45%,并将本金收回，但该项投资不得超过2万元；第IH种是在第二年的年初投资，第三年的

年底可获利65%,并将本金收回，但该项投资不得超过1.5万元；第IV种是在第三年的年初投

资，年底收回本金，且可获利35%,但该项投资不得超过1万元。现在本公司准备拿出3万元

来投资，问如何计划可使到第三年年未本利和最大？

解：问题分析.该问题的实际投资背景如下表所示：

年份一二四

1.15^)

石21.45XI2

孙1.15X21

心1.65々3

目1.15孙

%1.35X34

(1)决策变量：设%表示第i年对第j个方案的投资额，，=1,2,3;/=1,2,3,4

(2)目标函数:第三年年未的本利和为maxz=1.65^+1.15x3,+1.35%

(3)约束条件:

每一年的投资额应等于当年公司拥有的资金数:

X”+玉2=3;x21+々3=L15玉j;Xjj-t-x34=1.45XI2+1.15X21

每个方案投资额的限制:

x12<2；x23<1.5;<I

非负约束:

XjjN0,i=1,2,3;j=1,2,3,41»

例4混合配料问题

某糖果厂用原料A,B.C加工成三种不同牌号的糖果甲，乙,丙。已知各种牌号糖果中A,

B,C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表

所示。问该厂每月生产这三种牌号糖果各多少时，使该厂获利最大。试建立这个问题的线性规

划模型。

甲乙丙原料成本(元/kg)第每月限制量(kg)

A>60%>30%2.002000

B1.502500

C<20%<50%<60%1.001200

加工费（元/kg）0.500.400.30

售价（元/kg）3.402.852.25

解：（1）设决策变量勺表示生产第/种糖果（J=l,2,3表示甲，乙，丙三种糖果）耗用的第i

种原料（i=1.2.3表示A.B.C三种原料）的kg数

（2）目标函数：该厂的获利为三种牌号糖果的售价减去相应的加工费和原料成本。

maxz=(3.40-0.50)a]+x2l+x3))+(2.85-0.40)(xl2+x22+%)+(2.25-0.30)

(M3+X33)—

+x2i2.0(玉1+x12+x13)-1.50(X21+X22+X23)-1.0(X31+X32+.3)

（3）约束条件:

xn+xn+x\3-2000

.%+.5+々3«2500原料月供应量限制

+xi2+xi3<1200

%；().6(%]+孙+占1)

I+X31)

X31<().2(%]+々

222+X32)

Xl2>().3(占+工含量成分的限制

2)

xi2<().5(X12+x22+占

X333)

WO.6(X13+X23+七

与20

四、LP问题的标准形

1.标准型

为了讨论LP问题解的概念和解的性质以及对LP问题求解方便，必须把LP问题的一般形

式化为下面统一的标准型：

maxz=£qXj或maxz=CX

j=i

Z《jXj=e（i=l,2,…,〃2）（AX=b

j=\耿<

X>0

xy>0（J=l,2,...,n）-

标准型的特点：（1）目标函数是最大化类型（2）约束条件均由等式组成

（3）决策变量均为非负⑷bt>0j=1,2,•••,/??.

2.化一般形式为标准型

①目标函数：minz->max（-z）=-CX

②若约束为七”型7左边+“松驰变量”；若约束为、”型一左边一“剩余变量”

③若变量匕v。一>r户o；若变量Xj无限制一令弓=K-K

④若右边常数2<01等式两边同乘以（-1）。

例5化下述问题为标准型

minz=-X)+2x2-3x3

X1+2X2+3X3<7

-X2

J~X1+^23-~

-3X]4-x2+2x3=5

xpx3NO,当无约束

解：（1）首先考察变量：令々=乂一石，其中石,叼20；（2）在第一个约束不等式的左

端加入松弛变量%；（3）对第二个约束不等式两边同时乘以（-1）并减去剩余变量毛；（4）令

z'=-z,则原问题化为如下标准型：

maxz'=M-2（X-x；）+3x3

X1+2(犬;-x")+3x3+x4=7

x

X一(X-*)+-v3-x5=2

-3X]+(%2-x；)+2工3—5

%,芯,石,马,几,毛>0

第二节LP问题解的概念和性质

一、几个概念

1.可行解、最优解、基、基变量、基础解、基础可行解、退化解、基础最优解

设线性规划问题

maxz=CX（1-1）

AX=b

(1-2)

X>0

我们称满足约束条件（1-2）的X=（占,元2,…,X.）T为可行解。所有可行解构成可行解集，即

可行域。

使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。

设A为〃7X〃矩阵，r\A）=m,8是A中的〃?x机阶非奇异子矩阵（即|用工0）,则称6

是LP问题的一个基。

若8是LP问题的一个基，则8由m个线性无关的列向量组成，即

8=（匕，匕，…匕,），其中4…4时）丁，（，=1，2,…⑼）称为基向量。

与基向量々相对应的变量勺称为基变量，其它变量称为非基变量。显然，对应于每个基

总有机个基变量，n-m个非基变量。

设B是LP问题的一个基，令其〃-，”个非基变量均为零，所得方程AX=〃的解称为该

LP问题的一个基础解，显然，基8与基础解是一一对应的，基础解的个数KC；；。

在基础解中，称满足半负条件的基础解为基础可行解，对应的基称为可行基。

如果基础解中非零分量的个数小于〃？，则称此基础解为退化的，否则是非退化的。

加果对应于基B的基础可行解是LP问题的最优解，则称区为LP问题的最优基，相应的

解又称基础最优解，

LP问题解之间的关系如图所示：

2.凸集

若连接〃维点集S中任意两点P,/的线段仍在S内，则称S为凸集。即VX'/ES,都

有x=+(1-2)X2GS,V2G[0,1],则称S为凸集。

例如，矩形、三角形、圆、四面体等都是凸集。圆环、空心球等都不是凸集。

3.极点

若凸集S中的点x不能成为任何线段的内点，则称x为S的极点。即都有

x*Ax1+(1-2)x2G5,VZG(0,1),则称x为S的极点。

例如，矩形、三角形、四面体的顶点，圆周上的点等都是极点。

二、线性规划问题解的性质

定理1线性规划问题的可行域是凸集。

定理2可行域S中的点”是极点的充分必要条件是x为基础可行解。

定埋3LP问题最优解若存在，则必可在口」行域的极点上达到。

第三节LP问题的解法

一、两个变量LP问题的图解法

LP问题图解法的步骤：

(I)画出直角坐标系；

（2）依次做每条约束直线，标出可行域的方向，并找出它们共同的可行域；

（3）任取一目标函数值作一条FI标函数线（称等值线），根据目标函数（最大或最小）类型

移该直线即将离开可行域处，则与目标函数线接触的最终点即表示最优解“

例1：用图解法求解如下线性规划问题

maxz=4%+3x2

X

2xt+32<24

s.t.*3内+2X2<26

xpx2>0

最优解为X)=6,X2=4

最优值为maxz=36

解的几种情况：

(I)此例有唯一解Q2，即氏=6,々=4,

⑵有无穷多最优解（多重解），若将目标函数改为2=4内+6与，则线段Q2,Q3上的点

均为最优解。

（3）无界解

求max无界

但求min有唯一斜

（4）无可行解

图解法只适用于两个变量（最多含三个变量）的LP问题。

二、单纯形法

虽然线性规划问题的可行域（凸集）的顶点数目是有限的在理论上，可以通过

枚举法找出所有的基可行解，然后一一进行比较，最终找出最优解，但在实际上，当〃和加的

值较大时，这种方法是行不通的，需要用更有效、更简便的、适合于在计算机上用通用软件求

解的方法来确定最优解。单纯形法是一种既简便又有效，也适合用计算机通用软件求解线性规

划问题最优解的方法。

1.单纯形法的基本思路:

2.单纯形法的计算步骤(表格形式)

(I)建立初始单纯形表，假定3=1,520

设maxz=qX]+c2x2+•••+cnxn

%+4，川4+|+..%，/二彳

X2+a2m+lXm+l+…%/〃="2

%+W叱屈+i

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

将目标函数改写为：z-c^j-c2x2----------cnxn=0

把上述方程组和目标函数方程构成〃+1个变量，6+1个方程的方程组，并写成增广矩阵的形

式：

zxX

大2%，“十玉b

••*a•*

0100\.m+1A

001•**0a**

2.m-1・b2

*

••

**

9•*•*

0001f./nr+1*

cC•**一。%,*•C

1~\~2—1-1~n0

以非基变量表示基变量匹=瓦-£为与，i=l,2,・・・m.代入z中的基变量，有

7=m+l

z=%(瓦-1和)+ECjXj=£地-工XC4M+工中

i=li=m+\；=m+i1=1i=lj=ni-lj=ni+l

=zc£-Z(ZCiaii-Cj)xj

/■I/■1

"i_〃i

令z()=Zc£，z,=Zq%

r=lM

于是z=Zo_Z(Zj_q)Xj

j=m+l

因此，上述的增广矩阵就可写成:

5

ZX王…•••4

%一

5+i

010…0•••4”々

瓦

a•••

001…02.m+\J・

…

£

0001am/ll+.

〃】

100...0工函―

/=1

m

再令巴=2,-邑=20%-1则上述增广矩阵可写成下面表格形式：即初始单纯形表T

r=l

(B)

cj。…q”%+l…c

a

CBXBbx…4

q,瓦1---0G,向…

瓦。山…

c2X20---02””2“

••*•

**•:：::

Cmx,tn„An0---1“皿1川•••

Z(7••*cr一巴检验数行

z00…0/n+ln

上述初始单纯形表可确定初始可行基和初始基可行解:

B=(6，g,.・.，E")=/，工=(落瓦,...瓦,0,...,0"

从初始单纯形表建立的过程可以看到以下事实：

①凡LP模型中约束条件为“W”型，在化为标准型后必有8=/,如果匕20,则模型中约

束方程的各数据不改变符号照抄在表中相应的位置。目标函数中非基变量的系数则以相反数填

入检验数行各相应位置。

②在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。

③4=EcM，Oj=z厂Cj=Ec为一0（J=/〃+1,

/=11=1

（2）判别最优解

①在T（B）中，若所有的检验数％20（J=l,2,）

则8为最优基，相应的基可行解为最优解，停止计算。

②在T（B）中，若有q<0（1«火工〃），且看的系数列向量々W0,则该问题无界，停止

计算。否则转入（3）。

（3）换基迭代（基变换）

①先确定进基变量々，根据max{卜/%<0}=q来确定Z或攵=min{/卜<0},即选

择最小检验数或行从左至右选择第一个负检验数所对应的变量进基。

②按最小比值原则确定出基变量4：。=min生|。火〉0旦。

LaikJaLk

③以%K为主元，进行初等行变换（又称旋转变换），即将列向量七变换为单位歹J向量：

返回（2）。

换基迭代的关键在于将换入变量对应的列向量PK用初等行变换方法变换成单位列向量。

0

0

其中主元引《变成1。即&二-第L个分量。

如果在最终表中有非基变量的检验数为0,则该问题有多重最优解。

例2求解下列线性规划问题

maxz=4^+3x2

2x[+3X2<24

3玉+2X2<26

X],x2>0

解：引进松驰变量刍，工4,化为标准形得:

maxz=4%+3x2+()x3+()x4

2%+3X24-x,=24

3工1+2X2+x4=26

从标准形中可看出存在可行基，8=(8,6)=/,基变量为毛，匕；非基变量为内,々。建

立初始单纯形表得：

Cj4300

X"b芭“£

0与242310

0263201

Z0-4-300

由于与当的检验数均为负，且X的检验数绝对值最大，选取为为进基变量；再按最小比

^6>=min(24/2,26/3)=26/3,因此选取乙为出基变量，进行换基迭代。

Cj4300

X"bX]x2x3x4

020/305/31-2/3

4*26/312/301/3

Z104/30-1/304/3

%4300

GXRb内x2&x4

3X24013/5-2/5

4X\610-2/53/5

z36001/56/5

表中最后一行的所有检验数均为非负数，表明目标函数已达到最大值，上述表为最终表。

从表中可得到最优解为X=(x，&，七，七)=(6,4,0,0),最优值为z=36。

三、单纯形法的进一步讨论一用人工变量法求初始基可行解

1、人工变量法

若对LP模型标准化后，不具有8=/时，如何办？此时可采用人工变量法得到初始基可

行解。

所谓人工变量法是在原问题不含有初始可行基B=/的情况下，人为的对约束条件增加虚

拟的非负变量（即人工变量），构造出含有3=/的另一个LP问题后求解。当增加的人工变量

全部取值为0时，才与原问题等价。

这样，新问题将有一个初始基可行解（以人T.变最为基变显），可用单纯形法进行迭代。经

迭代后，若人工变量全部被换成非基变量，即人工变量全部出基，则得到原问题的一个基可行

解。

在最终表中若人工变量不能全部被换出，则说明原问题无可行解。

因此，该法的关键在于将人工变量全部换出。

2、大M法（通过下例简略介绍其方法与步骤）

在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影

响，为此当目标函数要实现最大时，假定人工变量的系数为（-M）,当目标函数要实现最小时,

假定人工变量的系数为M（其中M为任意大的正数）。

例3用大M法求解

minz=%+1.5工2

x,+3x2>3

<X1+x2>2

x1,x2>0

解:

minz—k+1.5K,十Ox3+0x4+Mvs十Mv6

x}+3X2-x3+x5=3

•%|+x2-x4+x6=2

X1,%2之0,工3，七>0,x5,^6>0

其中七,5为剩余变量，工,凡为人工变量，M为任意大的正数。

注意到：①分别在约束条件中增加人工变量七，玉是为了构成“人工基”

②对于Min的R标函数采用（+M）,而对于Max的目标函数则采用（-M）作为人工变

量的系数，是强加于人工变量的一种惩罚，其目的是为了强制人工变量由基变量转为非基变量，使

之恢复原问题，或与原问题等价。

③对于minz判别最优性准则应是cv-z;.<0<,

④大M法适合于计算机计算，不适用于手工求解。

所以本题求解过程略。

3、两阶段法

第一阶段：不考虑原问题是否存在基可行解；给原LP问题的约束条件加入人工变量，构

造仅含人工变量的目标函数并要求实现最小化（即使原LP问题目标函数是求最大化）的辅助

问题：

rnnw=xn+i+xn+2+---+x^m

4岛+…十即占+七“=2

生内+…+。2/“+乙.2二优

S.t.<.........

X,%xn+m20

然后用单纯形法求解上述模型。若WHO,则原问题无可行解，停止计算。若卬=0,且

所有的人工变最均为非基变量，则去掉人工变最后可得到原问题的基可行解：如果人T变软中

含有为（）的基变量时（即退化解）则可再进行初等行变换将其换出，从而获得原问题的基可行

解。

第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人_L变量列删去，同时将

人工目标函数行换为原问题的目标函数作为第二阶段计算的初始表。

例4将上例用两阶段法求解。

minz=c十1.5人2+。43+。人4min皿=A5+A6

e-、b工1+3占一占=34，、”1匹+3]，一冬+占=3

解：原问题：12勺辅助问题：1235

<X)+

-xi+x2-X4=2X2-X4+x6=2

X，%2-0,x3,x4>0[x]9x2>0,x3,x4>0,x5.x6>0

用单纯形法求解的迭代表如下:

Cj000011

GXRhZ工4%凡

1X5313-1010

1%2I10-101

w524-1-100

Cj000011

x

CBXBb玉2%&%

0x211/31-1/301/30

1几12/301/3-1-1/31

w12/301/3-1-4/30

4000011

XBb*x?%当%

0x21/201-1/21/21/2-1/2

03/2101/2-3/2-1/23/2

W00000-1-1

上述表中目标函数值卬=0,且人工变量已全部出基，得到原问题的一个可行基8=12,<）

和一个基可行解X=（X2，A）7=（1/2,3/2）『。去掉人工变量列，并将目标函数行换为原目标函

数行得：

%11/200

CBXRb不工2它乙

1.5X21/201-1/21/2

1芭3/2101/2-3/2

z9/400-1/4-3/4

上表中最后一行所有检验数均非正（因为是求极小化问题），所以上述表已是原问题的最优

表。从表中可知原问题的最优解为玉=3/2,&=1/2,最优目标函数值为z=9/4。

注意：第二阶段在填单纯形表时，检验数行的值是将原目标函数中的基变量用非基变量表

示（内=3/2-1/2七+3/2%，9=1/2+1/2七—1/25）后所得结果填入，或直接通过表中

数字关系计算而得。

例5分别用单纯形法中的大M法和两阶段法求解下述线性规划问题。

maxz=2内+3x2-5x3

x]+x2+x3=7

<2X]-5X2+>10

xpx2,x3>0

解：（1）大M法

加入人工变量，原问题可化为

maxz=2x1+3x2-5x3-Mr4+0-x5-Mv6

玉+%+工3+Z=7

<2%-5X2+-x5+x6=1（）

X1,X2,X3,A4,X5,X6>0

对此线性规划问题，用单纯性表进行计算，见下表。

Cj23-5-M0-M

%A

X

XBbXx2刍5%

-M匕71111007

-M入61012]-510-115

一z17M3MI234M2M50-M0

]_4

-Mx2011_1

412」2227

_5J_—

2X5A10,11

2222

713

-Z2M-100—M+8-M-60-M+\一一M-\

2222

4£2J_

3々0i

77777

456511

2X10

77777

10250161

-z00-M--——-M+一1

77777

454

由上表可得，此线性规划问题有唯一最优解X'=(一,二,0,0,0,0)T,目标函数最优值为

77

102

maxz=---