山东大学 运筹学课件及课后解答4第四章 整数规划与分配问题 (新)a.ppt

文档介绍：作业:P125 (a) 第四章整数规划与分配问题第一节整数规划的特点及应用
一、整数规划的一般形式定义:一部分或全部决策变量必须取整数值的规划问题称为整数规划。不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题。若松弛问题是线性规划,则该整数规划称为整数线性规划。
整数线性规划的一般形式:
不考虑整数要求时,
最优解为: X=( ,)T Z=13 (见下页图解法)
考虑整数要求时,最优解为:X=(4 ,1)T Z=14
凑整(3,2)可行,非最优,Z=13。
(4,3),(4,2),(3,3)
不可行
二、整数规划的分类1. 全整数线性规划 决策变量全部取整数,约束系数和约束常数项也取整数的整数线性规划。2. 纯整数线性规划 决策变量全部取整数,约束系数和约束常数项可取非整数的整数线性规划。 纯整数线性规划可化为全整数线性规划。3. 混合整数线性规划 决策变量中有一部分取整数值,另一部分可取非整数值的整数线性规划。4. 0-1整数线性规划 决策变量只能取0或1的整数线性规划。
三、0-1变量(或称逻辑变量)在模型中的应用 整数规划模型对研究管理问题有重要意义。很多不能归结为线性规划数学模型的管理问题,却可以通过设置逻辑变量建立起整数规划数学模型。
第二节分配问题(指派问题)与匈牙利法2-1 问题的提出及数学模型 假设有m项任务分配给m个人去完成,并指定每个人完成其中一项,每项任务也只由一个人完成,问应如何分配任务,才能使总效率最高?(或总费用最少,花费的总时间最少等等。) 设每个人完成不同任务的耗费见下面的效率矩阵,通常要求aij≥0。