1.用图解法求解两个变量线性规划问题的最优解和最优值。
??
?
??≥≤+≤++=0
,153562st.32max 21212121x x x x x x x x z
,15/7)
2.用图解法求解以下线性规划问题,并指出哪个问题有惟一解、无穷多最优解、无界解或无可行解
???
??≥≥+≥++=0
,34312st.46min 2121212
1x x x x x x x x z
??
?
??≥≥+-≤++=0
,810
22st.84max 2121212
1x x x x x x x x z
无可行解
3.某公司从中心制造地点向分别位于城区北、东、南、西方向的分配点运送材料。该公司有26辆卡车,用于从制造地点向分配点运送材料。其中有9辆,每辆能装5吨的大型卡车,12辆每辆能装2吨的中型卡车和5辆每辆能装1吨的小型卡车。北、东、南、西四个点分别需要材料14吨、10吨、20吨、8吨。每辆卡车向各分配点送材料一次的费用如表2-7所示。建立运送材料总费用最小的线性规划模型。
表2-7 车辆运送一次的费用
解 设大、中、小型车分别用i 表示,则3,2,1=i ;东、南、西、北四个分点分别用j 表
示,则4,3,2,1=j ;向j 方向发出的i 型车数量为ij x
。
34
3332312423222114131211223815204255605075926380min x x x x x x x x x x x x Z +++++++++++=
???
?????
???
?
=≥≤+++≤+++≤+++≥++≥++≥++4,3,2,1,,0512982520251025.343332312423222114131211
342414332313322212
312111j i x x x x x x x x x x x x x x x x x x x x x x st ij
4.某工厂生产A 、B 、C 三种产品,现根据合同及生产状况制定5月份的生产计划。已知合同甲为:A 产品1000件,每件价格为500元,违约金为100元/每件;合同乙:B 产品500件,每件价格为400元,违约金为120元/每件;合同丙为:B 产品600件,每件价格为420元,违约金为130元/每件;C 产品600件,价格400元/每件,违约金为90元/每件。有关各产品生产过程所需工时以及原材料的情况如表2-8所示。试以利润为目标建立该工厂生产计划的线性规划模型。
表2-8 产品使用的原材料、加工工序、资源限制、成本
解 设工厂5月份为完成合同甲生产1x 件A 产品;为完成合同乙生产2x 件B 产品;为
完成合同丙生产3x 件 B 产品,4x 件C 产品。
292000
260325295290)1040220420210152()()104032201031015()10404203102103152(90)600(400130)600(420120)500(400)1000(500max 43214
32144332211-+++=+?+?+?++?-+?+?+?+?++-+?+?+?+?+?-?--+?--+?--+--=x x x x x x x x x x x x x x x x Z
??????????????≤≤
≤≤≤≤≤≤≤+++≤+++≤+++≤+++,
6000,6000,5000,1000080002)(34100004)(2360002332400023.43214321
4321432143214321x x x x x x x x x x x x x x x x x x x x st
5.某公司从事某种商品的经营,现欲制定本年度10至12月的进货及销售计划。已知该种商品的初始库存量为2000件,公司仓库最多可存放10000件,公司拥有的经营资金80万元,据预测,10至12月的进货及销售价格如表2-9所示。若每个月仅在1号进货1次,且要求年底时商品存量达到3000件,在以上条件下,建立该问题的线性规划模型,使公司获得最大利润?(注:不考虑库存费用)
表2-9 进货和销售价格
解 12,11,10,=i x i ,为每月购进的货物,12,11,10,=i y i 为每月销售的货物。
????????
?????????
=≥=≥=---+++--+++≤-++≤+≤≤--+++≤-++≤+≤++---++=12
,11,10,012,11,10,0 30002000 2000 2000 2000 100002000 100002000 100002000 80000989590.989590115100100max 121110101112111010111212101011111010111010111210101110121110121110121110i y i x y y y x x x y y x x x y y x x y x y y y x x x y x x x x x x st x x x y y y Z i i 年底存量限制
销量限制销量限制销量限制库容限制库容限制库容限制资金限制
6.某饲养场饲养动物出售,设每头动物每天至少需700g 蛋白质、30g 矿物质、100mg 维生素。现有五种饲料可供选用,各种饲料每公斤营养成分含量单价如表2-10所示。
表2-10
饲料所含的营养成分及价格
解 设各送这5钟饲料1x ,2x ,3x ,4x ,5x kg 。
???
??
?
?=≥++++≥++++≥++++++++=5,4,3,2,1,1008.022.05.0305.022.05.070018623.8.03.04.07.02.0min 54321543215432154321i x x x x x x x x x x x x x x x x st x x x x x Z i
7.某一企业家需要找人清理5间会议室、12张桌子和18个货架。今有两个临时工A 和B 可供该企业家雇佣。A 一天可清理1间会议室、3张桌子与3个货架;而B 一天可清理1间会议室、2张桌子与6个货架。A 的工资每天25元,B 每天22元。为了使成本最低,应雇佣A 和B 各多少天?(用线性规划图解法求解)
解:设雇佣A 和B 分别为y x ,天
????
?
?
?
≥≥+≥+≥++=为整数且y x y x y x y x y x st y x Z ,0;186312235.2225min
由图知A 点为最优解,联立方程:
??
?=+=+51223y x y x
解得: x =2, =y 3,即: Z min =25x +22y =25?2+22?3=116 因此,雇佣A 工人2天,B 工人3天。
8.某外贸公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。1月1日,公司拥有库存1000担杂粮,并有资金20000元。估计第一季度杂粮价格如表2-11所示。
表2-11 第一季度杂粮价格表
―货到付款‖。公司希望本季度末库存为2000担,建立该问题的线性规划模型使三个月总的获利最大。
解 设一月份买入1x 担,卖出'1x 担;二月份买入2x 担,卖出'
2x 担;三月份买入3x 担,卖出'
3x 担。
??
??
?????
????=≥=≥≥+-+-+-++-≤≤+-+-+-≤≤+-≤-+-+-=3,2,1,0;3,2,1,02000
100025.310.385.22000090.25000100010.385.22000005.3500010002000085.2.90.295.205.325.385.210.3max '
3
'32'21'1'2'1132'
21'1'1121'1
13'
32'21'1j x i x x x x x x x x x x x x x x x x x x x x x st x x x x x x Z j i
1.求下列线性规划问题的所有基解、基可行解、最优解
??
?
??≥=++=++++=0
,,6422
st.33max 321321321321x x x x x x x x x x x x z
解:由题意知:A= 1
111
2
4??
???=(1,2,3p p p ) b=26?? ?
?? c=(3,1,3)
(1)1B =(
1,2
p p ),︱1B ︳≠0,1B 是基,1x ,2x 是基变量,3x 是非基变量,令
3x =0,得1x =-2,2x =4 即123x x x ??
? ?
???=()2,4,0-T 为基解,但不是基本可行解。
(2)2B =(
1,3
p p ),︱2B ︳≠0,2B 是基,1x ,3x 是基变量,2x 是非基变量。令
2x =0,得1x =2/3,3x =3/4,即123x x
x ?? ? ? ???=??
???? ??34320为基解,同时为基本可行解,
z max =(2/3)*3+0+4/3*3=6。
(3)
32,3()
B p p =,︱3B ︳≠0,3B 是基,2x ,3x 是基变量,1x 是非基变量,令
1x =0,得2x =1,3x =1,即123x x x ?? ? ? ???=??
??? ??110为基解,同时为基本可行解,
z max =1+3=4。
综上所述,基解为123x x x ?? ? ? ???=?????
?
?-042,123x x x ?? ? ? ???=????? ??34320,123x x x ?? ? ? ???=?
????
??110其中第二个和第三个为基本可行解,123x x x ?? ? ? ???=?
????
??34320为最优解。
2.分别用图解法和单纯形法求解下列线形规划问题,并指出单纯形法迭代的每一步相当于图形上哪一个顶点
???
??≥≤≤-+=0,21st.32max 2
112121x x x x x x x z
解:(1)图解法
有图解法知线性规划模型的可行域如阴影部分所示,令z=0,1,2……时,max z
逐渐增大,可行域是无界的,所以,此模型是无界解。
(2)单纯形法: 化为标准型为:
123412314123,4m ax 230012st.,,0z x x x x x x x x x x x x x =+++-+=??
+=??
≥???
A= 11101
1-?? ??? ????
??=21b C=(2,3,0,0)
对应图中原点。以1⊕为轴心项,换基迭代,得
此时对应图中A 点,坐标是 (1,0) 以1
⊕为轴心项,换基迭代,得
此时对应图中B 点,坐标是 (2,3)因为,3σ=5>0,同时3x 对应的列小于等于0,则原模型有无界解。 ???
??
?
?≥≤+≤≤+=0
,18231224st.52max 21212121x x x x x x x x z
解:(1)图解法:
可行域如上图阴影部分所示,令z=0,1,2……做等值线,得出在c 点取最大值,c 点坐标为(2,6),max z=34 (2)单纯形法:化为标准型为:
1234513241
25m ax 250004212st.32180,1,2......5j z x x x x x x x x x x x x x j =+++++=?
?
+=?
?
++=??≥=?
1
01000
201032
1A ?? ?= ? ??
?
=(
1,2345
,,,p p p p p ) b=
4128?? ? ? ???
C=(2,5,0,0,0) 取B=(345,,p p p )为可行基,B C =(0,0,0)
单纯性表如下:
此时对应图中O 点,坐标为(0,0),以1⊕为轴心项,换基迭代,得
此时对应图中A 点,坐标为(4,0) 以2⊕为轴心项,换基迭代,得
此时对应图中B 点,坐标为(4,3) 以3
⊕为轴心项,换基迭代,得
由于 σ基 =0,σ
非基<0,所以存在唯一解,也是最优解。
此时对应图中
C
点,坐标为(2,6),max z=2*2+5*6=34,
()()T
T
x x x x x 0,0,2,6,2,,,,54321=
??
?
??
?
?≥≤≤+≤++=0
,93821222st.42max 212212121x x x x x x x x x z
解:(1)图解法:
可行域如图阴影部分,当z=0,1,2……做等值线,已知1224z x x =+与直线
1228x x +=的斜率相同,当z 与这条直线重合时,该模型取最大值,因此该模型有无穷多
个解,无穷多个解是B,C 两点线段中的点,max z=16
(2)单纯形法:化为标准型: 1234512312425m ax 24000221229st.390,1,2......5j z x x x x x x x x x x x x x x j =++++++=??
++=??
+=?
?≥=?
2
21001
201003
1A ?? ?= ? ??
?
= (
1,2345
,,,p p p p p ) b=
1289?? ? ? ???
C=(2,4,0,0,0) B=(345,,p p p ) B C =(0,0,0) 单纯形表为:
此时对应图中点O ,坐标为(0,0),以2⊕为轴心项,换基迭代,得
此时对应图中点A ,坐标为(6,0) 以1
⊕为轴心项,换基迭代,得
此时对应图中点B ,坐标为(4,2) 由于σ≤0,又3x 为非基变量,且3σ=0,且此列存在正数,则此线性规划模型有无穷解。其中一个基本最优解为
()
T
T
x x x x x )3,0,0,2,4(54
321
=,max z=2*4+4*2=16
3.用单纯形法求解下列线性规划问题
???
??
?
?≥≤++≤+-≤-+-+=0,,,582242st.2min 321321321321321x x x x x x x x x x x x x x x f
解:化为标准型:
12345612341235126m ax 200024228st.50,1,2......6j z x x x x x x x x x x x x x x x x x x j =--+++++-+=??
-++=??
++=?
?≥=?
A=????? ?
?--10
1
1010221001112 b=48
5?? ? ? ??? C=(-1,-2,1,0,0,0)
令B=(456,,p p p ) B 为可行基,B C =(0,0,0) 单纯形表如下:
以2
⊕为轴心项,换基迭代,得
σ基 =0,σ非基<0,存在唯一解,此时1x =2x =0,3x =4。min f=0+2*0-4=-4
4.用大M 法求解下列线性规划问题
??
?
??≥≤+-≥++++=0,,1621024st.35max 321321321321x x x x x x x x x x x x f
解:化为标准型(加上人工变量a ):
1234512341235m ax 53004210
st.2160,1,2......5j f x x x x x M a x x x x a x x x x x j =++++-?++-+=?
-++=??≥=?
1421011
2
1
1
0A -??=
?-?? b=1016?? ?
?? C=(5,1,3,0,0)
以2⊕为轴心项,换基迭代,得
以1
⊕为轴心项,换基迭代,得
无界解。
5. 已知线性规划问题,用单纯形法计算时得到的中间某两步的计算表见表3-16所示,试将表中空白处的数字填上。
表3-16 单纯形迭代中的两步计算表
…
6.已知线性规划问题 33221
1max x c x c x c z ++=
???
??=≥=+++=+++5,1,0st.2
532322212114313212111 j x b x x a x a x a b x x a x a x a j
用单纯形法求解,得到最优单纯形表如表如表3-17所示:
表3-17 最终单纯形表
⑴求21232221131211,,,,,,,b b a a a a a a 的值; ⑵求321,,c c c 的值。
解:由题意可知:初始的基变量是4x , 5x ,将最终单纯形表的基变量通过迭代转换为4x ,5x ,还原成最初单纯形表,如下:
从而得出:
91410251
2
12
A ??
?
=
?
? ??? b=85?? ??? C=9,3,6,0,02?? ?
??
所以,11a =9
2 12a =1 13a =4 21a =5
2 22a =1 23a =2
1b =8 2b =5, 1c = 9
2 2c =
3 3c =6
7.某公司生产1、2两种产品,市场对1、2两种产品的需求量为:产品1在1-4月每月需求10000件,5-9月每月30000件,10-12月每月100000件,产品2在3-9月每月需求15000件,其它月每月50000件,该公司生产这两种产品的成本为:产品1在1-5月内生产每件5元,6-12月内生产每件4.5元;产品2在1-5月内生产每件8元,6-12月内生产每件7元。该公司每月生产这两种产品的能力总合不超过120000件。产品1容积每件0.2立方米,产品2每件0.4立方米,该公司仓库容量为15000立方米,占用公司仓库每月每立方米库容需1元;如该公司仓库不足时,可从外边租借,租用外面仓库每月每立方米库容需1.5元。试问在满足市场需求的情况下,该厂应如何安排生产,使总的费用最小?
8.某炼油厂使用三种原料油甲、乙、丙混合加工成A 、B 、C 三类不同的汽油产品,有关数据如下表3-18所示。另外,由于市场原因,A 的产量不得低于产品总量的40%。问该厂应如何安排生产才能使其总利润最大?
表3-18 三种原料的信息
解:设1x ,2x ,3x 分别为A 产品中甲、乙、丙的成分;4x ,5x ,6x 分别为B 产品中
甲、乙、丙的成分;7x ,8x ,9x 分别为C 产品中甲、乙、丙的成分。由题意,有
max z=(3.060-0.450)*(1x +2x +3x )+(2.565-0.360)*(4x +5x +6x )+(2.025-0.270)*(7x +8x +9x )-1.800*(1x +4x +7x )-1.350*(2x +5x +8x )-0.900*(3x +6x +9x )
1472583
69
112331234
45664569
789200025001200
0.6.0.20.150.60.50,1,2,...,9j x x x x x x x x x x x x x x st x x x x x x x x x x x x x x x x j ???
?++≤?
++≤??++≤??
≥?
++??≤?++??≥?
++???≤++??
?≤++??
≥=?
用计算机求解为:
9.线性规划的目标函数是求其值的极大化,在标准的单纯形法求解过程中得到如下表(其中21H ,H 是常数)
表3-19 求解中某一步的单纯形表
(1)在所有的空格上填上适当的数(可包含参数21H ,H )
(2)判断下面四种情况在什么时候成立,说明理由。1)此解为最优解,写出相应的基解和目标函数值;2)此解为最优解,且此线性规划有无穷多最优解;3)此规划有无界解;4)此解不是最优解,但可用单纯形法得到下一个基可行解。
解:(1)
(2)1)当2-51H <0 即 1H >2
5时,此线性规划模型有唯一解,基解为
1232(,,)(0,,0)x x x H T =T 最优值为52H 。
2)2-51H =0,即 1H =2
5时,大于0,此线性规划模型有无穷多最优解。 3)2-51H >0且 1H <0,即1H <0时, 此线性规划模型有无界解。
4)2-51H >0且 1H >0且2H >0, 即0<1H <2
5且2H >0时,
此解不是最优解。
10.表3-20是求某极大化线性规划问题计算得到的单纯形表。表中无人工变量,1a 、2a 、
3a 、d 、1c 、2c 为待定常数。试说明这些常数分别取何值时,以下结论成立。
表3-20 极大化线性规划问题计算得到的单纯形表