1、第二章 1用图解法求解两个变量线性规划问题的最优解和最优值。 0,153562s t.32m a x21212121xxxxxxxxz1x2x最 优 解 ： （ 1 2 / 7 ， 1 5 / 7 ）最 优 值 ： 6 9 / 72用图解法求解以下线性规划问题，并指出哪个问题有惟一解、无穷多最优解、无界解或无可行解 0,34312st.46min21212121xxxxxxxxz最 优 解 ： （ 1 / 5 , 3 / 5 ）最 优 值 ： 3 . 611 / 203 / 411x2x0,81022st.84max21212121xxxxxxxxz1x2x无可行解 3某公司从中心制造地点向分
2、别位于城区北、东、南、西方向的分配点运送材料。该公司有 26 辆卡车，用于从制造地点向分配点运送材料。其中有 9 辆，每辆能装 5 吨的大型卡车， 12 辆每辆能装 2 吨的中型卡车和 5 辆每辆能装 1 吨的小型卡车。北、东、南、西四个点分别需要材料 14 吨、 10 吨、 20 吨、 8 吨。每辆卡车向 各分配点送材料一次的费用如表2-7 所示。建立运送材料总费用最小的线性规划模型。 表 2-7 车辆运送一次的费用 北 东 南 西 大 80 63 92 75 中 50 60 55 42 小 20 15 38 22 解 设大、中、小型车分别用 i 表示，则 3,2,1i ；东、南、西、北四个
3、分点分别用 j 表示，则 4,3,2,1j ；向 j 方向发出的 i 型车数量为 ijx 。 343332312423222114131211 22381520 4255605075926380m i n xxxx xxxxxxxxZ 4,3,2,1,05129825202510251425.343332312423222114131211342414332313322212312111jixxxxxxxxxxxxxxxxxxxxxxxxxstij4某工厂生产 A、 B、 C 三种产品，现根据合同及生产状况制定 5 月份的生产计划。已知合同甲为： A 产品 1000 件，每件价格为 500 元
4、，违约金为 100 元 /每件；合同乙： B产品 500 件，每件价格为 400 元，违约金为 120 元 /每件；合同丙为： B产品 600 件，每件价格为 420 元，违约金为 130 元 /每件； C 产品 600 件，价格 400 元 /每件，违约金为 90 元 /每件。有关各产品生产过程所需工时以及原材料的情况如表 2-8 所示。试以利润为目标建立该工厂生产计划的线性规划模型。 表 2-8 产品使用的原材料、加工工序、资源限制、成本 产品 A 产品 B 产品 C 资源限制 工时或原材料成本 工序 1 2 1 2 4600 15 工序 2 3 1 1 4000 10 工序 3 2 3
5、2 6000 10 原料 1 3 2 4 10000 20 原料 2 4 3 2 8000 40 其他成本 10 10 10 解 设工厂 5 月份为完成合同甲生产 1x 件 A 产品；为完成合同乙生产 2x 件 B产品；为完成合同丙生产 3x 件 B产品， 4x 件 C 产品。 2 9 2 0 0 02 6 03 2 52 9 52 9 0)1040220420210152()()104032201031015()10404203102103152(90)6 0 0(4 0 01 3 0)6 0 0(4 2 01 2 0)5 0 0(4 0 0)1 0 0 0(5 0 0m a x432143
6、2144332211xxxxxxxxxxxxxxxxZ,6 0 00,6 0 00,5 0 00,1 0 0 008 0 0 02)(341 0 0 0 04)(236 0 0 023324 0 0 0234 6 0 022.432143214321432143214321xxxxxxxxxxxxxxxxxxxxxxxxst5某公司从事某种商品的经营，现欲制定本年度 10 至 12 月的进货及销售计划。已知该种商品的初始库存量为 2000 件，公司仓库最多可存放 10000 件，公司拥有的经营资金 80 万元，据预测， 10 至 12 月的进货及销售价格如表 2-9 所示。若每个月仅在 1号进
7、货 1 次，且要求年底时商品存 量达到 3000 件，在以上条件下，建立该问题的线性规划模型，使公司获得最大利润？（注：不考虑库存费用） 表 2-9 进货和销售价格 月份 10 11 12 进货价格 /（元 /件） 90 95 98 销售价格 /（元 /件） 100 100 115 解 12,11,10, ixi ，为每月购进的货物， 12,11,10, iyi 为每月销售的货物。 12,11,10,012,11,10,03 0 0 02 0 0 02 0 0 02 0 0 02 0 0 01 0 0 0 02 0 0 01 0 0 0 02 0 0 01 0 0 0 02 0 0 08 0
8、0 0 0989590.9895901 1 51 0 01 0 0m a x121110101112111010111212101011111010111010111210101110121110121110121110iyixyyyxxxyyxxxyyxxyxyyyxxxyxxxxxxstxxxyyyZii年底存量限制销量限制销量限制销量限制库容限制库容限制库容限制资金限制6某饲养场饲养动物出售，设每头动物每天至少需 700g 蛋白质、 30g 矿物质、 100mg维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量单价如表 2-10 所示。 表 2-10 饲料所含的营养成分及价格 饲料
9、 蛋 白质 /g 矿物质 /g 维生素 /g 价格 /（元 1kg ） 1 3 1 0.5 0.2 2 2 0.5 1.0 0.7 3 1 0.2 0.2 0.4 4 6 2 2 0.3 5 18 0.5 0.8 0.8 求这个问题的规划模型，使既满足动物生长的需要，又使费用最小的选用饲料的方案。 解 设各送这 5 钟饲料 1x ， 2x ， 3x ， 4x ， 5x kg。 5,4,3,2,1,1 0 08.022.05.0305.022.05.07 0 018623.8.03.04.07.02.0m in54321543215432154321ixxxxxxxxxxxxxxxxstxxxx
10、xZi 7某一企业家需要找人清理 5 间会议室、 12 张桌子和 18 个货架。今有两个临时工 A和 B可供该企业家雇佣。 A 一天可清理 1 间会议室、 3 张桌子与 3 个货架；而 B 一天可清理 1 间会议室、 2 张桌子与 6 个货架。 A 的工资每天 25 元， B每天 22 元。为了使成本最低，应雇佣 A 和 B各多少天？（用线性规划图解法求解） 解：设雇佣 A 和 B分别为 yx, 天 为整数且 yxyxyxyxyxstyxZ,0;186312235.2225m in045 6356xyA3 x + 2 y = 1 2x + y = 53 x + 6 y = 1 8由图知 A 点
11、为最优解，联立方程： 5 1223 yx yx 解得： x =2, y 3,即： Zmin=25x +22y =25 2+22 3=116 因此，雇佣 A 工人 2 天， B工人 3 天。 8某外贸公司专门经营某种杂粮的批发业务。公司现有库容 5000 担的仓库。 1 月 1 日，公司拥有库存 1000 担杂粮，并有资金 20000 元。估计第一季度杂粮价格如表 2-11 所示。 表 2-11 第一季度 杂粮价格表 进货价 /元 出货价 /元 1 月 2.85 3.10 2 月 3.05 3.25 3 月 2.90 2.95 如果买进的杂粮当月到货，但需到下月才能卖出，且规定 “货到付款 ”。
12、公司希望本季度末库存为 2000 担，建立该问题的线性规划模型使三个月总的获利最大。 解 设一月份买入 1x 担，卖出 1x 担；二月份买入 2x 担，卖出 2x 担；三月份买入 3x 担，卖出 3x 担。 3,2,1,0;3,2,1,02 0 0 01 0 0 025.310.385.22 0 0 0 090.25 0 0 01 0 0 010.385.22 0 0 0 005.35 0 0 01 0 0 02 0 0 0 085.2.90.295.205.325.385.210.3m a x33221121132211112111332211jxixxxxxxxxxxxxxxxxxxxxx
13、stxxxxxxZji 第三 章 1求下列线性规划问题的所有基解、基可行解、最优解 0,6422s t.33m a x321321321321xxxxxxxxxxxxz解：由题意知： A= 1 1 11 2 4=（ 1, 2, 3pp p ） b=26c=（ 3， 1， 3） （ 1） 1B =（ 1, 2pp）， 1B 0， 1B 是基， 1x ， 2x 是基变量， 3x 是非基变量，令3x =0，得 1x =-2， 2x =4 即123xxx= 2,4,0为基解，但不是基本可行解。 （ 2） 2B =（ 1, 3pp）， 2B 0， 2B 是基， 1x ， 3x 是基变量， 2x 是非基变
14、量。令2x =0，得 1x =2/3， 3x =3/4，即123xxx= 34320为基解，同时为基本可行解，zmax=(2/3)*3+0+4/3*3=6。 （ 3） 3 2, 3()B p p ， 3B 0， 3B 是基， 2x ， 3x 是基变量， 1x 是非基变量，令1x =0，得 2x =1， 3x =1，即123xxx= 110为基解，同时为基本可行解， zmax=1+3=4。 综上所述，基解为123xxx= 042，123xxx= 34320，123xxx= 110其中第二个和第三个为基本可行解，123xxx= 34320为最优解。 2分别用图解法和单纯形法求解下列线形规划问题，并
15、指出单纯形法迭代的每一步相当于图形上哪一个顶点 0,21st.32max2112121xxxxxxxz解：（ 1）图解法 o1x2xA21 xB121 xx有图解法知线性规划模型的可行域如阴影部分所示，令 z=0， 1， 2 时， max z 逐渐增大，可行域是无界的，所以，此模型是无界解。 （ 2）单纯形法： 化为标准型为： 1 2 3 41 2 3141 2 3 , 4m a x 2 3 0 012st., , 0z x x x xx x xxxx x x x A= 1 1 1 01 0 0 1 21bC=（ 2， 3， 0， 0） Bc Bx 2 1x 3 2x 0 3x 0 4x b
16、0 3x 1 -1 1 0 1 0 4x 1 0 0 1 2 2 3 0 0 对应图中原点。以 1 为轴心项，换基迭代，得 Bc Bx 2 1x 3 2x 0 3x 0 4x b 2 1x 1 -1 1 0 1 0 4x 0 1 -1 1 1 0 5 -2 0 -2 此时对应图中 A点，坐标是 （ 1， 0） 以 1 为轴心项，换基迭代，得 Bc Bx 2 1x 3 2x 0 3x 0 4x b 2 1x 1 0 0 1 2 3 2x 0 1 -1 1 1 0 0 3 5 -7 此时对应图中 B点，坐标是 （ 2， 3） 因为， 3 =50,同时 3x 对应的列小于等于 0，则原模型有无界解。
17、 0,18231224st.52max21212121xxxxxxxxz解：（ 1）图解法： 可行域如上图阴影部分所示，令 z=0， 1， 2 做等值线，得出在 c 点取最大值， c 点坐标为 （ 2， 6） ， max z=34 （ 2）单纯形法：化为标准型为： 1 2 3 4 513241 2 5m a x 2 5 0 0 042 1 2st. 3 2 1 80 , 1 , 2 . . . 5jz x x x x xxxxxx x xxj 1 0 1 0 00 2 0 1 03 2 0 0 1A = （ 1, 2 3 4 5, , ,p p p p p ） b= 4128 C=（ 2， 5， 0， 0， 0） 取 B=（ 345,p p p ）为可行基， BC =（ 0， 0， 0） 单纯性表如下： Bc Bx 2 1x 5 2x 0 3x 0 4x 0 5x b 0 3x 1 0 1 0 0 4 0 4x 0 2 0 1 0 12 0 5x 3 2 0 0 1 18 2 5 0 0 0 此时对应图 中 O 点，坐标为（ 0， 0）， 以 1 为轴心项，换基迭代，得 Bc Bx 2 1x 5 2x 0 3x 0 4x 0 5x b
