《经济数学基础配套教学课件 顾静相 经济数学基础 教学课件 作者 顾静相 teaching 09 07》由会员分享，可在线阅读，更多相关《经济数学基础配套教学课件 顾静相 经济数学基础 教学课件 作者 顾静相 teaching 09 07（99页珍藏版）》请在金锄头文库上搜索。
1、9 7 1线性规划数学模型 9 7 2线性规划问题的标准形式 9 7 3线性规划问题的几个基本概念 9 7 4两个变量线性规划问题的图解法 9 7线性规划问题 由于实际问题往往比较复杂 建立线性规划数学模型时 对某一问题要认真分析 抓住最本质的因素 用简单的数学式子将其描述出来 使建立的数学模型既简单 又能正确地反映问题的本质 9 7 1线性规划数学模型 返回 1 93 上一页 上一页 例1某工厂用甲 乙两种原料生产 型三种产品 已知生产一吨 型产品需要甲原料3吨 乙原料1吨 生产一吨 型产品需要甲原料1吨 乙原料2吨 生产一吨 型产品需要乙原料2吨 生产一吨 型产品可以分别获得利3千元 5千
2、元和2千元 该工厂现有50吨甲原料 60吨乙原料 问在现有条件下 应如何组织生产才能使利润最大 9 7 1线性规划数学模型 返回 2 93 解首先 把实际问题的含义搞清楚 一般可以将问题的条件列成表格 如表9 5 9 7 1线性规划数学模型 返回 3 93 其次 设决策变量为第种产品的生产总量 那么 然后 明确问题所追求的目标 该问题的目标是在现有条件下 追求最大的利润 9 7 1线性规划数学模型 返回 4 93 因为生产一吨 型产品可以分别获利3千元 5千元 2千元 那么生产吨 型产品 吨 型产品 吨 型产品可以分别获利千元 千元 千元 所以总利润为 即该问题的目标函数是 9 7 1线性规划
3、数学模型 返回 5 93 因为生产吨 型产品 吨 型产品 吨 型产品所需要的甲原料量为 9 7 1线性规划数学模型 返回 6 93 再明确问题中所有的约束条件 建立约束方程组 9 7 1线性规划数学模型 返回 7 93 综合上述分析 得该问题的数学模型为 9 7 1线性规划数学模型 返回 8 93 例2某铸造厂生产的铸件至少需要2个单位 每单位10 铅 2 4个单位铜 3个单位铁 现有4种合金材料可供选用 它们每单位中所含成份和价格如表9 6所示 问每种合金材料选用多少才能使费用量少 试列出数学模型 9 7 1线性规划数学模型 返回 9 93 9 7 1线性规划数学模型 返回 10 93 即目
4、标函数为 9 7 1线性规划数学模型 返回 11 03 解设四种合金材料分别选购单位 那么 该问题追求的目标是使购买合金材料的费用最少 由于四种合金材料的选购量是 那么总费用为 同样可得铸件中铜和秩和含量约束方程 9 7 1线性规划数学模型 返回 12 93 约束条件是铸件中铅的含量不少于2个单位 即 所以 该问题的数学模型为 9 7 1线性规划数学模型 返回 13 93 例3用长度300cm的条材 截成长度分别为90cm和70cm的两种坯料 要求共截出长90cm的坯料1万根 70cm的坯料2万根 问怎样截法才能使所用条材最少 试建立它的数学模型 9 7 1线性规划数学模型 返回 14 93
5、解首先把300cm长的条材截成长度分别为90cm和70cm的两种坯料 有四种比较经济的方法可供选用 如表9 7 9 7 1线性规划数学模型 返回 15 93 设变量分别为种下料方式所用条材数量 那么 问题所追求的目标是使用的条材总数 最少 即目标函数为 9 7 1线性规划数学模型 返回 16 93 因为四种截料方式获得90厘米的坯料为 它的需求量是10000根 所以这一约束方程为 同样可得70厘米长的坯料约束方程为 9 7 1线性规划数学模型 返回 17 93 综合上述分析 可以写出该问题的数学模型 9 7 1线性规划数学模型 上述问题均属于优化问题 它们具有以下共同特征 返回 18 93 1
6、 每一个问题都可用一组变量来表示 这组变量的一组定值就代表一个具体方案 通常要求这些变量取值是非负的 2 存在一定的约束条件 这些约束条件都可以用一组线性等式或线性不等表达 3 都有一个目标 这个目标可以表示为一组变量的线性函数 并按照问题的要求 求其最大值或最小值 9 7 1线性规划数学模型 返回 19 93 目标函数 其中 均为常数 9 7 1线性规划数学模型 返回 20 93 称 9 7 1 式为线性规划问题的数学模型一般形式 简写为 注意 有时将称为变量的非负约束 9 7 1线性规划数学模型 返回 21 93 规定标准形式有以下特点 1 求目标函数的最大值 2 所有的约束方程都用等式表
7、示 3 所有的变量都是非负的 4 约束方程等式右端的常数 称为约束常数 都是非负的 9 7 2线性规划问题的标准形式 返回 22 93 线性规划问题的标准形式 9 7 2线性规划问题的标准形式 返回 23 93 或写成 9 7 2线性规划问题的标准形式 返回 24 93 用矩阵表示 9 7 2线性规划问题的标准形式 返回 25 93 9 7 2线性规划问题的标准形式 返回 26 93 一般形式化为标准形式可分为以下几种情况 9 7 2线性规划问题的标准形式 返回 27 93 当约束方程是 约束时 如第个方程为 9 7 2线性规划问题的标准形式 返回 28 93 当约束方程是 约束时 如第个方程
8、为 可在上式 号的左端减去一个非负新变量 使得 其中也称为松驰变量 9 7 2线性规划问题的标准形式 返回 29 93 3 当某一个变量无非负约束时 可以用两个非负新变量 替换 只须将 代入原问题的数学模型中 4 当约束常数时 只须在第个约束方程的左 右两端分别乘上 1 便可得 9 7 2线性规划问题的标准形式 返回 30 93 例4将下列线性规划问题化为标准形式 9 7 2线性规划问题的标准形式 返回 31 93 解首先检查变量的非负约束情况 然后将目标函数化为求 令 得目标函数 9 7 2线性规划问题的标准形式 原问题中的变量都有非负约束 即 所以进行下一步 返回 32 93 再对含有不等
9、号的约束方程 引入松驰变量 使约束条件变为 9 7 2线性规划问题的标准形式 返回 33 93 最后在含有 的约束常数所在的方程两边同乘 1 使之变为 9 7 2线性规划问题的标准形式 返回 34 93 9 7 2线性规划问题的标准形式 原问题的标准形式 返回 35 93 设线性规划问题 9 7 3线性规划问题的几个基本概念 返回 36 93 基 设约束方程组中的系数矩阵的秩为 是矩阵中任一的非奇异矩阵 即 则称是该线性规划问题的一个基 9 7 3线性规划问题的几个基本概念 不妨设 其中是一个基 且 那么把与列对应的变量称为基变量 其它的变量称为非基变量 返回 37 93 基本解 把非基变量取
10、值为零的解称为线性规划问题的基本解 即 其中为基变量列向量 为非基变量列向量 9 7 3线性规划问题的几个基本概念 返回 38 93 可行解 满足约束条件的解称为可行解 可行域 满足约束条件的解组成的一个区域称为可行域 9 7 3线性规划问题的几个基本概念 返回 39 93 基本解可能是可行解 也可能不是可行解 只有当基本解中的每一个分量都非负时 它是可行解 反之 可行解也不一定是基本解 基本可行解 满足约束条件的基本解称为基本可行解 即 可行基 对应于基本可行解的基称为可行基 基本可行解一定是基本解 也一定是可行解 但反之不成立 同理 可行基一定是线性规划问题的一个基 反之不成立 9 7 3
11、线性规划问题的几个基本概念 最优解 使目标函数达到最大值或最小值的可行解 称为最优解 最优解是一个可行解 但不一定是基本可行解或基本解 返回 40 93 基本最优解 使目标函数达到最大值或最小值的基本可行解称为基本最优解 最优基 对应于基本最优解的基 称为最优基 9 7 3线性规划问题的几个基本概念 返回 41 93 例5设线性规划问题 9 7 3线性规划问题的几个基本概念 返回 42 93 1 如果取 它们满足约束条件 所以 是这一问题的一个可行解 9 7 3线性规划问题的几个基本概念 返回 43 93 同样 若取 它们也满足约束条件 所以 也是这一问题的一个可行解 当时 令 9 7 3线性
12、规划问题的几个基本概念 返回 44 93 由 得 取 那么 9 7 3线性规划问题的几个基本概念 返回 45 93 也是这一问题的可行解 这说明两个可行解之间联线上的点都是可行解 如果我们再取另两个可行解 同样可以得到这一结果 由此可知线性规划问题的任意两个可行解联线上的点都是可行解 9 7 3线性规划问题的几个基本概念 返回 46 93 2 原问题的标准形式是 9 7 3线性规划问题的几个基本概念 返回 47 93 那么这一问题的约束方程组 9 7 3线性规划问题的几个基本概念 的系数矩阵为 返回 48 93 令 9 7 3线性规划问题的几个基本概念 返回 49 93 由 可知 矩阵 都是这
13、一问题的基 9 7 3线性规划问题的几个基本概念 返回 50 93 3 对应基的基变量是 非基变量是 9 7 3线性规划问题的几个基本概念 返回 51 93 因为 那么由非基变量 表示基变量 的方程组为 9 7 3线性规划问题的几个基本概念 返回 52 93 当非基变量时 基变量 所以 基是一个可行基 对应的解是基本可行解 9 7 3线性规划问题的几个基本概念 对应的目标函数值为 返回 53 93 因为 4 对应于基的基变量是 非基变量是 9 7 3线性规划问题的几个基本概念 返回 54 93 那么由非基变量 表示基变量 的方程组为 9 7 3线性规划问题的几个基本概念 返回 55 93 当非
14、基变量时 基变量 所以 基是一个可行基 对应的解是基本可行解 对应的目标函数值为 9 7 3线性规划问题的几个基本概念 返回 56 93 5 对应于基的基变量是 非基变量是 因为 9 7 3线性规划问题的几个基本概念 返回 57 93 9 7 3线性规划问题的几个基本概念 返回 58 93 9 7 3线性规划问题的几个基本概念 那么由非基变量 表示基变量 的方程组为 返回 59 93 当非基变量时 基变量 所以 基是一个可行基 对应的解是基本可行解 对应的目标函数值为 9 7 3线性规划问题的几个基本概念 返回 60 93 6 对应于基的基变量是 非基变量是 9 7 3线性规划问题的几个基本概
15、念 因为 返回 61 93 那么由非基变量 表示基变量 的方程组为 9 7 3线性规划问题的几个基本概念 返回 62 93 当非基变量时 基变量 所以 基不是可行基 对应的解 9 7 3线性规划问题的几个基本概念 只是一个基本解 并不是一个可行解 所以 不是一个基本可行解 返回 63 93 上述几个基本概念之间的关系如下 9 7 3线性规划问题的几个基本概念 返回 64 93 例6用图解法求解例5中的线性规划问题 解例5的线性规划问题是 9 7 4两个变量线性规则问题的图解法 返回 65 93 首先 在直角坐标系中画出直线 9 7 4两个变量线性规则问题的图解法 返回 66 93 9 7节例6
16、示意图1动画演示 然后 确定约束条件所围成的可行域 因为 2 满足约束方程的点都在直线的左半平面内 9 7 4两个变量线性规则问题的图解法 返回 67 93 1 满足约束方程的所有点都在直线的左下方的半平面内 9 7节例6示意图2动画演示 3 满足约束方程的点都在直线的下半平面内 9 7 4两个变量线性规则问题的图解法 返回 68 93 9 7节例6示意图3动画演示 所以 同时满足上述五个约束方程的点组成的区域就是这五个半平面的公共部分即 我们称多边形为该线性规划问题的可行域 9 7 4两个变量线性规则问题的图解法 返回 69 93 9 7节例6示意图4动画演示 接下来在可行域上寻找使目标函数取值最大的可行解 即把中的看作是一个参数 当取定值时 如取 那么是一条直线 而且这条直接上的任何一点都使目标函数取 0 值 我们称此直线为目标函数等值线 如果我们再取 8 12 我们会得到一族平行的目标函数等值线 9 7 4两个变量线性规则问题的图解法 返回 70 93 9 7 4两个变量线性规则问题的图解法 返回 71 93 由图可以看出 当取值越大 目标函数等值线就越往右上方平行移动 但这样的
