运筹学通论
胡晓东
应用数学研究所 中国科学院数学与系统科学研究院 北京2734信箱,北京100190 Http://www.amt.ac.cn/member/huxiaodong/
Institute of Applied Mathematics
1. 线性规划-食谱问题
我们人体每天需要一定量的两种维生素,Vc 和 Vb.假设 这些维生素可以分别从牛奶和鸡蛋中得到.
维生素 Vc(mg) Vb(mg) 单价(US$)
奶(g)中含 2x 3x 3x
蛋(g)中含 4y 2y 2.5 y
每日需求 40 50
需要确定每天喝奶的量 x 和吃蛋的量 y .目标是以最低 可能的花费购买这些食物,而满足最低限度的维生素需求量.
1. 线性规划-食谱问题(续一)
食谱问题可以写成如下的数学形式: Min 3x + 2.5y s.t. 2x + 4y ≥ 40 3x + 2y ≥ 50 x, y ≥ 0. 可行区域(单纯形) 可行解 极小化目标函数
运筹学工作者参与建立关于何时出现最小费用(或者最大利 润)的排序,或者计划,早期被标示为programs.求最优安排 或计划的问题,称作programming问题.
xdhu 3
1. 线性规划-食谱问题(续二)
y 50 40 30 3x+2y≥50 20 10 2x+4y≥40 0 (15, 2.5) 10 20 30 40
xdhu
可行区域的极点: (0, 25) (15, 2.5) 最优解 3x +2.5y (20, 0)
50
x
4
1. 线性规划-单纯形法
George Bernard Dantzig (1914 - 2005) 1947年在美国五角大楼工 作, Dantzig常常被空军要 求去解实际的计划问题: 分配空军的人力,经费, 飞机和其它资源.他给这 些问题建立了线性规划模 型(Linear Programming), 并提出著名的单纯形法 (Simplex Method).
xdhu 5
1. 线性规划-单纯形法(续一)
单纯形法的思想 第一步:找到一个可行解(极点); 第二步:计算该点的判据函数; 第三步:若无法改进,退出; 第四步:否则选择一条棱, 找到另一可行解(极点); 回到第二步.
xdhu
6
1. 线性规划-历史注记
在没有线性规划之前,无法清晰地表示一般的目标,因此 目标经常与为求解而设定的规则相混淆. 当我们询问军事指挥官他们的目标是什么的时候,他可能 会说:"目标就是赢得战争."若要求说得更详尽一些,海军 指挥官可能会回答:"赢得战争的方法就是制造战舰."而如 果他是一位空军将领,他可能会说:"赢得战争的方法就是建 立一支庞大的轰炸机队." 这样实现目标的手段就变成了目标本身,而这又引出关于 如何获得这些手段的基本规则,如怎样最佳地建立轰炸机队. 这些手段反过来又混淆了目标.
xdhu 7
1. 线性规划-历史注记(续一)
我记得我试图用很普通的语言向冯诺依曼描述空军的 问题的情形.我根据活动和项目等等条件给出了一个线性规划 模型. 他做了我相信不符合他性格的事情."切入正题."约尼 不耐烦地厉声对我说.当时我多少有些激动,我对自己说: "那好吧,如果他要简短的,那就是他想要的."不到一分钟, 我在黑板上随意地写出了问题的几何与代数形式. 冯诺依曼站起来了,说到:"噢,是这样!"在随后的一 个半小时的时间里,他给我做了一个关于线性规划数学理论的 演讲.
xdhu 8
1. 线性规划-历史注记(续二)
此刻,冯诺依曼看到我目瞪口呆地坐在那里(因为 我已经查过文献而一无所获),他说到:"我不希望你想象 我像一个魔术师一样,不假思索地把所有这些东西从我的袖 子里倒出来.我最近与Morgenstern完成了一本有关博弈论 的书.我刚刚所叙述的就是猜想这两个问题是等价的.我刚 才讲的理论与我们在博弈论中发展的一个理论极其相似." 于是从他那里我第一次学到了Farkas引理和对偶理论. 冯 诺依曼后来答应我再想想计算问题,并在几周内与我联 系.他提出了一个迭代的非线性方案.后来大约在1952年, Hoffman和他的研究小组在标准局用几个测试问题检验了一 下该方案.他们还将该方案与单纯形法以及Motzkin提出的 方法做了比较.结果证明单纯形法是一个明显的赢家.

下一页