线性规划与单纯形法.ppt

1、第二章是线性规划和单纯形法，第二章是线性规划和单纯形法，第一节是线性规划问题及其数学模型，第二节是图解法，第四节是单纯形法原理及其计算步骤，第五节是人工变量法，第六节是小结，第一节是线性规划问题及其数学模型，第一节是如何合理利用有限的人力、物力和财力以获得最佳的经济效果。第一节线性规划问题及其数学模型，例1:如何用边长为a的方形铁片切割容器，使容器体积最大化(如下图所示)。第1节线性规划问题及其数学模型，例1:解决方法：在铁皮的四个角上，切下四个边长为x的正方形。V=(a-2x)(a-2x)xmax满足xa/2 x0，第1节线性规划问题及其数学模型，例2:一个企业计划生产两种产品，分别应在a、

2、b、c，根据工艺数据的规定，生产每种产品所需的设备为2、1、4、0(小时)，生产每种产品所需的设备为2、2、0、4(小时)。众所周知，在规划期内，每台设备生产这两种产品的能力分别为12、8、16和12(小时)，而且众所周知，每生产一种产品可以盈利2元，每生产一种产品可以盈利3元。问：企业应该如何安排生产两种产品的数量，以使企业的利润和收入最大化？第1节线性规划问题及其数学模型，示例2:解决方案：假设计划期内两个产品的产量为x1，x2z=2x13x2max 2x212x212x28，满足4x116 4x212 x1，x20，表示形式，第1节线性规划问题及其数学模型，2。数学规划研究，在给定的条件

3、下，从某种意义上找到被研究函数的极值。第1节线性规划问题及其数学模型，特征(1)决策变量(2)约束(3)目标函数，第1节线性规划问题及其数学模型，3)线性规划问题的特征(三要素)(1)决策变量：问题中的未知数(2)目标函数：问题要达到的目标(最大或最小)， 表示为决策变量的线性函数(3)约束：表示为一组非矛盾的线性等式或线性不等式的函数约束，带有决策变量和非负约束的决策变量，第1节线性规划问题及其数学模型，V=(a-2x)(a-2x)xmaxxa/2x 0z=2x 13 x2 max 2x 212 x28 4x 116 4x 212 x1，x20，第1节线性规划问题及其数学模型，线性规划问题数

4、学模型的形式(1)一般形式，第1节线性规划问题及其数学模型(2)缩写一般形式矩阵形式max z=2x 1 3 x2 2x 1 2x 212 x1 2x 28 4x 116 4x 212 x1，x20，解，第1节线性规划问题及其数学模型，4。 线性规划数学模型的标准形式(标准形式)寻求最大函数约束条件的目标函数都是等式决策变量都是非负函数约束条件都是非负的，第1节线性规划问题及其数学模型，5。如何将非标准型线性规划转化为标准型目标函数求最小值：让z-z函数约束为不等式；在函数约束的左端增加非负松弛变量；在函数约束的左端减去非负松弛变量；目标函数中松弛变量的系数均为0；让xj-xj为负；Xj0决策

5、变量不受约束：使xj xj- xj、xj0和xj0函数约束的右端项(bi)为负：函数约束的两端乘以-1。第一节线性规划问题及其数学模型要求将下列线性规划问题转化为标准形式。例4:最小z=x12x 3 x3-2x1x 2x 39-3x1x2x 34 3 x1-2x 2-3x 3=-6x 10，x20，x3值不受约束，第1节线性规划问题及其数学模型，例4:解决方法：让最大z=x1-2x 2-3x 3 x30x 40x 5 2x 1 x2 x3-x3 x4=9 3x 1 x2 2x 3-2x 3-X5=4 3x 1 2x 2 3x 3-3x 3=6x 1，x2，x3，x3，x4，x50，第1节线性规

6、划第一节线性规划问题及其数学模型，例5:解法：设max z=x1-2 x2-3 x3 3 x3 x1x 2 x3-x3 x4=7x1-x2x 3-x3-X5=2-3 x1x 2 x3-2x 3-2x 3=5x 1，x2，x3，x3，x4，x50 最小z=5x 1-2x2x 3-3 x4-x12x 2-x34x 4=-2-x13x2x 4142 x1-x23x 3-x42x 1是无约束的，x20，x3，x40 2，最小z=x12x 4 x32x 1 x2 3x 320 3 x1 2x 24x 325 x1，x20，x30，截面2解，线性规划问题数学模型的标准形式(以一般形式表示)，截面2解，1。

7、线性规划问题解的概念可行解：满足函数约束和非负约束的解，所有可行解的集合称为可行域的最优解：使目标函数最大化的可行解，相应的目标函数值称为最优值，第二节解，基：设A为约束方程的m阶系数矩阵，B为矩阵A中的m阶非奇异子矩阵，称为线性规划问题的基向量：基B中的每列向量Pj不是基向量；A中的其他列向量Pj(不在B中)基变量：与基向量Pj相对应的决策变量xj非基变量：与非基向量相对应的决策变量基解可行解：满足非负约束条件的基解可行解：与基可行解相对应的基，克莱姆法则克莱姆法则：如果线性方程a11x 1a 12x 2a 1 XM=b1a 21x 1a 22x 2 XM=b2am 1x 1 m2am XM

8、=BM的系数行列式不等于0，则该方程具有唯一的解。第2节解决方案，第2节解决方案，第2节解决方案，示例7:写出示例2的标准形式，并指出基础、基础变量、基础解决方案、基础可行解决方案和可行基础。第2部分解决方案，示例7:标准Max z=2x 1 3 x2 2x 1 2x 212 x1 2x 28 4x 116 4x 212 x1，x20，Max z=2x 1 3 x2 2x 2 x3=12x 1 2x 2 x4=8 4x 1 X5=16 4x 2 X6=12x 1-60，图形解决方案，第2部分解决方案，示例8 Max z=3x1x 23 x3x 3 x3x 2 x32x2x2x 4 x36x 1

9、，x2，x30，作业2-2，作业2-2:查找所有基本解决方案1、最大z=2x 1 3 x2 4x 3 7x 4 2x 1 3 x2-x3-4x 48-x1 2x 2-6x 3 7x 43 x1，x2，x3，x40 2、最大z=-5x 1 2x 2-3x 3 6x 4 x1 2x 2 3 x3 4x 47 2x 1 x2 x3 2x 43 x1，x2，x3，x40，第3节图形方法，1。图解法的适用条件：适用于求解只有两个决策变量的线性规划问题。(1)没有必要将线性规划问题转化为标准问题。(2)计算直观方便。第三节图解法，例9:用图解法解决下列线性规划问题。最大z=2x1 3x2 x1 2x28

10、4x116 4x212 x1，x20，第3节图解法，例9:标注约束条件，第3节图解法，例9:标注目标函数，唯一最优解，第3节图解法，第二，图解法的求解步骤建立一个二维坐标系来表示坐标系中的约束条件，通过建立可行域来绘制每个函数约束的约束边界，通过原点判断约束条件允许直线的哪一边， 并找出同时满足所有约束条件的区域，即在坐标系中按行区域画出目标函数，标出变化方向，给出目标函数的特定值k，画出目标函数的特定直线，当k变化时，目标函数的特定直线将平行移动，使目标函数最大化(最小化)。 找出目标函数的递增(递减)方向，目标函数最终离开可行域的点即为最优解，从而确定最优解。第3节，图解法，3。图解法类型

11、的唯一最优解：只有一点使目标函数值获得最大(小)值的无限(多个)最优解：直线(射线)上的任何一点使目标函数值获得相同的最大(小)值的无界解；可行域是无界的，没有可行解，目标函数值可以增加到无穷大：可行域是空集，无界解和不可行解统称为非最优解。第三节，图解法，要求：用图解法解决下列线性规划问题。例10:最大z=2x 14 x28 4x 116 4x 212 x1，x20，第3节图解法，例10:多重最优解，第3节图解法，例11:最大z=2x13x116x1，x20，无界解，第3节图解法，例12:最大z=2x1 3x2 2x1 2x212x1 2x214 x1，x20，没有可行解。第3节，图解法，第

12、四章。图形解的特征当可行域不是一个空集合时，可行域必须是一个有界或无界凸多边形。(凸集：对于集合c中的任意两点a和b，连线上的所有点也必须是集合c中的点。如果可行域是有界的，目标函数可以在可行域的顶点进行优化；如果可行域是无界的，可能没有最优解，或者可能有一个最优解，如果有，它必须在某个顶点达到。在第三节“图解法”中，线性规划问题的每个基本可行解对应于可行域的一个顶点。如果线性规划问题的最优解是在顶点达到的，那么必须有一个基本可行解，即最优解。如果有唯一的最优解，它必须在可行域的某个顶点上获得；如果两个顶点同时达到最优解，那么两个顶点之间的线上的任何一点都是最优解，并且有无穷多个最优解。如果有

13、线性规划问题的最优解，解决问题的思路是找出可行域的顶点，计算该顶点的目标函数值，并比较每个顶点的目标函数值。具有最大(较小)值的顶点是最优解的点或最优解的点之一。第3节图解法示例13下列哪些图形是凸集？a、B、C、D、凸多边形，第3节图解法，例9图解法：z，第3节图解法，例10图解法：顶点优化，第3节图解法，要求：用图解法解决下列线性规划问题。示例14:最小z=2x1-x2-2x1x22x1-2x21x1，x20，无界可行区域，第3节图形方法，示例15: 1，最大z=1x2x2-2x1x24x1-x22x1，x20，1号，最大z=50 x1 100 x2 x1 x2300 2x 1 x2400

14、 x22250 x1，x20 2，最大z=4x 1 8x 2 x1 2x 210-x1 x2 8 x1，x20，3，最大z=3x1 9x2Max z=2x1 3x2 x1 2x28 4x116 4x212 x1，x20，第4节单纯形法原理及其计算步骤，例16:解法：方法1:图解法，第4节单纯形法原理及其计算步骤，例16:解法：方法2:确定所有基本解、基本可行解和最优解都转化为标准类型max z=2x 1 3 x2 2x 2 x3=8 4x 1 x4=16 4x 2 X5=12x 1-50。第4节，单纯形法原理和计算步骤，例16:解法：方法3:确定部分基本可行解，并将最优解转化为标准类型Max Z=2x 1 3 x2 x2 x3=8 4x 1 x4=16 4x 2 X5=12x 1-50。第四节，单纯形法原理及其计算步骤。首先，单纯形法从某个基本可行解出发，将其转化为另一个相邻的基本可行解，并使相应的目标函数值具有，即从可行域沿约束边界的一个顶点到可行