线性规划

发布时间：2023-06-09 作者：admin 来源：文学

线性规划

2023年2月28日发(作者：守护明天观后感)

线性规划及单纯形法

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

两个变量问题的图解法

单纯形法原理

单纯形法计算步骤

人工变量及其处理方法

应用举例

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

一、问题的提出

资源有限和目标确定

在生产管理和经营活动中，经常会遇到两类问题：一类是（资源有限）

如何合理的使用现有的劳动力、设备、资金等资源，以得到最大的效益；

另一类是（目标一定）为了达到一定的目标，应如何组织生产，或合理安

排工艺流程，或调整产品的成分等，以使所消耗的资源（人力、设备台时、

资金、原材料等）为最少。

例：

(1)配载问题：某种交通工具（车、船、飞机等）的容积和载重量一定，运

输几种物资，这些物资有不同的体积和重量，如何装载可以使这种运输工

具所装运的物资最多？

(2)下料问题：某厂使用某种圆钢下料，制造直径相同而长度不等的三种机

轴，采用什么样的下料方案可以使余料为最少？

(3)物资调运：某种产品有几个产地和销地，物资部门应太如何合理组织调

运，从而既满足销地需要，又不使某个产地物资过分积压，同时还使运输

费用最省？

(4)营养问题：各种食品所含营养成分各不相同，价格也不相等，食堂应该

如何安排伙食才能既满足人体对各种营养成分得需要，同时又使消费者得

经济负担最少？

此外，在地质勘探、环境保护„„等方面也都有与上述情况类似的问

题。

例1某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。

生产每吨药品所需要的维生素量分别为30Kg，20Kg，所占设备时间

分别为5台班，1台班，该厂每周所能得到的维生素量为160kg，每周

设备最多能开15个台班。且根据市场需求，甲种产品每周产量不应超

过4t。已知该厂生产每吨甲、乙两种产品的利润分别为5万元及2万元。

问该厂应如何安排两种产品的产量才能使每周获得的利润最大？

每吨产品的消耗

每周资源总量

甲乙

维生素/kg

3020160

设备/台班

5115

解：设该厂每周安排生产甲、乙两种药品的产量分别为x

吨，则有



















155

1623

25max

xxz

例2喜糖问题

设市场上有甲级糖和乙级糖，单价分别为20元/斤，10元/斤。今要筹办一

桩婚事，筹备小组计划怎样花费不超过200元，使糖的总斤数不少于10斤，

甲级糖不少于5斤。问如何确定采购方案，使糖的总斤数最大。

解：设采购甲、乙两种糖各x

斤

则





















2001020

max

xxz

二、线性规划问题的数学模型

1.从上述两个例子可以看出，它们有3个共同点

(1)每个问题都有一组变量——称为决策变量

(2)都有一个关于决策变量的函数

(3)每个问题都有一组决策变量需满足的约束条件

2.线性规划问题定义：将约束条件及目标函数都是决策变量的线性函数的

规划问题称为线性规划问题。

3.建立线性规划问题的数学模型步骤

(1)确定问题的决策变量

(2)确定问题的目标，并表示为决策变量的线性函数

(3)找出问题的所有约束条件，并表示为决策变量的线性方程或不等式

4.线性规划的数学模型

假定线性规划问题中含n个变量，分别用x

(j=1,…,n)表示，在目标函数

中，x

的系数为c

(通常称为价值系数)。x

的取值受m项资源的限制，用

(i=1,…,m)表示第i种资源的拥有量，用a

表示变量x

的取值为一个单位时

所消耗或含有的第i种资源的数量(通常称为技术系数或工艺系数)。则上述

线性规划问题的数学模型可以表示为





















),,1(0

),(

max(min)

2211

22222121

11212111

2211

njx

bxaxaxa

xcxcxcz

mnmnmm

5.线性规划的标准型

由于目标函数和约束条件内容和形式上的差别，线性规划问题有多种

表达式，为了便于讨论和制定统一的算法，规定标准形式如下：(1)目标函

数极大化；(2)约束条件为等式且右端项≥0；(3)决策变量≥0。

(1)一般表达式

（2）Σ记号简写式

（3）矩阵形式

式中C=(c

,…,c

)X=(x

,….x

)’

(4)向量形式





















),,1(0

max

2211

22222121

11212111

2211

njx

bxaxaxa

xcxcxcz

mnmnmm





















),...,2,1(0

),...,2,1(

max

njx

mibxa

xcz

ijij











max

bAX

CXz











































...

............

...

22221

11211

aaa

mnmm



















max

bxp

CXz

式中C,X,b,0的含义与矩阵表达式相同，而

=[a

,…a

](j=1,2,…,n)

即A=(p

,…p

)

6将非标准形式化为标准形式（5种情况）

(1)目标函数为求极小值

minZ=CX,则作Z’=-CX,即maxZ’=-CX

(2)右端项小于0

只需将两端同乘(-1)，不等号改变方向，然后再将不等式改为等式。

例2x

≥－6，－2x

－x

≤6，－2x

－x

＋x

＝6

(3)约束条件为不等式

当约束条件为“≤”时，则在左边加上一个新变量——称为松弛变量，将

不等式改为等式。如x

－2x

≤8，x

－2x

＋x

＝8，x

≥0；

当约束条件为“≥”时，则在不等式左边减去一个新变量——称为松弛变

量，将不等式改为等式。如x

－2x

≥8，x

－2x

－x

＝8，x

≥0；

(4)取值无约束的变量

即可正可负，则可引入两个新变量，x’，x”，令x=x’-x”，其中x’≥0，x”

≥0，将其代入线性规划模型即可。

(5)X≤0的情况

令x’＝－x，显然x’≥0。

例将下列线性规划模型化为标准形式

解：令Z’=-Z=-x

+2x

-3x

-x

第一个约束条件左边加上松弛变量

x6，第二个左边减去剩余变量x7，第三个两边同乘(-1)，则得到标准形式

练习

练习答案





















无约束

321

6324

423

32min

xxx

xxxz





















无约束

321

523

32min

xxx

xxxz























523

00)(32'max

321

75421

65421

765421

xxx

xxxxx

xxxxxxz























6''3'32'4

4''22'3

9''''2

''3'32''max

3321

53321

43321

3321

xxxx

xxxxx

xxxxz

三、两个变量问题的图解法

图解法简单直观，对于两个变量的线性规划问题，可以通过在平面上

作图的方法求解。而且可以从中得到有关线性规划问题的许多重要结论，

有助于我们理解线性规划问题求解方法的基本原理。

1.图解法的基本步骤

(1)建立坐标系

(2)图示约束条件，找出可行域

(3)图示目标函数，寻找最优解

例用图解法求解下列线性规划问题

本例中目标函数与凸多边形的切点是B(2,5)，则X*=(2,5)为最优解，

maxZ=20

2.线性规划问题的几种可能结果

(1)有唯一最优解(如上例所示)

(2)有无穷多最优解



















155

1623

25max

xxz



















42min

xxz

(3)无界解(无最优解)

(4)无可行解

3.由图解法得到的启示

图解法虽然只能用来求解只具有两个变量的线性规划问题，但它的解

题思路和几何上直观得到的一些概念判断，对将要学习的单纯形法有很大

启示：

(1)求解线性规划问题时，解的情况有：唯一最优解；无穷多最优解；无界

解；无可行解。

(2)若线性规划问题的可行域存在，则可行域是一个凸集，顶点个数只有有

限个。

(3)若可行域非空且有界则必有最优解，若可行域无界，则可能有最优解，

也可能无最优解。

(4)若最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶



















max

xxz





















42max

xxz

点。

针对以上四个启示，得到新的解题思路（为单纯形法做铺垫）：

先找出凸集的任一顶点，计算顶点处的目标函数值。比较周围相邻顶

点的目标函数值是否比这个大，如果为否，则该顶点就是最优解的点或最

优解的点之一，否则转到比这个点的目标函数值大的另一顶点，重复上述

过程，直到找到最优解。

四、有关线性规划问题的解的概念

数学模型

(1)可行解与可行域：满足(2),(3)的解，称为线性规划问题的可行解，所有

可行解的集合称为可行域。

(2)最优解：使目标函数值达到最优，即满足(1)式的可行解称为最优解。

(3)基：设线性规划约束方程组中的系数矩阵A

m×n

的秩为m(m＜n)，则A中

任一个m阶可逆矩阵B称为线性规划问题的一个基矩阵，简称为基。

(4)基(基本)解：取A中一个基B=(p

,…p

)，对应的基变量为(x

,…x

)，

当基变量取值均为0，且满足约束条件(2)的一个解X，称为是关于基B的一

个基本解。

对于A中每一个基B，只能找出一个基本解X，而A中最多有C

m个

基，因此线性规划问题最多只有个C

m个基本解。

(5)基可行解：满足非负约束(3)的基本界称为基本可行解。

)3(

)2(

)1(





















),...,2,1(0

),...,2,1(

max

njx

mibxa

xcz

ijij

(6)可行基：对应于基可行解的基称为可行基。

例找出下列线性规划问题的全部基解，基可行解，并找出最优解

解：化为标准形式：

练习找出下列线性规划问题的全部基解，基可行解，并找出最优解

基本解：X

=(0,1,4,12,18)’X

=(4,0,0,12,6)’X

=(6,0,-2,12,0)’X

=(4,3,0,6,0)’

=(0,6,4,0,6)’X

=(2,6,2,0,0)’X

=((4,6,0,0,-6)’X

=(0,9,4,-6,0)’

其中基本可行解为：X

，X

最优解为X*＝X

=(2,6,2,0,0)’Z*=36



















max

xxz





















1823

53max

xxz

线性规划问题的几何意义

从两个变量线性规划问题的图解法得到以下两点：(1)LP问题的可行域

是一个有界或无界的凸多边形，其顶点个数是有限个；(2)若LP问题有最优

解，则其最优解必可在某顶点上达到。对于多变量的LP问题也有类似的结

论。.

一、基本概念

凸集：对简单的几何形体可以直观地判断其凹凸性，但在高位空间，只能

给出点集解析表达式，因此只能用数学解析式判断。

如果集合C中任意两个点X

，X

，其连线上的所有点

)1(XaaX

(0＜a＜1)也都是集合C中的点，称C为凸集。

凸组合：设X

,……X

是n维欧氏空间Rn中的k个点，若存在实数μ

,μ

,……,μ

,(0≤μ

≤1)，i=1,2,……,k；





，使

xxxX...

2211

则称X为X

,……X

的凸组合。

极点（顶点）：设K是凸集，X∈K；若X不能表示为S中任意两个不同点X

的一个严格凸组合。则称X为S中的一个极点。

若X为S中的一个顶点，且有X=

)1(XaaX

（0＜a＜1，X

∈S,则必有X=X

，如五边形的每个顶点都是极点，而圆域边界上任一

点都是极点。

二、基本定理

定理1：若线性规划问题存在可行域，则问题的可行域是凸集。

引理：线性规划的可行解X＝(x1,…xn)为可行解的充要条件是X的正分量所

对应的系数列向量是线性独立的。

定理2：线性规划问题的基可行解X对应线性规划问题可行域(凸集)的顶点。

引理2：若K是有界凸集，则任何一点X∈K可表示为K的顶点的凸组合。

定理3：若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶

点上达到最优。

单纯形法迭代原理

一、基本思路

枚举法：若LP问题有最优解，则必可在某个顶点上达到，即在某个基可行

解上取得最优解。因此，对LP问题，把所有基可行解都找出来，然后逐个

进行比较，求出最优解。基本可行解的个数≤C

m个，若m,n取值都很小还

可以列出来，但如果m,n很大时，例如m=20,n=40时，C

m≈1.3×1011，显然

行不通。

逐步改善法：对于LP问题，先找出一个基可行解，判断其是否为最优解，

如为否，则寻求一个更好的基可行解，一直找到最优解为止，但这种逐步

改善的求解方法需要解决以下三个问题：

（1）如何判别当前的基本可行解是否已达到了最优解

（2）若当前解不是最优解，如何去寻找一个比当前解更好的基可行解

（3）如何得到一个初始的基可行解

例求解下列线性规划问题的最优解

解：化为标准形式



















155

1602030

25max

xxz

第一步：确定一个初始基可行解；基可行解就是满足非负条件的基本解，

因此要在约束矩阵A中找出一个可逆的基矩阵。















10001

01015

0012030

这里m=3，3阶可逆方阵，可以看出x

的系数列向量是线性独立的，

这些向量构成一个基

),,(

100

010

001

543

)0(pppB















，对应的基变量为x

，x

为非基变量。

将基变量用非基变量表示，由(2)得：

=160-30x

-20x

=15-5x

-x

=4-x

将(3)代入目标函数得Z=5x1+2x2+0

令非基变量x1=x2=0,代入(3),得到一个基可行解X(0)

X(0)=(0,0,160,15,4)

第二步：从当前基可行解转换为更好的基可行解；





















155

1602030

00025max

421

321

54321

xxx

xxxxxz

从数学角度看，x

的增加将会增加目标函数值，从目标函数值中x

前的系数看，x

前的系数大于x

前的系数，所以让x

从非基变量转为基变

量，称为进基变量，怎样确定离基变量：

因为x

仍为非基变量，故x

则(3)式变为

=160-30x

160/30=16/3

=15-5x

15/5=3

=4-x

4/1=4

min=3，所以当x

=3时，x

第一个减少到0，所以x

出基

则X(1)=(3,0,70,0,1)

),,(

531

)1(pppB

Z(1)=15

此时非基变量为x

,用非基变量表示基变量，代入(3)

=70-14x

+6x

=3-1/5x

-1/5x

=1+1/5x

+1/5x

将(4)代入目标函数得Z=15+x

-x

第三步：继续迭代

进基，x

仍为非基变量，令x

=0，则(4)式表示为

x3=70-14x270/14＝5

x1=3-1/5x23/(1/5)＝15

x5=1+1/5x2

min=5，所以当x

=5时，x

首先减少到0，所以x

出基

则X(2)=(2,5,0,0,2)

),,(

521

)2(pppB

Z(2)=20

此时非基变量为x

,用非基变量表示基变量，代入(4)

=5-1/14x

+3/7x

=2+1/70x

-2/7x

=2-1/70x

+2/7x

将(5)代入目标函数得Z=20-1/14x

-4/7x

此时若非基变量x

的值增加，只能使Z值下降

所以X(2)为最优解，Z*=20,X*=(2,5,0,0,2)’

单纯形法计算步骤

第1步：将LP数学模型标准化，构造一个初始基可行解

对已经标准化的线性规划模型，设法在约束矩阵A

m×n

中构造出一个m

阶单位阵作为初始可行基，相应就有一个初始基本可行解。

第2步：判断当前基本可行解是否为最优解

用非基变量表示基变量及目标函数的表示式。在目标函数的表示式中，

若至少有一个非基变量前的系数（检验数）为正数，则当前解不是最优解，

反之，则是（最大化问题）。即对于最大化问题，当所有的检验数都≤0

时，当前解即为最优解。

第3步：若当前解不是最优解，则要进行基变换迭代到下一个基本可行解。

(1)进基变量：目标函数表示式中，最大正检验数所属的非基变量

(2)出基变量：最小比值原则

(3基变换：得到新的基可行解

1．单纯形表

例用单纯形法解上例中的线性规划问题

解：第1步：将LP数学模型标准化，构造一个初始基可行解



















155

1602030

25max

xxz

当线性规划的约束条件为≤号时，在每个约束条件的左端加上一个松

弛变量。

对约束条件为≥或＝的情况，为便于找到初始基可行解，可以构造人

工基，即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人

工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩

阵。

反映到表上

52000

160

-Z-5-2000

第2步：判断当前基本可行解是否为最优解

根据上节课讲的，将基变量用非基变量表示，判断检验数。

为了书写上的便利及总结规律，我们将所得到的标准形式中的变量次

序重新整理及编号：让基变量排在前m个变量的位置上。这对所讨论的结

果没有影响。这样可得到以下的模型形式：

s.t:

111111

...,bxaxax

nnmm





221122

...,bxaxax

nnmm

























155

1602030

00025max

421

321

54321

xxx

xxxxxz





xcz

max

……………………………

mnmnmmmm

bxaxax



...,'

),...,2,1(0njxj

这里，基变量为x

,…,x

,令非基变量x

m+1

m+2

=…=x

则X

=(b

,…,b

,0,0,…,0)’

一般情况下，经过若干次迭代后的当前解，其基变量用非基变量表示

的典式的一般形式为

nnmm

xaxabx'...,''

111111





nnmm

xaxabx'...,''

211222





……………………………

nnmmmmm

xamxabx'...,''

111





或简记为),...,2,1(''

mixabx

jij





将其代入目标函数中，得到目标函数用非基变量表示的典式：

Z





jjjj

xcxc







jjii

xcxc







jjj

iii

xcxabc

111

)''(







jjj

xcxacbc

1111







jjj

xcxacbc

1111







ijijii

xaccbc

111

)'('

记



bcZ

，



iij

acz

，(j=m+1,…,n)

则有





jjj

xzcZZ

)(

iijj

zcacc

1

'

得



xZZ



这就是目标函数用当前解得非基变量表示的典式。

i=1——m是基变量的下标j=m+1…….n是非基变量的下标

Ci是基变量的价值系数，Cj是非基变量的价值系数

σj就是非基变量xj的检验数

反映到单纯形表中则为

…C

m+1

m+2

…C

…x

m+1

m+2

…x

…

1,m+1

2,m+1

…

m,m+1

1,m+

2,m+

…

m,m+

…

-Z-Z

00..0

-σ

m+1

-σ

m+2

…

-σ

)(ZxzcZ

jjj











bcZ

iijj

zcacc

1



1．最优解判别定理：若关于非基变量的所有检验数≤0，则当前基本可行

解就是最优解。

2．无穷多最优解判别定理：若关于非基变量的所有检验数≤0，又存在某

个非基变量的检验数＝0，则线性规划问题有无穷多最优解。

3．无界解：如果某个σ

＞0,而x

对应的系数列向量P

中，所有的

,…,a

都≤0，则该线性规划问题有无界解。（以后讲）

第3步：基变换，求改善的基可行解，列出新的单纯形表

(1)进基变量：上节课讲的，目标函数的典式中最大正检验数(非基变量前的

系数)所对应的非基变量。

记}0max{＞

jjk



(2)离基变量：

maxZ=5x

+2x

进基，令x

=0x

=160-30x

160/30=16/3

=15-5x

15/5=3

=4-x

4/1=4

离基变量选择原则

(3)基变换：用x

替换基变量中的x

，得到新的基可行解。并得到新的单纯

形表。以主元素所在行为基准进行行变换。

主元素：主行和主列交叉处的元素称为主元素。

52000

160

[5]

16/3

15/5

4/1

-Z0-5-2000

[14]

1/5

-1/5

-6

1/5

-1/5

-Z-150-1010

1/14

-1/70

1/70

-3/7

2/7

-2/7

-Z-20001/44/70

}0min{

Z*=20,X*=(2,5,0,0,2)’

用单纯形表解题步骤：

(1)将LP数学模型标准化

(2)列出初始单纯形表，计算σ

(3)若所有的σ

≤0，则此时的基可行解为最优解，计算停止，否则转(4)

(4)选择最大正检验数所对应的非基变量进基，}0max{＞

jjk



(5)计算x

对应的系数列向量，若P

≤0，则计算停止，问题有无界解，否则

(6)求最小比值

确定x

为出基变量

(7)修改单纯形表，得到新的基可行解，转(3)

例1用单纯形法解线性规划问题(唯一解)

解：化为标准型

}0min{



















2426

155

2max

xxz

列出单纯形表

21000

[6]

-Z0-2-1000

1/3

[2/3]

1/6

-1/6

3/2

-Z-80-1/301/30

15/2

7/2

3/2

5/4

1/4

-1/4

-15/2

-1/2

3/2

-Z-200001/41/2

Z*=17/2,X*=(7/2,3/2,15/2,0,0)’

例2(无界解)

11000

[1]

-2



















max

xxz





















2426

155

0002max

521

421

54321

xxx

xxxxxz

4-11001

-Z0-1-1000

-2

-3

-1

-Z-20-3100

把表格还原为线性方程

















623

23max

532

432

321

xxx

xxz













325

324

321

236

xxx

令x













此时，若让x

进基，则会和基变量x

同时增加，使目标函数值无限增长，

所以本题无界

例3(无穷多解)

24000

8121004



















42max

xxz

[1]

-Z0-2-4000

[1]

-2

-Z-12-20004

-1

-2

-Z-1600200

-1/2

1/2

-1/2

-Z-1600200

Z*=16,X*=(2,3,0,2,0)’

Z*=16,X*=(4,2,0,0,1)’

练习

解：列表如下

35000

[2]

-Z035000

[3]

1/2

-1



















1823

122

53max

xxz

-Z-30300-5/20

1/3

1/2

-1/3

1/3

-Z-20000-3/2-1

X*=(2,6,6,0,0)’Z*=36

例下表是用单纯形法计算时某一表格，已知该线性规划的目标函数为

maxz=5x

+3x

，约束形式为≤，x

，x

为松弛变量，当前目标函数值为10：

1/5

-Zb-1fg

(1)计算A----G的值(2)表中解是否为最优解

练习

下表是用单纯形法计算时某一表格，已知目标函数为maxZ=28x

+2x

，

约束形式为≤，x

，x

为松弛变量，当前目标函数值为14：

(1)计算a----g的值(2)表中解是否为最优解

-14/3

5/2

-Zbc00-1g

（1）7，－6，0，1，0，1/3，0

（2）表中解是最优解

👁️ 阅读量：0

🔖 本文标签：

🔥 最新发布文章