LP管理运筹学.pptVIP

管理运筹学 (OR) (美Operations Research) §1 运筹学的产生和发展 运筹学是运用筹划的科学， 原意“作战研究”或“运用研究”。 基本思想：田忌赛马 齐王 田忌 齐王 田忌  上 上 上 上 中 中 中 中 下 下 下 下 实力 结果  “史记·高祖本纪”中刘邦语：“夫运筹帷幄之中，决胜于千里之外”。 1914年兰彻斯特战斗方程；1917年爱尔朗的排队论公式。 作为一种科学，运筹学产生于第二次世界大战。·39年英国成立了世界上第一个运筹学工作小组，从事防空预警系统的研制（研究如何合理运用雷达），使原先平均击落一架敌机要发20000发炮弹改善为只要发4000发炮弹·42年美国成立运筹学工作小组，研究战斗行动效能，行动方式·战争结束，Mores和Kimball合著第一部运筹学专著“运筹学的方法”·战后，运筹学的应用领域从军事扩展到其它各领域·我国50年代引入运筹学·由于计算机的发展和大系统的要求，越来越重视定性定量相结合、人机交互算法。 §2 运筹学的性质和内容 性质： 追求的目标是整个组织或系统的最佳行动路线 强调定量的手法 以软科学研究软系统，定性与定量相结合，多学科交叉 分支： ·规划论——线性规划、目标规划、非线性规划、整数规划、动态规划、组合规划等 ·图与网络 ·存储论 ·排队论 ·对策论 ·决策论 ·仿真 ·马尔科夫过程 ·可靠性 多目标规划  …… §3 运筹学的工作步骤 (1). 提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数； (2). 建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来； (3). 求解。用各种手段( 主要是数学方法，也可用其他方法 )将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出； (4). 解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反应现实问题； (5). 解的控制。通过控制解的变化过程决定对解是否要作一定的改变； (6). 解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。 §4 本课程的要求 二. 线性规划 (LP )( Linear Programming) 第一章 线性规划与单纯形法 1947年由美国空军G.B.Dantzig提出。 1．1 问题的提出 复习线性代数内容: 列向量 x=(x1，x2，…，xn）T为n维列向量。x?Rn 行向量 x=(x1，x2，…，xn）为n维列向量。x?Rn 矩阵(向量)运算规则 加减乘、求逆运算 结合律 分配律 交换律 乘法无交换律 线性相关 一组向量v1,…,vn,如果有一组不全为零的 系数α1, …,αn,使得: α1 v1+…+αnvn=0 则称v1,…,vn 是线性相关的. 线性无关 一组向量v1,…,vn,如果对于任何数α1,…,αn, 若要满足: α1 v1+…+αnvn=0 ,则必有系数 α1=…=αn=0,(全为零)则称v1,…,vn线性无关. 矩阵A的秩 设A为一个m×n阶矩阵(mn)若矩阵中最大线性 无关列向量个数为k,则称矩阵A的秩为k,记 为rank(A)=k. * (英 Operational Research) 一、 绪论 本部分是课程的最重要部分 §1 线性规划问题及其数学模型 利润最大 目标函数 max z = 2x1+ 3x2 x1 x2 0 4 Q2(4,2) Q1 Q3 Q4 4x1=16 4x2=12 x1+2x2=8 2x1+3x2=0 3 Q2 线性规划问题解的存在情况： (1