单纯形法的灵敏度分析与对偶

更新时间:2023-10-15 13:56:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

第三章 单纯形法的灵敏度分析与对偶

1、对偶单纯形法解最大化线性规划问题时,每次迭代要求单纯形表中 ( ) A.b列元素不小于零 B.检验数都大于零 C.检验数都不小于零 D.检验数都不大于零

2、关于线性规划的原问题和对偶问题,下列说法正确的是 ( ) A.若原问题为元界解,则对偶问题也为无界解

B.若原问题无可行解,其对偶问题具有无界解或无可行解 c.若原问题存在可行解,其对偶问题必存在可行解 D.若原问题存在可行解,其对偶问题无可行解

3、下面哪些不是线性规划问题的标准形式所具备的( ) A 所有的变量必须是非负的 B 所有的约束条件(变量的非负约束除外)必须是等式 C 添加新变量时,可以不考虑变量的正负性 D 求目标函数的最小值

4、已知线性规划问题 Max Z=4X1+7X2+2X3 X1+2X2+X3 ≤10 S.t 2X1+3X2+3X3≤10 X1,X2,X3 ≥0

应用对偶理论证明该问题最优解的目标函数值不大于25

5、已知线性规划问题max Z=3x1+4x2+x3 -x1+2x2+3x3≤6 S.t -3x1+x2-4x3≤7 x1,x2,x3 ≥0

利用对偶理论证明其目标函数值无界

6、写出下列线性规划问题的对偶问题

maxZ?3x1?x2?4x3?6x1?3x2?5x3?25?S?t??3x1?4x2?5x3?20?x?0(j?1,2,3)?j

7、已知线性规划

maxz?3x1?4x2?x3?x1?2x2?x3?10??2x1?2x2?x3?16?x?0,j?1,2,3?j

*TX?(6,2,0)的最优解为,试利用互补松弛定理,求对偶问题的最优解。

8、已知线性规划问题

max z?2x1?x2?5x3?6x4?2x1?x3?x4?8?s..t?2x1?2x2?x3?2x4?12?x?0, j?1,2,3,4?j

**y?4y?1,试用对偶理论求解原问题的最优解。

其对偶问题的最优解为1、2

9、用对偶单纯形法求解

min ??2x1?3x2?4x3?x1?2x2?x3?3?s..t?2x1?x2?3x3?4?x,x,x?0?123

10、有线性规划如下:

max z??5x1?5x2?13x3??x1?x2?3x3?20 ①?s..t?12x1?4x2?10x3?90 ②?x,x,x?0?123

先用单纯形法求出最优解,再分析以下各种条件下,最优解分别有什么变化: (1)约束条件①的右端常数由20变为30; (2)约束条件②的右端常数由90变为85; (3)目标函数中(4)(5)

x3的系数由13变为8;

x1的系数列向量由[-1, 12]T变为[0, 5]T;

x1和x2的系数列向量由[-1, 12]T 、[1, 4]T变为[0, 5]T 、[2, 1]T;

(6)增加一个约束条件③(7)将约束条件②改变为

2x1?3x2?5x3?50;

10x1?5x2?10x3?100。

**zt?011、试分析当参数变化时,(t)的变化,其中z是下述线性规划的最优目标函数值。

max z(t)?(3?2t)x1?(5?t)x2?x1?4?2x?12?s.t.?2?3x1?2x2?18??x1,x2?0

12、某个求最大值的线性规划问题的最优单纯形表如下,其中

x4、x5为松弛变量。 x4 3 -1 -3 b 2 4 x1 0 1 0 x2 -1 -1 -3 x3 1 0 0 x5 1 0 -1 ?j (1)写出该问题的最优解;

(2)当

?c3为何值时,其对偶问题无解?

13、已知线性规划

max z?x1?2x2??2x1?x2?2??x?2x?7?2s..t?1?x1?3??x1,x2?0

的最优单纯形表为

CB 2 1 0 XB b 5 3 3 x1 0 1 0 0 ?1x2 1 0 0 0 x3 0 0 1 0 x4 1/2 0 -1/2 -1 x5 1/2 1 3/2 -2 x2 x1 x3 ?j(1)写出最优基矩阵B及其逆矩阵B (2)写出其对偶问题; (3)给出对偶问题的最优解;

14、已知线性规划

maxz?6x1?2x2?12x3?4x1?x2?3x3?24?s..t?2x1?6x2?3x3?30?x,x,x?0?123的最优单纯形表为

cj 6 2 12 0 0 CB XB b x1 x2 x3 s1 s2 12 0 x3 s2 8 6 4/3 -2 -10 1/3 5 -2 1 0 0 1/3 -1 -4 0 1 0 ?j其中,

s1、s2分别为第1、2个约束的松弛变量。

(1)求出最优基不变的(2)求出最优解不变的

b2变化范围; c3变化范围;

(3)在原问题中增加约束条件

15、化下列线性规划为标准形 max z=2x1+2x2-4x3 x1 + 3x2-3x3 ≥30 x1 + 2x2-4x3 ≤80 x1、x2≥0,x3无限制

x1?2x2?2x3?12,求最优解。

16、将下述线性规划问题化成标准形式。

(1)maxz??3x1?4x2?2x3?5x4?4x1?x2?2x3?x4??2?x?x?x?2x?14?1234st.???2x1?3x2?x3?x4?2??x1,x2,x3?0,x4无约束

17、用单纯形法求解 max z=50x1+100x2 x1 + x2 ≤300 2x1 + x2≤400 x2≤250 x1、x2≥0

?2?minz?2x1?2x2?3x3??x1?x2?x3?4?st.??2x1?x2?x3?6?x?0,x?0,x无约束23?1

18、用单纯形法求解 max Z=2x1+x2 -x1 + x2≤5 2x1-5x2≤10 x1、x2≥0

19、用单纯形法(大M法)求解下列线性规划 max z =3x1-2x2-x3 x1 -2x2 + x3 ≤ 11 -4x1 + x2 + 2x3 ≥ 3 -2x1 + x3 = 1 x1、x2、x3≥0

20、用单纯形法(大M法)求解下列线性规划 max z=3x1+2x2 2x1+ x2 ≤ 2 3x1 +4x2 ≥12 x1、x2≥0

21、用单纯形法求解下述LP问题。

22、用单纯形法求解下述LP问题。

23、用单纯形法求解下述LP问题。

24、用单纯形法求解下述线性规划

25、用单纯形法求解下述LP问题。

26、用大M法求解下述LP问题

27、求解下述LP问题

28、写出下列线性规划问题的对偶问题 max z=2x1+2x2-4x3 x1 + 3x2 + 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2,x3≥0

29、写出下列线性规划问题的对偶问题 min z=2x1+8x2-4x3 x1 + 3x2-3x3 ≥30 -x1 + 5x2 + 4x3 = 80 4x1 + 2x2-4x3≤50 x1≤0、x2≥0,x3无限制

30、已知线性规划问题,写出其对偶问题: (1)

maxz?10x1?24x2?20x3?20x4?25x5?x1?x2?2x3?3x4?5x5?19?s.t.?2x1?4x2?3x3?2x4?x5?57?xj?0?(j?1,2,3,4,5) (2)

minz?8x1?6x2?3x3?6x4?x1?2x2?x4?3? ?3x1?x2?x3?x4?6?s.t.?x3?x4?2?x?x3?2?1?0j?1,2,3,4)?xj?(31、已知线性规划问题 max z=x1+2x2+3x3+4x4 x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2,x3,x4≥0

其对偶问题的最优解为y1*=6/5,y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。

32、已知线性规划 Max Z=3X1+4X2+X3 X1+2X2+ X3≤10 2X1+2X2+X3≤16 Xj≥0,j=1,2,3

的最优解为X=(6,2,0),试利用互补松弛定理,求对偶问题的最优解。

33、已知线性规划问题

?T

其对偶问题的最优解为

34、已知线性规划问题:

其最优解为 x1??5,x2?0,x3??1、

,试用对偶理论求解原问题的最优解。

minz?2x1?x2?2x3??x1?x2?x3?4?s.t.??x1?x2?kx3?6?x?0,x?0,x无约束23?1

(a)求k的值;

(b)写出并求出其对偶问题的最优解。

35、已知线性规划问题:

maxz?x1?2x2?3x3?4x4?x1?2x2?2x3?3x4?20?s.t.?2x1?x2?3x3?2x4?20?x,x,x,x?0?1234y y2?0.2。 1?1.2其对偶问题的最优解为,

试根据对偶理论求出原问题的最优解。

36、已知线性规划问题:

maxz?x1?x2??x1?x2?x3?2?st.??x1?x2?x3?1?x,x,x?0?123

试根据对偶问题性质证明上述线性规划问题目标函数值无界。

37、用对偶单纯形法求下面问题 Min f(X)=4X1+6X2 X1+2X2≥80 S.t. 3X1+X2≥75 X1,X2≥0

38、用对偶单纯形法求解下列线性规划 min z=4x1+2x2+6x3 2x1 +4x2 +8x3 ≥24 4x1 + x2 + 4x3≥8 x1、x2,x3≥0

39、用对偶单纯形法求解 Min W=2X1+3X2+4X3 X1+2X2+X3≥3 S.t. 2X1-X2+3X3≥4 X1,X2,X3≥0

40、用对偶单纯形法求解下列线性规划问题。

?1?minz?4x1?12x2?18x3?2?minz?5x1?2x2?3x3?x1?3x3?3?st.?2x2?2x3?5?x,x,x?0?123

41、已知2-45表为求解某线性规划问题的最终单纯形表,表中x4 , x5为松弛变量,问题的约束为≤形式。 表2-45 最终单纯形表

z X3 X1

(1)写出原线性规划问题; (2)写出原问题的对偶问题;

(3)直接由原问题的最终单纯形表写出对偶问题的最优解。

42、设某线性规划问题的初始单纯形表和最优单纯形表分别为

Cj CB XB 5 x1 4 x2 3 x3 0 x4 0 b x5 z 1 x1 0 0 1 x2 4 x3 0 x4 4 x5 2 RHS ?3x1?x2?2x3?4?st.?6x1?3x2?5x3?10?x,x,x?0?123

1/2 1 -1/2 0 1/2 0 5/2 -1/6 1/3 5/2 0 0

Cj CB 4 5 x4 x5 -z 1 2 5 1 1 4 1 4 3 1 0 0 0 1 0 60 80 0 5 XB x2 x1 -z x1 0 1 0 4 x2 1 0 0 3 x3 -2 3 -4 0 x4 2 -1 -3 0 b x5 -1 1 -1 40 20 -260 问:(1)c3在什么范围内变化,表中最优解不变?(2)c3从3变为8,求新的最优解

43、初始单纯形表和最优单纯形表分别如表,试分析使最优基不变的b3的变化范围。(初始单纯形表)

Cj CB 0 0 0 XB x3 x4 x5 -z 5 x1 1 2 1 5 4 x2 3 1 1 4 0 x3 1 0 0 0 0 x4 0 1 0 0 0 b x5 0 0 1 0 90 80 45 0 (最优单纯形表)

Cj CB 0 5 4

44、已知线性规划问题:

XB x3 x1 x2 -z 5 x1 0 1 0 0 4 x2 0 0 1 0 0 x3 1 0 0 0 0 x4 2 1 -1 -1 0 b x5 -5 -1 2 -3 25 35 10 -215 maxz?2x1?x2?x3 ?x1?x2?x3?6?st.??x1?2x2?4?x,x,x?0?123先用单纯形法求出最优解,再分析在下列条件单独变化的情况下最优解的变化。 (1)目标函数变为

maxz?2x1?3x2?x3

?6??3?????4??4?????(2)约束右端项由变为?;

(3)增添一个新的约束条件

45、某厂生产A,B,C三种产品,其所需劳动力、材料等有关数据见表2-46。要求:(1)确定利润最大的产品生产计划;(2)产品A的利润在什么范围内变动时,上述最优计划不变;(3)如果设计一种新产品D,单件劳动力消耗为8单位,材料消耗为2单位,每件可获利3元,问该种产品是否值得生产?(4)如果劳动力数量不增,材料不足时可从市场购买,每单位0.4元。问该厂要不要购进原材料扩大生产,以购多少为宜。(5)由于某种原因该厂决定暂停A产品的生产,试重新确定该厂的最优生产计划。 表2-46 产品单位利润及资源消耗 消耗定额产品 A B C 资源 劳动力 材料 产品利润(元/件)

6 3 5 3 4 5 3 1 4 45 30 可用量(单位) ?x1?x3?2。

本文来源:https://www.bwwdw.com/article/n0hf.html

微信扫码分享

《单纯形法的灵敏度分析与对偶.doc》
将本文的Word文档下载到电脑,方便收藏和打印
推荐度:
点击下载文档
下载全文
范文搜索
下载文档
Top