运筹学基础对偶线性规划

运筹学基础对偶线性规划第1页，共37页，2023年，2月20日，星期日一、对偶线性规划问题

某工厂计划安排生产Ⅰ、Ⅱ两种产品，已知每种单位产品的利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、现有原材料和设备台时的定额如下表所示：【例1】Ⅰ

Ⅱ设备128台时原材料A4016Kg原材料B0412Kg每单位产品利润（万元）23原问题的策略:问应如何安排生产才能使工厂获利最大？现在的策略:假设不生产Ⅰ、Ⅱ产品,而是计划将现有资源出租或出售,从而获得利润,这时需要考虑如何定价才合理?第2页，共37页，2023年，2月20日，星期日设x1、x2分别表示计划生产产品Ⅰ、Ⅱ的单位数量，由题意原问题的模型为：工厂获得最大利润符合资源限制Ⅰ

Ⅱ设备128台时原材料A4016Kg原材料B0412Kg每单位产品利润（万元）23原问题的模型第3页，共37页，2023年，2月20日，星期日

改变策略后，需要考虑如何给资源定价的问题！设y1、y2、y3分别表示出租单位设备台时的租金和出售单位原材料A、B的利润.y1+4y2≥2，2y1+4y3≥3则：工厂出租设备、原材料的租金要大于生产的利润才合算。工厂把所有设备台时和资源都出租和出让，其收入为：要寻找使租用者支付的租金最少的策略。Ⅰ

Ⅱ设备128台时原材料A4016Kg原材料B0412Kg每单位产品利润（万元）23新问题的模型第4页，共37页，2023年，2月20日，星期日工厂改变策略以后的数学模型为：工厂获得相应利润用户所付租金最少第5页，共37页，2023年，2月20日，星期日联系在于，它们都是关于工厂生产经营的模型,并且使用相同的数据；原模型和对偶模型既有联系又有区别区别在于,它们所反映的实质内容是完全不同的：前者是站在工厂经营者的立场上追求工厂的销售收入最大，而后者则是站在谈判对手的立场上寻求应付工厂租金最少的策略。第6页，共37页，2023年，2月20日，星期日所谓对偶规划，就是与线性规划原问题相对应并使用同一组数据按照特定方法形成的另一种反映不同性质问题的线性规划模型。第7页，共37页，2023年，2月20日，星期日

原模型与对偶模型有很多的内在联系和相似之处。如原问题如求目标函数最大化，对偶问题即求目标函数最小化；原问题目标函数的系数变成为对偶问题的右边项，而原问题的约束的右边项则变成为对偶问题目标函数的系数；对偶问题的系数矩阵是原问题系数矩阵的转置。就象一个人对着镜子会左右颠倒一样，原问题与对偶问题之间存在着严格的对应关系。原问题的一般模型可定义为：二、对偶规划的一般数学模型nnxcxcxcZ+++=...max2211s.t.11212111...bxaxaxann£+++22222121...bxaxaxann£+++

……….mnmnmmbxaxaxa£+++...22110,...,,21³nxxx相应的对偶问题的一般模型可定义为：

mmybybybS+++=...min2211

s.t.11221111...cyayayamm³+++22222112...cyayayamm³+++

………

nmmnnncyayaya³+++...22110,...,,21³myyy第8页，共37页，2023年，2月20日，星期日

上述的原问题P和对偶问题D还可以用矩阵形式写为：

(P)maxZ=cx

s.t.Ax≤b

x≥0其中),..,,(21myyyy=上述的对偶模型都称作为对称型对偶模型。而在当原问题转化为标准型以后所建立的对偶模型则是非对称型的，如：

(P)maxZ=cx

s.t.Ax=b

x≥0s.t.yAy≥

c≥0(D)minS=ybs.t.yA≥cy为自由变量(D)minS=yb原问题与对偶问题的矩阵形式问题：如何由原模型写出对偶模型？其规律是什么?第9页，共37页，2023年，2月20日，星期日三、原问题与对偶问题的对应关系当我们讨论对偶问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。下列的表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划原问题转化为对偶问题的一般规律。原问题线性规划模型对偶线性规划模型第10页，共37页，2023年，2月20日，星期日原问题为maxZ的线性规划问题对偶关系表原问题（或对偶问题）

对偶问题（或原问题）

目标函数最大化(maxZ)

n个变量

m个约束

约束条件限定向量（右边项）

目标函数价值向量（系数）

≥

0

变量

≤0≥

无限制

约束

≤

＝

目标函数最小化（minS）

n个约束

m个变量

目标函数价值向量（系数）

约束条件限定向量（右边项）

≥

约束

≤

≤0

＝

变量

≥0

无限制

同号反号第11页，共37页，2023年，2月20日，星期日原问题 对偶问题目标函数max

目标函数min 原问题(maxZ)与对偶之关系：原问题(maxZ)口诀:约束决定变量是反号原问题(maxZ)口诀:变量决定约束是同号第12页，共37页，2023年，2月20日，星期日解：由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3（还可依对偶问题写出原问题）例1写出下列问题的对偶问题：变量决定约束是同号,约束决定变量是反号

maxZ=2x1+x25x2≤

156x1+2x2≤

24x1+x2≤

5

x1,x2≥

0

minw=15y1+24y2+5y3

6y2+y3≥

2s.t.y1,y2,y3≥

0

5y1+2y2

+y3≥1第13页，共37页，2023年，2月20日，星期日原问题为minS的线性规划问题对偶关系表原问题（或对偶问题）对偶问题（或原问题）目标函数最小化(minS)

n个变量

m个约束

约束条件限定向量（右边项）目标函数价值向量

≥

0

变量≤0≥无限制

约束≤

＝目标函数最大化（maxZ）

n个约束

m个变量

目标函数价值向量（系数）约束条件限定向量

≤

约束≥

≥0

＝

变量≤0无限制

同号反号第14页，共37页，2023年，2月20日，星期日原问题 对偶问题目标函数min

目标函数max 原问题(minS)与对偶之关系：原问题(minS)口诀:约束决定变量是同号原问题(minS)口诀:变量决定约束是反号第15页，共37页，2023年，2月20日，星期日解：由原模型三个约束条件确定对偶模型有三个变量y1,y2,y332134maxyyyZ+-=s.t.1232

1£--yy2y-332

1£

+-y4y42321£++yyy（还可依对偶问题写出原问题）例2写出下列问题的对偶问题：32143MinxxxS+-=

s.t.1321£+-4xx2x423321-£++-xxx3-23

1£+

x

xx1,x2,x3

³0变量决定约束是反号,约束决定变量是同号01£y，02£y03£y，第16页，共37页，2023年，2月20日，星期日练习：试求下列线性规划问题的对偶问题321342maxxxxZ-+=

s.t.10321£+-xxx534321-=-+-xxx8523321³-+xxx01³x，02£x

第17页，共37页，2023年，2月20日，星期日练习：试求下列线性规划问题的对偶问题

答案：321342maxxxxZ-+=

s.t.10321£+-xxx534321-=-+-xxx8523321³-+xxx01³x，02£x

3218510minyyyS+-=s.t.23321³+-yyy424321£++-yyy353321-=--yyy01³y，03£y第18页，共37页，2023年，2月20日，星期日练习：试求下列线性规划问题的对偶问题

maxZ=5y1+4y2+6y3y1+2y2≥

2y1+2y2

+y3≤

3-3y1+y3≤

-5

y1-y2+y3＝1

y1≥

0,y2,y3≤

0

答案：第19页，共37页，2023年，2月20日，星期日线性规划的对偶理论包括以下几个基本定理。定理1（对称性定理）§2.2线性规划的对偶理论定理2（弱对偶定理）即对偶问题的对偶是原问题。设x和y分别是原问题和对偶问题的可行解，则必有cx≤yb，即原问题的目标值小于对偶问题的目标值定理3（无界性）若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。若原（对偶）问题有可行解,对偶（原）问题无可行解，则原（对偶）问题一定无界；注:此定理可以判定解的情况第20页，共37页，2023年，2月20日，星期日定理4（可行解是最优解的性质）

定理5（强对偶定理）设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时，X*与Y*是最优解。若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等综合上述结论得原问题与对偶问题的解的关系一般是：cx≤yb第21页，共37页，2023年，2月20日，星期日

对偶问题有最优解无界无可行解原有最优解一定不可能不可能问无界不可能不可能一定题无可行解不可能可能可能原问题与对偶问题解的对应关系由原问题与对偶问题的解的关系可以判定线性规划的解。第22页，共37页，2023年，2月20日，星期日例4已知线性规划问题

Maxz=x1+x2S.t.–x1+x2+x3≤2

–

2x1+x2

–x3≤1xi≥0(i=1,2,3)

Minw=2y1+y2S.t.–y1

–2y2≥1①y1+y2≥1②

y1

–y2≥0③

y1,y2≥0应用如上关系求解线性规划问题试用对偶理论证明上述规划问题无最优解。由第一约束条件可知对偶问题无可行解，则原问题的解无界或无可行解，由于原问题存在可行解，所以解无界。表2：原问题与对偶问题解的对应关系对偶问题有最优解无界无可行解原有最优解一定不可能不可能问无界不可能不可能一定题无可行解不可能可能可能[解]该问题存在可行解，如X=(0，0，0)；其对偶问题为：对偶问题无可行解第23页，共37页，2023年，2月20日，星期日定理6（互补松弛定理）在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。注：证明过程参见教材59页性质5证明第24页，共37页，2023年，2月20日，星期日讨论:互补松弛定理也称松紧定理，它描述了线性规划达到最优时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束松紧之间的对应关系。当线性规划问题达到最优时，我们不仅同时得到了原问题和对偶问题的最优解，而且也还得到了变量和约束之间的一种对应关系。互补松弛定理即揭示了这一点。第25页，共37页，2023年，2月20日，星期日1.如果原问题的某一约束为紧约束（严格等式:松弛变量为零），该约束对应的对偶变量应大于或等于零；2.如果原问题的某一约束为松约束（严格不等式:松弛变量大于零），则对应的对偶变量必为零；3.如果原问题的某一变量大于零该变量对应的对偶约束必为紧约束(严格等式)；4.如果原问题的某一变量等于零，该变量对应的对偶约束可能是紧约束(严格等式)，也可能是松约束(严格不等式)。线性规划达到最优时的关系第26页，共37页，2023年，2月20日，星期日例5已知线性规划问题

MinS=2x1+3x2+5x3+2x4+3x5

S.t.x1+x2+2x3+x4+3x5≥4

2x1–x2+3x3+x4+x5≥3xi≥0(i=1,2,3,4,5)2＝21/5＜317/5＜57/5＜23=3解：写出对偶问题为：

MaxZ=4y1+3yS.t.y1+2y2≤2①y1–y2≤3②

2y1+3y2≤5③y1+y2≤2④

3y1+y2≤3⑤

y1,y2≥0又例:应用如上关系求解线性规划问题已知对偶问题的最优解为y1=4/5,y2=3/5,试应用对偶理论求解原问题。x2=0x3=0x4=0等号又因y1,y2

＞0，故原问题的两个约束必为紧约束，即x1+3x5=42x1+x5=3解得：x1=x5=1。maxZ=5=minS=5得原问题的最优解X*=(1,0,0,0,1)minS=5第27页，共37页，2023年，2月20日，星期日

Max.Z=2x1+4x2+x3+x4

s.t.x1+3x2+x4≤82x1+x2≤6x2+

x3+x4≤6x1+

x2+x3≤9xj≥0（j=1,2,3,4）附练习答案：y1=4/5,y2=3/5,y3=1,y4=0已知原问题的最优解为:X*=(2,2,4,0)T，试根据互补松弛定理解出其对偶问题的最优解。线性规划问题的对偶问题为：

Min.Z=8y1+6y2+6y3+9y4

s.t.y1+2y2+y4≥23y1+y2+

y3+y4≥4y3+y4≥1y1

+y3≥1yj≥0（j=1,2,3,4）练习：已知线性规划问题为：第28页，共37页，2023年，2月20日，星期日④为严格不等式，由互补松弛定知，必有y4=0；

Max.Z=2x1+4x2+x3+x4

s.t.x1+3x2+x4≤82x1+x2≤6x2+

x3+x4≤6x1+

x2+x3≤9xj≥0（j=1,2,3,4）①8=8②6=6③6=6④8<9解之，有：y1=4/5,y2=3/5,y3=1，y4=0答案：因为原问题的最优解为:X*=(2,2,4,0)T：又因x1,x2,x3＞0，故对偶问题的前三个约束必为紧约束线性规划问题的对偶问题为：

Min.Z=8y1+6y2+6y3+9y4

s.t.y1+2y2+y4≥23y1+y2+

y3+y4≥4y3+y4≥1y1

+y3≥1yj≥0（j=1,2,3,4）

y1+2y2=23y1+y2+

y3=4y3=1等号第29页，共37页，2023年，2月20日，星期日（1）写出对偶问题；（2）已知原问题的最优解为X*=（2，0，1，1）T，求对偶问题的最优解。已知线性规划问题第30页，共37页，2023年，2月20日，星期日定理7结论：用单纯形法求解线性规划时，迭代的每一步在得到原问题一个基本可行解的同时，其：

线性规划原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这两个解代入各自的目标数中有z=w。注：证明过程参见教材60页性质6证明检验数行的-(cj-zj)值是其对偶问题的一个基本解yi

；第31页，共37页，2023年，2月20日，星期日用单纯形法同时求解原问题和对偶问题

原问题是：

maxZ=2x1+x25x2≤15

6x1+2x2≤24x1+x2≤5

x1,x2≥0原问题的标准型是：

maxZ=2x1+x2+0x3+0x4

+0x5

5x2

+x3=156x1+2x2

+x4=24x1+x2

+x5=5

xi≥0第32页，共37页，2023年，2月20日，星期日

Cj比值CBXBb检验数jx1x2x3x4x52100015051002462010511001x3x4x5000021000

maxZ=2x1+x2+0x3+0x4

+0x5

5x2

+x3

=15

6x1+2x2

+x4

=24x1+x2

+x5

=5

xi

≥0-24/6=45/1=5原问题变量原问题松驰变量对偶问题剩余变量y4、y5对偶问题变量y1、y2、y3得原问题可行解:X=(0,0,15,24,5)T对偶问题解:Y*=(0,0,0,-2,-1)T检验数行的－

(cj-zj)值是其对偶问题的一个基本解yi

；第33页，共37页，2023年，2月20日，星期日

检验数j1505100411/301/60102/30-1/61x3x1x5020-801/30-1/303121.5得原问题可行解:X=(4,0,15,0,1)T，此时Z=8同时得对偶问题基础解:Y*=(0,1/3,0,0,-1/3)T，W=8对偶问题剩余变量y4、y5对偶问题变量y1、y2、y3原问题变量原问题松驰变量检验数行的-(cj-zj)值是其对偶问题的一个基本解yi

；第34页，共37页，2023年，2月20日，星期日变换单纯形表Cj比值CBXBb检验数