第五章整数规划案例.ppt

第五章 整数规划;第五章 整数规划（重点和难点）;§1 整数规划问题的提出;背包问题 一背有容量为250 cm3的背包的小偷进入库房（或某户人家或机房），他需要从若干物品中选择一定数量装入背包带走。可选的物品有7种，其价值、体积及最大的数量入下表:;令xi表示小偷选择物品i的数量，则背包问题的数学模型为; 例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5-1： 问两种货物各托运多少箱,可使利润最大?;问题分析;什么是整数规划？;整数规划的可行解，最优解;§2 分枝定界法;求解整数规划的方法;分枝定界法;例2;如何分枝和定界;分枝;解得;对B1和B2再分枝定界;B3,B4;B5, B6;图5-4;§3 ? 割平面法;用割平面法求解纯整数规划问题;割平面约束：-1/7x3-2/7x5=-6/7;;割平面约束：-1/4-1/4x6=-3/4;;§4 0-1型整数规划;什么叫0-1规划;4.1 引入0-1变量的实际问题;解:;投资总额不超过B;同济考研题;2、相互排斥的约束条件;① 二者择一;这m个约束条件变为m+1个约束条件和m个变量。 ;相互排斥的约束条件;3、关于固定费用问题;?????;采用各种生产方式的成本分别为;Y=1,不同于目标函数; 假定市场需求不成问题，服装厂每月可用的人工工时为2000小时，该厂如何安排生产可使每月的利润最大？;4.背包问题 一登山队员做登山准备，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相机和通讯设备。每件物品的重要性系数和重量见下表，假定登山队员可携带的最大重量为25千克。; 令xi=1表示登山队员携带物品i，xi=0表示不携带物品i。则问题可写为：;工件排序问题;4.2 0-1整数规划的解法—— 隐枚举法 通过检查变量取值的部分组合求得最优解的方法。;;;;;4.2 0-1型整数规划的解法;例6;表5-5;§5 指派问题; ;表5-7;类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题；有n条航线，怎样指定n艘船去航行问题…等等。对应每个指派问题，需有类似表5-7那样的数表，称为效率矩阵或系数矩阵，其元素cij（≥）0（i,j=1,2.…,n）表示指派第i人去完成第j项任务时的效率（或时间、成本等）。 解题时需引入变量xij；其取值只能是1或0。并令 1 当指派第i人去完成第j项任务 xij= 0 当不指派第i人去完成第j项任务;当问题要求极小化时数学模型是：;如例7的一个可行解（矩阵）是：;指派问题是0-1规划的特例，也是运输问题的特例；即n=m，ai=bj=1.当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法。 指派问题的最优解的性质:若从系数矩阵(cij)的一行（列）各元素中分别减去一个常数 ，得到新矩阵(bij)，那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。 ;指派问题求解的思想;匈牙利算法;匈牙利算法的步骤;例7的计算为;第二步：进行试指派，以寻求最优解。为此，按以下步骤进行。 经第一步变换后，系数矩阵中每行每列都已有了0元素，但需找出n个独立的0元素。 若能找出，就以这些独立0元素对应解矩(xij)中的元素为1，其余为0，这就得到最优解。 当n较小时，可用观察法、试探法去找出n个独立0元素。若n较大时，就必须按一定的步骤去找， ;常用的步骤为：;（2）给只有一个0元素列（行）的0元素加圈，记作◎；然后划去◎所在行的0元素，记作ф （3）反复进行（1），（2）两步，直到所有0元素都被圈出和划掉为止。 ;（4）若仍有没有划圈的0元素，且同行（例）的0元素至少有两个（表示对这人可以从两项任务中指派其一）。 这可用不同的方案去试探。 从剩有0元素最少的行（列）开始，比较这行各0 元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈（表示选择性多的要“礼让”选择性少）。然后划掉同行同列的其它0元素。 可反复进行，直到所有0元素都已圈出和划掉为止。 ;（5）若◎元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。 若mn，则转入下一步(增加0元素)。 ;现用的例7的（bij）矩阵，按上述步骤进行运算，按步骤(1)，选给b22加圈，加后给b31加圈，划掉b11,b41，按步骤（2），给b43，划掉b44,最后给b14加圈，得到 ;可见m=n=4，所以得最优解为; 例8 求表5-8所示效率矩阵的指派问题的最小解。;解