《第1章线性规划及单纯形法.ppt》由会员分享，可在线阅读，更多相关《第1章线性规划及单纯形法.ppt（143页珍藏版）》请在金锄头文库上搜索。
1、 线性规划问题的数学模型图解法单纯形法 原理 计算步骤 数值实现 线性规划模型的应用 本章主要内容 第一章线性规划及单纯形法 线性规划是运筹学中应用最广泛的方法之一 线性规划是运筹学的最基本的方法之一 整数规划 目标规划和网络规划都是以线性规划为基础的 1线性规划问题的数学模型 1 1线性规划问题 线性规划问题的数学模型 线性规划通常解决下列两类问题 1 当任务或目标确定后 如何统筹兼顾 合理安排 用最少的资源 如资金 设备 原料 人工 时间等 去完成确定的任务或目标 2 在一定的资源条件限制下 如何组织安排生产获得最好的经济效益 如产品的产量最多 利润最大 线性规划问题的数学模型 例1某企业
2、计划生产甲 乙两种产品 这些产品分别要在A B C三种不同的设备上加工 按工艺资料规定 单件产品在不同设备上加工所需要的台时如下表所示 企业决策者应如何安排生产计划 使企业总的利润最大 线性规划问题的数学模型 解 设x1 x2分别为甲 乙两种产品的产量 则数学模型为 例2合理配料问题 求 最低成本的原料混合方案 解 设每单位添加剂中原料i的用量为xj j 1 2 3 4 根据题意 混合配料后 每单位添加剂中A的含量不得低于12 即4x1 6x2 x3 2x4 12每单位添加剂中B的含量不得低于14 即x1 x2 7x3 5x4 14每单位添加剂中C的含量不得低于8 即2x2 x3 3x4 8另
3、外 原料使用量不能为负 即 x1 x2 x3 x4 0 同时 我们有一个追求的目标 成本最低 即 MinZ 2x1 5x2 6x3 8x4 综合上述讨论 在添加剂中各维生素的含量以及成本与原料消耗量成线性关系的假设下 把目标函数和约束条件放在一起 可以建立如下的数学模型 目标函数 约束条件 MinZ 2x1 5x2 6x3 8x4 例3 求 运输费用最小的运输方案 解 设xij为i仓库运到j工厂的原棉数量其中 i 1 2 3j 1 2 3 MinZ 2x11 x12 3x13 2x21 2x22 4x23 3x31 4x32 2x33 x11 x12 x13 50 x21 x22 x23 30
4、 x31 x32 x33 10 x11 x21 x31 40 x12 x22 x32 15x13 x23 x33 35xij 0 s t 每个问题都用一组决策变量 x1 x2 xn 表示某一方案 这组未知数的值就代表一个具体的方案 通常要求这些未知数取值是非负的 满足以上三个条件的数学模型称为线性规划模型 3 都有一个目标要求 并且这个目标可表示为这组决策变量的线性函数 称为目标函数 按研究问题的不同 要求目标函数实现最大化或最小化 2 存在一定的限制条件 称为约束条件 这些条件都可以用关于决策变量的一组线性等式或不等式来表示 线性规划问题的数学模型 线性规划问题的数学模型 1 2线性规划模型
5、的三要素 决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints 其特征是 1 问题的目标函数是一组决策变量的线性函数 通常是求最大值或最小值 2 问题的约束条件是一组决策变量的线性不等式或等式 怎样辨别一个模型是线性规划模型 线性规划问题的数学模型 目标函数 约束条件 1 3线性规划模型的一般形式 简写为 线性规划问题的数学模型 向量形式 其中 线性规划问题的数学模型 矩阵形式 其中 2020 4 30 16 1 3线性规划问题的标准形式 标准形式 标准形式特点 4 决策变量取值非负 1 目标函数为求极大值 2 约束条件全为等式 3
6、 约束条件右端常数项全为非负 2020 4 30 17 一般线性规划问题如何化为标准型 1 目标函数求极小值 令 化为 2020 4 30 18 2 约束条件为不等式 1 当约束条件为 时 如 可令 显然 2 当约束条件为 时 如 可令 显然 称为松弛变量 称为剩余变量 2020 4 30 19 松弛变量和剩余变量统称为松弛变量 3 目标函数中松弛变量的系数 由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源 都没有转化为价值和利润 因此在目标函数中系数为零 2020 4 30 20 3 取值无约束的变量 显然x的取值可能是正也可能是负 这时可令 其中 令 4 变量xj 0 显然
7、2020 4 30 21 例3 将下述线性规划模型化为标准型 2020 4 30 22 解 令 得标准形式为 线性规划问题的数学模型 1 什么是模型结构的三要素 2 什么是线性规划模型 能举出线性规划模型的例子吗 3 LP模型中目标函数系数 约束条件系数 约束右端项的含义指的是什么 通常以什么符号表示 4 LP模型的一般表示方法有几种形式 能否写出这些形式 5 什么是线性规划模型的标准形式 你能否把一个线性规划模型的非标准形式转化为标准形式 思考题 线性规划问题的解 一 线性规划问题的解 线性规划问题 求解线性规划问题 就是从满足约束条件 2 3 的方程组中找出一个解 使目标函数 1 达到最大
8、值 可行解 满足约束条件 2 3 的解为可行解 所有可行解的集合为可行域 最优解 使目标函数达到最大值的可行解称为最优解 基 设A为约束条件 2 的m n阶系数矩阵 m n 其秩为m B是矩阵A中m阶满秩子矩阵 B 0 称B是规划问题的一个基 设 称B中每个列向量Pj j 1 2 m 为基向量 与基向量Pj对应的变量xj为基变量 除基变量以外的变量为非基变量 线性规划问题的解 基解 对某一确定的基B 令非基变量等于零 由约束条件方程 2 解出基变量 称这组解为基解 在基解中变量取非0值的个数不大于方程的个数m 基解的总数不超过基可行解 满足变量非负约束条件的基本解 简称基可行解 可行基 对应于
9、基可行解的基称为可行基 线性规划问题的解 2020 4 30 27 例 考察下述线性规划问题 2020 4 30 28 1 可行解 如 或 满足约束条件 所以是可行解 2 基 系数矩阵A 其中 或 2020 4 30 29 3 基向量 基变量 是对应于基 的三个基向量 而 是对应于这三个基向量的基变量 4 基解 基可行解 可行基 是对应于基 的一个基解 基可行解 是对应于基 的一个基解 基可行解 均是可行基 2020 4 30 30 为了便于建立n维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路 先介绍图解法 求解下述线性规划问题 2线性规划问题的图解法 x1 x2 2
10、 2 4 6 8 4 6 0 2020 4 30 32 1 可行域 约束条件所围成的区域 2 基可行解 对应可行域的顶点 3 目标函数等值线 4 目标函数最优值 最大截距所对应的 目标函数等值线有无数条 且平行 观察规律 2020 4 30 33 解的几种情况 2 无穷多最优解 1 唯一最优解 若目标函数改为 约束条件不变 则 2020 4 30 34 解的几种情况 4 无界解 3 无可行解 当可行域为空集时 无可行解 若目标函数不变 将约束条件1和3去掉 则可行域及解的情况见下图 此时 目标函数等值线可以向上无穷远处平移 Z值无界 2020 4 30 35 几点说明 1 图解法只能用来求解含
11、有两个决策变量的线性规划问题 2 若最优解存在 则必在可行域的某个顶点处取得 3 线性规划问题的解可能是 唯一最优解 无穷多最优解 无最优解 无界解 图解法 小结 1 线性规划问题的解有以下几种形式 唯一最优解 无穷多最优解 无界解 无可行解 2 作图时注意以下三点 1 可行域要画准确 2 目标函数增加的方向要找正确 3 带有参数的直线一定要平行移动 思考题 1 LP模型的可行域是否一定存在 2 图解法中如何去判断模型有唯一解 无穷多解 无界解和无可行解 3 LP模型的可行域的顶点对应它的什么解 4 你认为把所有的顶点都找出来 再通过比较目标函数值大小的方式找出最优解 是否是最好的算法 为什么
12、 图解法 单纯形法原理 1 凸集 如果集合C中任意两点x1 x2 其连线上的所有点也都是集合C中的点 则称C为凸集 其中x1 x2的连线可以表示为 x1 1 x2 0 1 数学语言可表为 任意x1 C x2 C 有 x1 1 x2 C 0 1 则C为凸集 一 凸集和顶点 2 顶点如果集合C中不存在任何两个不同的点x1 x2 使x为这两点连线上的一个点 即对任何不同的x1 C x2 C 不存在x x1 1 x2 0 1 则称x为凸集的顶点 单纯形法原理 单纯形法原理 定理1线性规划问题的可行域是凸集 证 设X1 X2为可行域C内的任意两点 则 有 故C为凸集 对于 二 基本定理 证毕 单纯形法原
13、理 引理线性规划问题的可行解为基可行解的充要条件是它的正分量所对应的系数列向量线性无关 证 1 必要性 设可行解 若X为基本可行解 则取正值的变量必是基变量 它们所对应的约束矩阵A中的列向量P1 Pk是基向量 故必线性无关 单纯形法原理 引理线性规划问题的可行解为基可行解的充要条件是它的正分量所对应的系数列向量线性无关 2 充分性 因为A的秩为m 则可以从其余向量中找 构成一个基 其对应的解为X 故X为基可行解 出m k个与 证毕 定理2LP的基可行解对应可行域的顶点 证 1 充分性 由引理知线性相关 即存在一组不全为零的数 使得 假设顶点X不是基可行解 不妨设它的前k个分量为正 则有 用反证
14、法 2 必要性 仍用反证法 因此X不是基可行解 证毕 定理3若线性规划问题有最优解 一定存在一个基可行解是最优解 证毕 通过以上定理 可以得到以下结论 1 线性规划问题的可行域是一个凸集 可行域可能有界也可能无界 但其顶点 极点 的个数是有限个 2 线性规划问题的每个基本可行解对应于可行域的顶点 3 若线性规划问题有最优解 则其最优解必在可行域的某个 或多个 顶点上达到 这就提供了寻求线性规划问题最优解的途径 在基本可行解中寻求最优解 而基本可行解的个数有限 不会超过基本解的个数 而基本解的个数不会超过 其中m n分别为线性规划问题约束条件中系数矩阵A的行数和列数 但这样的穷举法是低效率的 针
15、对线性规划问题的特点 有效地求解线性规划问题的方法是 单纯形方法 基本思想是 开始于某一个可行基及其对应的基本可行解 从一个基本可行解迭代到另一个基本可行解 并且使目标函数值不断增大 单调不减 经过有限步必能求得线性规划问题的最优解或者判定线性规划问题无有界的最优解 单纯形法原理 单纯形法的思路 初始基本可行解 新的基本可行解 最优否 STOP Y N 单纯形法的计算步骤 2020 4 30 50 3 3确定初始基可行解 设给定线性规划问题 2020 4 30 51 因此约束方程组的系数矩阵为 添加松弛变量得其标准形为 2020 4 30 52 由于该矩阵含有一个单位子矩阵 因此 这个单位阵就
16、是一组基 就可以求出一个基可行解 说明 如果约束条件不全是形式 如含所有形式 则无法找到一个单位阵做为一组基 这时需要添加人工变量 称其为初始基可行解 2020 4 30 53 3 4从初始基可行解转换为另一个基可行解 思路 对初始基可行解的系数矩阵进行初等行变换 构造出一个新的单位矩阵 其各列所对应的变量即为一组新的基变量 求出其数值 就是一个新的基可行解 设有初始基可行解 并可设前m个分量非零 即 于是 2020 4 30 54 由构造初始可行基的方法知总可以使得前m个基向量恰好是一个单位阵 所以约束方程组的增广矩阵为 由于任意系数列向量均可由基向量组线性表示 则非基向量中的用基向量组线性表示为 2020 4 30 55 设有 则 1 2 得 由此式可知 我们找到了满足约束方程组的另一个解 要使其成为可行解 只要对所有i 1 2 m 下式成立 要使其成为基可行解 上面m个式中至少有一个取零 基可行解中非零分量的个数不超过m个 与比较 2020 4 30 56 只要取 于是前m个分量中的第l个变为零 其余非负 第j个分量为正 于是非零分量的个数 并可证得 线性无关 所以是新的基可行解
