2006年全国研究生数学建模竞赛D题优秀论文(武汉科技学院).pdfVIP

武汉科技学院：郑仟，李柏勋，陈军旗 2006 年全国研究生数学建模竞赛一等奖 全国第三届研究生数学建模竞赛全国第三届研究生数学建模竞赛 题 目学生与面试老师人数的最优化分配模型 武汉科技学院：郑仟，李柏勋，陈军旗 摘要： 本文探讨了在保证公平公正原则下， 如何确定面试老师和学生人数的合理分 配方案。 问题一：为了确定面试老师与学生人数之间的关系， 首先列出所有面试老师 的组合，任意选定一个初始组，并把初始组与剩下的组合逐一比较，保留满足约 束条件的面试老师组合。 然后在上一步保留下来的老师组合中任取一个没有做过 参考基准的组合做为本次循环的初始组， 将该新始组与上一步保留下来的老师组 合中其他所有组合逐一比较， 保留满足约束条件的面试老师组合。 重复上述过程 ， 直到没有组合能保留下来。如此，不断改变老师数目 M，求出满足约束条件下 相对应的学生人数N， 然后通过曲线拟合的方法求出M关于N的关系式N=F(M)。 对 于 没 有 两 位 及 三 位 老 师 相 同 的 情 形 ， N=F(M) 分别 为 N=0.06735*M2- 0.2036*M+0.5141 和 N=14.89*e0.1398*M-25.9*e0.02322*M。 问题二：我们采用字典排序法，列出 M 个面试老师的所有组合。由于此排序 方法的特殊性，自然满足了 Y1，Y2 和 Y4。为了满足 Y3，我们首先考虑面试中老 师最多有一个相同的情形，类似问题一可确定 M 个老师可以面试的学生人数 N1， 如果 NN1，则 Y3 得到满足；否则，考虑两个考生的“面试组”中有两位老师相 同的情形,求出 M 个老师可以面试的学生人数 N2，再比较 N2 和 N 的大小。如果 N C,则说明 M 4 M 4 M 个老师无法在不重复的条件下面试 N 个学生；如果 N =C，则说明 M 个老师可 4 M 以在不重复的条件下面试 N 个学生。由问题一的的第一种情况的分析可知，当面 试老师人数 M 为 50 时，最多可以面试 23 万多学生，而在实际问题中，各大高校 一次面试人数几乎不会达到这个数，所以我们认为在 M 足够大时，是完全可以面 试足够多的学生的，因此在此问题中我只需考虑 N =C的情形。 4 M 下面我们根据条件 Y1-Y4，来依次分析，以寻求学生与面试老师之间合理的 分配模型，如下所示： 1）采用字典排序法见参考文献 1，排列出 M 个面试老师的所有组合，由 于此排序方法的特殊性，使得我们自然而然的满足了 Y1：每位老师面试的学生 数量应尽量地均衡，同时也满足了 Y2：面试不同考生的“面试组”成员不能完 武汉科技学院：郑仟，李柏勋，陈军旗 2006 年全国研究生数学建模竞赛一等奖5 全相同，和 Y4：被任意两位老师面试的两个学生集合中出现相同的学生的人数 尽量的少。 2）为了满足 Y3：两个考生的“面试组”中有两位或三位老师相同的情形尽 可能的少，我们依照下面的算法进行： 首先，我们考虑两个考生的“面试组”中有两位或三位老师相同的情形不存 在，即只考虑面试中老师至少有一个相同的情形，那么则可以通过编程确定 M 个老师可以面试的学生人数 N1； 然后考虑 N1 与 N 的大小，如果 NN1，再比较 N2 和 N 的大小，同理 如果 NN2，只要考虑至少有两个相同的就行，否则，就只能考虑三个相同的情 形了。 2.32.3 实例分析实例分析 按 照 上 述 算 法 ， N=379 ， M=24 时 的 具 体 方 案 如 下 ：（ 其 中 A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X 分别代表 24 位老师， i(1=i 2 2/M 2 2/M C*C,则说明 M 个老师无法在不重复的条件下面试 N 个学生；如果 N = 2 2/M 2 2/M C*C，则说明 M 个老师可以在不重复的条件下面试 N 个学生。由问题一 2 2/M 2 2/M 的的第一种情况的分析可知，当面试老师人数 M 为 50 时，最多可以面试 23 万多 学生，而在实际问题中，各大高校一次面试人数几乎不会达到这个数，所以我们 认为在 M 足够大时，是完全可以面试足够多的学生的，因此在此问题中我只需考 虑 N = C*C的情形。 2 2/M 2 2/M 下面我们根据条件 Y1-Y4，来依次分析，以寻求学生与面试老师之间合理的 分配模型，如下所示： 1）采用字典排序法见参考文献 1，排列出 M 个面试老师的所有组合，由 于此排序方法的特殊性，使得我们自然而然的满足了 Y1：每位老师面试的学生 数量应尽量地均衡，同时也满足了 Y2：面试不同考生的“面试组”成员不能完 全相同，和 Y4：被任意两位老师面试的两个学生集合中出现相同的学生的人数 尽量的少。 2）为了满足 Y3：两个考生的“面试组”中有两位或三位老师相同的情形尽 武汉科技学院：郑仟，李柏勋，陈军旗 2006 年全国研究生数学建模竞赛一等奖10 可能的少，我们依照下面的算法进行： 首先，我们考虑两个考生的“面试组”中有两位或三位老师相同的情形不存 在，即只考虑面试中老师至少有一个相同的情形，那么则可以通过编程确定 M 个老师可以面试的学生人数 N1； 然后考虑 N1 与 N 的大小，如果 NN1，再比较 N2 和 N 的大小，同理 如果 NN2，只要考虑至少有两个相同的就行，否则，就只能考虑三个相同的情 形了。 B、实例分析 按 照 上 述 算 法 ， N=379 ， M=24 时 的 具 体 方 案 如 下 ：（ 其 中 A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X 分别代表 24 位老师， i(1=i=379)表示第 i 个学生） 表 6当 N=379，M=24，并考虑文理分科老师时，具体的分配方案 ABCDEFGHIJKL M N OPQRSTUVW X 1 64 116158190 215 231 56 239 274 302 324 340 353 361 270 365 372 376 370 378 378 11 11 2 65 117159191 216 232 57 240 275 303 325 341 354 362 271 366 373 377 371 10 21 125 21 3 66 118160192 217 233 58 241 276 304 326 342 355 363 272 367 374 368 374 20 31 198 30 4 67 119161193 218 234 59 242 277 305 327 343 356 364 273 368 375 369 375 30 73 238 39 5 68 120 162194 219 235 60 243 278 306 328 344 357 266 298 369 365 372 376 72 83 245 46 6 69 121 163195 220 236 61 244 279 307 329 345 358 267 299 370 366 373 377 82 206 307 53 7 70 122 164196 221 237 62 245 280 308 330 346 359 268 300 371 3679 39 124 214 344 60 8 71 123 165197 222 238 63 246 281 309 331 347 360 269 3018 19 38 47 197 222 364 72 9 72 124 166198 223 48 108 247 282 310 332 348 262 294 320 18 29 46 55 205 230 367 83 10 73 125 167199 224 49 109 248 283 311333 349 263 295 321 28 37 54 63 213 251 377 90 11 74 126 168200 225 50 110249 284 312 334 350 264 296 322 36 45 62 91 221 257 378 99 12 75 127 169201 226 51 111250 285 313 335 351 265 297 323 44 53 90 99 229 279 20 104 13 76 128 170202 227 52 112251 286 314 336 352 290 316 336 52 61 98 107 237 285 31 113 14 77 129 171203 228 53 113252 287 315 337 258 291 317 337 60 71 106 115244 348 38 125 15 78 130 172204 229 54 114253 288 316 338 259 292 318 338 70 81 114133 250 352 47 131 16 79 131 173205 230 55 115254 289 317 339 260 293 319 339 80 89 123 141 256 356 52 138 17 80 132 174206 40 100 150 255 290 318 252 261 312 332 349 88 97 132 149 278 360 61 149 18 81 133 175207 41 101 151 256 291 319 253 286 313 333 350 96 105 140 157 284 369 73 156 19 82 134 176208 42 102 152 257 292 320 254 287 314 334 351 104 113148 165 306 371 82 162 20 83 135 177209 43 103 153 258 293 321 255 288 315 335 352 112131 156 173 343 373 91 171 21 84 136 178210 44 104 154 259 294 322 256 289 328 345 357 122 139 164 181 347 375 98 180 22 85 137 179211 45 105 155 260 295 323 257 308 329 346 358 130 147 172 189 351 10 105 189 23 86 138 180212 46 106 156 261 296 246 280 309 330 347 359 138 155 180 261 355 37 112198 24 87 139 181213 47 107 157 262 297 247 281 310 331 348 360 146 163 188 265 359 44 130 206 25 88 140 182214 92 142 182 263 298 248 282 311 340 353 361 154 171 196 269 363 55 139 213 武汉科技学院：郑仟，李柏勋，陈军旗 2006 年全国研究生数学建模竞赛一等奖11 根据表 6，我们通过统计的方法来分析该方案满足 Y1-Y4这些要求的情况： 1）对于 Y1，统计表 3 可知 24 个老师中有 20 个老师面试学生的数量为 63 26 89 141 183 32 93 143 183 264 299 249 283 324 341 354 362 162 179 236 273 366 62 148 221 27 90 142 184 33 94 144 184 265 300 250 284 325 342 355 363 170 187 243 289 368 88 157 230 28 91 143 185 34 95 145 185 266 301 251 285 326 343 356 364 178 204 260 293 370 97 163 238 29 92 144 186 35 96 146 186 267 239 274 302 327 34477 186 212 264 297 372 106 170 245 30 93 145 187 36 97 147 187 268 240 275 3036 17 121 17 195 220 268 301 374 115181 251 31 94 146 188 37 98 148 188 269 241 276 304 16 27 194 26 203 228 272 311376 124 188 256 32 95 147 189 38 99 149 189 270 242 277 305 26 69 234 35 211249 288 315 36 133 205 261 33 96 148 22 39 134 174 207 271 243 278 306 68 79 241 42 219 255 292 319 45 140 214 264 34 97 149 23 84 135 175 208 272 244 279 307 78 202 303 49 227 259 296 323 54 147 222 267 35 98 150 24 85 136 176 209 273 2455 35 120 210 340 56 235 263 300 327 63 154 229 270 36 99 151 25 86 137 177 2104 15 34 43 193 218 16 68 242 267 305 331 89 164 250 278 37 100 152 26 87 138 178 211 14 25 42 51 201 226 27 79 248 271 310 335 96 173 257 285 38 101 153 27 88 139 179 212 24 33 50 59 209 247 34 86 254 277 314 339 107 178 260 288 39 102 154 28 89 140 180 213 32 41 58 87 217 253 43 95 258 283 3189 114187 265 293 40 103 155 29 90 141 181 214 40 49 86 95 225 275 48 100 262 287 322 19 132 197 266 294 41 104 156 30 91 166 199 223 48 57 94 103 233 281 57 109 266 291 326 28 141 237 271 299 42 105 157 31126 167 200 224 56 67 102 1112406 69 121 270 295 330 70 146 244 279 307 43 106 12 74127 168 201 225 66 77 110129 246 33 78 127 276 299 334 81 155 259 284 309 44 107 13 75128 169 202 226 76 85 119137 252 40 87 134 282 309 338 123 165 262 289 312 45 108 14 76129 170 203 227 84 93 128 145 274 51 94 145 286 313 342 196 172 269 292 319 46 109 15 77130 171 204 228 92 101 136 153 280 58 101 152 290 317 362 204 179 272 295 322 47 110 16 78131 172 205 229 100 109 144 161 302 84 108 158 294 321 365 211186 286 298 324 48 111 17 79132 173 206 230 108 127 152 169 32 93 126 167 298 325 18 219 258 291 308 329 49 112 18 80133 190 215 231 118135 160 177 41 102 135 176 304 329 29 228 263 296 313 334 50 113 19 81158 191 216 232 126 143 168 185 50 111144 185 308 333 71 236 268 301 318 339 51 114 20 82159 192 217 233 134 151 1765 59 120 153 194 312 337 80 243 273 306 323 344 52 115 21 83160 193 218 234 142 159 184 15 85 129 159 202 316 346 203 249 287 311325 348 531 64 116161 194 219 235 150 167 192 24 92 136 166 209 320 350 212 254 290 314 328 351 542 65 117162 195 220 236 158 175 232 66 103 143 177 217 324 354 220 276 297 317 335 355 553 66 118163 196 221 237 166 183 239 77 110 150 184 226 328 358 227 283 300 320 338 360 564 67 119164 197 222 238 174 200 14 119128 160 201 234 3328 248 305 310 326 347 364 575 68 120165 19833 182 208 25 192 137 169 210 241 336 122 255 342 315 331 352 367 586 69 1212 13 117 13 191 216 67 200 142 174 218 247 341 195 277 346 316 332 356 369 597 70 122 12 23 190 22 199 224 76 207 151 183 225 252 345 235 282 349 321 337 359 370 608 71 123 22 65 12 64 2074 199 215 161 193 246 274 349 242 345 353 327 343 368 372 619 72 124 64 75 23 75 215 118208 224 168 233 253 281 353 304 350 358 330 363 371 375 62 10 73 125 742 65 117223 191 216 232 175 240 275 303 357 341 354 362 333 366 373 377 63 1111116 116 74 190 231 231 223 239 182 302 280 340 361 361 357 365 336 376 374 378 武汉科技学院：郑仟，李柏勋，陈军旗 2006 年全国研究生数学建模竞赛一等奖12 个，4 个老师面试学生的数量为 64 个，24 个老师面试学生数量的方差为 0.145, 所以该方案很好地满足了 Y1 的要求。 2）对于 Y2，因为从 M 个老师中挑选 4 个的全排列就已经排除了完全相同的 情况，所以该方案也满足了 Y2 的要求。 3）对于 Y3，从假设