《数学建模ch_4 数学规划模型》由会员分享，可在线阅读，更多相关《数学建模ch_4 数学规划模型（260页珍藏版）》请在金锄头文库上搜索。
1、第四章 数学规划模型,一、数学规划模型,1.模型的建立,问题1 某厂利用甲,乙,丙,丁四种设备生产A,B,C三种 产品, 相关数据如表所示. 已知这三种产品的单件利润 分别是4.5, 5, 7（百元）, 试问该厂应如何安排生产可获 得最大利润?,该问题的关键所在是确定每种产品的产量, 为此以表示三种产品的产量, 则目标为,在一个生产周期中, 每种设备所提供的工时为有限的, 故对四种设备而言还应该满足下列条件:,甲,乙,丙,丁,注意到变量 代表的是产品的产量, 故有 抽去所给问题的具体意义, 我们得到原问题的数学关系 为,非负性,用Lingo软件可以得到相应问题的解. 启动Lingo, 在窗 口
2、下中输入下列程序:,保存完之后执行Lingo菜单下的Solve命令,得到相应的解.,Variable Value Reduced CostX1 85.71429 0.000000X2 71.42857 0.000000X3 121.4286 0.000000Row Slack or Surplus Dual Price1 1592.857 1.0000002 0.000000 1.3571433 57.14286 0.0000004 0.000000 0.21428575 0.000000 0.4642857,注意到该问题的解为非整数解, 是由于在条件中, 并没 有要求变量 为整型变量. 若指
3、定变量为整型变量, 则问 题的解为:,最优解值为,问题2 某车间要制造100套钢筋架, 每套需要长为2.9 2.1 1.5 的钢筋各一根. 已知原料钢筋长度为7.4 问如何切割钢筋, 使得钢筋的利用率为最高?,分析 该问题的要点是如何切割钢筋, 使得每次切割之 后, 剩下的余料为最少?,假设在切割过程中, 我们不考虑钢筋的损耗, 并考虑如 下切割方案:,从分析中可以看出, 此问题的关键是确定每种方案下 的余料数.,设 表示第 种方案中使用的原料钢 筋数, 则余料数为,而相应的限制条件为,非负性,故原问题的数学关系式为,非负性,在Lingo下得到该问题的解为,运行后得到该问题的解为,X2 25.
4、00000 0.000000X3 0.000000 0.3666667X4 25.00000 0.000000X5 0.000000 1.283333X1 25.00000 0.000000,线性规划的模型一般可表示为,非负性,注 线性规划的目标函数还可以用min来表示, 表示 追求目标函数的最小值. 而 表示约束条件: （Subject to）.,问题3 要从甲地调出物质2000吨, 从乙地调出物质 1100吨, 分别供给 地1700吨, 地11吨, 地200吨和 100吨, 已知每吨运费如表所示, 试建立一个使运费达到 最小的调拨计划.,单位路程运费表,分析 设从第 个产地到第 个销地的运
5、输量为 运 输成本为 则问题的目标函数为,由于从第一个产地调出的物质的总和为第一个产地的产 量, 即有,同理, 有,对称地, 对销地而言, 有关系,由此得到该问题的数学模型,在Lingo下,可得问题之解:,注 该问题又称为运输问题. 运输问题的一般形式可写 成,其中 是第 个产地的产量, 是第 个销地的需求量.,在上面的关系中, 有,相应的运输问题称为产销平衡的运输问题. 若产销不平 衡, 应该如何处理?,问题4 随机规划模型,决策者要建造一座水库, 使水库的容量 在满足给定 的限制条件下达到最小, 以使其造价最小.,要求 1.在一年中的第 个季节水库应留出一定的容量以保证洪水的注入. 由于洪
6、水量是一个变数, 故假定 以较大的概率 使得,其中 为第 个季节的储水量.,2.为保证灌溉, 发电, 航运等用水供应, 水库在每个季 节应能保证一定的放水量 考虑到这仍然是一随机因 数, 要求满足满足这一条件的概率不小于 即,其中 为第 个季节的可放水量.,3.为保证水库的安全和水生放养, 水库还应有一定的 储水量 即,由此得到相应问题的数学模型为:,问题5 某公司准备派 个工人 去完成 项工作 已知第 个工人完成第 工作的效 率为 求如此的一个指派方案, 使工人完成这些工作 的效率为最大.,该问题可用一个网络图 来表示: 其中 表 示顶点集, 是边集, 是权集. 该问题即是从 的每一个顶点,
7、 找出唯一的一条到 的某一个 的边, 使得权之和为最大.,模型建立,若以 表示在顶点 存在边, 否则 则目标函数可表示为,而从 的每一个顶点 只能作一条边等价于,同样, 连 惟一的一条边等价于,由此得到相应的数学模型为,这样的规划又称为0-1规划.,注1 很多实际问题都可以转化成这样的模型. 例如游泳 接力队员的选拔.,注2 当人数和工作数不相同时, 这样的问题应该如何求 解, 又当 时, 并且容许一个人能完成两件工作, 又该如何解决?,二、模型的求解,例1 一奶制品加工厂用牛奶生产 两种奶制品, 1桶牛奶可以在设备甲上用12小时加工生产3公斤 或 则在设备乙上用8小时加工成4公斤 根据市场需
8、要, 生产的 全部能售出, 且每公斤 获利24元, 每公 斤 可获利16元. 现在加工厂每天能得到50桶牛奶的供 应, 每天工人总的劳动时间为480小时, 并且设备甲每天 至多能加工100公斤 设备乙的加工能力没有限制. 试 为该厂制定一个生产计划, 使每天获利最大, 并进一步 讨论以下3个附加问题:,若用35元可以买到1桶牛奶, 应否作这项投资? 若投 资, 每天最多购买多少桶牛奶?,若可以聘用临时工人以增加劳动时间, 付给临时工 人的工资最多是每小时几元?,由于市场需求变化, 每公斤 的利润增加到30元, 应否改变生产计划?,解 设 表示这两种产品每天所消耗牛奶的数量 （单位：桶）. 则用
9、于生产 的牛奶可获利 用于生产 的牛奶可获利 则目标函数为,限制条件分别为:,对原料的限制:,劳动力的限制,设备甲的开工限制,由此得到相应的规划模型,对每一约束条件,在第一象限中确定坐标点的范围, 最 终确定解的范围可行域（多边形区域）;,模型求解,解法1 （图解法）,确定等值线（图中用虚线），则最优解为可行域与 等值线的最后交点（即图中点的 坐标）即为所求问 题的最优解.,为此求解方程,容易得到该方程的解为,解法2 （单纯形方法）,原规划的标准型为,解法3 （利用计算机软件）,在软件Lingo8下进行求解:,输入命令,Variable Value Reduced CostX1 20.0000
10、0 0.000000X2 30.00000 0.000000,Row Slack or Surplus Dual Price1 3360.000 1.0000002 0.000000 48.000003 0.000000 2.0000004 40.00000 0.000000,得到的解为,表达式的意义,在第二张表中, Slack or Surplus表示引入的松弛变量 或剩余变量的取值. 因而第二及第三行表示 此说明条件1及2为紧约束条件. 而 表示条件3为 非紧约束条件, 即设备甲尚有40个工时的剩余时间.,第三列的Dual Price（对偶价格, 又称为影子价格）, 反映资源1和2每增加一
11、个单位所能带来的效益. 第二行 说明每增加一个单位, 可带来利润48元, 而第三行说明,每增加一个临时工, 能带来2元的收益.,而设备甲的对偶价格为0.,结果分析,三个约束条件的右端视为“资源”: 原料, 劳动时间, 设备甲的加工能力. 对当前解而言, 前两种“消耗殆尽”， 而设备甲尚余40公斤的加工能力.,目标函数可以看作为是“效益”. 成为紧约束的资源 一旦增加, 则“效益”必然增加. 解中列出的“对偶”价格表 示紧约束“资源”每增加一个单位后相应“效益”的增加值.,原料每增加一个单位, 利润可增加48个单位; 而劳动时间 每增加一个单位, 利润可增加2个单位. 而非紧约束资源 的增加,
12、不会带来相应的收益. 这种“资源”潜在价值被 称为 “影子”价格.,用“影子”价格即可回答附加问题.,用35元购买一桶牛奶, 低于牛奶的影子价格, 故可以 做这项投资; 临时工人每小时的工资不超过2元. 而设 备甲尚有富裕能力, 故增加工时不会产生效益.,目标函数的系数发生变化对最优解和最优值的影响.在图解法中可以看到，价值系数 对最优解会产 生一定的影响. 因为 确定了等值线的斜率, 原问题 等值线的斜率为 , 当斜率上升到 则 最优解将会改变, 此时最优解将在点取得.,灵敏度分析还给出了各个系数的范围: 的上界为24, 下界为8, 即当 时, 最优 解不变; 同样当 时,最优解不变.,从图
13、中还可以看出, 原 料（牛奶）的增加, 对应 的是直线 的向右的 平移, 此时最优解仍 为点 但当 与 重合 时, 最优解将不再改变,灵敏度分析结果: 执行Range命令, 可得相应结果,Current Allowable AllowableVariable Coefficient Increase DecreaseX1 72.00000 24.00000 8.000000X2 64.00000 8.000000 16.00000Righthand Side RangesRow Current Allowable AllowableRHS Increase Decrease2 50.00000 10.00000 6.6666673 480.0000 53.33333 80.000004 100.0000 INFINITY 40.00000,
