运筹学：线性规划的数学模型与单纯形法习题与答案

运筹学复习题第一章 线性规划及单纯形法一、单选题1. 线性规划具有无界解是指A. 可行解集合无界B. 有相同的最小比值C. 存在某个检验数0k λ>，且0(1,2,,)ik a i m ≤=D. 最优表中所有非基变量的检验数非零 2. 线性规划具有唯一最优解是指A. 最优表中非基变量检验数全部非零B. 不加入人工变量就可进行单纯形法计算C. 最优表中存在非基变量的检验数为零D. 可行解集合有界 3. 线性规划具有多重最优解是指A. 目标函数系数与某约束系数对应成比例B. 最优表中存在非基变量的检验数为零C. 可行解集合无界D. 基变量全部大于零 4. 使函数Z=-x 1+x 2+2x 3 减小最快的方向是A. (-1,1,2)B. (1,-1,-2)C. (1,1,2)D. (-1,-1,-2) 5. 当线性规划的可行解集合非空时一定 A. 包含点X =(0,0,···,0) B. 有界 C. 无界 D. 是凸集 6. 线性规划的退化基可行解是指A. 基可行解中存在为零的非基变量B. 基可行解中存在为零的基变量C. 非基变量的检验数为零D. 所有基变量不等于零 7. 线性规划无可行解是指A. 第一阶段最优目标函数值等于零B. 进基列系数非正C. 用大M 法求解时，最优解中还有非零的人工变量D. 有两个相同的最小比值 8. 若线性规划不加入人工变量就可以进行单纯形法计算A. 一定有最优解B. 一定有可行解C. 可能无可行解D. 全部约束是小于等于的形式 9. 设线性规划的约束条件为123124222401234 (,,,)jx x x x x x x j ⎧++=⎪++=⎨⎪≥=⎩ 则非退化基本可行解是A. (2， 0，0， 0)B. (0，2，0，0)C. (1，1，0，0)D. (0，0，2，4) 10. 设线性规划的约束条件为123124222401234 (,,,)jx x x x x x x j ⎧++=⎪++=⎨⎪≥=⎩ 则非可行解是A. (2，0，0， 0)B. (0，1，1，2)C. (1，0，1，0)D. (1，1，0，0) 11. 线性规划可行域的顶点一定是A. 可行解B. 非基本解C. 非可行解D. 是最优解 12. 1234min z x x =+1212124220,x x x x x ⎧+≥⎪+≤⎨⎪≥⎩ A. 无可行解 B.有唯一最优解 C.有无界解 D.有多重最优解13. 12122124432450,max z x x x x x x =-⎧+≤⎪≤⎨⎪≥⎩A. 无可行解B. 有唯一最优解C. 有多重最优解D. 有无界解 14. X 是线性规划的基本可行解则有A. X 中的基变量非负，非基变量为零B. X 中的基变量非零，非基变量为零C. X 不是基本解D. X 不一定满足约束条件 15. X 是线性规划的可行解，则错误的结论是A. X 可能是基本解B. X 可能是基本可行解C. X 满足所有约束条件D. X 是基本可行解 16. 下例错误的说法是A. 标准型的目标函数是求最大值 B 标准型的目标函数是求最小值 C. 标准型的常数项非正 D. 标准型的变量一定要非负 17. 为什么单纯形法迭代的每一个解都是可行解？答：因为遵循了下列规则 A. 按最小比值规则选择换出变量B. 先进基后出基规则C. 标准型要求变量非负规则D. 按检验数最大的变量选择换入变量 18. 线性规划标准型的系数矩阵A m×n ，要求A. 秩(A )=m 并且m <nB. 秩(A )=m 并且m <=nC. 秩(A )=m 并且m =nD. 秩(A )=n 并且n <m 19. 下例错误的结论是A. 检验数是用来检验可行解是否是最优解的数B. 检验数是目标函数用非基变量表达的系数C. 不同检验数的定义其检验标准也不同D. 检验数就是目标函数的系数 20. 对取值为无约束的变量j x ，通常令'''j j j x x x =-，其中''',0j j x x ≥；在用单纯形法求得的解中不可能出现A. '0j x =,''0j x ≥ B. '0j x =,''0j x = C. '0j x >,''0>j x D. '0j x >,''0j x =21．运筹学是一门A. 定量分析的学科B. 定性分析的学科C. 定量与定性相结合的学科D. 定量与定性相结合的学科，其中分析与应用属于定性分析，建立模型与求解属于定量分析二、设某种动物每天至少需要700克蛋白质、30克矿物质、100毫克维生素。

运筹学思考练习题答案第⼀章 L.P 及单纯形法练习题答案⼀、判断下列说法是否正确1. 线性规划模型中增加⼀个约束条件，可⾏域的范围⼀般将缩⼩，减少⼀个约束条件，可⾏域的范围⼀般将扩⼤。

(?)2. 线性规划问题的每⼀个基解对应可⾏域的⼀个顶点。

(?)3. 如线性规划问题存在某个最优解，则该最优解⼀定对应可⾏域边界上的⼀个点。

(?)4. 单纯形法计算中，如不按最⼩⽐值原则选取换出变量，则在下⼀个基可⾏解中⾄少有⼀个基变量的值为负。

(?)5. ⼀旦⼀个⼈⼯变量在迭代中变为⾮基变量后，该变量及相应列的数字可以从单纯形表中删除，⽽不影响计算结果。

(?)6. 若1X 、2X 分别是某⼀线性规划问题的最优解，则1212X X X λλ=+也是该线性规划问题的最优解，其中1λ、2λ为正的实数。

(?)7. 线性规划⽤两阶段法求解时，第⼀阶段的⽬标函数通常写为ai iMinZ x =∑(x ai 为⼈⼯变量)，但也可写为i ai iMinZ k x =∑，只要所有k i 均为⼤于零的常数。

(?)8. 对⼀个有n 个变量、m 个约束的标准型的线性规划问题，其可⾏域的顶点恰好为m n C 个。

(?)9. 线性规划问题的可⾏解如为最优解，则该可⾏解⼀定是基可⾏解。

(?)10. 若线性规划问题具有可⾏解，且其可⾏域有界，则该线性规划问题最多具有有限个数的最优解。

(?)⼆、求得L.P 问题121231425j MaxZ 2x 3x x 2x x 84x x 164x x 12x 0;j 1,2,,5=+++=??+=??+=?≥=的解如下： X ⑴=(0,3,2,16,0)T ;X ⑵=(4,3,-2,0,0)T ;X ⑶=(3.5,2,0.5,2,4)T ;X ⑷=(8,0,0,-16,12)T ; =(4.5,2,-0.5,-2,4)T ; X ⑹=(3,2,1,4,4)T ;X ⑺=(4,2,0,0,4)T 。

要求：分别指出其中的基解、可⾏解、基可⾏解、⾮基可⾏解。

1、图解法适用于含有（）个变量的线性规划问题。

正确答案：两或22、线性规划问题的可行解是指满足（）的解。

正确答案：所有约束条件3、在线性规划问题的基本解中，所有的非基变量等于（）。

正确答案：零或04、若线性规划问题有最优解，则最优解一定可以在可行域的（）达到。

正确答案：顶点或极点5、线性规划问题有可行解，则必有（）。

正确答案：基可行解6、如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其（）的集合中进行搜索即可得到最优解。

正确答案：基可行解7、满足（）条件的基本解称为基本可行解。

正确答案：非负8、求解线性规划问题可能的结果有四种，分别是（）。

正确答案：无解，有唯一最优解，有无穷多个最优解和退化解9、求一个线性函数在一组（）约束条件下的最大化或最小化问题，称为线性规划问题。

正确答案：线性1、若x、y满足约束条件{x≤2 y≤2x+y≥2则z=x+2y的取值范围是（）。

A. [2,6]B. [2,5]C. [3,6]D. [3,5]正确答案：A2、为化为标准形式而引入的松弛变量在目标函数中的系数应为（）。

A.0B.1C.2D.3正确答案：A3、若线性规划问题没有可行解，可行解集是空集，则此问题（）。

A.没有无穷多最优解B.没有最优解C.有无界解D.没有无界解正确答案：B4、在单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中（）。

A.不影响解的可行性B.至少有一个基变量的值为负C.找不到出基变量D.找不到进基变量正确答案：B5、用单纯形法求解极大化线性规划问题中，若某非基变量检验数为零，而其他非基变量检验数全部<0，则说明本问题（）。

A.有惟一最优解B.有多重最优解C.无界D.无解正确答案：B6、单纯形法当中，入基变量的确定应选择检验数（）。

A.绝对值最大B.绝对值最小C.正值最大D.负值最小正确答案：C7、在单纯形表的终表中，若非基变量的检验数有0，那么最优解（）。

A.不存在B.唯一C.无穷多D.无穷大正确答案：A8、线性规划模型不包括下列（）要素。

第一章 线性规划1、由图可得：最优解为2、用图解法求解线性规划： Min z=2x 1+x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤≥+≤+-01058244212121x x x x x x解：由图可得：最优解x=1.6,y=6.4Max z=5x 1+6x 2⎪⎩⎪⎨⎧≥≤+-≥-0,23222212121x 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 ， 所以⎪⎩⎪⎨⎧==2321x xmax Z = 8.1212125.max 23284164120,1,2maxZ .jZ x x x x x x x j =+⎧+≤⎪≤⎪⎨≤⎪⎪≥=⎩如图所示，在（4，2）这一点达到最大值为26将线性规划模型化成标准形式：Min z=x 1-2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≥-=++-≥+-≤++无约束321321321321,0,052327x 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’’≥0Max z ’=-x 1+2x 2-3x 3’+3x 3’’⎪⎪⎩⎪⎪⎨⎧≥≥≥≥≥≥-=++-=--+-=+-++0,0,0'',0',0,05232'''7'''5433213215332143321x x x x x x x x x x x x x x x x x x x7将线性规划模型化为标准形式Min Z =x 1+2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≤-=--≥++-≤++无约束，321321321321,00632442392-x x x x x x x x x x x x解：令Z ’ = -z ，引进松弛变量x 4≥0,引进剩余变量x 5≥0,得到一下等价的标准形式。

一、思考题1． 什么是线性规划模型，在模型中各系数的经济意义是什么？ 2． 线性规划问题的一般形式有何特征？3． 建立一个实际问题的数学模型一般要几步？4． 两个变量的线性规划问题的图解法的一般步骤是什么？5． 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？6． 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。

7． 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。

8． 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。

9． 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。

1． 线性规划问题的最优解一定在可行域的顶点达到。

2． 线性规划的可行解集是凸集。

3． 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。

4． 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。

5． 线性规划问题的每一个基本解对应可行域的一个顶点。

6． 如果一个线性规划问题有可行解，那么它必有最优解。

7． 用单纯形法求解标准形式（求最小值）的线性规划问题时，与0>j σ对应的变量都可以被选作换入变量。

8． 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。

9． 单纯形法计算中，选取最大正检验数k σ对应的变量k x作为换入变量，可使目 标函数值得到最快的减少。

10． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。

1 3 第一章线性规划与单纯形法运筹学习题集第一章线性规划与单纯形13第一章线性规划与单纯形法运筹学习题集第一章线性规划与单纯形法复习思考题1. 试述线性规划数学模型的结构及各要素的特征。

2. 求解线性规划问题时可能出现哪几种结果?哪些结果反映建模时有错误?3. 什么是线性规划问题的标准形式?如何将一个非标准型的线性规划问题转化为标准形式?4. 试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。

5. 试述单纯形法的计算步骤，如何在单纯形表上判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解?6. 如果线性规划的标准型变换为求目标函数的极小化min z，则用单纯形法计算时如何判别问题已得到最优解?7. 在确定初始可行基时，什么情况下要在约束条件中增添人工变量?在目标函数中人工变量前的系数为(-M)的经济意义是什么?8. 什么是单纯形法计算的两阶段法?为什么要将计算分成两个阶段进行,如何根据第一阶段的计算结果来判定第二阶段的计算是否需要继续进行?9. 简述退化的含义及处理退化的勃兰特规则。

10. 举例说明生产和生活中应用线性规划的可能案例，并对如何应用进行必要描述。

11. 判断下列说法是否正确:(a) 图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的;(b) 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大;(c) 线性规划问题的每一个基解对应可行域的一个顶点;(d) 如线性规划问题存在可行域，则可行域一定包含坐标的原点;(e) 对取值无约束的变量xj，通常令xj=x′j-x″j，其中x′j?0，x″j?0，在用单纯形法求得的最优解中有可能同时出现x′j,0，x″j,0;(f) 用单纯形法求解标准型的线性规划问题时，与σj,0对应的变量都可以被选作换入变量; (g) 单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负;(h) 单纯形法计算中，选取最大正检验数σk对应的变量xk作为换入变量，将使目标函数值得到最快的增长;(i) 一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果;(j) 线性规划问题的任一可行解都可以用全部基可行解的线性组合表示; (k)若X1，X2分别是某一线性规划问题的最优解，则X=λ1X1+λ2X2也是该线性规划问题的最优解，其中λ1、λ2可以为任意正的实数;(l) 线性规划用两阶段法求解时，第一阶段的目标函数通常写为minz=?ixai(xai为人工变量)，但也可写为min z=?ikixai,只要所有ki均为大于零的常数;(m)对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为Cmn个; (n) 单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解; (o) 线性规划问题的可行解如为最优解，则该可行解一定是基可行解; (p) 若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解;(q) 线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优;(r) 将线性规划约束条件的“?”号及“?”号变换成“=”号，将使问题的最优目标函数值得到改善;(s) 线性规划目标函数中系数最大的变量在最优解中总是取正的值;(t) 一个企业利用3种资源生产4种产品，建立线性规划模型求解得到的最优解中，最多只含有3种产品的组合;(u) 若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解; (v) 一个线性规划问题求解时的迭代工作量主要取决于变量数的多少，与约束条件的数量关系相对较小。

四、把下列线性规划问题化成标准形式：2、minZ=2x1-x2+2x3五、按各题要求。

建立线性规划数学模型1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。

月销售分别为250，280和120件。

问如何安排生产计划，使总利润最大。

2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省?某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示： 起运时间 服务员数 2—6 6—10 10一14 14—18 18—22 22—24 8 10 7 12 4每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少?五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当于图解法可行域中的哪一个顶点。

六、用单纯形法求解下列线性规划问题：七、用大M法求解下列线性规划问题。

并指出问题的解属于哪一类。

八、下表为用单纯形法计算时某一步的表格。

已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10XlX2 X3 X4 —10 b-1 f g X3 2 C O 1 1／5 Xlade1(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六、已知线性规划问题应用对偶理论证明该问题最优解的目标函数值不大于25七、已知线性规划问题maxZ=2x1+x2+5x3+6x4其对偶问题的最优解为Yl﹡=4，Y2﹡=1，试应用对偶问题的性质求原问题的最优解。

习题一1.1 用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。

(1) min z ＝6x1＋4x2(2) max z ＝4x1＋8x2st. 2x1＋x2≥1 st. 2x1＋2x2≤103x1＋4x2≥1.5 －x1＋x2≥8x1, x2≥0 x1, x2≥0(3) max z ＝x1＋x2(4) max z ＝3x1－2x2st. 8x1＋6x2≥24 st. x1＋x2≤14x1＋6x2≥－12 2x1＋2x2≥42x2≥4 x1, x2≥0x1, x2≥0(5) max z ＝3x1＋9x2(6) max z ＝3x1＋4x2st. x1＋3x2≤22 st. －x1＋2x2≤8－x1＋x2≤4 x1＋2x2≤12x2≤6 2x1＋x2≤162x1－5x2≤0 x1, x2≥0x1, x2≥01.2. 在下列线性规划问题中，找出所有基本解，指出哪些是基本可行解并分别代入目标函数，比较找出最优解。

(1) max z ＝3x1＋5x2(2) min z ＝4x1＋12x2＋18x3st. x1＋x3＝4 st. x1＋3x3－x4＝32x2＋x4＝12 2x2＋2x3－x5＝53x1＋2x2＋x5＝18 x j≥0 （j＝1, (5)x j≥0 （j＝1, (5)1.3. 分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。

(1) max z ＝10x1＋5x2st. 3x1＋4x2≤95x1＋2x2≤8x1, x2≥0(2) max z ＝100x1＋200x2st. x1＋x2≤500x1≤2002x1＋6x2≤1200x1, x2≥01.4. 分别用大M法和两阶段法求解下列线性规划问题，并指出问题的解属于哪一类：(1) max z ＝4x1＋5x2＋x3(2) max z ＝2x1＋x2＋x3st. 3x1＋2x2＋x3≥18 st. 4x1＋2x2＋2x3≥42x1＋x2≤4 2x1＋4x2≤20x1＋x2－x3＝5 4x1＋8x2＋2x3≤16x j≥0 （j＝1,2,3）x j≥0 （j＝1,2,3）(3) max z ＝ x 1＋ x 2 (4) max z ＝x 1＋2x 2＋3x 3－x 4 st. 8x 1＋6x 2≥24 st. x 1＋2x 2＋3x 3＝154x 1＋6x 2≥－12 2x 1＋ x 2＋5x 3＝202x 2≥4 x 1＋2x 2＋ x 3＋ x 4＝10x 1, x 2≥0 x j ≥0 （j ＝1, (4)(5) max z ＝4x 1＋6x 2 (6) max z ＝5x 1＋3x 2＋6x 3 st. 2x 1＋4x 2 ≤180 st. x 1＋2x 2＋ x 3≤183x 1＋2x 2 ≤150 2x 1＋ x 2＋3x 3≤16 x 1＋ x 2＝57 x 1＋ x 2＋ x 3＝10x 2≥22 x 1, x 2≥0，x 3无约束 x 1, x 2≥01.5 线性规划问题max z ＝CX ，AX ＝b ，X ≥0，如X*是该问题的最优解，又λ＞0为某一常数，分别讨论下列情况时最优解的变化：（1） 目标函数变为max z ＝λCX ；（2） 目标函数变为max z ＝（C ＋λ）X ；（3） 目标函数变为max z ＝C X ，约束条件变为AX ＝λb 。

3
B1：2.0
3
需要量（套）
200
150
问怎样下料使得（1）用料最少；（2）余料最少．
【解】第一步：求下料方案，见下表。
方案
一
二
三
四
五
六
七
八
九
十
十一
十二
十三
十四
需要量
B1:2.7m
2
1
1
1
0
0
0
0
0
0
0
0
0
0
300
B2:2m
0
1
0
0
3
2
2
1
1
1
0
0
0
0
450
A1:1.7m
0
0
1
0
0
1
0
2
1
0
3
2
1
0
(2)
【解】最优解X＝（3/4，7/2）；最优值Z=－45/4
(3)
【解】最优解X＝（4，1）；最优值Z=－10
(4)
【解】最优解X＝（3/2，1/4）；最优值Z=7/4
(5) 【解】最优解X＝（3，0）；最优值Z=3
(6)
【解】无界解。
(7)
【解】无可行解。
(8)
【解】最优解X＝（2，4）；最优值Z=13
【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为
1.3建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格及数量如表1－23所示：
表1－23窗架所需材料规格及数量
型号A
型号B
每套窗架需要材料
长度（m）

第一章 线性规划及单纯形法（作业）1.4 分别用图解法和单纯型法求解下列线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。

（1）Max z=2x 1+x 2St.⎪⎩⎪⎨⎧≥≤+≤+0,24261553212121x x x x x x 解：①图解法：由作图知，目标函数等值线越往右上移动，目标函数越大，故c 点为对应的最优解，最优解为直线⎩⎨⎧=+=+242615532121x x x x 的交点，解之得X=(15/4,3/4)T 。

Max z =33/4. ② 单纯形法：将上述问题化成标准形式有： Max z=2x 1+x 2+0x 3+0x 4St. ⎪⎩⎪⎨⎧≥≤++≤++0,,,242615535421421321x x x x x x x x x x其约束条件系数矩阵增广矩阵为：P 1 P 2 P 3 P 4⎥⎦⎤⎢⎣⎡241026150153 P 3,P 4为单位矩阵，构成一个基，对应变量向，x 3,x 4为基变量，令非基变量x 1,x 2为零，找到T 优解，代入目标函数得Max z=33/4.1.7 分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题，并指出属哪一类。

（3）Min z=4x 1+x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 解：这种情况化为标准形式： Max z ＇=-4x 1-x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 添加人工变量y1,y2Max z ＇=-4x 1-x 2+0x 3+0x 4-My 1-My 2⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x(2) 两阶段法： Min ω=y 1+y 2St.⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x第二阶段，将表中y 1,y 2去掉，目标函数回归到Max z ＇=-4x 1-x 2+0x 3+0x 4第二章 线性规划的对偶理论与灵敏度分析（作业）2.7给出线性规划问题：Max z=2x 1+4x 2+x 3+x 4⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤++≤++≤+≤++)4,3,2,1(096628332143221421j x x x x x x x x x x x x j要求：（1）写出其对偶问题；（2）已知原问题最优解为X *=(2,2,4,0),试根据对偶理论，直接求出对偶问题的最优解。

《运筹学》习题与答案（解答仅供参考）一、名词解释1. 线性规划：线性规划是运筹学的一个重要分支，它主要研究在一系列线性约束条件下，如何使某个线性目标函数达到最大值或最小值的问题。

2. 动态规划：动态规划是一种解决多阶段决策问题的优化方法，通过把原问题分解为相互联系的子问题来求解，对每一个子问题只解一次，并将其结果保存起来以备后续使用，避免了重复计算。

3. 整数规划：整数规划是在线性规划的基础上，要求决策变量取值为整数的一种优化模型，用于解决实际问题中决策变量只能取整数值的情形。

4. 马尔可夫决策过程：马尔可夫决策过程是一种随机环境下的决策模型，其中系统的状态转移具有无后效性（即下一状态的概率分布仅与当前状态有关），通过对每个状态采取不同的策略（行动）以最大化期望收益。

5. 最小费用流问题：最小费用流问题是指在网络流模型中，每条边都有一个容量限制和单位流量的成本，寻找满足所有节点流量平衡的同时使得总成本最小的流方案。

二、填空题1. 运筹学的主要研究对象是系统最优化问题，其核心在于寻求在各种（约束条件）下实现（目标函数）最优的方法。

2. 在运输问题中，供需平衡指的是每个（供应地）的供应量之和等于每个（需求地）的需求量之和。

3. 博弈论中的纳什均衡是指在一个博弈过程中，对于各个参与者来说，当其他所有人都不改变策略时，没有人有动机改变自己的策略，此时的策略组合构成了一个（纳什均衡）。

4. 在网络计划技术中，关键路径是指从开始节点到结束节点的所有路径中，具有最长（总工期）的路径。

5. 对于一个非负矩阵A，如果存在一个非负矩阵B，使得AB=BA=A，则称A为（幂等矩阵）。

三、单项选择题1. 下列哪项不是线性规划的标准形式所具备的特点？（D）A. 目标函数是线性的B. 约束条件是线性的C. 决策变量非负D. 变量系数可以为复数2. 当线性规划问题的一个基解满足所有非基变量的检验数都非正时，那么该基解（C）。

A. 不是可行解B. 是唯一最优解C. 是局部最优解D. 不一定是可行解3. 下列哪种情况适合用动态规划法求解？（B）A. 问题无重叠子问题B. 问题具有最优子结构C. 问题不能分解为多个独立子问题D. 子问题之间不存在关联性4. 在运输问题中，如果某条路线的运输量已经达到了其最大运输能力，我们称这条路线处于（A）状态。

《运筹学》试题及答案19、简述线性规划模型主要参数（p11）（1）、价值系数：目标函数中决策变量前的系数为价值系数（2）、技术系数：约束条件中决策变量前的系数（3）、约束条件右边常数项15、简述线性规划解几种可能的结果（情形）（ppt第二章39或89页）（1）.有唯一最优解 (单纯形法中在求最大目标函数的问题时，对于某个基本可行解，所有δj≤0)（2）.无可行解，即可行域为空域，不存在满足约束条件的解，也就不存在最优解了。

（3）.无界解，即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小，一般来说，这说明模型有错，忽略了一些必要的约束条件（4）.无穷多个最优解，则线段上的所有点都代表了最优解（5）退化问题，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，用图解法无退化解1、简述单纯形法的基本思路（p70）从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。

直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。

17、简述线性规划中添加人工变量的前提（p85）在系数矩阵中直接找不到初始可行解，进而通过添加人工变量的方法来构造初始可行基，得出初始基本可行解10、简述线性规划对偶问题的基本性质（p122）（1）对称性（2）弱对偶性（3）强对偶性（4）最优性（5）互补松弛型原函数与对偶问题的关系1）求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。

而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。

2）原问题的目标函数中的价值系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个价值系数就等于对偶问题中的第i个约束条件的右边常数项。

3）原问题的约束条件的右边常数项为对偶问题的目标函数中价值系数。

习 题 11 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。

⎪⎩⎪⎨⎧≥≥+≥++=0x x 42x 4x 66x 4x 3x 2x minz )a (21212121， ⎪⎩⎪⎨⎧≥≥+≤++=0x ,x 124x 3x 2x 2x 2x 3x maxz )b (21212121⎪⎩⎪⎨⎧≤≤≤≤≤++=8x 310x 512010x 6x x x maxz )c (212121 ⎪⎩⎪⎨⎧≥≤+-≥-+=0x ,x 23x 2x 2x 2x 6x 5x maxz )d (21212121 答案： (a)唯一解3*,)5.0,75.0(*==z X T); (b)无可行解;(c)唯一解16*,)6,10(*==z X T); (d)无界解）2 用单纯形法求解下列线性规划问题。

⎪⎩⎪⎨⎧≥≤+≤++=0x ,x 82x 5x 94x 3x 5x 10x maxz )a (21212121 ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+=0x ,x 5x x 242x 6x 155x x 2x maxz )b (212121221 答案： (a)唯一解5.17*,)5.1,1(*==z X T )，对偶问题5.17*,)786.1,357.0(*==w Y T ; (b)唯一解5.8*,)5.1,5.3(*==z X T ），5.8*,)5.0,25.0,0(*==w Y T3 用大M 法和两阶段法求解下列线性规划问题，并指出属于哪一类解。

⎪⎪⎩⎪⎪⎨⎧≥≥-≥+-≥+++-=0x x x 0x 2x 2x 2x 6x x x 2x x 2x maxz )a (3,2,13231321321 ⎪⎩⎪⎨⎧≥≥+≥++++=0x ,x ,x 62x 3x 82x 4x xx 3x 2x minz )b (32121321321 答案：(a)无界解；(b)唯一解8*,)0,8.1,8.0(*==z X T)，对偶问题8*,)0,1(*==w Y T4已知线性规划问题的初始单纯形表（如表1-54所示）和用单纯形法迭代后得到的表（如表1-55所示）如下，试求括弧中未知数a ～l 的值。

max (min)
Z = CX
AX ≤ ( = , ≥ ) b X ≥ 0
3、线性规划的标准形式 、
ma0
4、线性规划问题的解 、 （一）求解方法
一 般 有 两种方法 图 解 法 单纯形法 两个变量、 两个变量、直角坐标 三个变量、 三个变量、立体坐标
适用于任意多个变量、 适用于任意多个变量、但需将 一般形式变成标准形式
（二）线性规划问题的解
1、解的概念 可行解：满足约束条件② 的解为可行解。 ⑴ 可行解：满足约束条件②、③的解为可行解。 所有解的集合为可行解的集或可行域。 所有解的集合为可行解的集或可行域。 最优解： 达到最大值的可行解。 ⑵ 最优解：使目标函数①达到最大值的可行解。 ⑶ 基：B是矩阵A中m×m阶非奇异子矩阵 是矩阵A ≠0）， ），则 是一个基。 （∣B∣≠0），则B是一个基。
§2 图 解 法
例一、 例一、 max
Z = 2 x 2 x 2 x 4 x
2 2 1
+ 3 x
2
2 x1 + x + 1 4 x1 x1 ≥
≤ 12 ≤ 8 ≤ 16 ≤ 12
2
⑴ ⑵ ⑶ ⑷
2
0, x
≥ 0
max
Z = 2 x1 + 3 x 2 x 2 x
2 2
当xj=0时, 必有 j=zj=0, 因此 时 必有y
∑P x = ∑P y = ∑P z
j =1
r
r
r
r
j
j
j =1
j
j
j =1
j
j
=b
∑(y
j =1
j
− z j ) Pj = 0

1 3 P3 2 0 1 0 P5 2 1 2 1 P4 3 0 3 0 P5 0 1 1
(2) M inf x1 5 x2 2 x3
3x1 2 x 2 4 x3 6 2 x 3 x x 5 1 2 3 s.t : x1 x 2 x3 9 x1 0, x 2 0
令 z f , 则Maxz x1 5 x 2 2 x3
2 3
X2
2 1 0
X2
1 2 A
3 4 B
D
x1
5 B 4 3 2 1 0 1 2 3
C A Z
*
T z * 13
4 5 6 x1
4
(3)Max z= x1+ 2x2 s.t: 2x1- x2≤6 (A) 3x1+ 2x2≤12 (B) x1 ≤3 (C) x1，x2≥0 从图中可知，最优解为 0
T
T
同时为基本可行解， z 2 3 同时为基本可行解， z 1
对应 B6的基本解为0 1 0 对应 B7的基本解为0 对应 B8的基本解为0 对应 B9的基本解为0 对应 B10的基本解为0 ∴最优解为 x 14 3
5
B9 P3
共 10 个基
2 0 P5 1 1
B10 P4
1 0 P5 0 1
x1 20 3 x1 x 2 6 对应B1的基本解为：令x 3 x 4 x5 0得 2 x1 4 x 2 4 x 2 3
15 x1
1 1 2 1 0 A P1 1 4 1 0 1 B1 P1 B3 P1 B5 P2 B7 P2 1 1 P2 1 4 1 1 P4 1 0 1 2 P3 4 1 1 0 P5 4 1

X(2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根
显然用料最少的方案最优。
1.4A、B两种产品，都需要经过前后两道工序加工，每一个单位产品A需要前道工序1小时和后道工序2小时，每一个单位产品B需要前道工序2小时和后道工序3小时．可供利用的前道工序有11小时，后道工序有17小时．
3
B1：2.0
3
需要量（套）
200
150
问怎样下料使得（1）用料最少；（2）余料最少．
【解】第一步：求下料方案，见下表。
方案
一
二
三
四
五
六
七
八
九
十
十一
十二
十三
十四
需要量
B1:2.7m
2
1
1
1
0
0
0
0
0
0
0
0
0
0
300
B2:2m
0
1
0
0
3
2
2
1
1
1
0
0
0
0
450
A1:1.7m
0
0
1
0
0
1
0
2
1
0
3
2
1
0
《运筹学》
第1章线性规划
第2章线性规划的对偶理论
第3章整数规划
第4章目标规划
第5章运输与指派问题
第6章网络模型
第7章网络计划
第8章动态规划
第9章排队论
第10章存储论
第11章决策论
第12章对策论
习题一
1.1讨论下列问题：