运筹学通论.pdf

运筹学通论 胡晓东 应用数学研究所 中国科学院数学与系统科学研究院 北京100190 Http:///member/huxiaodong/ Institute of Applied Mathematics 1. 线性规划-食谱问题 我们人体每天需要一定量的两种维生素，Vc 和 Vb 。假设 这些维生素可以分别从牛奶和鸡蛋中得到。 维生素 奶(g) 中含 蛋(g) 中含 每日需求 Vc(mg) 2 x 4 y 40 Vb(mg) 3 x 2 y 50 单价(US$) 3 x 2.5 y 需要确定每天喝奶的量x 和吃蛋的量 y 。目标是以最低 可能的花费购买这些食物，而满足最低限度的维生素需求量。 1. 线性规划-食谱问题 （续一） 食谱问题可以写成如下的数学形式： Min 3x + 2.5y 极小化目标函数 s.t. 2x + 4y ≥40 3x + 2y ≥50 可行区域（单纯形） x , y ≥0. 可行解 运筹学工作者参与建立关于何时出现最小费用（或者最大利 润）的排序，或者计划，早期被标示为programs 。求最优安排 或计划的问题，称作programming 问题。 xdhu 3 1. 线性规划-食谱问题 （续二） 可行区域的极点： y (0, 25) 50 (15, 2.5) 最优解 40 3x +2.5y (20, 0) 30 3x+2y ≥50 20 10 (15, 2.5) 2x+4y ≥40 0 x 10 20 30 40 50 xdhu 4 1. 线性规划-单纯形法 George Bernard Dantzig (1914 - 2005) 1947年在美国五角大楼工 作， Dantzig常常被空军要 求去解实际的计划问题： 分配空军的人力、经费、 飞机和其它资源。他给这 些问题建立了线性规划模 型(Linear Programming) ， 并提出著名的单纯形法 (Simplex Method) 。 xdhu 5 1. 线性规划-单纯形法 （续一） 单纯形法的思想 第一步：找到一个可行解（极点）； 第二步：计算该点的判据函数； 第三步：若无法改进，退出； 第四步：否则选择一条棱， 找到另一可行解（极点）； 回到第二步。