《运筹学教学演示系统⑶.ppt》由会员分享，可在线阅读，更多相关《运筹学教学演示系统⑶.ppt（37页珍藏版）》请在金锄头文库上搜索。
1、第四章 整数规划第一节 整数规划问题的提出 对于一个线性规划问题，若要求某些决策变量的取值为整数，这样的规划问题称为整数规划。如：上班人数问题，厂址选择问题，集装箱运输问题等。 例1 某厂拟用集装箱托运甲、乙两种货物，集装箱的体积和重量以及获利如下表，确定如何托运获利最大。货物体积重量利润甲乙54252010资源限制2413则数学模型为： 若按一般线性规划问题求解，其解为：那么能否按照四舍五入的方式取整数呢？可以看出取整数后，并不是可行解。方法：分枝定界法、割平面法第二节 分枝定界法 设整数规划问题为 该整数规划相应的线性规划（辅助规划F）为：最优解为： 若辅助规划问题最优解的所有分量都为整数
2、，则已经得到原整数规划问题的最优解。 否则，确定整数规划问题的上下界。 上界： 分枝 以某一不为整数的分量，构造两个约束条件，形成两个规划问题。设令表示小于的最大整数，则可构造两个约束条件为： 下界：任一整数规划问题的可行解 将这两个约束条件分别加入到辅助规划问题中，得到两个辅助规划的子问题F1，F2。 F1为： F2为： 定界 对F1及F2进行求解，修改上下界。为F1，F2中较大的目标函数值为符合整数条件的最大目标函数值，否则为零 剪枝 对于辅助规划子问题的目标函数值小于下界的，可剪去。 对于辅助规划子问题的目标函数值大于下界的，而又没有得到整数解，可继续分枝，直到得到整数规划问题的最优解或
3、者判定原问题无最优解。例2 解：设原整数规划相应的辅助规划问题F为：为了描述清楚起见，用剪枝树状图表示分枝定界法的过程，见下页。辅助规划FX=(3.25,2.5)Z=14.75辅助规划F1X=(3.5,2)Z=14.5辅助规划F2X=(2.5,3)Z=13.5辅助规划F11X=(3,2)Z=13辅助规划F12X=(4,1)Z=14 分枝定界法应注意的问题： 分枝的方法 分枝前后辅助规划模型的区别方程个数的增加 如何确定上下界，怎样调整上下界 何时剪枝 最优解的确定第三节 割平面法 分枝定界法和割平面法有共同的特点，都是在辅助规划模型中增加约束条件。 但在思想上有显著的差异：割平面法是割去一部分
4、不含任何整数可行解的区域，但也是通过逐步切割，最终得到整数最优解。 例3 整数规划问题为：如果某决策变量的最优解不为整数，不妨设：则辅助规划问题最优单纯形表中，该决策变量所对应的方程可表示为：该方程中系数分解为整数部分和非负小数部分之和的形式，即：br表示小于等于该系数的最大整数。显然：将分解式代入决策变量所对应的方程。一、基本原理 根据整数的要求，由于等式左边为整数，等式右边也应为整数。又由于整数解的必要条件割平面方程！逐步增加类似的割平面方程，解辅助规划，直至整数解。二、案例分析 例4辅助规划问题的最优单纯形表为：XBbX1X2X3X4X1X25/38/310015/6-2/3-1/61/
5、3-Z-13/300-1/6-1/6XBbX1X2X3X4X1X25/38/310015/6-2/3-1/61/3-Z-13/300-1/6-1/6若以X1所对应的方程，构造割平面方程，先看系数分解0,5/6-1,5/61,2/3则割平面方程为：引入松弛变量，将该方程加入到模型中。XBbX1X2X3X4X5X1X2X55/38/3-2/31000105/6-2/3-5/6-1/61/3-5/6001-Z-13/300-1/6-1/60XBbX1X2X3X4X5X1X2X3116/54/5100010001-1111-4/5-6/5-Z-21/50000-1/5若再以X3所对应的方程，构造割平面
6、方程，则为：XBbX1X2X3X4X5X6X1X2X3X6116/54/5-4/5100001000010-11101-4/5 -6/5-4/50001-Z-21/50000-1/50XBbX1X2X3X4X5X6X1X2X3X50421100001000010-111000 015/4-1-3/2-5/4-Z-400000-1/4 三、应注意问题 割平面方程割去了非整数的最优解 割平面方程不会割去整数规划问题的任一可行解 可以用任一行（方程）构造割平面方程 割平面方程并不是把满足该方程的区域割掉第四节 0-1规划模型 0-1规划是整数规划的特殊情形，决策变量只取0-1值，在现实问题中，反映了
7、有或者无，建与不建等方面的规划问题。 一、实际问题的0-1规划描述 1.投资场所的选定 例5 某公司拟在市区的东、西、南三区建门市部，有七个位置可供选择，规定： 在东区，A1，A2，A3最多选2个； 在西区，A4，A5至少选1个； 在南区，A6，A7至少选1个。 选用Aj，投资bj元，获利Cj元。但投资总额不超过B元，如何选择？ 设当Aj点被选用当Aj点未选用 则： 2.相互排斥的约束条件 如关于体积限制：如何将这两个条件纳入一个规划模型中，可引入0-1变量Y,令： 3.典型例题 例5 某公司生产三种服装，若生产需要租用某种设备，有关数据如下表。服装厂每月可用2000个人工工时，问该厂如何安排
8、生产可使利润最大。服装种类设备租金生产成本销售价格人工工时设备工时设备台时西服衬衫大衣500020003000280302004004030051430.52300300300 问题在于是否租用设备，若租用才有设备台时资源，因而该问题一是决策是否租用，二是每种产品的产量是多少？ 设租用第i 种设备不租用第i 种设备 设xi表示各类服装生产量，则： 二、0-1规划的解法 穷举法 隐枚举法：只检查决策变量的一部分取值组合，就能够得到问题的最优解。 例6 从目标函数中，找到一个较好的容易找出的可行解，并计算目标函数的值。-过滤条件 如本例中X=(0,0,1)，Z=5，然后逐步判断迭代。 逐步判断迭代
9、过程列表如下：点条件是否可行Z值目标1234(0,0,1)(0,1,1)(1,0,1)58 在计算中，为了减少计算工作量，可采取如下措施： 1.改变过滤条件 2.重新排xi在目标函数中的顺序，解的组合也按此顺序组合。第五节 指派问题 现实中，经常遇到这样的问题，几个人恰好从事几项任务，由于每人专长不同，效率不同，那么如何分配任务使效率最大或所消耗时间最小。如： 工作 时间人员B1B2B3B4B5A1A2A3A4A579874512536974678116951199611 一、指派问题的数学模型 设第i位人员被分配到第j个岗位第i位人员不分配到第j个岗位 则问题的数学模型为： 二、模型的特征及
10、解的结构 从模型的结构上看，指派问题既是一类特殊的运输问题，又是一类特殊的0-1规划问题，能否按照运输问题等方法求解呢？ 模型任一可行解的结构（解矩阵）可描述为： 解矩阵的特征使得该模型若按运输问题的方法求解，基变量的个数为9个，因而是一个高度退化的运输问题。 三、价值系数特征 根据模型解矩阵的特征，其价值系数也构成了效益矩阵。不失一般性，效益矩阵记为： 在指派问题中，最优解具有这样的性质：若从效益矩阵的某行（列）的每一个元素中减去一个常数 k后，所得到的新的效益矩阵所表示的指派问题与原指派问题具有相同的最优解。原目标函数：新目标函数： 因此，新目标函数与原目标函数之差为该常数，是线性关系。也
11、就是说，新目标函数取得最大值时，原目标函数也将取得最大值。 四、指派问题的解法匈牙利法 匈牙利法的核心是匈牙利数学家D.Konig 提出了关于零元素的重要定理：效益矩阵中独立零元素的个数等于能覆盖所有零元素的最少直线数。 匈牙利法的步骤： 变换效益矩阵，使每行每列都有零元素 根据价值系数的特征，对效益矩阵中的每行（列）减去该行（列）的最小元素，使每行每列至少有一个零元素存在。 关键在于零元素的位置，特别是处于不同行不同列的零元素独立零元素。 如果独立零元素的个数等于n，则已得到最优解。 进行试分配 试分配的过程就是找独立零元素的过程。 从具有零元素最少的行（列）开始，圈出一个零元素并划去同行同
12、列的其他零元素，依次进行下去。 作能覆盖零元素的最少直线 对没有圈0的行打“”号； 对打“”号的行上有零元素的列打“”号； 对打“”号的列上圈0的行打“”号； 重复、，直到打不出 “”号为止； 对没有打“”号的行画横线，对打“”号的列画竖线。 效益矩阵的变换 在未被直线覆盖的元素中找出最小元素； 对未画直线的行的各元素都减去最小元素； 对画直线的列的各元素都加上最小元素。 五、注意的几个问题 1.效益矩阵的变换规则（找出最小元素） 未被直线覆盖的元素都减去最小元素； 竖单线覆盖的元素不变； 交叉线（双线）覆盖的元素加上最小元素。 2.对于求极大化问题如何处理 1）效益矩阵变成负的，再进行处理。 2）用bij=M-cij进行效益矩阵转换（M为足够大正数） 3.行列不等情形的处理 增加相应的行列，其效益值根据具体情况而定。
