运筹学第四章

第 5 次课 2学时

本次课教学重点：

建立数学模型

本次课教学难点：

建立数学模型

本次课教学内容：

第四章线性规划在工商管理中的应用

第一节人力资源分配的问题

例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：

设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?

解：设x i( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。

目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 + x7

约束条件：s.t. x1 + x2 + x3 + x4 + x5≥28

x2 + x3 + x4 + x5 + x6≥15

x3 + x4 + x5 + x6 + x7≥24

x4 + x5 + x6 + x7 + x1≥25

x5 + x6 + x7 + x1 + x2≥19

x6 + x7 + x1 + x2 + x3≥31

x7 + x1 + x2 + x3 + x4≥28

x1,x2,x3,x4,x5,x6,x7≥0

例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？

解：设x i ( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。

目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 + x7

约束条件：s.t. x1 + x2 + x3 + x4 + x5 ≥28

x2 + x3 + x4 + x5 + x6 ≥15

x3 + x4 + x5 + x6 + x7 ≥24

x4 + x5 + x6 + x7 + x1 ≥25

x5 + x6 + x7 + x1 + x2 ≥19

x6 + x7 + x1 + x2 + x3 ≥31

x7 + x1 + x2 + x3 + x4 ≥28

x1,x2,x3,x4,x5,x6,x7 ≥0

第二节生产计划的问题

例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？

解：设x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。

求x i 的利润：利润= 售价- 各成本之和

产品甲全部自制的利润=23-(3+2+3)=15

产品甲铸造外协，其余自制的利润=23-(5+2+3)=13

产品乙全部自制的利润=18-(5+1+2)=10

产品乙铸造外协，其余自制的利润=18-(6+1+2)=9

产品丙的利润=16-(4+3+2)=7

可得到x i（i = 1,2,3,4,5）的利润分别为15、10、7、13、9 元。

通过以上分析,可建立如下的数学模型:

目标函数：Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5

约束条件：5x1 + 10x2 + 7x3≤8000

6x1 + 4x2 + 8x3 + 6x4 + 4x5≤12000

3x1 + 2x2 + 2x3 + 3x4 + 2x5≤10000

x1,x2,x3,x4,x5≥0

例4．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成A 工序；有三种规格的设备B1、B2、B3能完成B 工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？

解：设x ijk表示第i 种产品，在第j 种工序上的第k 种设备上加工的数量。建立如下的数学模型:

s.t. 5x111 + 10x211 ≤6000 （设备A1）

7x112 + 9x212 + 12x312≤10000 （设备A2）

6x121 + 8x221≤4000 （设备B1）

4x122+ 11x322≤7000 （设备B2）

7x123≤4000 （设备B3）

x111+ x112- x121- x122- x123= 0 (Ⅰ产品在A、B工序加工的数量相等）

x211+ x212- x221= 0 （Ⅱ产品在A、B工序加工的数量相等）

x312 - x322= 0 （Ⅲ产品在A、B工序加工的数量相等）

x ijk≥0 , i = 1,2,3; j = 1,2; k = 1,2,3

目标函数为计算利润最大化，利润的计算公式为：

利润= [（销售单价- 原料单价）* 产品件数]之和-（每台时的设备费用*设备实际使用的总台时数）之和。

这样得到目标函数：

Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312–

300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-

250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).

经整理可得：

Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123第三节套裁下料问题

例5．某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？

解：共可设计下列5 种下料方案，见下表

设x1,x2,x3,x4,x5 分别为上面5 种方案下料的原材料根数。这样我们建立如下的数学模型。

目标函数：Min x1 + x2 + x3 + x4 + x5

约束条件：s.t. x1 + 2x2 + x4≥100

2x3 + 2x4 + x5≥100

3x1 + x2 + 2x3+ 3x5≥100

x1,x2,x3,x4,x5≥0

?用“管理运筹学”软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。

即x1=30;

x2=10；

x3=0；

x4=50；

x5=0；

只需90根原材料就可制造出100套钢架。

?注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。

第四节配料问题

例6．某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？

解：设x ij表示第i 种（甲、乙、丙）产品中原料j 的含量。这样我们建立数学模型时，要考虑：

对于甲：x11，x12，x13；

对于乙：x21，x22，x23；

对于丙：x31，x32，x33；

对于原料1：x11，x21，x31；

对于原料2：x12，x22，x32；

对于原料3：x13，x23，x33；

目标函数：利润最大，利润= 收入- 原料支出

约束条件：规格要求4 个；

供应量限制3 个。

?利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量，故有

目标函数

Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）

= -15x 11+25x 12+15x 13-30x 21+10x 22-40x 31-10x 33 约束条件：

从第1个表中有：

x 11≥0.5(x 11+x 12+x 13) x 12≤0.25(x 11+x 12+x 13) x 21≥0.25(x 21+x 22+x 23) x 22≤0.5(x 21+x 22+x 23)

从第2个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有 (x 11+x 21+x 31)≤100 (x 12+x 22+x 32)≤100 (x 13+x 23+x 33)≤60

通过整理，得到以下模型：

目标函数：Max z = -15x 11+25x 12+15x 13-30x 21+10x 22-40x 31-10x 33 约束条件：

s.t. 0.5 x 11-0.5 x 12 -0.5 x 13 ≥ 0 （原材料1不少于50%） -0.25x 11+0.75x 12 -0.25x 13 ≤ 0 （原材料2不超过25%） 0.75x 21-0.25x 22 -0.25x 23 ≥ 0 （原材料1不少于25%） -0.5 x 21+0.5 x 22 -0.5 x 23 ≤ 0 （原材料2不超过50%） x 11+ x 21 + x 31 ≤ 100 (供应量限制） x 12+ x 22 + x 32 ≤ 100 (供应量限制) x 13+ x 23 + x 33 ≤ 60 (供应量限制） x ij ≥ 0 , i = 1,2,3; j = 1,2,3

例7.汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表4-6中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求列于表4-7中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？

表 4-6

130100

28.45 ×10-2

108.0 4 408100 5.69×10-2 87.0 3 265200 11.38 ×10-2

93.0 2 380000 7.11×10-2 107.5 1 库存量(L)

蒸汽压力(g/cm 2) 辛烷数 标准汽油 不少于250000

不大于9.96 ×10-2

不小于100

2

越多越好 不大于9.96 ×10-2

不小于91 1 产量需求 蒸汽压力(g/cm 2) 辛烷数 飞机汽油

表 4-7

解：设x ij 为飞机汽油i 中所用标准汽油j 的数量(L)。

目标函数为飞机汽油1的总产量：

库存量约束为：

产量约束为飞机汽油2的产量： 由物理中的分压定律，∑==

n

j j

j

v

p PV 1

可得有关蒸汽压力的约束条件：

同样可得有关辛烷数的约束条件为：

综上所述，得该问题的数学模型为：

由管理运筹学软件求解得：

11121314

x x x x +++1121122213231424380000265200

408100130100x x x x x x x x +≤+≤+≤+≤21222324250000x x x x +++≥11121314212223242.85 1.42 4.2718.4902.85 1.42 4.2718.490x x x x x x x x -+-≥-+-≥111213141112131416.5 2.0 4.017.007.57.013.08.00x x x x x x x x +-+≥--+≥111213142122232411211222132314241112131421222324111213142122max 2500003800002652004081001301002.85 1.42 4.2718.4902.85 1.42 4.2718.49016.5241707.57x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ++++++≥+≤+≤+≤+≤-+-≥-+-≥--+≥-23241380

0,(1,2;1,2,3,4)ij x x x i j ?????

???????

??-+≥?

≥==??11121314111213max()933399.938261966.078265200315672.219x x x x x x x +++====

第五节投资问题

例8．某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项

目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第

一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额

不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规

定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本

利155%，但规定最大投资额不能超过100万元。

据测定每万元每次投资的风险指数如右表：

问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？

解：1）确定决策变量：连续投资问题

设x ij ( i = 1～5，j = 1～4)表示第i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：

A x11 x21 x31 x41 x51

B x12 x22 x32 x42

C x33

D x24

2）约束条件：

第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是x11+ x12 = 200；

第二年：B次年末才可收回投资，故第二年年初有资金1.1 x11，于是x21 + x22+ x24 = 1.1x11；

第三年：年初有资金1.1x21+ 1.25x12，于是x31 + x32+ x33 = 1.1x21+ 1.25x12；

第四年：年初有资金1.1x31+ 1.25x22，于是x41 + x42 = 1.1x31+ 1.25x22；

第五年：年初有资金1.1x41+ 1.25x32，于是x51 = 1.1x41+ 1.25x32；

B、C、D的投资限制：x i2 ≤30 ( i =1、2、3、4 )，x33≤80，x24≤100

3）目标函数及模型：

a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24

s.t. x11+ x12 = 200

x21 + x22+ x24 = 1.1x11；

x31 + x32+ x33 = 1.1x21+ 1.25x12；

x41 + x42 = 1.1x31+ 1.25x22；

x51 = 1.1x41+ 1.25x32；

x i2 ≤30 ( i =1、2、3、4 )，x33≤80，x24≤100

x ij≥0 ( i = 1、2、3、4、5；j = 1、2、3、4）

b)所设变量与问题a相同，目标函数为风险最小，有

Min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24

在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件，于是模型如下：Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24

s.t. x11+ x12 = 200

x21 + x22+ x24 = 1.1x11；

x31 + x32+ x33 = 1.1x21+ 1.25x12；

x41 + x42 = 1.1x31+ 1.25x22；

x51 = 1.1x41+ 1.25x32；

x i2 ≤30 ( i =1、2、3、4 )，x33≤80，x24≤100

1.1x51 + 1.25x42+ 1.4x33+ 1.55x24≥330

x ij≥0 ( i = 1、2、3、4、5；j = 1、2、3、4）

教学组织

1、课堂讲授、学生报告

2、软件求解演示

作业布置：

1、P57.2，4，6

本文档部分内容来源于网络，如有内容侵权请告知删除，感谢您的配合！

运筹学整数规划补例样本

运筹学难点辅导材料 整数规划补例 1、 对( IP) 整数规划问题12 12121212max 14951631..0,0,z x x x x x x s t x x x x =++≤?? -+≤?? ≥≥???为整数, 问用先解相应的线性规划然后凑 整的办法能否求到最优整数解? 再用分支定界法求解。 解 先不考虑整数约束, 得到线性规划问题( 一般称为松弛问题LP) 12 12121 2max 14951..6310,0 z x x x x s t x x x x =++≤?? -+≤??≥≥?用图解法求出最优解12310 ,23x x ==且296z =。 如用”舍入取整法”凑整可得到四个点, 即( 1, 3) 、 ( 2, 3) 、 ( 1, 4) 、 ( 2, 4) 。代入约束条件发现她们都不是可行解。可将可行域内的所有整数点一一列举( 完全枚举法) , 本例中( 2, 2) 、 ( 3, 1) 点为最大值4z =。 令() 0310,23T X ??= ??? 及最优值()0 296z =。可行域记为D, 显然()0X 不是整数解。 定界: 取()0296z z == , 再用视察法找一个整数可行解()0,0T X '=及0z '=, 取0z z '==, 即*2906 z ≤≤ 分支: ( 关键点, 在B 的最优解中任选一个不符合整数条件的变量j x , 其值为 j b , 构造两个约束条件1,j j j j x b x b ????≥+≤????, 这里用了取整函数呵! ) 任取最 优解中一个不为整数的变量值, 例如132x = , 根据312?? =???? , 构造两个约束条件,

运筹学第四章多目标规划

习题四 4.1 分别用图解法和单纯形法求解下述目标规划问题 （1） min z ＝p 1（+1d ＋+2d ）＋p 2-3d st. －x 1＋ x 2＋ d －1－ d ＋ 1＝1 －0.5x 1＋ x 2＋ d － 2－d ＋ 2＝2 3x 1＋3x 2＋ d －3－ d ＋3＝50 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1，2，3） （2） min z ＝p 1（2+1d ＋3+2d ）＋p 2-3d ＋p 3+4d st. x 1＋ x 2＋d －1－d ＋ 1 ＝10 x 1 ＋d －2－d ＋2 ＝4 5x 1＋3x 2＋d －3－d ＋3 ＝56 x 1＋ x 2＋d －4－d ＋4 ＝12 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1， (4) 4.2 考虑下述目标规划问题 min z ＝p 1（d ＋1＋d ＋2）＋2p 2d －4＋p 2d －3＋p 3d －1 st. x 1 ＋d －1－d ＋1＝20 x 2＋d －2－d ＋2＝35 －5x 1＋3x 2＋d － 3－d ＋ 3＝220 x 1－x 2＋d －4－d ＋4＝60 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1， (4) （1）求满意解； （2）当第二个约束右端项由35改为75时，求解的变化； （3）若增加一个新的目标约束：－4x 1＋x 2＋d －5－d ＋5＝8，该目标要求尽量达 到目标值，并列为第一优先级考虑，求解的变化； （4）若增加一个新的变量x 3，其系数列向量为（0，1，1，－1）T ，则满意解如何变化？ 4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律，该台每天允许广播12小时，其中商业节目用以赢利，每小时可收入250美元，新闻节目每小时需支出40美元，音乐节目每播一小时费用为17.50美元。法律规定，正常情况下商业节目只能占广播时间的20％，每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下： P 1：满足法律规定要求； P 2：每天的纯收入最大。 试建立该问题的目标规划模型。

运筹学第四章

运筹学第四章习题答案 4.1若用以下表达式作为目标规划的目标函数，其逻辑是否正确？为什么？ （1）max ｛- d -+d ｝ （2）max ｛-d ++ d ｝ （3）min ｛-d ++d ｝ （4）min ｛-d -+ d ｝ （1）合理，令f （x ）+- d -+ d =b,当f （x ）取最小值时，- d -+ d 取最大值合理。 (2)不合理，+ d 取最大值时，f （x ）取最大值，- d 取最大值时，f （x ）应取最小值 （3）合理，恰好达到目标值时，- d 和+ d 都要尽可能的小。 （4）合理，令f （x ）+- d -+ d =b,当f （x ）取最大值时，- d -+ d 取最小值合理。 4.2用图解法和单纯形法解下列目标规划问题 （1）min ｛P 13 +d ，P 2- 2d ，P 3（- 1d ++ 1d ）｝ 24261121=-+++- d d x x 52221=-+++- d d x x 155331=-++-d d x 3,2,1,0,,,21=≥+-i d d x x i i （2）min{P 1(+++43d d ),P 2+1d ,P 3-2d ,P 4(--+4 35.1d d )} 401121=-+++-d d x x 1002221=-++--d d x x 30331=-++-d d x 15442=-++-d d x 4,3,2,1,0,,,21=≥+-i d d x x i i (1)图解法

0 A B C X 1 由图可知，满足域为线段EG,这就是目标规划方程的解，可求得：E,G 的坐标分别为（0，12），（3,3） 故该问题的解为)312,3()3,3()12,0(21221a a a a a +=+ )1,0,(2121=+≥a a a a (2)图解法 2 1 由图可知，满足域为线段AB A(25,15),B(30,10)故该问题的解可 表示为)1015,3025()10,30()15,25(212121a a a a a a ++=+ )1,0(212,1=+≥a a a a

运筹学课件第四章目标规划

第四章目标规划 一、学习目的与要求 1、掌握目标规划的图解法模型； 2、掌握目标规划的单纯形的求解模型； 3、掌握目标规划的灵敏度分析。 二、课时6学时 第一节目标规划问题及其数学模型 一、问题的提出 应用线性规划可以处理许多线性系统的最优化问题，但线性规划，整数规划和非线性规划都只有一个目标函数，而在实际问题中，常常需要考虑多个目标：如设计一个新产品的工艺过程，不仅希望获利大，而且希望产量高，消耗低，质量好，投入少等。而这些目标之间通常是矛盾的。所以这类问题多目标问题比单目标问题要复杂得多，我们把这一类问题称为目标规划问题。 目标规划与线性规划相比，有以下优点： 1.线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题。 实际问题中，往往要考虑多个目标的决策问题，这些目标可能互相矛盾，也可能没有统一的度量单位，很难比较。目标规划就能够兼顾地处理多种目标的关系，求得更切合实际的解。 2.线性规划是在满足所有约束条件的可行解中求得最优解。而在实际问题 中往往存在一些相互矛盾的约束条件，如何在这些相互矛盾的约束条件下，找到一个满意解就是目标规划所要讨论的问题。 3.线性规划问题中的约束条件是不分主次、同等对待的，是一律要满足的“硬约束”。而在实际问题中，多个目标和多个约束条件不一定是同等重要的，而是有轻重缓急和主次之分的，如何根据实际情况确定模型和求解，使其更合实际是目标规划的任务。 4.线性规划的最优解可以说是绝对意义下的最优，为求得这个最优解，往往要花去大量的人力、物力和才力。而在实际问题中，却并不一定需要去找这种最优解。目标规划所求的满意解是指尽可能地达到或接近一个或几个已给定的指标值，这种满意解更能够满足实际的需要。 因此可以认为，目标规划更能够确切描述和解决经济管理中的许多实际问题。目前目标规划的理论和方法已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到广泛的应用。 二、目标规划的数学模型 例1 某工厂生产两种产品，受到原材料和设备工时的限制。在单件利润等有关数据已知的条件下，要求制定一个获利最大的生产计划，具体数据见表：

《运筹学》第四章习题及答案

问题。 运筹学》 第四章习题及 答案 、思考题 1．运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最 多等于 m ，n,1 ？ 2． 用左上角法确定运输问题的初始基本可行解的基本步骤是什么？ 小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到 运输问题的最优方案？ 4． 沃格尔法（ Vogel 法）的基本思想是什么？它和最小元素法相比给出的运 输问题的 初始基本可行解哪一个更接近于最优解？为什么？ 5． 试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意 义是什 么？ 6． 用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回 路？这闭 回路是否是唯一的？ 如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平 衡的运输 10．一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？ 11．试述在表上作业法中出现退化解的涵义及处理退化解的方法。 7． 试述用位势法求检验数的原理、步骤和方法。 8． 试给出运输问题的对偶问题（对产销平衡问题）。 9．

、判断下列说法是否正确 1．运输问题模型是一种特殊的线性规划模型，所以运输问题也可以用单纯形 方法求解。 2 ．因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现 下列四种情况： 有唯一最优解；有无穷多个最优解；无界解；无可行解。 3 ．在运输问题中， 只要给出一组（ ,,xijm ，n,1 ）个非零的，且满足 nm ，，就可以作为一个基本可行解。 4 ．表上作业法实 质上就是求解运输问题的单纯形法。 5．按最小元素法或元素差额法给出的初始基本可行解，从每一空格出发都可 以找到一 闭回路，且此闭回路是唯一的。 6．如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数 k ，最优 调运方案将不会发生变化。 7．如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数 k ，最优 调运方案将不会发生变化。 8．用位势法计算检验数时，先从某一行（或列）开始，给出第一个位势的 值，这个先 给出的位势值必须是正的。 9．用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每 个空格的 检验数是唯一的。 ■ ■ ■ I ■ ■ ■ ■ Jt ■ Jt x,aijix,b,,ijjj,1 i,1

第六章---运筹学-整数规划案例

第六章整数规划 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。 1、 max z=3x1+2x2 . 2x1+3x2≤12 2x1+x2≤9 x1、x2≥0 解： 2、 min f=10x1+9x2 . 5x1+3x2≥45 x1≥8 x2≤10 x1、x2≥0

求解下列整数规划问题 1、 min f=4x1+3x2+2x3 . 2x1-5x2+3x3≤4 4x1+x2+3x3≥3 x2+x3≥1 x1、x2、x3=0或1 解：最优解（0，0，1），最优值：2 2、 min f=2x1+5x2+3x3+4x3 . -4x1+x2+x3+x4≥2 -2x1+4x2+2x2+4x2≥4 x1+x2-x2+x2≥3 x1、x2、x3、x3=0或1 解：此模型没有可行解。 3、max Z=2x1+3x2+5x3+6x4 . 5x1+3x2+3x3+x4≤30 2x1+5x2-x2+3x2≤20 -x1+3x2+5x2+3x2≤40 3x1-x2+3x2+5x2≤25 x1、x2、x3、x3=正整数 解：最优解（0，3，4，3），最优值：47 4、 min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+ 5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19 约束条件x1 + x2+x3≤30 x4+ x5＋ x6-10 x16≤0 x7+ x8＋ x9-20 x17≤0 x10+ x11＋ x12-30 x18≤0 x13+ x14＋ x15-40 x19≤0 x1 + x4+ x7+x10+ x13＝30 x2 + x5+ x8+x11+ x14＝20 x3 + x6+ x9+x12+ x15＝20 x i为非负数（i=1,2…..8） x i为非负整数（i=9,10…..15） x i为为0－1变量（i=16,17…..19） 解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：860 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：

运筹学整数规划

实验报告 课程名称：___ 运筹学 ____ 项目名称：整数规划问题_ 姓名：__专业：、班级：1班学号：同组成员：_ __ 1注：1、实验准备部分包括实验环境准备和实验所需知识点准备。 2、若是单人单组实验，同组成员填无。

例4.5设某部队为了完成某项特殊任务，需要昼夜24小时不间断值班，但每天不同时段所需要的人数不同，具体情况如表4-4所示。假设值班人员分别在各时间段开时上班，并连续工作8h。现在的问题是该部队要完成这项任务至少需要配备多少名班人员？ 解： 根据题意，假设用i x（i=1,2,3,4,5,6）分别表示第i个班次开始上班的人数， 每个人都要连续值班8h，于是根据问题的要求可归结为如下的整数规划模型：目标函数： i i x z 6 1 min = ∑ = 约束条件： ? ? ? ? ? ? ? ? ? ? ? = ≥） 且为整数（6 ... 1 ,0 x 30 >= x6 + x5 20 >= x5 + x4 50 >= x4 + x3 60 >= x3 + x2 70 >= x2 + x1 60 >= x6 + x1 i i model: sets: num/1,2,3,4,5,6/:b,x; endsets data: b=60,70,60,50,20,30; enddata [obj]min=@sum(num(i):x(i)); x(1)+x(6)>=60; x(1)+x(2)>=70; x(2)+x(3)>=60; x(3)+x(4)>=50; 2注：实验过程记录要包含实验目的、实验原理、实验步骤，页码不够可自行添加。

解： 目标函数： y3*2000-y2*2000-y1*5000-x3*200)-(300+x2*30)-(40+x1*280)-(400=z max 约束条件：???????y3 *300<=x3*2y2*300<=x2*0.5y1*300<=x1*32000<=x3*4+x2+x1*5 model : sets : num/1,2,3/:x,y; endsets [obj]max =(400-280)*x(1)+(40-30)*x(2)+(300-200)*x(3)-5000*y(1)-2000*y(2)-2000*y(3); 5*x(1)+x(2)+4*x(3)<=2000; 3*x(1)<=300*y(1); 0.5*x(2)<=300*y(2); 2*x(3)<=300*y(3); @for (num(i):x(i)>=0;@bin (y(i));); end

运筹学第四章

第 5 次课 2学时 本次课教学重点： 建立数学模型 本次课教学难点： 建立数学模型 本次课教学内容： 第四章线性规划在工商管理中的应用 第一节人力资源分配的问题 例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 班次时间所需人数 1 6：00 ——10：00 60 2 10：00 ——14：00 70 3 14：00 ——18：00 60 4 18：00 ——22：00 50 5 22：00 ——2：00 20 6 2：00 ——6：00 30 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员? 解：设x i( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5≥28 x2 + x3 + x4 + x5 + x6≥15 x3 + x4 + x5 + x6 + x7≥24 x4 + x5 + x6 + x7 + x1≥25 x5 + x6 + x7 + x1 + x2≥19 x6 + x7 + x1 + x2 + x3≥31 x7 + x1 + x2 + x3 + x4≥28 x1,x2,x3,x4,x5,x6,x7≥0 例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？

运筹学经典案例

运筹学经典案例 案例一：鲍德西（（B AWDSEY）雷达站的研究 20世纪30年代，德国内部民族沙文主义及纳粹主义日渐抬头。以希特勒为首的纳粹势力夺取了政权开始为以战争扩充版图，以武力称霸世界的构想作战争准备。欧洲上空战云密布。英国海军大臣丘吉尔反对主政者的“绥靖”政策，认为英德之战不可避免，而且已日益临近。他在自己的权力范围内作着迎战德国的准备，其中最重要、最有成效之一者是英国本土防空准备。 1935年，英国科学家沃森—瓦特（R．Watson-Wart）发明了雷达。丘吉尔敏锐地认识到它的重要意义，并下令在英国东海岸的Bawdsey建立了一个秘密的雷达站。 当时，德国已拥有一支强大的空军，起飞17分钟即可到达英国。在如此短的时间内，如何预警及做好拦截，甚至在本土之外或海上拦截德机，就成为一大难题。雷达技术帮助了英国，即使在当时的演习中已经可以探测到160公里之外的飞机，但空防中仍有许多漏洞，1939年，由曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获诺贝尔奖金的P.M.S.Blachett为首，组织了一个小组，代号为“Blachett 马戏团”，专门就改进空防系统进行研究。 这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官及一名测量人员。研究的问题是：设计将雷达信息传送给指挥系统及武器系统的最佳方式；雷达与防空武器的最佳配置；对探测、信息传递、作战指挥、战斗机与防空火力的协调，作了系统的研究，并获得了成功，从而大大提高了英国本土防空能力，在以后不久对抗德国对英伦三岛的狂轰滥炸中，发挥了极大的作用。二战史专家评论说，如果没有这项技术及研究，英国就不可能赢得这场战争，甚至在一开始就被击败。“Blackett马戏团”是世界上第一个运筹学小组。在他们就此项研究所写的秘密报告中，使用了 “Operational Research”一词，意指作战研究”或“运用研究”。就是我们所说的运筹学。Bawdseg雷达站的研究是运筹学的发祥与典范。项目的巨大实际价值、明确的目标、整体化的思想、数量化的分析、多学科的协同、最优化的结果，以及简明朴素的表述，都展示了运筹学的本色与特色，使人难以忘怀。

运筹学整数规划例题

练习4.9 连续投资问题 某公司现有资金10万元,拟在今后五年考虑用于下列项目的投资: 项目A:从第一年到第四年每年年初需要投资,并于次年收回本利115%,但要求第一年投资最低金额为4万元,第二.三.四年不限. 项目B:第三年初需要投资,到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为5万元. 项目C:第二年初需要投资,到第五年末能收回本利140%,但规定其投资金额或为2万元,或为4万元,或为6万元,或为8万元. 项目D:五年每年年初都可购买公债,于当年末归还,并获利6%,此项目投资金额不限. 试问该公司应图和确定这些项目的每年投资金额,使到第五年末拥有最大的资金收益. (1) x 为项目各年月初投入向量。 (2) ij x 为 i 种项目j 年的月初的投入。 (3) 向量c 中的元素 ij c 为i 年末j 种项目收回本例的百分比。 (4) 矩阵A 中元素 ij a 为约束条件中每个变量ij x 的系数。 (5) Z 为第5年末能拥有的资金本利最大总额。 因此目标函数为 4325max 1.15 1.28 1.40 1.06A B C D Z x x x x =+++ 束条件应是每年年初的投资额应等于该投资者年初所拥有的资金. 第1年年初该投资者拥有10万元资金,故有 11100000A D x x +=. 第2年年初该投资者手中拥有资金只有()116%D x +,故有 22211.06A C D D x x x x ++=. 第3年年初该投资者拥有资金为从D 项目收回的本金: 21.06D x ,及从项目A 中第1年投资收回的本金: 11.15A x ,故有 333121.15 1.06A B D A D x x x x x ++=+ 同理第4年、第5年有约束为 44231.15 1.06A D A D x x x x +=+, 5341.15 1.06D A D x x x =+

运筹学第四章(完整版)

13物流工程3班第四组 组员：李鲁超胡军李康郭优沈西王伟 第四章 1.讨论面向顾客设计思想的重要性。P112-113 顾客需求的多样化和个性化，使得市场演变和产品更新的速度越来越快，产品的生命周期越来越短。通过与顾客的交流，倾听顾客的心声，听取他们对改进产品的建议，以此来分析顾客的需求，挖掘新产品创意。 2.讨论产品开发在企业战略中的重要地位。P135 一、21世纪企业产品设计的背景特征： （1）新产品开发是实现企业竞争战略的需要 技术进步和需求多样化使得产品寿命周期不断缩短，企业面临着缩短交货期、提高产品质量、降低成本和改进服务的多重压力。新产品开发是企业经营战略的核心内容之一，也是生产运作战略的出发点，产品开发智能的目的就是要研究、开发、设计出能满足市场需求并具有竞争力的产品。 （2）技术进步越来越快 科学技术飞速发展，并被迅速而广泛地应用于实践中，推动着新产品的开发，也使得产品更新换代的速度越来越快，产品生命周期越来越短。 （3）用户的要求越来越苛刻 随着时代的发展，大众知识水平的提高和激烈竞争带给市场越来越多、越来越好的产品，使用户的要求越来越高。 （4）产品研制开发的难度越来越大 越来越多的企业认识到新产品开发对企业创造收益的重要性，特别是那些大型、结构复杂，技术含量高的产品在研制中一般都需要各种先进的设计技术。 （5）可持续发展的要求 人类社会在经济快速发展的同时，由于忽略了环境保护，也带来了污染、酸雨、土地沙化，臭氧层破坏等恶果。各国政府将环境保护问题纳入发展战略，这对企业提出了更高的要求。 二、新产品开发的重要性 （1）有利于增强企业的核心竞争力 （2）有利于扩大市场份额 （3）适应个性化定制生产的需要 （4）产品更新换代的需要 3.讨论新产品开发的重要性？P109

运筹学经典案例

案例一：鲍德西（（B AWDSEY）雷达站的研究 20世纪30年代，德国内部民族沙文主义及纳粹主义日渐抬头。以希特勒为首的纳粹势力夺取了政权开始为以战争扩充版图，以武力称霸世界的构想作战争准备。欧洲上空战云密布。英国海军大臣丘吉尔反对主政者的“绥靖”政策，认为英德之战不可避免，而且已日益临近。他在自己的权力范围内作着迎战德国的准备，其中最重要、最有成效之一者是英国本土防空准备。 1935年，英国科学家沃森—瓦特（R．Watson-Wart）发明了雷达。丘吉尔敏锐地认识到它的重要意义，并下令在英国东海岸的Bawdsey建立了一个秘密的雷达站。 当时，德国已拥有一支强大的空军，起飞17分钟即可到达英国。在如此短的时间内，如何预警及做好拦截，甚至在本土之外或海上拦截德机，就成为一大难题。雷达技术帮助了英国，即使在当时的演习中已经可以探测到160公里之外的飞机，但空防中仍有许多漏洞，1939年，由曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获诺贝尔奖金的为首，组织了一个小组，代号为“Blachett马戏团”，专门就改进空防系统进行研究。 这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官及一名测量人员。研究的问题是：设计将雷达信息传送给指挥系统及武器系统的最佳方式；雷达与防空武器的最佳配置；对探测、信息传递、作战指挥、战斗机与防空火力的协调，作了系统的研究，并获得了成功，从而大大提高了英国本土防空能力，在以后不久对抗德国对英伦三岛的狂轰滥炸中，发挥了极大的作用。二战史专家评论说，如果没有这项技术及研究，英国就不可能赢得这场战争，甚至在一开始就被击败。“Blackett马戏团” 是世界上第一个运筹学小组。在他们就此项研究所写的秘密报告中，使用了 “Operational Research”一词，意指作战研究”或“运用研究”。就是我们所说的运筹学。Bawdseg雷达站的研究是运筹学的发祥与典范。项目的巨大实际价值、明确的目标、整体化的思想、数量化的分析、多学科的协同、最优化的结果，以及简明朴素的表述，都展示了运筹学的本色与特色，使人难以忘怀。

运筹学第四章作业的参考答案

第四章作业的参考答案 151P 5、判断下列函数是否为凸函数. （3）3132212 3222126293)(x x x x x x x x x x f ++-++= 解： )(x f 的Hesse 矩阵为 ???? ? ??--=?1862662222)(2 x f . )(2x f ?的各阶主子式分别为 .018 6 2 662224, 07218 66 6, 03418 22 2,086222 ,018,06,02=-->=>=>=-->>> 因而)(2 x f ?为半正定矩阵，所以)(x f 是凸函数。 152 P 9、用0.618法求以下问题的近似解 5060212)(min 230 +-+-=≥t t t t t ? 已知函数的单谷区间]5.3,5.0[,要求最后区间精度8.0=ε。 解：迭代过程用下表给出：

第三轮迭代开始时有ε=<=-=-8.0708.0646.1354.2a b 。所以近似最优解为 084.2*=t 。 152 P 14、求以下无约束非线性规划问题的最优解. （1）212212 2211620)(2)(min x x x x x x x f --+++= 解：化简目标函数，得 .1620223)(21212 221x x x x x x x f --++= 所以，)(x f 的Hesse 矩阵为 ??? ? ??=?4226)(2 x f . 因为)(2x f ?是正定矩阵，所以)(x f 是凸函数。另一方面，目标函数的梯度向量为 .)1624,2026()(1221T x x x x x f -+-+=? 令0)(=?x f ，即 ?? ?=-+=-+0 16240 20261221x x x x ， 求得目标函数的驻点为T x )514,512(* =. 所以，原问题的最优解为T x )5 14,512(*=.

运筹学--第四章 多目标规划汇总

习题四 4.1 分别用图解法和单纯形法求解下述目标规划问题 （1）min z ＝p1（＋）＋p2 st. －x1＋ x2＋ d－1－ d＋1＝1 －0.5x1＋ x2＋ d－2－d＋2＝2 3x1＋3x2＋ d－3－ d＋3＝50 x1，x2≥0；d－i，d＋i≥0（i =1，2，3） （2） min z ＝p1（2＋3）＋p2＋p3 st. x1＋ x2＋d－1－d＋1 ＝10 x1 ＋d－2－d＋2 ＝4 5x1＋3x2＋d－3－d＋3 ＝56 x1＋ x2＋d－4－d＋4 ＝12 x1，x2≥0；d－i，d＋i ≥0（i =1， (4) 4.2 考虑下述目标规划问题 min z ＝p1（d＋1＋d＋2）＋2p2d－4＋p2d－3＋p3d－1 st. x1 ＋d－1－d＋1＝20 x2＋d－2－d＋2＝35 －5x1＋3x2＋d－3－d＋3＝220 x1－x2＋d－4－d＋4＝60 x1，x2≥0；d－i，d＋i ≥0（i =1， (4) （1）求满意解； （2）当第二个约束右端项由35改为75时，求解的变化；

（3）若增加一个新的目标约束：－4x1＋x2＋d－5－d＋5＝8，该目标要求尽量达到目标值，并列为第一优先级考虑，求解的变化； （4）若增加一个新的变量x3，其系数列向量为（0，1，1，－1）T，则满意解如何变化？ 4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律，该台每天允许广播12小时，其中商业节目用以赢利，每小时可收入250美元，新闻节目每小时需支出40美元，音乐节目每播一小时费用为17.50美元。法律规定，正常情况下商业节目只能占广播时间的20％，每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下： P1：满足法律规定要求； P2：每天的纯收入最大。 试建立该问题的目标规划模型。 4.4 某企业生产两种产品，产品Ⅰ售出后每件可获利10元，产品Ⅱ售出后每件可获利8元。生产每件产品Ⅰ需3小时的装配时间，每件产品Ⅱ需2小时装配时间。可用的装配时间共计为每周120小时，但允许加班。在加班时间内生产两种产品时，每件的获利分别降低1元。加班时间限定每周不超过40小时，企业希望总获利最大。试凭自己的经验确定优先结构，并建立该问题的目标规划模型。 4.5 某厂生产A、B两种型号的微型计算机产品。每种型号的微型计算机均需要经过两道工序I、II。已知每台微型计算机所需要的加工时间、销售利润及工厂每周最大加工能力的数据如下： A B每周最大加工能力 I 4 6 150 II 3 2 70 利润（元/台）300 450 工厂经营目标的期望值及优先级如下： P1：每周总利润不得低于10000元；

《管理运筹学》第三版案例题解

《管理运筹学》案例题解 案例1：北方化工厂月生产计划安排 解：设每月生产产品i （i=1，2，3，4，5）的数量为X i ，价格为P 1i ，Y j 为原材料j 的数量，价格为P 2j ，a ij 为产品i 中原材料j 所需的数量百分比，则： 5 10.6j i ij i Y X a ==∑ 总成本：TC=∑=15 1 2j j j P Y 总销售收入为：5 11 i i i TI X P ==∑ 目标函数为：MAX TP （总利润）=TI-TC 约束条件为： 10 30 24800215 1 ?? ?≤∑=j j Y X 1+X 3=0.7∑=5 1 i i X X 2≤0.05∑=5 1 i i X X 3+X 4≤X 1 Y 3≤4000 X i ≥0,i=1,2,3,4,5 应用计算工具求解得到： X 1=19639.94kg X 2=0kg X 3=7855.97kg X 4=11783.96kg X 5=0kg 最优解为：348286.39元

案例2：石华建设监理工程师配置问题 解：设X i 表示工地i 在标准施工期需要配备的监理工程师，Y j 表示工地j 在高峰施工期需要配备的监理工程师。 约束条件为： X 1≥5 X 2≥4 X 3≥4 X 4≥3 X 5≥3 X 6≥2 X 7≥2 Y 1+Y 2≥14 Y 2+Y 3≥13 Y 3+Y 4≥11 Y 4+Y 5≥10 Y 5+Y 6≥9 Y 6+Y 7≥7 Y 7+Y 1≥14 Y j ≥ X i （i=j ，i=1,2,…,7） 总成本Y 为： Y=∑=+7 1)12/353/7(i i i Y X 解得 X 1=5；X 2=4；X 3=4；X 4=3；X 5=3；X 6=2；X 7=2； 1Y =9；2Y =5；3Y =8；4Y =3；5Y =7；6Y =2；7Y =5; 总成本Y=167.

运筹学第4章整数规划习题.doc

第四章 整数规划 4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A 、材料B ，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解） 解：设生产甲、乙这两种设备的数量分别为x 1、x 2，由于是设备台数，则其变量都要求为整数，建立模型如下： 2123max x x z += ????? ? ?≥≤+≤+为整数 21212121,0,5 .45.01432x x x x x x x x 4.2 2197max x x z += ??? ??≥≤+≤+-且为整数 0,35 76 3.212121x x x x x x t s 割平面法求解。（下表为最优表） 线性规划的最优解为： 63max ,0,2/7,2/94321=====z x x x x 由最终表中得： 2 7 221227432=++ x x x ④ 将系数和常数项分解成整数和非负真分式之和，上式化为； 2 132********+=++x x x 移项后得： ①②③④ ①②③

即： 2 1221227212212274343-≤--→≥+x x x x 只要把增加的约束条件加到B 问题的最优单纯形表中。 由x 1行得： 7 32 7171541= -+ x x x 将系数和常数项分解成整数和非负真分数之和： 74476715541+=+-+x x x x 得到新的约束条件： 74 767154-≤--x x 7 47671654-=+--x x x 在的最优单纯形表中加上此约束，用对偶单纯形法求解： 则最优解为3,421 ==x x ，最优目标函数值为z *=55。 4.3 max z ＝4x 1＋3x 2＋2x 3

运筹学实例分析及lingo求解

运筹学实例分析及lingo 求解 一、线性规划 某公司有6个仓库，库存货物总数分别为60、55、51、43、41、52，现有8个客户各要一批货，数量分别为35，37，22，32，41，32，43，38。各供货仓库到8个客户处的单位货物运输价见表 试确定各仓库到各客户处的货物调运数量，使总的运输费用最小。 解：设 ij x 表示从第i 个仓库到第j 个客户的货物运量。ij c 表示从第i 个仓库到第 j 个客户的单位货物运价，i a 表示第i 个仓库的最大供货量，j d 表示第j 个客户的订货量。 目标函数是使总运输费用最少，约束条件有三个：1、各仓库运出的货物总量不超过其库存数2、各客户收到的货物总量等于其订货数量3、非负约束 数学模型为： ∑∑===6 18 1)(min i j ij ij x c x f ????? ??????≥===≤∑∑==08,,2,1,6,2,1,,. .6 1 8 1ij j i ij i j ij x j d x i a x t s ΛΛ 编程如下： model : Sets : Wh/w1..w6/:ai; Vd/v1..v8/:dj;

links(wh,vd):c,x; endsets Data: ai=60,55,51,43,41,52; dj=35,37,22,32,41,32,43,38; c=6,2,6,7,4,2,5,9 4,9,5,3,8,5,8,2 5,2,1,9,7,4,3,3 7,6,7,3,9,2,7,1 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3; Enddata Min=@sum(links(i,j):c(i,j)*x(i,j)); @for(wh(i):@sum(vd(j):x(i,j))<=ai(i)); @for(vd(j):@sum(wh(i):x(i,j))=dj(j)); end Global optimal solution found. Objective value: Total solver iterations: 0 Variable Value Reduced Cost AI( W1) AI( W2) AI( W3) AI( W4) AI( W5) AI( W6) DJ( V1) DJ( V2) DJ( V3) DJ( V4) DJ( V5) DJ( V6) DJ( V7) DJ( V8) C( W1, V1) C( W1, V2) C( W1, V3) C( W1, V4) C( W1, V5) C( W1, V6) C( W1, V7)

运筹学第四章答案

4.1 工厂生产甲、乙两种产品，由Ａ、Ｂ二组人员来生产。Ａ组人员熟练工人比较多，工作效率高，成本也高；Ｂ组人员新手较多工作效率比较低，成本也较低。例如，A 组只生产甲产品时每小时生产10件，成本是50元有关资料如表4.21所示。 班生产的产品每件增加成本5元。 工厂根据市场需求、利润及生产能力确定了下列目标顺序： P 1：每周供应市场甲产品400件，乙产品300件 P 2：每周利润指标不低于500元 P 3：两组都尽可能少加班，如必须加班由Ａ组优先加班 建立此生产计划的数学模型。 4.1【解】 解法一：设x 1, x 2分别为A 组一周内正常时间生产产品甲、乙的产量，x 3, x 4分别为A 组一周内加班时间生产产品甲、乙的产量；x 5, x 6分别为B 组一周内正常时间生产产品甲、乙的产量，x 7, x 8分别为B 组一周内加班时间生产产品甲、乙的产量。 总利润为 135713572468246812345678 80()(50554550)75()(45504045)3030252535353030x x x x x x x x x x x x x x x x x x x x x x x x +++-+++++++-+++=+++++++ 生产时间为 A 组：12340.10.1250.10.125x x x x +++ B 组：56780.1250.20.1250.2x x x x +++ 数学模型为： 112233454671357112468221 234567833124456553min ()()(2) 400300 3030252535353030500 0.10.12540 0.1250.2400.10.Z p d d p d p d d p d d x x x x d d x x x x d d x x x x x x x x d d x x d d x x d d x ---++++ +-+-+ =++++++++++-=++++-=++++++++-=++-=++-=+－－ －－－466 787712510 0.1250.2100,,0,1,2,,7;1,2,,8j i i x d d x x d d x d d i j -+-+-+??????????+-=? ?++-=?≥≥==?? 解法二：设x 1, x 2分别为A 组一周内生产产品甲、乙的正常时间，x 3, x 4分别为A 组一周内 生产产品甲、乙的加班时间；x 5, x 6分别为B 组一周内生产产品甲、乙的正常时间，x 7, x 8分别为B 组一周内生产产品甲、乙的加班时间。 数学模型请同学们建立。 4.2设x ij 为A i 到B j 的运量，数学模型为

运筹学实验报告四整数规划

2018-2019学年第一学期 《运筹学》 实验报告（四） 班级：交通运输171 学号： 1000000000 姓名： ***** 日期： 2018.11.22

实验一： 用Lingo 软件求解下列整数规划问题（要求附程序和结果） 12 121212max 2506221 0,1,2i z x x x x x x x x x i =++≤?? -+≤?? +≤??≥=?且取整数 12312323123123 123max 232 45 2244 ,,01 z x x x x x x x x x x x x x x x x x =+-++≤??+≤?? +-≤??+-≤?=??或 解：例题（左）解题程序及运行结果如下： sets : bliang/1,2/:x,a; yshu/1,2,3/:b; xshu(yshu,bliang):c; endsets data : a=2,1; b=5,0,21; c=1,1 -1,1 6,2; enddata max =@sum (bliang(i):a(i)*x(i)); @for (yshu(j):@sum (bliang(i):x(i)*c(j,i))<=b(j)); @for(bliang(i):@gin(x(i))); Global optimal solution found. Objective value: 7.000000 Objective bound: 7.000000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X( 1) 3.000000 -2.000000 X( 2) 1.000000 -1.000000 A( 1) 2.000000 0.000000

第六章运筹学整数规划案例教材

第六章整数规划 6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。 1、 max z=3x1+2x2 S.T. 2x1+3x2≤12 2x1+x2≤9 x1、x2≥0 解： 2、 min f=10x1+9x2 S.T. 5x1+3x2≥45 x1≥8 x2≤10 x1、x2≥0

6.2 求解下列整数规划问题 1、 min f=4x1+3x2+2x3 S.T. 2x1-5x2+3x3≤4 4x1+x2+3x3≥3 x2+x3≥1 x1、x2、x3=0或1 解：最优解（0，0，1），最优值：2 2、 min f=2x1+5x2+3x3+4x3 S.T. -4x1+x2+x3+x4≥2 -2x1+4x2+2x2+4x2≥4 x1+x2-x2+x2≥3 x1、x2、x3、x3=0或1 解：此模型没有可行解。 3、max Z=2x1+3x2+5x3+6x4 S.T. 5x1+3x2+3x3+x4≤30 2x1+5x2-x2+3x2≤20 -x1+3x2+5x2+3x2≤40 3x1-x2+3x2+5x2≤25 x1、x2、x3、x3=正整数 解：最优解（0，3，4，3），最优值：47 4、min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+ 5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19 约束条件x1 + x2+x3≤30 x4+ x5＋x6-10 x16≤0 x7+ x8＋x9-20 x17≤0 x10+ x11＋x12-30 x18≤0 x13+ x14＋x15-40 x19≤0 x1 + x4+ x7+x10+ x13＝30 x2 + x5+ x8+x11+ x14＝20 x3 + x6+ x9+x12+ x15＝20 x i为非负数（i=1,2…..8） x i为非负整数（i=9,10…..15） x i为为0－1变量（i=16,17…..19） 解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：860 6.3 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：