逍遥学能 2014-09-13 08:39
约翰逊先生在户外有个炙肉架，正好能容纳2片炙肉。他的妻子和女儿贝特西都饥肠辘辘，急不可耐。问怎样才能在最短时间内炙完三片肉。
“约翰逊先生“瞧，炙一片肉的两面需要20分钟，因为每一面需要10分钟。我可以同时炙两片，所以花20分钟就可以炙完两片。再花20分钟炙第三片，全部炙完需要40分钟。”
“贝特西“你可以更快些，爸爸。我刚算出你可以节省10分钟。”
“啊哈!贝特西小姐想出了什么妙主意?
“为了说明贝特西的解法，设肉片为A，B，C。每片肉的两面记为1，2。第一个10分钟炙烤A1，和B1。把B肉片先放到一边。再花10分钟炙烤A2和C1。此时肉片A可以炙完。再花10分钟炙烤B2和C2，仅花30分钟就炙完了三片肉，对吗?
“这个简单的组合问题，属于现代数学中称之为运筹学的分枝。这门学科奇妙地向我们揭示了一个事实如果有一系列操作，并希望再最短时间内完成，统筹安排这些操作的最佳方法并非马上就能一眼看出。初看是最佳的方法，实际上大有改进的余地。在上述问题中，关键在于炙完肉片的第一面后并不一定马上去炙其反面。
“提出诸如此类的简单问题，可以采用多种方式。例如，你可以改变炙肉架所能容纳肉片的数目，或改变待炙肉片的数目，或两者都加以改变。另一种生成问题的方式是考虑物体不止有两个面，并且需要以某种方式把所有的面都予以“完成”。例如，某人接到一个任务，把”n”个立方体的每一面都涂抹上红色油漆，但每个步骤只能够做到把”k”个立方体的顶面涂色。
“今天，运筹学用于解决事物处理，工业，军事战略等等许多领域的实际问题。即使是像炙肉片这样简单的问题也是有意义的。为了说明这一点，请考虑下列一些变相问题
“琼斯先生和夫人有三件家务事要办。
“1．用真空吸尘器清洁一层楼。只有一个真空吸尘器，需要时间30分钟。
“2．用割草机修整草地。只用一台割草机，需要时间30分钟。
“3．喂婴儿入睡，需要时间30分钟。
“他们应该怎样安排这些家务，以求在最短时间内全部完成呢?你看出这个问题与炙肉片问题是同构的吗?假设琼斯先生和夫人同时进行操作，一般人开始往往以为做完这些家务需要60分钟。但是如果一件家务(譬如说用真空吸尘器做清洁工作)分为两个阶段，第二阶段延后进行(像炙肉片问题那样)，那么三件家务可以在3/4的时间内即45分钟内完成。
“下面有一个关于准备三片热涂奶油的烤面包问题。这个运筹学问题比较困难。烤面包架是老式的，两边各有一扇翼门，可以同时容纳两片面包，但是只能单面烘烤。如果要烤双面，需要打开翼门，把面包片翻过身来。
“将一片面包放入烤面包架需要时间3秒钟，取出来也需要3秒钟，将面包片在烤面包架内翻身又需要3秒钟。这些都需要双手操作，即不能同时进行放，取或把两片面包同时翻身，也不能在放入一片面包，将其翻身或取出的同时把另一片涂抹上奶油。单面烘烤一片面包需要30秒钟，把一片面包涂抹上奶油需要12秒钟。
“每片面包仅限于单面涂抹上奶油。未经烘烤不得事先在任何一面涂抹上奶油。单面已经烤过的和涂抹上奶油的面包片可以重新放入烤面包加内继续烘烤其另一面。如果烤面包架一开始就是热的，试问双面烘烤三片面包丙涂抹上奶油最少需要多少时间?
“在两分钟内完成上述工作并不太难。然而，如果你领悟到一片面包在单面烘烤尚未结束的情况下，也可以取出，以后再放回烤面包架内继续烘烤这一面，那么全部烘烤时间就可以缩减至111秒钟。使你想到这一点，统筹安排这些操作使效率达到最高也远非是一件易事。在这方面，尚有无数比此更为复杂的实际问题，需要借助于与计算机和现代图论有关的高度复杂的数学手段。