《运筹》教学课件整数规划第四章（一）整数规划问题.ppt

《《运筹》教学课件整数规划第四章（一）整数规划问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹帷幄之中决胜千里之外运筹学课件整数线性规划IntegerLinearProgramming内容整数规划问题介绍整数规划算法——分枝定界法整数规划算法——割平面法0-1规划指派问题(分派问题)线性规划模型：实际问题要求xi为整数！如机器的台数，人数等线性整数规划非线性整数规划简称整数规划3.1整数规划问题一、实例例2.1胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时，油漆工2小时。生产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小

2、时。问该厂如何组织生产才能使每月的销售收入最大？纯整数规划例（背包问题）一个旅行者，为了准备旅行的必备物品，要在背包里装一些有用的东西，但他最多只能携带b公斤的东西，而每件物品都只能整件携带，于是他给每件物品规定了一个“价值”，以表示其有用程度。如果共有m件物品，第i件件物品的重量为bi，价值为ci，问题就变成：在携带的物品总重量不超过b公斤的条件下，携带哪些物品可使总价值最大解：Z表示所带物品的总价值携带物品的总重量数学模型：0-1规划解：数学模型：混合型整数规划纯整数规划0—1规划混合型整数规划纯整数规划的数学模型：0--1规划的数学模型：例×√√√√Z=130√√√

3、√，可行且Z=140不可行可行注释最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多余于顶点，枚举法不可取二、整数规划解的理论（IP）（IP）问题的松弛问题∩≤松弛问题的最优值是原整数规划的目标函数值的上界