题目
五、 给出线性规划问题:(20)Max z=2x1+4x2+x3+x4 x1+3x2+x4≤8 2x1+x2≤6 x2+x3+x4≤6 x1+x2+x3≤9 xj≥0(j=1,2,3,4) 要求:(1)写出其对偶问题;(2)已知原问题最优解为 x1+3x2+x4≤8 2x1+x2≤6 x2+x3+x4≤6 x1+x2+x3≤9 xj≥0(j=1,2,3,4) X x1+3x2+x4≤8 2x1+x2≤6 x2+x3+x4≤6 x1+x2+x3≤9 xj≥0(j=1,2,3,4) =(2,2,4,0),试根据对偶理论,直接求出对偶问题的最优解。
五、 给出线性规划问题:(20)
Max z=2x1+4x2+x3+x4
要求:(1)写出其对偶问题;(2)已知原问题最优解为
X
=(2,2,4,0),试根据对偶理论,直接求出对偶问题的最优解。
题目解答
答案
解:(1)对偶问题为
Min
=8y1+6y2+6y3+9y4
(2)由互补松弛性可知:x1+x2+x3=8<9 为严格不等式 y4=0. 相反,其对偶问题的约束条件(1),(2),(3)的对偶变量值为非零(对偶问题的对偶即原问题),有
y1=4/5,y2=3/5,y3=1
即对偶问题的最优解为Y=(4/5,3/5,1,0)
解析
步骤 1：写出原问题的对偶问题
原问题是一个最大化问题，其约束条件为等式，变量非负。根据对偶理论，对偶问题是一个最小化问题，其约束条件为不等式，变量非负。对偶问题的变量对应原问题的约束条件，对偶问题的约束条件对应原问题的变量。
步骤 2：根据原问题的最优解求对偶问题的最优解
根据对偶理论中的互补松弛性，如果原问题的某个变量取值为0，则其对应的对偶问题的约束条件为严格不等式；如果原问题的某个变量取值为正，则其对应的对偶问题的约束条件为等式。利用这一点，可以求出对偶问题的最优解。
原问题是一个最大化问题，其约束条件为等式，变量非负。根据对偶理论，对偶问题是一个最小化问题，其约束条件为不等式，变量非负。对偶问题的变量对应原问题的约束条件，对偶问题的约束条件对应原问题的变量。
步骤 2：根据原问题的最优解求对偶问题的最优解
根据对偶理论中的互补松弛性，如果原问题的某个变量取值为0，则其对应的对偶问题的约束条件为严格不等式；如果原问题的某个变量取值为正，则其对应的对偶问题的约束条件为等式。利用这一点，可以求出对偶问题的最优解。