数学建模方法及其应用教学片课件

数学建模方法及其应用韩中庚编著数学建模方法及其应用韩中庚编著数学建模教学片第十一章整数规划方法设计制作：数学建模教学片第十一章整数规划方法设计制作：2主要内容

第十一章整数规划方法32022年11月23日整数规划的一般模型；整数规划解的求解方法；整数规划的软件求解方法；

0-1规划的模型与求解方法；整数规划的应用案例分析。主要内容第十一章整数规划方法32022年11月22日

一、整数规划的一般模型42022年11月23日1.问题的提出:固定资源分配问题一、整数规划的一般模型42022年11月22日52022年11月23日

固定资源分配问题52022年11月22日固定资源分配问题62022年11月23日2.整数规划模型的一般形式

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

二、整数规划求解方法松弛问题(A)中的约束条件,使构成易于求解的新问题---松弛问题(B)；如果问题(B)的最优解是原问题(A)的可行解,则就是原问题(A)的最优解；否则,在保证不改变松弛问题(B)的可行解的条件下,修正松弛问题(B)的可行域(增加新的约束),得到新问题(C)，再求问题（C)的解.

重复这一过程直到修正问题的最优解在原问题(A)的可行域内为止,即得到了原问题的最优解。72022年11月22日1.整数规划求解的总基82022年11月23日1.整数规划求解的总基本思想

二、整数规划求解方法82022年11月22日1.整数规划求解的总基92022年11月23日（1）分枝定界法的思想

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

（2）分枝定界法一般步骤

2、整数规划的分枝定界法

问题(B)无可行解，则(A)也无可行解，停止；102022年11月22日（2）分枝定界法一般112022年11月23日

（2）分枝定界法一般步骤

2、整数规划的分枝定界法112022年11月22日（2）分枝定界法一般122022年11月23日

（2）分枝定界法一般步骤

2、整数规划的分枝定界法122022年11月22日（2）分枝定界法一般132022年11月23日

（2）分枝定界法一般步骤

2、整数规划的分枝定界法132022年11月22日（2）分枝定界法一般142022年11月23日

（1）割平面法的思想

3、整数规划的割平面法

将原整数规划问题(A)去掉整数约束变为线性规划问题(B)，引入线性约束条件(称为Gomory约束，几何术语割平面)使问题(B)的可行域逐步缩小.

每次切割掉的是问题非整数解的一部分，不切掉任何整数解，直到最后使目标函数达到最优的整数解成为可行域的一个顶点时，即问题最优解。利用线性规划的求解方法逐步缩小可行域，最后找到整数规划的最优解。142022年11月22日（1）割平面法的思想152022年11月23日

（2）割平面法的一般步骤

3、整数规划的割平面法152022年11月22日（2）割平面法的一般（2）割平面法的一般步骤162022年11月23日（2）割平面法的一般步骤162022年11月22日172022年11月23日（2）割平面法的一般步骤这就是所要求的切割方程（Gomory约束条件）。172022年11月22日（2）割平面法的一般步骤这就是所182022年11月23日（2）割平面法的一般步骤5）应用单纯形法求解，直到最优解为整数解为止，否则继续构造Gomory约束条件。182022年11月22日（2）割平面法的一般步骤5）应用

3、整数规划的LINGO解法二、整数规划的求解方法192022年11月23日3、整数规划的LINGO解法二、整数规划的求解方法1202022年11月23日

1、0-1整数规划的模型三、0-1整数规划202022年11月22日1、0-1整数规划的模型三212022年11月23日

2、指派（或分配）问题三、0-1整数规划

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

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

匈牙利算法的基本思想

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

用LINGO求解0-1规划模型4、0-1规划的LINGO解法292022年11月22日用LINGO求解0-1规302022年11月23日四、案例分析:兼职值班员问题

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

1.问题的提出312022年11月22日实验室开放时间为上午8:00至晚上322022年11月23日四、案例分析:兼职值班员问题

2.模型的建立与求解322022年11月22日四、案例分析:兼职值班员问题2、模型的建立与求解332022年11月23日问题的数学模型：2、模型的建立与求解332022年11月22日问题的数学模型342022年11月23日3、模型的求解结果342022年11月22日3、模型的求解结果352022年11月23日3、模型的求解结果352022年11月22日3、模型的求解结果362022年11月23日五、案例分析:招聘公务员问题现有某市直属单位因工作需要，拟向社会公开招聘8名公务员，具体的招聘办法和程序如下：

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

1、问题的提出362022年11月22日五、案例分析:招聘公务员问题372022年11月23日五、案例分析:招聘公务员问题

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

1、问题的提出

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

2、问题的分析

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

2、问题的分析

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

3、模型的建立与求解问题为求下面的整数0-1规划问题的解：412022年11月23日五、案例分析:招聘公务员问题3、模型的建立与求解问题3、模型的建立与求解422022年11月23日3、模型的建立与求解422022年11月22日3、模型的建立与求解432022年11月23日3、模型的建立与求解432022年11月22日3、模型的建立与求解442022年11月23日3、模型的建立与求解442022年11月22日谢谢你的使用！设计制作：谢谢你的使用！设计制作：数学建模方法及其应用韩中庚编著数学建模方法及其应用韩中庚编著数学建模教学片第十一章整数规划方法设计制作：数学建模教学片第十一章整数规划方法设计制作：47主要内容

第十一章整数规划方法482022年11月23日整数规划的一般模型；整数规划解的求解方法；整数规划的软件求解方法；

0-1规划的模型与求解方法；整数规划的应用案例分析。主要内容第十一章整数规划方法32022年11月22日

一、整数规划的一般模型492022年11月23日1.问题的提出:固定资源分配问题一、整数规划的一般模型42022年11月22日502022年11月23日

固定资源分配问题52022年11月22日固定资源分配问题512022年11月23日2.整数规划模型的一般形式

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

二、整数规划求解方法松弛问题(A)中的约束条件,使构成易于求解的新问题---松弛问题(B)；如果问题(B)的最优解是原问题(A)的可行解,则就是原问题(A)的最优解；否则,在保证不改变松弛问题(B)的可行解的条件下,修正松弛问题(B)的可行域(增加新的约束),得到新问题(C)，再求问题（C)的解.

重复这一过程直到修正问题的最优解在原问题(A)的可行域内为止,即得到了原问题的最优解。72022年11月22日1.整数规划求解的总基532022年11月23日1.整数规划求解的总基本思想

二、整数规划求解方法82022年11月22日1.整数规划求解的总基542022年11月23日（1）分枝定界法的思想

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

（2）分枝定界法一般步骤

2、整数规划的分枝定界法

问题(B)无可行解，则(A)也无可行解，停止；102022年11月22日（2）分枝定界法一般562022年11月23日

（2）分枝定界法一般步骤

2、整数规划的分枝定界法112022年11月22日（2）分枝定界法一般572022年11月23日

（2）分枝定界法一般步骤

2、整数规划的分枝定界法122022年11月22日（2）分枝定界法一般582022年11月23日

（2）分枝定界法一般步骤

2、整数规划的分枝定界法132022年11月22日（2）分枝定界法一般592022年11月23日

（1）割平面法的思想

3、整数规划的割平面法

将原整数规划问题(A)去掉整数约束变为线性规划问题(B)，引入线性约束条件(称为Gomory约束，几何术语割平面)使问题(B)的可行域逐步缩小.

每次切割掉的是问题非整数解的一部分，不切掉任何整数解，直到最后使目标函数达到最优的整数解成为可行域的一个顶点时，即问题最优解。利用线性规划的求解方法逐步缩小可行域，最后找到整数规划的最优解。142022年11月22日（1）割平面法的思想602022年11月23日

（2）割平面法的一般步骤

3、整数规划的割平面法152022年11月22日（2）割平面法的一般（2）割平面法的一般步骤612022年11月23日（2）割平面法的一般步骤162022年11月22日622022年11月23日（2）割平面法的一般步骤这就是所要求的切割方程（Gomory约束条件）。172022年11月22日（2）割平面法的一般步骤这就是所632022年11月23日（2）割平面法的一般步骤5）应用单纯形法求解，直到最优解为整数解为止，否则继续构造Gomory约束条件。182022年11月22日（2）割平面法的一般步骤5）应用

3、整数规划的LINGO解法二、整数规划的求解方法642022年11月23日3、整数规划的LINGO解法二、整数规划的求解方法1652022年11月23日

1、0-1整数规划的模型三、0-1整数规划202022年11月22日1、0-1整数规划的模型三662022年11月23日

2、指派（或分配）问题三、0-1整数规划

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

现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人的能力和经验不同，所需完成各项任务的时间如右表：问如何分配何人去完成何项目使完成4项任务所需总时间最少？2.指派（或分配）问题222022年11月22日现682022年11月23日2.指派（或分配）问题232022年11月22日2.指派（或分配）问题692022年11月23日2.指派（或分配）问题242022年11月22日2.指派（或分配）问题702022年11月23日2.指派（或分配）问题252022年11月22日2.指派（或分配）问题712022年11月23日2.指派（或分配）问题指派问题的一般模型：262022年11月22日2.指派（或分配）问题指派问题的722022年11月23日2.指派（或分配）问题指派问题的一般模型：272022年11月22日2.指派（或分配）问题指派问题的732022年11月23日

匈牙利算法的基本思想

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

用LINGO求解0-1规划模型4、0-1规划的LINGO解法292022年11月22日用LINGO求解0-1规752022年11月23日四、案例分析:兼职值班员问题

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

1.问题的提出312022年11月22日实验室开放时间为上午8:00至晚上772022年11月23日四、案例分析:兼职值班员问题

2.模型的建立与求解322022年11月22日四、案例分析:兼职值班员问题2、模型的建立与求解782022年11月23日问题的数学模型：2、模型的建立与求解332022年11月22日问题的数学模型792022年11月23日3、模型的求解结果342022年11月22日3、模型的求解结果802022年11月23日3、模型的求解结果352022年11月22日3、模型的求解结果812022年11月23日五、案例分析:招聘公务员问题现有某市直属单位因工作需要，拟向社会公开招聘8名公务员，具体的招聘办法和程序如下：

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

1、问题的提出362022年11月22日五、案例分析:招聘公务员问题822022年11月23日五、案例分析:招聘公务员问题

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