1 第五节线性整数规划 整数规划 变量只能取整数的规划问题 当变量只能取0或1两个值 称0 1规划 整数规划分类 纯整数规划 全部变量为整数 混合整数规划 部分变量为整数 本节主要介绍0 1规划的模型建立 2 例13 投资场所选址问题 计划在东 西 南三个区开设若干商业网点 拟在 A1 A7 7个地点中选择 规定 东区在A1 A2 A3中 至多选2个 西区在A4 A5中至少选1个 南区在A6 A7中 至少选1个 已知在Ai建点需投资bi 可获利ci 现共有资 金为B 问应如何布局可使总利润最大 分析 iiiii i i i xbxcA A A x AAxx 需投资为的利润为则 不选 选中 即 的选择变量分别表示地址决策变量 0 1 7171 LL 3 变量是 则模型为 不选 选中 解 设 10 1 1 2 71 76 54 321 7 1 7 1 xx xx xx xxx Bxb xcMaxz A A x i ii i ii i i i L 0 1 东区在A1 A2 A3中至多 选2个 怎样表示 2 321 xxx 4 例14 固定费用问题 某工厂为生产某种产品 有3种不同的生产 方式可供选择 设第j种生产方式的固定成本为 kj 可变成本为cj 若不考虑其他约束 请建立 使总成本最小的规划模型 0 0 0 j jjjj j x xxck j xj 种方式时的成本为则使用第 种生产方式时的产量为设采用第分析 0 0 0 1 种生产方式时即不采用第 种生产方式时即采用第 若设 jx j x y j j j 333322221111 xcykxcykxcykz 则总费用 5 10 0 或 初步建立模型为 j j y x xcykxcykxcykMinz 333322221111 怎样解决 时必有问题 不能保证当1 0 jj yx 的上界 则最后模型为为 加约束 jjjjj xMyMx 10 0 333322221111 或 j jjj j y yMx x xcykxcykxcykMinz