运筹学第五章整数规划详解.pptx

薛威 2015年4月 ;;第五章整数规划;线性规划模型：;线性整数规划;整数线性规划问题;纯整数规划的数学模型：;例1.胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时，油漆工2小时。生产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？;例2.某服务部门各时段（每2小时为一时段）需要的服务员人数见下表。按规定，服务员连续工作8小时（即4个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。 ;解 设在第j时段开始时上班的服务员人数是xj。由于第j时段开始时上班的服务员将在第（j+1）时段结束时下班，所以决策变量只需考虑x1，x2 ，x3 ，x4 ，x5。该问题的数学模型是;解：;总结 整数规划的可行域包含在其对应的一般线性规划可行域之内； 整数规划的最优解可能不是其对应的一般线性规划的顶点； 整数规划的最优解不会优于其对应的线性规划的最优解。;分支定界法; （1）先不考虑整数约束，解( IP )的松弛问题( LP )，可能得到以下情况之一： ①若( LP )没有可行解，则( IP )也没有可行解，停止计算。 ②若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 ③若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。 为讨论方便，设( LP )的最优解为： ; （2）分支：; （4）修改上、下界：按照以下两点规则进行。 ①在各分枝问题中，找出目标函数值最小者作为新的下界； ②从已符合整数条件的分枝中，找出目标函数值最小者作为新的上界。;2、例题;解：先解该整数规划对应的松弛问题;问题2;分支定界过程;;割平面法;;计算步骤： （1）用单纯形法求解( IP )对应的松弛问题( LP )： ①若( LP )没有可行解，则( IP )也没有可行解，停止计算。 ②若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 ③若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。 ; （2）从(LP)的最优解中，任选一个不为整数的分量xr,,将最优单纯形表中该行的系数 和 分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程：;例：用割平面法求解整数规划问题; 此题的最优解为：X＊= (1 , 3/2) Z = 3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 生成割平面的条件为: ;0-1整数规划;0－1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。 是否能对上述方法进行优化，使得运算量进一步减少呢？根据上述算法的特点，可以按目标函数中各变量系数的大小顺序重新排列各变量，以使最优解尽可能早出现。;试用改进的算法求解下题：; 在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。;设决策变量 1 分配第i 个人去做第j 件工作 xij = 0 相反 ( i, j=1.2. …n );指派问题的性质;解题步骤：; 第二步：进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为： (1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎ 。然后划去◎ 所在列(行)的其它0元素，记作? ；这表示这列所代表的任务已指派完，不必再考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然