运筹学第四章

运筹学第四章习题答案

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)单纯形法

0 0 P1 0 0 P2 P3 P3

CB XB x1 x2 b P3

P2

6 2 0 0 0 0 -1 1 24

5

15

2 1 0 0 -1 1 0 0

5 0 -1 1 0 0 0 0

P1

P2

P3

0 0 1 0 0 0 0 0

-1 -1 0 0 1 0 0 0

-6 -2 0 0 0 0 2 0

P3

P2

0 x1

0 2 1.2 -1.2 0 0 -1 1 6

2

3

0 1 0.2 0.2 -1 1 0 0

1 0 -0.

2 0.2 0 0 0 0

P1

P2

P3

0 0 1 0 0 0 0 0

0 -1 -0.2 0.2 1 0 0 0

0 -2 -1.2 1.2 0 0 2 0

P3

x2

x1

0 0 0.8 -0.8 2 -2 -1 1 2

2

3

0 1 0.2 -0.2 -1 1 0 0

1 0 -0.

2 0.2 0 0 0 0

P1

P2

P3

0 0 1 0 0 0 0 0

0 0 0 0 0 1 0 0

0 0 -0.8 0.8 -2 2 2 0

x2

x1

0 0 0.4 -0.4 1 -1 -0.5 -0.5 1

3

3

0 1 0.6 -0.6 0 0 0.5 0.5

1 0 -0.

2 0.2 0 0 0 0

P1

P2

P3

0 0 1 0 0 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 1 1

x2

2 0 0 0 1 -1 -0.5 -0.5 7

12

5

3 1 0 0 0 0 0.5 0.5

5 0 -1 1 0 0 0 0

P1

P2

P3

0 0 1 0 0 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 1 1

故该问题的解为)312,3()3,3()12,0(21221a a a a a +=+ )1,0,(2121=+≥a a a a

（2）

P2

P3

P1

P4

P1

1.5P

4

CB XB x1 x2

b

0 1 1 -1 1 0

0 0 0 0 0 40

1 1 0 0 -1 1 0 0 0 0 100

1 0 0 0 0 0 -1 1 0

0 30

1

-1

1

15

P1 0 0 0 0 0 0 1 0 1 0

P2

1

P3 -1 -1

1 0

0 0

P4

-1

1.5 0

0 1 0 -1 1 0 0 0 0 1 -1 25

1 0 0 0 -1 1 0 0 1 -1 85

1 0 0 0 0 0 -1 1 0 0 30 0

x2 0 1

15

P1 0 0 0

0 0 0 1 0 1 0

P2

0 0

-1 0

P3 -1 0

1

-1 1 P4 -1 0

0 51 0 x1

1

0 -1 1 0 0 0 0 1 -1

1

-1

-1

1

0 0 1 -1 0 0 -1 1 -1 1 30 0 x2 0 1 0 0 0 0 0 0 0 0 P1 0 0 0 0 0 0 1 0 1 0 P2 0 0 1 0 0 0 0 0 0 0 P3 0 0 -1 1 1 0 0 0 0 0

P4

-1

1

1

1.5

4.3某商标的酒是用三种等级的酒兑制而成。这三种等级的酒每天供应量和单位成本见表4-20.三种商标的成品酒的兑制要求和售价见表4-21.决策者规定：首先必须严格按规定的比例兑制各商标的酒；其次是获利最大；再次是红商标的酒每天至少生产2000千克。试列出数学模型。

表4-20

表4-21

设x ij 代表等级i 的酒投入第j （1红，2黄，3蓝）种商标酒兑制的数量

{}-

+--2

2111),(min d p d d p

1300131211≤++x x x 2000232221≤++x x x 1000333231≤++x x x 09.01.01.0312111≤+--x x x 05.05.05.0312111≥--x x x

08.125.23.05.02.15.011333231232221131211=-+++++++---+-d d x x x x x x x x x

200022312111=-++++

-d d x x x

4.4判别下列表4-22和表4-23是否是表上作业法求解的运输问题的基可行解。 表4-22

此表不是表上作业求解法的运输问题的基可行解，

因为基变量的个数=3+4-1=6与表中基变量数为7不符。

表4-23

此表不是表上作业求解法的运输问题的基可行解

因为基变量的个数=6+4-1=9与表中基变量数为8不符。

4.5用表上作业法求表4-24和表4-25中各处的运输问题的最优解。

表4-24

表4-25

用沃格尔法求最优方案：

4.6表4-26给出了一个运输问题及它的一个解，试问

（1）表中给出的解是否为最优解？请用位势法进行检验。

（2）若价值系数C24由1变为3，所给出的解是否仍为最优解？若不是，请求出最优解。（3）若所有价值系数均增加1，最优解是否改变？为什么？

（4）若所有价值系数均乘以2，最优解是否改变？为什么？

表4-26

(1)

因为检验数都大于等于0，所以表中解为最优解。（2）

因为e21小于0，所以此解不为最优解。

不变，因为因为检验数都大于等于0，所以表中最优解不变

（4）

4.7甲，乙，丙三个城市每年需要煤炭分别为320万吨，250万吨，350万吨，由A,B两处煤炭负责供应。已知煤炭供应量分别为400万吨，450万吨。由煤矿至各城市的单位运价（万/万吨）如表4-27所示。由于需求大于供应，所以决定佳城市供应量可减少0~30万吨，宜城市需求量必须全部满足，并称是供应量不少于270万吨。试求总运费最低的调运方案（将可供煤炭量用完）

表4-27

运筹学第四章多目标规划

习题四 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班学号：同组成员：_ __ 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天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？

运筹学第四章(完整版)

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

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

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

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

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

第四章作业的参考答案 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．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员 解：设x i( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：. 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 约束条件：. 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

运筹学第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

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

《运筹学》第四章习题 一、思考题 1．运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最 多等于1-+n m ？ 2． 用左上角法确定运输问题的初始基本可行解的基本步骤是什么？ 3． 最小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到 运输问题的最优方案？ 4． 沃格尔法（V ogel 法）的基本思想是什么？它和最小元素法相比给出的运输问题的 初始基本可行解哪一个更接近于最优解？为什么？ 5． 试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什 么？ 6． 用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回路？这闭 回路是否是唯一的？ 7． 试述用位势法求检验数的原理、步骤和方法。 8． 试给出运输问题的对偶问题（对产销平衡问题）。 9． 如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输 问题。 10．一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？ 11．试述在表上作业法中出现退化解的涵义及处理退化解的方法。 二、判断下列说法是否正确 1．运输问题模型是一种特殊的线性规划模型，所以运输问题也可以用单纯形方法求解。 2．因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有唯一最优解；有无穷多个最优解；无界解；无可行解。 3．在运输问题中，只要给出一组（1-+n m ）个非零的 {}j i x ，且满足 ∑==n j i j i a x 1，∑==m i j j i b x 1，就可以作为一个基本可行解。 4．表上作业法实质上就是求解运输问题的单纯形法。 5．按最小元素法或元素差额法给出的初始基本可行解，从每一空格出发都可以找到一闭回路，且此闭回路是唯一的。 6．如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案将不会发生变化。 7．如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k ，最优调运方案将不会发生变化。 8．用位势法计算检验数时，先从某一行（或列）开始，给出第一个位势的值，这个先给出的位势值必须是正的。 9．用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每一个空格的检验数是唯一的。 10．当所有产地的产量和销地的销量都是整数时，运输问题的最优解也是整数。 三、求解下列产销平衡的运输问题，下表中列出的为产地到销地之间的运价。 （1）用左上角法、最小元素法、沃格尔法求初始基本可行解； （2）由上面所得的初始方案出发，应用表上作业法求最优方案，并比较初始方案需要

运筹学第四章答案

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

运筹学第四章

第 5 次课 2学时 本次课教学重点: 建立数学模型 本次课教学难点: 建立数学模型 本次课教学内容: 第四章 线性规划在工商管理中的应用 第一节 人力资源分配的问题 例1.某昼夜服务的公交线路每天各时间段内所需司机与乘务人员数如下: 问该公交线路怎样安排司机与乘务人员,解:设 x i 56712 x 6 + x 7 + x 1 + x 2 + x 3 ≥ 31 x 7 + x 1 + x 2 + x 3 + x 4 ≥ 28 x 1,x 2,x 3,x 4,x 5,x 6,x 7 ≥ 0 例2.一家中型的百货商场,它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息,售货人员每周工作5天,休息两天,并要求休息的两天就是连续的。问应该如何安排售货人员的作息,既满足工作需要,又使配备的售货人员的人数最少？ 解:设 x 第二节 生产计划的问题 例3.某公司面临一个就是外包协作还就是自行生产的问题。该公司生产甲、乙、丙三种产品,都 需要经过铸造、机加工与装配三个车间。甲、乙两种产品的铸件可以外包协作,亦可以自行生产,但产品丙必须本厂铸造才能保证质量。数据如表。问:公司为了获得最大利润,甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中,由本公司铸造与由外包协作各应多少件？ 解

产品乙全部自制的利润=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设备上加工;Ⅲ只能在A 解: 型: s、 ) ) 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 种下料方案,见下表