2010井冈山大学“井冈杯”数学建模论文

井冈山大学

2010年“井冈杯”数学建模竞赛

论文题目： A 自习教室开放的优化管理

参赛队员

班级： 工学院07土木本（1）班 姓名： 刘 洪 军 班级： 数理学院08计算本（1）班 姓名： 杨 海 龙 班级： 数理学院08计算本（1）班 姓名： 曾 志 均

2010 年 04 月 23 日

- 1 -

自习教室开放的优化管理

摘要 本文以线性规划为理论基础，针对学校自习教室开放的优化管理问题，在充分合理的假设条件下，建立了相应的数学模型，很好地解决了这一问题。

针对问题1，首先对表格中的数据进行统计和分析，得到了对每一个教室是否开放的重要重要指标：座位数和用电功率（教室用电功率 = 灯管数 * 每只灯管的功率）。依据这两个指标，再结合上自习的学生人数以及教室的有效座位数，利用0-1整数规划，在满足节约用电的目的，我们建立了相应的线性目标函数及相应的约束条件，最后我们利用MATLAB软件进行求解，得到了应该关闭的教室为

教室1，2，11，15，16，25，41，42，44，45

针对问题2，我们首先对每个自习区的单位座位用电功率以及宿舍区到自习区的距离进行了数据的归一化，我们对这两者进行赋值0.6和0.4，构造出一个满意函数F

F?0.6?P?0.4?Lm,n(m?1,2,...10,n?1,2,...9)

该满意函数能很好的体现节约用电的目的以及提高学生满意度。依据此满意函数算出每一个宿舍区到每一个自习区的满意函数值，如果满意函数值的总和最小，那么我们既节约了用电，又提高了学生上自习的满意度，在这里，我们运用指派问题中的匈牙利算法解决，然后再根据各个自习区能够容纳的学生人数，对其进行调整，调整之后，我们选择关闭的教室依次为

教室1，11，15，41，42，43，44，45

针对问题3，由于考试的原因，上自习的学生人数增加，我们首先计算出要搭建教室的座位数为242个，同样运用问题2的指派问题的匈牙利算法，将10个宿舍的学生指派到9个自习区上自习，得到宿舍区A2的一部分学生去搭建的教室上自习，这样即能节约用电，又能使学生的满意度最高。对于宿舍区A2的学生，依据问题2中函数值的大小，自习区B7，B6，B8,B4的函数值最小，显然，尽量安排宿舍区A2的学生去自习区B7，B6，B8,B4。在这两个自习区的10个教室中，我们依据这10个教室的距离和单位座位耗电量，运用灰局势决策，我们选择教室24和32，另一方面，教室24和教室32的座位数为160+160=320>242，满足要求，于是我们得到了

只要搭建2间教室，即在自习区B5搭建和教室24一样的教室，自习区B7搭建和教室32一样的教室

最后我们对建立的模型优缺点进行了分析，并说明了该模型在实际生活中的广泛应用，对决策者具有一定的指导意义。

关键词： 0-1整数规划 归一化 指派问题 匈牙利算法 灰局势决策

*n

- 2 -

1：问题的重述

自习教室开放的优化管理

近年来，大学用电浪费比较严重，集中体现在学生上晚自习上，一种情况是去某个教室上自习的人比较少，但是教室内的灯却全部打开，第二种情况是晚上上自习的总人数比较少，但是开放的教室比较多，这要求我们提供一种最节约、最合理的管理方法，下面是某学校收集的部分数据(见附录1，2)，请完成以下问题：

管理人员只需要每天晚上开一部分教室供学生上自习，每天晚上从7：00---10：00开放（如果哪个教室被开放，则假设此教室的所有灯管全部打开）。完成以下问题： 1．假如学校有8000名同学，每个同学是否上自习相互独立，上自习的可能性为0.7.要使需要上自习的同学满足程度不低于95%，开放的教室满座率不低于4/5，同时尽量不超过90%。问该安排哪些教室开放，能达到节约用电的目的.

2．假设这8000名同学分别住在10个宿舍区，现有的45个教室分为9个自习区，按顺序5个教室为1个区，即1,2,3,4,5为第1区，…，41,42,43,44,45为第9区。这10个宿舍区到9个自习区的距离见表2。学生到各教室上自习的满意程度与到该教室的距离有关系，距离近则满意程度高，距离远则满意程度降低。假设学生从宿舍区到一个自习区的距离与到自习区任何教室的距离相同。请给出合理的满意程度的度量，并重新考虑如何安排教室，既达到节约用电目的，又能提高学生的满意程度。另外尽量安排开放同区的教室。

3． 假设临近期末，上自习的人数突然增多，每个同学上自习的可能性增大为0.85，要使需要上自习的同学满足程度不低于99%，开放的教室满座率不低于4/5，同时尽量不超过95%。这时可能出现教室不能满足需要，需要临时搭建几个教室。假设现有的45个教室仍按问题2中要求分为9个区。搭建的教室紧靠在某区，每个区只能搭建一个教室，搭建的教室与该区某教室的规格相同（所有参数相同），学生到该教室的距离与到该区任何教室的距离假设相同。问至少要搭建几个教室，并搭建在什么位置，既达到节约用电目的，又能提高学生的满意程度。

2. 问题的分析

对于问题1，首先用EXCEL对题目中提供的数据进行统计和分析，计算出45个教室的用电功率，要以节约用电为目的，也就是要使教室用电功率总和最小，在结合上自习的学生人数及教室的有效座位数，依据这两个变量，我们建立0-1整数规划，我们建立了目标函数及相应的约束条件 ，约束条件主要是教室的满座率，最后我们利用MATLAB软件进行求解，可以得到要关闭的教室，使之达到节约用电。

对于问题2，对于每一个教室，在解答这个问题之前，我们引入单位座位功率这个概念，计算公式为

单位座位用电功率?教室的用电功率灯管数?灯管功率?座位数座位数

如果每个教室的单位座位功率越低，说明用电量越少，那么我们就能达到节约用电的目的。另一方面，对于学生来讲，如果学生去离自己宿舍区近的自习区上自习，那么学生上自习的满意度就越高。那么问题2就转化为求学生去上自习时，使单位座

- 3 -

位用电功率低，离自习区的距离近。于是我们可以建立一个函数来联系两者，我们称之为满意函数，如果满意函数值越小，那么用电功率总和将越少，学生的满意度也越高。在这里我们假设单位座位用电功率的重要性略高于学生的满意度。既在赋权重值时，单位座位用电功率的权重值稍大于距离的权重值。我们依据这个满意函数，以单位座位功率和距离为该函数的因变量，算出各个宿舍区到各个自习区的满意函数值，依据题意，我们要使满意函数值的总和最小。可以运用运筹学中的指派问题，我们利用匈牙利算法解决这个非标准的指派问题。当该满意函数值总和最小时，可以得到去各个自习区的学生人数之后，由于每个自习区的人数限制，我们对人数进行调整，这样我们可以得到要关闭的教室。

对于问题3，临近期末，上自习的人数增多，要满足开放的教室满座率不低于4/5，同时尽量不超过95%。这样就出现了教室不够的情况，因此我们需要临时搭建几个教室，我们首先计算要搭建教室的座位数，然后同样运用问题2中的匈牙利算法解决非标准的指派问题。依据问题2中函数值的大小，可以得到学生对自习区上自习的满意程度。我们以这些自习区教室的距离和单位座位耗电量为指标，运用灰局势决策，选择要搭建的教室，并且搭建的教室和这个区的某个教室的所有参数应完全相同，另外搭建的教室同样要满足满座率的要求。

3. 模型的假设和符号的说明

3.1 模型的假设

（1）题目提供的相关统计数据真实可信；

（2）如果哪个教室被开放，则假设此教室的所有灯管全部打开； （3）每个同学是否上自习相互独立，即相互之间不干扰；

（4）假设学生从宿舍区到自习区的距离与到自习区任何教室的距离相同 ； （5）假设搭建的教室与该区某教室的规格相同（所有参数相同），学生到该教室的距离与到该区任何教室的距离相同；

（6）从问题2开始，我们在安排教室时，考虑到节约用电的要求，我们尽量安排开放同区的教室；

（7）对单位座位用电功率和距离，我们考虑要尽量节约用电，假设单位座位用电功率的重要性略高于距离；

3.2 符号的使用及说明

- 4 -

Am 代表每一个宿舍区 ?m=1,2...10? ；

Bn 代表每一个自习区 ?n=1,2...9? ；

R 上自习的学生总人数 ；

R 临近期末时上自习的学生总人数 ； Zi 教室i的座位数（i=1,2...45）；

Mi 教室i上自习的学生数（i=1,2...45）；

pi 教室i的用电功率(i=1,2...45)；

Mn 4/5 自习区Bn满座率为4/5的学生数目（n=1,2...9）；

Mn 90% 自习区Bn满座率为90%的学生数目（n=1,2...9）；

Mn 95% 自习区Bn满座率为95%的学生数目（n=1,2...9）；Mn 4/5 自习区Bn满座率为4/5时,应该调整的学生数目（n=1,2...9）；

Mn 80% 自习区Bn满座率为90%时,应该调整的学生数目（n=1,2...9）；

Mn 80% 自习区Bn满座率为95%时,应该调整的学生数目（n=1,2...9）；

Nn 自习区 Bn上自习的学生数（n=1,2...9）；

Pn 自习区 Bn的单位座位用电功率（n=1,2...9）； Pn 归一化后自习区 Bn单位座位用电功率(n=1,2...9)；Lm,n 宿舍区Am到自习区Bn的距离(m=1,2...10,n=1,2...9)；

?

Lm,n 宿舍区A到自习区Bn归一化后的距离(m=1,2...10,n=1,2...9)；m

Z 临近考试需要搭建教室的座位数；

其他符号在模型中运用时再作说明。

4. 模型的建立与求解

4.1 问题1的模型建立与求解

我们对附录1中表格的数据进行计算，得到了45个教室的用电功率，

- 5 -

教室的用电功率= 灯管数 * 每只灯管的功率

这样就得到了每一个教室的用电功率，具体的数据见附录4的表格。

依据问题1的条件，去上自习的学生相互独立，且去上自习的可能性为0.7。我们容易知道去上自习的学生人数服从二项分布

R~b?8000，0.7?那么上自习的学生人数R为

R?8000?0.7?95%?5320?人?

其次我们要满足开放的教室满座率不低于4/5，同时尽量不超过90%，那么每一个开放的教室上自习的学生数为：

0.8Zi?Mi?0.9Zi （i=1,2...45）

且约束条件为 0.8?Zi?R?5320?0.95?Zii=1i=14545

由题目的要求，要求达到节约用电的目的，那么要求总用电功率最小,在这里我们引入0-1变量

? 0 表示关闭教室Xi?? （i=1,2...45） 1 表示开放教室?

依据上面的两个条件，我们建立以下目标函数Z上的线性表达式和约束条件，得到了以下的标准形式

minZ??PiXi?1680X1?1680X2?......?1250X44?2160X45i?145?0.9(64X1?88X2?......?70X44?120X45)?5320s..t??0.8(64X1?88X2?......?70X44?120X45)?5320?Xi?0或1 （i=1,2...45）?

要解决此线性规划问题，我们借助MATLAB软件进行求解，运行程序见附录3，

运行得到的结果为

X1?X2?X11?X15?X16?X25?X41?X42?X44?X45?0

所以我们要关闭的教室为

教室1，2，11，15，16，25，41，42，44，45

关闭上面的教室，我们在满足学生上自习的同时，尽量可以达到节约节约用电的目的。

- 6 -

4.2 问题（2）的模型建立与求解

要解决此问题，我们首先应该考虑到两个方面，对于学校来讲，应该达到节约用电的目的，就是要使用电功率总和最小；而对于学生来讲，应该尽量提高学生的满意度，就是宿舍区到自习区的距离近。我们构造一个满意函数，用单位座位用电功率和距离这两个指标来作为该函能的因变量，于是该函数能很好地代表这两个指标。之后我们对单位座位用电功率和距离进行数据归一化，将归一化的数据带入函数中，得到了一系列的函数值，再运用指派问题来解决，我们建立以下模型并进行求解。 4.2.1 单位座位用电功率和距离的归一化处理

步骤一:求解每个自习区的单位座位用电功率并对其进行数据的归一化

将45个教室分为9个自习区之后， 9个自习区的总座位数和用电总功率为各个区5个教室之和，对题目中提供的数据进行计算，得到了9个自习区总座位数和用电总功率，如表1所示

自习区的总座位数 = 等于该自习区5个教室座位数的总和自习区的用电总功率 = 等于该自习区5个教室用电功率的总和

表1：9个自习区总座位数和用电总功率（单位分别为个和w）

总座位数 用电总功率 B1 666 9720 B2 590 8028 B3 781 10939 B4 720 9720 B5 580 7488 B6 1051 12983 B7 786 9819 B8 1000 B9 670 11912 10581 其次计算每个自习区单位座位用电功率，依据表1的总座位数和用电总功率，用以下公式，得到的数据如了表2所示

单位座位用电功率?自习区的用电总功率总座位数

表2：每个自习区单位座位用电功率（单位为w）

区号 单位座位用电功率 B1 B2 B3 B4 B5 B6 B7 B8 B9 14.59 13.61 14.01 13.5 12.91 12.35 12.49 11.91 15.79 最后，我们用数据归一化公式1对单位座位用电功率数据归一化，得到了的结果如表3所示

- 7 -

Pn*????n?1,2...9? ?数据归一化公式 1?max?P??min?P?Pn?minPn1?n?9n1?n?9n1?n?9?

表3 ：归一化后自习区单位座位的用电功率Pn(单位为W，n=1,2...9) 区号 B1 B2 B3 B4 B5 B6 B7 B8 B9 单位座位用电功率 0.691 0.438 0.541 0.410 0.258 0.113 0.150 0.000 1.000 步骤二:对每个宿舍区到自习区的距离进行数据的归一化

我们同样对宿舍区到自习区的距离的数据进行归一化，附录2给出了各个宿舍区到各个自习区的距离，我们对表中的数据用以下的数据归一化公式2进行归一化，，得到的结果如表4所示

Lm,n?Lm,n?min?Lm,n?Lm,n??min?Lm,n??max1?n?m1?n?m1?n?m?m?1,2...10,n?1,2...9? ?数据归一化公式 2?

表4 ：归一化后宿舍区到自习区的距离Lm,n?单位为米，m?1,2...10,n?1,2...9? A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 B1 0.142 1.000 0.547 0.047 1.000 0.278 0.178 0.448 0.000 0.526 B2 0.000 0.469 0.735 0.615 0.742 0.740 0.299 0.000 0.246 0.504 B3 1.000 0.260 0.000 B4 0.213 0.380 0.291 B5 0.323 0.144 0.804 B6 0.737 0.272 0.803 0.901 0.552 0.653 0.909 0.034 0.879 0.952 B7 0.309 0.000 0.427 0.000 0.135 0.000 0.705 0.900 1.000 1.000 B8 0.518 0.466 0.611 0.788 0.961 0.872 0.029 0.888 0.964 0.565 B9 0.060 0.702 1.000 1.000 0.661 0.580 0.000 0.004 0.096 0.700 0.037 0.419. 0.496 0.287 0.076 0.963 0.556 0.814 0.348 0.365 0.316 1.000 1.000 0.006 0.000 0.000 1.000 0.734 0.119 0.500 0.909 4.2.2 建立满意函数以及利用匈牙利算法解决指派问题

- 8 -

对于每一个开放的教室，我们要求其满座率不低于4/5，同时尽量不超过90%，这样的要求9个自习区满足上面的要求，因此我们得到了这9个自习区上自习的学生人数，如表5所示

表5：9个自习区达到满座率要求时能容纳的学生人数数目

总座位数 B1 666 B2 590 B3 781 B4 720 B5 580 B6 1051 B7 786 B8 1000 B9 670 总和 6844 Mn 4/5 533 472 531 560 625 702 741 576 648 684 464 522 551 841 945 998 629 707 746 800 900 950 536 603 636 5476 6157 6598 Mn 90% 599 Mn 95% 632 （说明：对于每一自习区座位数，考虑上限，因为满座率为4/5，我们取大于该数的最小整数，考虑下限，因为满座率为90%和95%，我们取小于该数的最大整数）

由问题1，我们知道平时上自习的人数为5320人。对于假设（6），我们在安排教室时，考虑到节约用电的要求，我们尽量安排开放同区的教室，也就是说如果在9个自习区中如果关闭某个自习区时，仍然能容纳上自习的学生的情况下，我们可以关闭一些自习区，由表2可以知道自习区B5的座位数最少，如果关闭自习区B5，那么其他8个自习区上自习的学生人数为5012 至5635（人）。依然满足条件，在这里，我们暂时不考虑自习区B5，如果其他自习区的座位数满足不了时，我们再来考虑自习区B5。

对于单位座位用电功率和距离，我们依据假设单位座位用电功率比距离稍微的重要，因此在赋权重值的时候，我们取W=(0.6,0.4)，既要节约用电，且使每个学生到自习区的距离越短越好，那么单位座位耗电量和距离都要取最小值，那么我们建立下列满意函数：

F?0.6?Pn?0.4?Lm,n(m?1,2...10,n?1,2...9)

将表3和表4的数据带入上式显然，，我们得到了一系列函数值值，如表6所示

表6：各个宿舍区到各个自习区的满意函数值

A1 B1 B2 B3 B4 B5 B6 B7 B8 B9 *0.4714 0.2628 0.7246 0.3312 0.2970 0.3626 0.2136 0.2072 0.6240 - 9 -

A2 A3 A4 A5 A6 A7 A8 A9 A10 0.8146 0.4504 0.4286 0.3980 0.1896 0.1766 0.0900 0.1864 0.8808 0.6334 0.5568 0.3246 0.3624 0.5856 0.3890 0.2608 0.2444 1.0000 0.4334 0.5088 0.3394 0.4154 0.4008 0.4282 0.0900 0.3152 1.0000 0.8146 0.5596 0.4394 0.3920 0.1032 0.4886 0.1440 0.3844 0.8644 0.5258 0.5588 0.3550 0.3724 0.7032 0.3290 0.0900 0.3488 0.8320 0.4858 0.3824 0.7098 0.6460 0.5436 0.4314 0.3720 0.0116 0.6000 0.5938 0.2628 0.5470 0.6460 0.1746 0.0814 0.4500 0.3552 0.6016 0.4146 0.3612 0.6502 0.2484 0.4032 0.4194 0.4900 0.3856 0.6384 0.6250 0.4644 0.4638 0.2460 0.6486 0.4486 0.4900 0.2660 0.8800 表6中的满意函数值越大，表示用电功率越大，且学生的满意程度越低，反之，该值越小，表示用电功率越小，且学生的满意程度越高。那么可以把该满意函数值作为学生选择哪个自习区上自习的指标。因此我们进行以下排序：

A1 ：B8?B7?B2?B5?B4?B6?B1?B3?B9 A2 ：B7?B6?B8?B5?B4?B3?B2?B1?B9 A3 ：B8?B7?B5?B3?B4?B6?B2?B1?B9 A4 ：B7?B8?B3?B5?B4?B6?B1?B2?B9

A5 ：B5?B7?B6?B8?B4?B3?B2?B1?B9A6 ：B7?B6?B8?B3?B4?B1?B2?B5?B9A7 ：B1?B7?B2?B6?B1?B5?B4?B3?B9A8 ：B6?B5?B2?B8?B7?B3?B1?B9?B4A9 ：B4?B2?B8?B5?B1?B6?B7?B9?B3A10 ：B4?B8?B6?B3?B2?B7?B5?B1?B9

在上面的排序中，对于B9，满意函数的数值都很大，说明该自习区用电功率大，耗电多，节约不了用电；而且对学生来讲，满意度也差，因此将B9和B5同等对待，先不安排学生去这两个自习区上自习。我们定义满意函数值的总和为P

- 10 -

P??FPn,Lm,n ?m?1,2...10,n?1,2...9?m?110?*?

当上面的P取最小值时，既能节约用电，又能使学生上自习感到满意。我们再次引入0-1变量

?0 宿舍区Am的学生不选择自习区Bn上自习Xm,n???m?1,2...10,n?1,2...9??1 宿舍Am区的学生选择自习区Bn上自习

于是上面的问题可以归结为指派问题，我们用匈牙利算法借助MATLAB软件进行求解，运行程序见附录5，运行得到的结果为

X1，2?X3，3?X6，7?X7,8?X8，6?X9，1?X10,4?1

也就是宿舍区A1的学生安排到自习区B2上自习，宿舍区A3的学生安排到自习区B3上自习，宿舍区A6的学生安排到自习区B7上自习，宿舍区A7的学生安排到自习区B8上自习，宿舍区A8的学生安排到自习区B6上自习，宿舍区A9的学生安排到自习区B1上自习，宿舍区A10的学生安排到自习区B4上自习。 4.2.3 确定关闭的教室

根据步骤二的结果之后，我们把8个宿舍区的学生安排到8个自习区，但是有些自习区的人数满足不了要求，我们通过计算得到的结果如表7所示

表7：9个自习区上自习的学生人数及要调整的学生人数 B1 666 533 599 B2 590 472 531 532 满足 -1 A1 B3 781 625 702 532 93 170 A3 B4 720 576 648 532 44 116 A10 B6 1051 841 945 532 309 413 A8 B7 786 629 707 532 92 175 A6 B8 1000 800 900 532 268 368 A7 B9 670 536 603 532 4 71 A9 总座位数 Mn 4/5 Mn 90% 上自习学生数 532 Mn 4/5 Mn 90% 1 67 A4 学生来源 在上表中，为了满足开放的教室满座率不低于4/5，自习区B1还少1名学生，为

- 11 -

了满足开放的教室满座率不超过90%，自习区B2多了1名学生，我们将自习区B2的这名多余的学生安排到自习区B1，于是这两个自习区都满足条件，但是B1仍然多余了67个座位，由于教室1的座位数为64个，且单位座位用电功率相对较高，我们首先考虑关闭教室1。

宿舍区A2，A4，A5的学生数目为532*3=1596（人），对于宿舍区A2，A4，A5只能安排到自习区B3，B4，，B6，B7，B8，显然这几个区的座位数不够，将自习区B5和B9考虑进来，对于A2，A4，A5来讲，他们满意度高的自习区依次为

A2 ：B7?B6?B8?B5?B4?B3?B2?B1?B9 A4 ：B7?B8?B3?B5?B4?B6?B1?B2?B9

A6 ：B7?B6?B8?B3?B4?B1?B2?B5?B9

对于这宿舍区A2，A4，A5的1596个学生而言，综合式上面的3式，最喜欢的自习区依次

A2，A4，A5 ：B7?B6?B8?B4?B3?B1?B2?B9

自习区B7，B5，B8，B6，B4所能容纳的学生数目165+522+360+413+116=1576<1596,满足不了要求，还需要的座位数为1596-1596=20个，再考虑自习区B3，根据表7自习区B3如果满座率为90%时，还可以170个座位空余，所以多余的座位数位170-20=150个，因此，自习区B3可以关闭一些教室。依据附录4，我们选择的教室是11和15，这2个教室的单位座位用电功率最少；另一方面，座位数64+70=134<150，满足要求。综合以上分析，我们选择要关闭的教室为

教室1，11，15，41，42，43，44，45

关闭上面的8个教室，我们既达到了节约用电的目的，又提高了学生上自习的满意程度。

4.3 问题（3）的模型求解

由于临近期末，上自习的人数突然增多，相对于问题1，每个同学上自习的可能性增大为0.85，且上自习的同学满足程度保证不低于99%。

同样上自习的人数 R 满足二项分布

Rb?8000，0.85?

那么上自习的人数R为

- 12 -

R?8000?0.85?99%?6732?人?

该学校所有教室的座位数为6844个，而开放的教室满座率不低于4/5，同时尽量不超过95%。

0.8Zi?Mi?0.95Zi （i=1,2...45）

依据上面两式，显然座位数太少，不能满足学生上自习。因此要搭建一些临时

教室，搭建的教室的座位数应该满足

0.8Z?6844?R?6740?0.95Z?6844????

? Z??242，1571??同样考虑到学生数目为正数，对其进行了修正?问题3要求开放的教室满座率不低于4/5，同时尽量不超过95%。我们得到了9个自习区的人数及其要调整的人数，如下表9所示

表9：9个自习区的人数及其要调整的人数

B1 总座位数 666 533 632 B2 590 472 560 674 -114 B3 B4 781 625 741 674 67 720 576 684 674 10 B5 580 464 551 674 -123 B6 1051 841 998 674 324 B7 786 629 746 674 72 B8 1000 800 950 674 276 B9 670 536 636 674 38 Mn 4/5 Mn 95% 上自习学生数 674 Mn 95% -42 （注：最后一行表示满座率为95%时，需要调整的学生数，正数表示还能容纳的学生数，负数表示要该自习区不能满足满座率要求，要转移到其他的自习区）。

将自习区B5考虑进来，和问题2的解法相同，我们进行重新的指派问题，再次用匈牙利算法，借助MATLAB软件，运行程序见附录5，运行得到的结果为

X1，2?X3，3?X4，1?X5,5?X6，7?X7，8?X8,6?X9,9?X10,4?1

运行的结果表示宿舍区A2的674个学生中，其中的242个学生应该安排到搭建

的教室上自习，对于宿舍区A2的学生对各个自习区的满意程度的高低为：

A2 ：B7?B6?B8?B5?B4?B3?B2?B1?B9

宿舍区A2的学生去自习区B7,B6, B8, B5上自习的满意度比较高,而且用电量少,而去自习区B3,B2,B1,B9的满意度低,而且用电量多，一方面，由附录2知道,宿舍区A2离自习区距离最短的依次为:B7,B5,B6,B8,如果学生去这几个自习区上自习，学生的满意度高；另一方面，有附表4知道,单位座位用电功率最少的教室依次为:24(在自习

- 13 -

区B5),32(B7),40(B7),14(B7),28(B7),36(B7),39(B7),13(B7),27(B7),29(B7)，这10个教室的指标：距离和单位座位用电功率如表10所示

表10：10个教室的座位数，距离，单位座位用电功率

教室 24(B5) 32(B7) 40(B8) 14(B3) 28(B6) 座位数 160 160 200 190 210 距离 434 390 532 469 473 单位座位用电功率 10.12 10.12 11.52 11.90 11.90 教室 36(B8) 39(B8) 13(B3) 27(B6) 29(B6) 座位数 50 距单位座位离 用电功率 532 11.90 11.90 12.12 12.12 12.12 210 532 210 469 190 473 190 473 仔细分析表10中的数据，我们得到以下结论： （1）对于教室40，36，39：距离一样，但是单位座位用电功率40比36和39都少，所以排除教室36和39，优先选择教室40。

（2）对于教室14，13：距离一样，但是单位座位用电功率14比13少，所以排除教室13，优先选择教室14。

（3）对于教室28，27，29：距离一样，但是单位座位用电功率28比27和29少，所以排除教室27和29，优先选择教室28。

我们将这10个教室只有5个教室满足更高的要求，我们将这5个教室分为以下5类，我们运用灰局势决策，对这5类进行排序，找出满意的局势，得到最优的教室，可以得到搭建的教室与最优的教室的参数一样。

S1: 教室24S2: 教室32S3: 教室40S4: 教室14S5: 教室28

相应的符号说明：

ai: 教室i离宿舍区A2的距离值 ?i?1,2,3,4,5?bi: 教室i单位座位用电功率 ?i?1,2,3,4,5?ri: 教室i的满意局势函数值 ?i?1,2,3,4,5?步骤1：给出局势样本数据

S1=?a1,b1???434 , 10.12?

- 14 -

S2=?a2,b2???390 , 10.12?S3=?a3,b3???532 , 11.52?S4=?a4,b4???469 , 11.90?S5=?a5,b5???473 , 11.90?

步骤2：确认目标极性，作效果测度变换 （1）目标1：（距离为极小值），依据公式

ri1?min?ai1?ai1

?i?1,2,3,4,5?

依次计算出：r11?0.899，r21?1.000，r31?0.733，r41?0.832，r51?0.825（2）目标2：（单位座位用电功率为极小值），依据公式

ri2?min?b1i?b1i ?i?1,2,3,4,5?

依次计算出：r12?1.000，r22?1.000，r32?0.878，r42?0.850，r52?0.850，

步骤3：找出满意局势

对于单位座位用电功率和距离，我们设权重向量W=（0.6，0.4），依据公式

ri?w1?ri1+w2?ri2=0.6?ri1+0.4?ri2 ?i?1,2,3,4,5?

依次计算出：r1?0.939,r1?1.000,r1?0.791,r1?0.839,r1?0.835,

依据ri确定5个教室的排序为：S2?S1?S4?S5?S3，即教室： 32?24?14?28?40 我们选择教室32和24，另外，这两个教室的座位数为160+160=320>242，满足要求，再根据要求，搭建的教室与自习区的最优教室的规格相同（所有参数相同），所以我们选择搭建的教室应为

只要搭建2间教室，即在自习区B5搭建和教室24规格一样的教室，在自习区B7搭建和教室32规格一样的教室

这样既能够满足学生上自习的要求，既节约了用电，有提高学生上自习的满意度。

5.模型的评价

5.1 模型的优点

（1）对问题所给的数据进行了大量的仔细分析和全面的统计；

- 15 -

（2）针对3个问题，引入了单位座位用电功率来代替座位数和用电功率，这样减少了指标，更方便建模；

（3）运用匈牙利算法解决指派问题，得到的结果更精确；

5.2 模型的缺点

（1）附录表中提供的数据与现实不完全相符；

（2）在权重的赋值时，存在人为因素，导致结果有偏差；

（3）在问题2中考虑到开放同一区的教室，忽略了自习区B5，这样对结果的精确度或多或少产生了一定的影响；

6. 模型的应用

该模型不仅应用在学校，而且还在其他的优化系统中有着很广泛的应用，由于线性规划的问题涉及的因素很多，因此我们建立约束条件来满足所有的因素。因此我们在解答线性规划的优化问题时，首先建立目标函数，其次依据所有的因素建立目标函数的约束条件，最后借助数学软件来求解，得到我们满意的方案。因此，对于生活中的实际问题，我们依据模型中的方法，我们可以为决策者提供一定经验，让决策者采用更合理的方案。对决策者有一定的指导意义。

参考文献

[1] 郭林，最优化方法及其应用，北京：高等教育出版社，2007. [2] 胡知能，运筹学，北京：科学出版社，2003.

[3] 龚剑编，MATLAB5.0入门与提高，北京：清华大学出版社，2000 [4] 盛骤，概率论与数理统计，杭州：浙江大学出版社，2004

[5] zxg7980的博客，匈牙利算法的MatLab实现，2010/4/20 14:44:23，

http://zxg7980.blog.163.com/blog/static/118800419201021637453/

- 16 -

附 录

附录1：教室相关数据

教室 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 座位数 64 88 193 193 128 120 120 120 110 120 64 247 190 210 70 85 192 195 128 120 灯管数 42 42 48 50 36 36 36 36 36 36 27 75 48 50 42 42 48 50 36 36 开关数 3 3 4 5 2 2 4 3 3 4 3 5 3 5 3 3 4 5 2 2 一个开关控制的灯管数 14 14 12 10 18 18 9 12 12 9 9 15 16 10 14 14 12 10 18 18 灯管的功率/每只 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w - 17 -

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 120 120 110 160 70 256 190 210 190 205 110 160 70 256 190 210 190 190 210 200 150 150 180 70 36 36 36 36 27 75 48 50 48 50 36 36 27 75 48 50 48 48 50 48 50 48 48 25 4 3 3 4 3 5 3 5 3 5 3 4 3 5 3 5 3 3 5 3 5 3 3 5 9 12 12 9 9 15 16 10 16 10 12 9 9 15 16 10 16 16 10 16 10 16 16 5 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w 40w - 18 -

45

120 45 3 15 40w 附录2 ：学生区(标号为A)到自习区(标号为B)的距离(单位米)

A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 B1 355 695 512 324 696 465 354 425 307 482 B2 305 533 556 541 616 598 383 305 376 477 B3 658 469 384 320 475 407 543 454 535 441 B4 380 506 452 466 499 476 552 573 323 361 B5 419 434 613 422 386 673 448 337 447 570 B6 565 473 572 650 557 573 530 314 553 580 B7 414 390 484 306 428 385 481 545 587 591 B8 488 532 527 607 684 636 318 543 577 491 B9 326 604 618 688 591 552 311 306 334 522 （所有数据仅供计算参考.并非完全真实） 附录3 ：问题1的MATLAB程序

>>f=[42*40,42*40,48*50,50*48,36*45,36*45,36*48,36*45,36*40,36*45,27*40,75*45,48*48,50*50,...

42*40,42*40,48*50,50*48,36*45,36*45,36*48,36*45,36*40,36*45,27*40,75*45,48*48,50*50,...

48*48,50*50,36*40,36*45,27*40,75*45,48*48,50*50,48*48,48*48,50*50,48*48,...

50*50,48*48,48*48,25*50,45*48];

D=[64, 88, 193 ,193, 128 ,120, 120, 120, 110, 120 ,64, 247 ,190 ,210, 70 ,85 ,192 ,195 ,128 ... 120, 120, 120, 110, 160, 70 ,256 ,190, 210, 190, 205, 110, 160, 70, 256 ,190, 210 ...

190 ,190, 210, 200, 150 ,150, 180, 70, 120]; M=-0.9*D;m=0.9*D; N=0.8*D; A=[N;M;m];

- 19 -

b=[5320;-5320;5600]; [x,fval]=bintprog(f,A,b) Optimization terminated.

运行结果：

>>x =0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1

- 20 -

1 0 0 1 0 0

fval =

74093

附录4：每个教室的用电功率（耗电量）和单位座位用电功率

教室 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 座位数 64 88 193 193 128 120 120 120 110 120 64 247 190 210 70 85 192 灯管数 42 42 48 50 36 36 36 36 36 36 27 75 48 50 42 42 48 灯管的功率/每只 40 40 50 48 45 45 48 45 40 45 40 45 48 50 40 40 50 耗电量 1680 1680 2400 2400 1620 1620 1728 1620 1440 1620 1080 3375 2304 2500 1680 1680 2400 单位座位用电功率 26.25 19.09 12.43 12.43 12.65 13.50 14.40 13.50 13.09 13.50 16.87 13.66 12.12 11.90 24.00 19.76 12.50 - 21 -

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 195 128 120 120 120 110 160 70 256 190 210 190 205 110 160 70 256 190 210 190 190 210 200 150 150 180 50 36 36 36 36 36 36 27 75 48 50 48 50 36 36 27 75 48 50 48 48 50 48 50 48 48 48 45 45 48 45 40 45 40 45 48 50 48 50 40 45 40 45 48 50 48 48 50 48 50 48 48 2400 1620 1620 1728 1620 1440 1620 1080 3375 2304 2500 2304 2500 1440 1620 1080 3375 2304 2500 2304 2304 2500 2304 2500 2304 2304 12.30 12.65 13.50 14.40 13.50 13.09 10.12 15.42 13.18 12.12 11.90 12.12 12.19 13.09 10.12 15.42 13.18 12.13 11.90 12.12 12.12 11.90 11.52 16.67 15.36 12.80 - 22 -

44 70 25 50 1250 45 120 45 48 2160 附录5：匈牙利算法的MatLab实现

function [y,fval]=assign_math(C) C=C'; f=C(:);

[m,n]=size(C);

Aeq=zeros(2*n,n*n); for i=1:n

Aeq(1:n,1+(i-1)*n:i*n)=eye(n,n); end

for i=1:n

Aeq(n+i,1+(i-1)*n:i*n)=ones(1,n); end

beq=ones(2*n,1); lb=zeros(n*n,1); ub=ones(n*n,1);

x=linprog(f,[],[],Aeq,beq,lb,ub); y=reshape(x,n,n); y=y';

y=round(y); sol=zeros(n,n); for i=1:n

for j=1:n

if y(i,j)==1

sol(i,j)=C(j,i); end end end

fval=sum(sol(:));

问题2的运行及结果：

>> a=[0.4714 0.2628 0.7246 0.3312 0.3626 0.2136 0.2072 0 0 0

0.8146 0.4504 0.4286 0.3980 0.1766 0.0900 0.1864 0 0 0 0.6334 0.5568 0.3246 0.3624 0.3890 0.2608 0.2444 0 0 0 0.4334 0.5088 0.3394 0.4154 0.4282 0.0900 0.3152 0 0 0 0.8146

0.5596 0.4394 0.3920 0.2886 0.1440 0.3844 0 0 0

- 23 -

17.86 18.00

0.5258 0.5588 0.3550 0.3724 0.3290 0.0900 0.3488 0 0 0 0.4858 0.3824 0.7098 0.6460 0.4314 0.3720 0.0116 0 0 0 0.5938 0.2628 0.5470 0.6460 0.0814 0.4500 0.3552 0 0 0 0.4146 0.3612 0.6502 0.2484 0.4194 0.4900 0.3856 0 0 0 0.6250 0.4644 0.4638 0.2460 0.4486 0.4900 0.2660 0 0 0];

>>[y fval]=assign_math(a)

Optimization terminated successfully.

y = 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 fval =

1.4310

问题3的运行及结果：

>> a=[0.4714 0.2628 0.7246 0.3312 0.2970 0.3626 0.2136 0.2072 0.6240 0

0.8146 0.4504 0.4286 0.3980 0.1896 0.1766 0.0900 0.1864 0.8808 0 0.6334 0.5568 0.3246 0.3624 0.5856 0.3890 0.2608 0.2444 1.0000 0 0.4334 0.5088 0.3394 0.4154 0.4008 0.4282 0.0900 0.3152 1.0000 0 0.8146 0.5596 0.4394 0.3920 0.1032 0.2886 0.1440 0.3844 0.8644 0 0.5258 0.5588 0.3550 0.3724 0.7032 0.3290 0.0900 0.3488 0.8320 0 0.4858 0.3824 0.7098 0.6460 0.5436 0.4314 0.3720 0.0116 0.6000 0 0.5938 0.2628 0.5470 0.6460 0.1746 0.0814 0.4500 0.3552 0.6016 0 0.4146 0.3612 0.6502 0.2484 0.4032 0.4194 0.4900 0.3856 0.6384 0

- 24 -

0.6250

0.4644 0.4638 0.2460 0.6486 0.4486 0.4900 0.2660 0.8800 0];

>>[y fval]=assign_math(a)

Optimization terminated successfully.

y = 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 fval =

2.1914

- 25 -

本文来源：https://www.bwwdw.com/article/fano.html