线性规划问题及其数学模型.pptx

《线性规划问题及其数学模型.pptx》由会员分享，可在线阅读，更多相关《线性规划问题及其数学模型.pptx（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二.线性规划与目标规划第1 1章 线性规划与单纯形法第2章 对偶理论与灵敏度分析第3章 运输问题第4章 目标规划第1页/共42页第1章 线性规划与单纯形法第1节 线性规划问题及其数学模型第2节 线性规划问题的几何意义第3节 单纯形法第4节 单纯形法的计算步骤第5节 单纯形法的进一步讨论第6节 应用举例第2页/共42页第1节 线性规划问题及其数学模型1.1 问题的提出1.2 图解法1.3 线性规划问题的标准形式1.4 线性规划问题的解的概念第3页/共42页第1节 线性规划问题及其数学模型 线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能

2、处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法。1.1 问题的提出 从一个简化的生产计划安排问题开始第4页/共42页例 1 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。资源 产 品拥有量设 备1 2 8台时原材料 A 40 16 kg原材料 B04 12 kg第5页/共42页续例1 该工厂每生产一件产品可获利2元

3、，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多?第6页/共42页如何用数学关系式描述这问题，必须考虑第7页/共42页数学模型第8页/共42页例2.简化的环境保护问题 靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。第9页/共42页图1-1第10页/共42页续例2第一 化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需

4、各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米。第二 化工厂处理工业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。第11页/共42页建模型之前的分析和计算设：第一化工厂每天处理工业污水量为x1万立方米，第二化工厂每天处理工业污水量为x2万立方米 第12页/共42页数学模型第13页/共42页共同的特征(1)每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的；(2)要有各种资源和使用有关资源的技术数据，创造新价值的数据；第1

5、4页/共42页共同的特征（继续）(3)存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;(4)要有一个达到目标的要求，它可用决策变量的线性函数(称为目标函数)来表示。按问题的不同，要求目标函数实现最大化或最小化。第15页/共42页它们的对应关系可用表格表示：第16页/共42页线性规划的一般模型形式第17页/共42页1.2 图解法例1是二维空间（平面）线性规划问题，可用作图法直观地来表述它的求解。因存在 必须在直角坐标的第1象限内作图，求解。第18页/共42页图1-2第19页/共42页图1-3 目标值在（4，2）点，达到最大值14目标函数第20页/共42页可能出现的几种情

6、况（1）无穷多最优解(多重最优解)，见图1-4（2）无界解，见图1-5-1（3）无可行解，见图1-5-2第21页/共42页图1-4 无穷多最优解(多重最优解)目标函数 max z=2x1+4x2 第22页/共42页图1-5-1 无界解第23页/共42页 无可行解当存在矛盾的约束条件时，为无可行域。如果在例1的数学模型中增加一个约束条件:该问题的可行域为空集，即无可行解，第24页/共42页图1-5-2 不存在可行域增加的约束条件第25页/共42页1.31.3 线性规划问题的标准型式第26页/共42页线性规划问题的几种表示形式第27页/共42页用向量表示为：第28页/共42页用矩阵表示为：第29页

7、/共42页如何变换为标准型：(1)若要求目标函数实现最小化，即min z=CX。这时只需将目标函数最小化变换求目标函数最大化，即令z=-z，于是得到max z=-CX。这就同标准型的目标函数的形式一致了。(2)约束方程为不等式。这里有两种情况：一种是约束方程为“”不等式，则可在“”不等式的左端加入非负松弛变量，把原“”不等式变为等式；另一种是约束方程为“”不等式，则可在“”不等式的左端减去一个非负剩余变量(也可称松弛变量)，把不等式约束条件变为等式约束条件。下面举例说明。第30页/共42页例3 将例1的数学模型化为标准型。例1的数学模型,加松驰变量后第31页/共42页(3)若存在取值无约束的变

8、量xk,可令,其中。例4 将下述线性规划问题化为标准型第32页/共42页处理的步骤：(1)用x4-x5替换x3，其中x4，x50；(2)在第一个约束不等式号的左端加入松弛变量x6；(3)在第二个约束不等式号的左端减去剩余变量x7；(4)令z=-z，把求min z 改为求max z，即可得到该问题的标准型第33页/共42页例4的标准型第34页/共42页1.4 线性规划问题的解的概念1.可行解2.基3.基可行解4.可行基第35页/共42页1.可行解满足约束条件(1-5)，(1-6)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。第36页/共4

9、2页2.基，基向量，基变量第37页/共42页3.基可行解 满足非负条件（1-6）的基解，称为基可行解.基可行解的非零分量的数目也不大于m m，并且都是非负的。第38页/共42页4.可行基 对应于基可行解的基，称为可行基。约束方程组(1-5)具有基解的数目最多是 个。一般基可行解的数目要小于基解的数目。以上提到的几种解的概念，它们之间的关系可用图1-6表明。另外还要说明一点，基解中的非零分量的个数小于m个时，该基解是退化解。在以下讨论时，假设不出现退化的情况。以上给出了线性规划问题的解的概念和定义，它们将有助于用来分析线性规划问题的求解过程。第39页/共42页图1-6 它们之间的关系第40页/共42页小结1.线性规划问题的模型特征2.通过图解法了解如何求解线性规划问题3.为求解高维线性规划问题，必须建立的概念第41页/共42页感谢您的观看！第42页/共42页