第一范文网 - 专业文章范例文档资料分享平台

线性规划的对偶问题

来源:用户分享 时间:2025/7/11 18:55:03 本文由loading 分享 下载这篇文档手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:xxxxxxx或QQ:xxxxxx 处理(尽可能给您提供完整文档),感谢您的支持与谅解。

第二章 线性规划的对偶问题

第二章 线性规划的对偶问题

习题

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

(1) max z =10x1+ x2+2x3 (2) max z =2x1+ x2+3x3+ x4 st. x1+ x2+2 x3≤10 st. x1+ x2+ x3 + x4 ≤5

4x1+ x2+ x3≤20 2x1- x2+3x3 =-4 xj ≥0 (j=1,2,3) x1 - x3+ x4≥1

x1,x3≥0,x2,x4无约束

(3) min z =3x1+2 x2-3x3+4x4 (4) min z =-5 x1-6x2-7x3 st. x1-2x2+3x3+4x4≤3 st. -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 无约束

2.2 已知线性规划问题max z=CX,AX=b,X≥0。分别说明发生下列情况时,其对偶问题的解的变化:

(1)问题的第k个约束条件乘上常数λ(λ≠0);

(2)将第k个约束条件乘上常数λ(λ≠0)后加到第r个约束条件上; (3)目标函数改变为max z=λCX(λ≠0); (4)模型中全部x1用3x'1代换。

2.3 已知线性规划问题 min z=8x1+6x2+3x3+6x4

st. x1+2x2 + x4≥3

3x1+ x2+ x3+ x4≥6

x3 + x4=2

x1 + x3 ≥2

xj≥0(j=1,2,3,4)

(1) 写出其对偶问题;

(2) 已知原问题最优解为x*=(1,1,2,0),试根据对偶理论,直接求出对偶问题的最优解。

2.4 已知线性规划问题 min z=2x1+x2+5x3+6x4 对偶变量

st. 2x1 +x3+ x4≤8 y1 2x1+2x2+x3+2x4≤12 y2

xj≥0(j=1,2,3,4)

其对偶问题的最优解y1*=4;y2*=1,试根据对偶问题的性质,求出原问题的最优解。

47

第二章 线性规划的对偶问题

2.5 考虑线性规划问题 max z=2x1+4x2+3x3

st. 3x1+4 x2+2x3≤60

2x1+ x2+2x3≤40 x1+3x2+2x3≤80 xj≥0 (j=1,2,3)

(1)写出其对偶问题

(2)用单纯形法求解原问题,列出每步迭代计算得到的原问题的解与互补的对偶问题的解;

(3)用对偶单纯形法求解其对偶问题,并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解;

(4)比较(2)和(3)计算结果。

2.6 已知线性规划问题 max z=10x1+5x2

st. 3x1+4x2≤9

5x1+2x2≤8 xj≥0(j=1,2)

用单纯形法求得最终表如下表所示:

x2 x1 x1 0 1 0 x2 1 0 0 x3 x4 b ?j=cj-Zj 5 141— 75— 143 142 725— 14—3 21 试用灵敏度分析的方法分别判断: (1)目标函数系数c1或c2分别在什么范围内变动,上述最优解不变;

(2)约束条件右端项b1,b2,当一个保持不变时,另一个在什么范围内变化,上述最优基保持不变;

(3)问题的目标函数变为max z =12x1+4x2时上述最优解的变化;

(4)约束条件右端项由????时上述最优解的变化。 ???变为?2.7 线性规划问题如下: max z=—5x1+5x2+13x3 st. —x1+x2+3x3≤20 ①

12x1+4x2+10x3≤90 ②

?9??8??11??19?xj≥0 (j=1,2,3) 先用单纯形法求解,然后分析下列各种条件下,最优解分别有什么变化? (1) 约束条件①的右端常数由20变为30;

48

第二章 线性规划的对偶问题

(2) (3) (4) (5)

约束条件②的右端常数由90变为70; 目标函数中x3的系数由13变为8;

TT

x1的系数列向量由(—1,12)变为(0,5); 增加一个约束条件③:2x1+3x2+5x3≤50;

(6) 将原约束条件②改变为:10x1+5x2+10x3≤100。 2.8 用单纯形法求解某线性规划问题得到最终单纯形表如下:

cj a b 基变量 c d ?j=cj-Zj 50 x1 0 1 0 40 x2 1 0 0 10 x3 60 x4 1 2 f S 6 4 g 1 21 4e (1)给出a,b,c,d,e,f,g的值或表达式;

(2)指出原问题是求目标函数的最大值还是最小值;

(3)用a+?a,b+?b分别代替a和b,仍然保持上表是最优单纯形表,求?a,?b满足的范围。

2.9 某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人,每月白坯纸供应量为30000千克。已知工人的劳动生产率为:每人每月可生产原稿纸30捆,或日记本30打,或练习本30箱。已知原材料消耗为:每捆原稿纸用白坯纸坯纸

1040千克,每打日记本用白坯纸千克,每箱练习本用白3380千克。又知每生产一捆原稿纸可获利2元,生产一打日记本获利3元,生3产一箱练习本获利1元。试确定:

(1)现有生产条件下获利最大的方案;

(2)如白坯纸的供应数量不变,当工人数不足时可招收临时工,临时工工资支出为每人每月40元,则该厂要不要招收临时工?如要的话,招多少临时工最合适?

2.10 某厂生产甲、乙两种产品,需要A、B两种原料,生产消耗等参数如下表(表中的消耗系数为千克/件)。 产品原料 A B 销售价(元) 甲 2 3 13 乙 4 2 16 可用量(千克) 原料成本(元/千克) 160 180 1.0 2.0 (1)请构造数学模型使该厂利润最大,并求解。

49

第二章 线性规划的对偶问题

(2)原料A、B的影子价格各为多少。

(3)现有新产品丙,每件消耗3千克原料A和4千克原料B,问该产品的销售价格至少为多少时才值得投产。

(4)工厂可在市场上买到原料A。工厂是否应该购买该原料以扩大生产?在保持原问题最优基的不变的情况下,最多应购入多少?可增加多少利润?

2.11 某厂生产A、B两种产品需要同种原料,所需原料、工时和利润等参数如下表:

单位产品 原料(千克) 工时(小时) 利润(万元) A 1 2 4 B 2 1 3 可用量(千克) 200 300 (1) 请构造一数学模型使该厂总利润最大,并求解。

(2) 如果原料和工时的限制分别为300公斤和900小时,又如何安排生产? (3) 如果生产中除原料和工时外,尚考虑水的用量,设两A,B产品的单位产品

分别需要水4吨和2吨,水的总用量限制在400吨以内,又应如何安排生产?

复习思考题

2.12 试从经济上解释对偶问题及对偶变量的含义。

2.13 根据原问题同对偶问题之间的对应关系,分别找出两个问题变量之间、解以及检验数之间的对应关系。

2.14 什么是资源的影子价格,同相应的市场价格之间有何区别,以及研究影子价格的意义。

2.15 试述对偶单纯形法的计算步骤,它的优点及应用上的局限性。

2.16 将aij,b,c的变化分别直接反映到最终单纯形表中,表中原问题和对偶问题的解各自将会出现什么变化,有多少种不同情况以及如何去处理。 2.17 判断下列说法是否正确

(a)任何线性规划问题存在并具有唯一的对偶问题; (b)对偶问题的对偶问题一定是原问题;

(c)根据对偶问题的性质,当原问题为无界解时,其对偶问题无可行解,反之,当对偶问题无可行解时,其原问题具有无界解;

(d)若某种资源的影子价格等于k,在其它条件不变的情况下,当该种资源增加5个单位时,相应的目标函数值将增大5k;

(e)应用对偶单纯形法计算时,若单纯形表中某一基变量xi<0,又xi所在行的元素全部大于或等于零,则可以判断其对偶问题具有无界解;

(f)若线性规划问题中的bi,c,值同时发生变化,反映到最终单纯形表中,不会出

50

第二章 线性规划的对偶问题

现原问题与对偶问题均为非可行解的情况;

(g)在线性规划问题的最优解中,如某一变量xj为非基变量,则在原来问题中,无论改变它在目标函数中的系数cj或在各约束中的相应系数aij,反映到最终单纯形表中,除该列数字有变化外,将不会引起其它列数字的变化。

51

搜索更多关于: 线性规划的对偶问题 的文档
线性规划的对偶问题.doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
本文链接:https://www.diyifanwen.net/c7qfdw9usda6j6mw9r6xj_1.html(转载请注明文章来源)
热门推荐
Copyright © 2012-2023 第一范文网 版权所有 免责声明 | 联系我们
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ:xxxxxx 邮箱:xxxxxx@qq.com
渝ICP备2023013149号
Top