运筹学的理论与实践

运筹学的理论与实践我们通过系统地考察一些线性规划问题来说明这些基本步骤建立模型不仅是一门科学，更主要的是一种艺术这种艺术只有通过实践才能掌握例1多产品的生产组合问题生产炊事用具需要两种资源劳动力和原材料，某公司准备制订生产计划公司考虑生产三种不同的产品，生产管理部门提供的数据如下每天供应原材料200磅，每天可供使用的劳动力为150小时建立线性规划模型，为使总收益最大，求各种产品的日产量公式第一步，确定决策变量要求的未知变量是三个产品的日产量用代数符号表示它们XA产品A的日产量XB产品B的日产量XC产品C的日产量第二步，确定约束条件在这个问题中，约束条件是可用劳动力和原材料的限制产品A每单位需要7小时的劳动，产量为XA因此，仅产品A对劳动力的需求是7XA小时设为线性关系类似地产品B和C分别需要劳动力3XB和6XC小时总的劳动力需求为7XA3XB6XC，这不能超过150小时，于是劳动力的约束条件为7XA3XB6XC150同理，产品A需要原材料4XA磅，产品B需要4XB磅，产品C需要5XC磅，于是原材料约束条件为4XA4XB5XC200此外，我们还限制变量XA、XB、XC仅取非负值这叫做非负约束条件，是变量必须满足的条件实际上，大多数线性规划问题对决策变量都有非负限制可是，一般形式的线性规划并不限于非负数值后面，将讨论对没有符号限制的变量的处理方法第三步，确定目标函数本问题的目标是使整个销售利润最大假设存在可销售全部产品的理想市场，全部销售利润为Z4XA2XB3XC因此，这个生产组合问题的线性规划变成确定XA、XB、XC的值，使销售利润Z最大，Z4XA2XB3XC满足约束条件7XA3XB6XC1504XA4XB5XC200XA0，XB0，XC0例2操作训练问题某机床公司为机械工人举办操作训练班，每十名受训者中有一名可作为训练班的教师训练班为期一个月从以往的经验得知，在每十名受训者中，仅有七人可成功地完成训练不成功者便退学生产上需要输送经过训练的机械工人在今后三个月里，公司需要机械工人数是一月100二月150三月200公司四月份需要250名经过训练的机械工人，年初已有130名经过训练的机械工人可供使用每月的工资费用为一个受训者400美元一个经过训练的机械工人700美元机械加工或教学一个经过训练但空闲的机械工人500美元工会合同禁止解雇经过训练的机械工人建立线性规划问题，使雇佣费用和训练费用最小，并满足公司的生产需要公式一个经过训练的机械工人每月要做下列事情中的一件1生产，2教学，3空闲由于从事生产的机械工人数量是固定的，所以决策变量未知量是每月从事教学的人数和空闲人数要确定的变量是X1一月份从事教学的机械工人X2一月份空闲的机械工人X3二月份从事教学的机械工人X4二月份空闲的机械工人X5三月份从事教学的机械工人X6三月份空闲的机械工人约束条件是每月要有足够的已受过训练的机械工人从事生产下面的方程可满足这点B例如，一月份的约束条件变成100X1X2130二月份已受训的工人总数就是一月份已受训工人数与那些刚完成训练的工人数目之和一月份，这个训练班有10X1名学员，但其中仅有7X1名学员能完成学业，成为经过训练的机械工人因此，二月份的约束条件变成150X3X41307X1同理，三月份有200X5X61307X17X3由于公司四月份需要250名受训的机械工人，所以约束条件为1307X17X37X5250当然，所有变量都是非负的当从事生产的机械工人的费用为一常数时，就不必写在目标函数中了有关的费用包括训练班费用学员和教师的费用和空闲机械工人的费用因此，目标函数为MINZ40010X110X310X5700X1X3X5500X2X4X6于是这个线性规划问题变成例3广告宣传手段的选择一家广告公司想在电视、广播和杂志上做广告，其目的是尽可能多地招来顾客下面是市场调查结果这家公司希望广告费用不超过800,000美元还要求1至少要有两百万妇女收看广告；2电视广告费用不超过500,000美元；3电视广告白天至少播出三次，最佳时间至少播出两次；4通过广播和杂志做的广告要重复5到10次令X1，X2，X3，X4分别表示白天电视，最佳时间电视、广播和杂志广告的次数所得到的潜在顾客总数千人400X1900X2500X3200X4广告经费预算的约束条件为40,000X175,000X230,000X315,000X4800,000受广告影响的女顾客数的约束条件为300,000X1400,000X2200,000X3100,000X42,000,000电视广告的约束条件为由于广播和杂志广告的次数都在5到10之间，于是有下列约束5X3105X410经过化简，完整的线性规划问题如下注意前三个约束条件已被化简，所有约束系数在数量级上差别不大，这可减少计算机求解时的舍入误差例4检验问题某公司质量检验部门有1级和2级检验员各若干名每天8小时至少要检验1,800件产品1级检验员每小时检验25件，准确率达98，2级检验员每小时检验15件，准确率达951级检验员的工资是每小时4美元，2级检验员每小时3美元检验员出现一次检验差错，公司损失2美元这个公司有8名1级检验员和10名2级检验员，公司要求确定检验员的最优分配，使检验总费用最小公式令X1、X2表示检验部门中1级、2级检验员的人数由于检验人员有限，有下列约束条件X181级检验员X2102级检验员公司日检验量至少为1,800件因此有825X1815X21,800或200X1120X21,800为建立目标函数，还要考虑公司在产品检验中要承担的两笔费用，一是检验员的工资，二是因检验员工作差错需要负担的损失费用每个1级检验员的小时费用为42250025美元/小时每个2级检验员的小时费用为321500545美元/小时目标函数是使日检验费用Z最小Z85X145X240X136X2这个线性规划问题的完整公式是例5投资问题一个投资者星期一有100美元他在一周的任何时候，都可作如下投资选择第一天投资2个单位，第二天投资1个单位，第三天回收4个单位投资者要确定最优投资策略，该策略使他到星期六能拥有最多的钱公式由于不能确切知道每天何时进行各项投资和得到的收益，因此我们假设当天得到的收益可在同一天用于投资投资者每天有下列活动1继续给昨天的投资增加502开始当天新的投资3为今后的投资贮存现金注意，如果要从前一天的投资中马上得到收益，对第1项活动无选择余地，但对进行第2、第3项有充分的灵活性因此，我们每天需要考虑两个决策变量，一个表示当天发生的投资，另一个表示当天的存款数X1星期一的新投资S1星期一的存款数X2星期二的新投资S2星期二的存款数X3星期三的新投资S3星期三的存款数X4星期四的新投资S4星期四的存款数S5星期五的存款数星期五不做新投资，因为投资者不能在星期日之前得到星期五投资的收益约束条件保证了每一天都存在下列关系全部投资额继续的或新投资的存款额全部可用现金到星期六，手头的全部现金等于S52X4因此目标函数为MAXZS52X4例6生产A和B两种产品，每一种产品都需要进行两步化学反应A产品第一步反应需用2小时，第二步反应需用3小时B产品第一步反应需用3小时，第二步反应需用4小时实际可用于第一步反应的时间16小时，用于第二步反应的时间为24小时在不增加费用的情况下，生产B产品的同时产生副产品C虽然某些副产品C可出售获利，但剩余的副产品C必须销毁单位A产品卖4美元，单位B产品卖1美元单位副产品C可卖3美元，但若卖不出去，销毁费用是2美元预测表明，副产品C在5单位以上方可出售这家公司生产单位B产品可得2单位副产品C现在要求A、B和C的产量，以获得最大利润公式这个例题可以说明，如何用线性规划方法处理某些非线性的目标函数由于产品C的单位利润不同，使得目标函数呈非线性，即目标函数取决于产品C是被出售还是被销毁对于A产品和B产品，无论产量如何，单位利润总是分别为4美元和10美元，而单位产品C要么是获利3美元，要么是损失2美元如果以获利总金额和产量为座标作图，就可清楚地看到目标函数呈非线性，图21和22分别表示A产品和副产品C的生产、销售情况图22中的非线性函数为分段线性函数，它在区间0，5和5，上均是线性的我们把副产品C的产量分为两部分，一部分被销售，一部分被销毁，这样就可把目标函数表示为线性函数了这个问题的决策变量为X1A产品的产量X2B产品的产量X3副产品C的销售量X4副产品C的销毁量副产品C的产量X3X4由于每生产单位B产品就有两单位副产品C，故有X3X42X2对销售副产品C的约束条件为X35对反应1的可用时间约束条件为2X13X216对反应2则为3X14X224目标函数是使总收益最大Z4X110X23X32X4因此，这个线性规划问题变为应当指出，只有当副产品C多于5单位时，方可销毁换句话说，变量X3在没达到5单位时，变量X4不能为正目标函数中X3的利润系数是3，而X4的是2，从而自动地保证了这点例7机械加工车间有一台钻床和五台磨床，生产由部件1和部件2组成的组合件每台机床的生产能力如下页所示为使所有机床的负荷平衡，要求每天各机床的运转时间差最多不超过30分钟设五台磨床的加工任务相等设每天工作8小时，如何分配每台机床的工作时间，使组合件产量最大公式令X1部件1的日产量X2部件2的日产量4X13X2860480分钟对钻床有3X15