第五章运筹学-线性规划在管理中的应用案例

第五章线性规划在管理中的应用

5.1某企业停止了生产一些已经不再获利的产品，这样就产生了一局部剩余生产力。管理层考虑将

这些剩余生产力用于新产品I、【I、in的生产。可用的机器设备是限制新产品产量的主要因素，具体数

据如下表：

机器设备类型每周可用机器台时数

铳床5(X)

车床350

磨床150

每生产一件各种新产品需要的机器台时数如下表:

机器设备类型新产品I新产品H新产品III

铳床846

车床430

磨床301

三种新产品的单位利润分别为0.5元、0.2元、0.25元。目标是要确定每种新产品的产量，使得公

司的利润最大化。

1、判别问题的线性规划数学模型类型。

2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。

3、建立该问题的线性规划数学模型。

4、用线性规划求解模型进行求解。

5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目

标函数变量系数和常数项的变化范围进行详细分析）。

6、假设销售部门表示，新产品I、II生产多少就能销售多少，而产品HI最少销售18件，请重新完

成此题的l-5o

解：

本问题是资源分配型的线性规划数学模型。

2、该问题的决策忖标是公司总的利润最大化，总利润为:

0.5AI+().2x2+0.25x3

决策的限制条件：

8xi+4为+6X3《500铳床限制条件

4xi+3x2W350车床限制条件

3xi+X3W150磨床限制条件

即总绩效测试（目标函数）为：

maxz=0.5.ri+0.2x?+0.25.口

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

maxz=0.5xi+0.2x2+0.25.V3

S.T.8A4I+4XI+6X3^500

4A-I+3X2<350

3xi+X3WI5O

加20、也2°、132（）

4、用Excel线性规划求解模板求解结果：最优解150,25,0）,最优值：30元。

5、灵敏度分析

目标函数品优值为:30

变量最优解相差值

X1500

x2250

x30.083

约束2弛/剩余变量对偶价格

10.05

2750

30.033

目标函数系数范围：

变量下限当前值上限

X1.4.5无上限

x2.1.2.25

x3无下限.25.333

梏数项数范围•

约束下限当前值上限

1400500600

2275350无上限

337.5150187.5

⑴最优生产方案：

新产品I生产50件、新产品II生产25件、新产品HI不安排。最大利润值为30元。

(2)x3的相差值是0.083意味着，目前新产品III不安排生产，是因为新产品HI的利润太低，假设

要使新产品IH值得生产，需要将当前新产品m利润0.25元/件，提高到0.333元/件。

(3)三个约束的松弛/剩余变量0,75,0,说明铳床和磨末的可用工时已经用完，而车床的可用工

时还剩余73个工时：

三个对偶价格0.05,0,0.033说明三种机床每增加一个工时可使公司增加的总利润额。

(4)目标函数系数范围

说明新产品I的利润在0.4元/件以上，新产品II的利润在0.1到0.25之间，新产品HI的利润

在0.333以下，上述的最正确方案不变。

(5)常数项范围

说明铳床的可用条件在400到600工时之间、车铳床的可用条件在275工时以上、磨铳床的

可用条件在37.5到187.5工时之间。各自每增加一个工时对总利润的奉献005元，0元,0.033元不变。

6、假设产品III最少销售18件，修改后的的数学模型是：

maxz=0.5xi+0.2x2+0.25x3

S.T.8AI+4x2+6x3W50()

4xi+3x2W350

3xi+必号150

工3218

xi'O、必20、工320

这是一个混合型的线性规划问题。

代入求解模板得结果如下：

最优解(44,10,18),最优值：28.5元。

灵敏度报告：

目标函数最优值为:28.5

变量最优解相差值

X1440

x2100

x3180

约束玄弛/剩余变量对偶价格

10.05

21440

30.033

40083

目标函数系数范围：

变量下限当前值上限

X1.4.5无上限

x2.1.2.25

x3无下限.25.333

常数项数范围：

约束下限当前值上限

1460500692

2206350无上限

318150165

401830

(1)最优生产方案：

新产品【生产44件、新产品H生产10件、新产品【II生产18件。最大利润值为28.5元c

(2)因为最优解的三个变量都不为0,所以三个相关值都为仇

(3)四个约束的松弛/剩余变量0,144,0,0,说明铳床和磨床的可用工时已经用完，新产品IH的

产量也刚好到达最低限制18件，而车床的可用工时还剩余144个工时；

四个对偶价格0.05,0,0.033,-0.083说明三种机床每增加一个工时可使公司增加的总利润额，第

四个对偶价格-0.083说明新产品III的产量最低限再多规定一件，总的利润将减少0.083元。

(4)目标函数系数范围

说明新产品【的利润在0.4元/件以上，新产品II的利润在0.1到0.25之间，新产品HI的利润在0.333

以下，上述的最正确方案不变。

(5)常数项范围

说明铳床的可用条件在460到692工时之间、车铳床的可用条件在206工时以上、磨铳床的可用条

件在18到165工时之间、新产品IH产量限制在30件以内。各自每增加一个工时对总利润的奉献0.05

元，0元，0.033元，-.083元不变。

5.2某铜厂轧制的薄铜板每卷宽度为100cm,现在要在宽度上进行切割以完成以下订货任务：32cm

的75卷，28cm的50卷,22cm的110卷，其长度都是一样的。问应如何切割可使所用的原铜板为最少？

解：本问题是一个套材下料问题，用穷举法找到所有可能切割的方式并建立数学模型：

minf=xi+X2+X3+X4+X5+X6+X7+X8+X9+X10

S.T.3x]+2门+2%3+必+*+入,6275

X2+2X4+X6+3X7+2XS+X9，50

X3+3X5+X6+2,V8+3X?+4XIO>110

k20(i=l,2…10)

用Excel线性规划求解模型板求解：

最优解：(18.33,0,0,0,20,0.0.25,0,0,0),最优值：63.3333

因为铜板切割时必须整卷切割所以需要做整数近似。即其结果为：

即最优解：(19,0,0,0,20,0,0.25,0,0,0),最优值:64

灵敏度分析报告：

目标函数最优值为：63.333

变量最优解相差值

X118.3330

x20.056

x30.111

x40.111

x5200

x60.167

x70.167

x8250

x90.056

xlO0.111

约束松弛/剩余变量对偶价格

10333

20278

30222

目标函数系数范围■

变量下限当前值上限

X1.7511.071

x2.9441无上限

x3.8891无上限

x4.8891无上限

x5.83311.083

x6.8331无上限

x7.8331无上限

x8.44411.111

x9.9441无上限

xlO.8891无上限

常数项数范围：

约束下限当前值上限

12075无上限

2050110

350110275

这是一个统计型的线性规划问题，所以分析价值系数的取值范围和相差都没有意义。

松弛/剩余变量都为0,表示最优方案已到达三种规格薄铜板数量的最低限。

三个约束条件的对偶价格333、-.278、-.222分别表示三种规格薄铜板数量的最低限再增加一个,

将增加原铜板.333cm、.278cm、.222cm。这个数字实际跟薄铜板长度规格相一致。

常数项数范围表示三种规格薄铜板数量的最低限在这些范围内，每增一个限额所原原铜

板.333cm、.278cm、.222cm不变。这里需要特别指出的是，第一种规格的薄铜板32cm宽，已使三块组

合就能比拟恰当地用完原铜板，所以这种规格的薄铜板无论增加多少，都不改变用原铜板的比例。

5.3某医院对医生工作的安排为4小时一个工作班次，每人要连续工作二个班次。各班次需要医生

人数如下表：

班次时间人数

10:00-4:004

24:00-8:007

38:00-12:009

412:00-16:0012

516:00-20:00g

620:()0-24:006

其中，第6班报到的医生要连续上班到第二天的第1班。问在各班开始时应该分别有几位医生报到。假

设参加1、2、6班的医生需要支付夜班津贴，为了使支付总的夜班津贴为最少，应如何安排各班开始时

医生的报到人数。

解：第一步：不考虑夜班滓贴。

线性规划数学模型为：

min户X1+JC2+X3+X1+X5+X6

S.T.北+工124

x\+xr^-l

及+1329

力+足212

X4+X528

必+犬626

国20(i=l,2,3,4,5,6)

用Excel线性规划求解模板求解得：

第一班安排7人，第三班安排10人，第四班安排2人，第五班安排6人，第二、第六班不安排人。

总人数为25人。

灵敏度分析报告：

目标函数最优值为：25

变量最优解相差值

X170

x200

x3100

x420

x560

x600

约束勿驰/剩余变量对偶价格

13.0

20-1

31.0

40—1

50.0

60—1

目标函数系数范围：

变量下限当前值上限

X10.11

x211无上限.

x3U.11

x41.12

x5011

x611无上限

常数项数范围•

约束下限当前值上限

1无下限47

247无上限

3无下限910

41112无上限

5689

6568

这是一统计型线性规划规划问题，所以相差值的价值系数的变化范围没有必要分析。

班次时间所需人数本段安排人数上段安排人数本段实际人数多余人数

10:00-4:0047073

24:00-8:0070770

38:00-12:009100101

412:00-16:0012210120

516:00-20:0086280

620:00-24:0060660

合计4625504

松弛/剩余变量一栏就是上表的“多余人数”一列是各时间段安排所剩余的人数。

“对偶价格”一栏。

第一个常数项由4增加到5,因为还剩下2人，所以不会改变最优值；

第二个常数项由7增加到8,因为再没有剩余的人，所以本班必须再多安排一个人最优值解也必须

增加1,因为是求最小化问题，所以对偶价格为-1;

第三个常数项由9增加到10,刚好将原来剩余的人用上，所以不会改变最优值；

第四个、第六个常数项与笫二个常数项一样；

第五个常数项由2增加到3,因为再没有剩余的人，所以本班必须再多安排一个人，但下个班就可

以再少安排一个人，所以不会改变最优值：

此融解这掷脸况是每一个变量都会影响到两个时段的结果,所以在进行灵敏度分析时也必定要考虑

这个因素，这里第一个时段是特殊情况(有资源剩余)，其余的时段分析时相邻两个是相互影响的。因

此，第2时段为-1,第3时段为()，后面的依次相反。假设第2时段为0,那么第3时段就为-1。

第二步：考虑夜班津贴。

线性规划数学模型为：

minf=x\+X2+X3+X5+X6

S.T.

xi+.027

X2+X329

X3+X4212

X5+%6^6

刘20(i=l,2,3,4,5,6)

用Excel线性规划求解模板求解得：

即：总人数还是25人，但每班安排人数有所调整：

第一班不安排人，笫二班安排7人，笫三班安排2人，第四班安排10人,笫五班安排。人，笫六

班安排6人。

灵敏度分析报告：

目标函数最优值为:15

变量最优解相差值

X101

x270

x320

x4100

x500

x660

约束虫弛/剩余变量对偶价格

120

200

30-1

400

520

60-1

目标函数系数范围：

变量下限当前值上限

X101无上限

x2112

x3011

x4001

x511无上限

x6011

常数项数范围：

约束下限当前值上限

1无下限46

2579

37911

41012无上限

5无下限810

646无上限

这是一统计型线性规划规划问题，所以相差值的价值系数的变化范闹没有必要分析。

班次时间所需人数本段安排人数上段安排人数木段实际人数多余人数

10:00-4:0040662

24:00-8:0077070

38:00-12:(X)92790

412:00-16:00121()2120

516:00-20:008010102

620:00-24:0066060

合计4625504

“对偶价格”一栏。

笫一个常数项由4增加到5,因为还剩卜2人，所以不会改变最优值；

第二个常数项由7增加到8,由于上段时间已增一个人，这个人本班还上班，所以本也不需要增加

人。

第三个常数项由9增加到10,前面安排的人都己下班，本班刚好只朋9人，假设需求再增加一人,

就需要新安排一人所以对偶价格-1;

第四个、第五个、第六个常数项与前三个常数项一样；

5.4某塑料厂要用四种化学配料生产一种塑料产品，这四种配料分别由A、B、C三种化学原料配

制，三种化学原料的配方及原料价格如下表：

配料1234价格1元/公斤)

含原料A(%)3040201511

含原料B(%)2030604013

含原料C(%)4025153012

要配制的塑料产品中，要求含有20%的原料A,不少于30%的材料B和不少于20%的原料C。由于技

术原因，配料I的用量不能超过30%,配料2的用量不能少于40%。第一次配制的塑料产品不能少于5

公斤。请设计一套配料方案，使总的本钱为最低。

解：线性规划数学模型：

minf=10.7xi+lL3x2+11.8即+9.45★

S.T.0.Lvi+0.2x2-0.05x1=0

-0.lx\+0.3^3+0.1x4^0

0.2xi+0.05x2-0.05x3+0.1x4^0

0.7XI-0.3X2-0.3X3-0.3XI>0

-0.4_¥]+0.6犯-0.4力-()4匕・0

X|+X2+X3+XI25

GO(i=l,2,3,4,)

将模型代入到线性规划求解模板，得结果：

用配料1,1.5公斤；用配料2,0.1公斤；用配料3,0公斤；用配料4,3.4公斤；花费总的最低

本钱49.31元。

灵敏度分析报告：

目标函数最优值为：:49.31

变量最优相差值

X11.50

x2.10

x301.98

x43.40

约束松弛/剩余变量对偶价格

10-7.4

2.190

3.6450

4014

51.90

60-9.862

目标函数系数范围:

变量下限当前值上限

X110.5610.7无上限

x2-481.811.311.533

x39.8211.8无上限

x4-5.0539.459.8

格数项数范围：

约束下限当前值上限

10250.475

2无下限0.19

3无下限0.645

4-1.50.167

5-1.90无上限

605无上限

本问题的相差值栏，x3的相差值为1.98,表示目前配料3的本钱11.8太高，无法选用，假设该配

料的本钱再降低1.98元就可以选取用。

松弛/剩余变量栏：前五个给条件都表示的是配料或原料的配比关系。松弛/剩余变量为0关系表示

已完全按要求配比，不为0的表示没有到达配比要求。第五人约束是总产品的产量最低限，松弛/剩余

变量为0表示已到达产量要求。

关五个约束的对偶价格表示配料或者说原料不匹配时，对总费用的影响,不为0的对偶价格表示配

比每差一个单位都会使总费用的增加量。第五个对偶价格是每增加一公斤的产品，需要增加的费用值。

在学数项取值范围栏：前五个约束在常数项在这个范围内，保持上述的对偶价格，而此时的上限都

不高，说明这个最优方案中的匹配关系失衡并不严重，假设比例失衡将会导致费用的增加比例更大。对

五个对偶价格实际上说明了该产品的绝对本钱，在这个方案下，生产多少的产品都是这个本钱构成。

5.5某工厂生产【、II、山、IV四种产品，产品I需经过A、B两种机器加工，产品II需经过A、C

两种机器加工，产品IH需经过B、C两种机器加工，产品IV需经过A、B两种机器加工。有关数据见下

表所示：

广口口机器生产率（件〃J、时）原料本钱1元/件）产品价格（元/件）

ABC

I10201665

1120102580

III10151250

IV20101870

机器本钱（元/小时）200150225

每周可用机时数15012070

请为该厂制定一个最优生产方案。

解：线性规划数学模型：

maxZ=21.5x\+22.5&+8内+27XA

S.T.2xi+X2+X1<3000

xi+2t3+2xW2400

3X2+4X3<4200

汨20(i=l»2,......4)

用Excel线性规划求解模板求解得：

最优生产方案：产品I生产267件：

产品II生产1400件;

产品HI不安排生产：

产品IV生产1067件。

可获得的最高利润：66033.3元。

灵敏度分析报告：

跳：目标函数最优值为：66033.3495

变量最优解相差值

X1266.6670

x214000

x3030.8333

x41066.6670

约束松弛/剌余变量对偶价格

105.333

2010.833

305.722

目标函数系数范围：

变量卜.限当前值上限

X113.521.545

x25.33322.5无上限

x3无下限838.333

x410.752743

常数项数范围:

约束下限当前值上限

1260030006200

280024003200

3042005400

此模型的最优解中，四个变量有三个变量不为o,即需要安排生产，另一个为o的变量表示产品m

由于本钱高或价格低，使所获的利润太低，不值得生产。从相差值栏可见，该产品的单位利润需要再增

加30.8333元才值得生产。

松弛/剩J余变量栏中三个数据都为（），表示该决策中所提供三种设备的机时都已全部利用，没有剩

余；从对偶价格栏还可以看到三种设备的机时虽然都已用尽，但此时对三种设备增加机时，那么设备B

所带来的总利润为最多。因此设备B是瓶径。从约束条件的取值范围也可以看到这一点，因为设备B的

机时取值范围最小，因此该设备是关键。

5.6某企业生产I、II两种产品，市场两种产品的需求量为：产品I在1-4月份每月需1万件，5-9

月份每月需3万件，10-12月份每月需10万件；产品II在3-9月份每月需1.5万件，其他月份每月需5

万件。该企业生产这两种产品的本钱为：产品I在1-5月份生产时每件5元，6-12月份生产时每件4.5

元；产品II在1-5月份生产时每件8元，6-12月份生产时每件7元；该企业每月生产两种产品的能力总

和不超过12万件。产品I容积为每件0.2立方米，产品II容积为每件0.4立方米。该企业仓库容积为1.5

万立方米。要求：

I、问该企业应如何安排生产，使总的生产加工储存费用为最少，建立线性规划数学模型并求解，

假设无解请说明原因。

2、假设该企业的仓库容积缺乏时，可从外厂租借。假设占用本企业的仓库每月每立方米需1万元

的储存费，而租用外厂仓库时其储存费用为每月每立方米1.5万元，试问在满足市场需求情况下，该企

业又应如何安排生产，使总的生产加储存费用为最少。

解：

1、这是一个72个变量、60个约束条件的线性规划问题，假设不考虑外厂租借仓库，那么无法求解

（无解），只有考虑外厂租借仓库才能解决本问题,分析及解决过程和结果可见下表：

月份123456789101112仓容外存

销售量（千件）101010103030303030100100100

本钱（元、件）555554.54.54.54J4J4.54.5

产量（件）xl=10x2=10x3=10x4=10x5=30x6=30x7=30x8=45x9=105x10=70x11=70x12=70

1总容积（干一）0.2x10.2x20.2x30.2x40.2x50.2x60.2x70.2K80.2x90.2x100.2x110.2x12

库存数x25=0x26=0x27=0x28=0x29=0x30=0x31=0x32=15x33=90x34=60x35=30x36=0

销住量（千件）505015151515151515505050

本钱（元、件）888887777777容量

1。八BA

产量（件）x13=50x14=50x15=15xl6=15xl7=15xl8=15xl9=15x20=15x21=15x22=50x23=50x24=50不限

(m3〕

II总容积（千一）0.4x130.4x140.4>:150.4x160.4x170.4x180.4x190.4>200.4x210.4x220.1x230.4x24

库存数x37=0x38=0x39=0x40=0x41=0x42=0x43=0x44=0x45=0x46=0x47=0x48=01.5元

1元/nd

2/m3

本厂（千m‘）x50=0x51=0x52=0x53=0x54=0x55=0x56=3x57=15x58=12x59=6x60=0

容

外借（千♦）x61=0x62=0x63=0x64=0x65=0x66=0x67=0x68=0x69=3x70-0x71=0x72=0

产

（「件）120120120120120120120120120120120120

利

总的生产加储存最少费用为4910500元

外借的库房，在9月份用了3千平方米的容量。

本问题灵敏度详细分析太麻烦，从略。

5.7某快餐店坐落在••个远离市区的旅游点中，平时游客不多，而在除冬季外每个双休日游客都比

拟多。该快餐店有两名正式职工，正式职工每天工作8小时，且每个时间段都至少要有一个正式职工在

上班，其余工作由临时工来承当，临时工每班工作4小时。在双休日每天上午10时开始营业到下午10

时关门。根据游客就餐情况，在双休日每个营业时间段所需职工数（包括正式工和临时工）如下表：

时间段所需职工数

10:00-11:009

11:00-12:0010

12:00-13:001()

13:00-14:009

14:00-15:003

15:00-16:003

16:00-17:003

17:00-18:006

18:00-19:0012

19:0()-20:()()12

20:00-21:(M)7

21:00-22:007

一名正式职工10点开始上班，工作4小时后休息1小时，而后再工作4小时；另一名正式职工13

点开始上班，工作4小时后休息.1小时，而后再工作4小时。临时工每小时的工资为4元。

1、在满足对职工需求的条件下，如何安排临时工的班次，使得使用临时工的本钱为最小？

2、这时付给临时工的工资总额为多少？一共需要安排多少个班次的临时工？请用剩余量来说明如

果安排一些每班工作3小时的般时工班次，可使得总本钱更小。

3、如果临时工每班工作时间可以是3小时，也可以是4小时，那么应如何安排临时工的班次，使

得使用临时工的总本钱为最小？这样比第1问的结果能节省多少费用？这时要安排多少临时工的班次？

艇：1、线性规划数学模型：

minf=16xi+16x2+16x3+16.0+16x5+16x()+16x7+16内+16x9+12xio+8xn+4x12

x\28

Xi+x229

X1+X2+X329

为+必+内+工427

皿+不+乂+心》2

由+9+右+北21

为+右+北+刈