题目
三、(20分) 已知以下线性规划问题,max z =10x1+5x2st. 3x1+4x2≤95x1+2x2≤8x1, x2≥0(4) 用单纯形法求解下列线性规划问题。(10分)(5) 写出上述线性规划问题的对偶问题。(4分)(6) 求解上述线性规划问题的对偶问题的最优解。(6分)
三、(20分) 已知以下线性规划问题,
max z =10x1+5x2
st. 3x1+4x2≤9
5x1+2x2≤8
x1, x2≥0
(4) 用单纯形法求解下列线性规划问题。(10分)
(5) 写出上述线性规划问题的对偶问题。(4分)
(6) 求解上述线性规划问题的对偶问题的最优解。(6分)
题目解答
答案
解:(1)首先,将问题化为标准型(4分)。加松弛变量x3,x4,得
其次,列出初始单纯形表,计算最优值(4分)。
由单纯形表一得最优解为x (1,3/ 2)T , z* 35/ 2.(2分)
(2)对偶问题为(4分):
min w =9y1+8y2
st. 3y1+5y2≥10
4y1+2y2≥5
y1, y2≥0
(3)用互补松弛地定理求出对偶问题的解为(6分,其中步骤4分,结果2分):
先化为标准型,则有
min w =9y1+8y2
st. 3y1+5y2 –y3 =10
4y1+2y2 –y4 =5
y1, y2,y3,y4≥0
根据互补松弛定理有,
x1*y3=0, x2*y4=0, x1>0, x2>0,
则有:y3=y4=0,带入对偶问题标准型则有
3y1+5y2 =10
4y1+2y2 =5
则有:y1=5/14 y2=25/14, minW=35/2.
解析
步骤 1：将问题化为标准型
为了使用单纯形法，我们需要将问题转化为标准形式。为此，我们引入松弛变量x3和x4，将不等式约束转化为等式约束。
步骤 2：列出初始单纯形表
根据标准形式，我们列出初始单纯形表，并计算最优值。
步骤 3：求解对偶问题
根据原问题的对偶理论，写出对偶问题，并求解其最优解。
步骤 4：使用互补松弛定理求解对偶问题的解
根据互补松弛定理，求解对偶问题的最优解。
为了使用单纯形法，我们需要将问题转化为标准形式。为此，我们引入松弛变量x3和x4，将不等式约束转化为等式约束。
步骤 2：列出初始单纯形表
根据标准形式，我们列出初始单纯形表，并计算最优值。
步骤 3：求解对偶问题
根据原问题的对偶理论，写出对偶问题，并求解其最优解。
步骤 4：使用互补松弛定理求解对偶问题的解
根据互补松弛定理，求解对偶问题的最优解。