单纯形法的灵敏度分析与对偶
更新时间: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。
正在阅读:
单纯形法的灵敏度分析与对偶10-15
江苏省淮安市2014届高三5月信息卷物理试题 Word版含答案01-15
2014兰州事业单位成绩查询丨成绩排名丨面试时间(14)04-14
部编版六年级下学期数学强化训练练习期末模拟试卷 - 图文12-22
安徽华能龙头扶贫企业汇报材料20110605-30
新常态下法学实践教学远程互动平台应用研究12-29
【建筑施工】砼预制块安装施工组织设计06-02
我爱家乡的风景作文400字07-08
海尔空调1+5服务规范及重点回访内容04-14
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 对偶
- 灵敏度
- 单纯
- 分析
- 三年级奥数-逻辑推理(1)
- 2014中山大学博士生导师 - 图文
- 毛邓三调查报告模板—2015(2)
- 力控组态软件的OPC支持
- 充分挖掘资本市场资源保障资金供应
- 史上最全毛邓三复习资料
- 长三角征文终稿
- 小城镇建设工作会上的讲话
- 一级建造师《机电工程》第一章第二节练习题1
- 公司与员工协商一致解除劳动合同协议书
- 跨铁路施工方案
- 精密机械设计课程设计指导书 - 图文
- 户外素质拓展培训方案
- (改后14)新编数控铣实训报告黄妃学 - 图文
- 传承国粹文明,激发爱国
- 客货共线铁路单线空心桥墩环向温度应力分析
- 2018-2019学年最新小学语文S版四年级上册《绿叶的梦》教学设计-评奖教案
- 商场现场管理制度
- 爱情数字密码大全2018
- 新时期信访干部必须具备的素质和能力