基于某0-1整数规划地就业选择模型

实用文案

2012高教社杯全国大学生数学建模竞赛

承诺书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他

公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正

文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反

竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：

我们的参赛报名号为（如果赛区设置报名号的话）：

所属学校（请填写完整的全名）：

参赛队员 (打印并签名) ：1. 孔甜程

2. 王成

3. 刘子恒

指导教师或指导教师组负责人 (打印并签名)：

日期： 2012 年 8月 15 日

赛区评阅编号（由赛区组委会评阅前进行编号）：

2012高教社杯全国大学生数学建模竞赛

编号专用页

赛区评阅编号（由赛区组委会评阅前进行编号）：

全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：

基于0-1整数规划的就业选择模型

摘要：当今社会，大学生就业问题已引起了广大的关注，针对这一现象，假设有25个用人单位和25位应聘者，每个人及每个单位的基本条件和要求条件各不相同，某高等院校学生就业指导中心就如何根据用人单位和大学生的基本条件和要求条件进行牵线搭桥，使用人单位和大学生签订就业协议。

本文利用0-1型整数规划建立了大学生就业问题的数学模型，并结合实际提出了通用可行的算法。首先将用人单位的五个要求条件和应聘者的五个要求条件等级A、B、C、D、E分别做量化处理为5、4、3、2、1，得到用人单位和应聘者的基本条件量化矩阵和要求条件量化矩阵，得出满意度分量。然后确定最优方案模型，被选人员对用人单位的满意度最大时的人员选取即为所求，从而建立了应聘人员最优选取的0-1整数规划模型

关键词：0-1整数规划条件量化满意度

1问题重述

目前，随着我国高等教育的持续发展，大学生毕业人数逐年增多，大学生就业难问题已经引起了社会各方的广泛关注。一方面，大量大学生毕业后不能很快找到工作，实现就业；一方面，用人单位也苦于不能招收到适合的人才。这种现象的持续，严重影响到我国高等教育和国民经济的持续发展。

本题要求根据所给原始数据，解答以下五个问题：

问题一:在尽量满足双方各自要求的条件下，给出一种最佳的配对方案，并使得配对成功率尽可能高；

问题二：给出一种25个用人单位和25位应聘者可同时配对的最佳方案，使得全部配对成功的可能性最大；

问题三:如果25个用人单位和25位应聘者都相互了解对方的条件和要求，让每个用人单位和每位应聘者都可以做出一次选择，只有当双方都选中对方时才能够配对成功，每方只有一次选择机会。请问25个用人单位和25位应聘者应该如何选择，使得自己配对的可能性最大？按你的选择方案最多能配对成功多少对？

问题四：由于用人单位工作要求的限制，如用人单位5和用人单位13只招聘男生，用人单位9和用人单位20只招聘女生会对你上面的结论产生怎样的影响？

问题五：你的方法对一般的情况，即N个应聘人员M个用人单位时，是否可行？

2 模型假设

(1)每位应聘者只能被一个用人单位录取，一个单位只能录取一个一个人；（2）题目所给出的条件的评价是客观真实的；

（3）用人单位和应聘者的相关数据是透明的，即双方都知道；

（4）应聘者的基本要求在综合评价中的地位是等价的；

（5）用人单位的五项基本要求对应聘者的影响地位是同等的；

（6）双方在选择的时候是理智的。

3 符号说明

4 问题分析

该问题是现实生活中的实际问题，主要就是确定合理配对方案，使得在尽量满足个人要求条件下，使配对成功率尽可能的高。

对于问题（1），在充分考虑用人单位和应聘者的要求条件的前提下，综合双方的满意度，尤其将双方的基本条件和要求条件有机结合而综合确定一个优化指标，建立起优化模型（或算法）,给出最优的配对问题。

对于问题（2），要是25个用人单位和25位应聘者同时配对，使得全部同时成功的可能性（概率）最大。

对于问题(3),因为每个人只有选择一次，能不能配对成功取决于双方是不是同时选中对方，即要看双方彼此的满意度如何。实际上，假如一个用人单位(125)i p i ≤≤对一个应聘者(125)i q i ≤≤的满意度最高，

但是i q 对i p 的满意度不一定最高，即若i p 选择i q ，但i q 不一定选择i p 。因此i p 与i p 不一定配对成功，反之亦然。现在的问题是谁选谁，使得配对成功的可能性最大呢？

对于问题(4),要基于前面三个方案来看，可对应每个方案中这四个用人单位最优配对中其配对对象的性别讨论前面的最优方案是否受到影响。若和这几个用人单位的工作要求限制符合，则对整个方案而言，不会造成影响；若不符合，则需先考虑用人单位的工作要求。寻求他们的最优方案，将余下的用人单位和应聘者如上如上三问那样建立模型，并求解。

对于问题（5），只有把上述模型推广到N 个应聘者M 个用人单位时情况。在建模时，其模型与前述问题的模型一致，只需将i 的取值推广到M ，j 的值推广到N 即可。

5 模型建立与求解

5.1 问题一的模型建立与求解

针对问题一要使配对成功率尽可能的高，也就是给出一种方案，使得25个用人单位和25位应聘者的配对成功指数之和最高。

5.1.1 模型准备

5.1.1.1 条件量化处理

对于每位应聘者对用人单位的工资待遇、工作条件、劳动强度、晋升机会、深造机会的五个要求条件和每个用人单位对应聘者的基本知识面、专业知识面、动手能力、计算机能力、表达能力的五个要求条件等级A 、B 、C 、D 、E 分别作量化处理为5、4、3、2、1.于是根据上表可以得到用人单位和应聘者的基本条件量化矩阵和要求条件量化矩阵以及满意度分量分别记为：

'()205,'()205,

'()205,'()20 5.ik ik jk jk A a B b C c D d =?=???

=?=?? 0,1,,jk ik k

ij

ik

jk jk ik c b S c b c b

ji ik

jk ik jk a d T a d a d ?

则12345(,,,,)ij ij ij ij ij ij S S S S S S =， 12345(,,,,)ij ij ij ij ij ij T T T T T T =

最后，用人单位对应聘者的综合满意度为

12345()5ij ij ij ij ij ij S S S S S S =++++÷

应聘者对用人单位的综合满意度为

12345()5ij ij ij ij ij ij T T T T T T =++++÷

则用人单位与应聘者之间的综合满意度为

,ij ij ij F S T =+ 5.1.2

模型建立

在充分考虑应聘人员的意愿和用人单位期望要求的情况下，寻求更好的录用分配方案。应聘人员的意愿包括对用人单位的工资待遇、劳动强度等五个要求条件，即可用应聘人员对用人单位的综合满意度来表示，用人单位对应聘者的期望要求也用综合满意度来表示。一个好的录用方案就是使二者的满意度都尽可能的高，故就是要求两者之间的综合满意度之和最大，可以建立如下优化模型：

目标函数：25

25

11max ij ij i j z F x ===∑∑

约束条件:25

125

1

1,1,2,...,25,1,1,2,...,25,01(,1,2,...,25),ij i ij j ij x j x j x or i j ==?==???==???==??

∑∑

5.1.3 模型求解

根据上述建立的模型中，可以看出这是一个0-1整数规划问题，在求解过程中，我们用lingo 软件寻求其最优配对方案，并得出其最优解为23.6z =。

方案如下:

配对成功率最高方案

用人单位 P1 P2 P3 P4 P5 P6 P7 P8 P10 应聘人员 Q8 Q17 Q20 Q12 Q11 Q23 Q18 Q19 Q15 满意度 1.6 0.2 1 1.6 1.6 1 1.6 1.2 0.2 用人单位 P11 P12 P13 P14 P15 P16 P17 P18 P19 应聘人员 Q21 Q3 Q7 Q2 Q13 Q22 Q28 Q4 Q10 满意度 1 0.8 1 1.6 0.8 0.2 0.6 0.8 0.8 用人单位 P20 P21 P22 P24 P25 应聘人员 Q6 Q16 Q5 Q18 Q9 满意度 1.2 1.6 0.8 1.8 0.6

表一

5.2 问题二的模型建立与求解

针对问题二求解得出的匹配方案应使25个用人单位与25位应聘者全部配对成功，且配对的成功率之和最大。

5.2.1 模型建立

要使25个用人单位与25位应聘者同时配对且配对成功率尽可能高，记25个用人单位与25位应聘者成功配对概率为,ij i j

P P =∏

则目标函数为：

,max ij i j

p p =∏

由于，ij p 正比于ij F ，所以目标函数等价于

2525

1

1

max ij ij i j p T x ===∏∏

令ln()ij ij C F =，则

2525

11

max ij ij i j P C x ===∑∑，

约束条件:25

125

1

1,1,2,...,25,1,1,2,...,25,01(,1,2,...,25),ij i ij j ij x j x j x or i j ==?==???==???==??

∑∑：

5.2.2 模型求解

在求解过程中，应聘人员与用人单位的综合满意度有为0的情况，但是在求解全部配对成功的概率最大的情况时，利用对数函数求解过程中，0不能求出来，得出负无穷大的情况，为了方便计算，我们把负无穷换为-10000。

至于求解过程，与问题一的方法一致。我们利用lingo 软件计算出其最优配对方案，并得出其最优解z=-3.9。（注意：其最优解并不是所求概率，只是其变化趋势与概率等价，当Z 最大时，其概率就最大。）

方案如下：

全部配对成功的概率最大方案

用人单位 P1 P2 P3 P4 P5 P6 P7 P8 P9 应聘人员 Q19 Q14 Q10 Q23 Q5 Q21 Q1 Q9 Q12 满意度 1 0.3 0.8 1 0.8 1 0.8 1 0.6 用人单位 P10 P11 P12 P13 P14 P15 P16 P17 P18 应聘人员 Q11 Q24 Q7 Q18 Q25 Q3 Q6 Q16 Q4 满意度 0.8 1 1 1 0.8 1 0.6 0.8 0.8 用人单位 P19 P20 P21 P22 P23 P24 P25 应聘人员 Q22 Q2 Q13 Q20 Q8 Q17 Q15 满意度 0.8 1 1.2 1 0.4 1 0.8

表二

5.3 模型改进

首先要注意两个事实：其一，如果i A 基本条件ik a 比j C 的要求条件ik d 差很多的话，则i A 对j C 的第K 项条件的满意度ij T 就越小，反之亦然。也就是说，如果

一方的实际条件比对方期望的条件差距越大，则对方对另一方失望就越大，即满意度就越小。其二，如果i A 的基本条件ik a 比j C 的要求条件j C 高，则j C 对i A 的第K 项条件的满意

度ij T 就会增加，但不会增加很多。即当一方的实际条件高于对方期望的条件是，则对方对

另一方的满意度增加不会太大。也就是说，人们对不满意程度的敏感远远大于对满意程度的

敏感，即用人部门对应聘者的满意程度降低一级可能导致用人单位的极大不满，但满意度增加一级只能引起满意程度的少量。为此现在在模型一的基础上把满意度稍加修改。如果i A （j C ）基本条件ik a （ij c ）达不到j B （j D ）的要求ik b (ik d )，即ij c ≤ik b （ik jk a d <）

时，给它赋值ij c ≤ik b （ik jk a d <）它是一个负值，体现了当一方实际条件低于期望的条件是，则对方对他失望（相当于要求条件）就会增加差距越大，失望度就越大，相应的满意度就越小。显然改进后成功的解决了上述所提的问题，所以更加合理。

满意度矩阵中的各个分量分别表示如下：

,1,,ik ik jk ik

k

ij

ik ik

jk ik c b c b S c b c b -?

,1,ik jk ik jk

k ij ik

jk ik jk a d a d T a d a d -?

至于模型的求解与优化与模型一类似，我们通过原始数据得出满意度，然

后编程求的结果：

方案如下:

配对成功率最高方案

用人单位 P1 P2 P3 P4 P5 P6 P7 P8 P9 应聘人员 Q14 Q6 Q22 Q13 Q5 Q23 Q9 Q4 Q12 满意度 1.6 0.8 0.8 0.8 0.8 1 1 1.6 0.6 用人单位 P10 P11 P12 P13 P14 P15 P16 P17 P18 应聘人员 Q2 Q21 Q24 Q18 Q25 Q20 Q16 Q7 Q19 满意度 0.4 1 0.8 1 0.8 1 0.4 0.8 0.4 用人单位 P19 P20 P21 P22 P23 P24 P25 应聘人员 Q3 Q10 Q8 Q15 Q11 Q1 Q17 满意度 1 0.6 1.8 0.8 0.4 0.8 0.6

表三

5.4 模型比较

在模型一中，我们忽略了用人单位对应聘者综合满意度的负值及应聘者对用人单位综合满意度的负值，也就是说在模型一中，我们认为满意度及不满意度（满意度为负值时）对配对成功率的影响是一样的，但在实际情况中，人们对不满意度的敏感度比满意度的敏感度高的多，于是在模型改进中，我们对双方的满意度定义加以修正。根据得出的结论可知，模型改进后的得到的配对方式更优。

5.5 问题三的模型建立与求解

针对问题三，由于每个人只能选择一次，能否配对成功主要取决于双方能否同时选中对方，则需从双方彼此的满意度来看。要使配对率最高，则要使双方

的相互满意度达到最大。

5.5.1 模型建立

用人单位i P 与应聘者j Q 的相互满意度定义为 当i P 与 j Q 满足可能配对的条件时：

ij G =当i P 与j Q 不满足可能配对的条件时：

0ij G =

配对成功率达到最大取决于双方的相互满意度之和达到最大值。于是根据0-1整数规划模型，得出目标函数为

2525

11

max ij ij i j z G x ===∑∑,

其约束条件与问题一相同，即为

25

125

1

1,1,2,...,25,1,1,2, (25)

01(,1,2,...,25),ij i ij j ij x j x j x or i j ==?==???==???==??∑∑

5.5.2 模型求解

根据上述模型，编程可以得到最优解为Z=11.57，其配对方案如下:

配对方案

用人单位 P1 P2 P3 P4 P5 P6 P7 P8 P11 应聘人员 Q22 Q23 Q19 Q12 Q18 Q13 Q15 Q24 Q14 满意度 0.49 0.2 0.4 0.8 0.6 0.4 0.57 0.7 0.7 用人单位 P12 P13 P14 P15 P17 P18 P19 P20 P21 应聘人员 Q7 Q8 Q21 Q5 Q16 Q2 Q10 Q11 Q3 满意度 0.49 0.57 0.7 0.4 0.4 0.4 0.4 0.7 0.7

用人单位 P22 P24 P25 应聘人员 Q6 Q20 Q4 满意度 0.7 0.7 0.6

表四

5.5.3 模型改进

由于只能选择一次，要使成功率尽可能的大，则不能单纯的只考虑自己对对方的满意度。因为在实际中，一个用人单位i 对一位应聘者j 的满意度高，但不代表这位应聘者对该用人单位的满意度高，即i P 选择了

j

Q ，但

j

Q 不一定选择i P ，

于是两人不一定配对成功。因此，要使每一个个体配对成功的可能性最大，要保证双方的满意度差值不能太大。

所以我们定义了双方满意度差值的绝对值为差异指数，那么双方满意度差异指数为：ij K =ij ij S T -

要使其配对成功率最高，则要使双方满意度差异指数最小，故根据上述分析，利用0-1整数规划模型，得出目标函数：

2525

11

min ij ij i j z K x ===∑∑，

约束条件如下;

25

125

1

1,1,2,...,25,1,1,2,...,25,01(,1,2,...,25),ij i ij j ij x j x j x or i j ==?==???==???==??

∑∑ 5.5.4 模型求解

根据模型，我们得出最优解Z=2.00，其最佳配对方式如下：

配对方案

用人单位 P1 P5 P6 P7 P8 P12 P14 P22 应聘人员 Q7 Q21 Q23 Q8 Q20 Q4 Q3 Q24 满意度 0.2 0.2 0.2 0.6 0.2 0.2 0.2 0.2

表五

5.5.5 模型比较

在问题三中，模型一我们定义了相互满意度，相互满意度等于用人单位对应聘者的满意度与应聘者对用人单位的满意度的几何算术平均数，在实际情况中，如果一方的满意度过高，另一方的满意度偏低，两者相差太大，但是由于前者的满意度过高，使得相互满意度还是有点高，那样得出的结论可能会与实际情况有偏差。于是我们在模型改进中，又定义了满意度差异指数，要使配对成功率尽可能高，则要求满意度差异指数之和最小，这样得出的配对方案更具可取性，并且得出的结论更符合实际情况。

5.6 问题四的模型建立与求解

针对问题四，我们只需将工作要求也作为过滤条件，在已知的方案中对配对进行筛选，使得在满足工作条件的情况下，配对尽可能成功。

由于用人单位的工作要求的限制，用人单位招收有男女限制。这样对于用人单位5,13,9,20,的要求条件就多了一项，其他的不变。首先我们根据用人单位的用人限制，再对照前面已求的方案对照，如果已有的配对方案与用人单位的要求不冲突，那么我们就不用在进行优化，通过比较，发现已有方案不符合用人单位的要求，则我们用条件过滤的方法首先对特殊用人单位进行筛选。

5.6.1 模型建立

对于工作单位的性别要求，针对问题一，我们在进行条件筛选时，只需在模型一的基础上强化约束条件。

目标函数：2525

11

max ij ij i j z F x ===∑∑

其约束条件:25

1

25

15139201,1,2,...,25,1,1,2,...,25,0,1,2,3,9,10,11,12,13,21,22,23,240,0,4,5,6,7,8,14,15,16,17,18,19,20,250,ij i ij j m m n n x j x j x m x x n x ==?

==?

?

?

==?

?

?==??=?

==??=?

∑∑

5.6.2 模型求解

根据lingo 软件求的Z=23.6，其配对方式如下：

配对成功率最高方案

用人单位 P1 P2 P3 P4 P5 P6 P7 P8 P10 应聘人员 Q6 Q17 Q13 Q15 Q21 Q11 Q8 Q7 Q22 满意度 1.6 0.2 0.8 0.8 1 1.6 1.8 1.6 0.2 用人单位 P11 P12 P13 P14 P15 P17 P18 P19 P20 应聘人员 Q5 Q24 Q20 Q4 Q23 Q19 Q18 Q12 Q14 满意度 0.8 0.8 0.8 1.6 1

0.4

0.8

1.6

1.2

用人单位 P21 P22 P24 P25 应聘人员 Q16 Q10 Q2 Q3 满意度

1.6

0.8

1.6

1

表六

对于问题二和问题三的求解方法也问题一类似，只需在约束条件方面加

强。

问题二的配对方式：Z= 4.1-，

全部配对成功的概率最大方案

用人单位 P1 P2 P3 P4 P5 P6 P7 P8 P9 应聘人员 Q22 Q6 Q13 Q3 Q20 Q24 Q25 Q9 Q14 满意度 1 0.8 0.8 1 1 1 0.8 1 0.4 用人单位 P11 P12 P13 P14 P15 P16 P17 P18 P19 应聘人员 Q19 Q2 Q16 Q15 Q23 Q12 Q7 Q4 Q10 满意度 0.8 1 1 1.2 1 0.8 0.8

0.8

0.8

用人单位 P20 P21 P22 P23 P24 P25 应聘人员 Q18 Q1 Q21 Q8 Q17 Q5 满意度

1

0.8

1

0.4

1

0.8

表七

根据上表，可得由于用人单位的条件限制，不可能全部配对成功，用人

单位10未找到合适的应聘人员，应聘人员11未找到合适的工作。

问题三的配对方式：

配对方案

用人单位 P1 P8 P11 P16 P17 P20 P21 P25 应聘人员 Q7 Q8 Q21 Q3 Q6 Q16 Q24 Q23 满意度 0.2 0.6 0.2 0.2 0.2 0.2 0.2 0.2

表八

5.7 问题五的求解

对于N 个应聘人员和M 个用人单位的情况，如上的方法都实用，只是两个优化模型的规模会变大，给求解带来一定的困难。实际中，用人单位个数M 不会太大，当应聘人员的个数N 达到一定的程度时，可以分步处理。

对于问题一而言，取所有应聘人员综合满意度与用人单位的综合满意度

的均值，即可得

11

,

1M N

ij j i F F

N M

===

+∑∑，

对于满足F F <应聘人员应该淘汰掉，将剩下的应聘人员编号，在用上

述的方法求解，确定录用分配方案。如果剩下的人员仍然很多，则可以用类似的方法做进一步择优。对于问题二和问题三的处理方式类似，只是根据的是双方的相互满意度。

6 模型评价

优点：

（1）将用人单位与应聘者的条件等级量化，将实际问题转化为数学问

题。

（2 ）改进后的模型在考虑满意度方面更加全面。

（3）该模型的建立，为公司雇佣员工提出了可行性建议，使公司的效

益最大化。

（4）所建的模型具有普遍性。实际生活中还有很多类似的配对问题。缺点：

（1）在实际生活中，每位应聘者的要求条件与基本条件及每个用人单

为的基本条件和要求并不只包括题中所给的这几个方面，实际情况也

不能简单量化为1、2、3、4、5。

（2）在实际情况中，用人单位在选择应聘人员时的侧重点会不同，有

的注重动手能力，有的注重表达能力等。而我们在建立模型时，只是

简单的将五个方面的等级分别赋值，不能体现其侧重点。

7 模型推广

该模型可以推广到实际生活中的配对问题，例如婚配问题、交友网站、下岗职工再就业等问题。例如，交友网站就可以运用该模型，根据用户自身的资料填写对对方的要求，根据“我的条件——TA对我的要求”和“我对TA的要求——TA 的条件”这样的关系进行条件项的匹配。这是一种比较传统的匹配。在进行交友方面的匹配时，则根据用户的兴趣爱好来进行匹配，用户可以输入：杭州周末登山。这一系列的匹配关键字，可以匹配到同样有这方面爱好的朋友。

8 参考文献

[1] 韩中庚.数学建模方法及其应用[M].北京:高等教育出版社，2005.5.

[2] 谢季坚. 模糊数学方法及其应用[M]. 华中科技大学出版社，2006.

[3] 程冬时等. 关于求解0-1型整数规划的若干问题[J]. 江西电力职业技术学

院学报,2006(19).

[4] 韩中庚.招聘公务员问题的优化模型与评述,河南,工程数学报，2004年12

月

随机规划

第二讲 随机规划 第一节 基本概念 1、 问题的提出 许多实际决策问题，尤其是比较复杂的决策问题，可以建 立如下的线性规划模型： {}????? ??????≥=+++=+++=++++++.0,...,,............min 11221122222121112121112211n m n mn m m n n n n n n x x x b x a x a x a b x a x a x a b x a x a x a to subject x c x c x c M M （1.1） 用矩阵向量分析法，简化问题（1.1）得： ?? ???≥=0..min x b Ax t s x c T （1.2） 线性规划模型，在工业生产、运输业、农业、能源、生态、工程等领域都有广泛（典型）的应用。 在问题（1.1）中系数j c （例如价格因素）、ij a （比如生产率）、j b （比如需求量或存储能力）假设都已知为实数，这样我们的任务就是：寻找满足约束条件的决策变量j x （比如投入因素、生产率水平、能源 流），使这一组合达到最优。显然，在现实生活中，如果相关的函数（例如，费用函数或生产函数）关于决策变量是线性的，那么模型（1.1）就能够合理的描述现实生活中的问题。如果现实中不是这样

的，比如，因为产品的边际成本（边际成本指的是每一单位新增生产的产品（或者购买的产品）带来到总成本的增量）的增长或边际报酬的减少，我们就需要更一般的形式来建立问题的模型，如下： ?? ??? ?∈=≤.,...,1,0)(..)(min 0n i IR X x m i x g t s x g （1.3） 形式如（1.3）的问题就是一个数学规划问题。 这里的集合X 以及函数m i IR IR g n i ,...,0,:=→可以理解为是在建模过程中给出的。 在许多模型建立过程中（如问题(1.1)和(1.3)），若系数i ij j b a c ,,或 函数i g （和集合X ）分别为给定值，这是不合理的。比如说，在水电 发电站，流入发电站蓄水池的流水量，及运输网络中各个节点的需求量等等的因素，在建模的过程中，通常都作为不确定的参数。在一个生产问题中，未来的生产率，用概率分布来描述是最好的。但在建模过程中，这些参数真实值的不确定性，并不能用他们的平均值或别的估计值来消除（即真实值与平均值/估计值存在偏差）。就是说，在考虑实际情况的时候，问题（1.1）、（1.3）的模型，可能并不适合来解决更实际的问题。在这一章我们着重并尽可能的阐明，对于实际生活中的决策问题，需要扩大建模范围的必要性。 在数学规划中引入随机性是很自然的事情。在模型中的系数i ij j b a c ,,常常代表价格、成本、需求量、资源数量、经济指标等参数。 由于各种不确定性因素的影响，这些参数经常出现波动。例如，市场

整数规划的两种数学模型解法

规划模型求解 指导老师： 组员： 组员分工 实际的内容： 1·简要介绍线性规划的历史 线性规划是运筹学中最基本、应用最广泛的分支。规划模型是一类有着广泛应用的确定性的系统优化模型，1939年，苏联数学家康托洛维奇出版《生产组织和计划中的数学方法》一书. 1947年，美国数学家丹兹格提出了线性规划问题的单纯形求解方法. 1951年，美国经济学家库普曼斯（J.C.Koopmans,1910—1985）出版《生产与配置的活动分析》一书. 1950～1956年，线性规划的对偶理论出现. 1960年，丹兹格与沃尔夫（P.Wolfe）建立大规模线性规划问题的分解算法. 1975年，康托洛维奇与库普曼斯因“最优资源配置理论的贡献”荣获诺贝尔经济学奖. 1978年，苏联数学家哈奇扬（L.G.Khachian）提出求解线性规划问题的多项式时间算法（内点算法），具有重要理论意义. 1984年，在美国贝尔实验室工作的印度裔数学家卡玛卡（N.Karmarkar）提出可以有效求解实际线性规划问题的多项式时间算法——Karmarkar算法.

线性规划的基本点就是在满足一定约束条件下，使预定的目标达到最优. 现在线性规划已不仅仅是一种数学理论和方法，而且成了现代化管理的重要手段，是帮助管理者与经营者做出科学决策的一个有效的数学技术. 历史表明，重要数学概念对数学发展的作用是不可估量的，函数概念对数学发展的影响，可以说是贯穿古今、旷日持久、作用非凡，回顾函数概念的历史发展，看一看 函数概念不断被精炼、深化、丰富的历史过程，是一件十分有益的事情，它不仅有助于我们提高对函数概念来龙去脉认识的清晰度，而且更能帮助我们领悟数学概念 对数学发展，数学学习的巨大作用。 2·线性规划的原理：线性规划是合理利用、调配资源 的一种应用数学方法。它的基本思路就是在满足一定的约束条件下，使预定的目标达到最优。它的研究内容可归纳为两个方面：一是系统的任务已定，如何合理筹划，精细安排，用最少的资源(人力、物力和财力)去实现这个任务；二是资源的数量已定，如何合理利用、调配，使任务完成的最多。前者是求极小，后者是求极大。线性规划是在满足企业内、外部的条件下，实现管理目标和极值(极小值和极大值)问题，就是要以尽少的资源输入来实现更多的社会需要的产品的产出。因此，线性规划是辅助企业“转轨”、“变型”的十分有利的工具，它在辅助企业经营决策、计划优化等方面具有重要的作用。其一般形式为： n n n n n n b x a x a x a b x a x a x a x c x c x c x f =+++=+++→+++= 2 2222121112121112211min )(

第六章 随机规划

第六章 随机规划 第一节 问题的提出 随机规划所研究的对象是含有随机因素的数学规划问题。例如，我们熟悉的线性规划问题 CX X f =)(min 0≥=X b AX （6.1） 如果其中的A ，b ，C 的元素中部分的或全部的是随机变量，则称其为随机线性规划问题。 在数学规划中引入随机性是很自然的事情。在模型中的A ，b ，C 的元素常常代表价格、成本、需求量、资源数量、经济指标等参数。由于各种不确定性因素的影响，这些参数经常出现波动。例如，市场上对某种商品的需求量一般无法精确的预知，只能作出大致的预测，某种产品的生产成本往往受原材料价格、劳动生产率等各种因素的影响而经常变化，这些变化与波动，在许多场合可以用一定的概率分布去描述。因此，在数学规划中引入随机变量，能够使模型更加符合实际情况，从而是的决策更加合理。 例1 某化工厂生产过程中需要A ，B 两种化学成分，现有甲、乙两种原材料可供选用。其中原料甲中化学成分A 的单位含量为10/a ，B 的单位含量为3/a ；原料乙中化学成分A 的单位含量为10/1，B 的单位含量为3/1。根据生产要求，化学成分A 的总含量不得少于10/7个单位，化学成分A 的总含量不得少于3/4个单位。甲、乙两种原料的价格相同，问如何采购原料，使得即满足生产要求，又是的成本最低？ 显而易见，这个问题可以用线性规划模型来描述。根据题意，设原料甲的采购数量为1x ，原料乙的采购数量为2x ，容易得到如下线性模型： 21)(min x x X f += ,047 212121≥≥≥+≥+x x x bx x ax （6.2）

于是只要知道a 和b 的值，立即可以求得最优解。 但是，如果由于某种原因，原料甲中化学成分A 、B 的单位含量不稳定，其中T b a ),(=ξ是矩形}13 1,41{≤≤≤≤y x 内的均匀分布随机向量，则问题（7.2）就成为随机线性规划问题了。 由于引入了随机量，随机规划问题的分析与求解比普通数学规划问题要复杂大多。在处理随机规划问题时，人们最容易想到的方法也许是将模型中的随机变量用它们的期望值来代，从而得到确定性的数学规划模型，再去求解。事实上，过去许多确定性数学规划正是这样建立起来的，但是应当指出，这种处理方法在实际问题中并不总可行的。为了说明这一点，我们不妨用此方法试解例1中的问题。容易求得 T T b a E E )3/2,2/5(]),[()(==ξ， （6.3） 将此值代入问题（7.2），得到确定线性规划模型如下： 21)(min x x X f += ,043 272 5212121≥≥≥+≥+x x x x x x （6.4） 可以求得此问题的唯一最优解为 T T x x X )11/32,11/18(),(*2*1*==， （6.5） 于是以此*X 作为原随机线性规划问题（7.2）的最优解。可是，由于问题（7.2）中的T b a ),(是随机向量，我们自然希望知道，上述*X 是问题（7.2）的最优解这一事件的概率有多大？是问题（7.2）的可行解这一事件的概率有多大？然而，我们发现， 4/1}3/2,2/5),{(} 4,7),{(*2*1*2*1=≥≥=≥+≥+b a b a P x bx x ax b a P T T ， （6.6） 也即，*X 对问题（7.2）是可行解以0.75的概率是不可能的，只有0.25的可能性，这个解显然是不可用的。这个例子说明，用上述方法处理随机规

(完整word版)整数规划的数学模型及解的特点

整数规划的数学模型及解的特点 整数规划IP (integer programming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。 松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。 若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。 一、整数线性规划数学模型的一般形式 ∑==n j j j x c Z 1 min)max(或 中部分或全部取整数n j n j i j ij x x x m j n i x b x a t s ,...,,...2,1,...,2,10 ),(.211 ==≥=≥≤∑= 整数线性规划问题可以分为以下几种类型 1、纯整数线性规划(pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。

2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。 3、0—1型整数线性规划(zero —one integer liner programming)：指决策变量只能取值0或1的整数线性规划。 1 解整数规划问题 0—1型整数规划 0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的 ???? ? ????≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z

01型整数规划模型

甲乙公司不合作即竞争下所争取到的不同名专业推广者所建立的不同动态规划模 型的组合方案如下：其中X 为可能竞争到的专业推广者人数，即动态规划模型中第一天的

专业推广者推 广能力的份数，Y 为第二天需要的专业推广者推广能力的份数，即第三天安排从事推广 工作的专业推广者的人数；Z 为第三天需要的专业推广者推广能力的份数，即第三天安排从事推广工作的专业推广者的人数；a 为x 名专业推广者累计从事培训工作出来的兼职推广者的批数（每批20 人），其中，有多种组合方案；甲公司雇佣这些兼职推广者均工作一天，从事推广工作，第二天辞退a ?b 批兼职推广员，其余的b 批继续从事推广工作一天后辞退，即兼职宣传员总共最多雇佣2 天；cost 为花费的成本，即资金的使用数量；F 为不同方案下所达到的总推广效益。上表可以提供给甲公司做决策依据，根据效益的大小甲公司可以决策的目标方向顺序是从①--⑧，即不合作的情况下甲公司可以尽量争取到9 人，如若 不行，考虑争取4 人。 §5.4 0—1型整数规划模型 1、 0—1型整数规划模型概述 整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。 0—1型整数规划的的数学模型为： 目标函数 n n x c x c x c z M i n M a x +++= 2211)( 约束条件为： ???? ?? ?==≥≤++=≥≤++=≥≤++1 | 0 ) ,() ,() ,(2211222221211 1212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,21 这里，0 | 1表示0或1。 2、0—1型整数规划模型的解法

基于随机提前期的库存模型的规划周期word参考模板

随机提前期库存模型的规划周期 摘要：相关的规划周期的文献都大量地致力于分析具有确定提前期的库存系统。我们证明了，在某种情况下，相关的规划周期理论也适用于具有随机提前期的情况。特别的，当生产需求被认为是不可替换的以及确定的，这时生产运作只能被设置成符合这种特殊要求的并且也只适合于满足这种要求的情况。当持有订单、退订单、下订单时，在可变生产成本不变，并且销售提前期不变的情况下，按照一系列连续的整体的生产要求进行生产时总是最优的策略。特定发货量的生产日期具有凸性性质。基于以上的结论，我们证明了一些规划周期理论。并给出了远期的动态规划递归方法。这些结论被归纳为基本动态订购数量模型。我们呈现了几个案例用以阐述最优策略对提前期变化的灵敏度。 对于动态订购数量问题的规划周期的探索具有远远超越计算存储方法的优势。在许多情况下，对于下一个最佳生产决策的判断是最重要的，因为这些事项常常需要定期得到解决以纳入改善后的信息。这将导致在有限时间内的周期问题的自然停止法则，并随后降低获取和探索信息的成本。Lundin和Morton二人近来集成了规划周期的相关文献，将它们作为一个整体进行研究。至目前为止，这项研究已经致力于分析具有确定提前期的库存系统。这篇文章的主要目的是证明在某些假设下一些周期规划的理论和概念也可以被归纳为随机提前期的情况。 Gross和Soriano以及Vinson的研究清楚地证明了提前期变动

对库存成本有重大影响。然而文献间也存在差异，部分是由于连续提前期和随机提前期对库存系统的影响的根本区别。当提前期是连续的，所有的订单都将按照事先设置的顺序先后到达。当提前期是独立的随机变量，

数学建模(整数规划)

整数规划模型

实际问题中 x x x x f z Max Min T n "),(),()(1==或的优化模型 m i x g t s i ",2,1,0)(..=≤x ~决策变量f (x )~目标函数g i (x )≤0~约束条件 多元函数决策变量个数n 和数 线性规划条件极值约束条件个数m 较大最优解在可行域学 规 非线性规划解 的边界上取得划 整数规划

Programming +Integer 所有变量都取整数，称为纯整数规划；有一部分取整数，称为混合整数规划；限制取0，1称为0‐1型整数规划。 型整数规划

+整数线性规划 max(min) n z c x =1j j j n =∑1 s.t. (,) 1,2,,ij j i j a x b i m =≤=≥=∑"12 ,,,0 () n x x x ≥"且为整数 或部分为整数

+例：假设有m 种不同的物品要装入航天飞机，它们的重量和体积分别为价值为w j 和v j ，价值为c j ，航天飞机的载重量和体积限制分别为W 和V ，如何装载使价值最大化？ m 1?1 max j j j c y =∑ 1 0j j y =?被装载 s.t. m j j v y V ≤∑0 j ?没被装载1 j m =1 j j j w y W =≤∑ 0 or 1 1,2,,j y j m =="

(Chicago)大学的Linus Schrage教授于1980年美国芝加哥(Chi)Li S h 前后开发, 后来成立LINDO系统公司（LINDO Systems Inc.），网址：https://www.wendangku.net/doc/4a114384.html, I）网址htt//li d LINDO: Interactive and Discrete Optimizer (V6.1) Linear(V61) LINGO: Linear Interactive General Optimizer (V8.0) LINDO——解决线性规划LP—Linear Programming，整数规划IP—Integer Programming问题。 LINGO——解决线性规划LP—Linear Programming，非线性规划NLP—Nonlinear Programming，整数规划IP—Integer Programming g g整划g g g 问题。

线性规划模型在生活中的实际应用

线性规划模型在生活中的实际应用 一、线性规划的基本概念 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素. 二、线性规划模型在实际问题中的应用 （1）线性规划在企业管理中的应用范围 线性规划在企业管理中的应用广泛，主要有以下八种形式： 1.产品生产计划：合理利用人力、物力、财力等，是获利最大. 2.劳动力安排：用最少的劳动力来满足工作的需要. 3.运输问题：如何制定运输方案，使总运费最少. 4.合理利用线材问题：如何下料，使用料最少. 5.配料问题：在原料供应的限制下如何获得最大利润. 6.投资问题：从投资项目中选取方案，是投资回报最大. 7.库存问题：在市场需求和生产实际之间，如何控制库存量从而获得更高利益.

8.最有经济计划问题：在投资和生产计划中如何是风险最小 . （2）如何实现线性规划在企业管理中的应用 在线性规划应用前要建立经济与金融体系的评价标准及企业的计量体系，摸清企业的资源.首先通过建网、建库、查询、数据采集、文件转换等，把整个系统的各有关部分的特征进行量化，建立数学模型，即把组成系统的有关因素与系统目标的关系，用数学关系和逻辑关系描述出来，然后白较好的数学模型编制成计算机语言，输入数据，进行计算，不同参数获取的不同结果与实际进行分析对比，进行定量，定性分析，最终作出决策. 3.3 线性规划在运输问题中的应用 运输是物流活动的核心环节，线性规划是运输问题的常用数学模型，利用数学知识可以得到优化的运输方案. 运输问题的提出源于如何物流活动中的运输路线或配送方案是最经济或最低成本的.运输问题解决的是已知产地的供应量，销地的需求量及运输单价，如何寻找总配送成本最低的方案；运输问题包含产销平衡运输问题和产销不平衡运输问题；通常将产销不平衡问题转化为产销平衡问题来处理；运输问题的条件包括需求假设和成本假设.需求假设指每一个产地都有一个固定的供应量所有的供应量都必须配送到目的地.与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须有出发地满足；成本假设指从任何一个产地到任何一个销地的配送成本和所配送的数量的线性比例关系.产销平衡运输问题的一般提法是： 假设某物资有m个产地a1，a2，?，am;各地产量分别为b1，b2，?，bn，物资从产地Ai运往销地Bj的单位运价为cij,满足：

运筹学-线性规划模型在实际生活中的应用

线性规划模型在实际生活中的应用 【摘要】线性规划在实际生活中扮演着很重要的角色，研究对象是计划管理工作中有关安排和估值的问题,其广泛应用于经济等领域，是实际生活中进行管理决策的最有效的方法之一。解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案。本文通过对例题利用线性规划分析，如何合理的分配利用，最终找到最优解使企业利润最大，说明了线性规划在实际生活中的应用，而且对线性规划问题模型的建立，模型的解进行了分析，运用图解法和单纯形法解决问题。 【关键词】线性规划、建模、实际生活、图解法、单纯形法 前言：线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 在实际生活中，经常会遇到一定的人力、物力、财力等资源条件下，如何精打细算巧安排，用最少的资源取得最大的效益的问题，而这正是线性规划研究的基本容，它在实际生活中有着非常广泛的应用．任何一个组织的管理者都必须对如何向不同的活动分配资源的问题做出决策，即如何有效地利用人力、物力完成更多的任务，或在预定的任务目标下如何耗用最少的人力、物力去实现目标。在许多情况下，大量不同的资源必须同时进行分配，需要这些资源的活动可以是不同的生产活动，营销活动，金融活动或者其他一些活动。随着计算技术的不断发展，使成千上万个约束条件和决策变量的线性规划问题能迅速地求解，更为线性规划在经济等各领域的广泛应用创造了极其有利的条件。线性规划已经成为现代化管理的一种重要的手段。本文运用常用的图解法和单纯形法解决利润最大化决策问题，贴近生活，很好的吧线性规划应用到生活实践中。 1、简单线性问题步骤简单介绍 建模是解决线性规划问题极为重要的环节，一个正确的数学模型的建立要求建模者熟悉线性规划的具体实际容，要明确目标函数和约束条件，通过表格的形式把问题中的已知

整数线性规划理论

整数线性规划理论 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型整数线性规划。目前所流行的求解整数规划的方法，往 1.2 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.3 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21min x x z += 0,0,5422121≥≥=+x x x x 其最优实数解为：4 5min ,4 5,021===z x x 。LINGO1.lg4 LINGO11.lg4 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21m i n x x z += 0,0,6422121≥≥=+x x x x 其最优实数解为：2 3min ,23,021===z x x 。 若限制整数得：2min ,1,121===z x x 。LINGO2.lg4 LINGO21.lg4 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.4 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行

整数规划和多目标规划模型

1 整数规划的MATLAB 求解方法 （一） 用MATLAB 求解一般混合整数规划问题 由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下： [x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为： ????? ??????∈=≥≤≤=≤=） 取整数（M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ),,2,1(0..min 在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。 在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。

整数线性规划word版

第三章 整数线性规划 本章, 我们介绍三种解决整数线性规划问题的软件: 第一种: MATLAB 中的optimization toolbox 中的若干程序; 第二种: LINDO 软件; 第二种: LINGO 软件. 1. MATLAB 程序说明 程序名: intprogram, L01p_e, L01p_ie, transdetobi, biprogram intprogram 是利用分支定界法解决整数规划问题, 是全部的整数规划问题; L01p_e 是利用枚举法解决0-1规划问题, 变量要求全部为0或者1; L01p_ie 是利用隐枚举法解决0-1规划问题, 变量要求全部为0或者1; Transdetobi 是枚举法和隐枚举法中利用到的将十进制数转化为二进制数的函数; Biprogram 是MATLAB6.5以上版本中有的求解0-1规划的函数的程序. intprogram 执行实例1： 12 121212max 2010s.t.5424 2513 ,0, f x x x x x x x x =++≤+≤≥ 且为整数 在命令窗口的程序执行过程和结果如下: >> c=[-20,-10]; %将最大转化为最小; >> a=[5,4;2,5]; >> b=[24;13]; >> [x,f]=intprogram(c,a,b,[0;0],[inf;inf],[],0,0.0001) % c,a,b 之后[0;0] is the value of low bound;[inf;inf] is the value of up bound;[] is the initialization;0 is the number of the equation constraints; 0.0001 is the concise rate. x = 4.0000 1.0000 f = -90 intprogram 执行实例2: 书中例题3.3.1 在命令窗口的程序执行过程和结果如下: >> c=[-1,-1]; >> a=[-4,2;4,2;0,-2]; >> b=[-1;11;-1];

整数规划和多目标规划模型

1 整数规划的MATLAB 求解方法 （一） 用MATLAB 求解一般混合整数规划问题 由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下： [x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为： ????? ??????∈=≥≤≤=≤=） 取整数（M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ),,2,1(0..min Λ 在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。 在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x Λ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。

运筹学-电力系统规划-模型

运筹学在电力系统中的应用 运筹学的相关基础知识在电力系统中有着广泛应用，涉及最优随机潮流，电力市场中的最优潮流等等。本文就这两方面文献作详细分析。 随机潮流计算是电力系统分析的一项重要内容，有助于对整个电网在各种运行条件下的性能有一个全面、综合的评价，并对电网存在的薄弱环节做出量化分析。针对考虑负荷不确定性的随机最优潮流问题，建立相应的机会约束规划模型。基于确定性最优潮流的内点算法，以确定性负荷最优潮流计算结果为基础，通过建立状态变量的概率分布来判断概率约束是否满足。若不满足，则根据变量的分布和等效的机会约束，形成新的上下限约束，继续计算负荷为期望值时最优潮流，直至所有概率约束满足。 最优潮流是电力系统规划和运行的重要工具。经典的最优潮流问题是在网络结构和负荷功率完全确定的条件下求解满足各（物理和安全）约束的优化调度方案。但电力系统的运行时刻受到随机因素的影响和干扰：负荷功率难以精确预知、设备可能发生故障、元件参数也会发生变化。而电力工业的市场化改革给电力系统的运行带来了更多不确定性因素。因此，有学者提出了新的随机最优潮流的问题。 机会约束规划模型是一种随机规划模型，主要针对的是约束条件中含有随机变量，且必须在观测到随机变量的实现之前作出决策的情况而建立的模型。 求解机会约束规划的传统方法是根据事先给定的置信水平，把机会约束转化为各自确定的等价类，然后用传统的方法求解其等价的确定性模型。对于特殊的比较复杂的机会约束模型，可以借助一些启发式算法直接计算。 不同的研究出发点和考虑不同的随机因素，可导出多种形式的随机最优潮流的问题。最优潮流与概率最优潮流（Probabilistic Optimal PowerFlow, POPF）也是有区别的。概率最优潮流的主要目标根据负荷等因素的概率分布获得状态变量的概率分布函数，随机因素一般不影响最优潮流的计算结果；而随机最优潮流在建立模型和优化计算过程中考虑随机因素的影响，随机因素影响计算的过程和最终的结果。 在给出随机最优潮流基本模型的基础上，讨论了在考虑不同随机因素条件下SOPF的线性随机规划模型和求解方法。而之后的研究者在文献中使用随机最优潮流考虑了元件的随机故障，目标是得到基准条件下运行费用与校正各预想故障的期望费用之和最小的调度方案。再之后考虑了负荷的不确定性，优化的目标是使有功损耗的方差最小。以下列出随机最优潮流的机会约束规划模型。 在仅考虑负荷的不确定性，不考虑发电机和线路的随机故障的情况下，以发

数学建模——混合整数规划

实验四 混合整数规划 一、问题重述 某开放式基金现有总额为15亿元的资金可用于投资，目前共有8个项目可供投资者选择，每个项目可重复投资。根据专家经验，对每个项目投资总额不能太高，应有上限。这些项目所需要的投资额已知，一般情况下投资一年后各项目所得利润也可估算出来，如表1所示。 请帮该公司解决以下问题： (1) 就表1提供的数据，应该投资哪些项目，使得第一年所得利润最高？ (2) 在具体投资这些项目时，实际还会出现项目之间互相影响的情况。公司咨询有关专家后，得到以下可靠信息：同时投资项目A 1，A 3，它们的年利润分别是1005万元，1018.5万元；同时投资项目A 4，A 5，它们的年利润分别是1045万元，1276万元；同时投资项目A 2，A 6，A 7，A 8，它们的年利润分别是1353万元，840万元，1610万元，1350万元，该基金应如何投资？ 其中M 为你的学号后3位乘以10。 (3) 如果考虑投资风险，则应如何投资，使收益尽可能大，而风险尽可能小。投资项目 总体风险可用投资项目中最大的一个风险来衡量。专家预测出各项目的风险率，如表2所示。 二、符号说明 i A :：投资额； i b ：i A 个项目所获得的年利润； i C ：第i A 个项目投资所获得的利润； 'i C ：第i A 个项目同时投资所获得的利润； i m ：投资i A 的上限； i y ：表示0—1变量； i p ：投资第i A 个项目的投资风险； 三、模型的建立 对于问题一 目标函数：8 1max i i i c x ==∑

s.t. 150000i i i i i i b x b x m ?≤? ??≤?∑ 对于问题二 设定0—1变量 131130...,1...,A A y A A ?? ?项目不同时投资项目同时投资 452450...,1...,A A y A A ???项目不同时投资 项目同时投资 2678326780...,,1...,,A A A A y A A A A ?? ?,项目不同时投资 ,项目同时投资 目标函数：'''' 11133111332445524455' '''322 66 77 88 322667788max ()(1)()()(1)()()(1)() y x c x c y x c x c y x c x c y x c x c y x c x c x c x c y x c x c x c x c =++-++++-++ ++++-+++ s.t. 1 13 131 24545 23267826783 1500001000i i i i i i b x k y x x x x y k y x x x x y k y x x x x x x x x y k b x m ?≤?? =??≤??≥?? ≤???≥? ?≤? ?≥?? ≤?∑ 对于问题三： 目标函数： max min max() i i i i i i c x b x p =∑ s.t. 150000i i i i i i b x b x m ?≤? ??≤?∑ 对于问题三模型的简化 固定投资风险，优化收益，设a 为固定的最大风险。 max i i i c x =∑

1_6237190_两阶段随机规划的若干算法及应用研+究

论文题目： 两阶段随机规划的若干算法及应用研究 作者姓名：刘敬生入学时间：2006年9月专业名称：概率论与数理统计研究方向：统计理论与应用指导教师：周长银职称：副教授 论文提交日期：2009年5月 论文答辩日期：2009年6月 授予学位日期：

STUDY OF SOME ALGORITHMS FOR TWO-STAGE APPLICATIONS ITSAPPLICATIONS STOCHASTIC PROGRAM AND ITS A Dissertation submitted in fulfillment of the requirements of the degree of MASTER OF SCIENCE from Shandong University of Science and Technology b y Liu Jingsheng Supervisor:Vice Professor Zhou Changyin College of Information Science and Engineering May2009

声明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。 硕士生签名： 日期： AFFIRMATION I declare that this dissertation,submitted in fulfillment of the requirements for the award of Master of Science in Shandong University of Science and Technology,is wholly my own work unless referenced of acknowledge.The document has not been submitted for qualification at any other academic institute. Signature: Date:

整数线性规划

整数线性规划 【数学模型】 m in T x f x st. A x b ?≤ A eq x b eq ?= lb x ub ≤≤ i x 取值为整数 其中f , x , b , beq , lb 和ub 为向量，A 和Aeq 为矩阵。 【函数】 intprog 【说明】 在Matlab 中无求解整数线性规划的现成函数，利用Matlab 的线性规划函数linprog 来编写整数线性规划函数，输入与输出与linprog 类似，采用分枝定界法来实现。 Matlab 主程序intprog 如下： function [x,fval,status] = intprog(f,A,B,I,Aeq,Beq,lb,ub,e) %整数规划求解函数 intprog() % 其中 f 为目标函数向量 % A 和B 为不等式约束 Aeq 与Beq 为等式约束 % I 为整数约束 % lb 与ub 分别为变量下界与上界 % x 为最优解，fval 为最优值 % 控制输入参数 if nargin < 9, e = 0.00001; if nargin < 8, ub = []; if nargin < 7, lb = []; if nargin < 6, Beq = []; if nargin < 5, Aeq = []; if nargin < 4, I = [1:length(f)]; end , end , end , end , end , end %求解整数规划对应的线性规划,判断是否有解 options = optimset('display','off'); [x0,fval0,exitflag] = linprog(f,A,B,Aeq,Beq,lb,ub,[],options); if exitflag < 0 disp('没有合适整数解'); x = x0; fval = fval0; status = exitflag; return ; else %采用分支定界法求解

第六章整数规划

第五章整数规划 一、填空题 1．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）。 2．在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为（）。 3．已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P。（）。 4．在0 - 1整数规划中变量的取值可能是（）或（）。 5．对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为（）个。 6．分枝定界法和割平面法的基础都是用（）求解整数规划。 7．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行得X1+1／7x3+2／7x5=13／7，则以X1行为源行的割平面方程为（）。 8．在用割平面法求解整数规划问题时，要求全部变量必须都为（）。 9．用（）求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。 10．求解纯整数规划的方法是割平面法。求解混合整数规划的方法是（）。 11．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是（）。 12．在应用匈牙利法求解分配问题时，最终求得的分配元应是（）。 13.分枝定界法一般每次分枝数量为（）个. 二、单选题 1．整数规划问题中，变量的取值可能是（）。 A．整数B．0或1C．大于零的非整数D．以上三种都可能 2．在下列整数规划问题中，分枝定界法和割平面法都可以采用的是A（）。 A．纯整数规划B．混合整数规划C．0—1规划D．线性规划 3．下列方法中用于求解分配问题的是（）。 A．单纯形表B．分枝定界法C．表上作业法D．匈牙利法 三、多项选择

数学建模B题标准答案

2011高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：北京大学 参赛队员(打印并签名)：1.姚胜献 2.许锦敏 3.刘迪初 指导教师或指导教师组负责人(打印并签名)：刘业辉 日期：2011年9月12日 赛区评阅编号（由赛区组委会评阅前进行编号）：

2011高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 交巡警服务平台的设置与调度 摘要 本文通过建立整数规划模型，解决了分配各平台管辖范围、调度警务资源以及合理设置交巡警服务平台这三个方面的问题；通过建立线性加权评价模型定量评价了某市现有交巡警服务平台设置方案的合理性，并根据各个区对服务平台需求量的不同，提出了重新分配全市警力资源的解决方案。在计算交巡警服务平台到各个路口节点的路程时，使用了图论里的floyd算法。 针对问题一的第一个子问题，首先假设交巡警服务平台对某个路口节点的覆盖度是二元的，引入决策变量，建立了0-1整数规划模型。交巡警出警应体现时间的紧迫性，所以选择平均每个突发事件的出警时间最短作为目标函数，运用基于MATLAB的模拟退火算法进行求解，给出了中心城区A的20个服务平台的管辖范围，求得平均每个案件的出警时间为1.013分钟。 针对问题一的第二个子问题，为了实现对中心城区A的13个交通要道的快速全封锁，以最短的封锁时间为目标，建立了0-1整数规划模型，利用lingo软件编程求解，给出了该区交巡警服务平台警力合理的调度方案，并求得对13个交通要道实现全封锁最短需要8.02分钟。 问题一的第三个子问题是交巡警服务平台的选址问题。考虑到建设新的服务平台需要投入更多的成本和警务资源，还需平衡各个服务平台的工作量。因此，以增加最少的服务平台数和服务平台工作量方差最小为目标，采用集合覆盖理论，建立了双目标0-1整数规划模型，用基于MATLAB的模拟退火算法求解出增加的服务平台数为4个，新增 的服务平台具体位置为A 28,A 40 ,A 48 ,A 88 ，并得到各个服务平台的工作强度方差为2.28。 针对问题二的第一个子问题，通过建立线性加权评价模型定量评价了该市现有交巡警服务平台设置方案的合理性，结果发现全市服务平台覆盖率较低且各个区的工作量不均衡，得出全市服务平台的布局存在明显的不合理的结论。并确定各区域人口密度、各区域公路总长度以及各区域平均每天总的发案率为各区域对交巡警需求的指标，然后根据各个区对服务平台需求量的不同，提出了较为合理的分配全市警力资源的解决方案。 对于问题二的第二个子问题，以围堵范围最小和调动警力最少的原则，通过分析案发后嫌疑犯可能到达的位置，给出了围堵方案。 关键词：交巡警服务平台0-1整数规划模拟退火法