版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、运筹学Operations Research王慧王慧东南大学经济管理学院电子商务系暨管理工程研究 wh_whq126线性规划的图解法与单纯形解法 p线性规划问题的图解法线性规划问题的图解法 p线性规划单纯形解法的原理线性规划单纯形解法的原理p线性规划单纯形解法的计算步骤线性规划单纯形解法的计算步骤 p单纯形法计算的矩阵描述单纯形法计算的矩阵描述 p线性规划单纯形求解的大线性规划单纯形求解的大M法法p线性规划单纯形求解的两阶段法线性规划单纯形求解的两阶段法p线性规划单纯形求解可能的循环现象线性规划单纯形求解可能的循环现象线性规划问题的图解法p图解法,就是用作图的方法求解
2、线性规划问题。图解法,就是用作图的方法求解线性规划问题。p简单、直观的图解法一般只适用于具有两个决策变量的线性简单、直观的图解法一般只适用于具有两个决策变量的线性规划问题。规划问题。p用图解法求解实际线性规划问题,一般按照如下基本步骤:用图解法求解实际线性规划问题,一般按照如下基本步骤:p Step1 画直坐标系;画直坐标系;p Step2 根据约束条件画出可行域;根据约束条件画出可行域;p Step3 画过坐标原点的目标函数线;画过坐标原点的目标函数线;p Step4 确定目标函数值的增大方向确定目标函数值的增大方向(目标函数线法线方目标函数线法线方向向)p Step5 目标函数线沿着增大方
3、向平行移动,与可行域目标函数线沿着增大方向平行移动,与可行域相交且有最大目标函数值的顶点,即为线性规划问题的最优相交且有最大目标函数值的顶点,即为线性规划问题的最优解。解。x1x2O1020304010203040(15,10)最优解最优解X=(15,10)最优值最优值Z=8540221xx305 . 121xx0, 0305 . 1402212121xxxxxx例例2.12143maxxxZ246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)006346321212121xxxxxxxx、min Z=x1+2x2例例2.2246x1x2246X2)()(3,1)X1)(
4、)(1,3)006346321212121xxxxxxxx、min Z=5x1+5x2例例2.3有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 01 ,)1 ()2() 1 (XXX 当=0.5时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 246x1x2246006346321212121xxxxxxxx、无界解无界解(无最优解无最优解)max Z=x1+2x2例例2.4x1x2O102030401020304050500,050305 .140221212121xxxxxxxx无可行解无可行解即无最优解即无最优解max Z=10 x1+4x2例例
5、2.5由以上例题可知,线性规划的解有由以上例题可知,线性规划的解有4种形式:种形式:1.有唯一最优解有唯一最优解(例例2.1例例2.2)2.有多重解有多重解(例例2.3)3.有无界解有无界解(例例2.4)4.无可行解无可行解(例例2.5)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解由图解法得到的启示 p线性规划问题求解的基本依据是:线性规划问题的最优线性规划问题求解的基本依据是:线性规划问题的最优解总可在可行域的顶点中寻找。寻找线性规划问题的最解总可在可行域的顶点中寻找。寻找线性规划问题的最优解只需比较有限个顶点处的目标函数值。优解只需比较有限个顶点处的目标函数值。p线
6、性规划问题求解时可能出现四种结局:唯一最优解、线性规划问题求解时可能出现四种结局:唯一最优解、无穷多个最优解、无有界解、无解或无可行解。无穷多个最优解、无有界解、无解或无可行解。p如果某一线性规划问题有最优解,我们可以按照这样的如果某一线性规划问题有最优解,我们可以按照这样的思路来求解:先找可行域中的一个顶点,计算顶点处的思路来求解:先找可行域中的一个顶点,计算顶点处的目标函数值,然后判别是否有其它顶点处的目标函数值目标函数值,然后判别是否有其它顶点处的目标函数值比这个顶点处的目标函数值更大,如有,转到新的顶点,比这个顶点处的目标函数值更大,如有,转到新的顶点,重复上述过程,直到找不到使目标函
7、数值更大的新顶点重复上述过程,直到找不到使目标函数值更大的新顶点为止。为止。1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式2.作图的关键有三点作图的关键有三点 (1)可行解区域要画正确可行解区域要画正确 (2)目标函数增加的方向不能画错目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动线性规划单纯形解法的原理 p单纯形方法的基本思想单纯形方法的基本思想p 从可行域中的一个基可行解出发,判别它是否已从可行域中的一个基可行解出发,判别它是否已经是最优解,如不是,寻找下一个基可行解,并且经是最优解,如不是,寻找下一个基可行解,并且同时
8、努力使目标函数得到改进,如此迭代下去,直同时努力使目标函数得到改进,如此迭代下去,直到找到最优解或判定问题无解为止。到找到最优解或判定问题无解为止。p单纯形算法必须解决三个方面的问题:单纯形算法必须解决三个方面的问题:p 1. 如何确定初始的基可行解?如何确定初始的基可行解?p 2. 如何进行解的最优性判别?如何进行解的最优性判别?p 3. 如何寻找改进的基可行解?如何寻找改进的基可行解?确定初始的基可行解p标准型的线性规划问题0max1XbxPCXznjjj100000100001),(21mPPP系数矩阵中存在一个单位阵 以单位阵为一初始可行基。令非基变量取值为零,便得到一基可行解。 【例
9、【例2.6】用单纯形法求下列线性规划的最优解】用单纯形法求下列线性规划的最优解 0,30340243max21212121xxxxxxxxZ【解】化为标准型,加入松驰变量【解】化为标准型,加入松驰变量x3、x4则标准型为则标准型为系数矩阵系数矩阵A及可行基及可行基B1r(B1)=2,B1是一个初始基是一个初始基,x3、x4为基变量,为基变量,x1、x2为非基变量,令为非基变量,令x1=0、x2=0由约束方程知由约束方程知x3=40、x4=30得到初始基本可行解得到初始基本可行解X(1)=(0,0,40,30)T 0,30340243max432142132121xxxxxxxxxxxxZ103
10、10112A10011B以上得到的一组基可行解是不是最优解,可以从目标函数中的以上得到的一组基可行解是不是最优解,可以从目标函数中的系数看出。目标函数系数看出。目标函数 Z=3x1+4x2中中x1的系数大于零,如果的系数大于零,如果x1为为一正数,则一正数,则Z的值就会增大,同样若的值就会增大,同样若x2不为零为一正数,也能不为零为一正数,也能使使Z的值增大;因此只要目标函数中非基变量的系数大于零,的值增大;因此只要目标函数中非基变量的系数大于零,那么目标函数就没有达到最大值,即没有找到最优解,判别线那么目标函数就没有达到最大值,即没有找到最优解,判别线性规划问题是否达到最优解的数称为检验数,
11、记作性规划问题是否达到最优解的数称为检验数,记作j , j=1,2,n。 本例中本例中 1=3, 2=4, 3=0, 4=0。最优解判断标准最优解判断标准 当所有检验数当所有检验数 j0j=1,n时,基本时,基本可行解为最优解。可行解为最优解。 当目标函数中有基变量当目标函数中有基变量xi时,利用约束条件将目标时,利用约束条件将目标函数中的函数中的xi消去即可求出检验数。消去即可求出检验数。 检验数检验数 目标函数用非基变量表达时的变量系数目标函数用非基变量表达时的变量系数进基列进基列出出基基行行b i / a i 2,ai20i表表1-4(1)XBx1x2x3x4bx3211040 x413
12、0130 j3400 (2)x3x2 j (3)x1 x2 j 基变量基变量110001/301/3105/31-1/3-1/3405/30-4/3-4/330103/5-1/5-1/51801-1/5-1/5 2/5400-1-1-1-1将将3化为化为1乘乘以以1/3后后得得到到3018最优解最优解X=(18,4,0,0)T,最优值,最优值Z=70O20301040(3,4)X(3)=(18,4)最优解最优解X=(18,4)最优值最优值Z=7040221xx305 . 121xx0,30340243max432142132121xxxxxxxxxxxxZX(1)=(0,0)2010 x2x1
13、300, 0305 . 1402212121xxxxxxX(2)=(0,10)单纯形表单纯形法全过程的计算,可以用列表的方法计算更为简洁,单纯形法全过程的计算,可以用列表的方法计算更为简洁,这种表格称为单纯形表。这种表格称为单纯形表。单纯形算法的计算步骤 将线性规划问题化成标准型。将线性规划问题化成标准型。找出或构造一个找出或构造一个m阶单位矩阵作为初始可行基,建立初始单纯形表。阶单位矩阵作为初始可行基,建立初始单纯形表。计算各非基变量计算各非基变量xj的检验数的检验数 j,若所有,若所有 j0,则问题已得到最优解,则问题已得到最优解,停止计算,否则转入下步。停止计算,否则转入下步。在大于在大
14、于0的检验数中,若某个的检验数中,若某个 k所对应的系数列向量所对应的系数列向量Pk0,则此问,则此问题是无界解,停止计算,否则转入下步。题是无界解,停止计算,否则转入下步。根据根据max j j0= k原则,确定原则,确定xk为换入变量为换入变量(进基变量进基变量),再按,再按规则计算:规则计算:=minbi/aik| aik0=bl/ aik 确定确定xl为换出变量。建为换出变量。建立新的单纯形表,此时基变量中立新的单纯形表,此时基变量中xk取代了取代了xl的位置。的位置。以以aik为主元素进行迭代,把为主元素进行迭代,把xk所对应的列向量变为单位列向量,所对应的列向量变为单位列向量,即即
15、aik变为变为1,同列中其它元素为,同列中其它元素为0,转第,转第 步。步。 【例【例2.7】利用单纯形列表算法求解例】利用单纯形列表算法求解例2.6 0,30340243max21212121xxxxxxxxZ【例【例2.8】 用单纯形法求解用单纯形法求解02053115232321321321xxxxxxxxx、3212maxxxxZ3212maxxxxZ【解】将数学模型化为标准形式:【解】将数学模型化为标准形式:5 , 2 , 1, 0205311523253214321jxxxxxxxxxj不难看出不难看出x4、x5可作为初始基变量,单纯法计算结果如可作为初始基变量,单纯法计算结果如表
16、表 1.所示所示 。 Cj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j12100 0 x42x2j 1x1 2x2 j 表表151/3150120301713751/30902M2025601017/31/31250128/91/92/335/30098/91/97/3最优解最优解X=(25,35/3,0,0,0)T,最优值,最优值Z=145/3【例【例2.9】用单纯形法求解】用单纯形法求解 42122minxxxZ5 , 1, 0212665521421321jxxxxxxxxxxj【解】【解】 这是一个极小化的线性规划问题这是一个极小化的线性规
17、划问题,可以将其化可以将其化为极大化问题求解为极大化问题求解,也可以直接求解也可以直接求解,这时判断标准是:这时判断标准是:j0(j=1,n)时得到最优解。时得到最优解。容易观察到容易观察到,系数矩阵中有一个系数矩阵中有一个3阶单位矩阵阶单位矩阵,x3、x4、x5为基变量。目标函数中含有基变量为基变量。目标函数中含有基变量x4,由第二个约束由第二个约束得到得到x4=6+x1x2,并代入目标函数消去,并代入目标函数消去x4得得12121222(6)6Zxxxxxx XBx1x2x3x4x5bx3x4x51-1611210001000156215621/2j1-1-1000 x2x4x51-241
18、001-1-20100015111 j20100 表中表中j0,j=1,2,5所以最优解为所以最优解为X=(0,5,0,1,11,)最优值最优值 Z=2x12x2x4=251=11极小值问题极小值问题,注意判断标准注意判断标准,选进基变量时选进基变量时,应选应选j0, x2进基,而进基,而a120,a220且且aiki=1,2,m则线则线性规划具有无界解性规划具有无界解单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述 单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述线性规划求解的人工变量法p人工变量法人工变量法p 引用人工变量是用单纯形
19、法求解线性规划问题时解决可引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。行解问题的常用方法。p人工变量法的基本思路是:人工变量法的基本思路是:p 若原线性规划问题的系数矩阵中没有单位向量,则在每若原线性规划问题的系数矩阵中没有单位向量,则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。个单位向量。p 由于单位阵可以作为基阵,因此,可选加入的人工变量由于单位阵可以作为基阵,因此,可选加入的人工变量为基变量。然后,再通过基变换,使得基变量中不含非零为基变量。然后,再通过基变换,使得基变量中不含非零的人工变量。
20、如果在最终单纯形表中还存在非零的人工变的人工变量。如果在最终单纯形表中还存在非零的人工变量,这表示无可行解。量,这表示无可行解。 线性规划求解的人工变量法线性规划求解的人工变量法p为了使加入人工变量后线性规划问题的最优目标函数值不受影响,我们赋予人工变量一个很大的负价值系数-M (M为任意大的正数)。p由于人工变量对目标函数有很大的负影响,单纯形法的寻优机制会自动将人工变量赶到基外,从而找到原问题的一个可行基。p这种方法我们通常称其为大M法。 线性规划求解的大M法线性规划求解的大M法【例【例2.12】用大】用大M法解法解 下列线性规划下列线性规划012210243423max321321321
21、321321xxxxxxxxxxxxxxxZ、线性规划求解的大M法举例【解】首先将数学模型化为标准形式【解】首先将数学模型化为标准形式5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj式中式中x4,x5为松弛变量,为松弛变量,x5可作可作为一个基变量,第一、三约束中为一个基变量,第一、三约束中分别加入人工变量分别加入人工变量x6、x7,目标,目标函数中加入函数中加入Mx6Mx7一项,一项,得到人工变量单纯形法数学模型得到人工变量单纯形法数学模型用前面介绍的单纯形法求用前面介绍的单纯形法求解,见下表。解,见下表。 7 , 2 ,
22、1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZjCj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6M5M0M00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/3(1初始表中的检验数有两种算法,第一种
23、算法是利用第一、初始表中的检验数有两种算法,第一种算法是利用第一、三约束将三约束将x6、x7的表达式代入目标涵数消去的表达式代入目标涵数消去x6和和x7,得到用非,得到用非基变量表达的目标函数,其系数就是检验数;第二种算法是利基变量表达的目标函数,其系数就是检验数;第二种算法是利用公式计算,如用公式计算,如(2M是一个很大的抽象的数,不需要给出具体的数值,可以是一个很大的抽象的数,不需要给出具体的数值,可以理解为它能大于给定的任何一个确定数值;理解为它能大于给定的任何一个确定数值;MMM232)(10)4()(31最优解最优解X(31/3,13,19/3,0,0)T;最优值;最优值Z152/3
24、留意:留意:【例【例2.13】求解线性规划】求解线性规划 0,426385min21212121xxxxxxxxZ【解】加入松驰变量【解】加入松驰变量x3、x4化为标准型化为标准型4 , 2 , 1, 0426385min42132121jxxxxxxxxxZj在第二个方程中加入人工变量在第二个方程中加入人工变量x5,目标函数中加上,目标函数中加上M x5一项,一项,得到得到 5 , 2 , 1, 0426385min5421321521jxxxxxxxxMxxxZj用单纯形法计算如下表所示。用单纯形法计算如下表所示。 Cj5800MbCBXBx1x2x3x4x50Mx3x5311210010
25、164j5M8+2M0M0 5Mx1x5101/37/31/31/3010122j029/3+7/3M5/3+1/3MM0 表中表中j0,j=1,2,5,从而得到最优解,从而得到最优解X=(2,0,0,0,2),), Z=10+2M。但最优解中含有人工变量。但最优解中含有人工变量x50说明这个解是说明这个解是伪最优解,是不可行的,因此原问题无可行解。伪最优解,是不可行的,因此原问题无可行解。线性规划求解的两阶段法 线性规划求解的两阶段法然后用单纯形法求解所构造的新模型,若得到然后用单纯形法求解所构造的新模型,若得到w=0,这时,若基变量中不含人工变量,则说明原问题存在这时,若基变量中不含人工变
26、量,则说明原问题存在基可行解,可进行第二步计算;基可行解,可进行第二步计算;否则,原问题无可行解,应停止计算。否则,原问题无可行解,应停止计算。第二阶段,单纯形法求解原问题第二阶段,单纯形法求解原问题第一阶段计算得到的最终单纯形表中除去人工变量,第一阶段计算得到的最终单纯形表中除去人工变量,将目标函数行的系数,换成原问题的目标函数后,作将目标函数行的系数,换成原问题的目标函数后,作为第二阶段计算的初始表,继续求解。为第二阶段计算的初始表,继续求解。 【例【例2.14】用两阶段单纯形法求解例【】用两阶段单纯形法求解例【2.12】的线性规划。】的线性规划。012210243423max321321
27、321321321xxxxxxxxxxxxxxxZ、【解】标准型为【解】标准型为5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj在第一、三约束方程中加入人工变量在第一、三约束方程中加入人工变量x6、x7后,第一阶段问题为后,第一阶段问题为7 , 2 , 1, 0122102434min732153216432176jxxxxxxxxxxxxxxxxwj用单纯形法求解,得到第一阶段问题的计算表如下:用单纯形法求解,得到第一阶段问题的计算表如下:Cj0000011 bCBXBx1x2x3x4x5x6x7101x6x5x741231
28、21211000101000014101j2121000 100 x6x5x3632532001100010100 381j650100 000 x2x5x36/53/52/51000011/53/52/5010 3/531/511/5j00000 最优解为最优解为 最优值最优值w=0。第一阶段最后一张最优表。第一阶段最后一张最优表说明找到了原问题的一组基可行解,将它作为初始基可行解,说明找到了原问题的一组基可行解,将它作为初始基可行解,求原问题的最优解,即第二阶段问题为求原问题的最优解,即第二阶段问题为)5310 ,511,53, 0(X123124145134max32613555333155522115550,1,2,5jZxxxxxxxxxxxxxjCj32100bCBXBx1x2x3x4x5201x2x5x36/53/52/51000011/53/52/50103/531/5 11/5j5 0000 231x2x1x301010000111025/32/31331/319/3j000525/3 用单纯形法计算得到下表用单纯形法计算得到下表最优解最优解X(31/3,13,19/3,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年环保法律法规解读与合规实践报告001
- 2026年制造业降本增效解决方案报告
- 2026年BIM在建筑工程设计中的应用研究报告
- 2026年互联网+政策环境分析报告:产业发展与模式创新
- 2026年白领通勤需求变化趋势报告
- 2026年汽车行业电子元件可靠性评估与维护报告
- 2026年母婴护理服务行业市场细分报告及市场风险提示
- 《明妃曲》王安石
- GBT 43366-2023宇航用半导体分立器件规范
- 高中物理力学实验现象分析解题思路能力实践测试试卷及答案
- 2026事业单位财会岗面试历年真题题库及答案
- 2026版“优 质服务基层行”能力评价标准解读
- 安全生产法律法规及标准规范辨识清单(2026年11月版)
- 露酒生产工艺方案
- 2026年中国联通宁夏回族自治区分公司人员招聘考试模拟试题及详细答案解析
- 塔吊安拆工程安全风险评估报告
- DLT5210.1-2021电力建设施工质量验收规程第1部分-土建工程
- 慢阻肺合并心衰护理查房
- 传统礼仪文化:衣冠贵整
- 机械制造装备设计期末试卷及答案
- 建筑工程《拟投入本项目的主要施工设备表及试验检测仪器设备表》
评论
0/150
提交评论