第一章线性规划 1．1将下述线性规划问题化成标准形式 1)min z＝－3x1＋4x2－2x3＋5 x4 －x2＋2x3－x4＝－2 4x st. x1＋x2－x3＋2 x4 ≤14 －2x1＋3x2＋x3－x4 ≥ 2 x1，x2，x3≥0，x4无约束 2)min z ＝2x1－2x2＋3x3 ＋x2＋x3＝4 －x st. －2x1＋x2－x3≤6 x1≤0 ，x2≥0，x3无约束 1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。 1)min z＝2x1＋3x2 4x1＋6x2≥6 st2x1＋2x2≥4 x1，x2≥0 2)max z＝3x1＋2x2 2x1＋x2≤2 st3x1＋4x2≥12 x1，x2≥0 3)max z＝3x1＋5x2 6x1＋10x2≤120 st5≤x1≤10 3≤x2≤8 4)max z＝5x1＋6x2 2x1－x2≥2 st－2x1＋3x2≤2 x1，x2≥0 1．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解 （1）min z＝5x1－2x2＋3x3＋2x4 x1＋2x2＋3x3＋4x4＝7 st2x1＋2x2＋x3 ＋2x4＝3 x1，x2，x3，x4≥0
1．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。 1) maxz ＝10x 1＋5x 2 3x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥0 2) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥0 1．5 分别用大M 法与两阶段法求解下列LP 问题。 1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥0 2) max z ＝4x 1＋5x 2＋ x 3 . 3x 1＋2x 2＋ x 3≥18 St. 2x 1＋ x 2 ≤4 x 1＋ x 2－ x 3＝5 3) maxz ＝ 5x 1＋3x 2 +6x 3 x 1＋2x 2 －x 3 ≤ 18 st 2x 1＋x 2 －3 x 3 ≤ 16 x 1＋x 2 －x 3＝10 x 1，x 2 ，x 3≥0 123123 123123123 4)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤??-++≤?? ++ ≥??≥? 1．6
《运筹学》线性规划部分练习题 一、思考题 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． 某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：
线性规划及单纯形法 一．选择 1. 运筹学应用分析、试验、（C ）的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 A 统筹 B 量化 C 优化 D 决策 2. 运筹学研究的基本手段是（A ）。 A 建立数学模型 B 进行数学分析 C 进行决策分析 D 建立管理规范 3. 运筹学研究的基本特点是（ C ）。 A 进行系统局部独立分析 B 考虑系统局部优化 C 考虑系统的整体优化 D 进行系统的整体决策 4. 线性规划问题的数学模型包含三个组成要素：决策变量、目标函数、（B ） A 表达式 B 约束条件 C 方程变量 D 价值系数 5. 线性规划问题的基可行解X 对应线性规划问题可行域（凸集）的（ C ） A 边 B 平面 C 顶点 D 内部 6. 目标函数取极小化（Z min ）的线性规划问题可以转化为目标函数取极大化即（C ）的线性规划问题求解 A Z min B )min(Z - C )max(Z - D Z max - 7. 标准形式的线性规划问题，最优解（C ）是可行解 A 一定 B 一定不 C 不一定 D 无法确定 8. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（ C ）。 A 最优解 B 基可行解 C 可行解 D 基解 9. 生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的（D ） A 管理问题 B 规划问题 C 决策问题 D 优化问题 10. 在线性规划问题中，图解法适合用于处理变量（ B ）个的线性规划问题 A 1 B 2 C 3 D 4 11. 求解线性规划问题时，解的情况有:唯一最优解、无穷多最优解、（ C ）、无可行解 A 无解B 无基解 C 无界解 D 无基可行解 12. 在用图解法求解的时，找不到满足约束条件的公共范围，这时问题有（D ），其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正。 A 唯一最优解 B 无穷多最优解 C 无界解D 无可行解 13. 线性规划问题的基可行解()T n X X X ,,1 =为基可行解的充要条件是X 的正分量所对 应的系数列向量是（B ） A 线性相关 B 线性独立 C 非线性独立 D 无法判断 14. 线性规划问题进行最优性检验和解的判别时，如果当0≤j σ时，人工变量仍留在基本量中且不为零，（D ） A 唯一最优解 B 无穷多最优解 C 无界解 D 无可行解 15.如果集合C 中任意两个点21,X X 其连线上的所有点也都是集合C 中的点，称C 为（B ）
实验报告 课程名称：运筹学导论 实验名称：线性规划问题实例分析专业名称：信息管理与信息系统 指导教师：刘珊 团队成员：邓欣(20112111 蒋青青(20114298 吴婷婷(20112124 邱子群(20112102 熊游(20112110 余文媛(20112125 日期：2013-10-25 成绩：___________
1．案例描述 南部联盟农场是由以色列三个农场组成的联合组织。该组织做出了一个关于农场农作物的种植计划，如下： 每一个农场的农业产出受限于两个量，即可使用的灌溉土地量和用于灌溉的水量。数据见下表： 适合本地区种植的农作物包括糖用甜菜、棉花和高粱。这三种作物的差异在于它们每亩的期望净收益和水的消耗量不同。另外农业部门已经制定了南部联盟农场作物总亩数的最大配额，见下表： 作物的任何组合可以在任何农场种植，技术部门的任务是找出一个种植方案使南部联盟农场的净收益最大化。 2.建立模型 决策变量为Xi(i=1,2,……,9,表示每个农场每种作物的种植量。 MAX Z=1000(X1+X2+X3+750(X4+X5+X6+250(X7+X8+X9 约束条件： （1）每一个农场使用的土地 X1+X4+X7≤400
X2+X5+X8≤600 X3+X6+X9≤300 (2每一个农场的水量分布 3X1+2X4+X7≤600 3X2+2X5+X8≤800 3X3+2X6+X9≤375 (3每一种作物的总种植量 X1+X2+X3≤600 X4+X5+X6≤500 X7+X8+X9≤325 非负约束Xi≥0 , i=1,2, (9) 3.计算机求解过程 步骤1.生成表格 步骤2.输入数据
第二章 线性规划 主要内容：1、线性规划问题及数学模型 2、线性规划问题的解及其性质 3、图解法 4、单纯形法 5、大M 法和两阶段法 重点与难点：线性规划数学模型的建立：一般形成转化为标准型的方法：单纯形法的求解步骤。 要 求：理解本章内容，掌握本章重点与难点问题；深刻理解线性规划问题的基本概念、基本性质，熟练掌握 其求解技巧；培养解决实际问题的能力。 §1 线性规划的数学模型及解的性质 一、数学模型（一般形式） 例 1 已知某市有三种不同体系的建筑应予修建，其耗用资源数量及可用的资源限量如下表，问不同体系的面积应各建多少，才能使提供的住宅面积总数达到最大？ 解：设三种体系的建筑面积依次为1x ,2x ,3x 万平方米， 则目标函数为 321max x x x z ++= 约束条件为 ?? ?? ???????=≥≤++≤≤++≤++≤++3,2,10 4005.335.41470021015000 180190110200025301211000 122137105 3211321321321j x x x x x x x x x x x x x x j 例2 某工厂要安排生产甲、乙两种产品。已知：
问：如何安排两种产品的生产数量，才能使总产值最高？ 解：设 21,x x 分别为甲、乙两种产品的生产量： 则目标函数为 21127m ax x x z += 约束条件为??? ??? ?=≥≤+≤+≤+2,1,03001032005436049112121j x x x x x x x j 从以上两例可以看出，它们都属于一类优化问题。它们的共同特征： ①每一个问题都有一组决策变量（n x x x 21,）表示某一方案；这组决策变量的值就代表一个具体方案。一般这 些变量的取值是非负的。 ②存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示。 ③都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示；按问题的不同，要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为： 目标函数 n n x c x c x c z +++= 2211m ax (m in) 约束条件 ()()()????? ????=≥=≥≤+++=≥≤+++=≥≤+++n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n ,,2,1,0,,,22112222212111212111 可行解：满足约束条件的一组决策变量，称为可行解。 最优解：使目标函数取得最大（小）值的可行解，称为最优解。 最优值：目标函数的最大（小）值，称为最优值。 二、标准型 （一）问题的标准形式： n n x c x c x c z +++= 2211ma x ????? ?? ??=≥=+++=+++=+++n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n ,,2,1,022112222212111212111
第一章线性规划 习题1.1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？ 解：设x1、x2分别代表甲、乙两种产品的生产数量（件），z表示公司总利润。依题意，问题可转换成求变量x1、x2的值，使总利润最大，即 ma x z=50x1+100x2 且称z=50x1+100x2为目标函数。 同时满足甲、乙两种产品所消耗的A、B、C三种资源的数量不能超过它们的限量，即可分别表示为 x1 + x2≤300 2x1 + x2≤400 x2≤250 且称上述三式为约束条件。此外，一般实际问题都要满足非负条件，即x1≥0、x2≥0。 这样有 ma x z=50x1+100x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x1、x2≥0
习题1.2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m 3，在两个工厂之间有一条流量为200万m 3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m 3和1.4万m 3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m 3和800元/万m 3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。 解：设x 1、x 2分别代表工厂1和工厂2处理污水的数量(万m 3)。则问题的目标可描述为 min z =1000x 1+800x 2 约束条件有 第一段河流（工厂1——工厂2之间）环保要求 (2－x 1)/500 ≤0.2% 第二段河流（工厂2以下河段）环保要求 [0.8(2－x 1) +(1.4－x 2)]/700≤0.2% 此外有 x 1≤2； x 2≤1.4 化简得到 min z =1000x 1+800x 2 x 1 ≥1 0.8x 1 + x 2 ≥1.6 x 1 ≤2 x 2≤1.4 x 1、x 2≥0 习题1.3 ma x z =50x 1+100x 2 x 1 + x 2≤300 2x 1 + x 2≤400 x 2≤250 图1—1 x 2
《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ??? ??≥=++=+++++=?? ? ??≥≤+≤++=0,,,24 261553).(002max ,,0,24 261553).(2max 14.1843214213 214 321432121212 1x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【为初始基变量，选择43,x x )1000(00)0010(01 )2050(12)6030(24321=?+?-==?+?-==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择41x x
3 /1)6/122/10(00 )0210(03 /1)3/1240(10)1200(24321-=?+-?-==?+?- ==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择32x x 24 /724/528/11012/112/124/1100 021110120124321-=?+-?-=-=-?+?-==?+?-==?+?-=）（）（）（）（σσσσ 433 4341522max ,)4 3,415( ),(2112= +?=+===x x z x x X T T 故有：所以，最优解为
??? ??? ?≥=+ +=+=+ ++++=?????? ?≥≤+≤≤+=0,,,,18232424).(0002max ,,,0 ,182312212 ).(52max 24.185432152142315 43215432121212 1x x x x x x x x x x x x t s x x x x x z x x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【 )000010(00001000000000100520200052300010254321=?+?+?-==?+?+?-==?+?+?-==?+?+?-==?+?+?-=σσσσσ）（）（）（）（ 为出基变量。为进基变量，所以选择42x x
运筹学部分课后习题解答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）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21 j x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321 j x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。
习题一1.1 用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、 无穷多最优解、无界解或无可行解。 (1) min z ＝6x1＋4x2(2) max z ＝4x1＋8x2 st. 2x1＋x2≥1 st. 2x1＋2x2≤10 3x1＋4x2≥1.5 －x1＋x2≥8 x1, x2≥0 x1, x2≥0 (3) max z ＝x1＋x2(4) max z ＝3x1－2x2 st. 8x1＋6x2≥24 st. x1＋x2≤1 4x1＋6x2≥－12 2x1＋2x2≥4 2x2≥4 x1, x2≥0 x1, x2≥0 (5) max z ＝3x1＋9x2(6) max z ＝3x1＋4x2 st. x1＋3x2≤22 st. －x1＋2x2≤8 －x1＋x2≤4 x1＋2x2≤12 x2≤6 2x1＋x2≤16 2x1－5x2≤0 x1, x2≥0 x1, x2≥0 1.2. 在下列线性规划问题中，找出所有基本解，指出哪些是基本可行解并分别代入目标函数，比较找出最优解。 (1) max z ＝3x1＋5x2(2) min z ＝4x1＋12x2＋18x3 st. x1＋x3＝4 st. x1＋3x3－x4＝3 2x2＋x4＝12 2x2＋2x3－x5＝5 3x1＋2x2＋x5＝18 x j≥0 （j＝1, (5) x j≥0 （j＝1, (5) 1.3. 分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。 (1) max z ＝10x1＋5x2 st. 3x1＋4x2≤9 5x1＋2x2≤8 x1, x2≥0 (2) max z ＝100x1＋200x2 st. x1＋x2≤500 x1≤200 2x1＋6x2≤1200 x1, x2≥0 1.4. 分别用大M法和两阶段法求解下列线性规划问题，并指出问题的解属于哪一类： ９
运筹学 线性规划基本性质
线形规划基本性质目录 线性规划（概论） 线性规划问题:生产计划问题 例1.1 生产计划问题（资源利用问题）例1.1生产计划问题分析 例1.1生产计划问题模型 例1.1生产计划问题表格描述 例1 .2 营养配餐问题 各种食物的营养成分表 各种食物的营养成分表（转置） 例1 .2 营养配餐问题求解 用于成功决策的实例 线形规划的一般模型:特点 线形规划的一般模型:数学模型线性规划问题隐含的假定 比例性假定 可加性假定 连续性假定 确定性假定 线形规划的图解法 线形规划解的可能结果 线形规划的标准形式1 线形规划的标准形式2 非标准型LP的标准化:目标函数 非标准型LP的标准化:约束函数1 非标准型LP的标准化:约束函数2 非标准型LP的标准化:决策变量 线形规划解的概念：可行解 线形规划解的概念：最优解 线形规划解的概念：基本解 线形规划解的概念：最优基本解 线形规划的应用模型 生产计划问题 生产计划问题：表格分析 生产计划问题：模型 产品配套问题 产品配套问题：工时分析 产品配套问题：配套分析 产品配套问题：模型 结束放映
线性规划（概论） 线形规划是研究解决有限资源最佳分配的运筹学方法，即如何对有限的资源做出最佳方式的调配和最有利的利用，以便最充分地发挥资源的效能去获得最佳经济效益。
线性规划问题:生产计划问题 1、如何合理使用有限的人力、物力和资 金，实现最好的经济效益。 2、如何合理使用有限的人力、物力和资 金，以达到最经济的方式，完成生产 计划的要求。
例1.1 生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/张，椅子销售价格30元/把，生产桌子和椅子要求需要木工和油漆工两种工种。生产一张桌子需要木工4小时，油漆工2小时。生产一把椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？
线性规划模型在实际生活中的应用 【摘要】线性规划在实际生活中扮演着很重要的角色，研究对象是计划管理工作中有关安排和估值的问题,其广泛应用于经济等领域，是实际生活中进行管理决策的最有效的方法之一。解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案。本文通过对例题利用线性规划分析，如何合理的分配利用，最终找到最优解使企业利润最大，说明了线性规划在实际生活中的应用，而且对线性规划问题模型的建立，模型的解进行了分析，运用图解法和单纯形法解决问题。 【关键词】线性规划、建模、实际生活、图解法、单纯形法 前言：线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 在实际生活中，经常会遇到一定的人力、物力、财力等资源条件下，如何精打细算巧安排，用最少的资源取得最大的效益的问题，而这正是线性规划研究的基本内容，它在实际生活中有着非常广泛的应用．任何一个组织的管理者都必须对如何向不同的活动分配资源的问题做出决策，即如何有效地利用人力、物力完成更多的任务，或在预定的任务目标下如何耗用最少的人力、物力去实现目标。在许多情况下，大量不同的资源必须同时进行分配，需要这些资源的活动可以是不同的生产活动，营销活动，金融活动或者其他一些活动。随着计算技术的不断发展，使成千上万个约束条件和决策变量的线性规划问题能迅速地求解，更为线性规划在经济等各领域的广泛应用创造了极其有利的条件。线性规划已经成为现代化管理的一种重要的手段。本文运用常用的图解法和单纯形法解决利润最大化决
运筹学习题答案 第一章（39页） 1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max 12z x x =+ 51x +102x ≤50 1x +2x ≥1 2x ≤4 1x ，2x ≥0 （2）min z=1x +1.52x 1x +32x ≥3 1x +2x ≥2 1x ，2x ≥0 （3）max z=21x +22x 1x -2x ≥-1 -0.51x +2x ≤2 1x ，2x ≥0 （4）max z=1x +2x 1x -2x ≥0 31x -2x ≤-3 1x ，2x ≥0 解： （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解 1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。
（1）min z=-31x +42x -23x +54x 41x -2x +23x -4x =-2 1x +2x +33x -4x ≤14 -21x +32x -3x +24x ≥2 1x ，2x ，3x ≥0，4x 无约束 （2）max k k z s p = 11 n m k ik ik i k z a x ===∑∑ 1 1(1,...,)m ik k x i n =-=-=∑ ik x ≥0 (i=1…n; k=1,…,m) （1）解：设z=-z ',4x =5x -6x , 5x ,6x ≥0 标准型： Max z '=31x -42x +23x -5(5x -6x )+07x +08x -M 9x -M 10x s. t . -41x +2x -23x +5x -6x +10x =2 1x +2x +33x -5x +6x +7x =14 -21x +32x -3x +25x -26x -8x +9x =2 1x ,2x ,3x ,5x ,6x ,7x ,8x ,9x ,10x ≥0
一、需要掌握的主要内容 1、单纯形法的计算过程 （1）确定初始基本可行解 （2）最优性检验； （3）基变换。 2、单纯形法的灵敏度分析 （1）最终单纯形表中，变量系数的灵敏度分析针对最优解不变时，判断其变化范围； （2）约束条件常数项b的灵敏度分析针对最优解不变时，判断其变化范围； （3）增加一个变量的灵敏度分析 首先，确定增加变量在初始单纯形表中的系数列P j ；然后，求出其对应在最终单纯形表 中的系数列P j ；最后求出σ j =C j -C B B-1P j 。 若σ j ≤0，则最优解不变；σ j ≥0，则继续进行基变换，直到求出最优解。 二、需要基本掌握的内容 1、解、基本解、可行解、基本可行解等基本概念； 2、利用单纯形法求解如何判断无可行解、无界解和无穷最优解等基本理论； 3、如何写出一个线性规划的对偶问题； 4、对偶单纯形法的基本思路和过程。 一、填空题 （1）线性规划模型中，松弛变量的经济意义是，它在目标函数中的系数是。 （2）设有线性规划问题：max z=CX AX≤b X≥0 有一可行基B，记相应基变量为X B ,非基变量为X N ，则可行解的定义为，基本可行 解的定义为，B为最优基的条件是。 （3）线性规划模型具有可行域，若其有最优解，必能在上获得。 二、选择题 1．线性规划一般模型中，自由变量可以用两个非负变量的（）代换。 A．和 B．差 C．积 D．商 2．满足线性规划问题全部约束条件的解称为（） A．最优解 B．基本解 C．可行解 D．多重解 3．当满足最优检验，且检验数为零的变量的个数大于基变量的个数时，可求得（） A．多重解 B．无解 C．无界解 D．退化解 4．原问题与对偶问题的（）相同。 A．最优解 B．最优目标值 C.解结构 D．解的分量个数 5.记线性规划原问题（p）max z=CX，对偶问题（D） min w=Yb AX≤b YA≥C
1 人力资源分配的问题 例1.某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段开始时上班，并连续工作八小时，问该公交线路怎样安排 司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员? 分析：不同上班班次时段的司机和乘务人员数 （图见书） 解：设 xi 表示第i 班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 ?? ? ??? ???? ? =≥≥+≥+≥+≥+≥+≥++++++=6,,2,1030205060 7060.6554433221616 54321 j x x x x x x x x x x x x x t s x x x x x x minZ j 且为整数 例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？
解：设xi ( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 （图见书） ?? ? ??? ? ? ???? ?=≥≥++++≥++++≥++++≥++++≥++++≥++++≥++++++++++=7,6,,2,1028311925241528.432173217621765176547654365432543217654321 j 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 x x x x x x x t s x x x x x x x minZ j 且为整数 约束条件：目标函数： 2 生产计划的问题 例3.某企业生产甲、乙、丙三种产品，每一产品均须经过A 、B 两道工序。A 工序有两种设备可完成，B 工序有三种设备可完成，除甲产品和乙产品的A 工序可随意安排外，其余只能在要求的设备上完成。加工单位产品所需工序时间及其他各项数据的费用有关资料见下表。试制订利润最大的产品加工方案。 （图见书） 解：用8个单下标变量分别表示3种产品在相应工序中的生产量，如表所示。 在约束条件中需考虑 x1+x2=x3+x4+x5 线性规划模型的目标函数为： max z=[(1.25-0.25)(x1+x2)+(2-0.35)(x6+x7)+(2.8-0.5)x8] - [0.05(5x1+10x6)+0.0321(7x2+9x7+12x8)+0.0625(6x3+8x6+8x7)+0.111857(4x4+11x8)+0.05×7x5] 即:max z=0.75x1+0.7753x2+0.65x6+0.8611x7+0.6844x8-0.375x3-0.4474x4-0.35x5 该问题线性规划模型为： max z= 0.75x1+0.7753x2+0.65x6+0.8611x7+0.6844x8-0.375x3-0.4474x4-0.35x5 ? ????? ??? ??=≥=---+≤≤+≤++≤++≤+8 ,,2,1004000770001144000886100012976000105..543215 8476387261 j x x x x x x x x x x x x x x x x x t s j 3 套裁下料问题 例4.现要做100套钢架，每套用长为2.9m,2.1m 和1.5m 的圆钢各一根。已知原料长7.4m ，问应如何下料使所用料最省？ 若用套裁，下面有几种套裁方案，都可以考虑采用
第五章线性规划在管理中的应用 某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。管理层考虑将这些剩余生产力用于新产品Ⅰ、Ⅱ、Ⅲ的生产。可用的机器设备是限制新产品产量的主要因素，具体数据如下表： 司的利润最大化。 1、判别问题的线性规划数学模型类型。 2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。 3、建立该问题的线性规划数学模型。 4、用线性规划求解模型进行求解。 5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。 6、若销售部门表示，新产品Ⅰ、Ⅱ生产多少就能销售多少，而产品Ⅲ最少销售18件，请重新完成本题的1-5。 解： 1、本问题是资源分配型的线性规划数学模型。 2、该问题的决策目标是公司总的利润最大化，总利润为： + + 决策的限制条件： 8x1+ 4x2+ 6x3≤500 铣床限制条件 4x1+ 3x2≤350 车床限制条件 3x1 + x3≤150 磨床限制条件 即总绩效测试（目标函数）为： max z= + + 3、本问题的线性规划数学模型 max z= + + S．T． 8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1 + x3≤150 x1≥0、x2≥0、x3≥0 4、用Excel线性规划求解模板求解结果：最优解（50，25，0），最优值：30元。 5、灵敏度分析
目标函数最优值为 : 30 变量最优解相差值 x1 50 0 x2 25 0 x3 0 .083 约束松弛/剩余变量对偶价格 1 0 .05 2 75 0 3 0 .033 目标函数系数范围 : 变量下限当前值上限 x1 .4 .5 无上限 x2 .1 .2 .25 x3 无下限 .25 .333 常数项数范围 : 约束下限当前值上限 1 400 500 600 2 275 350 无上限 3 150 （1）最优生产方案： 新产品Ⅰ生产50件、新产品Ⅱ生产25件、新产品Ⅲ不安排。最大利润值为30元。 （2）x3 的相差值是意味着，目前新产品Ⅲ不安排生产，是因为新产品Ⅲ的利润太低，若要使新产品Ⅲ值得生产，需要将当前新产品Ⅲ利润元/件，提高到元/件。 （3）三个约束的松弛/剩余变量0，75，0，表明铣床和磨床的可用工时已经用完，而车床的可用工时还剩余75个工时； 三个对偶价格，0，表明三种机床每增加一个工时可使公司增加的总利润额。 （4）目标函数系数范围 表明新产品Ⅰ的利润在元/件以上，新产品Ⅱ的利润在到之间，新产品Ⅲ的利润在以下，上述的最佳方案不变。 （5）常数项范围 表明铣床的可用条件在400到600工时之间、车铣床的可用条件在275工时以上、磨铣床的可用条件在到工时之间。各自每增加一个工时对总利润的贡献元，0元，元不变。 6、若产品Ⅲ最少销售18件，修改后的的数学模型是： max z= + + S．T． 8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1 + x3≤150 x3≥18 x1≥0、x2≥0、x3≥0 这是一个混合型的线性规划问题。 代入求解模板得结果如下： 最优解（44，10，18），最优值：元。 灵敏度报告： 目标函数最优值为 : 变量最优解相差值 x1 44 0 x2 10 0 x3 18 0 约束松弛/剩余变量对偶价格