运筹学第1章线性规划--中后段.pdf

运筹学通论 第一章 线性规划 ℵℵℵ© 2006- 2013年3月20 日星期三 5.单纯形法:典则问题 • 线性规划之父——丹齐克 • 单纯形算法于1947年由美国数学家丹齐克(George B.Dantzig)所发明，源于军事目的。 • 在第二次世界大战期间，丹齐克就在美国空军的一 个小组从事资源分配和计划编制的工作。大战以后， 他回到伯克利加州大学，取得了博士学位。1947年 他成为美国空军审计长的数学顾问，从事计划工作 机械化的研究。主要工作是按成本——效果分配空 军的人力、经费、飞机等资源。 5.单纯形法:典则问题 • 丹齐克对于历史上一些重要方法作了总结 • 第二次世界大战初，为研究雷达在实战中的有效使用，英国 皇家空军于1939年吸收多个学科的专家建立了最早的运筹学 研究小组。1940年成立由著名物理学家P.M.S.布莱克特领导 的英国防空指挥研究小组，对机载雷达发现船只、潜艇等作 战问题进行研究。通过改变深水炸弹的爆炸深度，使皇家海 军空军摧毁敌方潜艇的成功率分别增加了3倍、 6倍。 • 此后,英国的陆军、海军也都相继设立了运筹分析机构，专门 从事军事运筹的理论和应用研究。 • 美国的运筹分析工作开始于1940年。1942年成立了由P.M.莫 尔斯领导的美国海军反潜战运筹小组，主要研究反潜作战效 果等问题。如1943年的研究表明，使用B-29飞机夜间单机布 雷效果最好，飞机损失率由10％～15%降低到1％～1.5%。 • 第二次世界大战期间，加拿大军队中也建立了运筹组织。至 战争结束时，英、美、加三国的军事运筹人员总数已超过 700人。 • 1945年，苏联学者A.H. 柯尔莫哥洛夫提出了多发齐射毁伤目 标的火力运用理论。 5.单纯形法:典则问题 • 前人的工作给丹齐克极大的启发，但其中能直接用于线性规 划的结果不多。 • 1947年初，丹齐克拜访了经济学家柯普曼，从他那里知道线 性规划问题还没有一种有效的、通用的算法，加强了发明新 理论的决心。 • 这年夏天，丹齐克就研究从 “线性规划问题可行区域凸多面 体”的一个顶点出发，沿着凸多面体的棱，走向目标函数值 更优的下一个顶点的方法。凸多面体 “单纯分割”为一个个 “单纯形”以后，属于同一单纯形的两个顶点称为相邻的顶 点。丹齐克的单纯形算法，通过一种矩阵表格的运算，提供 了从一个顶点走向相邻顶点中目标函数值最优的顶点的方法。 • 故此，单纯形算法诞生了。 5.单纯形法:典则问题 • 我们先从一例看看丹齐克的单纯形算法 • 例5.1 max{f=f(x) 3x +4x } 1 2 • S.t. x +2x ≤6 1 2 • 3 x +2x ≤12 1 2 • x ≤2 2 • x ≥0,x ≥0 1 2 • 化成标准型为 • min{f’ -f(x) -3 x -4x } =min{f’ 0- (3x +4x )} 1 2 1 2 • s.t. x +2x +x 6 1 2 3 • 3 x +2x +x 12