下载掌阅APP，畅读海量书库
立即打开
1 有4个工人，要指派他们分别完成4种工作，每人做各种工作所消耗的时间如表1-1-1所示，问指派哪个人去完成哪种工作，可使总的消耗时间为最小？ [北京邮电大学2018研]
表1-1-1
解： （1）先对各行减去本行的最小元素，再对各列减去本列最小元素，得到矩阵C如下：
（2）确定独立零元素，对C加圈，得到
（3）由于只有3个独立零元素，少于系数矩阵阶数n＝4，故需要确定能够覆盖所有零元素的最少直线数目的集合。结果如下：
（4）在未被覆盖的元素中找最小元素，未被覆盖的行分别减去该最小元素，在出现负数的列上整列加上最小元素，得到新矩阵C′：
（5）对其加圈，得到：
（6）同样发现独立零元素个数小于阶数，重复步骤（3）、（4），可得最终加圈矩阵C″：
或
最优指派方案有两种：
① 甲－A，乙－D，丙－C，丁－B
② 甲－B，乙－A，丙－C，丁－D
最小总消耗时间均为70。
2 图1-1-1中每条边上的数字表示边的长度（单位：公里），求点A到点G的最短路径（写出过程）。 [中山大学2019研]
图1-1-1
解： 将最短路问题分为4个阶段，第一阶段状态为A，第二阶段状态为B、C，第三阶段状态为D，第四阶段状态为E、F。采用逆序算法：
当k＝4时，f 4 （E）＝276，f 4 （F）＝186；
当k＝3时，f 3 （D）＝min{d（D，E）＋ f 4 （E）， d（D，E）＋ f 4 （F）}＝min{58＋276，110＋186}＝296，路径为D→F→G；
当k＝2时，f 2 （B）＝min{d（B，E）＋ f 4 （E）， d（B，D）＋ f 3 （D）}＝min{300＋276，350＋296}＝576，路径为B→E→G；
f 2 （C）＝ d（C，D）＋ f 3 （D）＝241＋296＝537，路径为C→D→F→G；
当k＝1时，f 1 （A）＝min{ d（A，B）＋ f 2 （B）， d（A，C）＋ f 2 （C）}＝min{404＋576，479＋537}＝980，路径为A→B→E→G
∴点A到点G的最短路径为A→B→E→G，共980公里。
3 某地铁入口设有一个安检处，所有旅客需进行安检，假设旅客到达服从Poisson分布，平均到达速率为300人/小时，检查时间服从负指数分布，平均检查时间为10秒/人。
（1）求安检处空闲的概率；
（2）求安检处有2个或2个以上旅客的概率；
（3）若某时刻安检处有一旅客A到达（此时安检处无其他旅客），10秒钟后一旅客B到达，此时A仍在检查中，求旅客A在安检处的平均逗留时间。 [中山大学2019研]
解： 该系统为M/M/1模型，λ＝300，μ＝3600/10＝360，ρ＝λ/μ＝300/360＝5/6
（1）空闲的概率P 0 ＝1－ρ＝1－5/6＝1/6
（2）P{N≥2}＝1－P（N＝0）－ P（N＝1）＝1－1/6－（1－5/6）×5/6＝25/36
（3）平均逗留时间W＝1/（μ－λ）＝1/（360－300）＝1/60（h）＝1 min
4 线性规划问题
（1）求解以下线性规划问题。
（2）最优解的松弛变量和剩余变量的值是多少？ [中山大学2019研]
解： （1）用单纯形法，加入松弛变量x 1 ，x 2 ，x 3 ，化为标准型如下：
由线性规划问题的标准型可列出单纯初始形表并逐步迭代，计算结果如表1-1-2所示。
表1-1-2
最优解为：A * ＝18/7，B * ＝15/7，最优值为87/7。
（2）无剩余变量，松弛变量值为x 1 ＝0，x 2 ＝0，x 3 ＝4/7。