1
管理运筹学高等教育出版社第三版韩伯棠
管理运筹学作业
第二章线性规划的图解法
P23：Q2：（1）－（6）；Q3：(2)
Q2：用图解法求解下列线性规划问题，并指出哪个问题具有唯一最优解，无穷多最优解，无界解或无可行解。
（1）Min f＝6X1+4X2
约束条件：2X1+X2>=1,
3X1+4X2>=3
X1, X2>=0
解题如下：如图1
Min f＝3.6
X1=0.2, X2=0.6
本题具有唯一最优解。
图1
（2）Max z＝4X1+8X2
约束条件：2X1+2X2<=10
-X1+X2>=8
X1,X2>=0
解题如下：如图2：
Max Z 无可行解。
图2
1
2
2
（3） Max z ＝X1+X2 约束条件 8X1+6X2>=24 4X1+6X2>=-12 2X2>=4 X1,X2>=0 解题如下：如图3： Max Z=有无界解。
图3
（4） Max Z ＝3X1-2X2 约束条件：X1+X2<=1 2X1+2X2>=4 X1,X2>=0 解题如下：如图4： Max Z 无可行解。
图
4
3
(5)Max Z＝3X1+9X2
约束条件：X1+3X2<=22
-X1+X2<=4
X2<=6
2X1-5X2<=0
X1,X2>=0
解题如下：如图5：
Max Z =66；X1=4 X2=6
本题有唯一最优解。
图5
(6)Max Z=3X1+4X2
约束条件：-X1+2X2<=8
X1+2X2<=12
2X1+X2<=16
2X1-5X2<=0
X1,X2>=0
解题如下：如图6
Max Z =30.669
X1=6.667 X2=2.667
本题有唯一最优解。
3
4
图6
Q3：将线性规划问题转化为标准形式
（2）min f＝4X1+6X2
约束条件：3X1-2X2>=6
X1+2X2>=10
7X1-6X2=4
X1,X2>=0
解题如下：1）目标函数求最小值化为求最大值：目标函数等式左边min改为max，等式右边各项均改变正负号。2）决策变量非负化：若Xi≤0，令Xi=－Xia，（Xia≥0）；若Xi无约束，令Xi=Xia－Xib，（Xia≥0，Xib≥0）；将上述替换变量代入目标函数和约束条件。3）约束条件不等式化为等式：不等号为≤的，不等式左边加松弛变量；不等号为≥的，不等式左边减剩余变量。4）常数项为非负。
本题标准化如下：
令：z＝-f，则：
Max z＝min (-f)= -4X1-6X2+0X3+0X4
所以：
Max z＝-4X1-6X2+0X3+0X4
约束条件：3X1-2X2-X3+0X4＝6
X1+2X2+0X3-X4=10
7X1-6X2+0X3+0X4=4
X1,X2,X3,X4>=0
4
5
第三章线性规划问题的计算机求解
P37: Q4; P38:Q5
Q4：考虑下面的线性规划问题：
Max Z＝2X1+X2-X3+X4
约束条件：X1-X2+2X3+X4>=2
X1-3X2+X3-X3-X4<=4
2X2+X3+2X4<=3
X1,X2,X3,X4>=0
计算机结果输出如下：
**********************最优解如下*************************
目标函数最优值为: 18.5
变量最优解相差值
------- -------- --------
x1 8.5 0
x2 1.5 0
x3 0 4.5
x4 0 4
约束松弛/剩余变量对偶价格
------- ------------- --------
1 5 0
2 0 2
3 0 3.5
目标函数系数范围:
变量下限当前值上限
------- -------- -------- --------
x1 .2 2 无上限
x2 -3 1 无上限
x3 无下限 1 5.5
x4 无下限 1 5
常数项数范围:
约束下限当前值上限
------- -------- -------- --------
1 无下限
2 7
2 -1 4 无上限
3 0 3 无上限
回答下列问题：
（1）请指出其最优解及其最优目标值。
（2）那些约束条件起到了约束作用，它们的对偶价格各为多少，请给予说明。
（3）如果请你选择一个约束条件，将它的常数项增加一个单位，你将选择哪一个约束条件，这时候最优目标函数值是多少？
（4）请问在目标函数中X3的系数在什么范围内变化时，其最优解不变，这时其最优目标函数值是否会发生变化，为什么？
（5）请问在目标函数中X1的系数在什么范围内变化时，其最优解不变，这时其最优目
5
6
标函数值是否会发生变化，为什么？
解题如下：
答：（1）其最优解是X1=8.5;X2=1.5;X3=0;X4=0；最优目标值是MaxZ=18.5
（2）约束条件2、3起到了约束的作用，它们的对偶价格分别为2和3.5。
（3）因为求目标函数值MaxZ，因选择约束条件3的对偶价格为3.5，当该约束条件改善一个单位时，目标函数最大值改善3.5。这时目标函数最大值为18.5+3.5＝22。
（4）计算机输出结果可知，当X3的系数在（－∞，5.5）范围内变化时，其最优解不变。且这时其最优目标函数值不会发生变化。因为输出结果中X3=0。
（5）计算机输出结果可知，当X1的系数在（0.2，∞）范围内变化时，其最优解不变。因X1=8.5为最优解，因此目标函数值会随着X1的变化而改变。
Q5、考虑下面线性规划问题：
MinZ＝16X1+16X2+17X3;
约束条件：X1+X2<=30
0.5X1-X2+6X3>=15
3X1+4X2-X3>=20
X1,X2,X3>=0
计算机输出结果如下：
**********************最优解如下*************************
目标函数最优值为: 148.916
变量最优解相差值
------- -------- --------
x1 7.297 0
x2 0 .703
x3 1.892 0
约束松弛/剩余变量对偶价格
------- ------------- --------
1 22.703 0
2 0 -3.622
3 0 -4.73
目标函数系数范围:
变量下限当前值上限
------- -------- -------- --------
x1 1.417 16 16.565
x2 15.297 16 无上限
x3 14.4 17 192
常数项数范围:
约束下限当前值上限
------- -------- -------- --------
1 7.297 30 无上限
2 3.33
3 15 435
3 -2.5 20 90
回答如下问题：
（1）第二个约束方程的对偶价格是一个负数（-3.622），它的含义是什么？
6
7
（2）X2的相差值为0.703，它的含义是什么。
（3）当目标函数中X1的系数从16降为15，而X2的系数从16升为18时，最优解是否会发生变化？会发生变化。
（4）当第一个约束条件的常数项从30变为15，而第二个常数项从15变为80时，你能断定其对偶价格是否会发生变化，为什么？会。384.32
解题如下：
答：（1）第二个约束方程的对偶价格是一个负数（-3.622），其含义是如果把约束条件2的下限15增加1，那么最优目标函数值将增加3.622。即148.916+3.622＝152.538 （2）决策变量最优解非零，则相差值为0；决策变量最优解为零，则存在正数相差值。相差值表示为使得相应的决策变量参加最优生产组合（最优解取正），其价值系数至少需要增加的量（max型目标函数）或其价值系数至少需要减少的量（min型目标函数）。X2的相差值为0.703，它的含义是X2的系统需要减少0.703，即16－0.703＝15.297，此时的目标函数值为148.919.
(3) 当目标函数中X1的系数从16降为15，而X2的系数从16升为18时，最优解不会发生变化，但是目标函数最优值会发生变化。因为X1在（1.417, 16.565）和X2在(15.297, )范围内变化时，最优解不会发生变化。只是会影响目标函数最优值变化。
（4）当第一个约束条件的常数项从30变为15，而第二个常数项从15变为80时，对偶价格不会发生变化。对偶价格是某种资源在最佳生产组合的基础上，每增加一个单位产生的最优目标值的改进量。常数项的变化只对目标函数最优解产生影响，对偶价格不会产生变化。
第四章线性规划在工商管理中的应用
作业：P57-58，Q2,Q3
Q2：某快餐店座落在一个旅游景点中。该景点远离市区，平时顾客不多，而在每个周六顾客猛增。该店主要为顾客提供低价位的快餐服务。该店雇佣2名正式工，每天工作8小时。其余工作由临时工担任，临时工每天工作4小时。周六营业时间11:00a.m-22:00p.m。根据就餐情况，在周六每个营业小时所需的职工数如表（包括正式工和临时工）。
已知一名正式工从11点上班，工作4小时后休息1小时，而后在工作4小时。另外一名正式工13点上班，工作4小时后，休息1小时，在工作4小时。又知临时工每小时工资4元。
（1）、满足对职工需求的条件下，如何安排临时工的班次，使得临时工成本最小。
（2）、这时付给临时工的工资总额是多少，一共需要安排多少临时工班次。请用剩余变量来说明应该安排一些临时工的3小时工作时间的班次，可使得总成本更小。
（3）、如果临时工每班工作时间可以是3小时，也可以是4小时，那么如何安排临时工的班次，使得临时工总成本最小。这样比（1）节省多少费用，这时要安排多少临时工班次。
解题如下：
7
8
(1)临时工的工作时间为4小时，正式工的工作时间也是4小时，则第五个小时需要新招人员，临时工只要招用，无论工作多长时间，都按照4小时给予工资。每位临时工招用以后，就需要支付16元工资。从上午11时到晚上10时共计11个班次，则设Xi(i
=1,2,…,11)个班次招用的临时工数量，如下为最小成本：
minf＝16（X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11)
两位正式工一个在11－15点上班，在15－16点休息，然后在16－20点上班。另外一个在13－17点上班，在17－18点休息，18－22点上班。则各项约束条件如下：
X1+1>=9
X1+X2+1>=9
X1+X2+X3+2>=9
X1+X2+X3+X4+2>=3
X2+X3+X4+X5+1>=3
X3+X4+X5+X6+2>=3
X4+X5+X6+X7+2>=6
X5+X6+X7+X8+1>=12
X6+X7+X8+X9+2>=12
X7+X8+X9+X10+1>=7
X8+X9+X10+X11+1>=7
Xi>=0(i＝1,2, (11)
运用计算机解题，结果输出如下;
**********************最优解如下*************************
目标函数最优值为: 320
变量最优解相差值
------- -------- --------
x1 8 0
x2 0 0
x3 1 0
x4 0 0
x5 1 0
x6 4 0
x7 0 0
x8 6 0
x9 0 0
x10 0 1
x11 0 1
目标函数最优值为: 320
这时候临时工的安排为：
变量班次临时工班次时间
------- -------- --------
x1 8 11：00－12：00
x2 0 12：00－13：00
x3 1 13：00－14：00
x4 0 14：00－15：00
8
9
x5 1 15：00－16：00
x6 4 16：00－17：00
x7 0 17：00－18：00
x8 6 18：00－19：00
x9 0 19：00－20：00
x10 0 20：00－21：00
x11 0 21：00－22：00
（2）付出工资总额为：
Minf＝16（X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11)
＝16（8+0+1+0+1+4+0+6+0+0+0)=320元
共需要安排20个临时工班次。
说明如下：
根据计算机输出结果如下：
**********************最优解如下*************************
目标函数最优值为: 320
变量最优解相差值班次
------- -------- --------
x1 8 0 11：00
x2 0 0 12：00
x3 1 0 13：00
x4 0 0 14：00
x5 1 0 15：00
x6 4 0 16：00
x7 0 0 17：00
x8 6 0 18：00
x9 0 0 19：00
x10 0 1 20：00
x11 0 1 21：00
约束松弛/剩余变量对偶价格
------- ------------- --------
1 0 -1 8
2 0 0 0
3 2 0 1
4 8 0 0
5 0 -1 1
6 5 0 4
7 1 0 0
8 0 0 6
9 0 -1 0
10 0 0 0
11 0 0 0
9
10
从输出结果看出：在11：00－12：00安排8个临时工的班次在14：00－15：00的剩余变量为8，因为临时工的工作时间为4小时，而实际工作仅需要3小时。在13：00－14：00招用的临时工，剩余变量为2，在16：00－17：00招用的临时工，剩余变量为5。都是因为实际工作要求达不到4小时。这部分费用为4小时工作时长不合理多支出的成本。因此建议安排3小时工作时长的临时工，可以是成本更小。
（3）根据题意，在满足工作需要的条件下，可以安排3小时或者4小时的临时工，工资仍然为4元/小时。则这时候确定安排为4小时的临时工工资为16元，安排为3小时的为12元，设每个班次安排的4小时临时工为Xi，3小时临时工为Yi，（i＝1，2，…,11)，则成本最小：
Minf＝16（X1+X2+…+X11)+12(Y1+Y2+…+Y11)
列出约束条件如下;
X1+Y1+1>=9
X1+X2+Y1+Y2+1>=9
X1+X2+X3+Y1+Y2+Y3+2>=9
X1+X2+X3+X4+ Y2+Y3+ Y4+2>=3
X2+X3+X4+X5+ Y3+Y4+Y5+1>=3
X3+X4+X5+X6+ Y4+Y5+Y6+2>=3
X4+X5+X6+X7+ Y5+Y6+Y7+1>=6
X5+X6+X7+X8+ Y6+Y7+Y8+2>=12
X6+X7+X8+X9+ Y7+Y8+Y9+2>=12
X7+X8+X9+X10+ Y8+Y9+Y10+1>=7
X8+X9+X10+X11+Y9+Y10+X11+1>=7
Xi>=0, Yi>=0 (i＝1,2, (11)
计算机输出结果为：
目标函数最优值为: 264
变量最优解相差值
------- -------- --------
x1 0 4
x2 0 4
x3 0 4
x4 0 4
x5 0 0
x6 0 4
x7 0 4
x8 6 0
x9 0 4
x10 0 12
x11 0 12
x12 8 0
x13 0 8
x14 1 0
x15 0 0
x16 1 0
10
11
x17 0 8
x18 4 0
x19 0 0
x20 0 0
x21 0 8
x22 0 8
目标函数最优解为264元，即最小成本为264元，比（1）节省56元。需要安排20个班次。即：4小时临时工安排6个班次：X8=6；3小时临时工16个班次：Y1(X12)=8，Y3(X14)=1，Y5(X16)=1，Y7(X18)=4。
1、在资源限量集市场容量运行条件下，如何安排生产使获利最多。
2、说明A,B,C三种产品的市场容量的对偶价格以及材料、台时的对偶价格的含义，并对其进行灵敏度分析。如要开拓市场应当首先开拓那种产品的市场。如要增加资源，则应在什么价位上增加机器台时数和材料数量。
解题如下：
(1) 设X1,X2,X3分别代表A,B,C产品生产的数量，则获利最多公式如下：
MaxZ＝10X1+12X2+14X3
约束条件为：
X1+1.5X2+4X3<=2000
2X1+1.2X2+X3<=1000
X1<=200
X2<=250
X3<=100
X1>=0,X2>=0,X3>=0
计算机计算输出结果如下：
**********************最优解如下*************************
目标函数最优值为: 6400
变量最优解相差值
------- -------- --------
x1 200 0
x2 250 0
x3 100 0
约束松弛/剩余变量对偶价格
------- ------------- --------
1 1025 0
2 200 0
3 0 10
11
12
4 0 12
5 0 14
目标函数系数范围:
变量下限当前值上限
------- -------- -------- --------
x1 0 10 无上限
x2 0 12 无上限
x3 0 14 无上限
常数项数范围:
约束下限当前值上限
------- -------- -------- --------
1 975 2000 无上限
2 800 1000 无上限
3 0 200 300
4 0 250 416.667
5 0 100 300
因此在资源数量和市场容量允许情况下，安排A产品生产200个，B产品生产250个，C 产生产100个能够获利最多，获利为6400元。
（2）对偶价格：A产品的对偶价格为10元，B 产品的对偶价格为12元，C产品的对偶价格为14元，材料的对偶价格为0，台时的对偶价格为0.
灵敏度分析：因市场容量有限，因此增加材料和台时都不能是获利增加。如果A产品市场容量每增加1，则可以使获利增加10元。如果B产品市场容量每增加1，则可以使获利增加12元。如果C产品市场容量每增加1，则可以使获利增加14元。
因C产品单个产品获利14元，获利最多，因此如果开拓市场容量，就开拓C产品容量。增加资源时：材料资源在975向上增加，台时资源在800个向上增加。
第八章整数规划
作业：P180 Q1
Q1：
（1）max z＝5X1+8X2
约束条件：X1+X2<=6
5X1+9X2<=45
X1,X2>=0，且为整数。
解题如下：计算机输出结果：
**********************最优解如下*************************
目标函数最优值为: 40
变量最优解
------- --------
x1 0
x2 5
12
13
约束松弛/剩余
------- ---------
1 1
2 0
（2）max z＝3X1+2X2
约束条件：2X1+3X2<=14
2X1+X2<=9
X1,X2>=0，且X1为整数。
解题如下：计算机输出结果：
**********************最优解如下*************************
目标函数最优值为: 14
变量最优解
------- --------
x1 4
x2 1
约束松弛/剩余
------- ---------
1 3
2 0
（3）max z＝7X1+9X2+3X3
约束条件：-X1+3X2+X3<=7
7X1+X2+3X3<=38
X1,X2,X3>=0，且X1为整数,X3为0~1变量。
解题如下：计算机输出结果：
**********************最优解如下*************************
目标函数最优值为: 19
变量最优解
------- --------
x1 1
x2 1
x3 1
约束松弛/剩余
------- ---------
1 4
2 27
第九章目标规划
作业：P198-199 Q2
Q2：目标规划问题：三种媒体广告如表：
13
14
第1优先权：目标：广告影响人数至少达到4 000 000人
第2优先权：目标：电视广告次数至少占比30%。
第3优先权：目标：广播的次数不能超过20%。
第4优先权：目标：广告费用控制在20 000元以内。
试建立本问题的目标规划并求解。
答题如下：
建立模型：设X1,X2,X3分别为投入的电视广告次数，报纸广告次数和广播广告次数，根据题意有：X1<=10,X2<=20,X3<=15
第1优先权目标：广告影响人数不少于4000000人，则有：
200000X1+100000X2+50000X3>=4000000
引入d1+表示超过4000000的部分和d1-表示低于4000000的部分人数，则有：
200000X1+100000X2+50000X3=4000000+ d1+- d1-，整理后得：
200000X1+100000X2+50000X3- d1++ d1-=4000000
第2优先权目标：电视广告次数至少占比30%，则有：
X1/(X1+X2+X3)>=0.3，即：0.3(X1+X2+X3)<=X1,引入d2+表示超过30%的部分和d2-表示低于30%，则有：0.3(X1+X2+X3)=X1+ d2+- d2-，整理后得：
-0.7X1+0.3X2+0.3X3- d2++ d2-=0
第3优先权目标：广播次数比例不超过20%，则有：
X3/(X1+X2+X3)<=0.2，即：0.2(X1+X2+X3)<=X3，引入d3+表示超过20%的部分和d3-表示低于20%则有：0.2(X1+X2+X3)=X2- d3++ d3-，整理后得：
0.2X1+0.2X2-0.8X3+ d3+- d3-=0
第4优先权目标：2500X1+500X2+300X3<=20000，引入d4+表示超过20000元的部分和d4-表示低于20000元的部分，则有：2500X1+500X2+300X3=20000- d4++ d4-，整理得：
2500X1+500X2+300X3 +d4+ -d4-=20000
上述各约束条件整理后如下：
绝对约束条件：
X1<=10
X2<=20
X3<=15
X1,X2,X3>=0
目标约束条件：
200000X1+100000X2+50000X3- d1++ d1-=4000000
-0.7X1+0.3X2+0.3X3- d2++ d2-=0
0.2X1+0.2X2-0.8X3+ d3+- d3-=0
2500X1+500X2+300X3 +d4+ -d4-=20000
d1+, d1-, d2+, d2- ,d3+, d3-,d4+ ,d4->=0
根据题意，要使d1-, d2- ,d3+, d4+ 最小
计算机解题结果如下：
14
15
15
目标函数值为 : 10125
变量 解 相差值 ------- -------- --------
x1 6.25 0 x2 20 0 x3 15 0 d1- 0 0 d1+ 0 .013 d2- 0 0 d2+ 6.125 0 d3- 6.75 0 d3+ 0 0 d4- 0 1 d4+ 10125 0
第十一章 图与网络模型
作业：P255-256 第Q1－Q5题
Q1：配送中心：v1～v7，其中v1表示配送中心，v7表示快餐店，v2，v3，v4，v5，v6表示其他地名。请解答按照什么线路送货使时间最短。如图：
答题如下：根据图示，计算机解结果如下： 从节点 1到节点7的最短路
************************* 起点 终点 距离 ---- ---- ---- 1 2 4
配送 中心 快餐店 V2
4
18
6
5
2
12
16
7
8
6
V4
V6
V1
V2
V3
V5
16
16
2 3 12 3 5 6 5 7 5 此问题的解为:27
Q2：最短路问题：机器更新，机器可用4年。也可于年末卖掉更新。新机器第一年运行及维修费0.3万元，1－3年后分别为0.8，1.5，2.0万元。购买机器，维修费，及1－3年的年
答题如下：
根据题意，做表如下：
根据上表，如图：
从节点 1到节点5的最短路
************************* 起点 终点 距离 ---- ---- ----
V1
3.9
17
17
1 2 .8 2 3 .9 3 4 1 4 5 1.1 此问题的解为:3.8
Q3：最小生成树问题：电力公司建设输电线路：8个居民点用v1～v8表示如图：边上的赋权数为道路长度。单位为公里。请设计输电线路，连接这8个居民点，使输电线路的总长度最短。 答题如下： 如图：
计算机解题结果如下： 此问题的最小生成树如下：
************************* 起点 终点 距离 ---- ---- ---- 1 3 2 3 4 2 1 2 4 2 5 2 5 7 3 7 8 2 7 6 3 此问题的解为:18
最小生成树如下：
V1
V3 V4
V2
V6
V5
V7
V8
4
5
3
2
2
3
4
5
7 6
2 2
18
18
Q4：最大流量问题：公路网如图，v1～v6为地点，边为公路，赋权数为该段车流量（单位为千辆/小时）请求出v1到v6的最大流量。 答题如下： 如图：
计算机解题结果如下：
从节点 1到节点6的最大流
************************* 起点 终点 距离 ---- ---- ---- 1 2 6 1 3 10 1 4 6 2 4 0 2 5 6 3 4 4 3 6 6
V1
V3 V4
V2
V6
V5
V7 V8
4
3
2
2
3
2
2
V1
V3
V2 V4 V5
V6
6
6
6
5
8
4
6
10
5
12
19
19
4 5 4 4 6 6 5 6 10 此问题的解为:22
Q5：请求下面网络中的最小费用最大流：如图。狐（Vi ，Vj ）的赋权为（Cij ，Bij ）其中Cij 为Vi 到Vj 的流量，Bij 为Vi 到Vj 单位流量的费用。 答题如下：如图。
计算机解题结果如下：
从节点 1到节点6的最大流 *************************
起点 终点 流量 费用 ---- ---- ---- ----
1 2 1 3 1 3 4 1 2 4 2 4 3 2 1 1 3 5 3 3 4 6 2 4 5 6 3 2
此问题的最大流为:5。此问题的最小费用为:39
第十二章 排序与统筹方法
V1 V2
V3
V4
V5
V6
（5，3） （4，1）
（1，1） （1，2）
（1，2）
（5，2）
（3，3）
（2，4）
（2，4）
20
20
作业：P284-285：Q5，Q6
解题如下：如图
5、对于上题，给出各工序所需的时间如表。请计算每个工序的最早开始时间，最晚开始时间，找出关键工序，找出关键路线，并求出完成此工程所需的最少时间。
计算机解题结果如下：
工序 最早开始时间 最迟开始时间 最早完成时间
最迟完成时间 时差 是否关键工序 ----------------------------------------------------------------------------------
第一章线性规划1、 由图可得：最优解为 2、用图解法求解线性规划： Min z=2x1+x2 ? ? ? ? ? ? ? ≥ ≤ ≤ ≥ + ≤ + - 10 5 8 24 4 2 1 2 1 2 1 x x x x x x 解： 由图可得：最优解x=1.6,y=6.4
Max z=5x 1+6x 2 ? ?? ??≥≤+-≥-0 ,23222212 121x x x x x x 解： 由图可得：最优解Max z=5x 1+6x 2, Max z= + ∞
Maxz = 2x 1 +x 2 ????? ? ?≥≤+≤+≤0,5242261552121211x x x x x x x 由图可得：最大值?????==+35121x x x ， 所以?????==2 3 21x x max Z = 8.
12 12125.max 2328416412 0,1,2maxZ .j Z x x x x x x x j =+?+≤? ≤?? ≤??≥=?如图所示，在（4，2）这一点达到最大值为2 6将线性规划模型化成标准形式： Min z=x 1-2x 2+3x 3 ????? ??≥≥-=++-≥+-≤++无约束 321 321321321,0,05232 7x x x x x x x x x x x x 解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中x 3’≥ 0,x 3’’≥0 Max z ’=-x 1+2x 2-3x 3’+3x 3’’ ????? ? ?≥≥≥≥≥≥-=++-=--+-=+-++0 ,0,0'',0',0,05 232 '''7'''543321 3215332143321x x x x x x x x x x x x x x x x x x x
《管理运筹学》（第二版）课后习题参考答案 第1章 线性规划（复习思考题） 1．什么是线性规划线性规划的三要素是什么 答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0≥i b ，决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示：
1 课程：管理运筹学 管理运筹学作业 第二章线性规划的图解法 P23：Q2：（1）－（6）；Q3：(2) Q2：用图解法求解下列线性规划问题，并指出哪个问题具有唯一最优解，无穷多最优解，无界解或无可行解。 （1）Min f＝6X1+4X2 约束条件：2X1+X2>=1, 3X1+4X2>=3 X1, X2>=0 解题如下：如图1 Min f＝3.6 X1=0.2, X2=0.6 本题具有唯一最优解。 图1 （2）Max z＝4X1+8X2 约束条件：2X1+2X2<=10 -X1+X2>=8 X1,X2>=0 解题如下：如图2： Max Z 无可行解。 图2 1
2 2 （3） Max z ＝X1+X2 约束条件 8X1+6X2>=24 4X1+6X2>=-12 2X2>=4 X1,X2>=0 解题如下：如图3： Max Z=有无界解。 图3 （4） Max Z ＝3X1-2X2 约束条件：X1+X2<=1 2X1+2X2>=4 X1,X2>=0 解题如下：如图4： Max Z 无可行解。 图 4
3 (5)Max Z＝3X1+9X2 约束条件：X1+3X2<=22 -X1+X2<=4 X2<=6 2X1-5X2<=0 X1,X2>=0 解题如下：如图5： Max Z =66；X1=4 X2=6 本题有唯一最优解。 图5 (6)Max Z=3X1+4X2 约束条件：-X1+2X2<=8 X1+2X2<=12 2X1+X2<=16 2X1-5X2<=0 X1,X2>=0 解题如下：如图6 Max Z =30.669 X1=6.667 X2=2.667 本题有唯一最优解。 3
《管理运筹学》第四版课后习题解析（上） 第2章 线性规划的图解法 1．解： （1）可行域为OABC 。 （2）等值线为图中虚线部分。 （3）由图2-1可知，最优解为B 点，最优解1x = 127，2157x =；最优目标函数值697 。 图2-1 2．解： （1）如图2-2所示，由图解法可知有唯一解12 0.2 0.6x x =??=?，函数值为3.6。 图2-2 （2）无可行解。 （3）无界解。 （4）无可行解。 （5）无穷多解。
（6）有唯一解 12203 8 3x x ?=????=?? ，函数值为923。 3．解： （1）标准形式 12123max 32000f x x s s s =++++ 1211221231212392303213229,,,,0 x x s x x s x x s x x s s s ++=++=++=≥ （2）标准形式 1212min 4600f x x s s =+++ 12112212121236210764,,,0 x x s x x s x x x x s s --=++=-=≥ （3）标准形式 1 2212min 2200f x x x s s ''''=-+++ 12 211 2212221 2212355702555032230,,,,0x x x s x x x x x x s x x x s s '''-+-+=''''-+=''''+--=''''≥ 4．解： 标准形式 1212max 10500z x x s s =+++ 1211221212349528,,,0 x x s x x s x x s s ++=++=≥ 松弛变量（0，0） 最优解为 1x =1，x 2=3/2。 5．解：
管理运筹学 ——管理科学方法谢家平 第一章 第一章 1. 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量（Decision Variable）是决策问题待 定的量值，取值一般为非负；约束条件（Constraint Conditions）是指决策变量取值时受到的各种资源条件的限制， 保障决策方案的可行性；目标函数（Objective Function）是决策者希望实现的目标，为决策变量的线性函数表达式， 有的目标要实现极大值，有的则要求极小值。 2.（1）设立决策变量； （2）确定极值化的单一线性目标函数； （3）线性的约束条件：考虑到能力制约，保证能力需求量不能突破有效供给量； （4）非负约束。 3.（1）唯一最优解：只有一个最优点 （2）多重最优解：无穷多个最优解 （3）无界解：可行域无界，目标值无限增大 （4）没有可行解：线性规划问题的可行域是空集 无界解和没有可行解时，可能是建模时有错。 4. 线性规划的标准形式为：目标函数极大化，约束条件为等式，右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 5. 可行解：满足约束条件AX =b,X≥0的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 6. 计算步骤： 第一步，确定初始基可行解。 第二步，最优性检验与解的判别。 第三步，进行基变换。 第四步，进行函数迭代。 判断方式： 唯一最优解：所有非基变量的检验数为负数，即σj< 0 无穷多最优解：若所有非基变量的检验数σj≤ 0 ，且存在某个非基变量xNk 的检验数σk= 0 ，让其进基，目标函数
关键路线为：H-B-G-A- Du3-F-K，总工期为20
关键路线为：a-f-i-n-o-q，总工期为152
2 直接费用为20＋30＋15＋5＋18＋40＋10＋15＝153百元，间接费用为5×15＝75百元，总费用为153＋75＝228百元 方案II：G工时缩短1天，总工期14天 直接费用为153＋3×1＝156百元，间接费用为5×14＝70百元，总费用为156＋70＝226百元 关键路线为：B-Du2-G-H、A-F-Du1-H和B-C 最低成本日程为226百元，总工期14天。
直接费用为100＋200＋80＋0＋150＋250＋120＋100＋180＋130＝1310元，间接费用为15×27＝405元，总费用为1310＋405＝1715元 方案II：1－2工序工时缩短2天，总工期25天 直接费用为1310＋10×2＝1330元，间接费用为15×（27－2）＝375元， 总费用为1330＋375＝1705元 关键路线为：关键路线为：1－2－3－4－6－8 方案III：2－3工序工时缩短4天，总工期21天 直接费用为1330＋20×4＝1410元，间接费用为15×（25－4）＝315元， 总费用为1410＋315＝1725元 最低成本日程为1705元，总工期25天。
9.5解：网络图如下： 方案Ⅰ：按正常工时工作，总工期19天，关键路线为：B-E-F 方案Ⅱ：E工时缩短2天，总工期17天，变化费用＝30－50×2＝－70； 关键路线为：B-E-F和C-F 方案Ⅲ：C工时缩短1天，E工时缩短1天，总工期16天，变化费用＝－70＋30＋15－50×1＝－75； 关键路线为：A-D-F、B-E-F和C-F 方案Ⅳ：F工时缩短1天，总工期15天，变化费用＝－75＋40－50＝－85； 关键路线为：A-D-F、B-E-F和C-F 方案Ⅴ：B工时缩短3天，C工时缩短3天，D工时缩短2天，A工时缩短1天，总工期12天，变化费用＝－85＋25×3＋30×3＋10×2＋20×1－50×3＝－30； 关键路线为：A-D-F、B-E-F和C-F 所以正常计划工期是19天，最少工期是12天，最佳工期是15天，各项工作的相应工时如上表方案Ⅳ所示。
《管理运筹学》第四版课后习题解析（下） 第9章 目 标 规 划 1、解： 设工厂生产A 产品1x 件，生产B 产品2x 件。按照生产要求，建立如下目标规划模型。 112212121211122212min ()() s.t 43452530 555086100 ,,,0,1,2 -- +-+-+-++++-+=+-+==i i P d P d x x x x x x d d x x d d x x d d i ≤≤≥ 由管理运筹学软件求解得 12121211.25,0,0,10, 6.25,0x x d d d d --++ ====== 由图解法或进一步计算可知，本题在求解结果未要求整数解的情况下，满意解有无穷多个，为线段(135/14,15/7)(1)(45/4,0),[0,1]ααα+-∈上的任一点。 2、解： 设该公司生产A 型混凝土x 1吨，生产B 型混凝土x 2吨，按照要求建立如下的目标规划模型。 ) 5,,2,1(0,,0,0145 50.060.015550.040.030000100150100 120275200.)()(min 2121215521442331222111215443 32 211 1 =≥≥≥≤+≤+=-++=-+=-+=-++=-++++++++-+-+-+-+-+-- - - + +- i d d x x x x x x d d x x d d x d d x d d x x d d x x t s d p d d p d p d d p i i 由 管 理 运 筹 学 软 件 求 解 得 . 0,0,20,0,0,0, 0,35,40,0,120,120554433221121============+-+-+-+-+-d d d d d d d d d d x x
11.1解： 4=λ人/小时，10660==μ人/小时，4.010 4===μλρ，属于M/M/1排队模型。 （1）仓库管理员空闲的概率，即为6.04.0110=-=-=ρP （2）仓库内有4个工人的概率即为()()01536.04.04.011444=?-=-=ρρP （3）至少有2个工人的概率为16.024.06.01110=--=--P P （4）领工具的工人平均数人6667.06 44104==-=-=λμλ s L （5）排队等待领工具工人的平均数人2667.06 6.141044.0==-?=-=λμρλq L （6）平均排队时间分钟小时4066 7.06 4.04104.0===-=-= λμρq W （7）待定 11.2解： 32060==λ人/小时，41560==μ人/小时，75.04 3===μλρ，属于M/M/1排队模型。
（1）不必等待概率，即为25.075.0110=-=-=ρP （2）不少于3个顾客排队等待的概率，即系统中有大于等于4个（或大于3个）顾客的概率，为 3164.01055.01406.01875.025.0113210=----=----P P P P （3）顾客平均数人31 3343==-=-=λμλ s L （4）平均逗留时间小时13 411=-=-=λμs W （5）λ λμ-=-=<4115.1s W 小时，即小时人/333.3>λ。平均到达率超过3.333人时，店主才会考虑增加设备或理发员。 11.3解：
4=λ人/小时，10660==μ人/小时，4.010 4===μλρ，属于M/M/1/3排队模型。 （1）仓库内没有人领工具的概率，即为6158.04 .014.0111410=--=--=+N P ρρ （2）工人到达必须排队等待的概率，即为仓库内有1个、2个和3个工人的概率和 ()() 3842.04.014.014.04.04.011432132321=--?++=--++=+++N P P P ρρρρρ （3）新到工人离去的概率为0394.04 .014.014.01143133=--?=--=+N P ρρρ （4）领工具的工人平均数()=-?--=-+--=++44114 .014.044.014.0111N N s N L ρρρρ （5）排队等待领工具工人的平均数人2667.06 6.141044.0==-?=-=λμρλq L （6）平均排队时间分钟小时4066 7.064.04104.0===-=-= λμρq W
清华第三版 运筹学 答案[键入文字] [键入文字] [键入文字] 运筹学教程 1. 某饲养场饲养动物出售，设每头动物每天至少需700g 蛋白质、30g 矿物质、100mg 维生素。现有五种饲料可供选用，各种饲料每kg 营养成分含量及单价如表1所示。 表1 要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。 解：设总费用为Z 。i=1,2,3,4,5代表5种饲料。i x 表示满足动物生长的营养需要时，第i 种饲料所需的数量。则有： ????? ? ?=≥≥++++≥++++≥++++++++=5,4,3,2,1,01008.022.05.0305.022.05.07008623..8.03.04.07.02.0min 54321543215432154321i x x x x x x x x x x x x x x x x t s x x x x x Z i 2. 某医院护士值班班次、每班工作时间及各班所需护士数如表2所示。每班护士值班 开始时间向病房报道，试决定： （1） 若护士上班后连续工作8h ，该医院最少需要多少名护士，以满足轮班需要； （2） 若除22:00上班的护士连续工作8h 外（取消第6班），其他班次护士由医院 排定上1～4班的其中两个班，则该医院又需要多少名护士满足轮班需要。 表2
6 2:00～6:00 30 解：（1）设x 第i 班开始上班的人数，i=1,2,3,4,5,6 ???????????=≥≥+≥+≥+≥+≥+≥++++++=且为整数 6,5,4,3,2,1,030 2050607060..min 655443 322161 654321i x x x x x x x x x x x x x t s x x x x x x Z i 解：（2）在题设情况下，可知第五班一定要30个人才能满足轮班需要。则设设i x 第i 班开始上班的人数，i=1,2,3,4。 ??? ????? ?? ??? ??=≥=+++=≥+++=+++=≥+++=+++=≥+++=+++=≥+++++++=4 ,3,2,1,1002 1502 16021702 ,160..30 min i 444342414444433422411434 33323133 443333223113242322212244233222211214131211114413312211114321j i y x y y y y y x y x y x y x y y y y y y x y x y x y x y y y y y y x y x y x y x y y y y y y x y x y x y x y t s x x x x Z ij 变量，—是，，，第四班约束，，第三班约束，，第二班约束，第一班约束 3. 要在长度为l 的一根圆钢上截取不同长度的零件毛坯，毛坯长度有n 种，分别为j a （j=1,2，…n ）。问每种毛坯应当截取多少根，才能使圆钢残料最少，试建立本问题的数学模型。 解：设i x 表示各种毛坯的数量，i=1,2,…n 。
第2章 线性规划的图解法 1．解： x ` A 1 (1) 可行域为OABC (2) 等值线为图中虚线部分 (3) 由图可知，最优解为B 点， 最优解：1x = 712，7152=x 。最优目标函数值：769 2．解： x 2 1 0 1 (1) 由图解法可得有唯一解 6.02.021==x x ，函数值为3.6。 (2) 无可行解 (3) 无界解 (4) 无可行解 (5) 无穷多解
(6) 有唯一解 38320 21== x x ，函数值为392。 3．解： (1). 标准形式： 3212100023m ax s s s x x f ++++= 0,,,,9 2213 2330 2932121321221121≥=++=++=++s s s x x s x x s x x s x x (2). 标准形式： 21210064m in s s x x f +++= ,,,4 6710 26 3212121221121≥=-=++=--s s x x x x s x x s x x (3). 标准形式： 21''2'2'10022m in s s x x x f +++-= 0,,,,30 22350 55270 55321''2'2'12''2'2'1''2'2'11''2'21≥=--+=+-=+-+-s s x x x s x x x x x x s x x x 4．解： 标准形式： 212100510m ax s s x x z +++= ,,,8259 432121221121≥=++=++s s x x s x x s x x 松弛变量（0，0） 最优解为 1x =1，x 2=3/2.
运筹学（第3版）习题答案 第1章线性规划 P36 第2章线性规划的对偶理论 P74 第3章整数规划 P88 第4章目标规划 P105 第5章运输与指派问题P142 第6章网络模型 P173 第7章网络计划 P195 第8章动态规划 P218 第9章排队论 P248 第10章存储论P277 第11章决策论P304 第12章 多属性决策品P343 第13章博弈论P371 全书420页 第1章 线性规划 1.1工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示． 310和130.试建立该问题的数学模型,使每月利润最大． 【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为 1231231 23123123max 1014121.5 1.2425003 1.6 1.21400 150250260310120130,,0 Z x x x x x x x x x x x x x x x =++++≤??++≤??≤≤?? ≤≤??≤≤?≥?? 1.2建筑公司需要用5m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格 及数量如表1－24所示：
问怎样下料使得（1）用料最少；（2）余料最少． 【解 设x j （j =1,2,…，10）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为 10 1 12342567368947910 min 2800212002600223900 0,1,2,,10 j j j Z x x x x x x x x x x x x x x x x x x j ==?+++≥? +++≥?? +++≥??+++≥??≥=?∑L （2）余料最少数学模型为 2345681012342567368947910 min 0.50.50.52800 212002********* 0,1,2,,10 j Z x x x x x x x x x x x x x x x x x x x x x x x x j =++++++?+++≥? +++≥?? +++≥??+++≥??≥=?L 1.3某企业需要制定1～6月份产品A 的生产与销售计划。已知产品A 每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1～6月份产品A 的单件成本与售价如表1－25所示。 （2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。 【解】设x j 、y j （j ＝1，2，…，6）分别为1～6月份的生产量和销售量，则数学模型为
管理运筹学第二版课后 习题参考答案 Document number【980KGB-6898YT-769T8CB-246UT-18GG08】
《管理运筹学》（第二版）课后习题参考答案 第1章 线性规划（复习思考题） 1．什么是线性规划线性规划的三要素是什么 答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0 i b ，决策变量满足非负性。
如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示： 5．用表格单纯形法求解如下线性规划。 . ??? ??≥≤++≤++0,,862383 21321321x x x x x x x x x 解：标准化 32124max x x x Z ++= . ?? ? ??≥=+++=+++0,,,,862385432153 214 321x x x x x x x x x x x x x 列出单纯形表
第 2 章 线性规划的图解法 1 1 a.可行域为 OABC 。 b.等值线为图中虚线所示。 12 c.由图可知，最优解为 B 点，最优解： x 1 = 7 69 。 7 2、解： 15 x 2 = 7 ， 最优目标函数值： a x 2 1 0.6 0.1 O 1 有唯一解 x 1 = 0.2 函数值为 3.6 x 2 = 0.6 b 无可行解 c 无界解 d 无可行解 e 无穷多解
1 2 2 1 2 f 有唯一解 20 x 1 = 3 8 函数值为 92 3 3、解： a 标准形式： b 标准形式： c 标准形式： x 2 = 3 max f max f = 3x 1 + 2 x 2 + 0s 1 + 0s 2 + 0s 3 9 x 1 + 2x 2 + s 1 = 30 3x 1 + 2 x 2 + s 2 = 13 2 x 1 + 2x 2 + s 3 = 9 x 1 , x 2 , s 1 , s 2 , s 3 ≥ 0 = ?4 x 1 ? 6x 3 ? 0s 1 ? 0s 2 3x 1 ? x 2 ? s 1 = 6 x 1 + 2x 2 + s 2 = 10 7 x 1 ? 6 x 2 = 4 x 1 , x 2 , s 1 , s 2 ≥ max f = ?x ' + 2x ' ? 2 x '' ? 0s ? 0s ' '' ? 3x 1 + 5x 2 ? 5x 2 + s 1 = 70 2 x ' ? 5x ' + 5x '' = 50 1 2 2 ' ' '' 3x 1 + 2 x 2 ? 2x 2 ? s 2 = 30 ' ' '' 4 、解： x 1 , x 2 , x 2 , s 1 , s 2 ≥ 0 标准形式： max z = 10 x 1 + 5x 2 + 0s 1 + 0s 2 3x 1 + 4 x 2 + s 1 = 9 5x 1 + 2 x 2 + s 2 = 8 x 1 , x 2 , s 1 , s 2 ≥ 0 s 1 = 2, s 2 = 0
《管理运筹学》第四版课后习题解析 第5章单纯形法 1．解： 表中a 、c 、e 、f 是可行解，f 是基本解，f 是基本可行解。 2．解： （1）该线性规划的标准型如下。 max 5x 1＋9x 2＋0s 1+0s 2+0s 3 s.t. 0.5x 1＋x 2＋s 1＝8 x 1＋x 2－s 2＝10 0.25x 1＋0.5x 2－s 3＝6 x 1，x 2，s 1，s 2，s 3≥0 （2）至少有两个变量的值取零，因为有三个基变量、两个非基变量，非基变量取零。 （3）（4，6，0，0，-2）T （4）（0，10，-2，0，-1）T （5）不是。因为基本可行解要求基变量的值全部非负。 （6）略 3.解： 令33 3x x x ''-'=，z f -=改为求f max ；将约束条件中的第一个方程左右两边同时乘以-1，并在第二和第三个方程中分别引入松弛变量5x 和剩余变量6x ，将原线性规划问题化为如下标准型： j x '、j x ''不可能在基变量中同时出现，因为单纯性表里面j x '、j x ''相应的列向 量是相同的，只有符号想法而已，这时候选取基向量的时候，同时包含两列会使 选取的基矩阵各列线性相关，不满足条件。 4．解： （1） 表5-1 0,,,,,, 24423 1863 1334 7234max 65433 21633 21543321433 214 321≥'''=-''+'--=++''+'-+-=+''+'---++-=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 f 约束条件：
运筹学（Operational Research）复习资料 第一章绪论 一、名词解释 1.运筹学：运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 二、选择题 1.运筹学的主要分支包括（ABDE ） A图论B线性规划C非线性规划D整数规划E目标规划 2. 最早运用运筹学理论的是（ A ） A . 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署 B . 美国最早将运筹学运用到农业和人口规划问题上 C . 二次世界大战期间，英国政府将运筹学运用到政府制定计划 D . 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上 第二章线性规划的图解法 一、选择题/填空题 1.线性规划标准式的特点： （1）目标函数最大化（2）约束条件为等式（3 决策变量为非负（4 ) 右端常数项为非负2. 在一定范围内，约束条件右边常数项增加一个单位： （1）如果对偶价格大于0，则其最优目标函数值得到改进，即求最大值时，最优目标函数值变得更大，求最小值时最优目标函数值变得更小。 （2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，最优目标函数值变小了；求最小值时，最优目标函数值变大了。 （3）如果对偶价格等于0，则其最优目标函数值不变。 3.LP模型（线性规划模型）三要素： （1）决策变量（2）约束条件（3）目标函数 4. 数学模型中，“s·t”表示约束条件。 5. 将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左端加上松弛变量。 6. 将线性规划模型化成标准形式时，“≥”的约束条件要在不等式左端减去剩余变量。7．下列图形中阴影部分构成的集合是凸集的是A
（1）解： , 5 3351042..715min 212 1 1 21 21≥≥+≥≥++=y y y y y y y t s y y ω （2）解： 无限制 3213 21 3132 3213121,0,0 2 520474235323. .86max y y y y y y y y y y y y y y y t s y y ≤≥=++≤-=+≥+--≤++=ω 解：例3原问题 6 ,,1,0603020506070 ..min 166554433221654321Λ=≥≥+≥+≥+≥+≥+≥++++++=j x x x x x x x x x x x x x t s x x x x x x z j 对偶问题： 6 ,,1,0111111 ..603020506070max 655443322161654321Λ=≥≤+≤+≤+≤+≤+≤++++++=j y y y x y y y y y y y y y t s y y y y y y j ω
解： （1）由最优单纯形表可以知道原问题求max ，其初始基变量为54,x x ，最优基的逆阵为 ????? ? ??-=-316102 11 B 。 由P32式（）（）（）可知b B b 1 -='，5,,1,,1Λ='-=='-j P C c P B P j B j j j j σ，其中b 和j P 都是初始数据。设???? ??=21b b b ，5,,1,21Λ=???? ??=j a a P j j j ，()321,,c c c C =，则 ?????? ??=???? ???????? ??-?='-2525316102 1 211 b b b B b ，即?????=+-=25316 12521211b b b ，解得???==10521b b ????? ? ??-=???? ???????? ??-?='-021******** 102 12322211312111 a a a a a a P B P j j ，即 ???????????????=+-=-=+-==+-=0 31 6 112121316121 211 316 1021 231313221212211111a a a a a a a a a ，解得???????????==-====12 1130231322 122111a a a a a a
运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都 为最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 ?+?= P47 1.3 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点， 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ，即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?=
单纯形法： 原问题化成标准型为 121231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 B C B X b 1x 2x 3x 4x 0 3x 9 3 4 1 0 0 4x 8 [5] 2 0 1 j j C Z - 10 5 0 0 0 3x 21/5 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 1/5 j j C Z - 1 0 - 2 5 2x 3/2 0 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 j j C Z - -5/14 -25/14
《管理运筹学》(第二版)课后习题参考答案 第1章线性规划(复习思考题) 1.什么是线性规划？线性规划的三要素是什么？ 答：线性规划(Lin ear Programmi ng, LP )是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2.求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？ 答：(1)唯一最优解：只有一个最优点； (2)多重最优解：无穷多个最优解； (3)无界解：可行域无界，目标值无限增大； (4)没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3.什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？ 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项b i 0， 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“2型约束的左边取值大于右边规划值，出现剩余量。 4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件AX b，X 0的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示：
《管理运筹学》作业题参考答案 一、简答题 1. 试述线性规划数学模型的结构及各要素的特征。 2. 求解线性规划问题时可能出现哪几种结果，哪些结果反映建模时有错误。 3. 举例说明生产和生活中应用线性规划的方面，并对如何应用进行必要描述。 4. 什么是资源的影子价格，同相应的市场价格之间有何区别，以及研究影子价格的意义。 5. 试述目标规划的数学模型同一般线性规划数学模型的相同和异同之点。 （答案参考教材） 二、判断题 1. (√) 2. (√) 3. (×) 4. (√) 5. (√) 三、计算题 1. 用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。 (a) min z =6x 1+4x 2 (b) min z =4x 1+8x 2 ??? ??≥≥+≥+0,5.1431 2.st 2 12121x x x x x x ??? ??≥≥+-≥+0,101022.st 2 12121x x x x x x (c) min z =x 1+x 2 (d) min z =3x 1-2x 2 ?????? ?≥≥-≥+≥+0 ,4212642468.st 2122 121x x x x x x x ??? ??≥≥+≤+0,4221 .st 2 12121x x x x x x (e) min z =3x 1+9x 2 ????? ????≥≤-≤≤+-≤+0 ,0 5264 2263.st 212 122121x x x x x x x x x 2. (a)唯一最优解，z* =3，x 1=1/2，x 2= 0；(b)无可行解；(c)有可行解，但max z 无界；（d ）无可行解；（c ）无穷多最优解，z*=66；（f ）唯一最优解，z*=.3/8,3/20,3 2 3021==x x
一、管理运筹学的定义 运筹学（Operational Research，简称OR) ，英文直译为“运作研究”。 管理运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 ——《中国企业管理百科全书》 绪论 二、管理运筹学Ⅰ的主要分支 线性规划(Linear Programming，简称LP) 整数规划(Integral Programming，简称IP) 目标规划(Objective Programming，简称OP) 动态规划(Dynamic Programming，简称DP) 图与网络(Graph and Network) 三、管理运筹学的工作步骤 提出问题、分析问题 建立模型 求解 解的检验、控制、实施 四、运筹学方法的特点 1. 最优化方法 2. 定量的方法 线性规划(LP) 一、问题的提出 1.生产计划安排问题： 合理利用人力、物力、财力等，在资源有限的约束条件下,寻求使得获利最大的最优生产计划方案。 2.人力资源分配的问题： 在满足工作的需要的条件下，寻求使用最少的劳动力的最优分配方案。 3.套裁下料问题： 在保证正常生产，完成生产任务的条件下，寻求使用原料最省的最优下料方案。 4.投资问题：在投资额限制的条件下，从多个投资项目中选取使得投资回报最大的最优投资方案。 5.运输问题：寻求使得总运费最小的最优调运方案。 二、建模 1.一般步骤:
分析问题，设出决策变量 根据所提问题列出目标函数 根据已知条件列出所有约束条件 数学模型的一般形式 ★矩阵形式：假设有n个决策变量，m个约束条件。 目标函数：Max （Min）z = CX 约束条件： AX ≤（=, ≥）b . X≥0 其中，C=(c1 , c2 , …, cn )(价值向量) X= (x1 , x2 , …, xn )T(决策变量向量) b=(b1 , b2 , …, bm )T (限定向量) a11 a12 (1) a21 a22 …a2n (约束条件系数矩阵) Am×n = …… am1 am2 …amn 数学模型的特点 （1）由目标函数和约束条件构成； （2）目标函数只有两种情况：求极小或求极大。 （3）双线性 ①目标函数是关于决策变量的线性函数; ②所有约束条件是关于决策变量的线性函数。 三、求解 1.方法一：图解法 （1）适用条件 有且仅有两个决策变量X1，X2。 （2）基本概念 可行解；可行域；最优解 （3）基本思路：先求出可行解（即找出可行域），再在可行解的基础上（即在可行域内）求出最优解。 （4）基本步骤作图找出可行域作出目标函数等值线，判断其平移的方向 平移目标函数等值线，在可行域内找出最优点，计算最优解。 （5）图解法解的情况 ①唯一最优解②无穷多最优解 ③无可行解④无界解 注意：能够区分无可行解和无界解的情况。