对偶问题
-
2023年3月2日发(作者：职工代表选举办法)第二章线性规划的对偶问题
习题
写出下列线性规划问题的对偶问题
1maxz＝10x1＋x2＋2x32maxz＝2x1＋x2＋3x3＋x4
st.x1＋x2＋2x3≤10st.x1＋x2＋x3＋x4≤5
4x1＋x2＋x3≤202x1－x2＋3x3＝－4
xj≥0j＝1,2,3x1－x3＋x4≥1
x1,x3≥0,x2,x4无约束
3minz＝3x1＋2x2－3x3＋4x44minz＝－5x1－6x2－7x3
st.x1－2x2＋3x3＋4x4≤3st.－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无约束
已知线性规划问题maxz＝CX,AX=b,X≥0;分别说明发生下列情况时,
其对偶问题的解的变化：
1问题的第k个约束条件乘上常数λλ≠0；
2将第k个约束条件乘上常数λλ≠0后加到第r个约束条件上；
3目标函数改变为maxz＝λCXλ≠0；
4模型中全部x1
用3
1
'x
代换;
已知线性规划问题minz＝8x1＋6x2＋3x3＋6x4
st.x1＋2x2＋x4≥3
3x1＋x2＋x3＋x4≥6
x3＋x4＝2
x1＋x3≥2
xj≥0j＝1,2,3,4
1写出其对偶问题；
2已知原问题最优解为x＝1,1,2,0,试根据对偶理论,直接求出对偶
问题的最优解;
已知线性规划问题minz＝2x1＋x2＋5x3＋6x4
对偶变量
st.2x1＋x3＋x4≤8y1
2x1＋2x2＋x3＋2x4≤12y2
xj≥0j＝1,2,3,4
其对偶问题的最优解y1=4；y2=1,试根据对偶问题的性质,求出原问题
的最优解;
考虑线性规划问题maxz＝2x1＋4x2＋3x3
st.3x1＋4x2＋2x3≤60
2x1＋x2＋2x3≤40
x1＋3x2＋2x3≤80
xj≥0j＝1,2,3
1写出其对偶问题
2用单纯形法求解原问题,列出每步迭代计算得到的原问题的解与互
补的对偶问题的解；
3用对偶单纯形法求解其对偶问题,并列出每步迭代计算得到的对偶
问题解及与其互补的对偶问题的解；
4比较2和3计算结果;
已知线性规划问题maxz＝10x1＋5x2
st.3x1＋4x2≤9
5x1＋2x2≤8
xj≥0j＝1,2
用单纯形法求得最终表如下表所示：
x1x2x3x4b
x201
—
14
3
x110
—
7
1
1
j=cj-Zj00
—
14
5
—
14
25
试用灵敏度分析的方法分别判断：
1目标函数系数c1
或c2
分别在什么范围内变动,上述最优解不变；
2约束条件右端项b1,b2
,当一个保持不变时,另一个在什么范围内变化,
上述最优基保持不变；
3问题的目标函数变为maxz＝12x1＋4x2
时上述最优解的变化；
4约束条件右端项由
8
9
变为
19
11
时上述最优解的变化;
线性规划问题如下：maxz＝—5x1＋5x2＋13x3
st.—x1＋x2＋3x3≤20①
12x1＋4x2＋10x3≤90②
xj≥0j＝1,2,3
先用单纯形法求解,然后分析下列各种条件下,最优解分别有什么变化
（1）约束条件①的右端常数由20变为30；
（2）约束条件②的右端常数由90变为70；
（3）目标函数中x
3
的系数由13变为8；
（4）x
1
的系数列向量由—1,12T变为0,5T；
（5）增加一个约束条件③：2x1＋3x2＋5x3≤50；
（6）将原约束条件②改变为：10x1＋5x2＋10x3≤100;
用单纯形法求解某线性规划问题得到最终单纯形表如下：
c
j基变量
50401060
S
x1x2x3x4
ac0116
bd1024
j=c
j-Zj00efg
1给出a,b,c,d,e,f,g的值或表达式；
2指出原问题是求目标函数的最大值还是最小值；
3用a+a,b+b分别代替a和b,仍然保持上表是最优单纯形表,求a,b
满足的范围;
某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品;
该厂现有工人100人,每月白坯纸供应量为30000千克;已知工人的劳动生
产率为：每人每月可生产原稿纸30捆,或日记本30打,或练习本30箱;已
知原材料消耗为：每捆原稿纸用白坯纸
3
10
千克,每打日记本用白坯纸
3
40
千
克,每箱练习本用白坯纸
3
80
千克;又知每生产一捆原稿纸可获利2元,生产
一打日记本获利3元,生产一箱练习本获利1元;试确定：
1现有生产条件下获利最大的方案；
2如白坯纸的供应数量不变,当工人数不足时可招收临时工,临时工工
资支出为每人每月40元,则该厂要不要招收临时工如要的话,招多少临时
工最合适
某厂生产甲、乙两种产品,需要A、B两种原料,生产消耗等参数如下
表表中的消耗系数为千克/件;
产品原料甲乙可用量千克原料成本元/千
克
A24160
B32180
销售价元1316
1请构造数学模型使该厂利润最大,并求解;
2原料A、B的影子价格各为多少;
3现有新产品丙,每件消耗3千克原料A和4千克原料B,问该产品的销
售价格至少为多少时才值得投产;
4工厂可在市场上买到原料A;工厂是否应该购买该原料以扩大生产在
保持原问题最优基的不变的情况下,最多应购入多少可增加多少利润
某厂生产A、B两种产品需要同种原料,所需原料、工时和利润等参数
如下表：
单位产品AB可用量千克
原料千克12200
工时小时21300
利润万元43
（1）请构造一数学模型使该厂总利润最大,并求解;
（2）如果原料和工时的限制分别为300公斤和900小时,又如何安排生产
（3）如果生产中除原料和工时外,尚考虑水的用量,设两A,B产品的单位
产品分别需要水4吨和2吨,水的总用量限制在400吨以内,又应如
何安排生产
复习思考题
试从经济上解释对偶问题及对偶变量的含义;
根据原问题同对偶问题之间的对应关系,分别找出两个问题变量之间、解
以及检验数之间的对应关系;
什么是资源的影子价格,同相应的市场价格之间有何区别,以及研究影子
价格的意义;
试述对偶单纯形法的计算步骤,它的优点及应用上的局限性;
将a
ij,b,c的变化分别直接反映到最终单纯形表中,表中原问题和对偶问
题的解各自将会出现什么变化,有多少种不同情况以及如何去处理;
判断下列说法是否正确
a任何线性规划问题存在并具有唯一的对偶问题；
b对偶问题的对偶问题一定是原问题；
c根据对偶问题的性质,当原问题为无界解时,其对偶问题无可行解,反之,
当对偶问题无可行解时,其原问题具有无界解；
d若某种资源的影子价格等于k,在其它条件不变的情况下,当该种资源增
加5个单位时,相应的目标函数值将增大5k；
e应用对偶单纯形法计算时,若单纯形表中某一基变量x
i<0,又xi所在行的
元素全部大于或等于零,则可以判断其对偶问题具有无界解；
f若线性规划问题中的bi,c,值同时发生变化,反映到最终单纯形表中,不
会出现原问题与对偶问题均为非可行解的情况；
g在线性规划问题的最优解中,如某一变量x
j为非基变量,则在原来问题中,
无论改变它在目标函数中的系数c
j或在各约束中的相应系数aij,反映到最
终单纯形表中,除该列数字有变化外,将不会引起其它列数字的变化;