运筹学整数规划与分配问题新PPT学习教案.pptx

会计学
1
运筹学整数规划与分配问题新
整数线性规划的一般形式:
第1页/共69页
不考虑整数要求时，
最优解为： X=( ,)T Z=13 （见下页图解法）
考虑整数要求时，最优解为：X=(4 ,1)T Z=14
凑整 （3，2）可行，非最优，Z=13。
（4，3），（4，2），（3，3）
不可行
第2页/共69页
第3页/共69页
二、整数规划的分类1. 全整数线性规划 决策变量全部取整数，约束系数和约束常数项也取整数的整数线性规划。2. 纯整数线性规划 决策变量全部取整数，约束系数和约束常数项可取非整数的整数线性规划。 纯整数线性规划可化为全整数线性规划。3. 混合整数线性规划 决策变量中有一部分取整数值，另一部分可取非整数值的整数线性规划。4. 0-1整数线性规划 决策变量只能取0或1的整数线性规划。
第4页/共69页
三、0-1变量（或称逻辑变量）在模型中的应用 整数规划模型对研究管理问题有重要意义。很多不能归结为线性规划数学模型的管理问题，却可以通过设置逻辑变量建立起整数规划数学模型。
第5页/共69页
第6页/共69页
第7页/共69页
第8页/共69页
第二节 分配问题(指派问题）与匈牙利法 2-1 问题的提出及数学模型 假设有m项任务分配给m个人去完成，并指定每个人完成其中一项，每项任务也只由一个人完成，问应如何分配任务，才能使总效率最高？（或总费用最少，花费的总时间最少等等。） 设每个人完成不同任务的耗费见下面的效率矩阵，通常要求aij≥0。
第9页/共69页