《运筹学课件PPT》由会员分享，可在线阅读，更多相关《运筹学课件PPT（63页珍藏版）》请在金锄头文库上搜索。
1、OR1 1 第一章线性规划与单纯形法 重点与难点 1 线性规划的概念和模型 线性规划问题的标准型 线性规划问题的标准化 2 线性规划问题解的概念 图解法 解的几何表示 基本可行解的几何意义 线性规划求解思路 单纯形法思想 3 单纯形法的一般描述 表格单纯形法 一般线性规划问题的处理 单纯形迭代过程中的注意事项 4 线性规划建模 决策变量 约束不等式 等式 目标函数 变量的非负限制 OR1 2 第一章线性规划与单纯形法 1 1LP linearprogramming 的基本概念LP是在有限资源的条件下 合理分配和利用资源 以期取得最佳的经济效益的优化方法 LP有一组有待决策的变量 决策变量 一个
2、线性的目标函数 一组线性的约束条件 OR1 3 1 1 1LP的数学模型例题1 生产计划问题 某厂生产两种产品 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 问题 如何安排生产计划 使得获利最多 OR1 4 例题1建模 步骤 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 人力约束9X1 4X2 360设备约束4X1 5X2 200原材料约束3X1 10X2 300非负性约束X1 0X2 0综上所述 该问题的数学模型表示为 OR1 5 例题2 人员安排问题 医院护士24小时值班 每次值班8小时
3、不同时段需要的护士人数不等 据统计 请问该医院至少需要多少名护士 OR1 6 例题2建模 目标函数 minZ x1 x2 x3 x4 x5 x6约束条件 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30非负性约束 xj 0 j 1 2 6 OR1 7 例题3 运输问题 三个加工棉花的加工厂 并且有三个仓库供应棉花 各供应点到各工厂的单位运费以及各点的供应量与需求量分别如下表所示 问如何运输才能使总的运费最小 OR1 8 例题3建模 设Xij为第i个仓库运到底j座工厂的运输量 目标函数 总运费最省 minZ 2x11 x12 3x13 2x21 2x22
4、4x23 3x31 4x32 2x33约束条件 供给要求 x11 x12 x13 50需求要求 x11 x21 x31 40 x21 x22 x23 30 x12 x22 x32 15x31 x32 x33 10 x13 x23 x33 35非负要求 Xij 0 OR1 9 例题4 连续投资问题 书P42页 某投资者有资金10万元 考虑在今后5年内给下列4个项目进行投资 已知 项目A 从第一年到第四年每年年初需要投资 并于次年末回收本利115 项目B 第三年初需投资 到第五年末能回收本利125 但规定投资额不超过4万元 项目C 第二年初需要投资 到第五年末能回收本利140 但规定最大投资额不超
5、过3万元 项目D 5年内每年初可购买公债 于当年末归还 并加利息6 问该投资者应如何安排他的资金 确定给这些项目每年的投资额 使到第五年末能拥有的资金本利总额为最大 OR1 10 建模 解 记xiA xiB xiC xiD i 1 2 3 4 5 分别表示第i年年初给项目A B C D的投资额 它们都是决策变量 为了便于书写数学模型 我们列表如下 OR1 11 例题5 合理下料问题 将长8m的圆钢 截取成长2 5m的毛坯100根 长1 3m的毛坯200根 问应该怎样选择下料方式 才能既满足需要 又使总的用料最少 各种搭配方案如下 OR1 12 例题5建模 设Xj表示采用第j种方案下料的根数 目
6、标函数 minZ x1 x2 x3 x4约束条件 3x1 2x2 x3 1002x2 4x3 6x4 200 xj 0且为整数 j 1 2 3 4 OR1 13 课堂练习 营养配餐问题 养海狸鼠饲料中营养要求 VA每天至少700克 VB每天至少30克 VC每天刚好200克 现有五种饲料 搭配使用 饲料成分如下表 OR1 14 建模 设抓取饲料Ix1kg 饲料IIx2kg 饲料IIIx3kg 目标函数 最省钱minZ 2x1 7x2 4x3 9x4 5x5约束条件 3x2 2x2 x3 6x4 18x5 700营养要求 x1 0 5x2 0 2x3 2x4 0 5x5 300 5x1 x2 0
7、2x3 2x4 0 8x5 200用量要求 x1 50 x2 60 x3 50 x4 70 x5 40非负性要求 x1 0 x2 0 x3 0 x4 0 x5 0 OR1 15 总结 从以上5个例子可以看出 它们都属于优化问题 它们的共同特征 1 每个问题都用一组决策变量表示某一方案 这组决策变量的值就代表一个具体方案 一般这些变量取值是非负的 2 存在一定的约束条件 这些约束条件可以用一组线性等式或线性不等式来表示 3 都有一个要求达到的目标 它可用决策变量的线性函数 称为目标函数 来表示 按问题的不同 要求目标函数实现最大化或最小化 满足以上三个条件的数学模型称为线性规划的数学模型 OR1
8、 16 线性规划模型的一般模式 目标函数 max min Z c1x1 c2x2 c3x3 cnxn约束条件 a11x1 a12x2 a13x3 a1nxn b1a21x1 a22x2 a23x3 a2nxn b2 am1x1 am2x2 am3x3 amnxn bm非负性约束 x1 0 x2 0 xn 0 OR1 17 线性规划的标准型 代数式maxZ c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmxj 0j 1 2 n OR1 18 线性规划的标准型 和式 maxZ cjxj aijxj
9、 bii 1 2 mxj 0j 1 2 n j 1 n n j 1 OR1 19 线性规划的标准型 向量式 maxZ CX pjxj bii 1 2 mxj 0j 1 2 nC c1 c2 c3 cn X X1 X2 X3 Xn T n j 1 OR1 20 线性规划的标准型 矩阵式 maxZ CXAX bX 0其中 b b1 b2 bm Ta11a12 a1nA a21a22 a2n am1am2 amn OR1 21 标准型的特征 目标函数极大化 也有的版本选择极小化 约束条件为等式决策变量非负 OR1 22 非标准型转化为标准型 目标函数极小化转为极大化 minZ max Z 一个数的极
10、小化等价于其相反数的极大化 不等式约束的转化 aijxj bi加入松弛变量 aijxj bi减去剩余变量非正变量 即xk 0则令x k xk自由变量 即xk无约束 令xk x k x k OR1 23 非标准型转化举例 minZ x1 2x2 3x3maxZ x 1 2x2 3 x 3 x 3 x1 x2 x3 9 x 1 x2 x 3 x 3 x4 9 x1 2x2 x3 2x 1 2x2 x 3 x 3 x5 23x1 x2 3x3 5 3x 1 x2 3 x 3 x 3 5x1 0 x2 0 x3无约束x 1 0 x2 0 x 3 0 x 3 0 x4 0 x5 0 OR1 24 课堂练
11、习 将下列非标准型化为标准型 1 minZ x1 2x2 3x32 maxZ x1 x2s t x1 x2 x3 7s t x1 x2 0 x1 x2 x3 23x1 x2 3 3x1 x2 2x3 5x1 x2 0 x1 x2 0 x3无约束 OR1 25 1 1 2线性规划问题的图解法 一 图解法的步骤1 在平面上建立直角坐标系 2 图示约束条件 找出可行域 3 图示目标函数 即为一直线 4 将目标函数直线沿其法线方向其最优化方向平移 直至与可行域第一次相切为止 这个切点就是最优点 二 几种可能结局 1 有唯一最优解 2 有无穷多个最优解 3 无界解 4 无解 OR1 26 线性规划图解法
12、例题 唯一最优解 maxZ 70X1 120X2s t 9X1 4X2 3604X1 5X2 2003X1 10X2 300X1 0X2 0 OR1 27 线性规划图解法例题 无穷多最优解 OR1 28 线性规划图解法例题 无界解 OR1 29 线性规划图解法例题 无解 OR1 30 利用图解法的常识 1 若存在唯一最优解 则此最优解在可行域的顶点上取得 2 若存在无穷多最优解 则最优解在可行域的边界上取得 3 若可行域为空集 则没有可行解 也就没有最优解 4 若可行域无界 目标函数取值可以增大到无穷大 称这种情况为无界解或无最优解 5 若有可行解 则可能有最优解 也可能无最优解 最优解无界
13、OR1 31 1 1 3解的概念 概念 1 可行解 满足所有约束条件的解 2 可行域 即可行解的集合 所有约束条件的交集 也就是各半平面的公共部分 满足所有约束条件的解的集合 称为可行域 3 凸集 集合内任意两点的连线上的点均属于这个集合 如 实心球 三角形 线性规划的可行域是凸集 OR1 32 基的概念 基 如前所述LP标准型和式 maxZ cjxj aijxj bixj 0j 1 2 n矩阵式 maxZ CXAX bX 0约束方程的系数矩阵A的秩为m 且m n 设A B N B是A中m m阶满秩子矩阵 则称B是该LP问题的一个基 即 B是A中m个线性无关向量组 n j 1 n j 1 OR
14、1 33 基本概念 秩 m n矩阵A的所有不为零的子式的最高阶数称为矩阵A的秩 记作R A 线性无关向量组 对于向量组a1 a2 an 如果存在一组不全为零的实数k1 k2 kn 使k1a1 k2a2 knan 0 则称向量组a1 a2 an线性相关 否则称它们线性无关 向量线性无关的充要条件是向量组的秩等于向量组所含向量个数 OR1 34 基解的概念 不失一般性 设B是A的前m列 即B p1 p2 pm 其相对应的变量XB x1 x2 xm T 称为基变量 其余变量XN Xm 1 Xn T称为非基变量 令所有非基变量等于零时得出的解 即X x1 x2 xm 0 0 T称为基解 注 基解不一定
15、就是可行解 因为基解不一定满足非负的约束条件 也即基解中可能存在负值的情况 OR1 35 基可行解的概念 基可行解 基解可正可负 负则不可行 违背非负性约束条件 满足非负约束条件的基解为基可行解 对应于基可行解的基称为可行基 退化的基可行解 若某个基变量取值为零 则称之为退化的基可行解 基解的数目 最多Cmn n m n m OR1 36 几种解之间的关系 部分基解是非可行解 OR1 37 例题8基可行解说明 maxZ 70X1 120X2P1P2P3P4P59X1 4X2 X3 360941004X1 5X2 x4 200A 450103X1 10X2 x5 300310001Xj 0j 1
16、 2 5这里m 3 n 5 Cmn 10 OR1 38 例题8基可行解说明 基 p3 p4 p5 令非基变量x1 x2 0 则基变量x3 360 x4 200 x5 300 可行解基 p2 p4 p5 令非基变量x1 0 x3 0基变量x2 90 x4 250 x5 600 非可行解基 p2 p3 p4 令非基变量x1 x5 0 则基变量x2 30 x3 240 x4 50 可行解 OR1 39 基本定理介绍 P16 19 定理1 若线性规划问题存在可行域 则其可行域D 是凸集 引理1 LP问题的可行解X x1 x2 xn T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的 OR1 40 基本定理介绍 定理2 LP问题的基可行解X对应于可行域的顶点 顶点 设K是凸集 X属于K 若X不能用不同的两点的线性组合表示为则称X为K的一个顶点 或极点 引理2 若K是有界凸集 则任何一点X属于K可表示为K的顶点的凸组合 OR1 41 基本定理介绍 定理3若可行域有界 LP问题的目标函数一定可以在其可行域的顶点上达到最优 另外 若可行域为无界 则可能无最优解 也可能有最优解 若有也必定
