《第02章线性规划及其对偶问题PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第02章线性规划及其对偶问题PPT讲稿.ppt（138页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第02章线性规划及其对偶问题第1页，共138页，编辑于2022年，星期一2.1线线性性规规划划(LinearProgramming)2.1.1线性规划问题的数学模型线性规划问题的数学模型2.1.2线性规划问题解的概念线性规划问题解的概念2.1.3求解线性规划问题的图解法求解线性规划问题的图解法2.1.4求解线性规划问题的单纯形法求解线性规划问题的单纯形法2.1.5单纯形法的进一步讨论单纯形法的进一步讨论2.1.6线性规划模型的应用线性规划模型的应用第2页，共138页，编辑于2022年，星期一为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完为了完成一项任务或达到
2、一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。成较多的任务或达到一定的目的，这个过程就是规划。例、有一正方形铁皮，如何截取例、有一正方形铁皮，如何截取x 使容积为最大？使容积为最大？xa此为无约束极值问题此为无约束极值问题2.1.1线性规划问题的数学模型线性规划问题的数学模型（一）、问题的提出（一）、问题的提出第3页，共138页，编辑于2022年，星期一设 备产 品ABCD利润（元）2140222043有 效 台 时1281612例、已知资料如下表例、已知资料如下表所示，问如何安排生所示，问如何安排生产才能使利润最大？产才能使利润最
3、大？或如何考虑利润大，或如何考虑利润大，产品好销。产品好销。模模型型max Z=2x1+3x2 x1 0,x2 0s.t.2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12此为带约束的极值问题此为带约束的极值问题第4页，共138页，编辑于2022年，星期一问题中总有未知的变量，需要我们去解决问题中总有未知的变量，需要我们去解决要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。如果在规划问题的数学模型中，变量是连续的（数值取实数）其目标函数是如果在规划问题的数学模型中，变量是连续的（数值取实
4、数）其目标函数是有关线性函数（一次方），约束条件是有关变量的线性等式或不等式，这样，有关线性函数（一次方），约束条件是有关变量的线性等式或不等式，这样，规划问题的数学模型是线性的。反之，就是非线性的规划问题（其中一个条规划问题的数学模型是线性的。反之，就是非线性的规划问题（其中一个条件符合即可）。件符合即可）。（二）、数学模型（二）、数学模型1、第5页，共138页，编辑于2022年，星期一目标函数：目标函数：约束条件：约束条件：2、线性规划数学模型的一般形式、线性规划数学模型的一般形式第6页，共138页，编辑于2022年，星期一也可以记为如下形式也可以记为如下形式：目标函数：目标函数：约束条件
5、：约束条件：第7页，共138页，编辑于2022年，星期一如将上例用表格表示如下：如将上例用表格表示如下：设变量设变量产 品 j设 备 i有效台时利润 第8页，共138页，编辑于2022年，星期一向向 量量 形形 式：式：第9页，共138页，编辑于2022年，星期一矩阵形式：矩阵形式：第10页，共138页，编辑于2022年，星期一规规划划确定型确定型随机型随机型静态规划静态规划动态规划动态规划线性规划线性规划非线性规划非线性规划整数规划整数规划非整数规划非整数规划整数规划整数规划非整数规划非整数规划3、规划类型、规划类型第11页，共138页，编辑于2022年，星期一一一般般有有两种方法两种方法图
6、图解解法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但需将适用于任意变量、但需将一般形式变成标准形式一般形式变成标准形式2.1.2线性规划问题解的概念线性规划问题解的概念（一）、求解方法（一）、求解方法第12页，共138页，编辑于2022年，星期一1、解的概念、解的概念可行解：满足约束条件可行解：满足约束条件、的解为可行解。所有解的集合的解为可行解。所有解的集合为可行解的集或可行域。为可行解的集或可行域。最优解：使目标函数达到最大值的可行解。最优解：使目标函数达到最大值的可行解。基：基：B是矩阵是矩阵A中中mm阶非奇异子矩阵（阶非奇
7、异子矩阵（B 0），则），则B是一个是一个基。基。则称则称Pj(j=1,2,m)为基向量。为基向量。Xj 为基变量，否则为非基变量。为基变量，否则为非基变量。（二）、线性规划问题的解（二）、线性规划问题的解第13页，共138页，编辑于2022年，星期一基本解基本解(基解基解)：令所有非基变量的值全为：令所有非基变量的值全为0，求得的基变量解与这些，求得的基变量解与这些0非基变量所组成的解非基变量所组成的解X=(x1,x2,xm,0,0)T称为称为LP的基本解，最多为的基本解，最多为个。个。基本可行解：满足非负约束条件的基本解，简称基可行解基本可行解：满足非负约束条件的基本解，简称基可行解可行基
8、：对应于基可行解的基称为可行基。可行基：对应于基可行解的基称为可行基。非可行解非可行解可可行行解解基解基解基可行解基可行解第14页，共138页，编辑于2022年，星期一2、解的基本定理、解的基本定理若线性规划问题存在可行解，则问题的可行域是凸集（凸多若线性规划问题存在可行解，则问题的可行域是凸集（凸多边形）边形）凸集凸集凸集凸集不是凸集不是凸集顶顶点点最优解一定是在凸集的某一顶点实现（顶点数目不超过最优解一定是在凸集的某一顶点实现（顶点数目不超过个）个）第15页，共138页，编辑于2022年，星期一先找一个基本可行解，与周围顶点比较，如不是最大，继续比先找一个基本可行解，与周围顶点比较，如不是
9、最大，继续比较，直到找出最大为止。较，直到找出最大为止。3、解的情况、解的情况唯唯一一解解无无穷穷解解无无界界解解无可行解无可行解有最优解有最优解无最优解无最优解第16页，共138页，编辑于2022年，星期一建立直角坐标建立直角坐标，图中阴影部分及边界上的点均为其，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。解，是由约束条件来反映的。例例2.32.1.3求解线性规划问题的图解法求解线性规划问题的图解法第17页，共138页，编辑于2022年，星期一01 2 3 4 5 6 7 8 1 2 3 4 5 6 作作图图有唯一最有唯一最优优解：解：x1=4,x2=2最优目标函数值最优目标函数
10、值Z*=14x2 x1(4 2)第18页，共138页，编辑于2022年，星期一例、例、例、例、无穷多最优解无穷多最优解无界解无界解x1x1x2 x2 第19页，共138页，编辑于2022年，星期一x1x2 无可行解无可行解例、例、第20页，共138页，编辑于2022年，星期一（一）基本思想（一）基本思想将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时
11、，得到最优解。到另一个基本可行解，当目标函数达到最大时，得到最优解。（二）线性规划模型的标准形式（二）线性规划模型的标准形式1、标准形式、标准形式2.1.4求解线性规划问题的单纯形法求解线性规划问题的单纯形法第21页，共138页，编辑于2022年，星期一2、特征：、特征：.目标函数为求极大值，也可以用求极小值；目标函数为求极大值，也可以用求极小值；.所有约束条件（非负条件除外）都是等式，右端常数项为非所有约束条件（非负条件除外）都是等式，右端常数项为非负；负；.变量为非负。变量为非负。3、转换方式：、转换方式：.目标函数的转换目标函数的转换如果是求极小值即如果是求极小值即，则可将目标函数乘以（
12、，则可将目标函数乘以（1），可化为求极大值问题。），可化为求极大值问题。也就是：令也就是：令，可得到上式。，可得到上式。即即第22页，共138页，编辑于2022年，星期一.约束方程的转换：由不等式转换为等式约束方程的转换：由不等式转换为等式称为松弛变量称为松弛变量称为剩余变量称为剩余变量第23页，共138页，编辑于2022年，星期一.变量的变换变量的变换若存在取值无约束的变量若存在取值无约束的变量，可令，可令其中：其中：例例2.2将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式为无约束（无非负限制）为无约束（无非负限制）第24页，共138页，编辑于2022年，星期一 解解:用用替换
13、替换，且，且，将第将第3个约束方程两边乘以个约束方程两边乘以（1）将极小值问题反号，变为求极大值将极小值问题反号，变为求极大值标准形式如下：标准形式如下：引入变量引入变量第25页，共138页，编辑于2022年，星期一例、将下列线性规划问题化为标准型例、将下列线性规划问题化为标准型为无约束为无约束解：解：第26页，共138页，编辑于2022年，星期一（三）、单纯形法（三）、单纯形法例例2.3变成标准型变成标准型第27页，共138页，编辑于2022年，星期一约束方程的系数矩阵约束方程的系数矩阵可作为为基变量可作为为基变量为非基变量为非基变量I 为单位矩阵且线性独立为单位矩阵且线性独立第28页，共1
14、38页，编辑于2022年，星期一令：令：则：则：基本可行解为基本可行解为（0,0,12,8,16,12）此时，此时，Z=0然后，找另一个基本可行解。即将非基变量换入基变量中，但然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。保证其余的非负。如此循环下去，直到找到最优解为止。注意：为尽快找到最优解，在换入变量时有一定的要求。如注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。将目标系数大的先换入等。第29页，共138页，编辑于2022年，星期一找出一个初始可行解找出一个初始可行解是否最优是否最优转移到另一个目标函数
15、转移到另一个目标函数（找更大的基本可行解）（找更大的基本可行解）最优解最优解是是否否循循环环直到找出为止，核心是：变量迭代直到找出为止，核心是：变量迭代结束结束其步骤总结如下：其步骤总结如下：第30页，共138页，编辑于2022年，星期一j（四）、单纯形表（四）、单纯形表第31页，共138页，编辑于2022年，星期一判定标准：判定标准：若求若求或或例例 题：题：第32页，共138页，编辑于2022年，星期一cj230000cBxBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612221000120100400010040001j2 3 0 0 0 012/28/21
16、2/4cj230000cBxBb x1 x2 x3 x4 x5 x6000 x3x4x516400010j3x23010001/42620100-1/210010 0-1/2第33页，共138页，编辑于2022年，星期一cj230000cBxBb x1 x2 x3 x4 x5 x60003x3x4x5x26216320100-1/210010-1/2400010010001/4j20000-3/46/2216/4cj230000cBxBb x1 x2 x3 x4 x5 x60203x3 x1x5x22283001-201/210010-1/2000-412010001/44412j000-20
17、1/4第34页，共138页，编辑于2022年，星期一cj230000cBxBb x1 x2 x3 x4 x5 x60203x6 x1x5x2 4402002-401101-10000-441001-1/2100j00-1/2-100000-201/44412001-201/210010-1/2000-412010001/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB230000cjj第35页，共138页，编辑于2022年，星期一cj230000cBxBb x1 x2 x3 x4 x5 x60203x3 x1x6 x2 0442001-1-1/4010001/
18、40000-21/210101/2-1/80j000-3/2-1/80000-201/44412001-201/210010-1/2000-412010001/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB230000cjj第36页，共138页，编辑于2022年，星期一练习练习00-1/12-7/24x2x112 x1 x2 x3 x4bxBcB2100cj15/43/4011/4-1/810-1/125/24j第37页，共138页，编辑于2022年，星期一（一）、模型情况（一）、模型情况变变量：量：xj0 xj0 xj无约束无约束结结1、组成、组成约束条件
19、：约束条件：=b目标函数：目标函数：maxmin果果2、变量、变量xj0令令xj=-xj，xj0 xj0不处理不处理xj 无约束无约束令令xj=xjxj,xj0,xj0唯一最优唯一最优无穷最优无穷最优无界解无界解无可行解无可行解2.1.5单纯形法的进一步讨论单纯形法的进一步讨论第38页，共138页，编辑于2022年，星期一3 3、约束、约束 条件：条件：加入松弛变量加入松弛变量加入人工变量加入人工变量先减去先减去 再加上再加上例例2.5第39页，共138页，编辑于2022年，星期一4 4、目标函数：、目标函数：max,min 设规划模型约束条件为设规划模型约束条件为 ，需加入人工变量，需加入人
20、工变量而得到一个而得到一个mm的单位矩阵，即基变量组合。因人工变量为虚拟变的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的人工变量，表示原问题有解。若当若基变量中不含有非零的人工变量，表示原问题有解。若当 ，而还有人工变量（非零）时，则表示原问题无可行解。，而还有人工变量（非零）时，则表示原问题无可行解。第40页，共138页，编辑于2022年，星期一加入人工变量后，目的是找到一个单位向量，叫人工基。其目标加入人工变量后，目的是找到一个单位向量，叫人工基。其目
21、标价值系数要确定，但不能影响目标函数的取值。一般可采用两种价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大方法处理：大M法和两阶段法。法和两阶段法。.大大M法：法：即假定人工变量在目标函数中的系数为即假定人工变量在目标函数中的系数为M（任意大正数）（任意大正数），如果是求极大值，需加，如果是求极大值，需加-M；如果是求极小值，需加；如果是求极小值，需加M。如基变量中。如基变量中还存在还存在M，就不能实现极值。，就不能实现极值。第41页，共138页，编辑于2022年，星期一cj-31100MMcBxBbx1x2x3x4x5x6x70 x4111-21100011Mx63-41
22、20-1103/2Mx71-20100011j-3+6M1-M1-3M0M00cBxBbx1x2x3x4x5x6x70 x4103-20100-1Mx610100-11-211x31-2010001j-11-M00M03M-1第42页，共138页，编辑于2022年，星期一cj-31100MMcBxBbx1x2x3x4x5x6x70 x4123001-22-541x210100-11-21x31-2010001j-10001M-1M+1cBxBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3j0001/
23、31/3M-1/3M-2/3最优解为最优解为 x*=(4,1,9,0,0,0,0)T，Z*=2第43页，共138页，编辑于2022年，星期一 用计算机处理数据时，只能用很大的数代替用计算机处理数据时，只能用很大的数代替M,可能可能造成计算机上的错误，故多采用两阶段法。造成计算机上的错误，故多采用两阶段法。第一阶段：第一阶段：在原线性规划问题中加入人工变量，构造如下模型：在原线性规划问题中加入人工变量，构造如下模型：.两阶段法：两阶段法：第44页，共138页，编辑于2022年，星期一对上述模型求解（单纯形法），若对上述模型求解（单纯形法），若W=0,W=0,说明问题存在基本可行说明问题存在基本可
24、行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。解，可以进行第二个阶段；否则，原问题无可行解，停止运算。第二阶段：在第一阶段的最终表中，去掉人工变量，将目标第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。的初始表（用单纯形法计算）。例例2.6第一阶段第一阶段第45页，共138页，编辑于2022年，星期一cj0000011cBxBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-20100011j6
25、-1-301000 x4103-20100-11x610100-11-210 x31-2010001j0-1001030 x4123001-22-50 x210100-11-20 x31-2010000j0000011第46页，共138页，编辑于2022年，星期一cj-31100cBxBbx1x2x3x4x50 x4123001-241x210100-11x31-20100j-10001-3x141001/3-2/31x210100-11x390012/3-4/3j0001/31/3第二阶段第二阶段最优解为最优解为 x*=(4,1,9,0,0,0,0)T，Z*=2第47页，共138页，编辑于2
26、022年，星期一6 6、无、无可行解的判断：运算到检验数全负为止，可行解的判断：运算到检验数全负为止，仍含有人工变量，无可行解。仍含有人工变量，无可行解。第48页，共138页，编辑于2022年，星期一 8 8、退化：、退化：即计算出的即计算出的（用于确定换出变量）存在有两个以上（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。这就是退化（会产生退化解）。虽任意换出变量，目标函数值不变，但此时不同的基却表虽任意换出变量，目标函数值不变，但此时不同的基却表示为同一顶点
27、，其特例是永远达不到最优解。需作如下处理：示为同一顶点，其特例是永远达不到最优解。需作如下处理：.当当 中出现两个以上最大值时，选下标最小中出现两个以上最大值时，选下标最小的非基变量为换入变量；的非基变量为换入变量；.当当中出现两个以上最小值时，选下标最小的基变量为中出现两个以上最小值时，选下标最小的基变量为换出变量。换出变量。第49页，共138页，编辑于2022年，星期一建立模型个 数取 值右 端 项等式或不等式极大或极小新加变量系数两个三个以上xj0 xj无约束xj 0bi 0bi 0=maxZminZxs xa求解图解法、单纯形法单纯形法不处理令xj=xj-xj xj 0 xj 0令 x
28、j=-xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z=-ZminZ=maxz0-M根据上表列出初始单纯形表根据上表列出初始单纯形表A（二）、线性规划小结（二）、线性规划小结A第50页，共138页，编辑于2022年，星期一j初始单纯形表初始单纯形表(max型型)第51页，共138页，编辑于2022年，星期一A第52页，共138页，编辑于2022年，星期一课堂练习课堂练习第53页，共138页，编辑于2022年，星期一-M+1/7-1/7-M-16/7-50/7001/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5
29、x4x3x2x1bxBcB-M0-M-532cj0-M0-5+2M3-4M2+3M51-101-5210 x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cjjj第54页，共138页，编辑于2022年，星期一一般而言，一个经济、管理问题凡是满足以下条件时，一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。才能建立线性规划模型。.要求解问题的目标函数能用数值指标来反映，且为线性函要求解问题的目标函数能用数值指标来反映，且为线性函数；数；.存在着多种方案；存在着多种方案；.要求达到的目标是在一定条件下实现的，这些约束可用线要求达到的目标是在一
30、定条件下实现的，这些约束可用线性等式或不等式描述。性等式或不等式描述。2.1.6线性规划模型的应用线性规划模型的应用第55页，共138页，编辑于2022年，星期一（一）、资源的合理利用（一）、资源的合理利用一般提法：一般提法：某厂计划在下一生产周期内生产某厂计划在下一生产周期内生产B1,B2,Bn种产品，要消耗种产品，要消耗A1,A2,Am种资源，已种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如表所示，问如何安排生产计划，才能充分利用现有的资源，使获得的总利润如表所示，问如何安排生产计划，才能
31、充分利用现有的资源，使获得的总利润最大？最大？单件 产 消耗 品资源资源限制单件利润第56页，共138页，编辑于2022年，星期一（二）、生产组织与计划问题（二）、生产组织与计划问题一般提法：某工厂用机床一般提法：某工厂用机床A A1 1,A,A2 2,A Am m 加工加工B B1 1,B,B2 2,B Bn n 种零件。在一个周期种零件。在一个周期内，各机床可能工作的机时（台时），工厂必须完成各种零件的数量、各机床加工内，各机床可能工作的机时（台时），工厂必须完成各种零件的数量、各机床加工每个零件的时间（机时每个零件的时间（机时/个）和加工每个零件的成本（元个）和加工每个零件的成本（元/个
32、）如表所示，问如何个）如表所示，问如何安排各机床的生产任务，才能完成加工任务，又使总成本最低？安排各机床的生产任务，才能完成加工任务，又使总成本最低？加工 零 时间 件机床机时限制必须零件数加工 零 成本 件机床第57页，共138页，编辑于2022年，星期一 =0s.t.min(11ijjijiijijminjijijijjiijxbxaxaxcZxBAx一组变量）。模型：一组变量）。模型：的数量，求的数量，求在一生产周期加工零件在一生产周期加工零件为机床为机床设设第58页，共138页，编辑于2022年，星期一（三）、合理下料问题（三）、合理下料问题一般提法一般提法设用某种原材料截取零件设用某
33、种原材料截取零件A1,A2,Am的毛坯。根据以往的经验，在一种原材的毛坯。根据以往的经验，在一种原材料上可以有料上可以有B1,B2,Bn种不同的下料方式，每种下料方式可截得的各种毛种不同的下料方式，每种下料方式可截得的各种毛坯个数以及每种零件的需要量如表所示，问应如下料才能既满足需要又坯个数以及每种零件的需要量如表所示，问应如下料才能既满足需要又使原材料消耗最少？使原材料消耗最少？下料 下料毛 件数 方式坯型号需 要毛坯数第59页，共138页，编辑于2022年，星期一第60页，共138页，编辑于2022年，星期一 现有一批某种型号的圆钢长现有一批某种型号的圆钢长8 8米，需要截取米，需要截取2
34、.52.5米长的毛米长的毛坯坯100100根，长根，长1.31.3米的毛坯米的毛坯200200根。问如何才能既满足需要，又能使总的根。问如何才能既满足需要，又能使总的用料最少？用料最少？1002002.5米米1.3米米需要需要根数根数下料下料下料下料毛毛件数件数方式方式坯型号坯型号设变量为设变量为 第第 j 种方法的所有种方法的所有原料件数原料件数例题例题1 1：一一30二二22三三14四四06第61页，共138页，编辑于2022年，星期一（四）、合理配料问题（四）、合理配料问题一般提法一般提法某饲养场用某饲养场用n种饲料种饲料B1,B2,Bn配置成含有配置成含有m种营养成分种营养成分A1,A
35、2,Am的混合饲料，其余资料如表所示。问应如何配料，才能既满足的混合饲料，其余资料如表所示。问应如何配料，才能既满足需要，又使混合饲料的总成本最低？需要，又使混合饲料的总成本最低？含 饲 量 料成分最 低需要量原料单价第62页，共138页，编辑于2022年，星期一第63页，共138页，编辑于2022年，星期一例题例题2 2：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省？问两种食物各食用多少，才能既满足需要、又使总费用最省？设：设：xj 表示表示Bj 种食物用量。种食物用量。2
36、1.5原料单价原料单价1.007.5010.000.10.151.70.751.101.30A1A2A3最最低低需要量需要量甲甲乙乙含含食食量量物物成分成分第64页，共138页，编辑于2022年，星期一（五）、运（五）、运输输问问题题已知资料如表所示：已知资料如表所示：单位 销 运价 地产地产量销 量模型如下：模型如下：第65页，共138页，编辑于2022年，星期一第66页，共138页，编辑于2022年，星期一某运输问题的资料如下：某运输问题的资料如下：6483销量7524852431921092产量单位 销地 运价产地例题例题3：第67页，共138页，编辑于2022年，星期一第68页，共13
37、8页，编辑于2022年，星期一（六）、作物布局问题（六）、作物布局问题单 土 产 地作物播种面积土地面积此外，还有连续投资、投入产出等模型问题。此外，还有连续投资、投入产出等模型问题。第69页，共138页，编辑于2022年，星期一2.2对偶理论对偶理论(DualityTheory)2.2.1对偶问题的提出对偶问题的提出2.2.2线性规划问题解的概念线性规划问题解的概念2.2.3线性规划的对偶理论线性规划的对偶理论2.2.4对偶问题的经济解释对偶问题的经济解释影子价格影子价格2.2.5对偶单纯形法对偶单纯形法第70页，共138页，编辑于2022年，星期一2.2.1对偶问题的提出对偶问题的提出例例
38、2.7某某工工厂厂拥拥有有A、B、C三三种种类类型型的的设设备备，生生产产甲甲、乙乙两两种种产产品品。每每件件产产品品在在生生产产中中需需要要占占用用的的设设备备机机时时数数，每每件件产产品品可可以以获获得得的的利利润润以以及及三三种种设设备备可可利利用的时数如下表所示。求获最大利润的方案。用的时数如下表所示。求获最大利润的方案。产品甲产品甲产品乙产品乙设备能力设备能力（h）设备设备A3265设备设备B2140设备设备C0375利润（元利润（元/件）件）15002500第71页，共138页，编辑于2022年，星期一解：解：设设x1，x2分别为甲乙两种产品的生产量，则有分别为甲乙两种产品的生产量
39、，则有第72页，共138页，编辑于2022年，星期一若例若例2.7问题的设备都用于外协加工，工厂收取加工费。试问：设备问题的设备都用于外协加工，工厂收取加工费。试问：设备A、B、C每工时各如何收费才最有竞争力？每工时各如何收费才最有竞争力？minminf f=65=65y y1 1+40+40y y2 2+75+75y y3 3s.t.3s.t.3y y1 1+2+2y y2 215001500（不少于甲产品的利润）（不少于甲产品的利润）（不少于甲产品的利润）（不少于甲产品的利润）2 2y y1 1+y y2 2+3+3y y3 325002500（不少于乙产品的利润）（不少于乙产品的利润）（
40、不少于乙产品的利润）（不少于乙产品的利润）y y1 1,y y2 2,y y3 300解：解：设设y1，y2，y3分别为每工时设备分别为每工时设备A、B、C的收取费用。则有的收取费用。则有第73页，共138页，编辑于2022年，星期一原问题原问题MinMinf f=65=65y y1 1+40+40y y2 2+75+75y y3 3s.t.3s.t.3y y1 1+2+2y y2 215001500（不少于甲产品的利润）（不少于甲产品的利润）（不少于甲产品的利润）（不少于甲产品的利润）2 2y y1 1+y y2 2+3+3y y3 325002500对偶问题对偶问题对偶问题对偶问题（不少于
41、乙产品的利润）（不少于乙产品的利润）（不少于乙产品的利润）（不少于乙产品的利润）y y1 1,y y2 2,y y3 300第74页，共138页，编辑于2022年，星期一1、对偶定义、对偶定义对称形式：对称形式：互为对偶互为对偶(LP)maxz=cx(DP)minf=b Tys.t.Ax bs.t.ATycTx0y0“max-”“min-”2.2.2线性规划的对偶理论线性规划的对偶理论第75页，共138页，编辑于2022年，星期一一对一对对称形式对称形式的对偶规划之间具有下面的对应关系。的对偶规划之间具有下面的对应关系。(1)若若一一个个模模型型为为目目标标求求“极极大大”，约约束束为为“小小
42、于于等等于于”的的不不等等式式，则则它它的的对对偶偶模模型型为为目目标标求求“极极小小”，约约束束是是“大大于于等等于于”的的不不等等式式。即即“max，”和和“min，”相对应。相对应。(2)从从约约束束系系数数矩矩阵阵看看：一一个个模模型型中中为为，则则另另一一个个模模型型中中为为AT。一一个个模模型是型是m个约束，个约束，n个变量，则它的对偶模型为个变量，则它的对偶模型为n个约束，个约束，m个变量。个变量。(3)从数据从数据b、C的位置看：在两个规划模型中，的位置看：在两个规划模型中，b和和C的位置对换。的位置对换。(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。第76页，
43、共138页，编辑于2022年，星期一2、非对称形式的对偶规划、非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将将模模型型统统一一为为“max，”或或“min，”的的形形式式，对对于于其其中中的的等等式式约约束束按按下下面面（2）、（）、（3）中的方法处理；）中的方法处理；（2）若若原原规规划划的的某某个个约约束束条条件件为为等等式式约约束束，则则在在对对偶偶规规划划中中与与
44、此此约约束束对对应应的的那个变量取值没有非负限制；那个变量取值没有非负限制；（3）若若原原规规划划的的某某个个变变量量的的值值没没有有非非负负限限制制，则则在在对对偶偶问问题题中中与与此此变变量量对对应应的那个约束为等式。的那个约束为等式。第77页，共138页，编辑于2022年，星期一线性规划的原问题与对偶问题的关系，其变化形式可归纳为表线性规划的原问题与对偶问题的关系，其变化形式可归纳为表2-12所示的对应关系。所示的对应关系。原问题（或对偶问题）对偶问题（或原问题）目标函数maxZ目标函数 minf约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项第78页，共138页，编辑于
45、2022年，星期一例例2.8写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型解：解：先将约束条件变形为先将约束条件变形为“”形式形式第79页，共138页，编辑于2022年，星期一再根据非对称形式的对应关系，直接写出对偶规划再根据非对称形式的对应关系，直接写出对偶规划第80页，共138页，编辑于2022年，星期一3 3、单纯形法计算的矩阵描述、单纯形法计算的矩阵描述假设原问题及对偶问题为对称假设原问题及对偶问题为对称LPLP问题。原问题和对偶问题分别为问题。原问题和对偶问题分别为(2.1)(LP)(2.2)(DP)第81页，共138页，编辑于2022年，星期一（2.3）单纯形法计算时
46、总是选取单纯形法计算时总是选取I为初始基，对应的基变量为为初始基，对应的基变量为Xs。设迭代若干步后基变量。设迭代若干步后基变量为为XB，XB在初始单纯形表中的系数矩阵为在初始单纯形表中的系数矩阵为B。将。将B在初始表中单独列出来，而在初始表中单独列出来，而A中去掉中去掉B的若干列后剩下的列组成矩阵的若干列后剩下的列组成矩阵N。则（。则（2.3）的初始单纯形表为）的初始单纯形表为对称对称LP问题（问题（2.1）的矩阵表达式加上松弛变量后为）的矩阵表达式加上松弛变量后为非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0第82页，共138页，编辑于2022年，星期一基变量非基变量cj-z
47、jXBX XN NXXs sCBXBB-1b0IB-1NB-1CN-CBB-1N-CBB-1非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0当迭代若干步，基变量为当迭代若干步，基变量为XB时，则该步的单纯形表中时，则该步的单纯形表中由由XB系数组成的矩阵为系数组成的矩阵为I。对应。对应Xs的系数矩阵在新表中的系数矩阵在新表中应为应为B-1。故当基变量为。故当基变量为XB时，时，新的单纯形表为新的单纯形表为第83页，共138页，编辑于2022年，星期一当当B B为最优基时，在上表中有为最优基时，在上表中有CN-CBB-1N0-CBB-10因因x xB B的检验数可写为的检验数可写为故
48、以上故以上3 3个式子可重写为个式子可重写为CB -CB B-1 B=0C-CBB-1A0-CBB-10CBB-1称为单纯形乘子，若令称为单纯形乘子，若令YT=CBB-1，则有，则有ATYCTY0以上可以看出，此时检验数行中，若取初始基变量检验数的以上可以看出，此时检验数行中，若取初始基变量检验数的相反数，则恰好得到对偶问题的一个可行解。相反数，则恰好得到对偶问题的一个可行解。第84页，共138页，编辑于2022年，星期一4、对偶定理、对偶定理(原问题与对偶问题解的关系）原问题与对偶问题解的关系）考虑（考虑（LP）和（）和（DP）定理定理2-1(弱对偶定理）弱对偶定理）若若x,y分别为（分别为
49、（LP)和（和（DP）的可行解，那么）的可行解，那么cxbTy。推论推论 若（若（LP）可行，那么（）可行，那么（LP）无有限最优解的充分必要条件是）无有限最优解的充分必要条件是（DP）无可行解。）无可行解。第85页，共138页，编辑于2022年，星期一 定理定理2-2(最优性准则定理最优性准则定理)若若x,y分别为分别为(LP)、(DP)的可行解，且的可行解，且cx=bTy，那么，那么x,y 分别为分别为(LP)和和(DP)的最优解。的最优解。定理定理2-3(主对偶定理主对偶定理)若若(LP)和和(DP)均可行均可行那么那么(LP)和和(DP)均有最优解均有最优解,且最优值相等。且最优值相等
50、。以上定理、推论对任意形式的线性规划的对偶均有效以上定理、推论对任意形式的线性规划的对偶均有效 定理定理2-4(互补松弛性互补松弛性)在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。偶变量一定为零。第86页，共138页，编辑于2022年，星期一例例2.10已知线性规划问题已知线性规划问题其对偶问题的最优解为其对偶问题的最优解为，试运用对偶问题的性质，求原问题的最优解