第2章 线性规划的图解法1.ppt

1、第一、二章线性计划的示意图法，第一题中提出的2度法3度法的灵敏度分析，第二章线性计划的示意图法，管理中的几个茄子典型线性计划应用节目合理利用盘存问题：生产保障条件下的最小材料问题：原材料供应限制下的最大利益投资问题：从投资项目中选择方案，最大化投资收益的最大产品生产计划：人力、物力、资金。也就是说，可以用最少的劳动力满足业务需求的运输问题：如何编制运输方案以最小化总运费；线性计划的构成：目标函数Max F或Min F约束s.t. (subject to)是以符号表示可控制因素的决策变量，提出3，1问题，实例1。如果您知道在计划期间生产两个产品、生产单位产品所需的设备台，则线性编程模型：目标函数

2、：Max z=50 x1 100 x2约束：s.t.x1 x2 300 2x1 x2 400x2 250x1，x2 0，4，1问题建议，建模流程1。理解要解决的问题，理解问题解决2。定义决定变数(x1，x2，xn)。每个值集代表一个方案。3.作为决策变量的线性函数编写目标函数，以确定最大化或最小化目标。4.表示问题解决到决策变量集的等式或不等式时要遵循的约束一般形式目标函数。Max (Min) z=C1 x1 C2 x2 cn xn约束条件：s.t. a11 x1 a12 x2 a1n xn (=，)b1a21x1a22x2a2nxn (=，)b2am1x1am2x2amnxn目标函数：Max

3、 z=50 x1 100 x2约束：s . t . x1 x2 300(a)2x1 x2 400(b)x2 250(c)x1 0(d)x2 0(;a)；2图解，对于只有两个决定变量的线性规划问题，可以通过在平面直角坐标系中绘制表示线性规划问题的概念来解决。以下将通过示例1详细说明该方法。6，2度法，(1)每个确定变量X1，X2设定坐标矢量的直角坐标系。在直角坐标系中，图形中任意点的坐标表示决策变量的一组值。示例1中的每个约束表示一个半平面。7，2度解，(2)对于每个不等式(约束)，首先用方程在坐标系中创建直线，然后确定不等式确定的半平面。8，2度法，(3)将5个图形合并为一个图形，以获取每个约

4、束的公共部分，如图2-1所示。9，2图解解释，(4)目标函数z=50 x1 100 x2，z获得固定值时的直线。善意所有点都具有相同的目标函数值，称为等值线。平行移动等值线和移动到B点时，Z在可执行字段内最大化。a、B、C、D、E是可执行域中的顶点，受限制约束的可执行域中的顶点也有限制。10，2度法，线性编程的标准化内容之一：在李莞变量(资源的余量)引入实例1中，S1，S2，S3被建模为目标函数。Max z=50 x1 100 x2 0 S1 0 S2 0 S3约束条件：s . t . x1 x2 S1=300 2 x1 x2 S2=400 x2 S3=250 x1，x2，S1，S2，S3 0

5、最佳解决方案x1=50 x2，11，2度解，重要结论：如果线性规划中存在最优解，则可行域的顶点应与最优解相对应。无限多的最佳解决方案。如果将示例1中的目标函数更改为max z=50 x1 50 x2，则线段BC上的所有点都表示最佳解决方案。没有界限。可行字段的范围无限扩展。目标函数值可以是无限或无限。一般来说，这表明模型错误，忽略了必要的约束条件。没有可行的解决方案。在示例1的数学模型中再添加一个约束4x1 3x21200，可执行的域是空域，没有满足约束的解，当然没有最优解。12，进一步讨论，例2某公司因生产要求，总A，B两种茄子原料至少需要350吨(A，B两种茄子材料有一定的替代性)，其中A

6、原料至少购买125吨。但是A，B的两种茄子原料的规格不同，因此各自需要的加工时间也不同。加工每吨A原料需要2小时，加工每吨B原料需要1小时，公司总共有600小时的加工时间。还知道每吨A原料的价格是2万韩元，每吨B原料的价格是3万韩元。在满足生产要求的前提下，在公司的加工能力范围内，如何购买A，B两种茄子原料，使购买成本降至最低？13，详细说明，解决方法：目标函数：Min f=2x1 3 x2约束条件：s.t. x1 x2 350 x1 125 2 x1 x2 600 x1，使用x2 0图形。下图：Q点坐标(250，100)是最佳解决方案。14，3度敏感度分析，线性计划的标准化一般格式目标函数：

7、Max z=C1 x1 C2 x2 cn xn约束条件：s.t. a11 x1 a12 x2 a1n xn (=，)b1a21x1a22x2a2nxn (=)约束为方程式；决策变量不是负数。右边的项目不是负数。对于各种非标准格式的线性规划问题，始终可以通过以下转换将其转换为标准格式：16，3图的灵敏度分析：1.最小化目标函数的问题。可以通过将目标函数设置为Min f=c1x1 c2x2 cnxn(示例)来创建z -f。也就是说，Max z=-c1x1-c2x2 - cnxn对上述两个问题的最佳解决方案相同，但需要注意的是，最佳解决方案的目标函数值与一个茄子符号(Min f-Max z，17，3

8、图)的敏感度分析不同。2、约束不是等式的问题。将约束设置为ai1 x1 ai2 x2 ain xn bi后，可以引入新变量s，使约束右和左之间的差值s=bi(ai1 x1 ai2 x2 ain xn)。s也有非负约束，即s0牙齿。新的约束条件是ai1 x1 ai2 x2 ain xn s=bi，18，3示意图的敏感度分析，如果约束条件是ai1 x1 ai2 x2 ain xn bi，则s=(ai1 x1 ai2 x2 ain xn)- bi显然也不是S。此时，新的约束成为ai1 x1 ai2 x2 ain xn-s=bi，19，3度式的敏感度分析，在不等式中引入约束的变量S在不等式“小于或等于

9、”时称为“松弛变量”。不等式“大于或等于”时，称为“剩馀变量”。如果原始问题中有多个非等约束，则转换为标准格式时，必须为每个约束引入不同的松弛变量。3 .右侧项目具有负值的问题：在标准格式中，右侧项目的每个元件都不能为负值。当右端系数为负值(例如bi0)时，等式约束的两端乘以-1，结果为-ai1 x1-ai2 x2- -ain xn=-bi。20，3图表的敏感度分析，例如，将以下线性规划问题转换为标准格式min f=2 x1-3x 2 4x 3s . t . 3x 1 4x 2-5x 3 2x 1x 3 8x1x 2x 3=-9x 1、x2、x30解决方案将转换为函数最大化：z=-3x 3第三

10、个约束条件的右端值为负值，等式两边乘以-1。通过21，3度法的灵敏度分析，上述转换，得到了以下标准形式的线性规划问题：最大z=-2x 1 3x 2-4x 3s . t . 3x 1 4x 2-5x3x 4=62x 1x 3-X5=8-；如果变量XJ没有非负约束，则可以创建XJ=xj- XJ 。其中xj0，XJ 0是两个非负变量的差异，表示无符号变量。当然，XJ的符号取决于XJ和XJ 的大小。22，3度法的敏感度分析，敏感度分析：构建数学模型并求出最佳解决方案后，研究线性计划中一个或多个参数(系数)ci、AIJ、bj发生变化时对最佳解决方案的影响。在3.1目标函数中，系数ci的灵敏度分析考虑了实

11、例1，ci的变化仅影响目标函数等值线的斜率，目标函数z=50 x1 100 x2在z=x2 (x2=z斜率0)中z=x1 x2 (x2=-x1 z斜率-1) 整理0 C1 100假设产品的利润为50元，即C1=50，世代式(*)整理50 C2。 假设产品，利润分别为60韩元和55韩元，则-2-(60/55)-1如果是，最佳解决方案为z=x1 x2和z=2 x1 x2的交点x1=100，x2=200。24，3度法的灵敏度分析、3.2约束中右系数bj的灵敏度分析约束中右系数bj的变化可能导致线性计划的可行域发生变化，从而导致最佳解决方案的变化。请考虑示例1中的情况。设备支架增加10个后，更改为B1牙齿310将扩大可行域，从而成为x2=250和x1 x2=310的交点x1=60，x2=250牙齿的最佳解决方案。变更后总收益-变更前总收益=增加收益(5060 100250)-(50 50 100 250)=500，500/10=50元表示，在某个范围内每增加(减少)一台设备，设备能力就可能增加。25，3示意图的灵敏度分析，如果原料A增加10公斤，B2变为410，则可能的域变大，但最佳解决方案仍然是x2=250和x1 x2=300的交点x1=50，x2=250。更改牙齿不会影响总利润。牙齿约