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

《线性规划模型的分析及应用.ppt》由会员分享，可在线阅读，更多相关《线性规划模型的分析及应用.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

5、z=线性规划问题的标准型主要特点为 目标函数为最大化类型；所有的决策变量取非负值；约束条件均由等式表示；每一约束等式的右端常数均为非负值其缩写形式为:用向量和矩阵符号表述时为：Max z=CX向量 对应的决策变量 .用矩阵描述时为：称A为约束条件的 一般m0;b为资源向量 C为价值向量 X为决策变量向量。实际碰到各种线性规划问题的数学模型都应变换为标准型式后求解。3 线性规划问题的单纯形解法试以例试以例1来讨论它的求解。来讨论它的求解。例1的标准型为 (1.11)(1.12)约束方程(1.12)的系数矩阵从(1.12)中可以看到 的系数列向量 是线性独立的，这些向量构成一个基对于B的变量 为基

6、变量，从(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）。由这些资源中的薄弱环节，就确定了产品的产量。这儿就是由原材料B的数量确定产品的产量 件。为了求得以 为基变量的一个基可行解和进一步分析问题，需将（1.13）中 的位置与 的位置对调。得到

8、（1）（2）（1.16）（3）用高斯消去法，将（1.16）式中 的系数列向量 变换为单位列向量。其运算步骤是：=,并将结果仍按原顺序排列有：(1)(2)(1.17)(3)再将（1.17）代入目标函数（1.11）得到 (1.18)令非基变量 得到另一个基可行解 从目标函数的表达式（1.18）中可以看到，非基变量 的系数是正的，说明目标函数值还可以增大，不一定是最优解，于是再用上述方法确定 换入，换出变量，继续迭代，再得到另一个基可行解 再经过一次迭代，再得到一个基可行解 而这时得到目标函数的表达式是 (1.19)再分析（1.19），可见到所有非基变量 的系数都是非负。这说明若要用剩余资源 ，就必

9、须支付附加费用。所以当时，即不再利用这些资源时，目标函数达到最大值。所以 是最优解。第三部分第三部分 线性规划模型的应用线性规划模型的应用1运输问题的产销平衡的解法（表上作业法）运输问题的产销平衡的解法（表上作业法）表上作业法首先在表上给出一个初始方案（即初始基可行解）：表上作业法首先在表上给出一个初始方案（即初始基可行解）：然后，按照给出的准则对方案进行判别是否最优。如果所得方然后，按照给出的准则对方案进行判别是否最优。如果所得方案不是最优，则需要对所得方案进行调整。如此直到最优案不是最优，则需要对所得方案进行调整。如此直到最优下面通过例子说明表上作业法的方法与步骤。下面通过例子说明表上作业法的方法与步骤。设某产品从产地设某产品从产地 运往销地 运量和单价运价如表所示。问如何调运才能使总的运费最小？