运筹02线性规划与单纯形法素材.ppt

《运筹02线性规划与单纯形法素材.ppt》由会员分享，可在线阅读，更多相关《运筹02线性规划与单纯形法素材.ppt（132页珍藏版）》请在金锄头文库上搜索。

1、Chapter2线性规划与单纯形法 LinearProgrammingandSimplexAlgorithm 1 线性规划问题及其数学模型2 线性规划问题的几何意义3 单纯形法4 单纯形法的计算步骤5 单纯形法的进一步讨论6 应用举例 线性规划是运筹学的一个重要分支 自1947年丹捷格 G B Dantzig 提出了线性规划问题求解的方法 单纯形法之后 线性规划在理论上趋向成熟 在实用中日益广泛与深入 特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后 线性规划的适用领域更为广泛 从解决技术问题的最优化设计到工业 农业 商业 交通运输业 军事 经济计划和管理决策等领域都可以发挥

2、作用 引言 线性规划研究的问题 如何合理地利用有限的人力 物力 财力等资源 以便得到最好的经济效果 2 1线性规划问题及其数学模型 2 1 1问题的提出 例1某工厂在计划期内要安排生产I II两种产品 已知生产单位产品所需的设备台时及A B两种原材料的损耗 如表1 1所示 表1 1 该工厂每生产一件产品 可获利2元 每生产一件产品 可获利3元 问应如何安排计划使该工厂获利最多 1 确定决策变量 2 确定目标函数 4 确定变量取值限制 3 确定约束条件 得到本问题的数学模型为 这就是一个最简单的线性规划模型 例2靠近某河流有两个化工厂 见图1 1 流经第一化工厂的河流流量为每天500万立方米 在

3、两个工厂之间有一条流量为每天200万立方米的支流 化工厂1每天排放含有某种有害物质的工业污水2万立方米 化工厂2每天排放的工业污水为1 4万立方米 从化工厂1排出的污水流到化工厂2前 有20 可自然净化 根据环保要求 河流中工业污水的含量应不大于0 2 因此两个工厂都需处理一部分工业污水 化工厂1处理污水的成本是1000元 万立方米 化工厂2处理污水的成本是800元 万立方米 问 在满足环保要求的条件下 每厂各应处理多少工业污水 使两个工厂处理工业污水的总费用最小 1 确定决策变量设第一化工厂每天处理工业污水x1万立方米 第二化工厂每天处理工污水x2万立方米 2 确定目标函数 3 确定约束条件

4、 从第一化工厂到第二化工厂之间 河流中工业污水含量不大于0 2 由此可得近似关系式 流经第二化工厂后 河流中的工业污水含量仍要不大于0 2 这时有近似关系式 4 确定变量取值限制 得到本问题的数学模型为 上述两个问题具有的共同特征 每一个线性规划问题都用一组决策变量 x1 x2 xn 表示某一方案 这组决策变量的值代表一个具体方案 一般这些变量的取值是非负且连续的 都有关于各种资源和资源使用情况的技术数据 并存在可以量化的约束条件 这些约束条件可以用一组线性等式或线性不等式来表示 都有一个达到某一目标的要求 可用决策变量的线性函数 称为目标函数 来表示 按问题的要求不同 要求目标函数实现最大化

5、或最小化 决策变量及各类系数之间的对应关系 满足以上特征的数学模型 我们称之为线性规划问题 简单的说线性规划问题是求一个线性目标函数满足一组线性约束条件的极值问题 线性规划模型的一般形式 例 常山机器厂生产 两种产品 这两种产品都要分别在A B C三种不同设备上加工 按工艺资料规定 生产每件产品 需占用各设备分别为2h 4h 0h 生产每件产品 需占用各设备分别为2h 0h 5h 已知各设备计划期内用于生产这两种产品的能力分别为12h 16h 15h 又知每生产一件产品 企业能获得2元利润 每生产一件产品 企业能获得3元利润 问该企业应安排生产两种产品各多少件 使总的利润收入为最大 2 1 2

6、线性规划的数学模型 1分析实际问题2确定决策变量3确定目标函数4找出约束条件5整理 写出数学模型 运输工具配载问题 有一辆运输卡车 载重2 5t 容积18用来装载如下两种货物 箱装件 125kg 0 4包装件 20kg 1 5请问 如何装配 卡车所装的物件个数最多 1 分析问题 这是一个运输工具的配载问题 给出了最大载重和容积 要求装最多的物件 2 确定决策变量 此问题的决策变量有两个 箱装件和包装件 因此分别设为X1 X2 3 确定目标函数 本问题的目标要求为装物件个数最多 Maxz X1 X24 找出约束条件 约束条件有两个 载重和容积约束 因此列出约束条件 容积约束 0 4X1 1 5X

7、2 18载重约束 125X1 20X2 2500非负约束 X1 0 X2 0 5 整理 写出数学模型 南京某市场调查公司受一洗涤剂厂委托 调查消费者对新型洗衣粉的了解与反应 对不同家庭采用不同调查方式的费用见表 洗涤剂厂对市场调查公司提出了以下几个方面的具体要求 1 调查800个家庭 2 被调查家庭中 至少有300个是没有孩子的家庭 同时至少有300个是有孩子的家庭 3 至少对500个被调查家庭采用问卷式书面调查 其余家庭可用口头调查 4 在有孩子的被调查家庭中 至少有50 的家庭采用问卷式书面调查 5 在没有孩子的被调查家庭中 至少有60 的家庭采用问卷式书面调查 市场调查计划优化问题 投资

8、问题 上海某投资公司在今后三年内有四种投资机会 第1种是3年内每年年初投资 年底可获利润20 并可将本金收回 第2种是在第一年的年初投资 第二年年底可获利润50 并将本金收回 但该项投资不得超过2000万 第3种是在第二年的年初投资 第三年年底收回本金 并获利润60 但该项目投资不得超过1500万 第4种是在第三年的年初投资 于该年年底收回本金 且获利润40 但该项投资不得超过1000万 现在该公司拿出3000万 问如何制定投资计划 使得第三年年末本利和最大 配料问题 某糖果厂用原料A B C加工成三种不同牌号的糖果甲 乙 丙 已知各种牌号糖果中A B C含量 原料成本 各种原料的每月限制用量

9、 三种牌号糖果的单位加工费及售价如下表所示 问该厂每月应生产这三种牌号糖果各多少千克 使得该厂获利最大 试建立这个问题的线性规划的数学模型 下料问题 某建筑工地有一批长度为10米的相同型号的钢筋 今要截成长度为3米的钢筋90根 长度为4米的钢筋60根 问怎样下料 才能使所使用的原材料最省 1 每个行动方案可用一组变量 x1 xn 的值表示 这些变量一般取非负值 2 变量的变化要受某些限制 这些限制条件用一些线性等式或不等式表示 3 有一个需要优化的目标 它也是变量的线性函数 具备以上三个特点的数学模型称为线性规划 LinearProgramming 简记为LP 下料问题练习 有一批原料钢材 如

10、钢管 钢筋 角钢 钢梁等 每根长7 4m 现需做100套钢架 每套利用长2 9m 2 1m 1 5m的钢材各一根 问如何下料 才能使所用的原料最省 有A B C三个工地 每天需要水泥各为17 18 15百袋 为此甲 乙两个水泥厂每天各生产23百袋和27百袋水泥供应这三个工地 其单位运价如下表 求最佳调运方案 线性规划模型的一般形式 Ci为价值系数 ai为技术系数 bi为限制系数 2 1 3线性规划问题的标准形式 目标函数为求最大值 约束条件为等式约束 约束方程右端常数项为非负数值 决策变量取非负数值 用向量形式表示的标准形式线性规划 价值向量 决策向量 系数向量 资源向量 用矩阵形式表示的标准

11、形式线性规划 这时只需将目标函数最小化变换为求目标函数最大化 必须注意 尽管以上两个问题的最优解相同 但它们最优解的目标函数值却相差一个符号 如何将一般线性规划转化为标准形式的线性规划 引进一个松弛变量 把原不等式约束用两个约束来等价地替换 设约束条件为 2 约束方程为不等式有两种情况 一种是约束方程为 不等式 则可在 不等式的左端加入非负松弛变量 把原 不等式变为等式 另一种是约束方程为 不等式 则可在 不等式的左端减去一个非负剩余变量把原 不等式变为等式 引进一个剩余变量 把原不等式约束用两个约束来等价地替换 设约束条件为 4 在标准形式中 要求约束条件的右端项bi 0 否则等式两端乘以

12、1 下面举例说明 可以令 其中 即用两个非负变量之差来表示一个无符号限制的变量 当然的符号取决于和的相对大小 3 若存在取值无约束的变量 例3将例1的数学模型化为标准形式的线性规划 例4将下述线性规划问题化为标准形式线性规划 1 用x4 x5替换x3 其中x4 x5 0 2 在第一个约束不等式左端加入松弛变量x6 3 在第二个约束不等式左端减去剩余变量x7 4 令z z 将求minz改为求maxz 即可得到该问题的标准型 例4例4的标准型 2 1 4线性规划问题解的概念 可行解满足约束条件 1 5 1 6 式的解称为线性规划问题的可行解 其中使目标函数达到最大值的可行解称为最优解 考虑LP的标

13、准型 称为基向量 与基向量相对应的变量称为基变量 否则称为非基变量 设A是约束方程组的维系数矩阵 其秩为m B是A中m阶非奇异子矩阵 B 0 则称B是线性规划问题的一个基 这就是说 矩阵B是由A中m个线性无关的列向量组成 为不失一般性 可设B是A中的前m列 即 2基 注 1 对应于给定的基B 基解是唯一的 2 基解中非基变量取零值 非零分量的数目不超过m 3 基解一定满足等式约束 但不一定满足非负约束 称为对应于基B的基解 令所有非基变量得到 因B可逆 该方程有唯一解 把约束方程 1 5 式写成 例在下述线性规划问题中列出全部的基并确定相应的基解 解 将该线性规划问题化为标准形 只要从A的列向

14、量中找出3个线性无关的列向量就组成该线性规划问题的一个基 取A的第一 二 三列组成子矩阵易见 故B1是该线性规划问题的一个基 令非基变量 则约束方程变为 基变量为 非基变量 令非基变量为零 求解线性方程组 就可找出全部基解 解得 取A的第一 四 五列得到基 相应地基解 取A的第一 三 五列得到基 相应地基解 类似地取A的第一 二 四列得到基 相应地基解 取A的第一 二 五列得到基 相应地基解 对于A的第一 三 四列组成的矩阵易见 故不能作成一组基 取A的第二 三 四列得到基相应地基解取A的第二 四 五列得到基相应地基解取A的第三 四 五列得到基 相应地基解 同理 也不能作成一组基 1 基解的数

15、目最多是个 2 基解中非零分量的个数小于m个时 该基解是退化解 3基可行解满足非负约束条件的基解称为基可行解 以下讨论时 假设不出现退化的情况 即基解中非零分量恰为m个 说明 4可行基对应于基可行解的基称为可行基 几何上 图中A B C D E F G H对应X i i 1 2 8 直观上 可行解即可行域中的点 基解是约束直线的交点 基可行解即可行域的顶点 它们之间的关系可以用图1 6表示 在下述线性规划问题列出一个基并确定相应的基解 线性规划问题的求解方法 一般有两种方法 图解法单纯形法 两个变量 直角坐标三个变量 立体坐标 适用于任意变量 但必需将一般形式变成标准形式 下面我们分析一下简单

16、的情况 只有两个决策变量的线性规划问题 这时可以通过图解的方法来求解 图解法具有简单 直观 便于初学者窥探线性规划基本原理和几何意义等优点 2 1 2图解法 例1一个二维线性规划问题 因而可用图解法直观地进行求解 目标值在 4 2 点 达到最大值14 1 无穷多最优解 多重最优解 见图1 2 无界解 见图2 3 无可行解 见图 3 通过图解法 可观察到线性规划的解可能出现的几种情况 目标函数maxz 2x1 4x2 图1无穷多最优解 多重最优解 maxz 2x1 3x24x1 16x1 x2 0则x2 z 即存在无界解 图2无界解 当存在相互矛盾的约束条件时 线性规划问题的可行域为空集 例如 如果在例1的数学模型中增加一个约束条件 则该问题的可行域即为空集 即无可行解 无可行解的情形 图3不存在可行域 思考 1 线性规划的可行域是一个什么形状 2 最优解在什么位置获得 结论 问题 性质2有何重要意义 凸集 如果集合C中任意两个点X1 X2 其连线上的所有点也都是集合C中的点 称C为凸集 凸集 凸集 不是凸集 2 2线性规划问题的几何意义1基本概念 试判断下列图形是否凸集 凸组合 设是n