线性规划与单纯形法-第1节.pptVIP

若要求目标函数实现最小化，即minz=CX。这时只需将目标函数最小化变换求目标函数最大化，即令z′=-z，于是得到maxz′=-CX。这就同标准型的目标函数的形式一致了。约束方程为不等式。这里有两种情况：一种是约束方程为“≤”不等式，则可在“≤”不等式的左端加入非负松弛变量，把原“≤”不等式变为等式；另一种是约束方程为“≥”不等式，则可在“≥”不等式的左端减去一个非负剩余变量(也可称松弛变量)，把不等式约束条件变为等式约束条件。下面举例说明。12如何变换为标准型：

（第三版）《运筹学》教材编写组编清华大学出版社运筹学第1章线性规划与单纯形法第1节线性规划问题及其数学模型钱颂迪制作二.线性规划与目标规划第1章线性规划与单纯形法第2章对偶理论与灵敏度分析第3章运输问题第4章目标规划第1章线性规划与单纯形法第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例第1节线性规划问题及其数学模型问题的提出图解法线性规划问题的标准形式线性规划问题的解的概念第1节线性规划问题及其数学模型线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法。1.1问题的提出从一个简化的生产计划安排问题开始资源产品例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。ⅠⅡ?拥有量设备128台时原材料A4016kg原材料B0412kg01每生产一件产品Ⅰ可获利2元，02每生产一件产品Ⅱ可获利3元，03问应如何安排计划使该工厂获利最多?该工厂续例1如何用数学关系式描述这问题，必须考虑数学模型例2.简化的环境保护问题靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。图1-10102第一化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米。第二化工厂处理工业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。续例2设：01第一化工厂每天处理工业污水量为x1万立方米，02第二化工厂每天处理工业污水量为x2万立方米03建模型之前的分析和计算数学模型每一个线性规划问题都用一组决策变量要有各种资源和使用有关资源的技术数据表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的；，创造新价值的数据；共同的特征存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;要有一个达到目标的要求，它可用决策变量的线性函数(称为目标函数)来表示。按问题的不同，要求目标函数实现最大化或最小化。共同的特征（继续）它们的对应关系可用表格表示：线性规划的一般模型形式例1是二维空间（平面）线性规划问题，可用作图法直观地来表述它的求解。01因存在02必须在直角坐标的第1象限内作图，求解。031.2图解法图1-2图1-3目标值在（4，2）点，达到最大值14目标函数01无穷多最优解(多重最优解)，见图1-402无界解，见图1-5-103无可行解，见图1-5-2可能出现的几种情况图1-4无穷多最优解(多重最优解)目标函数maxz=2x1+4x2图1-5-1无界解01当存在矛盾的约束条件时，为无可行域。02如果在例1的数学模型中增加一个约束条件:03该问题的可行域为空集，即无可行解