第三章整数规划问题.ppt

1、第三章 整数规划模型,3.1 投资决策问题 3.2 背包问题 3.3 合理下料问题 3.4 生产组织与计划问题 3.5 工厂选址问题 3.6 设备购置和安装问题 3.7 旅行商问题,3.1 投资决策问题,问题,某市在“十五”计划期间有b亿元的资金可用于n个 项目的投资。 若对第i个项目投资，需资金 亿 元，可获利税收入 亿元。试确定一个投资方案， 使该方案下该市新增的利税收入最多。 建立此问 题的数学模型。,解：,设该市获得的新增利税收入为z亿元，并令 1，若对第i个项目投资 = i=1,2,n 0，若不对第i个项目投资 则上述问题的数学模型如下：,max z =,s.t. b,=0或1；i=

2、1，2，n,说明,1. 是本投资方案的总收益； 是 本投资方案的总投入。 2.这是个纯整数规划问题，也是一个0-1 规划问题。由于目标函数z是决策变量的线性函数，并且约束条件也是决策变量的线性不等式，所以这是个0-1整数线性规划问题。,3.2 背包问题,问题,设有一个容积为b的背包，有n个体积 为 (i = 1，2，n),使用价值分别为 （i = 1，2，n）的物品可以装入背包。 问应选择哪几件物品装入背包，才能得到 最大的使用价值？试建立数学模型。,解： 1 将第i件物品装入背包 令 = 0 不将第i件物品装入背包 (i=1,2,n) 并设装入背包的总使用价值为z，则本背包 问题的数学模型为

3、：,max z =,s.t. b,= 0或1；i=1，2，n,说明,为装入背包的物品的总价值，希望其取 最大值。 为装入背包的物品的总体积，它不能超 过背包的容量。 3. 本模型也是一个0-1整数线性模型。,3.3 合理下料问题,问题,假设要利用某类钢板下m种零件 ， ， 的毛料。根据既省料又容易操作的原则，人们在 一块钢板上，已经设计出n种不同的下料方案。 设在第j种下料方案中，可下得第i种零件 的个 数为 ，第i种零件的需要量为 ，i=1，2， m。问应如何下料，才能既满足需要，又使所用 的钢板总数最少？,解：设采用第j种方案下料的钢板数为 ，所用钢 板的块数为y，则本问题的数学模型如下：

4、,min y = s.t. i=1，2，m 0 I，j=1，2，n,说明,1.采用各种方案下料的钢板数 的总和，即为 所用的钢板数。 2.完工后，第i种零件下料的数目不少于 。 3.本模型是一个非0-1的整数规划模型。,3.4 生产组织与计划问题,问题,某工厂用m台机床： ， ， ，加工n种 零件 ， ， 。在一个生产周期内，已 知第i台机床只能工作 个机时，i=1，2， m。该工厂必须完成加工零件 的数量为 个， j=1，2，n。机床 加工零件 一个所需的 机时和成本分别为 （机时/个）和 （元/个）。 问在这个生产周期，应如何安排各机床的生产任 务，才能既完成生产任务，又使总的加工成本最

5、小？,解：设机床 在一生产周期内加工零件 的个数为 ， i=1，2，m； j=1，2，n。又设总的加工 成本为y，则本问题的数学模型如下：,min y = s.t. ，i=1，2，m ， j=1，2，n 0 ，且 I， i=1，2，m； j=1，2，n,说明,1.总加工成本应等于各机床 加工零件 的个数 乘以该机床加工零件 的单位成本 （元/个）的 总和。,2. 因为按问题要求，机床 加工各零件的机时不能 超过该机床能工作的机时数 ，所以第一个约束 条件成立。 3. 因为按问题要求，各机床 加工零件 的数目不 能少于对 的需要量 ，所以第二个约束条件成 立。 4. 本模型是一个非0-1的整数规

6、划模型。,3.5 工厂选址问题,问题,设有n个需求点（如城市、仓库或商店等），有m个 可供选择的建厂地址。每个地址至多可建一个工厂。 在 i 地址建立工厂后的生产能力为 ，在 i 地址经 营工厂，单位时间的固定成本为 （元），需求点 j 需求量为 ，从厂址 i 到需求点 j 的单位运费为 （元/吨）。问应如何选择厂址和安排运输计划，才 能得到经济上最少的方案？,解：设在单位时间内，从厂址 i 运到 需求点j的物资 数量为 （吨），并引入布尔变量 1，若在 i 地建厂 = 0，若不在 i地建厂 又设单位时间的总花费为s（元），则本问题的 数学模型为：,min s = +,s.t. ，i=1，2，

7、m,，j = 1，2，n,0， 其中 = 0 或 1， i=1，2，m j=1，2，n,说明,是总运费， 是总生产成本。 是产地 i 运出的物资总量， 是产地i 的生产总量。 是所有产地运达需求点j的物资总量， 是j地的需求量。 本模型中的变量既有0-1变量，又有非0-1变 量，所以是一个混合型的整数规划模型。,3.6 设备购置和安装问题,问题,某工厂需要m种设备 ， ， ，设 的单价 为 元。该厂已有第i种设备 台，i=1，2，m。 今有资金 M 元，可用于购置这些设备。另知该厂有 n处可安装这些设备， 处最多能安装 台；将一台 设备 安装在 处，经济效益为 。应如何购置和 安装这些设备，才

8、能使总的经济效益最高？,解：用 表示设备 安装在 处的台数， 表示购置 的台数，z表示总的经济效益，则本问题的数学 模型为：,max z = s.t. + ，i=1，2，m j=1，2，n,M,0,且 ， I，i=1，2，m,j=1，2，n,说明,是第i种设备安装在第j处产生的效益；全 体各已安装的设备产生的效益的总和即为总的 经济效益。 2.安装设备 到各处的总数目不会超过设备 的 拥有数。即新购置的数目 与原有数目 之和。 3.安装在j处的各种设备的总数目 不能超过j处 可安装的数目 。 4.购置新设备的总花费 不能超过可用的资金 总量M。,3.7 旅行商问题,问题,一个商人拟到n个城市去推销商品。已知每两个 城市 和 之间的距离为 ，任何选择一条道 路， 使得商人每个城市走一遍回到起点，且所 走的路径最短。,本问题称为旅行商问题（记为TSP），也叫货郎 担问题或邮路问题。是一种特殊的Hamilton（哈 密尔顿回路问题。,解： 令,1，商人选择的路线包含从 到 的边 = 0