第二章 线性规划习题课

1、 一般讲，一个经济、管理问题满足以下条件时，一般讲，一个经济、管理问题满足以下条件时，才能建立线性规划模型才能建立线性规划模型 1. 1. 要求解问题的目标函数能用数值指标来反要求解问题的目标函数能用数值指标来反映，且为线性函数；映，且为线性函数； 2. 2. 存在着多种方案；存在着多种方案； 3. 3. 要求达到的目标是在一定约束条件下实现要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。的，这些约束条件可用线性等式或不等式来描述。一、一、建建 模模 条条 件件二、建二、建 模模 步步 骤骤 1 确定决策变量：确定决策变量：即需要我们作出决策或选择即需要我们作出

2、决策或选择的量。一般情况下，题目问什么就设什么为决策变的量。一般情况下，题目问什么就设什么为决策变量。量。 2 找出所有限定条件：找出所有限定条件：即决策变量受到的所有即决策变量受到的所有的约束；的约束； 3 写出目标函数：写出目标函数：即问题所要达到的目标，并即问题所要达到的目标，并明确是明确是max 还是还是 min。三、建三、建 模模 案案 例例 C 工序工序 产产品品 A B 销售销售 报废报废 工时限工时限制制 工序工序 1 2 3 12 工序工序 2 3 4 24 单位利润单位利润 （百元）（百元） 4 10 3 2 注：每生产单位产品注：每生产单位产品 B 可得到可得到 4 单位

3、副产品单位副产品 C，据预测，市场上产品据预测，市场上产品 C 的最大销量为的最大销量为 5 单位，若单位，若产品产品 C 销售不出去，则报废。销售不出去，则报废。 解：设总利润为解：设总利润为z，A、B产品销量为产品销量为x1、x2，产品产品C的销售量为的销售量为x3，报废量为报废量为x4，则：，则： 2 x1 + 3x2 12 3x1 + 4x2 24 4x2 +x3 + x4 = 0 x3 5 x1、x2 、x3 、x4 0max z = 4 x1 + 10 x2 + 3 x3 2 x4 例例1 某工厂生产某工厂生产A、B两种产品，有关资料如下表所示：两种产品，有关资料如下表所示：船只种

4、类船只种类船只数船只数拖拖 轮轮30A型驳船型驳船34B型驳船型驳船52航线号航线号合同货运量合同货运量12002400航线航线号号船队船队类型类型编队形式编队形式货运成本货运成本（千元队）（千元队）货运量货运量（千吨）（千吨）拖轮拖轮A型型驳船驳船B型型驳船驳船1112362521436202322472404142720 例例2 某航运局现有船只种类、数量以及计划期内各某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：条航线的货运量、货运成本如下表所示：问：应如何问：应如何编队，才能既完成合同任务，又使总货运成本为最小？编队，才能既完成合同任务，又使总货运成本为最

5、小？ 解：设解：设 xj 为第为第 j 号类型船队的队数号类型船队的队数( j = 1,2,3,4 ), z 为总货运成本为总货运成本,则：则： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 30 2x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1 + 20 x2 200 40 x3 + 20 x4 400 xj 0 j = 1,2,3,4 用单纯形法可求得：用单纯形法可求得：x1 = 8，x2 = 0 ，x3 = 7， x4 = 6 最优值：最优值：z = 954，即：四种船队类型的队数分别是，即：四种船队类型的

6、队数分别是8、0、7、6，此时可使总货运成本为最小，为，此时可使总货运成本为最小，为954千元。千元。例例3 合理利用线材问题合理利用线材问题现要做现要做100100套钢架，每套用长套钢架，每套用长2.9m2.9m，2.1m2.1m，1.5m1.5m，的圆钢各一根。已知原料长的圆钢各一根。已知原料长7.4m7.4m，问应如何下料，使用，问应如何下料，使用的原材料最省？的原材料最省？解：所有下料方案如下表：解：所有下料方案如下表： 方方案案长度长度m 2.9 2.1 1.5 合计合计 料头料头2017.30.11207.10.31116.50.91037.40.00306.31.10227.20

7、.20136.60.80046.01.41x2x3x4x5x6x7x8x 方方案案长度长度m 2.9 2.1 1.5 合计合计 料头料头2017.30.11207.10.31116.50.91037.40.00306.31.10227.20.20136.60.80046.01.41x2x3x4x5x6x7x8x876543214 . 18 . 02 . 01 . 109 . 03 . 01 . 0minxxxxxxxxz 010043203010001230201000000287654321876543218765432187654321xxxxxxxxxxxxxxxxxxxxxxxxxxx

8、xxxxx，产品名称产品名称规规 格格 要要 求求单价（元单价（元/kg）AC不少于不少于50%，P不超过不超过25%50BC不少于不少于25%，P不超过不超过50%35D不限不限25原材料名称原材料名称每天最多供应量（每天最多供应量（kg）单价（元单价（元/kg）CPH10010060652535 例例4 配料问题。配料问题。 某工厂要用三种原材料某工厂要用三种原材料C、P、H混合调配出三种混合调配出三种不同规格的产品不同规格的产品A、B、D。已知产品的规格要求，产。已知产品的规格要求，产品单价，每天供应的原材料数量及原材料单价如下表，品单价，每天供应的原材料数量及原材料单价如下表，该厂应如

9、何安排生产，使利润收入为最大？该厂应如何安排生产，使利润收入为最大？ 解：解： 原料原料产品产品 C P H 单单 价价ABD503525单单 价价 65 25 35)(25. 0AHAPACAPxxxx BHBPBCxxxDHDPDCxxxDHDPDCBHBPBCAHAPACxxxxxxxxxz1004001030152515max )(50. 0AHAPACACxxxx )(50. 0BHBPBCBPxxxx AHAPACxxx)(25. 0BHBPBCBCxxxx 100 DCBCACxxx100 CPBPAPxxx60 DHBHAHxxxHPCJDBAixij,0 321xxx 例例5

10、 连续投资问题。连续投资问题。 某部门在今后某部门在今后5年内给下列项目投资，已知：年内给下列项目投资，已知： 项目项目A，从第一年到第四年初需要投资，并于次年，从第一年到第四年初需要投资，并于次年末回收本利末回收本利115%； 项目项目B，第三年初需要投资，到第五年末回收本利，第三年初需要投资，到第五年末回收本利125%；但规定最大投资额不超过；但规定最大投资额不超过4万元；万元； 项目项目C，第二年初需要投资，到第五年末回收本利，第二年初需要投资，到第五年末回收本利140%；但规定最大投资额不超过；但规定最大投资额不超过3万元；万元； 项目项目D， 5年内每年初可购买公债，与当年末归还，年

11、内每年初可购买公债，与当年末归还，并加利息并加利息6%。 该部门现有资金该部门现有资金10万元，问他应如何确定给这些项万元，问他应如何确定给这些项目每年的投资额，使到五年末拥有资金的本利总额为最目每年的投资额，使到五年末拥有资金的本利总额为最大？大？ 年份年份项目项目123455年末年末ABCD1Ax2Ax3Ax4Ax415. 1Ax3Bx2Cx2Dx3Dx4Dx5Dx506. 1Dx1Dx106. 1Dx2315. 106. 1ADxx1215. 106. 1ADxx3415. 106. 1ADxx10325. 1Bx240. 1Cx年初拥有年初拥有 资金资金523406. 140. 125

12、. 115. 1maxDCBAxxxxz 1011 DAxx122206. 1DDCAxxxx 1233315. 106. 1ADDBAxxxxx 234415. 106. 1ADDAxxxx 34515. 106. 1ADDxxx 54321,0， jDCBAixij 43 Bx32 Cx解：解： 确定决策变量如下表：确定决策变量如下表： 例例6 某厂生产三种药物，某厂生产三种药物，这些药物可以从四种不同的这些药物可以从四种不同的原料中提取。下表给出了单原料中提取。下表给出了单位原料可提取的药物量位原料可提取的药物量 要求：生产要求：生产A种药物至少种药物至少160单位；单位；B种药物恰好种

13、药物恰好200单单位，位，C种药物不超过种药物不超过180单位，单位，且使原料总成本最小。且使原料总成本最小。解：解：1. 决策变量：设四种原料的使决策变量：设四种原料的使用量分别为：用量分别为：x1、x2 、x3 、x42. 目标函数：设总成本为目标函数：设总成本为z，则有：则有： 3. 约束条件：约束条件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 + x3 +2 x4 180 x1、x2 、x3 、x4 0 药物药物原料原料ABC单位成本单位成本(元吨元吨)甲甲1235乙乙2016丙丙1417丁丁1228min z = 5 x1

14、+ 6 x2 + 7 x3 + 8 x4线性规划研究的主要问题 实际上，上述两类问题是一个问题的两个不同实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（的方面，都是求问题的最优解（ max 或或 min ）。）。 一类是已有一定数量的资源（人力、物质、一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。使完成的任务量为最大。 另一类是当一项任务确定以后，研究如何统另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。筹安排，才能使完成任务所耗费的资源量为最少。线性规划问题求解程序设计要求型型线性规划问题的数学模线性规划问题的数学模. 1nnxcxcxcz 2211max(min)11212111)(bxaxaxann ，22222121)(bxaxaxann ，mnmnmmbxaxaxa)(2211 ，)(021无无约约束束， nxxx 法法线性规划问题的求解方线性规划问题的求解方. 2采采用用两两阶阶段段