线性规划数学模型

章线性规划（LinearProgramming）

线性规划问题是目标函数和约束条件均为线性的最优化问题。自从1947年丹捷格(Dantzig)提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛，已成为现代管理中经常采用的基本方法之一。线性规划是最优化问题中的重要领域之一，很多运筹学中的实际问题都可以用线性规划来表述。很多其他种类的最优化问题算法也都可以分拆成线性规划子问题，然后求解。通过学习本章，应当了解线性规划的有关概念，掌握线性规划模型的建立及优化方法，会用计算机对大型线性规划模型问题进行求解和分析。本章的难点为单纯形计算方法。2021/5/91第一节线性规划问题的提出线性规划是运筹学的一个重要分支，主要用于研究解决有限资源的最佳分配问题，即如何对有限资源做出最佳方式的调配和最有利的使用，以便最充分地发挥资源的效能，以获取最佳经济效益。它的适用领域非常广泛，从工业、农业、商业、交通运输业、军事的计划和管理及决策到整个国民经济计划的最优方案的提出，都有它的用武之地，是现代管理科学的重要基础和手段之一。2021/5/92第一节线性规划问题的提出线性规划研究的问题主要有以下两类。(1) 给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源完成最大任务。（如资金、设备、原标材料、人工、时间等）(2) 给定一项任务，如何运筹规划，合理安排，以最少资源来完成它。（如产品量最多、利润最大.）线性规划要研究的两类问题中都有一个限制条件：第一类问题是给出一定量的人力、物力和财力等资源；第二类问题是给定一项任务。2021/5/93第二节线性规划问题的数学模型当用线性规划的方法对实际问题进行优化时，必须把这个实际问题用恰当的数学形式表达出来，这个表达的过程，就是建立数学模型的过程。数学模型的建立需要经验和技巧以及有关的专业知识，只有通过大量的实践，在建立模型时才能得心应手。初学时可从题目中所给出的限制条件和目标入手，由限制条件建立起线性方程组，由目标得到目标函数。下面，结合若干个实际问题讨论数学模型的建立。2021/5/94一、投资问题的数学模型解（参见教材P15）2021/5/95二、配料问题的数学模型解（参见教材P16）2021/5/96二、配料问题的数学模型

某化工厂要用三种原料

A，B，C

混合配制三种不同规格的产品

X，Y，Z。有关数据如下：产品规格单价(元/kg)X原料D不少于50%原料P不超过25%50Y原料D不少于25%原料P不超过50%35Z不限25原料最大供量(kg/天)单价(元/kg)A10065B10025C6035应如合配制，才能使利润达到最大？表2-3表2-42021/5/97二、配料问题的数学模型一、决策变量

设以

xij表示每天生产的第i

种产品中所含第j

种原料的数量(kg，右表)。ji

A

B

CXYZx11x12x13x21x22x23x31x32x33二、约束条件⑴规格约束(据表2-3)x11+

x12+

x13x11≥

0.50x11+

x12+

x13x12≤

0.25x11+

x12+

x13x21≥

0.25x11+

x12+

x13x22≤

0.502021/5/98二、配料问题的数学模型改写成

-

x11+

x12

+

x13≤

0-

x11+3

x12-x13≤

0-3

x21

+x22+

x23≤

0

x21+x22-

x23≤

0⑵资源约束(据表2-4)x11+

x21

+

x31≤

100x12+

x22+

x32≤

100x13+

x23

+

x33≤

602021/5/99二、配料问题的数学模型三、目标函数⑴总产值(据表2-3)产品X的产值:50(x11+

x12+

x13)产品Y的产值:35(x21+

x22+

x23)产品Z的产值:25(x31+

x32+

x33)以上三项之和即总产值。⑵总成本(据表2-4)原料A的成本:65(x11+

x21+

x31)原料B的成本:25(x12+

x22+

x32)原料C的成本:35(x13+

x23+

x33)以上三项之和即总成本。2021/5/910二、配料问题的数学模型

目标函数为：

总利润

=总产值-

总成本max

z=-15x11+25x12+15x13-30x21+10x22-40x31-10x33该问题的数学模型为:s.t.

-x11

+x12+

x13

≤0-x11+3x12-

x13

≤0

-3x21+x22

+x23

≤0x21+x22-

x23≤0x11+x21+x31≤100x12+x22

+x32≤100x13

+x23+x33

≤60

xij≥

0，i=1,2,3；j=1,2,32021/5/911配料问题练习：某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有A，B，C三种化学成分，其含量(%)是:甲为12，2，

3；乙为3，3，15。按合同规定，产品中三种化学成分的含量(%)不得低于4，2，5。甲、乙原料成本为每千克3，2元。厂方希望总成本达到最小，则应如何配制该产品？2021/5/912配料问题

成分含量(%)

原

料

化学成分

甲

乙

产品成分

最低含量(%)A

B

C

12

3

2

3

3

15

4

2

5

成本（元/千克）

3

2

x1x2min

z

=3x1+2x212x1

+3x2≥42x1

+3x2≥2s.t.

3x1+15x2≥5

x1

+x2

=

1

x1

,

x2≥0配料平衡条件z2021/5/913三、人力资源问题的数学模型解（参见教材P17）2021/5/914三、人力资源问题的数学模型练习：

某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：班次时间所需人员16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?2021/5/915三、人力资源问题的数学模型解：设xi表示第i班次时开始上班的司机和乘务人员人数。此问题最优解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司机和乘务员150人。2021/5/916四、合理下料问题的数学模型合理下料问题是机械工业常遇到的问题。毛坯车间经常要在长度一定的条形材料或面积一定的板材上切割若干个具有一定形状、尺寸的毛坯。在一般情况下，材料不可能被完全利用，会有边角余料，造成浪费。因此，如何最大限度地减少边角余料，提高材料利用率，使得切割规定数量的毛坯所用材料最少就是合理下料问题所要研究的。例2-5某车间有一批长度为180cm的钢管(数量充分多)，为了制造零件的需要，要将其截成三种不同长度的管料：70cm、52cm、35cm。规定这三种管料的需要量分别不少于100根、150根和100根。问：应如何下料能使消耗的钢管数量最少？解（参见教材P18）2021/5/917四、合理下料问题的数学模型练习：

制造某种机床，需要

A,B,C三种轴件，其规格与数量如表所示，各类轴件都用5.5米长的同一种圆钢下料。若计划生产100台机床，最少需要用多少根圆钢？2021/5/918四、合理下料问题的数学模型轴类

规格：长度（米）

每台机床所需轴件数

A

3.1

1

B

2.1

2

C

1.2

4

余料δj<1.2找出全部省料截法一根圆钢所截各类轴件数

截法轴类

轴

件

需要量

A(3.1)

100

B(2.1)

200

C(1.2)

400

余料(米)

234511100.310200210.1

0

0

1

0

2

4

1

0.72021/5/919四、合理下料问题的数学模型min

z=

x1

+

x2

+

x3

+

x4

+

x5s.t.x1

+x2

≥100x1

+2x3

+x4

≥2002x2

+x3

+2x4

+4x5

≥400x1，x2

，x3，x4，x5

≥

0则该问题的数学模型为:设第j

种截法下料

xj

根。2021/5/920四、合理下料问题的数学模型例：现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出4种下料方案以供套裁用。ⅠⅡⅢⅣ2.5m32101.3m0246料头00.40.30.22021/5/921四、合理下料问题的数学模型设按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根数分别为xj(j=1，2,3,4)，可列出下面的数学模型：2021/5/922五、运输问题的数学模型问题的提出：某类产品有若干个产地，已知每个生产地的产量；这类产品有若干个消费地，已知每个消费地的需要量。假设总的产量等于总的需要量。问题是如何编制一个最优的运输计划，使从产地到消费地的运输费用最小。解（参见教材P20）2021/5/923六、产品配比问题的数学模型例

某厂拟生产甲、乙两种产品，每件利润分别为3、5百元。甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、乙产品的部件分别需要A、B车间的生产能力1、2工时。两件产品的部件最后都要在C车间装配，装配每件甲、乙产品分别需要3、4工时，三车间每天可用于生产这两种产品的工时分别为8、12、36，问应如何安排生产这两种产品才能获利最多？2021/5/924产品配比问题z

x1

x2决策变量z=3x1

+5x2max0目标函数x1

≤8①2x2

≤12

②3x1

+4x2

≤36③函数约束

x1

，x2

≥0④非负性约束s.t.甲乙103024

81236ABC车间产品单耗（工时/件）最大生产能力（工时/天）单位利润（百元/件）

3

52021/5/925线性规划问题的数学模型练习：某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？

设备产品ABCD利润（元）

甲21402

乙22043

有效台时12816122021/5/926线性规划问题的数学模型解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤122021/5/927七、生产计划问题的数学模型

某企业拟用m种资源生产n种产品，已知第i种资源的数量为bi,其单价为pi,每生产一个单位第j种产品所提供的产值为vj,所消耗的第i种资源的数量为aij。第j种产品的合同与指令性计划的产量指标为ej,最高需求量为dj。该企业应如何拟定生产计划？2021/5/928

一、决策变量

设xj为第j种产品的计划产量

二、约束条件⑴指标约束xj≥ej

,

j=1,2,…

,n⑵需求约束xj≤dj

,

j=1,2,…

,n⑶资源约束

三、目标函数⑴总产值七、生产计划问题的数学模型

j=1n∑aijxj≤bi,

i=1,2,…,mj=1nm

i=1z2=∑pi(∑aij

xj)

⑵总成本z1=∑vj

xj

nj=12021/5/929七、生产计划问题的数学模型

i=1=∑vj

xj-∑pi(∑aij

xj)j=1nmj=1n=∑(vj-

∑piaij

)

xjj=1n

i=1m令

cj

=vj-

∑piaij

i=1mxj≥ej

,

j=1,2,…

,nxj≤dj∑aijxj≤bi,

i=1,2,…,mj=1nmaxz=∑cj

xjj=1n

s.t.则⑶

总利润

z=z1-z22021/5/930七、生产计划问题的数学模型

某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1和A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。2021/5/931七、生产计划问题的数学模型设备产品设备有效台时设备加工费（单位小时）ⅠⅡⅢ27910000321B168124000250B247000783B37114000200原料费（每件）0.250.350.5售价（每件）1.252.002.82021/5/932七、生产计划问题的数学模型解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：2021/5/933七、生产计划问题的数学模型目标是利润最大化，即利润的计算公式如下：带入数据整理得到：2021/5/934七、生产计划问题的数学模型因此该规划问题的模型为：2021/5/935有n种食品,每种食品中含有m种营养成分。食品用

j=1,2,…

,n表示，养分用

i=1,2,…

,m表示。已知第

j种食品单价为

cj,每天最大供量为

dj;

而每单位第

j种食品所含第

i种养分的数量为

aij。假定某种生物每天对第

i种养分的需求量至少为

bi,

而每天进食数量限定在

[

h1,

h2

]

范围内。试求该生物的食谱，使总成本为最小。八、食谱问题的数学模型2021/5/936八、食谱问题的数学模型设xj为每天提供给该生物食用的第j种食品的数量，则该问题的数学模型为:

s.t.

0

≤

xj

≤

dj

,

j=1,2,…,nminz=∑cj

xjj=1nj=1

h1

≤

∑xj

≤h2nj=1

∑aij

xj

≥

bi,

i=1,2,…,mn2021/5/937八、食谱问题的数学模型配料问题例：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省？21.5原料单价1.007.5010.000.10.151.70.751.101.30A1A2A3

最低需要量

甲乙含量食物成分2021/5/938八、食谱问题的数学模型解：设Xj表示Bj

种食物用量2021/5/939九、产品配套问题的数学模型

某厂制造某种部件，由2个B1零件,3个B2零件配套组装而成。该厂有A1,A2,A3三种机床可加工这两种零件，每种机床的台数，以及每台机床的生产率如下表所示。求产量最大的生产方案。2021/5/940九、产品配套问题的数学模型

一、决策变量

设以xij表示每台Ai(i=1,2,3)机床每个工作日加工Bj(j=1,2)零件的时间(单位:工作日)；

z为B1,B2零件按2:3的比例配套的数量(套/日)。机床种类机床台数每台机床生产率(件/日)零件B1零件B2A132030A223545A341018x11x12x21x22x31x322021/5/941九、产品配套问题的数学模型

二、约束条件

⑴工时约束

⑵配套约束机床种类总生产率(件/日)零件B1零件B2A16090A27090A34072x11x12x21x22x31x32z=min{(60x11+70x21+40x31),(90x12+90x22+72x32)}1213z≤(60x11+70x21+40x31)12z≤(90x12+90x22+72x32)13非线性，等价改写成：

或x11