1．用图解法求解两个变量线性规划问题的最优解和最优值。
???
??≥≤+≤++=0,153562st.32max 2
1212121x x x x x x x x z
，15/7）
2．用图解法求解以下线性规划问题，并指出哪个问题有惟一解、无穷多最优解、无界解或无可行解
???
??≥≥+≥++=0,34312st.46min 2121212
1x x x x x x x x z
???
??≥≥+-≤++=0
,810
22st.84max 21212121x x x x x x x x z
无可行解
3．某公司从中心制造地点向分别位于城区北、东、南、西方向的分配点运送材料。该公司有26辆卡车，用于从制造地点向分配点运送材料。其中有9辆，每辆能装5吨的大型卡车，12辆每辆能装2吨的中型卡车和5辆每辆能装1吨的小型卡车。北、东、南、西四个点分别需要材料14吨、10吨、20吨、8吨。每辆卡车向各分配点送材料一次的费用如表2-7所示。建立运送材料总费用最小的线性规划模型。
表2-7 车辆运送一次的费用
解 设大、中、小型车分别用i 表示，则3,2,1=i ；东、南、西、北四个分点分别用j 表示，则4,3,2,1=j ；向j 方向发出的i 型车数量为ij x 。
34
3332312423222114131211223815204255605075926380min x x x x x x x x x x x x Z +++++++++++=
???
?????
????
?=≥≤+++≤+++≤+++≥++≥++≥++≥++4,3,2,1,,05129825202510
251425.343332312423222114131211342414332313322212
312111j i 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 st ij
4．某工厂生产A 、B 、C 三种产品，现根据合同及生产状况制定5月份的生产计划。已知合同甲为：A 产品1000件，每件价格为500元，违约金为100元/每件；合同乙：B 产品500件，每件价格为400元，违约金为120元/每件；合同丙为：B 产品600件，每件价格为420元，违约金为130元/每件；C 产品600件，价格400元/每件，违约金为90元/每件。有关各产品生产过程所需工时以及原材料的情况如表2-8所示。试以利润为目标建立该工厂生产计划的线性规划模型。
表2-8 产品使用的原材料、加工工序、资源限制、成本
解 设工厂5月份为完成合同甲生产1x 件A 产品；为完成合同乙生产2x 件B 产品；为完成合同丙生产3x 件 B 产品，4x 件C 产品。
292000
260325295290)1040220420210152()()104032201031015()10404203102103152(90)600(400130)600(420120)500(400)1000(500max 43214
32144332211-+++=+?+?+?++?-+?+?+?+?++-+?+?+?+?+?-?--+?--+?--+--=x x x x x x x x x x x x x x x x Z
?????
???
??
?????≤≤≤≤≤≤≤≤≤+++≤+++≤+++≤+++≤+++,6000,
6000,5000,
1000080002)(34100004)(23600023324000
23460022.4321
4321432143214321
4321x x x x x x x x x x x x x x x x x x x x x x x x st
5．某公司从事某种商品的经营，现欲制定本年度10至12月的进货及销售计划。已知该种商品的初始库存量为2000件，公司仓库最多可存放10000件，公司拥有的经营资金80万元，据预测，10至12月的进货及销售价格如表2-9所示。若每个月仅在1号进货1次，且要求年底时商品存量达到3000件，在以上条件下，建立该问题的线性规划模型，使公司获得最大利润？（注：不考虑库存费用）
表2-9 进货和销售价格
解
12,11,10,=i x i ，为每月购进的货物，12,11,10,=i y i 为每月销售的货物。
????????
?????????
=≥=≥=---+++--+++≤-++≤+≤≤--+++≤-++≤+≤++---++=12
,11,10,012,11,10,0 30002000 2000 2000 2000 100002000 100002000 100002000 80000989590.989590115100100max 121110101112111010111212101011111010111010111210101110121110121110121110i y i x y y y x x x y y x x x y y x x y x y y y x x x y x x x x x x st x x x y y y Z i i 年底存量限制
销量限制销量限制销量限制库容限制库容限制库容限制资金限制
6．某饲养场饲养动物出售，设每头动物每天至少需700g 蛋白质、30g 矿物质、100mg 维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量单价如表2-10所示。
表
2-10 饲料所含的营养成分及价格
解 设各送这5钟饲料1x ，2x ，3x ，4x ，5x kg 。
??????
?=≥++++≥++++≥++++++++=5
,4,3,2,1,1008.022.05.0305.022.05.070018623.8.03.04.07.02.0min 54321543215432154321i x x x x x x x x x x x x x x x x st x x x x x Z i
7．某一企业家需要找人清理5间会议室、12张桌子和18个货架。今有两个临时工A 和B 可供该企业家雇佣。A 一天可清理1间会议室、3张桌子与3个货架；而B 一天可清理1间会议室、2张桌子与6个货架。A 的工资每天25元，B 每天22元。为了使成本最低，应雇佣A 和B 各多少天？（用线性规划图解法求解）
解：设雇佣A 和B 分别为y x ,天
??????
?
≥≥+≥+≥++=为整数且y x y x y x y x y x st y x Z ,0;186312235.2225min
由图知A 点为最优解，联立方程：
??
?=+=+51223y x y x
解得：
x =2, =y 3,即： Z min =25x +22y =25?2+22?3=116
因此，雇佣A 工人2天，B 工人3天。
8．某外贸公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。1月1日，公司拥有库存1000担杂粮，并有资金20000元。估计第一季度杂粮价格如表2-11所示。
表2-11 第一季度杂粮价格表
―货到付款‖。公司希望本季度末库存为2000担，建立该问题的线性规划模型使三个月总的获利最大。
解 设一月份买入1x 担，卖出'1x 担；二月份买入2x 担，卖出'
2x 担；三月份买入3x 担，
卖出'
3x 担。
????
??
???????=≥=≥≥+-+-+-++-≤≤+-+-+-≤≤+-≤-+-+-=3,2,1,0;3,2,1,02000
100025.310.385.22000090.25000100010.385.22000005.35000
10002000085.2.90.295.205.325.385.210.3max '3'32'21'1'2'1132'21'1'
1
121'
113
'
32'21'1j x i x x x x x x x x x x x x x x x x x x x x x st x x x x x x Z j i
1．求下列线性规划问题的所有基解、基可行解、最优解
???
??≥=++=++++=0
,,6422
st.33max 3213213213
21x x x x x x x x x x x x z
解：由题意知：A= 1
11124??
???=（1,2,3p p p ） b=26??
?
?? c=（3，1，3）
（1）1B =（1,2p p ），︱1B ︳≠0，1B 是基，1x ，2x 是基变量，3x 是非基变量，令
3x =0，得1x =-2，2x =4 即123x x x ??
? ?
???=()2,4,0-T 为基解，但不是基本可行解。
（2）2B =（1,3p p ），︱2B ︳≠0，2B 是基，1x ，3x 是基变量，2x 是非基变量。令
2x =0，得1x =2/3，3x =3/4，即123x x x ?? ? ? ???=??
???? ??34320为基解，同时为基本可行解，
z max =(2/3)*3+0+4/3*3=6。
（3）32,3()B p p =，︱3B ︳≠0，3B 是基，2x ，3x 是基变量，1x 是非基变量，令
1x =0，得2x =1，3x =1，即123x x x ?? ? ? ???=??
??? ??110为基解，同时为基本可行解，
z max =1+3=4。
综上所述，基解为123x x x ?? ? ? ???=????? ?
?-042，123x x x ?? ? ? ???=????? ??34320，123x x x ?? ? ? ???=?
???? ??110其中第二个和第三个为基本可行解，123x x x ?? ? ? ???=?
????
??34320为最优解。
2．分别用图解法和单纯形法求解下列线形规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点
???
??≥≤≤-+=0,21st.32max 2
112121x x x x x x x z
解：（1）图解法
有图解法知线性规划模型的可行域如阴影部分所示，令z=0，1，2……时，max z 逐渐增大，可行域是无界的，所以，此模型是无界解。 （2）单纯形法： 化为标准型为：
123412314
123,4max 230012st.,,0z x x x x x x x x x x x x x =+++-+=??+=?
?≥???
A= 11101
00
1-?? ??? ????
??=21b C=（2，3，0，0）
对应图中原点。以1为轴心项，换基迭代，得
此时对应图中A 点，坐标是 （1，0） 以1
为轴心项，换基迭代，得
此时对应图中B 点，坐标是 （2，3）因为，3=5>0,同时3x 对应的列小于等于0，则原模型有无界解。
??????
?
≥≤+≤≤+=0,18231224st.52max 2121212
1x x x x x x x x z
解：（1）图解法：
可行域如上图阴影部分所示，令z=0，1，2……做等值线，得出在c 点取最大值，c 点坐标为（2，6），max z=34 （2）单纯形法：化为标准型为：
123451324125max 250004212st.32180,1,2......5j z x x x x x x x x x x x x x j =+++++=?
?+=??
++=??≥=?
101000
201032
1A ?? ?= ? ??
? =（1,2345,,,p p p p p ） b= 4128??
? ? ?
??
C=（2，5，0，0，0） 取B=（345,,p p p ）为可行基，B C =（0，0，0）
单纯性表如下：
此时对应图中O 点，坐标为（0，0），以1为轴心项，换基迭代，得
此时对应图中A 点，坐标为（4，0） 以2为轴心项，换基迭代，得
此时对应图中B 点，坐标为（4，3） 以3
为轴心项，换基迭代，得
由于
σ基 =0，σ非基<0,所以存在唯一解，也是最优解。
此时对应图中
C
点，坐标为（2，6），max z=2*2+5*6=34，
()()T T x x x x x 0,0,2,6,2,,,,54321=
???????≥≤≤+≤++=0,93821222st.42max 21221
2121x x x x x x x x x z
解：（1）图解法：
可行域如图阴影部分，当z=0，1，2……做等值线，已知1224z x x =+与直线
1228x x +=的斜率相同，当z 与这条直线重合时，该模型取最大值，因此该模型有无穷多
个解，无穷多个解是B,C 两点线段中的点，max z=16
（2）单纯形法：化为标准型：
1234512312425max 24000221229st.390,1,2......5j z x x x x x x x x x x x x x x j =++++++=??++=??
+=??≥=?
221001
201003
1A ?? ?= ? ??
?= （1,2345,,,p p p p p ） b=1289?? ? ?
???
C=（2，4，0，0，0） B=（345,,p p p ） B C =（0，0，0） 单纯形表为：
此时对应图中点O ，坐标为（0，0），以2为轴心项，换基迭代，得
此时对应图中点A ，坐标为（6，0） 以1
为轴心项，换基迭代，得
此时对应图中点B ，坐标为（4，2） 由于σ≤0,又3x 为非基变量，且3σ=0，且此列存在正数，则此线性规划模型有无穷解。其中一个基本最优解为
()T T x x x x x )3,0,0,2,4(54
321
=，max z=2*4+4*2=16
3．用单纯形法求解下列线性规划问题
???????≥≤++≤+-≤-+-+=0,,,582242st.2min 321321321
321321x x x x x x x x x x x x x x x f
解：化为标准型：
12345612341235126max 200024
228st.50,1,2 (6)
j z x x x x x x x x x x x x x x x x x x j =--+++++-+=??-++=??
++=??≥=?
A=????? ??--100011010221001112 b=485?? ? ? ??? C=（-1，-2，1，0，0，0）
令B=（456,,p p p ） B 为可行基，B C =（0，0，0） 单纯形表如下：
以2
为轴心项，换基迭代，得
σ基 =0，σ非基<0,存在唯一解，此时1x =2x =0，3x =4。min f=0+2*0-4=-4
4．用大M 法求解下列线性规划问题
???
??≥≤+-≥++++=0
,,16210
24st.35max 321321321321x x x x x x x x x x x x f
解：化为标准型（加上人工变量a ）：
1234512341235max 53004210
st.2160,1,2......5j f x x x x x Ma x x x x a x x x x x j =++++-?++-+=?
-++=??≥=?
1421011
21
1
0A -??=
?-?? b=1016?? ?
?? C=（5，1，3，0，0）
以2为轴心项，换基迭代，得
以1
为轴心项，换基迭代，得
无界解。
5. 已知线性规划问题，用单纯形法计算时得到的中间某两步的计算表见表3-16所示，试将表中空白处的数字填上。
表3-16 单纯形迭代中的两步计算表
…
6．已知线性规划问题 332211max x c x c x c
z ++=
???
??=≥=+++=+++5,1,0st.2532322212114313212111 j x b x x a x a x a b x x a x a x a j
用单纯形法求解，得到最优单纯形表如表如表3-17所示：
表3-17 最终单纯形表
⑴求21232221131211,,,,,,,b b a a a a a a 的值； ⑵求321,,c c c 的值。
解：由题意可知：初始的基变量是4x ， 5x ，将最终单纯形表的基变量通过迭代转换为4x ，5x ，还原成最初单纯形表，如下：
从而得出：
91410251
2
12A ?? ?=
?
? ??? b=85?? ??? C=9,3,6,0,02?? ?
??
所以,11a =92 12a =1 13a =4 21a =5
2 22a =1 23a =2 1b =8 2b =5， 1c = 9
2 2c =
3 3c =6
7．某公司生产1、2两种产品，市场对1、2两种产品的需求量为：产品1在1-4月每月需求10000件，5-9月每月30000件，10-12月每月100000件，产品2在3-9月每月需求15000件，其它月每月50000件，该公司生产这两种产品的成本为：产品1在1-5月内生产每件5元，6-12月内生产每件4.5元；产品2在1-5月内生产每件8元，6-12月内生产每件7元。该公司每月生产这两种产品的能力总合不超过120000件。产品1容积每件0.2立方米，产品2每件0.4立方米，该公司仓库容量为15000立方米，占用公司仓库每月每立方米库容需1元；如该公司仓库不足时，可从外边租借，租用外面仓库每月每立方米库容需1.5元。试问在满足市场需求的情况下，该厂应如何安排生产，使总的费用最小？
8．某炼油厂使用三种原料油甲、乙、丙混合加工成A 、B 、C 三类不同的汽油产品，有关数据如下表3-18所示。另外，由于市场原因，A 的产量不得低于产品总量的40%。问该厂应如何安排生产才能使其总利润最大？
表3-18 三种原料的信息
解：设1x ，2x ，3x 分别为A 产品中甲、乙、丙的成分；4x ，5x ，6x 分别为B 产品中甲、乙、丙的成分；7x ，8x ，9x 分别为C 产品中甲、乙、丙的成分。由题意，有
max z=（3.060-0.450）*（1x +2x +3x ）+（2.565-0.360）*（4x +5x +6x ）+（2.025-0.270）*（7x +8x +9x ）-1.800*（1x +4x +7x ）-1.350*（2x +5x +8x ）-0.900*（3x +6x +9x ）
1472583
69
11
2331234
45664569789200025001200
0.6
.0.20.150.60.50,1,2,...,9j x x x x x x x x x x x x x x st x x x x x x x x x x x x x x x x j ???
?++≤?
++≤??++≤??
≥?++??≤?++??≥?
++???≤++???≤++??
≥=?
用计算机求解为：
9．线性规划的目标函数是求其值的极大化，在标准的单纯形法求解过程中得到如下表(其中21H ,H 是常数)
表3-19 求解中某一步的单纯形表
（1）在所有的空格上填上适当的数（可包含参数21H ,H ）
（2）判断下面四种情况在什么时候成立，说明理由。1）此解为最优解，写出相应的基解和目标函数值；2）此解为最优解，且此线性规划有无穷多最优解；3）此规划有无界解；4）此解不是最优解，但可用单纯形法得到下一个基可行解。
解：（1）
（2）1)当2-51H <0 即 1H >2
5时，此线性规划模型有唯一解，基解为
1232(,,)(0,,0)x x x H T =T 最优值为52H 。
2）2-51H =0，即 1H =2
5时，大于0，此线性规划模型有无穷多最优解。
3）2-51H >0且 1H <0，即1H
<0时， 此线性规划模型有无界解。
4）2-51H >0且 1H >0且2H >0, 即0<1H <2
5且2H >0时，此解不是最优解。
10．表3-20是求某极大化线性规划问题计算得到的单纯形表。表中无人工变量，1a 、2a 、
3a 、d 、1c 、2c 为待定常数。试说明这些常数分别取何值时，以下结论成立。
表3-20 极大化线性规划问题计算得到的单纯形表
⑵表中解为最优解，但存在无穷多最优解； ⑶该线性规划问题具有无界解；
⑷表中解非最优，为对解改进，换入变量为1x ，换出变量为6x 解：（1）当d≥0，1c <0 且 2c <0, 此线性规划模型有唯一解。
（2）当d≥0，1c =0 或 2c =0，1a <0, 此线性规划模型有无穷个最优解。 （3）当d≥0，2c >0 且 1a <0, 此线性规划模型有无界解。
（4）当d≥0，1c >0 且 3a >12d
，表中解非最优，为对解改进，换入变量为1x ，换出变量为6x 。
第四节
1．写出线性规划问题的对偶问题。
???
??≥≤+≤++++=0,,7341552st.5310max 321313213
21x x x x x x x x x x x z
???????≤≥≤++≥-+-=++++=0,083743
5522st.365max 3213213
213213
21x x x x x x x x x x x x x x x z ，无约束
???????≤≥=+-+-≤++≥-++++-=0,0,0
5732846253st.2423min 4215432153254215321x x x x x x x x x x x x x x x x x x x z ?????????==≥=====∑∑∑∑====),,2,1;,2,1( 0),,2,1( ),,2,1(
st.min 1
111
m i n j x n j b x m i a x x c z ij m
i j ij n j i ij m i n
j ij
ij
解：（1） （2）
??????
?≥≥+≥≥++=0
,533510
4y 2st.715min 212112121y y y y y y y y ω ??????
?≥≤≤+-≥++=+-++=0,0,3
3267525
4y st.835min 3213213213213
21y y y y y y y y y y y y y y 无约束ω
（3）
《管理运筹学》（第二版）课后习题参考答案 第1章 线性规划（复习思考题） 1．什么是线性规划线性规划的三要素是什么 答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0≥i b ，决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示：
课程学习 《管理运筹学基础》 判断正误 线性规划问题的一般模型中不能出现等式约束。 正确答案：说法错误 2.在线性规划模型的标准型中,b j（j=1，2，…m）一定是非负的。正确答案：说法正确 解答参考： 3. 判断正误 线性规划问题的基本解一定是基本可行解 正确答案：说法错误 解答参考： 5. 判断正误 同一问题的线性规划模型是唯一的。 正确答案：说法错误 解答参考： 12.第一个顶点和最后一个顶点相同的闭链叫回路。 正确答案：说法错误 解答参考： 14. 判断正误
Djisktra算法可求出非负赋权图中一顶点到任一顶点的最短距离。 正确答案：说法正确 解答参考： 15.简述编制统筹图的基本原则。 参考答案：统筹图是有向图，箭头一律向右；统筹图只有一个起始点。一个终点，没有缺口；两个节点之间只能有一个作业相连；统筹图中不能出现闭合回路。 17.简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较优。 参考答案：西北角法：按照地图中的上北下南，左西右东的判断，对调运表中的最西北角上的空格优先满足最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。最小元素法：对调运表中的最小运价对应的空格优先没醉最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。差值法：在运价表中，计算各行和各列的最小运价和次最小运价之差，选出最大者，它所在某行或某列中的最小运价对应的空格优先满足最大供应，重复这种做法，直至得到初始可行解。一般来讲，用差值法求出的初始可行解最接近最优解，也就是最优的。 2. 用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能找出最优解。 正确答案：说法正确 单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数的值增加更快。 正确答案：说法错误 解答参考： 6.若原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。 正确答案：说法正确 解答参考： 8.表上作业法中，任何一种确定初始基本可行解的方法都必须保证有（m + n -1）个变量。正确答案：说法正确 解答参考： 9.用分枝定界法求解一个极大化整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界 正确答案：说法正确
《管理运筹学》第四版课后习题解析（上） 第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 课程：管理运筹学 管理运筹学作业 第二章线性规划的图解法 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
《管理运筹学》(第二版)课后习题参考答案 第1章线性规划(复习思考题) 1. 什么是线性规划？线性规划的三要素是什么？ 答：线性规划(Lin ear Programmi ng , LF)是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2. 求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？答：(1)唯一最优解：只有一个最优点； (2)多重最优解：无穷多个最优解； (3)无界解：可行域无界，目标值无限增大； (4)没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3. 什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？ 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项 ' ，决策变量满足非负性。
如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业 来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明 “遅 约束的左边取值大于右边规划值，出现剩余量。 4?试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关 系。 答：可行解：满足约束条件 扎—‘丸 的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示： 5 ?用表格单纯形法求解如下线性规划 解：标准化 1 可行基：对应于基可行解的基，称为可行基。 基可行解 SA] + S 2
四 川 大 学 网 络 教 育 学 院 模 拟 试 题( A ) 《管理运筹学》 一、 单选题（每题２分，共20分。） 1．目标函数取极小（minZ ）的线性规划问题可以转化为目标函数取极大的线性规 划问题求解，原问题的目标函数值等于（ C ）。 A. maxZ B. max(-Z) C. –max(-Z) D.-maxZ 2. 下列说法中正确的是（ B ）。 Ａ．基本解一定是可行解 Ｂ．基本可行解的每个分量一定非负 Ｃ．若B 是基，则B 一定是可逆Ｄ．非基变量的系数列向量一定是线性相关的 3．在线性规划模型中，没有非负约束的变量称为 （ D ） 多余变量 B ．松弛变量 C ．人工变量 D ．自由变量 4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得（ A ）。 Ａ．多重解 Ｂ．无解 Ｃ．正则解 Ｄ．退化解 5．对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足 （ D ）。 A ．等式约束 B ．“≤”型约束 C ．“≥”约束 D ．非负约束 6. 原问题的第ｉ个约束方程是“＝”型，则对偶问题的变量i y 是（ B ）。 Ａ．多余变量 Ｂ．自由变量 Ｃ．松弛变量 Ｄ．非负变量 7.在运输方案中出现退化现象，是指数字格的数目( C )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1 8. 树Ｔ的任意两个顶点间恰好有一条（ B ）。 Ａ．边 Ｂ．初等链 Ｃ．欧拉圈 Ｄ．回路 9．若G 中不存在流f 增流链，则f 为G 的 （ B ）。 A ．最小流 B ．最大流 C ．最小费用流 D ．无法确定 10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足（ D ） Ａ．等式约束 Ｂ．“≤”型约束 Ｃ．“≥”型约束 Ｄ．非负约束 二、多项选择题（每小题4分，共20分） 1．化一般规划模型为标准型时，可能引入的变量有 （ ） A ．松弛变量 B ．剩余变量 C ．非负变量 D ．非正变量 E ．自由变量 2．图解法求解线性规划问题的主要过程有 （ ） A ．画出可行域 B ．求出顶点坐标 C ．求最优目标值 D ．选基本解 E ．选最优解 3．表上作业法中确定换出变量的过程有 （ ） A ．判断检验数是否都非负 B ．选最大检验数 C ．确定换出变量 D ．选最小检验数 E ．确定换入变量 4．求解约束条件为“≥”型的线性规划、构造基本矩阵时，可用的变量有 （ ） A ．人工变量 B ．松弛变量 C. 负变量 D ．剩余变量 E ．稳态 变量 5．线性规划问题的主要特征有 （ ） A ．目标是线性的 B ．约束是线性的 C ．求目标最大值 D ．求目标最小值 E ．非线性 三、 计算题（共60分） 1. 下列线性规划问题化为标准型。(10分)
上交作业课程题目可以打印，答案必须手写，否则该门成绩0分。 管理运筹学 作业题 一、名词解释(每题3分，共15分) 1. 可行解：满足某线性规划所有的约束条件（指全部前约束条件和后约束条件）的任意一 组决策变量的取值，都称为该线性规划的一个可行解，所有可行解构成的集合称为该线性规划的可行域（类似函数的定义域），记为K 。 2. 最优解：使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称 为该线性规划的一个最优解。线性规划的最优解不一定唯一，若其有多个最优解，则所有最优解所构成的集合称为该线性规划的最优解域。 3. 状态：指每个阶段开始时所处的自然状态或客观条件。 4. 决策树：决策树(Decision Tree ）是在已知各种情况发生概率的基础上，通过构成决策 树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。 5. 最大最小准则：最大最小准则又称小中取大法或悲观法。为不确定型决策的决策准则之 一，其决策的原则是“小中取大”。这种决策方法的思想是对事物抱有悲观和保守的态度，在各种最坏的可能结果中选择最好的。决策时从决策表中各方案对各个状态的结果选出最小值，即在表的最右列，再从该列中选出最大者。这种方法的基本态度是悲观与保守。其基本思路是首先找出最不利情况下的最大收益。 二、 简答题（每题6分，共24分） 1. 简述单纯形法的基本步骤。 答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数j σ对初始基可行解进行最优性检验，若0≤j σ ，则求得最优解，否则，进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得新的基本可行解；（5）重复步骤（3）、（4）直至0≤j σ，求得最优解为止。 2. 简述动态规划的基本方程。 答：对于n 阶段的动态规划问题，在求子过程上的最优指标函数时，k 子过程与k+1过程有如下递推关系： 对于可加性指标函数，基本方程可以写为 n k s f x s r s f k k k k k s D x k k opt k k k ,,2,1)}(),({)(11) ( =+=++∈ 终端条件：f n+1 (s n+1) = 0
管理运筹学 ——管理科学方法谢家平 第一章 第一章 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 ，让其进基，目标函数
09 <<运筹>>期末考试试卷（A）答案 一、不定项选择题（每小题2分共20分） 1、A 2、B 3、ABCD 4、ABC 5、D 6、C 7、B 8、ABCD 9、ABC 10、ABC 二、名词解释（每小题4分，共20分） 1、运筹学是一门以人机系统的组织、管理为对象，应用数学和计算机等工具来研究各类有限资源的合理规划使用期并提供优化决策方案的科学。 2、线性规划是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。 3、如果系统中包含元素A、B、C、K….等，按照经典意义（非模糊，非统计意义）的原则来聚类。 4、系统的综合性原则是指系统内部各组成部分的联系与协调，包含要素间的协调及系统与环境问题的协调。 5、TSP问题称为“旅行推销员问题”，是指：有N个城市A、B、…….等，它们这间有一定的距离，要求一条闭合路径，由某城市出发，每个城市经历过一次，最终返回原城市，所经历的路程最短。 三、简答题（每小题5分，共28分） 1、列出一些企业产品结构优化的柔性模型约束条件。 （1）关键设备的生产能力（2）各类能源的约束（3）工艺的约束 （4）产品类结构关系，以及物流过程中上、下游产品供需的约束 （5）某些产品的下限约束（6）非负约束 2、排队规则：损失制等待制：先到先服务、后到先服务、随机服务、优先权 服务混合制 3、运筹学的特点：（1）以最优性为核心。（2）以模型化为特征（3）以计算机为主要实现手段。（4）多学科交融 4、神经元的功能：（1）整合功能（2）兴奋与抑制（3）突触延时与不应期（4）学习、遗忘与疲劳
四、应用题。（每题15分，共45分） 1、设A、B的产量为X、Y 模型：目标MAX利润=500X+900Y 约束条件：9X+4Y≤360 4X+5Y≤200 3X+10Y≤300 X、Y均大于或等于零 图解略 最优解：X=20千克 Y=24千克利润31600元 2、企业在选择运用“农村包围城市”还是“城市中心”的指导思想时，应考虑自己的条件，竞争对手的情况，宏观和中观形势。 如，我国不少实力较弱的汽车企业，在发展之初，面临国内合资企业和国外汽车巨头的压力下，以农村，或三、四线城市为突破口，先在这些国内合资企业和国外汽车巨头不太重视的地区发展市场，在积累资金、经验、管理、技术等生产经营资源后，向大城市等竞争激烈的地区进军。 如果企业与国外合资，或在资金、技术、品牌、管理等方面有较大的优势，企业可以一开始就以广州等一线城市为主战场。 3、（1）如果两国没有任何的协调，A国最终会选择报复，因为只要A国选择报复，不论B国如何选择，对A国来说都最佳选择。反之亦然。 （2）如果两国协调，如果协调成功两国的对策是都不报复，如果两国协调不成功，两国都会选择报复。
第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.
管理运筹学第二版课后 习题参考答案 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 列出单纯形表
第一章 第一章 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 ，让其进基，目标函数的值仍然保持原值。如果同时存在最小θ值，说明有离基变量，则该问题在两个顶点上同时达到最优，为无穷多最优解。无界解：若某个非基变量xNk 的检验数σk> 0 ，但其对应的系数列向量P k' 中，每一个元素a ik' (i=1,2,3,…,m)均非正数，即有进基变量但找不到离基变量。
四、把下列线性规划问题化成标准形式： 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：
根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250，280和120件。问如何安排生产计划，使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省? 1．某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示： 起运时间服务员数 2—6 6—10 10一14 14—18 18—22 22—2 4 8 10 7 12 4 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少?
五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当 于图解法可行域中的哪一个顶点。
六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。
八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10 X l X2X3X4 —10b-1f g X32C O11／5 X l a d e01 (1)求表中a～g的值 (2)表中给出的解是否为最优解? （1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2）表中给出的解为最优解 第四章线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x1+2x2+4x3
第二章 2.5 表2-3为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 12max 53z x x =+，约束形式为≤，34,x x 为松弛变量，表中解代入目标函数后得10z =。 (1)求a ~g 的值； (2)表中给出的解是否为最优解。 解：a=2,b=0,c=0,d=1,e=4/5,f=0,g=5；表中给出的解为最优解。 2.6 表2-4中给出某求最大化线性规划问题的初始单纯形表及迭代后的表，45,x x 为松弛变量，求表中a ~l 的值及各变量下标m ~t 的值。 解：a=-3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=-5,k=3/2,l=0；变量的下标为m —4,n —5,s —1,t —6 2.10下述线性规划问题：
2.11某单位加工制作100套工架，每套工架需用长为2.9m 、2.1m 和1.5m 的圆钢各一根。已知原材料长7.4m 。问如何下料使得所用的原材料最省？ 解：简单分析可知，在每一根原材料上各截取一根2.9m,2.lm 和1.5m 的圆钢做成一套工架，每根原材料剩下料头0.9m ，要完成100套工架，就需要用100根原材料，共剩余90m 料头。若采用套截方案，则可以节省原材料，下面给出了几种可能的套截方案，如表2-5所示。 实际中，为了保证完成这100套工架，使所用原材料最省，可以混合使用各种下料方案。 设按方案A,B,C,D,E 下料的原材料数分别为x 1,x 2,x 3,x 4,x 5，根据表2-5可以得到下面的线性规划模型 12345124345 1235min 00.10.20.30.82100 22100..3231000,1,2,3,4,5 i z x x x x x x x x x x x s t x x x x x i =++++++=??++=?? +++=??≥=? 用大M 法求解此模型的过程如表2-6所示，最优解为：x *=(0,40,30,20,0)T ，最优值为z *=16。
《管理运筹学》作业题参考答案 一、简答题 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
（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
0后退" 地址匹I hi ip://wvw.doc in. c om/p-34224062, html 笫2章线性规划的图解法 a 可行城为OABC b ?聲值线为图中W 线所示。 C.IIIRH 可知.加优解为B 点，衆优M ： x, = y x 2 = y , 69 〒 文件匕）編辑电）查看电）版藏逻 工具① 帮 址优JI 杯沥数们:
b 无可行解 C 无界斛 d 无可行解 e 尢穷多解 20 戈厂三 92 f 冇唯一解 ?两数值为学 8 3 3、Vh a 标准形式： max / = 3? + 2r 2 + 0打 + 0s 2 + 0% max / = 一4* 一 6X 3 - 0刁-0孔 v =（）2 冇呱一解宀―“函数值为3.6 x 2 ■ 0.6
3勺 _ 兀2 一 B ■ 6 X] + 2X2+s2 = 10 7.v1 - 6A2二 4 f汕』2 2 0 C标准形式:max f =-?i； + 2.v s一2x； - 0片 - Qs2 -a— + 5X2-5A* +斗二70 2A； - 5.Vj + 5xj 二50 3x\ + 2x z一2r； - s2 =- 30 f 2 , *2，?，*2 2 ° 4、斡 标浪形式：max c = 10A（十5.v2十0、十0.T2 3\ + 4.V2 +耳二9 5x1 + 2X2 +52 = 8 兀“工2?亠? 0 5 .餅： 标ME形式：min f - 11xj + + 5 + O.v2 + O.v3 10A,+2X2 - 51— 20 3.V, + 3.V2-s2 =18 4x1 + 9X2一内=36 斗=0,y2 =0,^ = 13 6 >贻 b 1 s q 兰 3 c 2Sq S6 x2 = 4 e 斗G（4,8）x2 = 16 -2v1 2 f变化。廉斜率从-彳变为-1
5、线性规划数学模型具备哪几个要素？答：（1）.求一组决策变量x i或x ij的值（i =1，2，…m j=1，2…n）使目标函数达到极大或极小；（2）.表示约束条件的数学式都是线性等式或不等式；（3）.表示问题最优化指标的目标函数都是决策变量的线性函数 第二章线性规划的基本概念 一、填空题 1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。 2．图解法适用于含有两个变量的线性规划问题。 3．线性规划问题的可行解是指满足所有约束条件的解。 4．在线性规划问题的基本解中，所有的非基变量等于零。 5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关 6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。7．线性规划问题有可行解，则必有基可行解。 8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。 9．满足非负条件的基本解称为基本可行解。 10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。 11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。 13．线性规划问题可分为目标函数求极大值和极小_值两类。 14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。
15．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解 16．在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。 17．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。 18.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。 19.如果某个变量X j为自由变量，则应引进两个非负变量X j′,X j〞,同时令X j＝X j′－X j。 20.表达线性规划的简式中目标函数为max(min)Z=∑c ij x ij。 21..(2.1 P5))线性规划一般表达式中，a ij表示该元素位置在i行j列。 二、单选题 1．如果一个线性规划问题有n个变量，m个约束方程(m 第一章线性规划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 12 1 2 5.max23 28 416 412 0,1,2 maxZ. j Z x x x x x x x j =+ ?+≤ ? ≤ ? ? ≤ ? ?≥= ? 如图所示，在（4，2）这一点达到最大值为2 6将线性规划模型化成标准形式： Min z=x1-2x2+3x3 ? ? ? ? ? ? ? ≥ ≥ - = + + - ≥ + - ≤ + + 无约束 3 2 1 3 2 1 3 2 1 3 2 1 ,0 ,0 5 2 3 2 7 x x x x x x x x x x x x 解：令Z’=-Z,引进松弛变量x4≥0，引入剩余变量x5≥0，并令x3=x3’-x3’’,其中x3’≥0,x3’’≥0 Max z’=-x1+2x2-3x3’+3x3’’ ? ? ? ? ? ? ? ≥ ≥ ≥ ≥ ≥ ≥ - = + + - = - - + - = + - + + ,0 ,0 '' ,0 ' ,0 ,0 5 2 3 2 '' ' 7 '' ' 5 4 3 3 2 1 3 2 1 5 3 3 2 1 4 3 3 2 1 x x x x x x x x x x x x x x x x x x x 管理运筹学(本科)(参考答案) 上交作业课程题目可以打印，答案必须手写，否则该门成绩0分。 管理运筹学作业题 一、名词解释(每题3分，共15分) 1.可行解：满足某线性规划所有的约束条件（指全部前约束条件和后约束条 件）的任意一组决策变量的取值，都称为该线性规划的一个可行解，所有可行解构成的集合称为该线性规划的可行域（类似函数的定义域），记为K。 2.最优解：使某线性规划的目标函数达到最优值（最大值或最小值）的任一可 行解，都称为该线性规划的一个最优解。线性规划的最优解不一定唯一，若其有多个最优解，则所有最优解所构成的集合称为该线性规划的最优解域。 3.状态：指每个阶段开始时所处的自然状态或客观条件。 4.决策树：决策树(Decision Tree）是在已知各种情况发生概率的基础上，通 过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。 5.最大最小准则：最大最小准则又称小中取大法或悲观法。为不确定型决策的 决策准则之一，其决策的原则是“小中取大”。这种决策方法的思想是对事物抱有悲观和保守的态度，在各种最坏的可能结果中选择最好的。决策时从决策表中各方案对各个状态的结果选出最小值，即在表的最右列，再从该列中选出最大者。这种方法的基本态度是悲观与保守。其基本思路是首先找出最不利情况下的最大收益。 二、 简答题（每题6分，共24分） 1. 简述单纯形法的基本步骤。 答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数j σ对初始基可行解进行最优性检验，若0≤j σ ，则求得最优解，否则，进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得新的基本可行解；（5）重复步骤（3）、（4）直至0≤j σ，求得最优解为止。 2. 简述动态规划的基本方程。 答：对于n 阶段的动态规划问题，在求子过程上的最优指标函数时，k 子过程与k+1过程有如下递推关系： 对于可加性指标函数，基本方程可以写为 n k s f x s r s f k k k k k s D x k k opt k k k ,,2,1)} (),({)(11) ( =+= ++∈ 终端条件：f n+1 (s n+1) = 0 对于可乘性指标函数，基本方程可以写为 n k s f x s r s f k k k k k s D x k k opt k k k ,,2,1)} (),({)(11) ( =?= ++∈ 终端条件：f n+1 (s n+1) = 1 3. 简述破圈法求最小生成树的步骤。 答：第1 步: 令i=1, E0=Φ, G0=G;第2 步: 取边ei ∈E ( Gi- 1) 即E\Ei- 1, 令Ei =Ei- 1∪{ei}, 使得Gi= G [E\Ei] 连通, 且W ( ei) 权尽可能大; 第3 步: 若i运筹学课后习题答案
管理运筹学(本科)(参考答案)复习过程
相关主题
文本预览