第1章线性规划要点解析.ppt

运 筹 学Operational Research 运筹帷幄，决胜千里 ?史记《张良传》 绪 论 一、运筹学的起源与发展 二、运筹学的特点及研究对象 三、运筹学解决问题的方法步骤 四、运筹学的发展趋势 一、运筹学的起源与发展 起源于二次大战的一门新兴交叉学科 与作战问题相关 如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等 英国称为 Operational Research 美国称为 Operations Research 战后在经济、管理和机关学校及科研单位继续研究 1952年，Morse 和 Kimball出版《运筹学方法》 1948年英国首先成立运筹学会 1952年美国成立运筹学会 1959年成立国际运筹学联合会(IFORS) 我国于1982年加入IFORS，并于1999年8月组织了第15届大会 三、运筹学解决问题的方法步骤 明确问题 建立模型 设计算法 整理数据 求解模型 评价结果 第一章 线性规划与单纯形法 一、线性规划问题举例 例1.1 生产计划问题（Max, ?） 例1.2 配料问题（Min, ≥） 某公司打算利用甲、乙、丙三种原料配置一种新型保健饮料，已知每千克原料中两种主要保健成分A、B的含量及原料单价如表1-2所示。 二、线性规划的模型结构：  线性规划问题的共同特点： （1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值； （2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示； （3）有一个需要优化的目标，它也是变量的线性函数。 具备以上三个特点的数学模型称为线性规划（Linear Programming，简记为LP） 线性规划解的概念 例1.7 练习1 第二节 线性规划的标准形式和解的性质 一、LP的标准形式 变换一般LP为标准形式的方法： 例1.9：将下列线性规划问题化为标准形式 二、LP的基可行解的概念 线性规划标准型问题解的关系 可行解、基本解和基本可行解举例 §1.3 单纯形法 单纯形方法的解题思路 单纯形要点和单纯形表 单纯形法的补充说明 第二次换基迭代：选 x2入基 约束方程： 第三次换基迭代：选 x1入基 单纯形法是一种迭代算法，其步骤总结如下： 二、单纯形要点和单纯形表 1. 检验数的意义和计算公式 ①用非基变量表示基变量的表达式 3. 单纯形法的基本法则 法则2 换入变量确定法则 设 则xk为换入变量。 法则3 换出变量确定法则 最小比所在行的原基变量xl为换出变量 法则4 换基迭代运算法则 按照主元素进行矩阵的初等行变换——把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量） 练习 三、关于单纯形法的补充说明 1. 无穷多最优解与唯一最优解的判别法则 若对某可行解X1， （1）所有检验数σj≤0，且有一个非基变量xk的检验数等于0，则问题有无穷多最优解； （2）所有非基变量的检验数σj0，则问题有唯一最优解。 例1.13 讨论线性规划 2. 无最优解（无界解）的判定 若对基可行解X1，存在非基变量xk的检验数σk0，但aik≤0，i=1，2，…，m。即xk的系数列向量无正分量，则问题无最优解。 c 4 1 0 0 0 cB xB b x1 x2 x3 x4 x5 ? 0 x3 2 -1 1 1 0 0 -- 0 x4 4 1 -4 0 1 0 4 0 x5 8 1 -2 0 0 1 8 σj 4 1 0 0 0 3.求min z 的情况 两种处理方式： （1）令z1=-z，转化为标准形式求max z1； （2）直接计算 第四节 初始可行基的求法 一、大 M 法 基本思想 引入人工变量，人为的地构造一组初始基变量； 在目标函数中赋予人工变量很大的罚系数 M； 用线性规划的优化机制迫使人工变量出基，