当前位置: 首页 > >

管理运筹学课件第2章线性规划-精品文档_图文

发布时间:

第2章 线性规划 教学目标与要求 ? ? ? 【教学目标】 通过对本章的学*,理解线性规划的含义、解、可行解、可行域、基 解、基可行解、最优解的定义;掌握图解法、单纯形法(包括大M 法);会建立线性规划数学模型;至少掌握一种软件求解LP 【知识结构】 LP 基本概念与实际问题建模 图解法(2 个变量) 知 识 目 标 理 论 解 法 单纯形法(无人工变量) 大 M 法(有人工变量) 技 能 目 标 计算机解法(Lingo,WinQSB 或 Excel) 2019/3/13 课件 2 导入案例——最优生产计划 2019/3/13 课件 3 本章主要内容 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2.1 线性规划问题与模型 2.1.1 线性规划问题的提出 2.1.2 线性规划的数学模型 2.1.3 线性规划标准模型 2.2 图解法 2.2.1 线性规划几何解的有关概念 2.2.2 图解法基本步骤 2.2.3 线性规划几何解的讨论 2.3 单纯形法 2.3.1 线性规划解的有关概念及性质 2.3.2 单纯形法 2.4 人工变量法 2.5 线性规划应用举例 案例2-1 媒体选择问题 案例2-2 投资计划问题 案例2-3 自制/外购决策问题 案例2-4 合理下料问题 本章小结 课件 4 2019/3/13 2.1.1 线性规划问题的提出 承导入案例 产品甲 产品乙 生产能力 设备A 设备B 单位利润 2 1 3 1 1 2 10 8 决策变量 (decision variable) 目标函数 (objective function) 约束条件 (subject to) 设两种产品产量为x1,x2,则有: 最大化 设备A台时占用 m a x z ? 3 x1 ? 2 x 2 三要素 总利润表达式 ? 2 x1 ? x 2 ≤ 1 0 设备B台时占用 s . t . ? ? x1 ? x 2 ≤ 8 ?x ,x ≥ 0 产量非负 ? 1 2 2019/3/13 生产能力,不 允许超过 当目标函数与约束条件均为决策变 量的线性函数,且变量取连续值时, 称为线性规划LP;变量取整称为整 数线性规划ILP;变量取二进制为 0-1规划BLP。 课件 5 2.1.2 线性规划的数学模型 【例2.1】(合理配料问题)由下表建立一个LP模型求解满足动物成长 需要又使成本最低的饲料配方。 饲料 1 2 3 4 5 营养甲(g/kg) 0.5 2 3 1.5 0.8 营养乙(g/kg) 0.1 0.06 0.04 0.15 0.2 营养丙(g/kg) 0.08 0.7 0.35 0.25 0.02 成本(g/kg) 2 6 5 4 3 解 设xi为第i种饲料的用量,有: m i n26543 z ????? x 目标是总成本最低 1 x 2 x 3 x 4 x 5 ? 0 . 5 0 x ? 2 . 0 0 x ? 3 . 0 0 x ? 1 . 5 0 x ? 0 . 8 08 x ≥ 5 满足营养甲需求 1 2 3 4 5 ? 满足营养乙需求 ? 0 . 1 0 x ? 0 . 0 6 x ? 0 . 0 4 x ? 0 . 1 5 x ? 0 . 2 05 x ≥ 1 2 3 4 5 s .t . ? 满足营养丙需求 . 0 8 x ? 0 . 7 0 x ? 0 . 3 5 x ? 0 . 2 5 x ? 0 . 0 2 x ≥ 1 8 ? 0 1 2 3 4 5 ?? x≥ 0 ( j? 1 , 2 , 3 , 4 , 5 ) 变量非负限制 j 课件 6 2019/3/13 2.1.2 线性规划的数学模型 线性规划的一般形式: 线性规划的向量形式 : m ax(m in)z ? c1x1 ?c2x2 ? ?cnxn ?a1nxn ≤(或≥ ,) ? b ?a 11x 1 ?a 12x 2 ? 1 ? ,) ? b2 ?a21x1 ?a22 x2 ? ?a2nxn ≤(或≥ st . .? ? ?a x ?a x ? ?a x ≤(或≥ ,) ? bm m n n ? m1 1 m2 2 线性规划的集合形式 : Max(Min)Z ? ?c j x j j ?1 n M a x ( M in ) Z ? ?c j ?1 n j xj ? n ≥)b ? ? p j x j ≤ (或 ? , s .t . ? j ? 1 ? x ≥ 0 ( j ? 1, 2 , , n ) ? j 线性规划的矩阵形式 : Max(Min)Z ? CX , m) ? ≥)bi (i ? 1,2, ??aij x j ≤(或 ? , s.t. ? j ?1 ?x ≥0( j ? 1,2, , n) ? j n ≥)b ?AX ≤(或 ? , s.t. ? ?X ≥0 7 2019/3/13 课件 2.1.3 线性规划的标准模型 标准形式: 目标函数最大化、约束条件为等式、决策变量均非负、右端项非负. 非标准形式进行如下转化: 2019/3/13 课件 8 2.1.3 线性规划的标准模型 【例2.2】将LP模型转化为标准式 m in z ? 3 x1 ? 5 x 2 ? x 3 ≤9 ? ? x1 ? x 2 ??2 x ? x ? 3x ≥ 4 ? 1 2 3 s .t . ? ? 3 x1 ? 2 x 2 ? x 3 ≥ ? 6 ? ? x1 ≤ 0, x 2 ≥ 0, x 3 无 约 束 解 (1)决策变量变为非负 ? ?≥ 令 :x ? x ,x 0 1? 1 ? x ? ? ?≥ ? ? 0 x x ,x 0 ,x 3? 3? 3 3 3≥ ? ? x3 ? min z ? ? 3 x1? ? 5 x2 ? x3 ≤9 ? x1? ? x2 ? 2 x ? ? x ? 3 x ? ? 3 x ?



友情链接: