第2章线性规划的对偶问题

第二章线性规划的对偶问题习题2.1写出下列线性规划问题的对偶问题(1)maxz＝10x1＋x2＋2x3(2)maxz＝2x1＋x2＋3x3＋x4st.x1＋x2＋2x3≤10st.x1＋x2＋x3＋x4≤54x1＋x2＋x3≤202x1－x2＋3x3＝－4x j ≥0（j＝1,2,3）x1－x3＋x4≥1xj≥0（j＝1,2,3,4）其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。

2.5考虑线性规划问题maxz＝2x1＋4x2＋3x3st.3x1＋4x2＋2x3≤602x1＋x2＋2x3≤40x 1＋3x2＋2x3≤80xj≥0（j＝1,2,3）（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；仅供个人学习参考（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。

2.6已知线性规划问题maxz＝10x1＋5x2st.3x1＋4x2≤95x1＋2x2≤8xj≥0（j＝1,2）（1）给出a，b，c，d，e，f，g的值或表达式；（2）指出原问题是求目标函数的最大值还是最小值；（3）用a+?a，b+?b分别代替a和b，仍然保持上表是最优单纯形表，求?a，?b满足的范围。

仅供个人学习参考仅供个人学习参考2.9某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。

该厂现有工人100人，每月白坯纸供应量为30000千克。

已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或日记本30打，或练习本30箱。

已知原材料消耗为：每捆原稿纸用白坯纸310千克，每打日记本用白坯纸340千克，每箱练习本用白坯纸380千克。

又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生产一箱练习本获利1元。

试确定：（1）现有生产条件下获利最大的方案；（2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？2.10某厂生产甲、乙两种产品，需要A 、B 两种原料，生产消耗等参数如下表（表中2.12试从经济上解释对偶问题及对偶变量的含义。

习题二2.1 写出下列线性规划问题的对偶问题(1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤54x1＋x2＋x3≤20 2x1－x2＋3x3＝－4x j≥0 （j＝1,2,3）x1－x3＋x4≥1x1，x3≥0，x2，x4无约束(3) min z ＝3x1＋2 x2－3x3＋4x4(4) min z ＝－5 x1－6x2－7x3st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤202x1－3x2－7x3 －4x4＝2＝x1－x2－x3＝－5 x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束2.2 已知线性规划问题max z＝CX，AX=b，X≥0。

分别说明发生下列情况时，其对偶问题的解的变化：（1）问题的第k个约束条件乘上常数λ（λ≠0）；（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为max z＝λCX（λ≠0）；'x代换。

（4）模型中全部x1用312.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4st. x1＋2x2＋x4≥33x1＋x2＋x3＋x4≥6x3 ＋x4＝2x1 ＋x3 ≥2x j≥0（j＝1,2,3,4）(1) 写出其对偶问题；(2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。

2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量st. 2x1 ＋x3＋x4≤8 y12x1＋2x2＋x3＋2x4≤12 y2x j≥0（j＝1,2,3,4）对偶问题的最优解y1*=4；y2*=1，试对偶问题的性质，求出原问题的最优解。

2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3st. 3x1＋4 x2＋2x3≤602x1＋x2＋2x3≤40x1＋3x2＋2x3≤80x j≥0 （j＝1,2,3）４７４８（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。

2.1 写出线性规划问题的对偶问题，并进一步写出其对偶问题的对偶问题(a) min z=2x1+2x2+4x3(b) max z=5x1+6x2+3x3s.t. x1+3x2+4x3≥2 s.t. x1+2x2+2x3=52x1+x2+3x3≤3 -x1+5x2-3x3≥3x1+4x2+3x3=5 4x1+7x2+3x3≤8x1, x2≥0, x3无约束x1无约束,x2≥0, x3≤0解：(a)对偶问题的原问题为max w=2y1+3y2+5y3s.t. y1+2y2+y3≤23y1+y2+4y3≤24y1+3y2+3y3=4y1≥0, y2≤0, y3无约束(b)原问题的对偶问题为min w=5y1+3y2+8y3s.t. y1-y2+4y3=52y1+5y2+7y3≥62y1-3y2+3y3≤3y1无约束, y2≤0, y3≥02.3 已知线性规划问题：max z=x1+x2s.t. -x1+ x2+ x3 ≤2-2x1+x2- x3 ≤1x1, x2, x3≥0试应用对偶理论证明上述线性规划问题最优解为无界。

解：原问题的对偶问题为min w=2y1+ y2s.t. -y1- 2y2 ≥12y1+ 5y2 ≥1y1- y2 ≥0y1, y2≥0由于约束条件3可得y1-y2 ≥0 →y1≥y2 →-y1≤-y2 且y2≥0所以-y1-2y2 ≤-3y2≤0 （1）由于约束条件1可得-y1- 2y2 ≥1 （2）（1）（2）不等式组无解所以其对偶问题无可行解,又知点X=(1,1,1)为原问题一个可行解,即原问题有可行解, 现在其对偶问题无可行解。

根据对偶理论性质3原问题无界.2.4 已知线性规划问题：max z=2x 1+4x 2+ x 3+x 4 s.t. x 1+ 3x 2 +x 4 ≤8 2x 1+ x 2 ≤6 x 2+ x 3 +x 4 ≤6 x 1+ x 2+ x 3 ≤9 x j ≥0 (j=1,…4)要求(a)写出其对偶问题;(b)已知原问题最优解X=(2,2,4,0),试根据对偶理论,直接求出对偶问题的最优解. 解:对偶问题: min w=8y 1+ 6y 2+6y 3+9 y 4 s.t. y 1+ 2y 2 +y 4 ≥2 3y 1+ y 2 + y 3 +y 4 ≥4 y 3+ y 4 ≥1 y 1 +y 3 ≥1 y 1, y 2,y 3, y 4≥0将最优解X=(2,2,4,0)代入原问题的约束条件得: x 1+ 3x 2 +x 4 =8 2x 1+ x 2 =6 x 2+ x 3 +x 4 =6 x 1+ x 2+ x 3 =8<9根据对偶理论性质5， 如果∑=<ni i j ij b xa 1ˆ，则0ˆ=i y 。