《管理运筹学》02-1线性规划的数学模型及相关概念.ppt

第1节 LinearProgramming LP 线性规划 的数学模型 第1节线性规划的数学模型及相关概念 2 一 现实中的线性规划问题及数学模型二 线性规划的标准形式三 线性规划的几何解释四 线性规划的基及基本可行解 第1节线性规划的数学模型及相关概念 3 一现实中的线性规划问题及模型 例2 1生产计划问题某工厂拥有A B C三种类型的设备 生产甲 乙 丙 丁四种产品 每件产品在生产中需要占用的设备机时数 每件产品可以获得的利润以及三种设备可利用的时数如表2 1所示 试用线性规划制订使总利润最大的生产计划 第1节线性规划的数学模型及相关概念 1 05 03 0 2 41 03 5 1 03 51 0 4 一现实中的线性规划问题及模型 z x1x2x3x4 决策变量 z 5 24x1 7 30 x2 8 34x3 4 18x4 max 0 目标函数 1 5x1 1 0 x2 2 4x3 1 0 x4 2000 函数约束 非负性约束 s t 第1节线性规划的数学模型及相关概念 1 0 x1 5 0 x2 1 0 x3 3 5x4 8000 1 5x1 3 0 x2 3 5x3 1 0 x4 8000 x1 x2 x3 x4 0 1 05 03 0 2 41 03 5 1 03 51 0 5 一现实中的线性规划问题及模型 第1节线性规划的数学模型及相关概念 求解这个线性规划 可以得到最优解为 x1 294 12 件 x2 1500 件 x3 0 件 x4 58 82 件 最大利润为z 12737 06 元 请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产 说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性 尤其当产品品种很多 设备类型很多的情况下 用手工方法安排生产计划很难获得满意的结果 6 一现实中的线性规划问题及模型 例2 2配料问题某工厂要用四种合金T1 T2 T3和T4为原料 经熔炼成为一种新的不锈钢G 这四种原料含元素铬 Cr 锰 Mn 和镍 Ni 的含量 这四种原料的单价以及新的不锈钢材料G所要求的Cr Mn和Ni的最低含量 如下表所示 设熔炼时重量没有损耗 要熔炼成100公斤不锈钢G 应选用原料T1 T2 T3和T4各多少公斤 使成本最小 第1节线性规划的数学模型及相关概念 4 531 123 06 2 193 574 27 1 764 332 73 x1x2x3x4 7 第1节线性规划的数学模型及相关概念 z 115x1 97x2 82x3 76x4 min 0 0321x1 0 0453x2 0 0219x3 0 0176x4 3 20 s t x1 x2 x3 x4 0 0 0204x1 0 0112x2 0 0357x3 0 0433x4 2 10 0 0582x1 0 0306x2 0 0427x3 0 0273x4 4 30 x1 x2 x3 x4 100 求解这个线性规划 可以得到最优解为 x1 26 58x2 31 57x3 41 84x4 0最大利润为z 9549 87 元 一现实中的线性规划问题及模型 8 一现实中的线性规划问题及模型 例2 3背包问题一只背包最大装载重量为50公斤 现有三种物品 每种物品数量无限 每种物品每件的重量 价值如下表所示 要在背包中装入这三种物品各多少件 使背包中的物品价值最高 第1节线性规划的数学模型及相关概念 4172 2035 x1x2x3 9 第1节线性规划的数学模型及相关概念 z 17x1 72x2 35x3 max 10 x1 41x2 20 x3 50 s t x1 x2 x3 0且为整数 求解这个线性规划 可以得到最优解为 x1 1x2 0 x3 2最高价值为z 87 元 一现实中的线性规划问题及模型 10 一现实中的线性规划问题及模型 例2 4最小费用流问题某公司下设两个分工厂 两个仓库及一个配送中心 其中F1和F2是两个工厂 W1和W2是两个仓库 D是一个分销中心 由工厂生产的产品经由图所示的运输网络运往仓库 每一条路线运输的单位成本在线段上给出 其中 F1 F2与D W2路线由于受到路线中的桥梁承重上限的要求 因此有最大运输量限制 其他路线有足够的运输能力来运输两个工厂生产的货物 需要制订的决策是关于每一条路线应该运输多少 目标是总体的运输成本最小化 第1节线性规划的数学模型及相关概念 11 一现实中的线性规划问题及模型 例2 4最小费用流问题 第1节线性规划的数学模型及相关概念 生产50单位 12 第1节线性规划的数学模型及相关概念 z 200 x1 400 x2 900 x3 300 x4 100 x5 3x6 200 x7 min x1 x2 x3 50 s t x1 x7 0 x1 x4 40 x2 x4 x5 0 x3 x6 x7 30 求解这个线性规划 可以得到最优解为 x1 x2 x3 x4 x5 x6 x7 0 40 10 40 80 0 20 z 49000 元 一现实中的线性规划问题及模型 x5 x6 x7 60 x1 10 x5 80 13 线性规划的一般形式 一般LP模型的三类参数 价值系数cj 消耗系数aij 右端常数bi LP模型的三要素 决策变量 目标函数 约束条件 s t max min z c1x1 c2x2 c3x3 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmxj 或 0 或自由 j 1 2 n 第1节线性规划的数学模型及相关概念 一现实中的线性规划问题及模型 14 线性规划的向量和矩阵的表达形式 记向量和矩阵 第1节线性规划的数学模型及相关概念 一现实中的线性规划问题及模型 则线性规划问题可以表示为 max min z CX s t AX b X 0 15 二 线性规划的标准形式 称以下线性规划的形式为标准形式 maxz c1x1 c2x2 c3x3 cnxn s t a11x1 a12x2 a1nxn b1 0 a21x1 a22x2 a2nxn b2 0 am1x1 am2x2 amnxn bm 0 x1 x2 xn 0 简记为 maxz CX s t AX b X 0 M1 M2 第1节线性规划的数学模型及相关概念 16 非标准形LP问题的标准化一 极小化目标函数的问题minz CX令z zmaxz CX例 minz 3x1 2x2maxz 3x1 2x2二 约束条件不是等式的问题 bi 0两边同时乘以 1 约束为 形式加上松弛变量 约束为 形式减去剩余变量三 变量符号无限制或小于等于零的问题若xk为自由变量 令xk xk xk 且xk xk 0若xk 0 令xk xk 则xk 0 第1节线性规划的数学模型及相关概念 二 线性规划的标准形式 x z z zmin z z z max x 17 第1节线性规划的数学模型及相关概念 例2 5将下述LP问题化成标准形式 解 令z z x2 x2 x2 x3 x3 maxz 2x1 3x2 3x2 x3 x1 x2 x2 2x3 x4 32x1 3x2 3x2 x3 x5 5x1 x2 x2 x3 4x1 x2 x2 x3 x4 x5 0 s t 二 线性规划的标准形式 第1章线性规划的数学模型及相关概念 18 解 maxz x1 2x2 3x3 s t x1 2x2 x3 x4 52x1 3x2 x3 x5 6x1 x2 x3 x6 2x1 x4 x5 x6 0 x3 0 练习 将下述LP问题化成标准形 二 线性规划的标准形式 第1章线性规划的数学模型及相关概念 19 令 x2 x2 x2 且x2 x2 0 x3 x3 代入上式中 得 二 线性规划的标准形式 第1节线性规划的基本性质 20 只有两个变量的线性规划问题 X 4 6 T z 42 1 画出可行域图形2 画出目标函数的等值线及其法线3 确定最优点 x1 8 A 8 0 2x2 12 D 0 6 3x1 4x2 36 z 15 z 30 z法向 z 42 边界方程 三 线性规划的几何解释 第1节线性规划的基本性质 21 几点说明实际运用时还须注意以下几点 1 若函数约束原型就是等式 则其代表的区域仅为一直线 而且问题的整个可行域R 若存在的话 也必然在此直线上 2 在画目标函数等值线时只须画两条就能确定其法线方向 为此 只须赋给z两个适当的值 3 在找出最优点后 关于其坐标值有两种确定方法 在图上观测最优点坐标值 通过解方程组得出最优点坐标值 三 线性规划的几何解释 第1节线性规划的基本性质 22 几种可能结果一 唯一解如例1 例2都只有一个最优点 属于唯一解的情形 二 多重解 z 12 z 36 线段BC上无穷多个点均为最优解 三 线性规划的几何解释 第1节线性规划的基本性质 23 x1 x2 z 三 无界解 R2 R1 R2 四 无可行解 R1 三 线性规划的几何解释 第1节线性规划的基本性质 24 相关定义定义2 1可行域在n维空间中 满足条件ai1x1 ai2x2 ainxn bi且xj 0的点集 三 线性规划的几何解释 第1节线性规划的基本性质 25 定义2 2凸集 三 线性规划的几何解释 设S是n维空间中的一个点集 若对任意n维向量X1 S X2 S 且X1 X2 以及任意实数 0 1 有X X1 1 X2 S则称S为n维空间中的一个凸集 ConvexSet 点X称为点X1和X2的凸组合 凸集 非凸集 第1节线性规划的基本性质 26 定义2 3凸集的极点 三 线性规划的几何解释 设S为一凸集 且X S 若X不能用不同的两点X1 S X2 S的线性组合表示为X X1 1 X2 0 1 则称X为S的一个极点 运用以上的定义 线性规划的可行域以及最优解有以下性质 1 若线性规划的可行域非空 则可行域必定为一凸集 2 若线性规划有最优解 则最优解一定可以在凸集的极点中找到 这样 求线性规划最优解的问题 从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题 27 第1节线性规划的数学模型及相关概念 基 设A为线性规划模型约束条件系数矩阵 m n m n 而B为其m m子矩阵 若 B 0 则称B为该线性规划模型的一个基 基变量 基中每个向量所对应的变量称为基变量 非基变量 模型中基变量之外的变量称为非基变量 基本解 基解 令模型中所有非基变量X非基 0后 由模型约束方程组n aijxj bi i 1 2 m 得到的一组解 j 1 基本可行解 基可行解 在基本解中 同时又是可行解的解称为基本可行解 可行基 对应于基本可行解的基称为可行基 四 线性规划的基 基本可行解 28 Maxz 2x1 3x2st x1 x2 3x1 2x2 4x1 x2 0 Maxz 2x1 3x2 0 x3 0 x4st x1 x2 x3 3x1 2x2 x4 4x1 x2 x3 x4 0 A x1x2x3x4 11101201 可行解 X 0 0 T X 0 1 T X 1 2 1 3 T等 设 B 1001 令 则 B 1 0 令x1 x2 0 则x3 3 x4 4 X 0 0 3 4 T 例 x3x4 基变量 令 B 1110 x1x3 则 令x2 x4 0 则x3 1 x1 4 X 4 0 1 0 T B 1 0 非基本可行解 基本可行解 标准化 第1节线性规划的数学模型及相关概念 四 线性规划的基 基本可行解 29 定理2 1线性规划的基本可行解就是可行域的极点 第1节线性规划的数学模型及相关概念 四 线性规划的基 基本可行解 Maxz 2x1 3x2s t x1 x2 3x1 2x2 4x1 x2 0 Maxz 2x1 3x2 0 x3 0 x4s t x1 x2 x3 3x1 2x2 x4 4x1 x2 x3 x4 0 例 标准化 A矩阵包含以下六个2 2的子矩阵 B1 p1 p2 B2 p1 p3 B3 p1 p4 B4 p2 p3 B5 p2 p4 B6 p3 p4 其中所有的子矩阵行列式值均不等于0 均为非奇异方阵 因此该问题共有6个基 30 第1节线性规划的数学模型及相关概念 四 线性规划的基 基本可行解 B6 1001 则 B6 1 0 x3x4 基变