用VBA解决动态规划中的挤牛奶问题

用VBA解决动态规划中的挤牛奶问题 甘伟雄 (阳江广播电视大学，广东 阳江 529500) 摘 要:从一个故事出发，生动又图文并茂的解决算法中的复杂问题是一件很有趣的教学过程.在所有的计算机应用中，办公软件office使用最为广泛，VBA可以称作EXCEL的“遥控器”，图形并茂让算法研究变得不再枯燥无趣.利用excel中的规划求解高级应用作为显示和输出端，让学生充分掌握动态规划中的挤牛奶问题.经过多次在EXCEL的实践和仔细研究分析，通过程序设计和EXCEL的规划求解两种方法求解动态规划中的挤牛奶问题，挤牛奶问题是算法研究中难度比较大，技巧性比较强的多阶段决策最优化问题.通过程序设计和EXCEL中的规划求解充分理解动态规划的算法精髓，让人对算法研究的学习变得容易，两种方法相得益彰. 关键词:动态规划;挤牛奶问题;编程;规划求解 中图分类号:TP391.13 文献码:A 文章编号:1673-260X(2012)01-0075-02 问题从一个故事说起，小卡卡终于帮农夫John找到了走丢的那一头奶牛，John为了感谢小卡卡，不仅告诉了他在 Pascal山脉上可能存在Pascal圣地最大的宝藏，还说要请小卡卡喝牛奶.可是农夫John发现他家里所储藏的牛奶已经喝光了,所以要临时给奶牛挤奶.小卡卡实在是太好心了,说要帮农夫John一起挤牛奶.John答应了，他把他的n头奶牛中的n/2头(n是个偶数)分给小卡卡挤，他自己挤剩下的n/2头奶牛.但是每一头奶牛都有不同的产奶量,农夫John为了让小卡卡减轻负担,他希望他们两个所挤的牛奶的总量之差最小，产奶量的总和不超过200.小卡卡得知了每头奶牛的产奶情况之后很快就解决了这个问题.在一定的限制条件下，利用科学方法进行运算，使对前景的规划达到最优的方法，在现代管理科学有着重要使用价值，也是运筹学的一个分支.利用规划求解可以解决诸如产品1.组合问题2.配料问题3.下料问题4.物资调运问题5.任务分配问题6.投资效益问题7.合理布局问题等，这些应用在许多书籍和中有详细的介绍.“规划求解”是一组命令的组成部分，这些命令有时也称作假设分析中公式的最优值.“规划求解”将对直接或间接与目标单元格中公式相关联的一组单元格中的数值进行调整，最终在目标单元格公式中求得期望的结果.“规划求解”通过调整所指定的可更改的单元格(可变单元格)中的值，从目标单元格公式中求得所需的结果.在创建模型过程中，可以对“规划求解”模型中的可变单元格数值应用约束条件，而且约束条件可以引用其他影响目标单元格公式的单元格.算法研究和应用借道EXCEL中规划求解方面就不多见了，规划求解在解决动态规划问题有着奇妙的应用. 高校计算机专业教科书中已经比较完整的描述了动态规划问题，具体而言可以看作基本是将待求解问题分解成若干子问题，先求解子问题，最后用这些子问题带到原问题，与分治算法的不同是，经分解得到的子问题往往是不是相互独立，若用分治则子问题太多. 1 编程实现部分 假设产奶量的总和不超过200，X代表小卡卡选择的奶牛，Y代表农夫选择的奶牛，根据题意得出如下式子: 参考文献: 〔1〕严蔚敏.数据结构[M].清华大学出版社. 〔2〕余文芳.计算机应用基础[M].北京:人民邮电出版社，2004. 〔3〕王晓东.计算机算法设计与分析[M].电子工业出版社，2007. 〔4〕夏昕，曹晓刚，唐勇.深入浅出Hibernate[M].电子工业出版社，2007.