《线性规划问题的数学模型讲稿.ppt》由会员分享，可在线阅读，更多相关《线性规划问题的数学模型讲稿.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于线性规划问题的数学模型第一页，讲稿共五十三页哦线性规划问题第一节第一节第一节第一节 线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型（一）引言（一）引言 线性规划是运筹学的重要分支之一，也是研究较早、发展较快、应用较广而且比较成熟的一个分支。自1947年线性规划被成功的运用于工业、交通、农业和军事等各个领域后，现在它已成为管理科学的重要基础和手段之一。随着计算机的普及，它的适应领域越来越广泛。线性规划研究的问题主要有两类：一是一项任务确定后，如何统筹安排，尽量作到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源，如何安排使用他们，使
2、得完成任务最多。其实这两类问题是一个问题的两个方面，就是所谓寻求整个问题的某个整体指标最优的问题。1.1.运输问题运输问题 2.2.生产的组织与计划问题生产的组织与计划问题 3.3.合理下料问题合理下料问题 4.4.配料问题配料问题 5.5.布局问题布局问题 6.6.分配问题分配问题第二页，讲稿共五十三页哦（二）线性规划问题的数学模型（二）线性规划问题的数学模型1.运输问题运输问题设有两个砖厂设有两个砖厂A A1 1、A A2 2。其产量分别为。其产量分别为2323万块与万块与2727万块。它们生产的供万块。它们生产的供应应B B1 1、B B2 2、B B 3 3三个工地。其需要量分别为三个
3、工地。其需要量分别为1717万块、万块、1818万块和万块和1515万块。万块。自各产地到各工地的运价格如下表：问应如何调运，才使总运费自各产地到各工地的运价格如下表：问应如何调运，才使总运费最省。最省。运价 工地 砖厂B1B2B3A1506070A260110160第三页，讲稿共五十三页哦解：设解：设解：设解：设 x xi ji j表示由砖厂表示由砖厂表示由砖厂表示由砖厂A Ai i 运往工地运往工地运往工地运往工地 B Bj j 砖的数量（砖的数量（砖的数量（砖的数量（i=1,2i=1,2；j=1,2,3)j=1,2,3)运量 工地砖厂B1B2B3发量A1x11x12x1323A2x21x
4、22x2327收量17181550第四页，讲稿共五十三页哦目标函数目标函数目标函数目标函数 约束条件约束条件约束条件约束条件第五页，讲稿共五十三页哦2.2.生产的组织与计划问题生产的组织与计划问题生产的组织与计划问题生产的组织与计划问题 某工厂生产某工厂生产某工厂生产某工厂生产A A、B B两种产品，现有资源数、生产每单位产品所需原材料数两种产品，现有资源数、生产每单位产品所需原材料数两种产品，现有资源数、生产每单位产品所需原材料数两种产品，现有资源数、生产每单位产品所需原材料数以及每单位产品可得利润如下表所示。问如何制定生产计划使两种产品总利润以及每单位产品可得利润如下表所示。问如何制定生产
5、计划使两种产品总利润以及每单位产品可得利润如下表所示。问如何制定生产计划使两种产品总利润以及每单位产品可得利润如下表所示。问如何制定生产计划使两种产品总利润最大？最大？最大？最大？单位产品单位产品 产品产品耗用资源耗用资源资源资源A（公斤）（公斤）B（公斤）（公斤）现有资源现有资源铜（吨）铜（吨）94360电力（千瓦）电力（千瓦）45200劳动日（个）劳动日（个）310300单位利润单位利润（万元（万元/公斤）公斤）712第六页，讲稿共五十三页哦解解解解：假设生产假设生产假设生产假设生产A A产品产品产品产品x x1 1公斤，公斤，公斤，公斤，B B产品产品产品产品x x2 2公斤，公斤，公斤
6、，公斤，x x1 1 ，x x2 2称为决称为决称为决称为决 策变量，简称变量。得到利润策变量，简称变量。得到利润策变量，简称变量。得到利润策变量，简称变量。得到利润7 7 x x1 1+12+12 x x2 2万元，万元，万元，万元，这一问这一问这一问这一问 题的数学模型为：题的数学模型为：题的数学模型为：题的数学模型为：约束条件约束条件 目标函数目标函数第七页，讲稿共五十三页哦上述例子虽然有不同的实际内容，但是都可归结为一类上述例子虽然有不同的实际内容，但是都可归结为一类优化问题。从数学上说它们具有以下优化问题。从数学上说它们具有以下共同特征共同特征：每一个问题都是求一组变量（称为决策变量
7、）的值。这组变量的一组定值就代表一个具体方案。通常要求这组变量的取值是非负的。存在一定的限制条件，称为约束条件。这些约束条件都可以用一组线性等式或不等式来表示。都有一个期望达到的目标，并且这个目标可以表示为决策变量的线性函数（称为目标函数）。按所研究问题的不同，要求目标函数值最大化或最小化。我们将具有上述三个特点的我们将具有上述三个特点的最优化问题最优化问题归结为线性规划问题，其数归结为线性规划问题，其数学模型称为线性规划问题的数学模型，简称学模型称为线性规划问题的数学模型，简称线性规划数学模型。线性规划数学模型。第八页，讲稿共五十三页哦线性规划问题的数学模型的线性规划问题的数学模型的线性规划
8、问题的数学模型的线性规划问题的数学模型的一般形式一般形式一般形式一般形式（1）式称为目标函数目标函数（2）式中等式或不等式称为约束条件约束条件（3）式是非负约束条件非负约束条件x1,x2,xn称为决策变量决策变量，简称变量变量。第九页，讲稿共五十三页哦满足约束条件的一组变量的值称为线性规划问题的一个可行解可行解，使目标函数取得最大（或最小）的可行解称为最优解最优解。此时，目标函数的值称为最优值最优值。建立线性规划数学模型的步骤建立线性规划数学模型的步骤首首先先，确定决策变量。线性规划的数学模型建得是否容易，求解是否方便，取决于决策变量的选取是否得当。其其次次，确定约束条件，并根据实际问题添加非
9、负条件。明确问题中所有的限制条件，并用决策变量的线性等式或不等式表示。一般可用表格形式列出所有的限制数据，然后根据所列出的数据写出相应的约束条件，以避免遗漏或重复所规定的限制要求。最最后后，确定目标函数，并确定是求极大还是求极小。用决策变量的线性函数来表示实际问题所要达到的目标，得到目标函数。第十页，讲稿共五十三页哦第二节第二节 两个变量的线性规划问题的图解法两个变量的线性规划问题的图解法例例例例1 1求x1、x2的值，使它们满足并且使目标函数f=2x1+5x2的值最大。图解法是利用直观的几何图形求解线性规划的一种几何解法第十一页，讲稿共五十三页哦x12x1+5x2=192x1+5x2=152
10、x1+5x2=82x1+5x2=4x2=3x1=4x1+2x2=80 x2最优解为 x1=2，x2=3相应的目标函数的最大值为S=2*2+5*3=19第十二页，讲稿共五十三页哦x1x1+2x2=8x1+2x2=6x1+2x2=2x1+2x2=0 x2=3x1=4x1+2x2=80 x2例例例例2 2若把例1的目标函数改为改为 s=xs=x1 1+2x+2x2 2，最优解有 无穷多个无穷多个无穷多个无穷多个，它们对应的目标函数值都是8 8。（见下图）第十三页，讲稿共五十三页哦例例3求x1、x2的值，使它们满足并且使目标函数s=2x1+2x2的值最小。第十四页，讲稿共五十三页哦x1x20X X1
11、1-x-x2 2=1 1X X1 1+2x+2x2 2=0=02X1+2x2=22X1+2x2=62X1+2x2=102X1+2x2=16最优解最优解最优解最优解 X X X X1 1 1 1=1=1=1=1，x x x x2 2 2 2=0,=0,=0,=0,目标函数最小值目标函数最小值目标函数最小值目标函数最小值 s=2s=2s=2s=2解解解解：例例例例4 4若把例3改为改为使的目标函数的值最大，从图可看出目标函数无上界，因此无最优解第十五页，讲稿共五十三页哦例例例例5 5求x1、x2的值，使它们满足并且使目标函数s=2 x1+2x2的值最小。第十六页，讲稿共五十三页哦x1x2-x1+x
12、2=1x1+x2=-2没有可行解，当然没有最没有可行解，当然没有最优优解。解。解：解：解：解：第十七页，讲稿共五十三页哦（一）线性规划问题的标准形式（一）线性规划问题的标准形式 线性规划问题的数学模型有各种不同的形式。为了便于讨论，需要将线性规划数学模型写成统一格式。线性规划问题的标准型标准型标准型标准型是：第三节第三节 单纯形法单纯形法约束条件（2）式又称等式约束等式约束（3）式称非负约束非负约束。标准型的特点为标准型的特点为（1 1）目标函数为最大值形式（）目标函数为最大值形式（）目标函数为最大值形式（）目标函数为最大值形式（2 2）约束条件用等式表示且等）约束条件用等式表示且等）约束条件
13、用等式表示且等）约束条件用等式表示且等 式右端的常数式右端的常数式右端的常数式右端的常数 为非负值（为非负值（为非负值（为非负值（3 3）决策变量非负。）决策变量非负。）决策变量非负。）决策变量非负。第十八页，讲稿共五十三页哦 把一般的线性规划问题化成标准型的过程称为线性规划问题的标准化。线性规划问题的标准化的方法如下：1.1.求目标函数的最小值求目标函数的最小值求目标函数的最小值求目标函数的最小值 令令F=-fF=-f，则可将求，则可将求f f的最小值问题转化成求的最小值问题转化成求F F的最大值问题，即的最大值问题，即2.2.约束条件为不等式约束条件为不等式约束条件为不等式约束条件为不等式
14、 引入一个非负变量引入一个非负变量 xn+in+i，转化为线性等式，称，转化为线性等式，称 xn+i n+i 为为松弛变量松弛变量。3.3.若有若有若有若有b bi i0 0 可在该约束条件两边同乘可在该约束条件两边同乘 -1-1，化为，化为 4.4.如果有某个变量如果有某个变量如果有某个变量如果有某个变量x xj j 无非负约束无非负约束无非负约束无非负约束 可引进非负变量可引进非负变量xj j/,xj j/，令，令xj j=xj j/-xj/代入约束条件和目标函数中。代入约束条件和目标函数中。第十九页，讲稿共五十三页哦例例例例1 1 将下面的线性规划问题化成标准型。将下面的线性规划问题化成
15、标准型。解解解解引进松弛变量 x40,x5 0，将式中不等式约束条件变换成等式约束条件：将3x1-x2-2x3=-5两边同乘-1，变为-3x1+x2+2x3=5变量x3无非负约束，引进非负变量x6,x7，令x3=x7-x6，代入约束条件和目标函数。得最后，令F=-f，则可将求f的最小值问题转化成求F的最大值问题。标准型为：第二十页，讲稿共五十三页哦（二）、基本概念（二）、基本概念 定义定义定义定义在线性规划的标准型中，如果有变量只在某一个约束方程中系数为1，在其余约束方程中系数全为0，则称为该约束的一个基变量基变量基变量基变量；如果每个等式约束都有一个基变量，则称等式约束条件是这些基变量的典型
16、方程组典型方程组典型方程组典型方程组。如果线性规划的约束条件是典型方程组，不失一般性，设n个变量的线性规划问题的典型方程组为：第二十一页，讲稿共五十三页哦其中基变量为其中基变量为x x1 1,x x2 2,x xm m，从而，从而x xm+1 m+1,x xm+2 m+2,x xn n称为非基变量。称为非基变量。令非基变量令非基变量x xm+1 m+1=0=0,x xm+2 m+2=0=0,x xn n=0=0，则可求得约束方程的一个解：，则可求得约束方程的一个解：x x1 1=b b1 1,x x2 2=b b2 2,x xm m=b bm m,x xm+1 m+1=0=0 ,x xm+2
17、m+2=0=0,x xn n=0 =0 称为称为基本解基本解基本解基本解。如。如果果b bi i0(i=1,2,m)0(i=1,2,m)则称此基本解为则称此基本解为基本可行解基本可行解基本可行解基本可行解。(三三)、单纯形法、单纯形法1 1单纯形法的基本思想单纯形法的基本思想单纯形法的基本思路是：根据标准型，从可行域的一个基本可行解开始，转移到另一个基本可行解，并且使目标函数值逐步变优，当目标函数值达到最大值时，就得到问题的最优解。第二十二页，讲稿共五十三页哦下面举例说明单纯形法的基本思想下面举例说明单纯形法的基本思想下面举例说明单纯形法的基本思想下面举例说明单纯形法的基本思想例例例例2 2
18、求解线性规划问题求解线性规划问题解解解解先将问题化成标准型第二十三页，讲稿共五十三页哦显然x4,x5为基变量，x1,x2,x3为非基变量，约束条件是典型方程组。由（1）可得：将（2）代入目标函数可得f=2x1+3 x2+x3+0,令非基变量x1=x2=x3=0则有f=f=2 2x x1 1+3 3 x x2 2+1 1x x3 3+0=0+0=0,同时得到一个基本可行解基本可行解基本可行解基本可行解 x x1 1=x x2 2=x x3 3 =0,=0,x x4 4=1,=1,x x5 5=3=3由f=2x1+3 x2+x3+0可知，非基变量的系数都是正数，若将其中任意一个非基变量变成基变量（
19、取值从0变成正数）,都可以使目标函数值增加,所以只要在目标函数的表达式中还存在有正系数的非基变量，就表示目标函数值还有增加的可能，从而不是最优解，就需要将非基变量与基变量进行对换。我们把非基变量转换为基变量称为进基进基进基进基。一般选择正系数最大的那个非基变量（本例为x2）为进基变量，以求得目标函数值较快的增加。将x2换入到基变量中。同时，还要确定基变量中有一个要换出来成为非基变量。变量由基变量转化成非基变量称为出基出基出基出基。第二十四页，讲稿共五十三页哦怎样确定出基变量，由（怎样确定出基变量，由（2 2）式，）式，x x2 2 为进基变量，为进基变量，x x1 1,x x3 3仍为非基仍为
20、非基变量，故变量，故x x1 1,x x3 3的值为零。代入（的值为零。代入（2 2）式可得）式可得随着x2的值增加，x4,x5的值会逐渐变小，由于才能保证x40,x50（即解的可行性）。当x2=9/4时，x5=0。即用 x2替换x5（x5出基），于是得到新的基变量基变量基变量基变量x x4 4,x x2 2,非基变量非基变量非基变量非基变量x x1 1,x x3 3,x x5 5。这种确定出基变量的方法称为最小比值原则最小比值原则最小比值原则最小比值原则。第二十五页，讲稿共五十三页哦由（由（2 2）式写出用非基变量表示基变量的表达式：）式写出用非基变量表示基变量的表达式：整理得代入目标函数得
21、f=27/4+f=27/4+5/45/4 x x1 1-17/4-17/4 x x3 3 9/4 9/4 x x5 5令非基变量x1=x3=x5=0得一新的基本可行解基本可行解基本可行解基本可行解 x x1 1=0,0,x x2 2=9/4=9/4,x x3 3=0,0,x x4 4=1/4=1/4,x x5 5 =0=0代入代入目标函数得相应的目标函数值f=27/4 f=27/4 非基变量x1的系数是正数，说明目标函数值还可能增加，于是再用上述方法，确定进基、出基变量，又得到另一个基本可行解另一个基本可行解另一个基本可行解另一个基本可行解 x x1 1=1,1,x x2 2=2=2,x x3
22、 3=x x4 4=x x5 5 =0 =0 f=21+32=8f=21+32=8用非基变量表示目标函数f=8-f=8-3 3x x3 3 5 5x x4 4-1 1x x5 5第二十六页，讲稿共五十三页哦式中所有非基变量的系数均是负数，意味着目标函数值不可能再式中所有非基变量的系数均是负数，意味着目标函数值不可能再增加，故此时的增加，故此时的基本可行解基本可行解就是就是最优解最优解最优解最优解，最优值最优值最优值最优值为为8 8 2 2最优性检验最优性检验最优性检验最优性检验由标准形等式约束条件得代入目标函数进行简单的运算后，用非基变量表示目标函数为称为非基变量的检验数检验数检验数检验数。将
23、用检验数来判定线性规划问题是否有最优解，有最优解定理。第二十七页，讲稿共五十三页哦定理定理定理定理 (1)1)如果关于非基变量的所有检验数如果关于非基变量的所有检验数如果关于非基变量的所有检验数如果关于非基变量的所有检验数 则则基本可行解基本可行解就是就是最优解最优解最优解最优解(2)如果关于非基变量的所有检验数如果关于非基变量的所有检验数且其中有一个非基变量且其中有一个非基变量xm+k的的检验数为零检验数为零 则该线性规划问题有则该线性规划问题有无穷多个最优解无穷多个最优解无穷多个最优解无穷多个最优解(3)如果存在非基变量如果存在非基变量xm+k 的的检验数检验数0 且且xm+k对应的对应的
24、系数列系数列系数列系数列均均小于等于零小于等于零 则该线性规划问题则该线性规划问题无最优解无最优解无最优解无最优解 第二十八页，讲稿共五十三页哦3.3.单纯形表单纯形表单纯形表单纯形表用表格的形式来表示上面求解线性规划问题的单纯形法的计算过程可以用表格的形式来表示上面求解线性规划问题的单纯形法的计算过程可以 使计算和检验更加简便。具体方法如下：使计算和检验更加简便。具体方法如下：将目标函数式改写为将目标函数式改写为-f+c1 x1+c2 x2 +cnxn=0 且作为等式约束方程且作为等式约束方程组的第组的第m+1个方程，得个方程，得对方程组对方程组(3-1)的增广矩阵施行初等行变换，化为如下的
25、阶梯形矩阵的增广矩阵施行初等行变换，化为如下的阶梯形矩阵第二十九页，讲稿共五十三页哦将矩阵表示成将矩阵表示成将矩阵表示成将矩阵表示成单纯形表单纯形表单纯形表单纯形表xBb100010001-f000-f0 x1x2xmxm+1xnx1x2xmb1b2bma1m+1a2m+1amm+1a1na2namn下面通过具体的例子说明用单纯形法求解线性规划问题。下面通过具体的例子说明用单纯形法求解线性规划问题。第三十页，讲稿共五十三页哦例例例例1 1 用单纯形法解线性规划问题用单纯形法解线性规划问题用单纯形法解线性规划问题用单纯形法解线性规划问题解解解解 将该线性规划问题化为标准型将该线性规划问题化为标准
26、型第三十一页，讲稿共五十三页哦显然显然x x3 3,x x4 4,x x5 5为基变量，为基变量，x x1 1,x x2 2为非基变量。可得单纯形表为非基变量。可得单纯形表(下表所示）。这种直接下表所示）。这种直接从线性规划问题得到的单纯形表称为从线性规划问题得到的单纯形表称为初始单纯形表初始单纯形表初始单纯形表初始单纯形表xBb2210012120108400016-f2300001x3x x4 4x5x1x x2 2x3x4x5初始基本可行解为x1=x2=0,x3=12,x4=8,x5=16。由于检验系数有正数，所以这个基本可行解不是最优解。从x1，x2中选一个检验数最大的变量变量变量变量
27、x x2 2进基进基进基进基。根据最小比值原则(mim12/2,8/2=4)确定,x x4 4出基出基出基出基。进基变量x2所在列与出基变量x4所在行的交叉处元素称为主元主元主元主元，加上方括号，再施行行初等变换，将主元所在列的主元化为1 1 1 1，其余元素化为0 0 0 0，得下表 注注注注用最小比值原则确定出基变量的一般方法是：在单纯形表中，用最小比值原则确定出基变量的一般方法是：在单纯形表中，用最小比值原则确定出基变量的一般方法是：在单纯形表中，用最小比值原则确定出基变量的一般方法是：在单纯形表中，b b b b列元素与进基变量列元素与进基变量列元素与进基变量列元素与进基变量 列对应的
28、正元素之比，取其比值最小的所对应的基变量出基。列对应的正元素之比，取其比值最小的所对应的基变量出基。列对应的正元素之比，取其比值最小的所对应的基变量出基。列对应的正元素之比，取其比值最小的所对应的基变量出基。第三十二页，讲稿共五十三页哦xBb101-1041/2101/204400016-f1/200-3/20-12x3x2x x5 5x2x3x5x4x x1 11xBb001-1-1/400101/2-1/8210004-f000-3/2-1/8-14x1x2x3x4x5x3注：比值相等时可任选其一 x2x11/4最优解为最优解为x x1 1=4=4=4=4 x x2 2=2=2=2=2 x
29、 x3 3=x x4 4=x x5 5=0=0=0=0目标函数值为目标函数值为f=14f=14f=14f=14 非非基基变变量量的的检检验验数数小小于于0第三十三页，讲稿共五十三页哦例例例例2 2 用单纯形法求解线性规划问题用单纯形法求解线性规划问题用单纯形法求解线性规划问题用单纯形法求解线性规划问题解解解解 x3 ,x4为基变量，为基变量，x1 ,x2为非基变量。可得初始单纯形表为非基变量。可得初始单纯形表 XBb1-1102-31014-f32000X X1 1X3X4X2X X3 3X4第三十四页，讲稿共五十三页哦XBb1-11020-23110-f05-30-6X1X2X3X4X1X4
30、有检验数有检验数0系系系系数列数列数列数列均均0 无无无无最优解最优解最优解最优解例例例例3 3 用单纯形法求解线性规划问题用单纯形法求解线性规划问题第三十五页，讲稿共五十三页哦解解解解 将该线性规划问题化为标准型：将该线性规划问题化为标准型：将该线性规划问题化为标准型：将该线性规划问题化为标准型：F=-f进行换基迭代，计算过程如表第三十六页，讲稿共五十三页哦XBb111006120108010013-F33000011100601-1102010013-F00-300-18XBb111006120108010013-F33000011100601-1102010013-F00-300-18X
31、Bb111006120108010013-F33000011100601-1102010013-F00-300-18xBb111100612010801003-F33000011100601-110201003-F00-300-18x x1 1x4x x3 3x5x2x3x4x5x1x4x511非基变量有非基变量有检验数检验数0，有有检验数检验数=0 无穷多个最优解无穷多个最优解无穷多个最优解无穷多个最优解其中一个最优解是其中一个最优解是 x1=6,x2=0 最优值为最优值为 f=-F=-18 第三十七页，讲稿共五十三页哦第四节第四节 两阶段法两阶段法 求解线性规划问题的单纯形法必须满足每个等
32、式约束都有一个基变量即线性规划的约束条件是典型方程组，但经常出现的情况是线性规划的标准型的约束条件不是典型方程组，从而不具有初始单纯形表，这时，需要在线性规划问题中加入人工变量，把问题变为约束条件是典型方程组的情形，再按上述方法换基迭代求出最优解。人工变量是后加入原约束方程组中的虚拟变量，我们必须把它们从基变量中逐渐替换掉。若经过基的变换，基变量中不再含有人工变量，这表示原问题有解；若经过基的变换，最后在基中还有一个或几个人工变量，这意味着原问题无可行解。两阶段法是处理人工变量的方法之一，它是将加入人工变量后的线性规划问题分成两阶段求解。第三十八页，讲稿共五十三页哦第一阶段第一阶段第一阶段第一
33、阶段：判断原线性规划问题是否有基本可行解。其方法是：对于线：判断原线性规划问题是否有基本可行解。其方法是：对于线性规划问题标准型的目标函数、等式约束、非负约束引入人工变量性规划问题标准型的目标函数、等式约束、非负约束引入人工变量y y11,y y22,y,ymm，构造一个辅助线性规划问题。，构造一个辅助线性规划问题。对辅助线性规划问题应用单纯形法，求出辅助问题的最优解。若最优值Z=0，说明所有人工变量都变换为非基变量，表明原问题已得到一个基本可行解，则进入第二阶段；否则原问题无可行解，计算结束。第三十九页，讲稿共五十三页哦第二阶段第二阶段第二阶段第二阶段：在第一阶段所得的初始单纯形表基础上，进
34、行换基迭代。在第一阶段所得的初始单纯形表基础上，进行换基迭代。将第一阶段最终计算表中的目标函数的系数换成原问题目标函数的系将第一阶段最终计算表中的目标函数的系数换成原问题目标函数的系数，划去人工变量所在的列，完成单纯形表，就得到求解原问题的初数，划去人工变量所在的列，完成单纯形表，就得到求解原问题的初始单纯形表。然后用单纯形法进行计算求出最优解。始单纯形表。然后用单纯形法进行计算求出最优解。例例例例1 1用两阶段法求解下面的线性规划问题用两阶段法求解下面的线性规划问题解解解解 第一阶段第一阶段：第一、第二约束中暂缺基变量，分别引入人工变量y1、y2,引入辅助线性规划问题第四十页，讲稿共五十三页
35、哦Z用非基变量表示：用单纯形表进行换基迭代如下XBb5118101024320110-Z7541000201001-Z00011102-Z0000-1-10XBx1x2x3x4y1y2by151181010y224320110-Z754100020第四十一页，讲稿共五十三页哦XBx1x2x3x4y1y2bx45/81/81/811/805/4y23/415/411/40-1/4115/2-Z3/415/411/40-5/4015/2x43/501/3012/15-1/301x21/5111/150-1/154/152-Z0000-1-10由于得到辅助问题的最优值由于得到辅助问题的最优值Z=0，
36、且人工变量均已出基，于是进入第二阶段。，且人工变量均已出基，于是进入第二阶段。第四十二页，讲稿共五十三页哦第二阶段第二阶段第二阶段第二阶段 在第一阶段的最终表中划去人工变量所在的列，并将在第一阶段的最终表中划去人工变量所在的列，并将-Z-Z行换成行换成-f-f 行即得原问题的初始单纯形表。这里需注意的是，填行即得原问题的初始单纯形表。这里需注意的是，填 f f 行前，需将行前，需将 f f 用非基变量表示，由上表最后一次换基用非基变量表示，由上表最后一次换基迭代知：迭代知：用单纯形法进行计算，如下表所示第四十三页，讲稿共五十三页哦XBx1x2x3x4bx43/501/3011x21/5111/
37、1502-f20-1/30-10 x1101/185/35/3x20113/18-1/35/3-f00-4/9-10/3-40/3原线性规划问题原线性规划问题最优解最优解最优解最优解为为 x1 1=5/3,=5/3,x x2 2=5/3,=5/3,x3=x4 4=0=0 最优值最优值最优值最优值为为 f=40/3f=40/3 第四十四页，讲稿共五十三页哦例例例例2 2 用两阶段法求解下面的线性规划问题用两阶段法求解下面的线性规划问题解解解解化成标准型第四十五页，讲稿共五十三页哦解解解解 第一阶段第一阶段第一阶段第一阶段：引入人工变量引入人工变量 y y11、y y22、y y3 3,引入辅助线
38、性规划问题引入辅助线性规划问题Z用非基变量表示：用单纯形表进行换基迭代如下：第四十六页，讲稿共五十三页哦xBx x1 1x2x3y1y2y3by195010014y213-20102y y3 33-230014-Z136100020y y1 1011-910-32y2011/3-301-1/32/3x11-2/31001/34/3-Z044/3-1200-13/38/3x201-9/111/110-3/112/11y2000-1/312/30 x1105/112/3305/3316/11-Z000-4/30-1/30第四十七页，讲稿共五十三页哦于是得辅助问题的最优值于是得辅助问题的最优值于是得
39、辅助问题的最优值于是得辅助问题的最优值Z=0Z=0。人工变量。人工变量。人工变量。人工变量y y y y2 2 2 2尚未出基，且尚未出基，且尚未出基，且尚未出基，且y y y y2 2 2 2所在行的非人工人工变量列元所在行的非人工人工变量列元所在行的非人工人工变量列元所在行的非人工人工变量列元素均素均素均素均为零，无法让为零，无法让为零，无法让为零，无法让y y y y2 2 2 2出基。但是由最后一个单纯形表中出基。但是由最后一个单纯形表中出基。但是由最后一个单纯形表中出基。但是由最后一个单纯形表中y y y y2 2 2 2所在行，得所在行，得所在行，得所在行，得这表明原问题的约束方程
40、组中的第二个方程可由第一个方程减去二倍的第三个方程这表明原问题的约束方程组中的第二个方程可由第一个方程减去二倍的第三个方程得出。因此，第二个方程是多余的，故最后一个迭代的基变量得出。因此，第二个方程是多余的，故最后一个迭代的基变量y y2 2所在的第二行可以划所在的第二行可以划去，再划去人工变量列，且将去，再划去人工变量列，且将-Z行换成行换成-F行，先将行，先将F用非基变量表示，由上表最后一次换基用非基变量表示，由上表最后一次换基迭代知迭代知 得原问题的初始单纯形表得原问题的初始单纯形表第四十八页，讲稿共五十三页哦XBx1x2x3bx201-9/112/11x1105/1116/11-F00
41、-5/1118/11于是得原问题于是得原问题最优解最优解最优解最优解:x x x x1 1 1 1 =16/11 x=16/11 x=16/11 x=16/11 x2 2 2 2 =2/11 x=2/11 x=2/11 x=2/11 x3 3 3 3 =0=0=0=0最优值最优值最优值最优值 f=18/11f=18/11f=18/11f=18/11第四十九页，讲稿共五十三页哦例例例例3 3 用两阶段法求解下面的线性规划问题用两阶段法求解下面的线性规划问题用两阶段法求解下面的线性规划问题用两阶段法求解下面的线性规划问题 解解解解引进辅助线性规划问题引进辅助线性规划问题 用非基变量表示用非基变量表
42、示Z：Z=5xZ=5xZ=5xZ=5x1 1 1 1-5x-5x-5x-5x2 2 2 2+10/3x+10/3x+10/3x+10/3x4 4 4 4-5-5-5-5 用单纯形表进行换基迭代如表用单纯形表进行换基迭代如表 第五十页，讲稿共五十三页哦XBx1x2x3x4y1y2y3by11/211/2-2/31002y23/20-1/200103y33-6040010-Z5-5010/30005y1021/2-4/310-1/62y203-1/2-201-1/23x11-204/3001/30-Z050-10/300-5/35x2011/4-2/31/20-1/121y200-5/40-3/2
43、1-1/40 x1101/20101/62-Z00-5/40-5/20-5/40第五十一页，讲稿共五十三页哦最后最后-Z-Z行检验数均非正，得到辅助问题的最优值行检验数均非正，得到辅助问题的最优值Z=0Z=0，但此时人工变量，但此时人工变量y y2 2尚未出基，可采用下述尚未出基，可采用下述方法让人工变量方法让人工变量y y2 2出基：在未出基的那个人工变量所在行的非人工变量列中任选一个非零元素为主元，出基：在未出基的那个人工变量所在行的非人工变量列中任选一个非零元素为主元，进行迭代。此处让进行迭代。此处让y y2 2出基，出基，x x3 3进基，得单纯形表如表进基，得单纯形表如表XBx1x2x3x4y1y2y3bx2010-2/31/5-/5-1/151x300106/5-4/5-/50 x110002/52/5-/152-Z0000-1-1-10在表中划去人工变量列，并将-Z行换成-f行(见后），得原问题的初始单纯形表XBx1x2x3x4bx2010-2/31x300100 x110002-f00008第五十二页，讲稿共五十三页哦感感谢谢大大家家观观看看第五十三页，讲稿共五十三页哦