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 极大化线性规划问题计算得到的单纯形表