线性规划的对偶问题

《线性规划的对偶问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性规划的对偶问题第二章线性规划的对偶问题习题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＝－4xj≥0（j＝1,2,3）x1－x3＋x4≥1x1，x3≥0，x2，x4无约束(3)minz＝3x1＋2x2－3x3＋4x4(4)minz＝－5x1－6x2－7x3st.x1－2x2＋3x3＋4x4≤3st.－x1＋5x2－3x3≥15x2＋

2、3x3＋4x4≥－5－5x1－6x2＋10x3≤202x1－3x2－7x3－4x4＝2＝x1－x2－x3＝－5x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束2.2已知线性规划问题maxz＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化：（1）问题的第k个约束条件乘上常数λ（λ≠0）；（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为maxz＝λCX（λ≠0）；（4）模型中全部x1用3代换。2.3已知线性规划问题minz＝8x1＋6x2＋3

3、x3＋6x4st.x1＋2x2＋x4≥33x1＋x2＋x3＋x4≥6x3＋x4＝2x1＋x3≥2xj≥0（j＝1,2,3,4）(1)写出其对偶问题；(2)已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。2.4已知线性规划问题minz＝2x1＋x2＋5x3＋6x4对偶变量st.2x1＋x3＋x4≤8y12x1＋2x2＋x3＋2x4≤12y2xj≥0（j＝1,2,3,4）其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。５１第二章线性规划的对偶问题2

4、.5考虑线性规划问题maxz＝2x1＋4x2＋3x3st.3x1＋4x2＋2x3≤602x1＋x2＋2x3≤40x1＋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）用单纯形法求得

5、最终表如下表所示：x1x2x3x4bx201—x110—1sj=cj-Zj00——试用灵敏度分析的方法分别判断：（1）目标函数系数c1或c2分别在什么范围内变动，上述最优解不变；（2）约束条件右端项b1，b2，当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；（3）问题的目标函数变为maxz＝12x1＋4x2时上述最优解的变化；（4）约束条件右端项由变为时上述最优解的变化。2.7线性规划问题如下：maxz＝—5x1＋5x2＋13x3st.—x1＋x2＋3x3≤20①12x1＋4x2＋10x3≤90②xj≥

6、0（j＝1,2,3）先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化？（1）约束条件①的右端常数由20变为30；５１第二章线性规划的对偶问题（1）约束条件②的右端常数由90变为70；（2）目标函数中x3的系数由13变为8；（3）x1的系数列向量由（—1，12）T变为（0，5）T；（4）增加一个约束条件③：2x1＋3x2＋5x3≤50；（5）将原约束条件②改变为：10x1＋5x2＋10x3≤100。2.8用单纯形法求解某线性规划问题得到最终单纯形表如下：cj基变量50401060Sx1x2x3x4ac01

7、16bd1024sj=cj-Zj00efg（1）给出a，b，c，d，e，f，g的值或表达式；（2）指出原问题是求目标函数的最大值还是最小值；（3）用a+Da，b+Db分别代替a和b，仍然保持上表是最优单纯形表，求Da，Db满足的范围。2.9某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每月白坯纸供应量为30000千克。已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸千克，每打日记本用白坯纸千克，每箱练习本用白

8、坯纸千克。又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生产一箱练习本获利1元。试确定：（1）现有生产条件下获利最大的方案；（2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？2.10某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如