第2章线性规划的对偶理论

第2章

线性规划的对偶理论2.1

线性规划的对偶模型

DualModelofLP2.2对偶性质

Dualproperty

2.3

对偶单纯形法

DualSimplexMethod2.4灵敏度与参数分析

SensitivityandParametricAnalysis12.1线性规划的对偶模型某工厂生产A，B两种产品，已知制造A产品每件需劳动力7人，原料5公斤，电力2度。制造B产品每件需劳动力5人，原料8公斤，电力5度，工厂可使用的劳动力最多为3500人，原料最多为4000公斤，电力最多为2000度，A产品每件利润6元，B产品每件利润7元，问如何安排生产，才使工厂的利润最大？2ⅠⅡ劳动力753500原材料584000电力252000单位产品的利润（元）673线性规划的对偶问题的例子设x1,x2分别是A，B产品的生产量，则：劳动力约束原料约束电力约束现在从另一个角度来考虑企业的决策问题。假如企业不考虑自己生产产品，而将现有的资源标价出售，

问题：决策者应怎样给定资源一个合理的价格？4设购买该厂的资源(劳动力，原料，电力)的单位价格分别为y1,y2,y3,则有生产1个单位的A产品的资源出售给公司应大于其利润生产1个单位的B产品的资源出售给公司应大于其利润线性规划的对偶问题5线性规划的对偶问题两个问题的线性规划如下：两个线性规划之间的关系？6两个线性规划的特点约束条件的右端是另一个规划的目标函数的系数约束条件的系数矩阵的转置是另一个规划的约束条件的系数矩阵这两个线性规划具有对称性。7线性规划的对偶问题称(LP)和(LD)是一对相互对偶的线性规划问题目标函数求最小，约束条件写成大于等于；目标函数求最大，约束条件写成小于等于。8线性规划问题(2.2)就是原线性规划问题(2.1)的对偶线性规划问题，反之，(2.2)的对偶问题就是(2.1)．原问题与对偶问题有如下关系(假设原问题(2.1))：(1)原问题求最大，对偶问题是求最小(2)原问题的约束个数(不含非负约束)等于对偶变量的个数(3)原问题的目标函数系数对应于对偶问题的右端项(4)原问题的右端项对应于对偶问题的目标函数系数(5)原问题的约束矩阵转置就是对偶问题系数矩阵(6)原问题不等式约束符号为“≤”,对偶问题不等式约束符号为“≥”9例2.1写出下列线性规划的对偶问题【解】设Y=(y1，y2)，则有10线性规划问题的规范形式(CanonicalForm或叫对称形式)：定义：

目标函数求极大值时，所有约束条件为≤号，变量非负；

目标函数求极小值时，所有约束条件为≥号，变量非负。

注：(1)线性规划规范形式与标准型是两种不同形式，但可以相互转换。(2)规范形式的线性规划问题的对偶仍然是规范形式．11问题：讨论一般形式的线性规划问题的对偶问题？方法：先将其转化为规范形式的线性规划问题，然后写出其对偶问题，适当将其进行化简。122.2对偶性质Dualproperty

13设原问题是(记为LP)：对偶问题是(记为LD)：2.2.1对偶性质这里A是m×n矩阵,X是n×1列向量。【性质1】弱对偶性:

设X*、Y*分别为LP(max)与

LD(min)的可行解，则14由这个性质可得到下面几个结论：

(LP)的任一可行解的目标值是(LD)的最优值下界；(LD)的任一可行解的目标值是(LP)的最优值的上界；

(2)在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；

(3)若原问题可行且另一个问题不可行，则原问题具有无界解。

注意:

上述结论(2)及(3)的条件不能少。一个问题无可行解时，另一个问题可能有可行解(此时具有无界解)也可能无可行解。15例如：无可行解，而对偶问题有可行解，由结论(3)知必有无界解。16【性质3】无界性:如果原问题(对偶问题)具有无界解,则对偶问题(原问题)无可行解。【性质2】最优性:

设X*与Y*分别是(LP)与(LD)的可行解，则X*、Y*是(LP)与(LD)的最优解当且仅当CX*=Y*b.17【性质4】强对偶性：若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。另一结论：若(LP)与(LD)都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。【性质5】互补松弛性:在线性规划的最优解中，如果对应某一约束条件的对偶变量为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。即18根据对偶性质；可将原问题与对偶问题解的对应关系列表如下：一个问题max另一个问题min有最优解有最优解性质4无无最优解无最优解性质4最优无界解(有可行解)无可行解性质2解无可行解无界解(有可行解)19影子价格在单纯形法的每步迭代中，目标函数都取式中：bi是线形规划原问题约束条件的右端项，它代表第i种资源的拥有量。对偶变量yi的意义代表对一个单位第i种资源的估价。影子价格指的是根据资源在生产中做出的贡献的估价，而不是资源的市场价格。20影子价格是一种边界价格说明yi的值相当于在给定的生产条件下，bi每增加一个单位时目标函数z的增量。21从图中可看到，设备增加一台时，代表该约束条件的直线由①移至①′，相应的最优解由(4，2)变为(4，2.5)，目标函数z=2×4+3×2.5=15.5，即比原来的增大1.5。又若原材料A增加1kg时，代表该约束方程的直线由②移至②′，相应的最优解从(4，2)变为(4.25，1.875)，目标函数z=２×4.25+3×1.875=14.125。比原来的增加0.125。原材料B增加1kg时，该约束方程的直线由③移至③′，这时的最优解不变。22——代表第j种产品的产值影子价格的经济意义——是生产一个单位产品所消耗的各项资源的影子价格的总和，即产品的隐含成本。23影子价格(Shadowprice)取决于企业对资源使用的状况，受生产任务、产品结构差异、管理效率等因素影响。边际利润的概念：增加单位资源对利润的贡献。对资源使用决策的参考依据：买进、卖出制定内部结算价格的参考242.3对偶单纯形法由于单纯表中同时反映原问题与对偶问题的最优解，故可以从求对偶问题最优解角度求解LP模型。例：minz=2x1+3x2maxz'=-2x1-3x2+0x3+0x4 s.tx1+x23标准化s.tx1+x2-x3=3 x1+2x24 x1+2x2-x4=4 x10,x20 xj0,(j=1,2,3,4)maxz'=-2x1-3x2+0x3+0x4

s.t-x1-x2+x3=-3 -x1-2x2+x4=-4 xj0,(j=1,2,3,4)25Cj→x1x2x3x4XBbCB-1 -1 1 0-1 -2 01-2 -3 0 0-3-4x3x400cj-zj-2-300-1/2 0 1 -1/21/2 1 0-1/2x3x2-12cj-zj-1/2 00-3/20-31 0 -2 10 1 1-1x1x221cj-zj0 0 -1 -1-2-3列单纯表计算：26对偶单纯形法步骤：1.列初始单纯形表，使得所有检验数j0；2.出基变量：取min{bi<0

}=bl

→x(l) 3.入基变量：min{——|alk<0}=→xk 4.主元素：[alk]5.迭代：同单纯形法，新单纯表中pk化为单位向量cj-zjalj说明：10使用对偶单纯形法时，初始表中检验数必须全部为j0，即使得其对偶问题为可行解，20为便于说明，这里采取从原问题角度叙述迭代步骤。27本例如果用单纯形法计算，确定初始基可行解时需引入两个人工变量，计算量要多于对偶单纯形法。一般情况下，如果问题能够用对偶单纯形法计算，计算量会少于单纯形法。但是，对偶单纯形法并不是一种普遍算法，它有一定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。当线性规划问题具备下面条件时，可以用对偶单纯形法求解：

①问题标准化后，价值系数全非正；

②所有约束全是不等式。282.4灵敏度分析1．灵敏度分析的概念：当某一个参数发生变化后，引起最优解如何改变的分析。可以改变的参数有： bi——约束右端项的变化，通常称资源的改变；

cj——目标函数系数的变化，通常称市场条件的变化；

pj

——约束条件系数的变化，通常称工艺系数的变化；其他的变化有：增加一种新产品、增加一道新的工序等。29302．分析原理：借助最终单纯形表将变化后的结果按下述基本原则反映到最终表里去。（1）bi变化：（b+△b）´=B-1（b+△b） =B-1b+B-1

△b=b´+B-1

△b（2）pj变化：（pj+△pj

）´=B-1（pj+△pj

） =B-1pj+B-1

△pj

=pj

´+B-1

△pj

（3）cj变化：直接反映到最终表中，计算检验数。（4）增加一个约束方程：直接反映到最终表中。（5）增加新产品：仿照pj变化。313．计算示例：maxz=2x1+3x2s.t2x1+2x2

12

x1+2x28

4x1

164x212x10,x20例：已知某线性规划模型及最终的单纯表如下：问：（1）若b2增加8个单位，最优解如何变化？（2）若c2还可增加2个单位，最优解如何改变？（3）若引进一个新变量（产品）y，其目标函数系数为cy=5，系数列向量为py=[3263]，问最优解是否会改变？

cj—230000

CBXBbx1x2x3x4x5x60x302x140x643x22001-1-0.25010000.250000-20.510100.5-0.1250cj－zj000-1.5-0.125032解：（1）（b+△b）´=B-1b+B-1

△b=b´+B-1

△b =0442T

+-80-164T=-84-126TB-1△b=1-1-0.250000.2500-20.5100.5-0.12500800=-80-164利用对偶单纯形法继续求最优解。（2）当cj变化时，´=C´－CB´B-1

A，列出单纯形表，重新求出检验数，如表中所示：（3）增加y时，y=cy-CB

B-1

py=5-(01.50.1250)[3263]T =1.25>0选择y作入基变量，py´=B-1

py==-0.51.520.25T继续迭代：33

cj—230000

CBXBbx1x2x3x4x5x60x3-82x140x6-123x26001-1-0.25010000.250000-20.510100.5-0.1250cj－zj000-1.5-0.12500x3-22x140x463x230010-0.5-0.510000.2500001-0.25-0.5010000.25cj－zj0000-0.5-0.750x542x130x673x2300-2011100.500-0.2500-0.510-0.25010000.25cj－zj00-100-0.25返回右端项变化分析单纯形表：34

cj—250000

CBXBbx1x2x3x4x5x60x302x140x645x22001-1-0.25010000.250000-20.510100.5-0.1250cj－zj000-2.50.12500x322x120x585x23001-200.510010-0.5000-412010000.25cj－zj000-20-0.25返回Cj变化分析单纯形表：35

cj—230000

5

CBXBbx1x2x3x4x5x6