中国矿业大学：《运筹学》课程教学课件（讲稿）Chapter 1 线性规划（Linear Programming）

运筹学线性规划Chapter1(LinearProgramming)本章主要内容：线性规划问题及其模型线性规划问题几何意义单纯形法单纯形法计算步骤单纯形法进一步讨论应用举例掌握Excel软件求解线性规划-1-?China University of Mining and Technology

-1- China University of Mining and Technology 运 筹 学 Chapter1 线性规划 (Linear Programming ) 线性规划问题及其模型 线性规划问题几何意义 单纯形法 单纯形法计算步骤 单纯形法进一步讨论 应用举例 掌握Excel软件求解线性规划 本章主要内容：

运筹学口线性规划是运筹学的一个重要分支，是研究较早、理论较完善、应用最广泛的一个学科。口由前苏联经济学家康托洛维奇于1939年提出，而此人也因此获得1960年的诺贝尔经济学奖。1947年，G.B.Dantzig(丹捷格）提出求线性规划的单纯形法，理论上趋向成熟，实际上的应用也越来越广泛。-2-后退退出一页质N贝ChinaUniversity of Mining and Technology+

-2- China University of Mining and Technology 运 筹 学 线性规划是运筹学的一个重要分支，是研究较早、理论较 完善、应用最广泛的一个学科。 由前苏联经济学家康托洛维奇于1939年提出，而此人也因 此获得1960年的诺贝尔经济学奖。 1947年，G.B.Dantzig （丹捷格）提出求线性规划的单纯形 法，理论上趋向成熟，实际上的应用也越来越广泛

运筹学线性规划所研究的问题主要包括两个方面：(如人力、物力、一是在一项任务确定后，如何以最低成本资金和时间等）去完成这一任务；二是如何在现有资源条件下进行组织和安排，以产生最大收益。因此，线性规划是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法。线性规划不仅仅是一种数学理论和方法，而且已成为现代管理工作中帮助管理者做出科学决策的重要手段。-3-退出页上一页下一页后退主ChinaUniversity of Mining and Technology

-3- China University of Mining and Technology 运 筹 学  因此，线性规划是求一组变量的值，使它满足一组线性 式子，并使一个线性函数的值最大（或最小）的数学方 法。  线性规划不仅仅是一种数学理论和方法，而且已成为现 代管理工作中帮助管理者做出科学决策的重要手段。 •线性规划所研究的问题主要包括两个方面： • 一是在一项任务确定后，如何以最低成本（如人力、物力、 资金和时间等）去完成这一任务； •二是如何在现有资源条件下进行组织和安排，以产生最大收益

运筹学第一章线性规划$1线性规划问题及其模型S2线性规划问题几何意义83上单纯形法84单纯形法计算步骤85 单纯形法进一步讨论86应用举例-4-后退退出一页NChina University of Mining and Technology

-4- China University of Mining and Technology 运 筹 学 第一章 线性规划 §1 线性规划问题及其模型 §2 线性规划问题几何意义 §3 单纯形法 §4 单纯形法计算步骤 §5 单纯形法进一步讨论 §6 应用举例

运筹学1.1问题的提出1.1问题的提出在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。我们先通过几个实际问题来认识什么是线性规划。-5-后退退出一页主页顶7China University of Mining and Technology

-5- China University of Mining and Technology 运 筹 学 1.1 问题的提出 在生产管理和经营活动中经常需要解决：如何合理地利用有限 的资源，以得到最大的效益。 我们先通过几个实际问题来认识什么是线性规划。 1 .1 问题的提出

运筹学1.1问题的提出利润最大化问题【例1]某企业生产A1,A2,A，三种产品，这些产品分别需要甲乙两种原料。生产每种产品一吨所需原料和每天原料总限量及（生产计划问题）每吨不同产品可获利润情况如表1.1所示。表1.1企业生产数据表产品+4AA原料总限量（吨）原料甲t212100K3134100*Z*利润千元/吨3474L试问：该企业怎样安排生产才会使每天的利润最大？-6-X退出页上一页下一页后退主China University of Mining and Technology

-6- China University of Mining and Technology 运 筹 学 【例1】 某企业生产 A1 , A2 , A3三种产品，这些产品分别需要甲、 乙两种原料。生产每种产品一吨所需原料和每天原料总限量及 每吨不同产品可获利润情况如表1.1所示。 （生产计划问题） 利润最大化问题 试问：该企业怎样安排生产才会使每天的利润最大？ 表1.1 企业生产数据表 1 .1 问题的提出

运筹学1．1问题的提出解设该企业每天生产产品 A,A,A的数量分别为 X,,x（单位：吨），则总利润的表达式为B我们希望在现有资源条件下总利润最大.现有资源的限制为（原料甲的限制）X（原料乙的限制）3B<x≥Q-23此外，由于未知数（我们称之为决策变量）X，x,x是计划产量应有为非负的限制，即产品4AA原料总限量（吨）原料甲21241003134100p利润千元/吨）437447-?退一页后退出主页页下ChinaUniversityofMining and Technology

-7- China University of Mining and Technology 运 筹 学 解 设该企业每天生产产品 的数量分别为 （单位：吨），则总利润的表达式为 f4x13x27x3 我们希望在现有资源条件下总利润最大.现有资源的限制为 x x x 1 2 3    2 2 100 （原料甲的限制） 3 3 100 x x x 1 2 3   （原料乙的限制） 此外，由于未知数（我们称之为决策变量） 是计划产量， 应有为非负的限制，即 1 2 3 x ,x ,x 1 2 3 x ,x ,x 1 2 3 A A A , , xj0,j1,2,3 1 .1 问题的提出

运筹学1．1 问题的提出由此得到问题的数学模型为max f = 4x, +3x2 +7xs.t. xj +2x2 +2x, ≤1003xi + X2 +3x ≤100x, ≥0 (j = 1,2,3)其中s.t.为英文“subject to”白的缩写，表示决策变量x;(i=1,2,3)受它后面的条件约束-8-米一页后退退出主页页NChina University of Mining and Technology

-8- China University of Mining and Technology 运 筹 学 由此得到问题的数学模型为 1 2 3 1 2 3 1 2 3 max 4 3 7 s.t. 2 2 100, 3 3 100, 0 ( 1, 2, 3). j f x x x x x x x x x x j            其中s.t.为英文“subject to”的缩写，表示决策变量xj (j=1,2,3) 受它后面的条件约束. 1 .1 问题的提出

运筹学1．1问题的提出线性规划模型的三要素决策变量：需决策的量，即待求的未知数；自标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；约束条件：为实现优化自标需受到的限制，用决策变量的等式或不等式表示。-9-后退退出一页主页顶7China University of Mining and Technology

-9- China University of Mining and Technology 运 筹 学 决策变量：需决策的量，即待求的未知数； 目标函数：需优化的量，即欲达的目标，用决策变量的表达式 表示； 约束条件：为实现优化目标需受到的限制，用决策变量的等式 或不等式表示。 线性规划模型的三要素 1 .1 问题的提出

运筹学1.1问题的提出成本最小化问题【例2]】某钢铁厂熔炼一种新型不锈钢，需要4种合金TT,T,T4为原料经测定这4种原料关于元素铬（Cr）、锰(Mn)和镍（Ni）的质量分数（%）、单价以及这种新型不锈钢所需铬、锰和镍的最低质量分数，情况如表1.2所示.假设熔炼时质量没有损耗，问：要熔炼100吨这样的不锈钢，应选能够使成本最小？用原料T,T,T,T4各多少吨，-11--后退退出一页顶NChina University of Mining and Technology+

-11- China University of Mining and Technology 运 筹 学 成本最小化问题 【例2】 某钢铁厂熔炼一种新型不锈钢，需要4种合金 T1T2T3T4为原料经测定这4种原料关于元素铬（Cr）、锰 （Mn）和镍（Ni）的质量分数（%）、单价以及这种新型不 锈钢所需铬、锰和镍的最低质量分数，情况如表1.2所示. 假设 熔炼时质量没有损耗，问：要熔炼100吨这样的不锈钢，应选 用原料T1T2T3T4各多少吨，能够使成本最小？ 1 .1 问题的提出