线性模型与图解法

第二章线性规划（Linear

Programming）第一节

线性规划的模型与图解法第二节

单纯形法第三节

对偶问题与灵敏度分析第四节

问题第五节

线性整数规划第一节线性规划的模型与图解法一、线性规划问题及其数学模型在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。例1

某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。资源单耗

产品资源甲乙资源限量煤94360电45200油310300单位产品价格712线性规划模型的三要素决策变量：需决策的量，即待求的未知数；（decision

variable）目标函数：需优化的量，即欲达的目标，（objective

function）

用决策变量的表达式表示；约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示；（subject

to）决策变量：甲、乙产品的计划产量，记为

x

,

x

；决策变量：甲、乙产品的计划产量，记为

x

,

x

；目标函数：总收入，记为z,则

，追求极大化，在z

的前面冠以极大号Max；Maxz

7x1

12x2决策变量：甲、乙产品的计划产量，记为

x

,

x

；目标函数：总收入，记为z,则

，追求极大化，在z

的前面冠以极大号Max；Maxz

7x1

12x2约束条件：分别来自资源煤、电、油限量的约束，产量非负的约束。决策变量：甲、乙产品的计划产量，记为

x

,

x

；目标函数：1.总收入，记为z,则

，2.追求极大化，在z

的前面冠以极大号Max；Maxz

7x1

12x2约束条件：分别来自资源煤、电、油限量的约束，产量非负的约束。9x1

4x2

3604x1

5x2

2003x1

10x2

300x1,

x2

0s.t.x1,

x2zMaxz

7x1

12x29x1

4x2

3604x1

5x2

2003x1

10x2

300x1,

x2

0s.t.例2.某企业在生产计划中，计划生产甲、乙两种产品。这两种产品需要分别在A、B两种不同设备上加工。每件产品的工时消耗

、每种设备的生产能力、每件产品的利润如表所示：产品甲产品乙生产能力设备A设备B2111108单位利润32问题：在计划期内，如何安排生产方案，可使总利润最大？产品甲产品乙生产能力设备A设备B2111108单位利润32解：设两种产品产量为x1,x2,总收入为Z

，则模型为：s.t.max

z

3x1

2x2

1

2x1

x2

≤8x

,

x

≥

0最大化设备A台时占用

2x1

x2

≤10设备B台时占用生产能力,不允许超过产量非负决策变量（decision

variable）目标函数（objective

function）约束条件（subject

to）总利润表三达要式素线性规划模型的一个基本特点：11x3x2

、2

ln

x

、2练习：某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2)，求建造方案。解:设今年计划修建砖混、壁板、大模住宅各为x1,x2,x3

m2,z为总面积,则本问题的数学模型为:0.210

x1

147000s.t

2

000..0.00xx03

x044003050Maxz

x1x2

x312000..1.1xx03

x1315120500012000..0.0xx13

x0322020005012000..1.1xx13

x1910580000123xxx

,0,1前

的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。线性规划模型的一般形式：目标函数：约束条件：决策变量：x1,

x2，

,

xn则模型可表示为模型一般式的矩阵形式：记mX

(x1,A

(aij

)mn

,

b

(b1,

,AX

bs.t.X

0Maxz

CX称X

为决策变量向量，C

称为价格系数向量,

A

称为技术系数矩阵,

b

称为资源限制向量。回顾例1的模型回顾例1的模型其中表示决策变量的向量；表示产品的价格向量；表示资源限制向量；表示产品对资源的单耗系数矩阵。X

(x

,

x

)T1

2C

(7,12)b

(360,200,300)T

9 4

10

3A

4 5

二、线性规划模型的图解法图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。1.图解法的步骤（1）做约束的图形先做非负约束的图形；再做资源约束的图形。以例1为例，其约束为9x1

4x2

3604x1

5x2

2003x1

10x2

300x1,

x2

0s.t0x1x2不等式的几何意义是什么？怎样做图？半平面，可用代入点的方法（如把原点（0，0）代入不等式，满足，说明原点所在的半平面即该不等式所表示的区域）。1

2如9x

4x

360，它表示以9x

4x

360为边界的1

2

1

2一个半平面。因此，它的做图方法是：先做直线9x

4x

360,

用两点连线方法（令1

2x

0,则x

90,再令x

0,则x

40,于是该直线过1

2

2

1点（0，90）、（40，0））；再确定不等式9x

4x

360表示上述直线的哪（1）做约束的图形先做非负约束的图形；再做资源约束的图形。以例1为例，其约束为s.t9x1

4x2

3604x1

5x2

2003x1

10x2

300x1,

x2

0各约束的公共部分即模型的约束，称可行域。0x1x29040

5010030401.图解法的步骤（2）做目标的图形0x1x2对于目标函数z

c

x

c

x1

1

n

n任给z二不同的值，便可做出相应的二直线，用虚线表示。1

2以例1为例，其目标为

z

7x

12x

，分别令z

84和z

168，做出相应的二直线，便可看出z增大的方向。7121424（3）求出最优解将目标直线向使目标z优化的方向移，直至可行域的边界为止，这时其与可行域的“切”点即最X优*

解。如在例1中，X

*

是可行域的一个顶点，经求解交出X

*

的二约束直线联立的方程可解得

(20,24)TX

*0x1x29040

501003040X

*由图解法的结果得到例1的最优解X

*

(20,24)，T将其代入目标函数求得相应的最优目标值z

*说明当甲产量安排20个单位，乙产量安排24个单位时，可获得最大的收入428。

428可行域2x11

2

1

2ms.t.

x

x

x

,

x

≥

0ox1x2令3x1+2x2=Z10x1+x2=884

586(2,6)

z=3×2+2×6=18最优解：x1=2,x2=6最优值：z=182x1+x2=10问题：在上两例中线性规划的可行域是一个什么形状？——

多边形，而且是“凸”形的多边形。最优解在什么位置获得？——在边界，而且是在某个顶点获得。2.

由图解法得到线性规划解的一些特性（1）线性规划的约束集（即可行域）是一个凸多面体。凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：凸集中的“极点”，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。（2）线性规划的最优解（若存在的话）必能在可行域的角点获得。因为，由图解法可知，只有当目标直线平移到边界时，才能使目标z

达到最大限度的优化。问题：本性质有何重要意义？它使得在可行域中寻优的工作由“无限”上升为“有限”，从而为线性规划的算法设计提供了重要基础。（3）线性