运筹学ABC-2整数规划建模课.ppt

整数规划在经济管理中的应用 整 数 规 划 4.5.1 装载问题 货物 每件体积（立方米） 每件重量（千克） 每件利润（百元） 甲 195 4 2 乙 273 40 3 托运限制 1365 140 表4-6 货物信息表 整数规划在经济管理中的应用 4.5.1 装载问题 解：设x1,x2分别为甲、乙两种货物的托运件数，其数学模型建 立如下： 整数规划在经济管理中的应用 4.5.2 选址问题 在东城区由A1、A2、A3三个点至多选择两个； 在西城区由A4、A5两个点中至少选一个； 在南城区由A6、A7两个点中至少选一个； 在北城区由A8、A9、A10三个点中至少选二个； Ai各点的投资金额及每年可获利润由于地点不一样而不同，预测情况如表4-7所示： 投资总额不超过720万元，请问应选择哪几个销售点，使年利润最大？ A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 投资额 100 120 150 80 70 90 80 140 160 180 利润 36 40 50 22 20 30 25 48 58 61 表4-7地区利润表 单位：万元 整数规划在经济管理中的应用 4.5.2 选址问题 解：设0-1变量 这样我们可建立如下数学模型： 约束条件如下： 整数规划在经济管理中的应用 4.5.3 固定成本问题 资源 产品A 产品B 产品C 原材料/吨 2 4 8 劳动力（人/月） 2 3 4 机器设备（台/月） 1 2 3 表4-8 产品资源需求量表 整数规划在经济管理中的应用 4.5.3 固定成本问题 此问题的数学模型如下： 把上述模型输入WinQSB软件中，得到如下结果：最大目标函300，最优解为x1=100, x2=0, x3=0, 也就是说生产100台A产品可获取最大利润300万元。 整数规划在经济管理中的应用 4.5.4 指派问题 在工作任务的安排中，有n项不同的任务，有m个人分别承担这些任务，但由于每个人特长不一样，完成各种任务的效率也不相同。现假设必须指派每个人去分别完成一项任务，怎么样把n项任务指派给m个人，使得完成n项任务的总效率最高，这就是指派问题。 对于有m个人n项任务的一般指派问题，设： xij 并设cij为第i个人去完成j项任务的成本（如所需时间、费用等），则一般指派问题的模型可以写成： 整数规划在经济管理中的应用 4.5.4 指派问题 约束条件： 因为m不一定等于n,当mn时，即人多于任务时，就有人没有任务，所以前面m个约束条件都是小于等于1，这就是说每人至多承担一个任务，而后面的n个约束条件说明每项工作正好有一个人承担，所以都是等于1。 整数规划在经济管理中的应用 4.5.4 指派问题 时间/ 工 小时 作 工人 A B C D 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 表4-9 每人工作消耗时间表 整数规划在经济管理中的应用 4.5.4 指派问题 解：引入0-1变量xij,并令： xij 为使总的消耗时间为最少，写出目标函数： 每人只能完成一项工作，其约束条件如下： 整数规划在经济管理中的应用 4.5.4 指派问题 每项工作只能由一个人来完成，其约束条件如下： 再加上约束条件：xij为0-1变量，对i=1,2,3,4。以上就组成了此整数规划问题的数学模型。 我们将此模型输入WinQSB软件中，得到如下结果：x21=1,x12=1,x33=1,x44=1,其最小目标函数值为70，也就是说安排乙干A工作，甲干B工作，丙干C工作，丁干D工作，这时消耗的时间最少，即70小时。 整数规划在经济管理中的应用 4.5.5 投资问题 【例4-12】某公司在以后五年内考虑给以下项目投资，已知： 项目A：从第一年到第四年年初需要投资，并于次年回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限； 项目B：第三年初需要投资，到第五年末能收回本利128%，但规定最低投资额为3万元，最高金额为5万元。 项目C：第二年年初需要投资，到第五年末能收回本利140%，但规定其投资额为2万元或4万元，6万元、8万元。 项