卫生管理运筹学课件-线性规划

第一节 基本概念第二节 线性规划问题的图解法第三节 线性规划模型的解及性质第四节

单纯形法第五节 对偶规划第六节 运输问题及表上作业法线性规划第二节 线性规划问题的图解法—

、图解法解极大化问题二、图解法求解极小化问题三、

线性规划模型的解的各种情况四、

解法的优点及局限性—

、用图解法解极大化问题例1．MaxZ

＝

60x

＋50y2x

＋

4y

≤803x

＋

2y

≤60x,

y

≥

01．图示全部约束条件，确定可行解区域(1)以x、y作为坐标轴，建立平面直角坐标系，根据x、y非负的约束，可行解区域位于坐标图的第一象限（见图（a））（2）用等式约束代替非等式约束，画出直线

2x＋4y＝80和3x＋2y＝60（见图（b））从可行解中找出 最优解等直线法试算法（

1）等直线法：把目标函数Z＝60x＋50y

看成是随着Z的取值不同而产生的一族直线。令目标函数值分别为0、600、1200作平行线族（见图（2））.从图中可见，Z值越高，目标函数直线离原点越远。所以，寻找最优解问题可归结为：找出离原点最远的一条直线与可行解集的交点。（2）试算法：*

试算法是根据下面线性规划解的性质而得出的一种算法：线性规划的可行域是凸多边形或凸集；线性规划的最优解如果存在，必然在可行解集的某个顶点上达到。*

根据线性规划解的性质，先求出可行解集各顶点的坐标，然后试算目标函数之值，使目标函数达到极值的解，即为最优解（见下面表1－3）表1－3

例1试算结果目标函数可行解集 顶点的坐标顶点目标函数之值Ｏ0Ａ1200Ｂ1350(最优解)*1000最优解为（x，y）＝（10，15）最优值为ZMax

＝

1350返回二、图解法求解极小化问题例２MinZ

＝

50x

＋80y4x

+10y

≥4010x

＋

5y

≥

5035x

+

35y

≥

245x，

y

≥

0解：1、图示全部约束条件，确定可行解区域2．可行解中找出最优解用等直线法求最优解。本例是极小值问题，因此目标函数值应该取离原点尽可能近的等直线的值（见图（4））。通过p2点的等直线离原点最近，p2点的坐标既满足全部约束条件又能使目标函数取得最小值，故为最优解。用试算法求最优解（见表1－4）表1-4

例2试算结果目标函数顶点的坐标可行解集顶

点Ｐ1目标函数之

值500Ｐ2410(最优解)Ｐ3470800Ｐ4最优解为（x，y）＝（5，2）最优值为ZMin

＝410返回三、线性规划模型的解的各种情况例3解：在本例中，由于目标函数（Z＝2x＋4y）的等直线与约束条件（x＋2y

≤8）的直线相平行，故最优解同时在两个顶点上达到。则在此两顶点连线上的任何一点都是最优解，即有无限多个最优解。解：从图（6）可见，本例的可行域无上界，目标函数的值可趋于无穷大。在这种情况下无法确定最优解。例4解：从图（7）可以看出，本题的可行域是一个空集，因此，无可行解。这是由于本题中包括了相互矛盾的约束条件的缘故。例5线性规划问题解的几种情况有唯一的最优解。这时最优解一定在可行域的某个顶点达到；有最优解，但不唯一。这时最优解一定充满一个线段，此线段是可行域的一条边；有可行解，但没有最优解。这时可行域上的点能使目标函数趋向无穷大；没有可行解（空集）。即线性规划问题是不可行的。返回图解法的优点及局限性图解法的优点：直观、形象，它容易使人具体地认识线性规划模型的求解过程。图解法的局限性：一般仅适用于只有两个变量的。对于三维以上的模型，约束条件表现为平面，这就难用图解法去求解了。返回第三节 线性规划模型的解及有关概念一、线性规划问题的标准型二、线性规划模型的解（性质略，见P15）线性规划的标准形有如下四个特点：目标最大化、变量均非负、约束为等式、右端项非负。一、线性规划问题的标准型返回二、线性规划模型的解（1－2）（1－3）（1－4）我们把满足约束条件（1-3）、（1-4）的解称为线性规划模型的可行解。当m＜n时，约束方程组（1-3）可以有无穷多个解。全部可行解的集合，称为可行域。线性规划模型的最优解，就是指能满足（1-2），即能使目标函数达到最大值的可行解。1．线性规划的解2．线性规划标准形式的基、基本解、基本可行解我们称这个解为基本解，若这个解能同时满足线性规划模型的非负约束条件，则把这个基本解称为基本可行解。基基变量非基变量称变量

在约束方程组对应的系数列向量为线性规划模型的一个基。基对应的变量称为基变量，其它变量称为非基变量。即：任取A中的3个线性无关列向量构成矩阵B，那么B为线性规划的一个基。如果B为单位矩阵，则称B为一个单位基。线性规划的任一个基，总可以通过线性方程

组的变换化成单位基。基基变量非基变量一般形式：（1）线性规划的基、基变量对于线性规划的约束条件系数矩阵A,设B是A矩阵中的一个非奇异（可逆）的子矩阵，则称B为线性规划的一个基。任取A中的m个线性无关列向量构成矩阵B，那么B为线性规划的一个基。如果B为单位矩阵，则称B为一个单位基。称对应于基B的变量为基变量，而其它变量称为非基变量。（2）基本解、基本可行解和可行基对于线性规划问题，设矩阵B为一个基，令所有非基变量为零，可以得到m个关于基变量的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解。若得到的基变量的值均非负，则称为基本可行解，同时称这个基B为可行基。上面线性规划约束方程组（*）的一个单位基为B，对应的基变量为，非基变量为。令所有非基变量为零，解线性方程组（*）得到基变量的值我们称解为一个基本可行解，同时称基B为可行基。＃返回本次课小结第二节线性规划问题的图解法1.两个变量的线性规划问题的图解法步骤第一步建立平面直角坐标系第二步求满足约束条件的可行解区域第三步作目标函数的等值线簇，确定目标函数值增加方向（或用等值线法）。第四步从可行解区内找满足目标函数的最优解。本次课小结2.

图解法的优点及局限性图解法的优点：直观、形象，它容易使人具体地认识线性规划模型的求解过程。图解法的局限性：一般仅适用于只有两个变量的。对于三维以上的模型，约束条件表现为平面，这

就难用图解法去求解了。３．线性规划问题解的几种情况有唯一的最优解；有最优解，但不唯一；有可行解，但没有最优解；没有可行解（空集）。第三节 线性规划模型的解及有关概念一、线性规划问题的标准型（四个特点）二、线性规划模型的解及有关概念１．线性规划模型的解的概念：可行解、可行域、最优解、基本解、基本可行解。2．线性规划标准形式的基的概念：基、单位基、可行基、基变量、非基变量。本次课小结练

习思考题建立线性规划模型的三个步骤是什么?

(2)两个变量的线性规划问题的图解法的一般步骤是什么?(3)求解线性规划问题时可能出现几种结果?

(4)什么是线性规划的标准型?如何把一个非标准形式的线性规划问题转化成标准形式?(5)理解线性规划问题的可行解、基本解、基本可行解、最优解的概念。练

习判断下列说法是否正确线性规划问题的最优解一定在可行域的顶点达到。线性规划的可行解集是凸集。如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。如果一