线性规划及其对偶问题课件.ppt

1、第第2章章 线性规划及其对偶问题线性规划及其对偶问题(Linear Programming&its Dual Problem)2.1线性规划线性规划2.2 对偶理论对偶理论2.3 灵敏度分析灵敏度分析*2.4 LINGO软件求解线软件求解线 性规划模型的方法性规划模型的方法 2.1 线线 性性 规规 划划(Linear Programming)2.1.1 线性规划问题的数学模型线性规划问题的数学模型2.1.2 线性规划问题解的概念线性规划问题解的概念2.1.3 求解线性规划问题的图解法求解线性规划问题的图解法2.1.4 求解线性规划问题的单纯形法求解线性规划问题的单纯形法2.1.5 单纯形法的

2、进一步讨论单纯形法的进一步讨论2.1.6 线性规划模型的应用线性规划模型的应用为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。例、有一正方形铁皮，如何截取例、有一正方形铁皮，如何截取 x 使容积为最大？使容积为最大？xa 22xxav 此为无约束极值问题此为无约束极值问题22(2)(2)(2)0axxax 6ax 0 dxdv2.1.1 线性规划问题的数学模型线性规划问题的数学模型（一

3、）、问题的提出（一）、问题的提出 设设 备备产产 品品 A B C D利润（元）利润（元）2 1 4 0 2 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12例、已知资料如下表例、已知资料如下表所示，问如何安排生所示，问如何安排生产才能使利润最大？产才能使利润最大？或如何考虑利润大，或如何考虑利润大，产品好销。产品好销。模模 型型max Z=2x1+3x2 x1 0,x2 0s.t.2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12此为带约束的极值问题此为带约束的极值问题问题中总有未知的变量，需要我们去解决问题中总有未知的变量，需要我们去解决要求：有目标函数及约

4、束条件，一般有非负条件存在，由此组成规划要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。数学模型。如果在规划问题的数学模型中，变量是连续的（数值取实数）其目标如果在规划问题的数学模型中，变量是连续的（数值取实数）其目标函数是有关线性函数（一次方），约束条件是有关变量的线性等式或函数是有关线性函数（一次方），约束条件是有关变量的线性等式或不等式，这样，规划问题的数学模型是线性的。反之，就是非线性的不等式，这样，规划问题的数学模型是线性的。反之，就是非线性的规划问题（其中一个条件符合即可）。规划问题（其中一个条件符合即可）。（二）、数学模型（二）、数学模型 1、1 12 21

5、1 112 2111 12 21max(min)(,)(,)0,0n nn nmmmn nmnZcxc xc xa xa xa xba xa xa xbxx 目标函数：目标函数：约束条件：约束条件：2、线性规划数学模型的一般形式、线性规划数学模型的一般形式也可以记为如下形式也可以记为如下形式：11 max(min)Z (,)(i1,2,)0 (j 1,2,)njjjnijjijjc xa xbmxn 目标函数：目标函数：约束条件：约束条件：如将上例用表格表示如下：如将上例用表格表示如下：设变量设变量 (1,2,)jxjn 产产 品品 j 设设 备备 i 有效台时有效台时 利润利润 mnmijn

6、aaaaa 1111n 2 1m 2 1 mbbb 21nccc 21jcib向向 量量 形形 式：式：12(,)nCccc nxxX1 mjjjaap1 mbbb1max (min)(,).0 jjZCXp xbs tX 矩阵形式：矩阵形式：mnmnaaaaA1111m ax (m in)(,)0 ZC XA XbX 规规划划确定型确定型随机型随机型静态规划静态规划动态规划动态规划线性规划线性规划非线性规划非线性规划 整数规划整数规划 非整数规划非整数规划整数规划整数规划非整数规划非整数规划3、规划类型、规划类型一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐

7、标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但需将适用于任意变量、但需将一般形式变成标准形式一般形式变成标准形式2.1.2 线性规划问题解的概念线性规划问题解的概念（一）、求解方法（一）、求解方法1、解的概念、解的概念 可行解：满足约束条件可行解：满足约束条件、的解为可行解。所有解的集的解为可行解。所有解的集合为可行解的集或可行域。合为可行解的集或可行域。最优解：使目标函数达到最大值的可行解。最优解：使目标函数达到最大值的可行解。基：基：B是矩阵是矩阵A中中mm阶非奇异子矩阵（阶非奇异子矩阵（B 0），则），则B是一个基。是一个基。111121(,)mmmm maa

8、Bp ppaa则称则称 Pj(j=1,2,m)为基向量。为基向量。Xj 为基变量，否则为非基变量。为基变量，否则为非基变量。（二）、线性规划问题的解（二）、线性规划问题的解 基本解基本解(基解基解)：令所有非基变量的值全为：令所有非基变量的值全为0，求得的基变，求得的基变量解与这些量解与这些0非基变量所组成的解非基变量所组成的解 X=(x1,x2,xm,0,0)T称为称为LP的基本解，最多为的基本解，最多为 个。个。Cmn 基本可行解：满足非负约束条件的基本解，简称基可行解基本可行解：满足非负约束条件的基本解，简称基可行解 可行基：对应于基可行解的基称为可行基。可行基：对应于基可行解的基称为可

9、行基。非可行解非可行解可可行行解解基解基解基可行解基可行解2、解的基本定理、解的基本定理 若线性规划问题存在可行解，则问题的可行域是凸集若线性规划问题存在可行解，则问题的可行域是凸集（凸多边形）（凸多边形）凸集凸集凸集凸集不是凸集不是凸集顶顶 点点 最优解一定是在凸集的某一顶点实现（顶点数目不超最优解一定是在凸集的某一顶点实现（顶点数目不超过过 个）个）Cmn 先找一个基本可行解，与周围顶点比较，如不是最大，先找一个基本可行解，与周围顶点比较，如不是最大，继续比较，直到找出最大为止。继续比较，直到找出最大为止。3、解的情况、解的情况唯唯 一一 解解无无 穷穷 解解无无 界界 解解无可行解无可行

10、解有最优解有最优解无最优解无最优解建立直角坐标建立直角坐标 ，图中阴影部分及边界上的点均为，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。其解，是由约束条件来反映的。例例2.3)0 ,(21xx1212121212m a x23221 228.4 1 6 41 20,0Zxxxxxxs txxxx2.1.3 求解线性规划问题的图解法求解线性规划问题的图解法01 2 3 4 5 6 7 8 1 2 3 4 5 6 作作 图图 有唯一最有唯一最 优优 解：解：x1=4,x2=2最优目标函数值最优目标函数值 Z*=14x2 x1(4 2)00124 16 48212223221212121

11、21xxxxxxxxxxZ,max 例、例、例、例、121212212max2263212.20,0Zxxxxxxs txxx无穷多最优解无穷多最优解12121212max22.1,0 Zxxxxs txxxx 无界解无界解x1x1x2 x2 1121212min32 1.236,0 Zxxxxs txxxxx1x2 无可行解无可行解例、例、（一）基本思想（一）基本思想将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不一个基本可行解，并判断是否是最优。如果是，获得最

12、优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。（二）线性规划模型的标准形式（二）线性规划模型的标准形式max (i1,2,m).0 (j1,2,n)jjijjijZc xa xbstx1、标准形式、标准形式2.1.4 求解线性规划问题的单纯形法求解线性规划问题的单纯形法 2、特征：、特征：.目标函数为求极大值，也可以用求极小值；目标函数为求极大值，也可以用求极小值；.所有约束条件（非负条件除外）都是等式，右端常数项所有约束条件（非负条件除外）都是等式，右端常数项为非负；为非负；.变量为非负。变量为非负。3

13、、转换方式：、转换方式：.目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数乘以，则可将目标函数乘以（1），可化为求极大值问题。），可化为求极大值问题。jjxcZmin jjxcZZmax也就是：令也就是：令 ，可得到上式。，可得到上式。ZZ 即即.约束方程的转换：由不等式转换为等式约束方程的转换：由不等式转换为等式 ijijbxa0 iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量称为剩余变量.变量的变换变量的变换 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：jxjjjxxx

14、 0,jjxx例例2.2 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式123123123123123m in235 7 42.325,0,Zxxxxxxxxxs txxxxxx 为无约束（无非负限制）为无约束（无非负限制）解解:用用 替换替换 ，且，且 ，54xx 3x0,54 xx将第将第3个约束方程两边乘以个约束方程两边乘以（1）将极小值问题反号，变为求极大值将极小值问题反号，变为求极大值标准形式如下：标准形式如下：12456712456124571245124567max23()005()7()2.52()5,0 Zxxxxxxxxxxxxxxxxstxxxxx xxxx

15、x76,xx引入变量引入变量例、将下列线性规划问题化为标准型例、将下列线性规划问题化为标准型12121212m in2385.340,Zxxxxs txxxx 为无约束为无约束解：解：1341345134613456max2()38()5 .3()4 ,0 Zxxxxxxxs txxxxxxxxx（三）、单纯形法（三）、单纯形法例例2.31212121212m a x23221 228.4 1 6 41 2,0 Zxxxxxxs txxxx变成标准型变成标准型12345612312415max23000022 12 2 8 .4 16 Zxxxxxxxxxxxxs txx26123456 4

16、12 ,0 xxxxxxxx约束方程的系数矩阵约束方程的系数矩阵 654321100040010004001021000122ppppppA IppppB100001000010000165436543 xxxx,21xx,可作为为基变量可作为为基变量为非基变量为非基变量I 为单位矩阵且线性独立为单位矩阵且线性独立令：令：12x 16x 8x 12x 0654321 xx则：则：基本可行解为基本可行解为（0,0,12,8,16,12）此时，此时，Z=0然后，找另一个基本可行解。即将非基变量换入基变然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到量中，

17、但保证其余的非负。如此循环下去，直到找到最优解为止。最优解为止。注意：为尽快找到最优解，在换入变量时有一定的要求。注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。如将目标系数大的先换入等。找出一个初始可行解找出一个初始可行解是否最优是否最优转移到另一个目标函数转移到另一个目标函数（找更大的基本可行解）（找更大的基本可行解）最优解最优解是是否否循循环环直到找出为止，核心是：变量迭代直到找出为止，核心是：变量迭代结束结束其步骤总结如下：其步骤总结如下：jjcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11

18、,110010 0 ijijjacc min(0)ilikiikbaa（四）、单纯形表（四）、单纯形表判定标准：判定标准：0 0:min0 0:maxz j jjjjjjjjijijjjczzcczzcaczc 若求若求 或或12345612312415max23000022 12 2 8 .4 16 Zxxxxxxxxxxxxs txx26123456 4 12 ,0 xxx xxxxx例例 题：题：cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4

19、 0 0 0 1j i2 3 0 0 0 012/28/212/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x6000 x3x4x516 4 0 0 0 1 0 ji3x23010001/42620100-1/210010 0-1/2cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60003x3x4x5x262163 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/4j i2 0 0 0 0 -3/46/2216/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5

20、 x60203x3 x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/44412j 0 0 0 -2 0 1/4icj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x6 x1x5x2 4402 0 0 2 -4 0 1 1 0 1 -1 0 0 0 0 -4 4 1 0 0 1 -1/2 1 0 0j 0 0 -1/2 -1 0 0i 0 0 0 -2 0 1/44412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/

21、42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cjijcj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x6 x2 0442 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0j 0 0 0 -3/2 -1/8 0i 0 0 0 -2 0 1/44412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4

22、 x5 x6bxBcB 2 3 0 0 0 0cjij练习练习1212121223515.6224 ,0maxZxxxxs txxxx121231241234235 15.62 24 ,0maxZxxxxxs txxxxxxx 0 0 -1/12 -7/24 x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cji15/43/4011/4-1/810-1/125/24j（一）、模型情况（一）、模型情况 变变 量：量：xj0 xj0 xj无约束无约束 结结1、组成、组成 约束条件：约束条件：=b 目标函数：目标函数：max min 果果2、变量、变量 xj0 令令 xj=-xj，xj

23、0 xj0 不处理不处理 xj 无约束无约束 令令xj=xj xj,xj0,xj0 唯一最优唯一最优无穷最优无穷最优无界解无界解无可行解无可行解2.1.5 单纯形法的进一步讨论单纯形法的进一步讨论3 3、约束、约束 条件：条件：bxpbxpbxpjjjjjj 加入松弛变量加入松弛变量加入人工变量加入人工变量先减去先减去 再加上再加上axaxsxsx例例2.512312312313123m in3 21 1423.2 1,0 Zxxxxxxxxxs txxxxx 1231234 12356137123min3 2 11 42 3 .2 1 ,0 Zxxxxxxxxxxxxs txxxxxx 4

24、4、目标函数：、目标函数：max,min 设规划模型约束条件为设规划模型约束条件为 ，需加入人工变量，需加入人工变量而得到一个而得到一个mm的单位矩阵，即基变量组合。因人工变量的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基本可行解中，需要将它们从基为虚拟变量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的人工变量，表示变量中替换出来。若基变量中不含有非零的人工变量，表示原问题有解。若当原问题有解。若当 ，而还有人工变量（非零）时，而还有人工变量（非零）时，则表示原问题无可行解。则表示原问题无可行解。axjjp xb0j加入人工变量后，目的是找到一

25、个单位向量，叫人工基。其加入人工变量后，目的是找到一个单位向量，叫人工基。其目标价值系数要确定，但不能影响目标函数的取值。一般可目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大采用两种方法处理：大M法和两阶段法。法和两阶段法。.大大M法：法：即假定人工变量在目标函数中的系数为即假定人工变量在目标函数中的系数为M（任（任意大正数），如果是求极大值，需加意大正数），如果是求极大值，需加-M；如果是求极小值，；如果是求极小值，需加需加M。如基变量中还存在。如基变量中还存在M，就不能实现极值。，就不能实现极值。1234567 min300ZxxxxxMxMx 如上例：0 j计算

26、过程如下：用来判断cj-31100MMcBxBbx1x2x3x4x5x6x70 x4111-21100011Mx63-4120-1103/2Mx71-20100011j-3+6M1-M1-3M0M00cBxBbx1x2x3x4x5x6x70 x4103-20100-1Mx610100-11-211x31-2010001j-11-M00M03M-1iicj-31100MMcBxBbx1x2x3x4x5x6x70 x4123001-22-541x210100-11-21x31-2010001j-10001M-1M+1cBxBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/3

27、1x210100-11-21x390012/3-4/34/3-7/3j0001/31/3M-1/3M-2/3ii最优解为最优解为 x*=(4,1,9,0,0,0,0)T，Z*=2 用计算机处理数据时，只能用很大的数代替用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。可能造成计算机上的错误，故多采用两阶段法。第一阶段：第一阶段：在原线性规划问题中加入人工变量，构造如下模型：在原线性规划问题中加入人工变量，构造如下模型：1111 11111 1min00 .nn mnnnnmmnnn mmWxxxxa xa xxbsta xaxxb1 0 n mxx.两阶段法：

28、两阶段法：对上述模型求解（单纯形法），若对上述模型求解（单纯形法），若W=0,W=0,说明问题存在基本可说明问题存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停止行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。运算。第二阶段：在第一阶段的最终表中，去掉人工变量，将目第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。计算的初始表（用单纯形法计算）。例例2.61231234 12356137123min3 2 11 42 3 .2 1 ,0 Zx

29、xxxxxxxxxxxs txxxxxx 第一阶段第一阶段cj0000011cBxBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-20100011j6-1-301000 x4103-20100-11x610100-11-210 x31-2010001j0-100103i0 x4123001-22-50 x210100-11-20 x31-2010000j0000011cj-31100cBxBbx1x2x3x4x50 x4123001-241x210100-11x31-20100j-10001-3x141001/3-2/31x210100

30、-11x390012/3-4/3j0001/31/3i第二阶段第二阶段最优解为最优解为 x*=(4,1,9,0,0,0,0)T，Z*=23231 323x ,3 :052122 xxxbbii，变变换换有有：两两端端乘乘如如、6 6、无、无可行解的判断：运算到检验数全负为止，可行解的判断：运算到检验数全负为止，仍含有人工变量，无可行解。仍含有人工变量，无可行解。7 max min 0 0 (0)0)jjjj、检验数：或或（8 8、退化：、退化：即计算出的即计算出的（用于确定换出变量）存在（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个有两个以上相同的最小比值，会造成下

31、一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。或几个基变量等于零，这就是退化（会产生退化解）。虽任意换出变量，目标函数值不变，但此时不同的基虽任意换出变量，目标函数值不变，但此时不同的基却表示为同一顶点，其特例是永远达不到最优解。需作如却表示为同一顶点，其特例是永远达不到最优解。需作如下处理：下处理：.当当 中出现两个以上最大值时，选下标最中出现两个以上最大值时，选下标最小的非基变量为换入变量；小的非基变量为换入变量；.当当中出现两个以上最小值时，选下标最小的基变中出现两个以上最小值时，选下标最小的基变量为换出变量。量为换出变量。0j建建立立模模型型个个 数数取取 值值右右

32、端端 项项等式或等式或不等式不等式极大或极小极大或极小新加新加变量变量系数系数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa求求解解图图解解法、法、单单纯纯形形法法单单纯纯形形法法不不处处理理令令xj=xj-xj xj 0 xj 0令令 xj=-xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=-ZminZ=max z0-M根据上表列出初始单纯形表根据上表列出初始单纯形表 A（二）、线性规划小结（二）、线性规划小结Ajjcnmmcccc1

33、1BcBXbmcc 1mxx 1mbb 1nmmxxxx 11ijjjjiijczcc a初始单纯形表初始单纯形表(max型型)ija停止停止Ajjjzc :求求0 j所所有有kj即即找找出出max)()0(0 jika对对任任一一min(0)ilikiikbaalkxx替替换换基基变变量量用用非非基基变变量量新新单单纯纯形形表表列列出出下下一一个个ax含有含有量中是否量中是否基变基变 0 j非非基基变变量量的的有有某某个个最最优优解解一一唯唯 无无可可行行解解最优解最优解无穷多无穷多是是否否环环循循否否否否否否是是是是是是循环循环无无界界解解课堂练习课堂练习123123123123m ax2

34、357.2510,0Zxxxxxxs txxxxxx123456123412356123456max23507.2510,0ZxxxMxxMxxxxxs txxxxxxxxxxx-M+1/7-1/7-M-16/7-50/7001/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5x4x3x2x1bxBcB-M0-M-532cj0-M0-5+2M3-4M2+3M51-101-5210 x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cjijj 一般而言，一个经济、管理问题凡是满足以下条件一般而言，一个经济、管理问题凡是满

35、足以下条件时，才能建立线性规划模型。时，才能建立线性规划模型。.要求解问题的目标函数能用数值指标来反映，要求解问题的目标函数能用数值指标来反映，且为线性函数；且为线性函数；.存在着多种方案；存在着多种方案；.要求达到的目标是在一定条件下实现的，这些要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。约束可用线性等式或不等式描述。2.1.6 线性规划模型的应用线性规划模型的应用（一）、资源的合理利用（一）、资源的合理利用 一般提法：一般提法：某厂计划在下一生产周期内生产某厂计划在下一生产周期内生产B1,B2,Bn种产品，要消耗种产品，要消耗A1,A2,Am种资源，已知每件产品所

36、消耗的资源数、每种资源的数量限制以及每件产种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如表所示，问如何安排生产计划，才能充分利用现有的资品可获得的利润如表所示，问如何安排生产计划，才能充分利用现有的资源，使获得的总利润最大？源，使获得的总利润最大？单件 产 消耗 品资源资源限制单件利润nBB 1mAA 1mbb 1nCC 1mnmnaaaa 1111max.0 jjijjijZc xa xbs tx模 型（二）、生产组织与计划问题（二）、生产组织与计划问题 一般提法：某工厂用机床一般提法：某工厂用机床A A1 1,A,A2 2,A Am m 加工加工B B1

37、1,B,B2 2,B Bn n 种零件。种零件。在一个周期内，各机床可能工作的机时（台时），工厂必须完成各在一个周期内，各机床可能工作的机时（台时），工厂必须完成各种零件的数量、各机床加工每个零件的时间（机时种零件的数量、各机床加工每个零件的时间（机时/个）和加工每个个）和加工每个零件的成本（元零件的成本（元/个）如表所示，问如何安排各机床的生产任务，才个）如表所示，问如何安排各机床的生产任务，才能完成加工任务，又使总成本最低？能完成加工任务，又使总成本最低？加工 零 时间 件机床机时限制必须零件数nBB 1mAA 1maa 1nbb 1mnmnaaaa 1111加工 零 成本 件机床nBB

38、1mAA 1mnmncccc 1111 0 s.t.min (11ijjijiijijminjijijijjiijxbxaxaxcZxBAx一组变量）。模型：一组变量）。模型：的数量，求的数量，求在一生产周期加工零件在一生产周期加工零件为机床为机床设设（三）、合理下料问题（三）、合理下料问题 一般提法一般提法 设用某种原材料截取零件设用某种原材料截取零件A1,A2,Am的毛坯。根据以往的经验，的毛坯。根据以往的经验，在一种原材料上可以有在一种原材料上可以有B1,B2,Bn种不同的下料方式，每种下料种不同的下料方式，每种下料方式可截得的各种毛坯个数以及每种零件的需要量如表所示，问方式可截得的各种

39、毛坯个数以及每种零件的需要量如表所示，问应如下料才能既满足需要又使原材料消耗最少？应如下料才能既满足需要又使原材料消耗最少？下料 下料毛 件数 方式坯型号需 要毛坯数nBB 1mAA 1mbb 1mnmnaaaa 1111121111111(1,2)min 0 (1,2,)jjnnnmmnnmjxBjnZxxxa xa xb s.t.axaxbxjn设：表示用种方式下料的原材料件数，其数学模型为：现有一批某种型号的圆钢长现有一批某种型号的圆钢长8 8米，需要截取米，需要截取2.52.5米米长的毛坯长的毛坯100100根，长根，长1.31.3米的毛坯米的毛坯200200根。问如何才能既满足需根。

40、问如何才能既满足需要，又能使总的用料最少？要，又能使总的用料最少？1002002.5米米1.3米米需要需要根数根数下料下料 下料下料毛毛 件数件数 方式方式坯型号坯型号1234123234min32100.2462000(1.2.3.4)jZxxxxxxxs txxxxj设变量为设变量为 第第 j 种方法的所有种方法的所有原料件数原料件数jx例题例题1 1：一一30二二22三三14四四06（四）、合理配料问题（四）、合理配料问题 一般提法一般提法 某饲养场用某饲养场用n种饲料种饲料B1,B2,Bn配置成含有配置成含有m种营养成分种营养成分A1,A2,Am的混合饲料，其余资料如表所示。问应如何配

41、料，的混合饲料，其余资料如表所示。问应如何配料，才能既满足需要，又使混合饲料的总成本最低？才能既满足需要，又使混合饲料的总成本最低？含 饲 量 料成分最 低需要量原料单价nBB 1mAA 1mbb 1nCC 1mnmnaaaa 111111 min (i1,2m)0 jnjjjnijjijjxjZc xa xbs.t.x设 表示第 种饲料所用的数量，其模型如下：例题例题2 2：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省？问两种食物各食用多少，才能既满足需要、又使总费用最省？

42、设：设：xj 表示表示Bj 种食物用量。种食物用量。2 1.5原料单价原料单价1.007.5010.00 0.1 0.15 1.7 0.75 1.10 1.30A1A2A3 最最 低低需要量需要量 甲甲 乙乙 含含 食食 量量 物物成分成分1212121212min21.50.100.151.001.700.757.50.1.101.3010.00,0Zxxxxxxs txxxx（五）、运（五）、运 输输 问问 题题已知资料如表所示：已知资料如表所示：单位 销 运价 地产地产量销 量nBB 1mAA 1maa 1nbb 1mnmncccc 1111模型如下：模型如下：11min .()0 mn

43、ijijijijiijjijijZc xxas txbabx 11min .()0 mnijijijijiijjijijZc xxas txbabx 某运输问题的资料如下：某运输问题的资料如下：6483销量7524852431921092产量单位 销地 运价产地4321 BBBB321AAA例题例题3：)4.3.2.1,3.2.1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

44、xZxijij 约约束束条条件件：目目标标函函数数：为为运运量量设设（六）、作物布局问题（六）、作物布局问题单 土 产 地作物播种面积土地面积nBB 1mAA 1maa 1nbb 1mnmncccc 1111ijijjjabxBA已知资料如下表所示，假设设为土地种植作物为的面积数。max(1,2).(1,2)0 ijijijiijjijZc xxa imstxbjnx此外，还有连续投资、投入产出等模型问题。此外，还有连续投资、投入产出等模型问题。2.2 对偶理论对偶理论(Duality Theory)2.2.1 对偶问题的提出对偶问题的提出2.2.2 线性规划问题解的概念线性规划问题解的概念2

45、.2.3 线性规划的对偶理论线性规划的对偶理论 2.2.4 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 2.2.5 对偶单纯形法对偶单纯形法 2.2.1 对偶问题的提出对偶问题的提出 例例2.7 某工厂拥有某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。利润的方案。产品甲产品甲产品乙产品乙设备能力（设备能力（h）设备设备A3

46、265设备设备B2140设备设备C0375利润（元利润（元/件）件）15002500 解：解：设设 x1，x2 分别为甲乙两种产品的生产量，则有分别为甲乙两种产品的生产量，则有121212212max150025003265240.375,0zxxxxxxstxx x若例若例2.7问题的设备都用于外协加工，工厂收取加工费。试问：设备问题的设备都用于外协加工，工厂收取加工费。试问：设备 A、B、C 每工时各如何收费才最有竞争力？每工时各如何收费才最有竞争力？解：解：设设 y1，y2，y3 分别为每工时设备分别为每工时设备 A、B、C 的收取费用。则有的收取费用。则有原问题原问题121212212

47、max150025003265240.375,0zxxxxxxstxx x1、对偶定义、对偶定义 对称形式：对称形式：互为对偶互为对偶 (LP)max z=c x (DP)min f=b Ty s.t.Ax b s.t.AT y cT x 0 y 0 “max-”“min-”2.2.2 线性规划的对偶理论线性规划的对偶理论 一对一对对称形式对称形式的对偶规划之间具有下面的对应关系。的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求若一个模型为目标求“极大极大”，约束为，约束为“小于等于小于等于”的不等式，的不等式，则它的对偶模型为目标求则它的对偶模型为目标求“极小极小”，约束是，约束是

48、“大于等于大于等于”的不等的不等式。即式。即“max，”和和“min，”相对应。相对应。(2)从约束系数矩阵看：一个模型中为从约束系数矩阵看：一个模型中为，则另一个模型中为，则另一个模型中为AT。一。一个模型是个模型是m个约束，个约束，n个变量，则它的对偶模型为个变量，则它的对偶模型为n个约束，个约束，m个变个变量。量。(3)从数据从数据b、C的位置看：在两个规划模型中，的位置看：在两个规划模型中，b和和C的位置对换。的位置对换。(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。2、非对称形式的对偶规划、非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划

49、。一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。划。（1）将模型统一为）将模型统一为“max，”或或“min，”的形式，对于其中的等式的形式，对于其中的等式约束按下面（约束按下面（2）、（）、（3）中的方法处理；）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题

50、中与此若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。变量对应的那个约束为等式。线性规划的原问题与对偶问题的关系，其变化形式可归纳为表线性规划的原问题与对偶问题的关系，其变化形式可归纳为表2-12所示所示的对应关系。的对应关系。原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数max Z目标函数目标函数 min f约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项00n个变量无约束n个约束条件m个约束条件=00m个变量无约束例例2.8 写出