第三章整数规划
一般整数规划问题
整数规划的解法
0—1规划
指派问题
物流资源分配问题
知识目标
掌握整数规划的基本形式;
掌握分枝定界法计算过程;
理解割平面法;
掌握0—1规划的标准形式;
了解0—1变量的应用;
掌握0—1规划的匈牙利解法。
技能目标
能够结合实际情况建立整数规划模型,并可利用分枝
定界法求解;
能够应用0—1规划建模并求解,安排人员工作。
第一节一般整数规划问题
什么是整数规划问题?
整数规划的一般形式:
第二节整数规划的解法
割平面法
分枝定界法
例3-5
割平面法
基本思想:求原问题对应松弛问题最优解,如果不是原问题的可行解,则通过引入线性约束条件(即割平面),使松弛问题的可行域逐步缩小(即切掉一部分),每次切割掉的是松弛问题的非整数解的一部分,但不切掉任何整数解,直到最后使目标函数达到最优的整数解成为可行域的一个顶点时,即为原问题的最优解。其本质是利用线性规划的求解方法逐步缩小可行域,最后找到整数规划的最优解。
例3-6
其最优解为=(1,1)最优值为=1
第三章 物流运筹学—— 整数规划 来自淘豆网m.daumloan.com转载请标明出处.
