线性规划模型的分析及应用.ppt

《线性规划模型的分析及应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、题目线性规划模型分析及应用文章简介我的论文总体上分为三大部分。第一部分是线性规划的简介，主要介绍了线性规划的背景和发展。第二部分是线性规划的分析，主要对线性规划问题的提出，线性规划的图解法，线性规划问题的标准型，线性规划问题矩阵描述，线性规划问题的解的概念，线性规划问题的几何意义，线性规划问题的单纯形解法，线性规划的灵敏度分析等问题做出了具体的分析。第三部分是线性规划的应用，我主要讨论的是运输问题，主要分析了运输问题数学模型的特点，应用表上作业法来解产销平衡时的运输问题，而产销不平衡时的运输问题是把它转化为产销平衡时的运输问题来解。下面就由我为大家简单介绍一下这三部

2、分的重点内容：第一部分1背景线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法。线性规划的实用领域比较广泛，从解决技术问题的最优化设计到工业，农业，商业，交通运输业，军事，经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。第二部分1线性规划模型的特点:举例说明某工厂在计划期内要安排生产I、II、两种产品，已知生产单位产品所需的设备台时及A、B、两种原材料的消耗，如表1-1所示。ⅠⅡ设备128台时原材料A4016Kg原材料B0

3、412Kg该工厂每生产一件产品Ⅰ可获利2元，没生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多?这问题可以用以下的数学模型来描述，设、分别表示在计划期内产品Ⅰ、Ⅱ的产量。因为设备的有效台时8，这是一个限制产量的条件，所以在确定产品Ⅰ、Ⅱ的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为同理，因为原材料A,B的限量，可以得到以下不等式该工厂的目标是在不超过所有资源限量的条件下，如何确定产量，以得到最大的利润。若用z表示利润，这时，综合上诉，该计划问题可用数学模型表示为：目标函数max满足约束条件从以上例子可以看出，他们都是属于一类优化问题，他们的共同

4、特点：（1）每一个问题都用一组决策变量表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值是非负的。（2）存在一定的约束条件，这些约束条件可以用一组线性不等式表示。（3）都有一个要求达到目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划的数学模型，期一般形式为:目标函数max(min)（1.1）满足约束条件：（1.2）（1.3）在线性规划的数学模型中，方程(1.1)称为目标函数；（1.2），（1.3）称为约束条件；（1.3）也称为变量的非负约束条件。2线性规划问题的

5、标准型我们把具有m个约束条件和n个决策变量的如下线性规划模型称为线性规划的标准型。maxz=线性规划问题的标准型主要特点为①目标函数为最大化类型；②所有的决策变量取非负值；③约束条件均由等式表示；④每一约束等式的右端常数均为非负值其缩写形式为:用向量和矩阵符号表述时为：Maxz=CX向量对应的决策变量.用矩阵描述时为：称A为约束条件的一般m0;b为资源向量C为价值向量X为决策变量向量。实际碰到各种线性规划问题的数学模型都应变换为标准型式后求解。3线性规划问题的单纯形解法试以例1来讨论它的求解。例1的标准型为(1.11)(1.12)约束方程(1.12)的系数

6、矩阵从(1.12)中可以看到的系数列向量是线性独立的，这些向量构成一个基对于B的变量为基变量，从(1.12)中可以得到（1.13）将（1.13）代入目标函数(1.11)得到(1.14)当令非基变量便得到z=0.这时得到一个基可行解这个基可行解表示：工厂没有安排生产产品Ⅰ、Ⅱ;资源都没有被利用，所以工厂的利润指标z=0.从分析目标函数的表达式(1.14)可以看出：非基变量（即没有安排生产产品Ⅰ、Ⅱ）的系数都是正数，因此将非基变量变换基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就可以使工厂的利润指标增加。所以只要在目标函数(1.14)的表达式中还

7、存在有正系数的非基变量，这表示目标函数还有增加的可能，就需要将非基变量与基变量进行对换。一般选择正系数最大的那个非基变量为换入变量，将它换入到基变量中去，同时还需要确定基变量中有一个要换出来成为非基变量，可以按一下方法确定换出变量。现分析（1.13）当将定位换入变量后，必须从中换出一个，并保证其余的都是非负，即当由（1.13）式得到(1.15)从（1.15）中可以看出，只有选择时，才能使（1.15）成立。因此时，基变量这就决定用去替换以上数学描述说明了每生产一件产品Ⅱ，需要用掉各种资源数为（2,0,4）。由这些资源中的薄弱环节，就确定了产品Ⅱ的产量。这儿就是由原