1 -1 问题的分析与重述问题的分析与重述很多城市街道和学校道路已经建成可视化智能交通自动控制系统，使用安装在道路上的摄像头来监控所发生的一切情况,目前主要安装有两种摄像头，一类是可以 360 度需旋转，另一类是不能旋转主要用于监控交通违章某理工学院汇南校区摄像头道路的平面图如图一，试以该区域如图 1 的 37 个位置安装监控摄像头为例，选择在哪些安位置装摄像头才能在有效监控时使所需要的摄像头数目最少 2 -2 运筹学模型的建立运筹学模型的建立2.1 基本假设与符号说明基本假设与符号说明2.1.1 模型的假设模型的假设1. 任何两个只有一段连线的位置之间只要有一个摄像头，就可以实现有效监控2. 在监控期间，所有的摄像头都正常工作，不考虑出现以外的摄像头监控无效3. 所安置的摄像头均为 360 度需旋转的2.1.2 模型符号说明（） 个位置安置摄像头，第个位置不安置摄像头第iixi1, 0373 , 2 , 1 i------实现有效监控所摄像头的总数z2.2 模型的建立模型的建立首先将该问题的实际平面图简化，得到关于一个位置点和道路的直观图，如下图二所示：- 3 -根据运筹学所学知识，可以将该实际问题转化为 0-1 整数规划问题，分别对各个道路的情况进行分析，建立模型。
首先要在满足有效监控的前提下，实现所安置的方案最优，所安置的摄像头最少，即： 取得最小值此时：z 371miniixz然后对各个路段进行分析，在位置 与位置之间的路段间，只要位置 与121位置其中一个安置了摄像头，就可实现在次路段上的有效监控，即：2121 xx在位置 与位置 之间的路段间，只要一个位置安置了摄像头，就可实现13在次路段上的有效监控，即：131 xx分别分析图二中所有的路段，可以得到如下结果：在位置 与位置 8 之间的路段间，要实现有效监控则有：1181 xx在位置 9 与位置 8 之间的路段间，要实现有效监控则有：189 xx在位置 4 与位置 8 之间的路段间，要实现有效监控则有：184 xx在位置 4 与位置 5 之间的路段间，要实现有效监控则有：154 xx在位置 4 与位置 6 之间的路段间，要实现有效监控则164 xx在位置 7 与位置 5 之间的路段间，要实现有效监控则- 4 -157 xx在位置 17 与位置 5 之间的路段间，要实现有效监控则1517 xx在位置 11 与位置 6 之间的路段间，要实现有效监控则1611 xx在位置 11 与位置 12 之间的路段间，要实现有效监控则11211 xx在位置 11 与位置 16 之间的路段间，要实现有效监控则11611 xx在位置 11 与位置 10 之间的路段间，要实现有效监控则11011 xx在位置 13 与位置 10 之间的路段间，要实现有效监控则11013 xx在位置 17 与位置 10 之间的路段间，要实现有效监控则11017 xx在位置 13 与位置 14 之间的路段间，要实现有效监控则11413 xx在位置 13 与位置 15 之间的路段间，要实现有效监控则11513 xx在位置 17 与位置 24 之间的路段间，要实现有效监控则12417 xx在位置 23 与位置 24 之间的路段间，要实现有效监控则12423 xx- 5 -在位置 25 与位置 24 之间的路段间，要实现有效监控则12425 xx在位置 23 与位置 21 之间的路段间，要实现有效监控则12123 xx在位置 23 与位置 22 之间的路段间，要实现有效监控则12223 xx在位置 18 与位置 21 之间的路段间，要实现有效监控则12118 xx在位置 20 与位置 21 之间的路段间，要实现有效监控则12120 xx在位置 18 与位置 19 之间的路段间，要实现有效监控则11918 xx在位置 20 与位置 19 之间的路段间，要实现有效监控则11920 xx在位置 20 与位置 22 之间的路段间，要实现有效监控则12220 xx在位置 25 与位置 26 之间的路段间，要实现有效监控则12625 xx在位置 25 与位置 29 之间的路段间，要实现有效监控则12925 xx在位置 25 与位置 30 之间的路段间，要实现有效监控则13025 xx在位置 27 与位置 26 之间的路段间，要实现有效监控则- 6 -12627 xx在位置 27 与位置 28 之间的路段间，要实现有效监控则12827 xx在位置 31 与位置 30 之间的路段间，要实现有效监控则13031 xx在位置 34 与位置 30 之间的路段间，要实现有效监控则13034 xx在位置 31 与位置 32 之间的路段间，要实现有效监控则13231 xx在位置 31 与位置 35 之间的路段间，要实现有效监控则13531 xx在位置 33 与位置 32 之间的路段间，要实现有效监控则13233 xx在位置 36 与位置 32 之间的路段间，要实现有效监控则13236 xx在位置 33 与位置 37 之间的路段间，要实现有效监控则13733 xx综合以上情况，得到该问题的模型如下：目标函数： 371miniixz约束条件：121 xx131 xx181 xx- 7 -189 xx184 xx154 xx164 xx157 xx1517 xx1611 xx11211 xx11611 xx11011 xx11013 xx11017 xx11413 xx11513 xx12417 xx12423 xx12425 xx12123 xx12223 xx12118 xx12120 xx11918 xx11920 xx- 8 -12220 xx12625 xx12925 xx13025 xx12627 xx12827 xx13031 xx13034 xx13231 xx13531 xx13233 xx13236 xx13733 xx)372 , 1(01 ixi，或- 9 -3 模型的求解模型的求解3.1 采用采用 0-1 整数规划的解法求解整数规划的解法求解在该模型里，由于变量多达 37 个，约束条件也多达 40 个，所以根本无法用 0-1 整数规划的一般解法求解，为此我们通过求解线性和非线性优化问题的简易工具—lingo 来编程求解。
3.2 运用运用 lindo 软件求解软件求解3.2.1 lindo 程序运行结程序运行结在 lindo 中求解的结果见附录图五，图六，图七，图八所示3.2.2 结果解释结果解释由图五到图八中的数据结果我们可以得到：在 11 次迭代后得到全局最优解，且最优目标值为 16，变量到的值依次为：1x37x1，0，0，0，1，1，0，1，0，0，1，0，1，0，0，0，1，1，0，1，0，0，1，0，1，0，1，0，0，1，0，1，0，0，1，0，1表示在位置1，5，6，8，11，13，17，18，20，23，25，27，30，32，35，37 处安置摄像头就可以保证整个区域的有效监控了在校区将摄像头安置的最优方案反应到图中的位置点上的具体情况如下图三所示：- 10 -在实际的学校平面图中，所安置摄像头的位置及数量情况如下图四所示：4 问题的进一步分析问题的进一步分析由图六和图七中所给出的结果，在 “Reduced Cost”列出最优单纯形表中判别数所在行的变量的系数中，表我们可以得到：当位置点1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、21、22、29 上增加一个安置一个摄想头时，目标函数都会增加 1，也就是说这些点中，- 11 -如果最优方案里不需要安置摄像头的位置点上，而实际情况是却安置了，那么就一定多出相应个数的摄像头。
在最优方案里需要安置的位置点有1，5，6，8，11，13，17，18，20，23，25，27，30，32，35，37，所以说，当在 2、3、4、7、9、10、12、14、15、16、21、22、29 位置点上安置时，就没有必要安置对于位置点19、20、22、23、24、25、26、27、28、30、31、32、33、34、35、36、37 上安置增加安置摄像头时，不会增加目标函数的值，例如：对位置点 19 和位置点20，在最优方案里，选择的是 20，但是如果选择安置位置点 19 而不安置位置点 20 时，仍然能在实现有效监控的情况下，目标函数的值不变5 模型优缺点及改进方向模型优缺点及改进方向5.1 模型的优点模型的优点在实际情况出发，针对现实问题作出了可行解决方案，具有较强的适用性；采用 0-1 整数规划模型和 lingo 软件求解，使得解决问题的方案本身具有更高的优化效果合理的假设，严格的推导，结合图形直观的分析可以很清晰的了解所需要解决的问题的情况和所得到的方案，有效的简化，对实际的道路分布情况简化简化到点与线的关系（如图二） ，易于理解5.2 模型的不足模型的不足模型是一个平面内建立建立起来的，虽然通过采用了可以 360 度旋转的摄像头来有效的弥补了道路出现斜坡的情况，但是在实际情况中可能会出现某一位置点没有斜坡范围需要监控，采用不能够旋转的摄想头也能达到有效监控，这正是该模型的局限所在。
5.3 模型的改进和推广模型的改进和推广在实际考查所有的位置点后，根据各个位置点是否存在斜坡等实际情况出- 12 -发，提出问题，建立模型，从而使模型具有更好的使用效果该模型可以推广到一般的交通道路，街道和小区结束语结束语充分结合运筹学所学的知识，建立了一个关于可安置摄像头的位置点的 0-1 整数规划模型，利用 LINGO 软件求解，得到了一个在学校内所有的道路实现有效监控的最优方案，其具体方案为在下图一中的位置点：1，5，6，8，11，13，17，18，20，23，25，27，30，32，35，37 处安置摄像头就可以保证整个区域的有效监控了最后对该模型进一步的拓展、分析和推广，使得该模型的实用性变得更强参考文献参考文献[1] 胡运权，运筹学基础及应用(第五版) [M]，高等教育出版社,2008.6[2] 熊伟主编，运筹学[M]，武汉大学出版社,200579[3] 龙子泉，管理运筹学[M].，武汉大学出版社,2002- 13 -致谢辞致谢辞在课程设计的尾声，我不是为设计的圆满完成而高兴，而首先想到的是给我们无微不至的关怀和指导的孙文娟老师在课程设计过程中,我遇到了许多问题，但在孙老师指导下,我克服了重重困难，最终得以完成此次课程设计。
同时，通过此次课程设计，我们对运筹学这门学科及相关数学工具有了更深刻了解，让我们认识到了理论与实践结合的重要意义.在此,我向老师表示衷心的感谢!附录附录附件附件 1 lindo 运算结果运算结果LP OPTIMUM FOUND AT STEP 21OBJECTIVE FUNCTION VALUE1) 16.00000VARIABLE VALUE REDUCED COSTX1 1.000000 0.000000X2 0.000000 1.000000X3 0.000000 0.000000X4 0.000000 0.000000X5 1.000000 0.000000X6 1.000000 0.000000- 14 -X7 0.000000 。