《b规划第二节 图解法及标准型的转化.ppt》由会员分享，可在线阅读，更多相关《b规划第二节 图解法及标准型的转化.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、同学们：第二章第二章线性规划线性规划第一节第一节第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题及其数学模型第二节第二节第二节第二节 线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法第三节第三节第三节第三节 单纯形法单纯形法单纯形法单纯形法第四节第四节第四节第四节 线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题第五节第五节第五节第五节 线性规划在卫生管理中的应用线性规划在卫生管理中的应用线性规划在卫生管理中的应用线性规划在卫生管理中的应用小结小结小结小结 第一节第一节第一节第一节 线性规
2、划问题及其数学模型线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题及其数学模型一、线性规划问题及其数学模型一、线性规划问题及其数学模型一、线性规划问题及其数学模型一、线性规划问题及其数学模型二、线性规划问题的共同特征二、线性规划问题的共同特征二、线性规划问题的共同特征二、线性规划问题的共同特征三、线性规划问题的标准形式三、线性规划问题的标准形式三、线性规划问题的标准形式三、线性规划问题的标准形式（第三节介绍第三节介绍第三节介绍第三节介绍）上次课内容回顾上次课内容回顾上次课内容回顾上次课内容回顾资源给定资源给定资源给定资源给定一、一、一、一、线性规划问题及其数学模型线性规划问题及其数
3、学模型线性规划问题及其数学模型线性规划问题及其数学模型线性规划线性规划线性规划线性规划研究内容研究内容研究内容研究内容最大效益最大效益最大效益最大效益合理计划合理计划合理计划合理计划统筹安排统筹安排统筹安排统筹安排最少资源最少资源最少资源最少资源合理计划合理计划合理计划合理计划统筹安排统筹安排统筹安排统筹安排任务给定任务给定任务给定任务给定表示为决策变量的线性函数表示为决策变量的线性函数表示为决策变量的线性函数表示为决策变量的线性函数目标函数目标函数目标函数目标函数用一组变量来表示用一组变量来表示用一组变量来表示用一组变量来表示（x x1 1，x x2 2,x xn n）决策变量）决策变量）决
4、策变量）决策变量用线性等式或不等式来表示用线性等式或不等式来表示用线性等式或不等式来表示用线性等式或不等式来表示约束条件方程式约束条件方程式约束条件方程式约束条件方程式二二二二 、线性规划问题的线性规划问题的线性规划问题的线性规划问题的共同特征共同特征共同特征共同特征问题的方案问题的方案问题的方案问题的方案存在限制条件存在限制条件存在限制条件存在限制条件一个目标要求一个目标要求一个目标要求一个目标要求线线线线性性性性规规规规划划划划问题问题问题问题建立模型的三个步骤建立模型的三个步骤建立模型的三个步骤建立模型的三个步骤 确定一组变量（决策变量）；确定一组变量（决策变量）；表示出一定的限制条件；
5、表示出一定的限制条件；写出目标函数。写出目标函数。Max(Min)Max(Min)Z=cZ=c11x x1 1 +c+c2 2 x x2 2 +c cn n x xn na11x1+a12 x2+a1n xn(=,)b1 1a21x1+a22x2+a2n xn(=,)b2 2 am1x1+am2 x2+amn xn(=,)bm x1，x2，xn 0 0约束条件：约束条件：约束条件：约束条件：目标函数：目标函数：目标函数：目标函数：线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式 C Cj j 称为成本或利润系数称为成本或利润系数称为成本或
6、利润系数称为成本或利润系数b bi i i i 称称称称为为为为限定系数限定系数限定系数限定系数 a a2121称称称称为约为约为约为约束条件束条件束条件束条件中未知中未知中未知中未知变变变变量的系数量的系数量的系数量的系数#第二章第二章线性规划线性规划第一节第一节第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题及其数学模型第二节第二节第二节第二节 线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法第三节第三节第三节第三节 单纯形法单纯形法单纯形法单纯形法第四节第四节第四节第四节 线性规划的对偶问题线性规划的对偶问
7、题线性规划的对偶问题线性规划的对偶问题第五节第五节第五节第五节 线性规划在卫生管理中的应用线性规划在卫生管理中的应用线性规划在卫生管理中的应用线性规划在卫生管理中的应用第二节第二节 线性规划问题的图解法线性规划问题的图解法 1 1、图解法解极大化问题图解法解极大化问题2 2、图解法求解极小化问题图解法求解极小化问题一、线性规划问题解的基本概念一、线性规划问题解的基本概念一、线性规划问题解的基本概念一、线性规划问题解的基本概念 二、两个变量的线性规划问题的图解法二、两个变量的线性规划问题的图解法二、两个变量的线性规划问题的图解法二、两个变量的线性规划问题的图解法 三、线性规划问题解的特点三、线性
8、规划问题解的特点三、线性规划问题解的特点三、线性规划问题解的特点 Max(Min)Max(Min)Z=cZ=c11x x1 1 +c+c2 2 x x2 2 +c cn n x xn na11x1+a12 x2+a1n xn(=,)b1 1a21x1+a22x2+a2n xn(=,)b2 2 am1x1+am2 x2+amn xn(=,)bm x1，x2，xn 0 0约束条件：约束条件：约束条件：约束条件：目标函数：目标函数：目标函数：目标函数：满足约束条件的解，满足约束条件的解，满足约束条件的解，满足约束条件的解，称为线性规划问题的称为线性规划问题的称为线性规划问题的称为线性规划问题的可行解
9、可行解可行解可行解所有可行解所有可行解所有可行解所有可行解的集合称为的集合称为的集合称为的集合称为可行域可行域可行域可行域.线性规划问题的线性规划问题的线性规划问题的线性规划问题的最优解和最优值最优解和最优值最优解和最优值最优解和最优值 一、线性规划问题解的基本概念一、线性规划问题解的基本概念一、线性规划问题解的基本概念一、线性规划问题解的基本概念（一）用（一）用（一）用（一）用图图图图解法解极大化解法解极大化解法解极大化解法解极大化问题问题问题问题 例例1 1MaxZ 6060 x 5050y 2 2x 4 4y 80 80 3 3x 2 2y 60 60 x,y 0 0(1)以以 x、y
10、作为坐标轴，建立平面作为坐标轴，建立平面 直角坐标系直角坐标系 根据根据 x、y 非负的约束，可行解区非负的约束，可行解区 域位于第一象限（见图（域位于第一象限（见图（a）x xy yo o图图图图(a a)1.1.图示全部约束条件，确定可图示全部约束条件，确定可图示全部约束条件，确定可图示全部约束条件，确定可 行解区域行解区域行解区域行解区域 解：解：解：解：（2 2）用等式约束代替非等用等式约束代替非等 式约束，画出直线式约束，画出直线 2x4y80 3x2y60 （见见图（图（b）（3）根据不等式约束）根据不等式约束,确定可行确定可行 解区域解区域 2x4y 80 3x2y 60 （见图
11、（见图（c）0 0 x xy y图图图图(b b)2x4y803x2y600 0 x xy y图图图图(c)(c)2 2x 4 4y 80 803 3x 2 2y 60 60（1 1）等直线法：等直线法：等直线法：等直线法：把目标函数把目标函数 Z60 x50y 看成是随着看成是随着Z的取的取值不同而产生的一族直线。令目值不同而产生的一族直线。令目标函数值分别为标函数值分别为0、600、1200作平行线族（图（作平行线族（图（2）从图中可见，从图中可见，Z值越高，目标值越高，目标函数直线离原点越远。所以，函数直线离原点越远。所以，寻找最优解问题可归结为：寻找最优解问题可归结为：找找找找出离原点
12、最远的一条直线与可出离原点最远的一条直线与可出离原点最远的一条直线与可出离原点最远的一条直线与可行解集的交点。行解集的交点。行解集的交点。行解集的交点。2 2从可行解中找出最优解从可行解中找出最优解从可行解中找出最优解从可行解中找出最优解（1）等直线法）等直线法（2）试算法）试算法0 0 x xy y(c)(c)MaxZ60 x50y表表表表1 1 1 13 3 3 3 例例例例1 1 1 1试算结果试算结果试算结果试算结果目标函数目标函数可行解集可行解集顶点顶点顶点的坐标顶点的坐标目标函数目标函数之值之值0 0120012001350(1350(1350(1350(最优最优最优最优解解)10
13、001000最优解为（最优解为（最优解为（最优解为（x x，y y）（）（）（）（1010，1515）最优值为最优值为最优值为最优值为 Z ZMaxMax 13501350（2 2 2 2）试算法：试算法：试算法：试算法：第二章第二章线性规划线性规划第一节第一节第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题及其数学模型第二节第二节第二节第二节 线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法第三节第三节第三节第三节 单纯形法单纯形法单纯形法单纯形法第四节第四节第四节第四节 线性规划的对偶问题线性规划的对偶问题线
14、性规划的对偶问题线性规划的对偶问题第五节第五节第五节第五节 线性规划在卫生管理中的应用线性规划在卫生管理中的应用线性规划在卫生管理中的应用线性规划在卫生管理中的应用第三节第三节单纯形法单纯形法一、一、一、一、单纯形法的基本原理单纯形法的基本原理 三、三、三、三、大大M法法二、二、二、二、单纯形解法单纯形解法一、单纯形法的基本原理一、单纯形法的基本原理（一）线性规划问题的（一）线性规划问题的（一）线性规划问题的（一）线性规划问题的标准标准标准标准规规规规范型范型范型范型（二）基本变量（二）基本变量（二）基本变量（二）基本变量（三）基本解（三）基本解（三）基本解（三）基本解（四）基本可行解（四）基
15、本可行解（四）基本可行解（四）基本可行解（五）单纯形法的原理（五）单纯形法的原理（五）单纯形法的原理（五）单纯形法的原理 1.1.标准标准标准标准型（型（型（型（P P11 11 三三三三）2.2.规规规规范型（范型（范型（范型（典型方程式典型方程式典型方程式典型方程式）小结小结小结小结1.1.1.1.线性规划的标准型线性规划的标准型线性规划的标准型线性规划的标准型 （一）（一）线性规划问题的标准型和规范型线性规划问题的标准型和规范型线性规划问题的标准型和规范型线性规划问题的标准型和规范型 四个特点：四个特点：四个特点：四个特点：目标最大化目标最大化目标最大化目标最大化约束为等式约束为等式约束
16、为等式约束为等式变量均非负变量均非负变量均非负变量均非负右端项非负右端项非负右端项非负右端项非负 书写形式书写形式书写形式书写形式（1 1）简缩形式）简缩形式 （2 2）矩阵形式）矩阵形式 见教材见教材 P12P12 （1 1 1 1）极小化目标函数的问题极小化目标函数的问题极小化目标函数的问题极小化目标函数的问题设目标函数为设目标函数为令令 Zf 则可转化为标准形则可转化为标准形标准形式的转化标准形式的转化（2 2 2 2）约束条件不是等式的问题）约束条件不是等式的问题）约束条件不是等式的问题）约束条件不是等式的问题显然，显然，S也具有非负约束，即也具有非负约束，即S0可以引进一个新的变量可
17、以引进一个新的变量S，使得：使得：设约束条件为：设约束条件为：类似地引进一个新变量类似地引进一个新变量S S，使得：使得：为为了使了使约约束由不等式成束由不等式成为为等式而引等式而引进进的的变变量量S S，称称为为“松弛松弛变变量量”。如果原问题中有若干个非等式约束，必须对各个约束如果原问题中有若干个非等式约束，必须对各个约束引进不同的松弛变量。引进不同的松弛变量。(S0)当约束条件为当约束条件为（2 2 2 2）约束条件不是等式的问题）约束条件不是等式的问题）约束条件不是等式的问题）约束条件不是等式的问题在标准形式中，必须每一个变量有非负约束，在标准形式中，必须每一个变量有非负约束，当某一个
18、变量当某一个变量xj 没有非负约束时，令没有非负约束时，令（3 3 3 3）变量无符号限制的问题）变量无符号限制的问题）变量无符号限制的问题）变量无符号限制的问题（4 4 4 4）右端项有负值的问题）右端项有负值的问题）右端项有负值的问题）右端项有负值的问题在在标标准形式中，要求右端准形式中，要求右端项项必必须须每一个分量非每一个分量非负负，当某一个右端当某一个右端项项系数系数为负时为负时，则则把把该该等式等式约约束两端同束两端同时时乘以乘以1 1，得到：，得到：例例例例1 1 1 1 将以下线性规划问题转化为标准形式：将以下线性规划问题转化为标准形式：将以下线性规划问题转化为标准形式：将以下
19、线性规划问题转化为标准形式：例例例例2 2 2 2 将线性规划问题将线性规划问题将线性规划问题将线性规划问题 转化为标准形式转化为标准形式转化为标准形式转化为标准形式 解：解：解：解：标准形式为标准形式为标准形式为标准形式为2.2.规范型（典型方程式）规范型（典型方程式）规范型（典型方程式）规范型（典型方程式）例例例例:解下列线性方程组解下列线性方程组解下列线性方程组解下列线性方程组一般情况一般情况一般情况一般情况典型方程式典型方程式典型方程式典型方程式每个约束方程中要有一个每个约束方程中要有一个每个约束方程中要有一个每个约束方程中要有一个变量的系数，而这个变变量的系数，而这个变变量的系数，而
20、这个变变量的系数，而这个变量在其余方程中不出现。量在其余方程中不出现。量在其余方程中不出现。量在其余方程中不出现。系数矩阵中包含系数矩阵中包含系数矩阵中包含系数矩阵中包含一个单位子矩阵一个单位子矩阵一个单位子矩阵一个单位子矩阵规规规规范范范范化化化化典型方程典型方程典型方程典型方程组组组组2.2.规范型（典型方程式）规范型（典型方程式）规范型（典型方程式）规范型（典型方程式）规范型规范型规范型规范型方程组方程组方程组方程组（二）基本变量（二）基本变量（二）基本变量（二）基本变量如果如果变变量量xj在某一方程中系数为在某一方程中系数为1，而在其它一切方程，而在其它一切方程中的系数为零，则称中的系
21、数为零，则称xj为该方程中的为该方程中的基本变量基本变量基本变量基本变量否则否则为为非基本变量非基本变量非基本变量非基本变量.基本变量基本变量基本变量基本变量为线性无关的方程的个数为线性无关的方程的个数为线性无关的方程的个数为线性无关的方程的个数基本变量的组基本变量的组基本变量的组基本变量的组数为数为数为数为（三）基本解（三）基本解（三）基本解（三）基本解在典型方程中，设在典型方程中，设非基本变量为零非基本变量为零非基本变量为零非基本变量为零，求解基本变量得，求解基本变量得到的解，称为到的解，称为基本解基本解基本解基本解基本解的个数为基本解的个数为个个。（四）基本可行解（四）基本可行解（四）基
22、本可行解（四）基本可行解基本变量为基本变量为非负非负非负非负的一组基本解称为的一组基本解称为基本可行解基本可行解基本可行解基本可行解，基本，基本可行解的个数最多不超过可行解的个数最多不超过个个。不是基本可行不是基本可行不是基本可行不是基本可行解解解解得到最优解或得到最优解或得到最优解或得到最优解或证明最优解不存在证明最优解不存在证明最优解不存在证明最优解不存在标准型标准型标准型标准型从可行域某个顶点开始从可行域某个顶点开始从可行域某个顶点开始从可行域某个顶点开始检查该点检查该点检查该点检查该点是否最优解是否最优解是否最优解是否最优解不是不是不是不是取一个取一个取一个取一个“相邻相邻相邻相邻”、
23、“更好更好更好更好”的顶点的顶点的顶点的顶点(五五)单纯形法的基本原理单纯形法的基本原理规范型规范型规范型规范型初始初始初始初始基本基本基本基本可行解可行解可行解可行解第一步第一步 建立平面直角坐标系建立平面直角坐标系第二步第二步 求满足约束条件的可行解域求满足约束条件的可行解域 （或判断可行解域不存在）（或判断可行解域不存在）第三步第三步 用等值线法或试算法，确定最优解用等值线法或试算法，确定最优解 （或判断最优解不存在）。（或判断最优解不存在）。第四步第四步 写出最优解并确定最优值。写出最优解并确定最优值。2.2.2.2.两个变量的线性规划问题的图解法步骤两个变量的线性规划问题的图解法步骤
24、两个变量的线性规划问题的图解法步骤两个变量的线性规划问题的图解法步骤第二节第二节第二节第二节 线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法线性规划问题解的几种情况线性规划问题解的几种情况线性规划问题解的几种情况线性规划问题解的几种情况1 1.线性规划问题解的基本概念线性规划问题解的基本概念线性规划问题解的基本概念线性规划问题解的基本概念 目标求极大值目标求极大值目标求极大值目标求极大值变量非负变量非负变量非负变量非负右端项非负右端项非负右端项非负右端项非负全部等式约束全部等式约束全部等式约束全部等式约束标标标标准准准准型型型型规规规规范范范范型型型型系数矩阵
25、中包含系数矩阵中包含系数矩阵中包含系数矩阵中包含一个单位子矩阵一个单位子矩阵一个单位子矩阵一个单位子矩阵每个约束方程中要有一每个约束方程中要有一每个约束方程中要有一每个约束方程中要有一个变量的系数为，而个变量的系数为，而个变量的系数为，而个变量的系数为，而这个变量在其余方程中这个变量在其余方程中这个变量在其余方程中这个变量在其余方程中不出现。不出现。不出现。不出现。第三节第三节单纯形法单纯形法一、单纯形法一、单纯形法一、单纯形法一、单纯形法的基本原理的基本原理的基本原理的基本原理（一）（一）（一）（一）线性规划线性规划线性规划线性规划问题的标准型和问题的标准型和问题的标准型和问题的标准型和规范
26、型规范型规范型规范型 得到最优解或得到最优解或得到最优解或得到最优解或证明最优解不存在证明最优解不存在证明最优解不存在证明最优解不存在标准型标准型标准型标准型从可行域某个顶点开始从可行域某个顶点开始从可行域某个顶点开始从可行域某个顶点开始检查该点检查该点检查该点检查该点是否最优解是否最优解是否最优解是否最优解不是不是不是不是取一个取一个取一个取一个“相邻相邻相邻相邻”、“更好更好更好更好”的顶点的顶点的顶点的顶点(五五)单纯形法的基本原理单纯形法的基本原理规范型规范型规范型规范型初始初始初始初始基本基本基本基本可行解可行解可行解可行解#作作作作 业业业业 1 1 1 1判断下列说法是否正确判断
27、下列说法是否正确判断下列说法是否正确判断下列说法是否正确 （1 1）线性规划最优解一定在可行域的顶点达到。）线性规划最优解一定在可行域的顶点达到。（2 2）线性规划的可行解集是凸集。）线性规划的可行解集是凸集。（3 3）若一个线性规划有两个不同的最优解，则它有无穷多）若一个线性规划有两个不同的最优解，则它有无穷多 个最优解。个最优解。（4 4）如果一个线性规划问题有可行解，那么它必有最优解。）如果一个线性规划问题有可行解，那么它必有最优解。（5）线性规划的最优值至多有一个；）线性规划的最优值至多有一个；（6）线性规划的标准型右端项非零；）线性规划的标准型右端项非零；（7）线性规划一定有不等式约束；）线性规划一定有不等式约束；（8）线性规划标准型变量无非负限制。）线性规划标准型变量无非负限制。2.2.规划规划规划规划教材教材P49习题二习题二3(2)(3)(4)3.3.预习预习预习预习P1925二、单纯形解法二、单纯形解法