运筹学--线性规划与单纯形法.ppt

运 筹 学 教师：赵玮 电话： 引言 数学要求 课程的地位与作用 运筹学概要 线性规划(LP) 问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析 线性规划(LP) 问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析 线性规划(LP) 问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析 线性规划(LP) 问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析 线性规划(LP) 问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析 问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析 线性规划(LP) 问题与建模 二维线性规划图解法 计算机解法 极小化下的求解与大M法 灵敏度分析 对偶规划 LP求解步骤与OR软件包操 建模与案例分析 2. 线性整数规划 基本概念 定义 研究概况 分支定界法的理论与算法 基本思想 算法与判别准则 线性规划 人力资源分配的问题 例1. 某昼夜服务的工交公交线路每天各时间段内所需司机和乘务人员数如下： xi： 实际安排司乘人员数 设司机和乘务人员分别在各时间段一 开始时上班，并连续工作八小时，问该公 交线路怎样安排司机和乘务人员，既能满 足工作需要，又配备最少司机和乘务员？ 解：设xi表示第i班次时开始上班的司 机和乘务人员数，这样可以知道在第i班 工作的人数应包括第i-1班次时开始上班的 人员数和第班次时开始上班的人员数，例 如有x1 +x2≥70。又要求这六个班次时开 始上班的所有人员最少，既要求x1 +x2 +x3+x4 +x5 +x6最小，这样建立如下的数 学模型： 目标函数：min z = (x1 +x2 +x3+x4 +x5 +x6) 约束条件： 生产计划决策 例2. 某工厂在计划内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A,B两种原材料的消耗，以及资源的限制，如下表所示。 可以用x1和x2的线性函数形式来表示工 厂所要求的最大利润的目标： max z=50x1+100x2 其中max为最大化的符号（最小化符号为 min)；50和100分别为单位产品Ⅰ、Ⅱ的利 润。上式称为目标函数。同样也可以用x1和x2 的线性不等式来表示问题的一些约束条件。 对于台时数方面的限制可以表示为： x1+x2≤300. 同样，原材料的限量可以表示为 2x1+2x2≤400 x2≤250 暂不考虑市场需求。该工厂每生产一单位 产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获 利100元，问工厂应分别生产多少个Ⅰ产品和 Ⅱ产品才能使工厂获利最多？ 这个问题可以用以下的数学模型来加以描 述。工厂目前要决策的问题是生产多少个Ⅰ产 品和Ⅱ产品，把这个要决策的问题用变量x1、 x2来表示，则称x1和x2为决策变量，即决策变 量x1=生产Ⅰ产品的数量，决策变量x2 =生产Ⅱ 产品的数量。 除了上述约束外，显然还应该有x1≥0， x2≥0， 因为Ⅰ产品、Ⅱ产品的产量是不能取负值的。综上 所述，就得到了例1的数学模型如下： 目标函数：max z=50x1+100x2 满足约束条件： 问题与建模 模型：对真实系统的结构与行为用图、解析式或方程来描述的合称为模型。 预测模型 评价模型 优化模型 仿真模型 例1. 生产计划决策 max z=50x1+100x2 xj生产产品j的数量 例2. 人力资源分配问题决策 min z = (x1 +x2 +x3+x4 +x5 +x6) xj：第j个班次司乘人员数 LP四要素 s.t ：subject约束条件 z称为目标函数 xj称为决策变量 max或min成为优化准则 LP def1： 若目标函数z为决策变量xj的线性函数，约束条件亦为决策变量xj的线性不等式（或等式），则该数学表达式（模型）称为线性规划。若目标与约束中至少有一为非线性时，则该模型称为非线性模型（NLP）。 模型的标准化 标准化LP模型的