線性规划的对偶问题.docVIP

第二章 线性规划的对偶问题 习题 2.1 写出下列线性规划问题的对偶问题 (1) max z ＝10x1＋ x2＋2x3 (2) max z ＝2x1＋ x2＋3x3＋ x4 st. x1＋ x2＋2 x3≤10 st. x1＋ x2＋ x3 ＋ x4 ≤5 4x1＋ x2＋ x3≤20 2x1－ x2＋3x3 ＝－4 xj ≥0 （j＝1,2,3） x1 － x3＋ x4≥1 x1，x3≥0，x2，x4无约束 (3) min z ＝3x1＋2 x2－3x3＋4x4 (4) min z ＝－5 x1－6x2－7x3 st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3 ≥15 x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3 ≤20 2x1－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）； （4）模型中全部x1用3代换。 2.3 已知线性规划问题 min z＝8x1＋6x2＋3x3＋6x4 st. x1＋2x2 ＋ x4≥3 3x1＋ x2＋ x3＋ x4≥6 x3 ＋ x4＝2 x1 ＋ x3 ≥2 xj≥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 y1 2x1＋2x2＋x3＋2x4≤12 y2 xj≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。 2.5 考虑线性规划问题 max z＝2x1＋4x2＋3x3 st. 3x1＋4 x2＋2x3≤60 2x1＋ x2＋2x3≤40 x1＋3x2＋2x3≤80 xj≥0 （j＝1,2,3） （1）写出其对偶问题 （2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解； （3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解； （4）比较（2）和（3）计算结果。 2.6 已知线性规划问题 max z＝10x1＋5x2 st. 3x1＋4x2≤9 5x1＋2x2≤8 xj≥0（j＝1,2） 用单纯形法求得最终表如下表所示： x1 x2 x3 x4 b x2 0 1 — x1 1 0 — 1 ?j=cj-Zj 0 0 — — 试用灵敏度分析的方法分别判断： （1）目标函数系数c1或c2分别在什么范围内变动，上述最优解不变； （2）约束条件右端项b1，b2，当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变； （3）问题的目标函数变为max z ＝12x1＋4x2时上述最优解的变化； （4）约束条件右端项由变为时上述最优解的变化。 2.7 线性规划问题如下： max z＝—5x1＋5x2＋13x3 st. —x1＋x2＋3x3≤20 ① 12x1＋4x2＋10x3≤90 ② xj≥0 （j＝1,2,3） 先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化？ 约束条件①的右端常数由20变为30； 约束条件②的右端常数由90变为70； 目标函数中x3的系数由13变为8； x1的系数列向量由（—1，12）T变为（0，5）T； 增加一个约束条件③：2x1＋3x2＋5x3≤50； 将原约束条件②改变为：10x1＋5x2＋10x3≤100。 2.8 用单纯形法求解某线性规划问题得到最终单纯形表如下： cj 基变量 50 40 10 60 S x1 x2 x3 x4 a c 0 1 1 6 b d 1 0 2 4 ?j=cj-Zj 0 0 e f g （1）给出a，b，c，d，e，f，g的值或表达式； （2）指出原问题是求目标函数的最大值还是最小值； （3）