《运筹学ppt课件Ch1线性规划》由会员分享，可在线阅读，更多相关《运筹学ppt课件Ch1线性规划（97页珍藏版）》请在金锄头文库上搜索。
1、 运筹学OperationsResearch Chapter1线性规划LinearProgramming 1 1LP的数学模型MathematicalModelofLP1 2图解法GraphicalMethod1 3标准型StandardformofLP1 4基本概念BasicConcepts1 5单纯形法SimplexMethod 1 1数学模型MathematicalModel 2020 2 9 1 1线性规划的数学模型MathematicalModelofLP 线性规划 LinearProgramming 缩写为LP 通常研究资源的最优利用 设备最佳运行等问题 例如 当任务或目标确定后
2、如何统筹兼顾 合理安排 用最少的资源 如资金 设备 原标材料 人工 时间等 去完成确定的任务或目标 企业在一定的资源条件限制下 如何组织安排生产获得最好的经济效益 如产品量最多 利润最大 2020 2 9 例1 1 生产计划问题 某企业在计划期内计划生产甲 乙两种产品 按工艺资料规定 每件产品甲需要消耗材料A2公斤 消耗材料B1公斤 每件产品乙需要消耗材料A1公斤 消耗材料B1 5公斤 已知在计划期内可供材料分别为40 30公斤 每生产一件甲 乙两产品 企业可获得利润分别为300 400元 如表1 1所示 假定市场需求无限制 企业决策者应如何安排生产计划 使企业在计划期内总的利润收入最大 1
3、1线性规划的数学模型MathematicalModelofLP 1 1 1应用模型举例 2020 2 9 解 设x1 x2分别为甲 乙产品的产量 数学模型为 1 1线性规划的数学模型MathematicalModelofLP 表1 1 2020 2 9 线性规划的数学模型由 决策变量Decisionvariables目标函数Objectivefunction及约束条件Constraints构成 称为三个要素 其特征是 1 解决问题的目标函数是多个决策变量的线性函数 通常是求最大值或最小值 2 解决问题的约束条件是一组多个决策变量的线性不等式或等式 怎样辨别一个模型是线性规划模型 1 1线性规划
4、的数学模型MathematicalModelofLP 2020 2 9 例1 2 某商场决定 营业员每周连续工作5天后连续休息2天 轮流休息 根据统计 商场每天需要的营业员如表1 2所示 表1 2营业员需要量统计表 商场人力资源部应如何安排每天的上班人数 使商场总的营业员最少 1 1线性规划的数学模型MathematicalModelofLP 2020 2 9 解 设xj j 1 2 7 为休息2天后星期一到星期日开始上班的营业员 则这个问题的线性规划模型为 1 1线性规划的数学模型MathematicalModelofLP 2020 2 9 例1 3 合理用料问题 某汽车需要用甲 乙 丙三种
5、规格的轴各一根 这些轴的规格分别是1 5 1 0 7 m 这些轴需要用同一种圆钢来做 圆钢长度为4m 现在要制造1000辆汽车 最少要用多少圆钢来生产这些轴 解 这是一个条材下料问题 设切口宽度为零 设一根圆钢切割成甲 乙 丙三种轴的根数分别为y1 y2 y3 则切割方式可用不等式1 5y1 y2 0 7y3 4表示 求这个不等式关于y1 y2 y3的非负整数解 象这样的非负整数解共有10组 也就是有10种下料方式 如表1 3所示 表1 3下料方案 1 1线性规划的数学模型MathematicalModelofLP 2020 2 9 设xj j 1 2 10 为第j种下料方案所用圆钢的根数 则
6、用料最少数学模型为 求下料方案时应注意 余料不能超过最短毛坯的长度 最好将毛坯长度按降的次序排列 即先切割长度最长的毛坯 再切割次长的 最后切割最短的 不能遗漏了方案 如果方案较多 用计算机编程排方案 去掉余料较长的方案 进行初选 1 1线性规划的数学模型MathematicalModelofLP 2020 2 9 1 1 2线性规划的一般模型一般地 假设线性规划数学模型中 有m个约束 有n个决策变量xj j 1 2 n 目标函数的变量系数用cj表示 cj称为价值系数 约束条件的变量系数用aij表示 aij称为工艺系数 约束条件右端的常数用bi表示 bi称为资源限量 则线性规划数学模型的一般表
7、达式可写成 为了书写方便 上式也可写成 1 1线性规划的数学模型MathematicalModelofLP 2020 2 9 在实际中一般xj 0 但有时xj 0或xj无符号限制 1 1线性规划的数学模型MathematicalModelofLP 2020 2 9 1 什么是线性规划 掌握线性规划在管理中的几个应用例子2 线性规划数学模型的组成及其特征3 线性规划数学模型的一般表达式 作业 教材习题1 1 1 6 1 1线性规划的数学模型MathematicalModelofLP 下一节 图解法 1 2图解法GraphicalMethod 2020 2 9 x1 x2 O 10 20 30 4
8、0 10 20 30 40 300 400 15 10 最优解X 15 10 最优值Z 8500 例1 7 1 2图解法TheGraphicalMethod 2020 2 9 2 4 6 x1 x2 2 4 6 最优解X 3 1 最优值Z 5 3 1 minZ x1 2x2 例1 8 1 2 1 2图解法TheGraphicalMethod 2020 2 9 2 4 6 x1 x2 2 4 6 X 2 3 1 X 1 1 3 5 5 minZ 5x1 5x2 例1 9 有无穷多个最优解即具有多重解 通解为 0 1 当 0 5时 x1 x2 0 5 1 3 0 5 3 1 2 2 1 2图解法T
9、heGraphicalMethod 2020 2 9 2 4 6 x1 x2 2 4 6 1 2 无界解 无最优解 maxZ x1 2x2 例1 10 1 2图解法TheGraphicalMethod 2020 2 9 x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解即无最优解 maxZ 10 x1 4x2 例1 11 1 2图解法TheGraphicalMethod 2020 2 9 由以上例题可知 线性规划的解有4种形式 1 有唯一最优解 例1 7例1 8 2 有多重解 例1 9 3 有无界解 例1 10 4 无可行解 例1 11 1 2情形为有最优解3
10、 4情形为无最优解 1 2图解法TheGraphicalMethod 2020 2 9 图解法的步骤 1 求可行解集合 分别求出满足每个约束包括变量非负要求的区域 其交集就是可行解集合 或称为可行域 2 绘制目标函数图形 先过原点作一条矢量指向点 c1 c2 矢量的方向就是目标函数增加的方向 称为梯度方向 再作一条与矢量垂直的直线 这条直线就是目标函数图形 3 求最优解 依据目标函数求最大或最小移动目标函数直线 直线与可行域相交的点对应的坐标就是最优解 一般地 将目标函数直线放在可行域中求最大值时直线沿着矢量方向移动求最小值时沿着矢量的反方向移动 1 2图解法TheGraphicalMetho
11、d 2020 2 9 1 通过图解法了解线性规划有几种解的形式2 作图的关键有三点 1 可行解区域要画正确 2 目标函数增加的方向不能画错 3 目标函数的直线怎样平行移动 作业 教材习题1 7 1 2图解法TheGraphicalMethod 下一节 线性规划的标准型 1 3线性规划的标准型StandardformofLP 2020 2 9 在用单纯法求解线性规划问题时 为了讨论问题方便 需将线性规划模型化为统一的标准形式 1 3线性规划的标准型StandardformofLP 线性规划问题的标准型为 1 目标函数求最大值 或求最小值 2 约束条件都为等式方程3 变量xj非负4 常数bi非负
12、2020 2 9 max 或min Z c1x1 c2x2 cnxn 1 3线性规划的标准型StandardformofLP 注 本教材默认目标函数是max 2020 2 9 或写成下列形式 或用矩阵形式 1 3线性规划的标准型StandardformofLP 2020 2 9 通常X记为 称 为约束方程的系数矩阵 m是约束方程的个数 n是决策变量的个数 一般情况m n 且r m 其中 1 3线性规划的标准型StandardformofLP 2020 2 9 例1 12 将下列线性规划化为标准型 解 因为x3无符号要求 即x3取正值也可取负值 标准型中要求变量非负 所以令 1 3线性规划的标准
13、型StandardformofLP 2020 2 9 3 第二个约束条件是 号 在 号左端减去剩余变量 Surplusvariable x5 x5 0 也称松驰变量 1 3线性规划的标准型StandardformofLP 2 第一个约束条件是 号 在 左端加入松驰变量 slackvariable x4 x4 0 化为等式 4 第三个约束条件是 号且常数项为负数 因此在 左边加入松驰变量x6 x6 0 同时两边乘以 1 5 目标函数是最小值 为了化为求最大值 令Z Z 得到maxZ Z 即当Z达到最小值时Z 达到最大值 反之亦然 2020 2 9 综合起来得到下列标准型 1 3线性规划的标准型S
14、tandardformofLP 2020 2 9 当某个变量xj 0时 令x j xj 当某个约束是绝对值不等式时 将绝对值不等式化为两个不等式 再化为等式 例如约束 将其化为两个不等式 再加入松驰变量化为等式 1 3线性规划的标准型StandardformofLP 2020 2 9 例1 13 将下例线性规划化为标准型 解 此题关键是将目标函数中的绝对值去掉 令 则有 1 3线性规划的标准型StandardformofLP 2020 2 9 得到线性规划的标准形式 1 3线性规划的标准型StandardformofLP 对于a x b a b均大于零 的有界变量化为标准形式有两种方法 一种方
15、法是增加两个约束x a及x b另一种方法是令x x a 则a x b等价于0 x b a 增加一个约束x b a并且将原问题所有x用x x a替换 2020 2 9 1 如何化标准形式 可以对照四条标准逐一判断 标准形式是人为定义的 目标函数可以是求最小值 2 用WinQSB软件求解时 不必化成标准型 图解法时不必化为标准型 3 单纯形法求解时一定要化为标准型 作业 教材习题1 8 1 3线性规划的标准型StandardformofLP 下一节 基本概念 1 4线性规划的有关概念BasicConceptsofLP 2020 2 9 设线性规划的标准型maxZ CX 1 1 AX b 1 2 X
16、 0 1 3 式中A是m n矩阵 m n并且r A m 显然A中至少有一个m m子矩阵B 使得r B m 1 4基本概念BasicConcepts 基 basis A中m m子矩阵B并且有r B m 则称B是线性规划的一个基 或基矩阵basismatrix 当m n时 基矩阵唯一 当m n时 基矩阵就可能有多个 但数目不超过 2020 2 9 例1 14 线性规划 求所有基矩阵 解 约束方程的系数矩阵为2 5矩阵 容易看出r A 2 2阶子矩阵有C52 10个 其中第1列与第3列构成的2阶矩阵不是一个基 基矩阵只有9个 即 1 4基本概念BasicConcepts 2020 2 9 由线性代数知 基矩阵B必为非奇异矩阵并且 B 0 当矩阵B的行列式等式零即 B 0时就不是基 当确定某一矩阵为基矩阵时 则基矩阵对应的列向量称为基向量 basisvector 其余列向量称为非基向量 基向量对应的变量称为基变量 basisvariable 非基向量对应的变量称为非基变量 在上例中B2的基向量是A中的第一列和第四列 其余列向量是非基向量 x1 x4是基变量 x2 x3 x5是非基变量 基变量
