线性规划与单纯形法(1-4节).ppt

1、第一页，第二章，线性规划和单纯形法，第二页，在生产管理和经营活动中，经常提出以下两类问题：1.利用有限的人力、物资、财力等资源安排生产，使产值最大化或利润最大化。 2、对于所授任务，如何统一安排，以最低人力、物资、财力等资源消耗完成任务。 第三页，对于这种生产的修订计划和组织提出的以达到最大利益或最小支付为目的的问题研究，构成了运营学的重要分支数学修订计划论。 第4页，第1节线性修正画问题及其数学模型第2节线性修正画问题的解法第3节线性修正画问题的标准型第4节线性修正画问题的解第5节线性修正画问题的几何意义第6节简单形法的基本原理第7节简单形法的应用第8节线性修正画的管理方面的应用第9节数据包

2、络分析， 第五页第一节线性修订问题及其数学模型，一、问题的提出，例1某厂在修订内生产I、II两种产品，了解生产单位产品所需的设备台时数、原材料a的消耗量、原材料b的消耗量，并将具体数据表示出来。 第6页，也知道每生产一个产品I利润为2元，每生产一个产品II可以获得3元，问如何安排生产订单才能获得工厂利润最多。 解：生产修订计划是确定生产产品I和II各有多少个。 因此，成为问题的决定变量是生产的产品I的数量、生产的产品II的数量。 需要生产的产品I的数量： x1需要生产的产品II的数量： x 2，7页，影响生产修订计划(即产品I和II的生产数量)的制约因素有3个，分别是： (1)设备台数限制：

3、x1x2(2)原材料a的数量限制问题的目标是使创造的利益最大，创造的利益值为z max z=2x1 3x2，可以表示为第8页，如上所述，要建立问题的数学模型，目的函数： maxz=2x1x3x2，约束条件：可以表示为第9页，工厂I的污染： 2万立方米/日。 工厂的排烟： 1.4万立方米/日。 第10页，根据环境保护的要求，河川中的污水含量请控制在0.2%以下。 为了环保，污水处理是必要的。 处理方式为： (1)河川自然净化：工厂1排出的污水流入工厂2后，20%被自然净化。 (2)工厂自行进行污水处理：工厂I的污水处理成本： 1000元/万立方米工厂II的污水处理成本： 800元/万立方米如何制

4、定污水处理修订计划，询问工厂的总污水处理成本为最低。 第11页，解：污水处理修订计划是确定工厂I和工厂II分别处理多少污水。 因此，问题的决定变量是在工厂I处理的污水，在工厂II处理的污水。 工厂I应处理的污水： x1万立方米工厂II应处理的污水： x2万立方米，第12页，影响污水处理修订计划(即工厂I和II的污水处理量)的制约因素有4个，分别为： (1)工厂I的污水处理量的上限： x1 1)工厂II的污水处理量生成可以表示为min z=1000 x1 800 x2、(4)工厂II以后的河流污水含量的0.2%限制：0.8(2-x1)(1.4-x2)/700.002、0.8x1x2的问题的数学模

5、型为目标函数： min z=1000 x1 800 x2、制约线性修正画问题的特征，从这两个例子可以看出，这些都是优化问题的一种，它们的共同特征是：对于各个问题，使用一系列的决定变量(。 一组决策变量的值通常表示采用非负值的具体方案。中的组合图层性质变更选项。 第16页有可用一组线性方程或线性不等式表示的约束。 任何一个都有要求表示的目标，其可以用决策变量的线性函数表示(称为目标函数)，并且对于某些问题，要求目标函数的最大化或最小化。第17页、第3页、线性修正图像问题的数学模型、满足上述三个条件的数学模型称为线性修正图像的数学模型：目标函数max(min) z=c1x1 c2x2 cnxn限制

6、条件a11x1 a12x2 a1nxn (=) b1a 21 x1a1nxn b2am1x1am2x2amn xn (=)，bm x1，x2， xn 0，第18页，4，线性修正像素问题数学模型的特征，1 .决定变量正负没有限定。 2 .约束可以是=、即，约束是决策变量的线性方程或不等式。 3 .每个约束的右端常数可以是正、负。 4 .目标函数要求可以极大，也可以极小。 5 .目标函数是决策变量的线性函数。 第19页，第2节线性校正图像问题的解法，第1，解法的步骤可以用解法解决2个或3个变量的线性校正图像问题。 并在笛卡尔坐标系上绘制所有约束不均匀公式的可能公用值范围。 中的组合图层性质变更选项

7、。 在第20页，公共值范围内的所有点都满足所有被称为线性校正图像可执行区域的约束。 在可执行领域的边界上改变方向的点称为可执行领域的顶点。 可执行区域的每个点满足所有约束，可执行区域的每个点称为线性修正图的可执行解。 在可执行领域中使目标函数极大或极小的可执行解称为最佳解。 最优解必然在可行区域的顶点得到。 定义，第21页，最大化目标函数：将目标函数沿正交坐标系所代表的直线沿法线方向向右上或左上平移，停止平移，直到该图的可执行区域(公共值范围)的边界点相交为止，第22页，最小化目标函数：将目标函数的正交坐标系所代表的直线沿法线方向向右下中的组合图层性质变更选项。 定义：位于同一目标函数表示的直

8、线上的点称为等值线，因为它们具有相同的目标函数值。 在第二十三页，获得目标函数直线与可执行区域相交的边界点坐标值。 这个边界值是问题的最佳解，代入目标函数求问题的最佳解。 第24页，例如目标函数： max z=2x1 3x2，约束条件：第25页，解： (1)共同可取值的范围： x1x2:直线x1x2=8的左下4x1 16 :画直线，x1，x2，4x2=12，x1x2=8，4 x1=16 (4)最佳解为x1=4，x2=2，其中，x1=4，x2=2，优化解为，x1=4，x2=2，优化解为，x1=4，x2=2，更优化解为，x1=4，x2=2，更优化解为，x1=4，x2=2，更优化解为，x1=4，x

9、最佳值为第z=14，28页，确定由约束围绕的区域，获得该区域的边界点，并且在列表中获得目标函数的最佳值。 二、图解法的改善顺序基于线性修正图像问题的最佳解，在其可执行区域的顶点取得。 第29页、x1、x2、4x2=12、x1x2=8、4x2=12、2 x1x2q1=(4，0，0 )； Q2=(4，2，2 )； Q3=(2，3，3 )； q4=(0，3，3 )，第30页，3，求解结果分析，最佳解是唯一的。 无限多最优解：目标函数直线与某约束直线平行。 无界解：可实行领域无界。 没有可行的解：没有可行的领域。 第31页，最佳解是唯一的。 目标函数： max z=2x1 3x2，限制条件：32页，目

10、标函数： max z=2x1 4x2，限制条件：无穷多最优解：目标函数直线与某限制条件直线平行。 第三十三页、第一页、第二页、第四页、第二页、第三页、第四页分析：目标函数直线与约束x1 2x28的边界平行。 第34页，目标函数： max z=2x1 3x2，约束条件：无界解：可执行领域无界。第35页，、x1、x2、4x2=12、4x1=16、x1 2x2=8，注意：可执行区域没有边界，可能没有最佳解，或者可能存在最佳解，但在这种情况下，最佳解必须在顶点获取。 第36页，无可执行解：无可执行域。 目的函数： max z=2x1 3x2、约束条件：第37页、x1、x2、4x2=12、x12x216

11、、4x2=12、(4)、38页、解析：如果求解结果出现3、4两种情况，则线性修正情况3可能缺少建模时所需的约束。 情况4可能是因为在建模时出现了不一致的约束。 图解法虽然直观简便，但变量达到3个以上则无力。 后一章要介绍的代数法的单纯形法是必要的。第39页、第3节线性修正图像问题的标准类型，鉴于线性修正图像问题模型形式的多样性，为了便于解决和讨论，对一般线性修正图像问题总是先作为标准形式的线性修正图像问题再进行分析或解决。 具有m个约束条件和n个决定变量的线性校正像素问题的标准，以及第40页的线性校正像素问题的标准，其中maxz=c1x1c2x2cn xns.t.a 11 x1a 12 x2a

12、1nxn=b1a 21 x1a 22 x2a2nxn=b2am1x1am2x2amn xn=BM其它xn 0格式1 (完全格式)、第41页、格式2 (简化格式)、第42页、格式3 (向量格式)、Max z=CX s.t. AX=b X0其中： C=(c1，)所有约束都是等式。 并非所有的决策变量都是负值。 每个约束条件右端的常量不是负数。 实际遇到的各种线性修正图问题的数学模型需要在转换为标准类型后解决。 二、线性修正图像问题标准型的四个特征：第44页，第3页，将线性修正图像问题的非标准型变换为标准型，第1页，将目标函数极小化：目标函数乘以-1，将成为等效的极大化问题。Min z=c x、Ma

13、x z=-c x、第45页、min z=- 2x1 - 3x2、max z=2x1 3x2、解：线性修正图模型的标准类型是：第46页新增的非负变量称为缓和变量。 (2)制约条件，从不等式的左端减去非负的新变量就成为等式。 新添加的非负变量称为剩馀的佗变量。 第、47页，max z=2x1 3x2，max z=2x1 3x2，解：导入缓和变量x3和x4，剩馀的佗变量x5。 因此，线性修正图像模型的标准类型是第，48页，第3页，决策变量不是非负值： (1)决策变量存在非正限制：以决策变量的倒数即新变量进行替换。 导入xj 0、新变量xj 0，设为xj=-xj。 将xj式代入线性修正图像模型，用xj

14、代替xj。 第49页，max z=2x1 3x2，max z=2x1 - 3x2，解：导入新的变量x2，设为x2=-x2。 线性修正模型的标准类型是，第50页，(2)决定变量符号不受限制(自由变量) :被两个非负的新变量替换。 导入新变量xj 0和xj 0，使xj=xj- xj，而不管xj正负。 将xj式代入线性修正像素模型，将xj替换为xj、xj。 第51页，max z=2x1 3x2，max z=213232，解：导入新的变量x2，x 2“0，x2=x2 x2”。 因此，线性修正图模型的标准型是，第52页，(3)决定变量有上下界：导入新变量，使原变量减去下限值，将模型中的原变量替换为新变量

15、，将新变量的上限约束转换为新的约束，转换为方程式。 导入a xj b、新变量xj，设定xj=xj -a、0 xj b-a。 将xj表达式(xj=xj a )代入线性修正模型，将xj变换为xj。 将xj b-a转换为约束，然后转换为方程式。第53页，max z=2x1 3x2，解：引入新的变量x2，将x2=x2、x2、x2=x2代入模型，将x2替换为x2，将x2转换为约束，将第54页max z=2x1 3 x2 9，第56页，max z=0 max z=2x1 3x2，解：第三个约束的两端分别乘以- 1。 因此，线性校正图像模型的标准类型是第(max z=2x 1，3 x 2，58 )页的第四节线性校正图像问题的