《线性代数教学课件作者张德全课件6.2线性规划》由会员分享，可在线阅读，更多相关《线性代数教学课件作者张德全课件6.2线性规划（32页珍藏版）》请在金锄头文库上搜索。
1、,第六章 线性经济模型简介,投入产出模型简介,单纯形法,线性规划,6.2 线性规划,一、规划线性问题的数学模型,例1 某工厂生产甲、乙两种产品，要用A,B,C三种不同的原料，从工艺资料知道：每生产1件甲种产品，需用三种原料分别为1，1，0单位；生产1件乙种产品，需用三种原料为1，2，1单位；每天原料供应的能力分别为6，6，3单位。又知道，每生产1件甲、乙产品，工厂利润收入分别为3千元和4千元，问：工厂应如何安排计划，使一天的总利润为最大？,解： 为了解决这个问题，首先需要建立它的数学模型。 建立数学模型一般要经过以下四步： 第一步，明确问题的条件。一般可以将问题的条件列成表格形式，如下表63,
2、第二步，明确问题的变量。,为了做出决策，我们把决策中关键量设为未知量，这种变量称为决策变量。本例中，设产品甲的日产量为件，产品乙的日产量为件。显然，它们都是非负的，即,第三步，明确问题的目标。,该问题的目标是在现有条件下，追求最大的利润。设该工厂一天获得的总利润为S，则依题意得,问题就是要求它的最大值，因此，目标函数为,第四步，明确问题的约束条件。由于每天的原料供应限制，A种原料每天只能供给6个单位，所以一天生产甲、乙两种产品所消耗A种原料不得超过6个单位，即,第四步，明确问题的约束条件。,由于每天的原料供应限制，A种原料每天只能供给6个单位，所以一天生产甲、乙两种产品所消耗A种原料不得超过6
3、个单位，即,类似地，有,因此，对变量 的限制为,约束条件,综合上述分析，我们可以写出该问题的数学模型如下,约束条件,目标函数,例2 某建设工地，需要直径相同、长度不同的成套钢筋，,每套由7根2m长和2根7m长的钢筋组成，今有15m长的钢筋150根，问怎样下料，才能使废料最少？ 解：把一根15m长的钢筋割成分别为7m和2m的两种规格，有三种比较经济的方法，如表64所示。,S表示废料的总长度。依题意，得,把分别表示采用上述三种方法割料的15m长的钢筋的根数，,又由于每套由7根2m长，2根7m长的钢筋组成，而2m长有 根,7m长有 根，根据配套要求，有,问题的目标是废料最少，总废料长为,综合上述讨论
4、，得到该问题的数学模型为：,总结,从以上两例子可以看出，它们都属于优化问题，并具有以下共同特征： （1）每一个问题都可以用一组称为决策变量的未知量来表示某种方案，这组未知变量的一组定值就代表一个具体方案。通常，要求这些未知量的取值是非负的。 （2）每个问题都存在一定的限制条件，这些限制条件都可能用决策变量的一组线性等式或线性不等式来表示。 （3）都有一个目标，并且这个目标可以表示为决策变量的线性函数，并按问题的要求，求这个目标函数的最大（小）值。,线性规划问题的数学模型的定义,一般地，这类问题都可用数学语言描述如下：求一组变量的值，使其满足约束条件,并使函数,达到最大（小）值，其中,均为常数。
5、这就是线性规划问题的数学模型。,线性规划问题的数学模型的一般形式是,简记为,二、线性规划问题的标准形式,定义1 下述线性规划问题的数学模型,称为线性规划问题的标准形式 。,线性规划问题的标准形式有以下特点：,1.求目标函数的最大值。 2.所有的约束方程都用等式表示。 3.所有的变量都是非负的。 4.约束方程等式右边的常数（称为约束常数）都是非负的。,上述标准形式还可以简写为,矩阵表示,化为标准形,1.化小为大,2.化不等式为等式,松弛变量,松弛变量,3.化负为正,4.化“无非负限制”为正,第i个约束方程的两边同乘以1,例3 试将下面的线性规划问题化为标准形式：,解：,例4 试将下面的线性规划问
6、题化为标准形式：,解：,三、线性规划问题的几个基本概念,定义2 在线性规划问题中，满足约束条件的解， 称为可行解。,一般来说，线性规划问题可能有无穷多个可行解， 也可能没有可行解。 使目标函数达到最大值或最小值的可行解，称为最优解。将最优解代入目标函数，所得到的目标函数值，称为最优值。,定义3 在线性规划问题,中，设约束方程AX=b中的系数矩阵A的秩r(A)=m, B是矩阵A中任一 mm 阶的非奇异矩阵,则称B为该线性规划问题的一个基。,基向量、非基向量、基变量、非基变量,B的列向量称为基向量,N的列向量称为非基向量,基向量对应的变量xj 称为基变量,非基变量所对应的变量称为非基变量,基本解、
7、基本可行解、基可行解、最优基可行解,定义4 ： 在线性规划问题中，非基变量取零值时所得到的解称为基本解。 如果基本解又满足非负条件，则称为基本可行解，简称基可行解。 能使目标函数达到最优的基可行解，称为最优基可行解。,基本可行解一定是基本解，也一定是可行解，但反之不成立。,例5 写出下列线性规划问题的所有基阵：,解： 约束方程组的系数矩阵及各列向量分别为,知 都是非奇异矩阵， 所以 都是这一问题的基。,四、两个变量线性规划问题的图解法,例6 用图解法求解下列线性规划问题：,解： （1）画出可行域； （2）画出等值线； （3）求出最优解。,因此，方程 的交点坐标为（4，2），该问题的最优解为： 对应的目标函数值为：Z=14。,线性规划问题中解的情况有以下几种：,（1）唯一解（如上例）；（2）无穷多最优解； （3）无界解； （4）无可行解。,无穷多最优解,无界解,无界解,无可行解,无可行解,
