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

1、 4.5.1 装载问题 4.5.24.5.2 选址问题 4.5.34.5.3 固定成本问题 4.5.4 指派问题 4.5.54.5.5 投资问题 4.5.6 工件排序问题 整 数 规 划 【例4-8】某公司准备用集装箱托运甲、乙二种货物，而这二种货物 每件的体积、重量、可获取利润及体积和重量托运限制如表4-6所示。 又知甲种货物至多托运4件，乙种货物最多托运5件，问两种货物各 托运多少件，可使获得利润最大，建立其数学模型。 货物每件体积（立方米） 每件重量（千克）每件利润（百元） 甲19542 乙273403 托运限制1365140 表4-6 货物信息表 整 数 规 划 在 经 济 管 理 中

2、 的 应 用 解：设x1,x2分别为甲、乙两种货物的托运件数，其数学模型建 立如下： 整 数 规 划 在 经 济 管 理 中 的 应 用 【例4-9】某公司计划在本市东、南、西、北四区建立销售部门，初 步考虑后有10个位置Ai(i=1,2,310)可供选择，考虑到各地区居民 消费的水平及居民居住密集度，设定： 在东城区由A1、A2、A3三个点至多选择两个； 在西城区由A4、A5两个点中至少选一个； 在南城区由A6、A7两个点中至少选一个； 在北城区由A8、A9、A10三个点中至少选二个； Ai各点的投资金额及每年可获利润由于地点不一样而不同，预测情 况如表4-7所示： 投资总额不超过720万元

3、，请问应选择哪几个销售点，使年利润最大？ A1A2A3A4A5A6A7A8A9A10 投资额10012015080709080140160180 利润36405022203025485861 表4-7地区利润表 单位：万元 整 数 规 划 在 经 济 管 理 中 的 应 用 解：设0-1变量 这样我们可建立如下数学模型： 约束条件如下： 整 数 规 划 在 经 济 管 理 中 的 应 用 【例4-10】某工厂生产三种类型的产品A、B、C，所用的资源为：原材料、劳动力 和机器设备。生产每个产品的资源需求量如表4-8所示。不考虑固定成本，每种产 品A、B、C的利润分别为4万元、5万元、6万元，可使

4、用的材料总量为500吨，劳动 力300人/月，机器100台/月。此外，如果工厂开通该产品的生长线，不管生产多少 个A、B、C产品，工厂都需要付出一定量的固定成本，具体如下：A产品为100万，B 产品为150万，C产品为200万元。现在要制定一个生产计划，使其获得利润最大。 资源产品A产品B产品C 原材料/吨248 劳动力（人/月）234 机器设备（台/月）123 表4-8 产品资源需求量表 整 数 规 划 在 经 济 管 理 中 的 应 用 此问题的数学模型如下： 把上述模型输入WinQSB软件中，得到如下结果：最大目 标函300，最优解为x1=100, x2=0, x3=0, 也就是说生产1

5、00台 A产品可获取最大利润300万元。 整 数 规 划 在 经 济 管 理 中 的 应 用 在工作任务的安排中，有n项不同的任务，有m个人分别承担 这些任务，但由于每个人特长不一样，完成各种任务的效率也 不相同。现假设必须指派每个人去分别完成一项任务，怎么样 把n项任务指派给m个人，使得完成n项任务的总效率最高，这 就是指派问题。 对于有m个人n项任务的一般指派问题，设： xij 并设cij为第i个人去完成j项任务的成本（如所需时间、 费用等），则一般指派问题的模型可以写成： 整 数 规 划 在 经 济 管 理 中 的 应 用 约束条件： 因为m不一定等于n,当mn时，即人多于任务时，就有人

6、没有任 务，所以前面m个约束条件都是小于等于1，这就是说每人至多 承担一个任务，而后面的n个约束条件说明每项工作正好有一 个人承担，所以都是等于1。 整 数 规 划 在 经 济 管 理 中 的 应 用 【例4-11】有四个人甲、乙、丙、丁，每人分别去完成四项不同的 工作，每人做各项工作所消耗的时间如表4-9所示，问应该如何指 派工作，才能使总消耗的时间最短？ 时间/ 工 小时 作 工人 ABCD 甲15182124 乙19232218 丙26171619 丁19212317 表4-9 每人工作消耗时间表 整 数 规 划 在 经 济 管 理 中 的 应 用 解：引入0-1变量xij,并令： xi

7、j 为使总的消耗时间为最少，写出目标函数： 每人只能完成一项工作，其约束条件如下： 整 数 规 划 在 经 济 管 理 中 的 应 用 每项工作只能由一个人来完成，其约束条件如下： 再加上约束条件：xij为0-1变量，对i=1,2,3,4。以上 就组成了此整数规划问题的数学模型。 我们将此模型输入WinQSB软件中，得到如下结果： x21=1,x12=1,x33=1,x44=1,其最小目标函数值为70，也就是说安 排乙干A工作，甲干B工作，丙干C工作，丁干D工作，这时消耗 的时间最少，即70小时。 整 数 规 划 在 经 济 管 理 中 的 应 用 【例4-12】某公司在以后五年内考虑给以下项

8、目投资，已知： 项目A：从第一年到第四年年初需要投资，并于次年回收本利 115%，但要求第一年投资最低金额为4万元，第二、三、四年 不限； 项目B：第三年初需要投资，到第五年末能收回本利128%，但 规定最低投资额为3万元，最高金额为5万元。 项目C：第二年年初需要投资，到第五年末能收回本利140%， 但规定其投资额为2万元或4万元，6万元、8万元。 项目D：五年内每年年初可购买公债，于当年归还，并加息6%， 此项目投资金额不限。 该部门现有10万元，问它应该如何确定给这些项目的投资金额， 使到第五年末拥有的资金本利总额为最大？ 整 数 规 划 在 经 济 管 理 中 的 应 用 此问题的数学模型如下： 整 数 规 划 在 经 济 管 理 中 的 应 用 【例4-13】用4台机床加工3件产品。各产品的机床加工顺序，以及 产品i在机床j上的加工工时aij见表4-11。由于交货期要求，产品2 的加工总时间不得超过d。现要求确定各件产品在机床上的加工方 案，使在最短的时间内加工全部的产品。 产品1 a11 a13 a14 机床1 机床3 机床4 产品2 a21 a22 a24 机床1 机床2 机床4 产品3 a32 a33 机床2 机床3 表4-11 机床加工信息表 整 数 规 划 在 经 济 管 理 中 的 应 用 解：设xij表示产品i