线性代数 教学课件 ppt 作者 张德全PPT课件 6.2线性规划.ppt

《线性代数 教学课件 ppt 作者 张德全PPT课件 6.2线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章线性经济模型简介投入产出模型简介6.1单纯形法6.3线性规划6.26.2线性规划一、规划线性问题的数学模型二、线性规划问题的标准形式三、线性规划问题的几个基本概念四、两个变量线性规划问题的图解法一、规划线性问题的数学模型例1某工厂生产甲、乙两种产品，要用A,B,C三种不同的原料，从工艺资料知道：每生产1件甲种产品，需用三种原料分别为1，1，0单位；生产1件乙种产品，需用三种原料为1，2，1单位；每天原料供应的能力分别为6，6，3单位。又知道，每生产1件甲、乙产品，工厂利润收入分别为3千元和4千元，问：工厂应如何安排计划，使一天的总利

2、润为最大？解：为了解决这个问题，首先需要建立它的数学模型。建立数学模型一般要经过以下四步：第一步，明确问题的条件。一般可以将问题的条件列成表格形式，如下表6－3第二步，明确问题的变量。为了做出决策，我们把决策中关键量设为未知量，这种变量称为决策变量。本例中，设产品甲的日产量为件，产品乙的日产量为件。显然，它们都是非负的，即第三步，明确问题的目标。该问题的目标是在现有条件下，追求最大的利润。设该工厂一天获得的总利润为S，则依题意得问题就是要求它的最大值，因此，目标函数为第四步，明确问题的约束条件。由于每天的原料供应限制，A种原料每天只能供给

3、6个单位，所以一天生产甲、乙两种产品所消耗A种原料不得超过6个单位，即第四步，明确问题的约束条件。由于每天的原料供应限制，A种原料每天只能供给6个单位，所以一天生产甲、乙两种产品所消耗A种原料不得超过6个单位，即类似地，有因此，对变量的限制为约束条件综合上述分析，我们可以写出该问题的数学模型如下约束条件目标函数例2某建设工地，需要直径相同、长度不同的成套钢筋，每套由7根2m长和2根7m长的钢筋组成，今有15m长的钢筋150根，问怎样下料，才能使废料最少？解：把一根15m长的钢筋割成分别为7m和2m的两种规格，有三种比较经济的方法，如表6－

4、4所示。S表示废料的总长度。依题意，得把分别表示采用上述三种方法割料的15m长的钢筋的根数，又由于每套由7根2m长，2根7m长的钢筋组成，而2m长有根7m长有根，根据配套要求，有问题的目标是废料最少，总废料长为综合上述讨论，得到该问题的数学模型为：总结从以上两例子可以看出，它们都属于优化问题，并具有以下共同特征：（1）每一个问题都可以用一组称为决策变量的未知量来表示某种方案，这组未知变量的一组定值就代表一个具体方案。通常，要求这些未知量的取值是非负的。（2）每个问题都存在一定的限制条件，这些限制条件都可能用决策变量的一组线性等式或线性不等

5、式来表示。（3）都有一个目标，并且这个目标可以表示为决策变量的线性函数，并按问题的要求，求这个目标函数的最大（小）值。线性规划问题的数学模型的定义一般地，这类问题都可用数学语言描述如下：求一组变量的值，使其满足约束条件并使函数达到最大（小）值，其中均为常数。这就是线性规划问题的数学模型。线性规划问题的数学模型的一般形式是简记为二、线性规划问题的标准形式定义1下述线性规划问题的数学模型称为线性规划问题的标准形式。线性规划问题的标准形式有以下特点：1.求目标函数的最大值。2.所有的约束方程都用等式表示。3.所有的变量都是非负的。4.约束方程等

6、式右边的常数（称为约束常数）都是非负的。上述标准形式还可以简写为矩阵表示化为标准形1.化小为大2.化不等式为等式松弛变量松弛变量3.化负为正4.化“无非负限制”为正第i个约束方程的两边同乘以—1例3试将下面的线性规划问题化为标准形式：解：例4试将下面的线性规划问题化为标准形式：解：三、线性规划问题的几个基本概念定义2在线性规划问题中，满足约束条件的解，称为可行解。一般来说，线性规划问题可能有无穷多个可行解，也可能没有可行解。使目标函数达到最大值或最小值的可行解，称为最优解。将最优解代入目标函数，所得到的目标函数值，称为最优值。定义3在线性

7、规划问题中，设约束方程AX=b中的系数矩阵A的秩r(A)=m,B是矩阵A中任一m×m阶的非奇异矩阵,则称B为该线性规划问题的一个基。基向量、非基向量、基变量、非基变量B的列向量称为基向量N的列向量称为非基向量基向量对应的变量xj称为基变量非基变量所对应的变量称为非基变量基本解、基本可行解、基可行解、最优基可行解定义4：在线性规划问题中，非基变量取零值时所得到的解称为基本解。如果基本解又满足非负条件，则称为基本可行解，简称基可行解。能使目标函数达到最优的基可行解，称为最优基可行解。基本可行解一定是基本解，也一定是可行解，但反之不成立。例5写

8、出下列线性规划问题的所有基阵：解：约束方程组的系数矩阵及各列向量分别为知都是非奇异矩阵，所以都是这一问题的基。四、两个变量线性规划问题的图解法例6用图解法求解下列线性规划问题：解：（1）画出可