第十一章 整数规划方法 第十一章 整数规划方法 3 2016年8月19日 2016年8月19日 2016年8月19日 整数规划的一般模型； 整数规划解的求解方法； 整数规划的软件求解方法； 0-1 规划的模型与求解方法； 整数规划的应用案例分析。

Presentation on theme: "第十一章 整数规划方法 第十一章 整数规划方法 3 2016年8月19日 2016年8月19日 2016年8月19日 整数规划的一般模型； 整数规划解的求解方法； 整数规划的软件求解方法； 0-1 规划的模型与求解方法； 整数规划的应用案例分析。"— Presentation transcript:

1

2

3 第十一章 整数规划方法 第十一章 整数规划方法 3 2016年8月19日 2016年8月19日 2016年8月19日 整数规划的一般模型； 整数规划解的求解方法； 整数规划的软件求解方法； 0-1 规划的模型与求解方法； 整数规划的应用案例分析。

4 一、整数规划的一般模型 4 2016年8月19日 2016年8月19日 2016年8月19日 1. 问题的提出 : 固定资源分配问题

5 5 2016年8月19日 2016年8月19日 2016年8月19日 固定资源分配问题 固定资源分配问题

6 6 2016年8月19日 2016年8月19日 2016年8月19日 2. 整数规划模型的一般形式 一、整数规划的一般模型 问题是如何求解整数规划问题呢？ 能否设想先略去决策变量整数约束，即变为线性 规划问题求解，再对其最优解进行取整处理呢？ 实际上，可借鉴这种思想来解决整数规划问题．

7 7 2016年8月19日 2016年8月19日 2016年8月19日 1. 整数规划求解的总基本思想 二、整数规划求解方法 松弛问题 (A) 中的约束条件, 使构成易于求解的 新问题 --- 松弛问题 (B) ； 如果问题 (B) 的最优解是原问题 (A) 的可行解, 则 就是原问题 (A) 的最优解； 否则, 在保证不改变松弛问题 (B) 的可行解的条 件下, 修正松弛问题 (B) 的可行域 ( 增加新的约束 ), 得 到新问题 (C) ，再求问题（ C) 的解. 重复这一过程直到修正问题的最优解在原问题 (A) 的可行域内为止, 即得到了原问题的最优解。

8 8 2016年8月19日 2016年8月19日 2016年8月19日 1. 整数规划求解的总基本思想 二、整数规划求解方法

9 9 2016年8月19日 2016年8月19日 2016年8月19日 （ 1 ）分枝定界法的思想 2 整数规划分枝定界法 2. 整数规划分枝定界法 继续求解定界，重复下去，直到得到最优解为 止 。

10 10 2016年8月19日 2016年8月19日 2016年8月19日 （ 2 ） 分枝定界法一般步骤 2 、整数规划的分枝定界法 问题 (B) 无可行解，则 (A) 也无可行解，停止；

11 11 2016年8月19日 2016年8月19日 2016年8月19日 （ 2 ） 分枝定界法一般步骤 2 、整数规划的分枝定界法

12 12 2016年8月19日 2016年8月19日 2016年8月19日 （ 2 ） 分枝定界法一般步骤 2 、整数规划的分枝定界法

13 13 2016年8月19日 2016年8月19日 2016年8月19日 （ 2 ） 分枝定界法一般步骤 2 、整数规划的分枝定界法

14 14 2016年8月19日 2016年8月19日 2016年8月19日 （ 1 ） 割平面法的思想 3 、整数规划的割平面法 将原整数规划问题 (A) 去掉整数约束变为线性规 划问题 (B) ，引入线性约束条件 ( 称为 Gomory 约束， 几何术语割平面 ) 使问题 (B) 的可行域逐步缩小. 每次切割掉的是问题非整数解的一部分，不切掉 任何整数解，直到最后使目标函数达到最优的整数 解成为可行域的一个顶点时，即问题最优解。 利用线性规划的求解方法逐步缩小可行域，最后 找到整数规划的最优解。

15 15 2016年8月19日 2016年8月19日 2016年8月19日 （ 2 ） 割平面法的一般步骤 3 、整数规划的割平面法

16 （ 2 ） 割平面法的一般步骤 16 2016年8月19日 2016年8月19日 2016年8月19日

17 17 2016年8月19日 2016年8月19日 2016年8月19日 （ 2 ） 割平面法的一般步骤 这就是所要求的切割方程（ Gomory 约束条件） 。

18 18 2016年8月19日 2016年8月19日 2016年8月19日 （ 2 ） 割平面法的一般步骤 5 ）应用单纯形法求解，直到最优解为整数解为 止，否则继续构造 Gomory 约束条件。

19 3 、整数规划的 LINGO 解法 二、整数规划的求解方法 19 2016年8月19日 2016年8月19日 2016年8月19日

20 20 2016年8月19日 2016年8月19日 2016年8月19日 1 、 0-1 整数规划的模型 三、 0-1 整 数 规 划

21 21 2016年8月19日 2016年8月19日 2016年8月19日 2 、指派（或分配）问题 三、 0-1 整 数 规 划 在生产管理上，总希望把人员最佳分派， 以发挥其最大工作效率，创造最大的价值。 例如：某部门有 n 项任务，正好需要 n 个人 去完成，由于任务的性质和各人的专长不同， 如果分配每个人仅能完成一项任务。 如何分派使完成 n 项任务的总效益为最高 （效益量化），这是典型的分配问题。

22 2. 指派（或分配）问题 22 2016年8月19日 2016年8月19日 2016年8月19日 现在不妨设有 4 个人，各有能力去完成 4 项科研 任务中的任一项，由于 4 个人的能力和经验不同， 所需完成各项任务的时间如右表： 问如何分配何 人去完成何项 目使完成 4 项 任务所需总时 间最少？

23 23 2016年8月19日 2016年8月19日 2016年8月19日 2. 指派（或分配）问题

24 24 2016年8月19日 2016年8月19日 2016年8月19日 2. 指派（或分配）问题

25 25 2016年8月19日 2016年8月19日 2016年8月19日 2. 指派（或分配）问题

26 26 2016年8月19日 2016年8月19日 2016年8月19日 2. 指派（或分配）问题 指派问题的一般模型：

27 27 2016年8月19日 2016年8月19日 2016年8月19日 2. 指派（或分配）问题 指派问题的一般模型：

28 28 2016年8月19日 2016年8月19日 2016年8月19日 匈牙利算法的基本思想 因为每个指派问题都有一个相应的效 益矩阵，通过初等变换修改效益矩阵的行 或列，使得在每一行或列中至少有一个零 元素，直到在不同行不同列中都至少有一 个零元素为止。从而得到与这些零元素相 对应的一个完全分配方案，这个 方案对原 问题而言是一个最优的分配方案。 3. 指派问题的匈牙利算法

29 29 2016年8月19日 2016年8月19日 2016年8月19日 用 LINGO 求解 0-1 规划模型 4 、 0-1 规划的 LINGO 解法

30 30 2016年8月19日 2016年8月19日 2016年8月19日 1. 问题的提出

31 31 2016年8月19日 2016年8月19日 2016年8月19日 实验室开放时间为上午 8:00 至晚上 10:00; 开放时间内须有且仅段一名学生值班 ; 规定大学生每周值班不少于 8 小时 ; 研究生每周值班不少于 7 小时 ; 每名学生每周值班不超 3 次 ; 每次值班不少于 2 小时 ; 每天安排值班的学生不超过 3 人，且其中必须 有一名研究生. 试为该实验室安排一张人员的值班表，使总 支付的报酬这最少。 1. 问题的提出

32 32 2016年8月19日 2016年8月19日 2016年8月19日 2. 模型的建立与求解

33 33 2016年8月19日 2016年8月19日 2016年8月19日 问题的数学模型：问题的数学模型：

34 34 2016年8月19日 2016年8月19日 2016年8月19日

35 35 2016年8月19日 2016年8月19日 2016年8月19日

36 36 2016年8月19日 2016年8月19日 2016年8月19日 现有某市直属单位因工作需要，拟向社会公开招聘 8 名 公务员，具体的招聘办法和程序如下： （一）公开考试：凡是年龄不超过 30 周岁，大学专科以 上学历，身体健康者均可报名参加考试，考试科目有：综合 基础知识、专业知识和 “ 行政职业能力测验 ” 三个部分，每科 满分为 100 分．根据考试总分的高低排序按 1:2 的比例选择进 入第二阶段的面试考核． （二）面试考核：主要考核应聘人员的知识面、对问题 的理解能力、应变能力、表达能力等综合素质．按照一定的 标准，面试专家组对每个应聘人员的各个方面都给出一个等 级评分，从高到低分成 A/B/C/D 四个等级． 1 、问题的提出

37 37 2016年8月19日 2016年8月19日 2016年8月19日 1 、问题的提出 （三）由招聘领导小组综合专家组的意见、笔初试成绩 以及各用人部门需求确定录用名单, 并分配到各用人部门． 该单位拟将录用的 8 名公务员安排到所属的 7 个部门， 并且要求每个部门至少安排一名．这 7 个部门按工作性质可 分为： (1) 行政管理、 (2) 技术管理、 (3) 行政执法、 (4) 公共 事业． 招聘领导小组在确定录用名单的过程中，本着公平、 公开的原则，同时考虑录用人员的合理分配和使用，有利 于发挥个人的特长和能力．招聘领导小组将 7 个用人单位的 基本情况和四类工作对聘用公务员的具体条件的希望达到 的要求都向所有应聘人员公布．

38 38 2016年8月19日 2016年8月19日 2016年8月19日 1 、问题的提出 每一位参加面试人员都可以申报两个自己的工 作类别志愿． 研究下列问题： （ 1 ）如果不考虑应聘人员的意愿，择优按需录 用，试帮助招聘领导小组设计一种录用分配方案； （ 2 ）在考虑应聘人员意愿和用人部门的希望要 求的情况下，请你帮助招聘领导小组设计一种分配 方案； （ 3 ）你的方法对于一般情况，即 N 个应聘人员 M 个用人单位时，是否可行？

39 39 2016年8月19日 2016年8月19日 2016年8月19日 2 、问题的分析 问题（１）：在不考虑应聘人员的个人意愿的情况 下，择优按需录用８名公务员． “ 择优 ” 就是综合考虑所有应聘者的初试和复试的成 绩来选优； “ 按需 ” 就是根据用人部门的需求，即各用 人部门对应聘人员的要求和评价来选择录用． 这里复试成绩没有明确给定具体分数，仅仅是专 家组给出的主观评价分。首先应根据专家组的评价给 出一个复试分数，然后，综合考虑初试、复试分数和 用人部门的评价来确定录取名单，并按需分配给各用 人部门．

40 40 2016年8月19日 2016年8月19日 2016年8月19日 2 、问题的分析 问题（２）：在充分考虑应聘人员的个人意愿的 情况下，择优录用８名公务员，并按需求分配给７ 个用人部门． 公务员和用人部门的基本情况都是透明的，在 双方都是相互了解的前提下为双方做出选择方案． 每一个部门对所需人才都一个期望要求，即可 以认为每一个部门对每一个要聘用的公务员都有一 个实际的 “ 满意度 ” ；每一个公务员根据自己意愿对 各部门也都有一个期望 “ 满意度 ” ，由此根据双方的 “ 满意度 ” ，来选取使双方 “ 满意度 ” 最大的录用分配方 案．

41 3 、模型的建立与求解 问题为 求下面 的整数 0-1 规划 问题的 解： 41 2016年8月19日 2016年8月19日 2016年8月19日

42 42 2016年8月19日 2016年8月19日 2016年8月19日

43 43 2016年8月19日 2016年8月19日 2016年8月19日

44 44 2016年8月19日 2016年8月19日 2016年8月19日

45