第四章整数规划与分配问题(IntegerProgramming,iP)整数规划的有关概念及特点指派问题及匈牙利解法整数规划的求解方法：分枝定界法、割平面法82$3$422024-10-27
2024-10-27 2 第四章 整数规划与分配问题 （Integer Programming, IP) n 整数规划的有关概念及特点 n 指派问题及匈牙利解法 n 整数规划的求解方法：分枝定界法、割平面法 §2 §3 §4
s13整数规划的有关概念及特点概念整数规划：要求决策变量取整数值的规划问题。（线性整数规划、非线性整数规划等）0-1变量：在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量0-1规划：在整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。2024-10-27
2024-10-27 3 0-1变量：在整数规划中，如果变量的取值只限于0和1，这 样的变量我们称之为0-1变量。 0-1规划：在整数规划问题中，如果所有的变量都为0-1变 量，则称之为0-1规划。 §1 整数规划的有关概念及特点 一 、 概念 整数规划： 要求决策变量取整数值的规划问题。 （线性整数规划、非线性整数规划等）
0一1规划举例：选址问题一一相互排斥的计划例1：某公司拟于东、西、南三区建立项目部，有7个位置A;（1，2，……，7）可供选择，规定：（1）在东区，由A’A2，A,三点中至多选择2个；（2）在南区，由A4，A,两点中至少选择1个；（3）在西区，由Ab，A,两点中至少选择1个如选用A点，设备投资估计为b元，每年可获利估计为c元，但设备投资总额不能超过B元。问应选择哪几个点可使年利润最大？试建立数学模型。2024-10-27
2024-10-27 4 例1：某公司拟于东、西、南三区建立项目部，有7个位置Ai （i=1，2，.，7）可供选择，规定： （1）在东区，由A1，A2，A3三点中至多选择2个； （2）在南区，由A4，A5两点中至少选择1个； （3）在西区，由A6，A7两点中至少选择1个。 如选用Ai点，设备投资估计为bi元，每年可获利估计为ci元， 但设备投资总额不能超过B元。问应选择哪几个点可使年利 润最大？ 试建立数学模型。 0-1规划举例：选址问题——相互排斥的计划
0一1规划举例：选址问题一一相互排的计划解：引入0-1变量x;，[1选A,(i = 1,2,., 7)X10不选A,则:max z =xCi=11x,b, ≤Bi=X+X2+X3≤2X4 +x, ≥1X +x, ≥1x, = 0或1(i =1,2,,7)2024-10-27
2024-10-27 5 解：引入0-1变量xi， 0-1规划举例：选址问题——相互排斥的计划 1 ( 1, 2, ,7) 0 i i i A x i A 选 不选 则： 7 1 max i i i z x c x b B i i i 7 1 x1 x2 x3 2 x4 x5 1 x 0 1(i 1,2, ,7) i 或 x6 x7 1
整数规划的求解特点求整数解的线性规划问题，不是用四舍五入法或去尾法对性规划的非整数解加以处理就能解决的，用枚举法又往往会计算量太大，所以要用整数规划的特定方法加以解决。例：求解下列整数规划：max z = 3x +2x2[2xi +3x2≤14s.t) x, +0.5x2 ≤ 4.5xi,x2≥0,并取整数2024-10-27
2024-10-27 6 求整数解的线性规划问题，不是用四舍五入法或去尾法对 性规划的非整数解加以处理就能解决的，用枚举法又往往 会计算量太大，所以要用整数规划的特定方法加以解决。 例： 求解下列整数规划： 二、 整数规划的求解特点 , 0,并取整数 0.5 4.5 2 3 14 .max 3 2 1 2 1 2 1 2 1 2 x x x x x x st z x x