第一章 线性规划1.1将下述线性规划问题化成标准形式1)min z=-3x1+4x2-2x3+5 x4 4x1-x2+2x3- x4 =-2st.x1+x2-x3+2 x4 ≤ 14-2x1+3x2+x3-x4 ≥ 2x1,x2,x3≥ 0,x4 无约束2)min z =2x1-2x2+3x3-x1+x2+x3=4st.-2x1+x2-x3≤ 6x1≤0 ,x2≥ 0,x3无约束1.2用图解法求解LP问题,并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。
1)min z=2x1+3x24x1+6x2≥6st 2x1+2x2≥4x1,x2≥02)max z=3x1+2x22x1+x2≤2st 3x1+4x2≥12x1,x2≥03)max z=3x1+5x26x1+10x2≤120st 5≤x1≤103≤x2≤84)max z=5x1+6x22x1-x2≥2st -2x1+3x2≤2x1,x2≥01.3找出下述LP问题所有基解,指出哪些是基可行解,并确定最优解(1)min z=5x1-2x2+3x3+2x4x1+2x2+3x3+4x4=7st 2x1+2x2+x3 +2x4=3x1,x2,x3,x4≥01.4分别用图解法与单纯形法求解下列LP 问题,并对照指出最优解所对应的顶点。
1)maxz =10x 1+5x 23x 1+4x 2≤9st 5x 1+2x 2≤8x 1,x 2≥02)maxz =2x 1+x 23x 1+5x 2≤15st 6x 1+2x 2≤24x 1,x 2≥01.5分别用大M 法与两阶段法求解下列LP 问题。
1)minz =2x 1+3x 2+x 3x 1+4x 2+2x 3≥8st 3x 1+2x 2 ≥6x 1,x 2 ,x 3≥02) max z =4x 1+5x 2+ x 3. 3x 1+2x 2+ x 3≥18 St. 2x 1+ x 2 ≤4x 1+ x 2- x 3=53) maxz = 5x 1+3x 2 +6x 3x 1+2x 2 -x 3 ≤ 18st 2x 1+x 2 -3 x 3 ≤ 16 x 1+x 2 -x 3=10x 1,x 2 ,x 3≥01231231231231234)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤⎧⎪-++≤⎪⎨++≥⎪⎪≥⎩1.6求下表中a ~l 的值。
c j →(a )-1200C B X B b x 1x 2x 3x 4x 50x 46(b )(c )(d )100x 51-13(e )01σj →(a )-1200(a )x 1(f )[(g )]2-11/200x 54(h )(I )11/21c j→(a)-1200C B X B b x1x2x3x4x5σj0-7(j)(k)(l)1.7某班有男生30人,女生20人,周日去植树。
根据经验,一天男生平均每人挖坑20个,或栽树30棵,或给25棵树浇水;女生平均每人挖坑10个,或栽树20棵,或给15棵树浇水。
问应怎样安排,才能使植树(包括挖坑、栽树、浇水)最多?请建立此问题的线性规划模型,不必求解。
1.8某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。
已知各种牌号糖果中A、B、C含量,原料成本,各种原料的每月限制用量,三种牌号糖果的单位加工费及售价如下表所示。
问该厂每月应生产这三种牌号糖果各多少千克,使该厂获利最大?试建立此问题的线性规划的数学模型。
甲乙丙原料成本(元/千克) 每月限量(千克)A ≥60%≥15% 2.00 2000B 1.50 2500C ≤20%≤60%≤50% 1.00 1200加工费(元/千克)0.50 0.40 0.30售价 3.40 2.85 2.251.9某商店制定7-12月进货售货计划,已知商店仓库容量不得超过500件,6月底已存货200件,以后每月初进货一次,假设各月份此商品买进售出单价如下表所示,问各月进货售货各多少,才能使总收入最多?请建立此问题的线性规划模型。
月份7 8 9 10 11 12买进单价28 24 25 27 23 23售出单价29 24 26 28 22 251.10某厂接到生产A、B两种产品的合同,产品A需200件,产品B需300件。
这两种产品的生产都经过毛坯制造与机械加工两个工艺阶段。
在毛坯制造阶段,产品A每件需要2小时,产品B每件需要4小时。
机械加工阶段又分粗加工和精加工两道工序,每件产品A 需粗加工4小时,精加工10小时;每件产品B需粗加工7小时,精加工12小时。
若毛坯生产阶段能力为1700小时,粗加工设备拥有能力为1000小时,精加工设备拥有能力为3000小时。
又加工费用在毛坯、粗加工、精加工时分别为每小时3元、3元、2元。
此外在粗加工阶段允许设备可进行500小时的加班生产,但加班生产时间内每小时增加额外成本4.,5元。
试根据以上资料,为该厂制订一个成本最低的生产计划。
1.11某公司有三项工作需分别招收技工和力工来完成。
第一项工作可由一个技工单独完成,或由一个技工和两个力工组成的小组来完成。
第二项工作可由一个技工或一个力工单独去完成。
第三项工作可由五个力工组成的小组完成,或由一个技工领着三个力工来完成。
已知技工和力工每周工资分别为100元和80元,他们每周都工作48小时,但他们每人实际的有效工作小时数分别为42和36。
为完成这三项工作任务,该公司需要每周总有效工作小时数为:第一项工作10000小时。
第二项工作20000小时,第三项工作30000小时。
又能招收到的工人数为技工不超过400人,力工不超过800人。
试建立数学模型,确定招收技工和力工各多少人。
使总的工资支出为最少(第二章 对偶与灵敏度分析2.1 写出以下线性规划问题的DLP 1)minz =2x 1+2x 2+4x 3 x 1+3x 2+4x 3 ≥2st2x 1+ x 2+3x 3 ≤3 x 1+4x 2+3x 3 =5x 1,x 2≥0,x 3无约束2)max z =5x 1+6x 2+3x 3 x 1+2x 2+2x 3 =5st -x 1+5x 2- x 3 ≥34x 1+7x 2+3x 3 ≤8x 1无约束,x 2≥0,x 3≤03)max z =c 1x 1+c 2x 2+c 3x 3a 11x 1+a 12x 2+a 13x 3 ≤b 1st a 21x 1+a 22x 2+a 23x 3 =b 2a 31x 1+a 32x 2+a 33x 3 ≥b 3x 1≥0,x 2≤0,x 3无约束2.2 对于给出的LP :minz =2x 1+3x 2+5x 3+6x 4 x 1+2x 2+3x 3+x 4 ≥2st -2x 1+x 2-x 3+3x 4 ≤-3 x j ≥0 (j=1,2,3,4)1)写出DLP ;2)用图解法求解DLP ;3)利用2)的结果及根据对偶性质写出原问题的最优解。
2.3 对于给出LP :maxz =x 1+2x 2+x 3 x 1+ x 2- x 3 ≤2st x 1- x 2+ x 3 =12x 1+ x 2+ x 3 ≥2x 1≥0, x 2≤0,x 3无约束1)写出DLP ;2)利用对偶问题性质证明原问题目标函数值Z≤12.4 已知LP :max z =x 1+x 2-x 1+ x 2+ x 3 ≤2st -2x 1+ x 2- x 3 ≤1 x j ≥0试根据对偶问题性质证明上述线性问题目标函数值无界。
2.5 给出LP :maxz =2x 1+4x 2+x 3+x 4 x 1+ 3x 2 +x 4 ≤82x 1+ x 2 ≤6st. x 2 + x 3+ x 4≤6x 1+ x 2 + x 3 ≤9 x j ≥01)写出DLP ;2)已知原问题最优解X =(2,2,4,0),试根据对偶理论,直接求出对偶问题的最优解。
2.6 用对偶单纯形法求解下列线性规划问题1)minz =4x 1+12x 2+18x 3x 1 +3x 3 ≥3st 2 x 2+2x 3 ≥5 x j ≥0 (j=1,2,3)1231231231232)min 524324.63510,,0z x x x x x x st x x x x x x =++++≥⎧⎪++≥⎨⎪≥⎩2.7 考虑如下线性规划问题minz =60x 1+40x 2+80x 33x 1+2x 2+ x 3 ≥2st 4x 1+ x 2+3x 3 ≥42x 1+2x 2+2x 3 ≥3 x j ≥01)写出DLP ;2)用对偶单纯形法求解原问题;3)用单纯形法求解其对偶问题;4)对比以上两题计算结果。
2.8 已知LP :maxz =2x 1-x 2+x 3x 1+ x 2+ x 3≤6st -x 1+2x 2 ≤4x 1,x 2,x 3≥01)用单纯形法求最优解2)分析当目标函数变为maxz =2x 1+3x 2+x 3时最优解的变化;3)分析第一个约束条件右端系数变为3时最优解的变化。
2.9 给出线性规划问题maxz =2x 1+3x 2+x 31/3x 1+1/3x 2+1/3x 3≤1st 1/3x 1+4/3x 2+7/3x 3≤3x j≥0用单纯形法求解得最终单纯形表如下cj→2310C B X BB x 1x 2x 3x 4X 52x 1110-14-13x 22012-11σj-3-5-1试分析下列各种条件下,最优解(基)的变化: 1)目标函数中变量x 3的系数变为6;2)分别确定目标函数中变量x 1和x 2的系数C 1、C 2在什么范围内变动时最优解不变;3)约束条件的右端由1变为 2;332.10 某厂生产甲、乙两种产品,需要A 、B 两种原料,生产消耗等参数如下表(表中的消耗系数为千克/件)。
产品原料甲乙可用量(千克)原料成本(元/千克)A 24160 1.0B 321802.0销售价(元)1316(1)请构造数学模型使该厂利润最大,并求解。
(2)原料A 、B 的影子价格各为多少。
(3)现有新产品丙,每件消耗3千克原料A 和4千克原料B ,问该产品的销售价格至少为多少时才值得投产。
(4)工厂可在市场上买到原料A 。
工厂是否应该购买该原料以扩大生产?在保持原问题最优基的不变的情况下,最多应购入多少?可增加多少利润?3.5 某玩具公司分别生产三种新型玩具,每月可供量分别为1000、2000、2000件,它们分别被送到甲、乙、丙三个百货商店销售。
已知每月百货商店各类玩具预期销售量均为1500件,由于经营方面原因,各商店销售不同玩具的盈利额不同,见下表。
又知丙百货商店要求至少供应C 玩具1000件,而拒绝进A 玩具。