重庆大学最优化方法习题答案

1、习题一1.1 利用图解法求下列线性规划问题：（1） max z x1 x 23x1 x 2 2s.t.x1 2x2 5x1 , x2 0解：根据条件，可行域为下面图形中的阴影部分， ，有图形可知，原问题在 A 点取得最优值， 最优值 z=5（2） min z x1 6x 22x1 x2 1s.t. x1 x 2 7x1 , x2 0解：图中阴影部分表示可行域，由图可知原问题在点 A 处取得最优值，最优值 z=-6.（3） max z 3x1 2x 2s.t.x1 2x2 4x1, x2 0解 ： 如 图 所 示 ， 可 行 域 为 图 中 阴 影 部 分 ， 易 得 原 线 性 规 划 问 题

2、 为 无 界 解 。 x1 x2 1（4） min z 2x1 5x 2x1 2x2 6s.t.x1 x2 2x1 , x2 0解：由图可知该线性规划可行域为空，则原问题无可行解。1.2对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。（1） min z 5x1 2x2 3x3 6x4s.t.2x1 x2 x3 2x4 3x1 , x2 , x3 , x4 0 x1 2x2 3x3 4x4 7解： 易知 x1 的系数列向量 p1 ，x2 的系数列向量 p2 ，x3 的系数列向量 p3 ， 21 1 2 1 3x4 的系数列向量 p4 。 2 4因为 p1, p2 线性无关，故

3、有 2x1 x2 3 x3 2x4x1 2x2 7 3x3 4x4，令非基变量为 x3 x4 0 ，得x11 1x2 3 13，所以得到一个基解 x(1) (,0,0) 是非基可行解；3 31 11因为 p1 , p3 线性无关，可得基解 x ( ,0,0) ， z2 ；555211( 2)43因为 p1, p4 线性无关，可得基解 x (,0,0,) ，是非基可行解；36111(3)因为 p2 , p3 线性无关，可得基解 x (0,2,1,0) ， z4 1；( 4)因为 p2 , p4 线性相关， x2 , x4 不能构成基变量；因为 p3 , p4 线性无关，可得基解 x (0,0,1

4、,1) ， z6 3 ；(6)所以 x( 2) , x(4) , x(6) 是原问题的基可行解， x(6) 是最优解，最优值是 z 3 。（2） max z x1 x2 2x3 x4 x5x1 x2 x3 x 4 1s.t. x1 2x2 x5 4xi 0, i 1,2,3,4,5解：易知 x1 的 系数列向 量 p1 ， x 2 的 系 数列向 量 p2 ， x3 的系 数列向量 11 1 2 01 ， x 的系数列向量 p 01 p344 ， x 的系数列向量 p 0 55 。1 因为 p1, p2 线性无关，故有 x1 2x2 4 x5x1 x2 1 x3 x4，令非基变量为 x3 x4

5、 x5 0 ，得x5 1x2 3 23，所以得到一个基解 x(1) (,0,0,0) ，是非基可行解；3 32 5因为 p1 , p3 线性无关，可得基解 x (4,0,5,0,0) ，是非基可行解；( 2)因为 p1, p4 线性无关，可得基解 x (4,0,0,5,0) ，是非基可行解；(3)因为 p1 , p5 线性无关，可得基解 x (1,0,0,0,5) ， z4 4 ；( 4)因为 p2 , p3 线性相关，得基解 x (0,2,1.0,0) ，是非基可行解；(5)因为 p2 , p4 线性无关，可得基解 x (0,2,0,1,0) ，是非基可行解；(6)因为 p2 , p5 线性

6、无关，可得基解 x (0,1,0,0,2) ， z7 1；(7)因为 p3 , p4 线性相关， x3 , x4 不能构成基变量；因为 p3 , p5 线性无关，可得基解 x (0,0,1,0,4) ， z9 6 ；(9)因为 p4 , p5 线性无关，可得基解 x (0,0,0,1,4) ， z10 3 ；(10)所以原线性规划的基可行解是 x( 4) , x(7) , x(9) , x(10) ，最优解是 x(7) ，最优值是 z 1。1.3 用单纯形法求解下列线性规划问题；（1） max z 2x1 3x2x1 3x 2 5s.t.x1 x2 2x1 , x2 0解：引入松弛变量 x3

7、，剩余变量 x4 和人工变量 x5 ，把原问题化为规范式max z 2x1 3x2 Mx5s.t.x1 x2 x4 x5 2 ，其中 M 无限大，xi 0, i 1,2.5构造初始单纯形表并计算如下：x1 3x2 x3 5以 x2 作为换入基， x3 作为换成基，计算得以 x1 为换入基， x5 作为换出基有以 x4 换入， x2 换出有x1x2x3x4x52+M3+M0-M0 x3131005x5110-112x1x2x3x4x51+ 2 M30-1- M3-M0 x2131130053x5230 13-1113x1x2x3x4x500 1232 3 M 2-5.5x2011212 121.

8、5x110 12 32320.5根据单纯形表可知，原问题的最优解为 x* (5,0,0,3) ，最优值为 z* 10（2） max z x1 x2 2x33x1 x2 x3 5s.t.x1 4x2 x3 7x1, x2 , x3 0解：引入松弛变量 x4 ，剩余变量 x5 和人工变量 x6 ，把原问题规范化为max z x1 x2 2x3 Mx63x1 x 2 x3 x4 5s.t.x1 4x2 x3 x5 x6 7xi 0, i 1,2.6以 x1 作为换入基， x4 作为换出基有x1x 2x3x4x50-3-20 3 M-10 x 40211-13x1131005x1x2x3x4x5x61

9、+M1-4M-2+M0-M0 x431-11005x61-410-117x1x2x3x4x5x6以 x3 为换入变量， x6 为换出变量，得所以原问题最优解为 x* (3,0,4) ，最优值为 z* 5 。（3） min z 2x1 3x2 x3x1 4x2 2x3 8s.t.3x1 2x2 6x1 , x2 , x3 0解：引入剩余变量 x4 , x5 和人工变量 x6 , x7 ,利用两阶段法得到辅助线性规划max w x6 x7123max z 2x 3x xs.t.3x1 2x2 x5 x7 6xi 0, i 1,2.7构造初始单纯形表，并计算x1 4x2 2x3 x4 x6 802

10、13M334M 5331 M3-M0 x1113- 13130053x60 1334313-11163x1x2x3x4x5x60 19 4M 40 1 12 545 4M4x11 56014-133x30 1341 14- 34344以 x2 为换入变量， x6 为换出变量，得以 x1 为换入变量， x7 为换出变量，得从单纯行表中可知，原问题有无限多个最优解，其中一个为 x* (0.8,1.8,0) ，最优值为z* 7 。（4） max z 10 x1 15x2 12x3x1x2x3x4x5x6x7z-2-3-10000w462-1-100 x6142-10108x73200-1016x1x

11、2x3x4x5x6x7z 54012 340340w520-112-1320 x214112- 1401402x7520-112-1 1212x1x2x3x4x5z000 12 12x2010.6-0.30.11.8x110-0.40.2-0.40.8x2x1 x2 x3 5 5x 6x 15x 155x1 3x2 x3 9s.t. 0, j 1,2,3j123解：引入松弛变量 x4, x5 ，剩余变量 x6, ，人工变量 x7 ，将原问题化为规范式max z 10 x1 15x2 12x3 Mx75x1 3x2 x3 x4 9x2x1 x2 x3 x6 x7 5 5x 6x 15x x 15

12、s.t. 0, j 1,2,.,7j1235构造初始单纯形表并计算得以 x1 为换入变量， x4 为换出变量，得以 x1 为换入变量， x4 为换出变量x1x2x3x4x5x6x7z10+2M15+M12+M00-M0 x453110009x5-5615010015x721100-115x1x2x3x4x5x6x7进一步计算知道， x7 0 ，所以原问题没有可行解。1.4设目标函数极大化的线性规划问题的单纯形表如下，表中无人工变量，当待定常数a1 , a 2 , b1, c1, c2 为何值时，表中的解： （1）为唯一最优解， （2）为多重解， （3）有无界解，（4）为退化解。解：当 b1 0

13、, c1 , c2 0 ，为唯一最优解；当 b1 0, c1 0, c2 0或 c1 0, c2 0 ，为多重解；当 b1 0, a 2 0, c1 0, c2 0 ，具有无界解； b1 0, c1 0或 a 2 0, c2 0 ，为退化的可行解。1.5 某商店要制定某种商品第二季度的计划，已知该商店仓库容纳此种商品的容量不超过600 件，3 月底已存货 200 件，以后每月初进货一次。假定各月份此种商品买进售出的单价 如下，问各月进货、售货各多少件才能使利润最大？假设进货时受到仓库容量的限制，售货z09 M510 3M52 2M50-M0 x110.60.20.20001.8x5091611

14、0024x70-0.20.6-0.40-111.4x1x2x3x4x5x6c10c2-900z0 x2a11a 2-1007x5-10-50103x640-2101b1时受到进货量的限制，不考虑货物存放在仓库的耗损与保管费用。解：设 xi 表示每个月进货量， yi 表示相应月份售货量，其中 i 1,2,3 ，则有数学模型：max z 18y1 18y2 19y3 17x1 16.5x2 17x3x1 600 200 x y x y x y 200 x1 y1 x2 y2 200 11223s.t. x1 y1 200 xi , yi 0, i 1,2,3x y x y x 600 200 11

15、2x y x 600 200112233经计算，当 x1 400, y1 600, x2 500, y2 600, x3 600, y3 600 时，即四月份进货400 件，售货 600 件，五月份进货 500 件，售货 600 件，六月份进货 600 件售货 600 件时，最大利润为 6100 元。1.6 设市场上可买到 n 种不同的食品，第 j 种食品的单位售价为 c j ，每种食品含有 m 种基本 营养成分，第 j 种食品每一个单位含第 i 种营养成分为 aij ，每人每天对第 i 种营养成分的需 要量不少于 bi ，试确定在保持营养成分要求条件下的最经济食谱。解：设没人每天需要第 j

16、种食品的数量为 x j （j=1,2,.,n） ，建立数学模型为：nmin z c jx jj1月份买进单价/(元/件)售出单价/(元/件)41718516.51861719x j 0, j 1,2,.naijx j bi , i 1,2,., ms.t. j1 n1.7A,B 两种产品都需要经过前、后两道工序加工，每一个单位产品 A 需要前道工序 1h 和后道工序 2h，每一个位产品 B 需要前道工序 2h 和后道工序 3h.可利用的前道工序有 11h， 后道工序有 17h。没加工一个单位产品 B 的同时，会产生 2 个单位的副产品 C，并且不需要 任何费用，产品 C 一部分可出售盈利，其余

17、的只能加以销毁。出售单位产品 A,B,C 的利润 分别为 3 元，7 元，2 元，每单位产品 C 的销毁费为 1 元。预测表明，产品 C 最多只能出 售 13 个单位。试建立总利润最大的生产计划数学模型。解：设 x1 , x2 分别为产品 A,B 的产量， x3 为副产品 C 的销售量， x4 为副产品 C 的销毁量， 于是有 x3 x4 2x2 ，z 为总利润，则数学模型如下：max z 3x1 7x2 2x3 x4x1 2x2 11x3 13s.t. 2x2 x3 x4 0 x1, x2 , x3 , x 4 02x 3x 1712习题二2.1 写出下列线性规划问题的对偶问题：（1） mi

18、n z 10 x1 5x2 x3x1 2x 2 4x3 10 x , x1 x2 7 132 123x 6x 5x 2s.t. 0, x 自由变量解：原问题的对偶问题为：max w 10y1 2y2 y3 7y4y1 y2 104y1 5y2 1y1 0, y2 , y3 , y4 0（2） max z x1 2x2 3x3 4x 4x1 5x2 x3 2x 4 62y 6y y y 5s.t.1234x , x , x 0, x 自由变量4x1 2x2 3x3 x 4 5 1232x x x 5x 13s.t.41234解：原问题的对偶问题是min w 6y1 13y2 5y3y1 2y2

19、4y3 12y1 5y2 y3 4s.t.2 y1 y2 3y3 3y1无约束 , y2 0, y3 05y y 2y 21232.2 证明下列线性规划为题为最优解min z x1 2x2 2x3 s.t.x , x1 x2 7 12 123x 2x 3x 22x1 x 2 2x3 3 0, x 自由变量3证明：原问题的对偶问题为max w 3y1 2y22y1 y2 1 2y1 3y2 2y2 0, y1无约束易知该对偶问题无可行解，由定理知则原问题无最优解。 12y 2y 2s.t.2.3对线性规划问题min z 4x1 6x2 18x3x1 3x3 3s.t.x2 2x3 5x1 , x

20、2 , x3 0（1）写出该线性规划问题的对偶问题；（2）已知对偶为题的最优解为（2,6） ，试用互补松弛定理求其原问题的最优解。 解： （1）原问题的对偶问题为：max w 3y1 5y23y1 2y2 18y1 , y2 0（2）根据互不松弛定理有(yA c)x 0 则yy1 4s.t. 621 (3,5) (2,6) 023 (x1 , x2 , x3 )010 3有 13 x2 2x3 5又因为 yb cx 有x 3x 6 2 6 (3,5)18 4 (x , x , x3 )12即： 2x1 3x2 9x3 18x1 0联立解得 x 3 即原问题的最优解为（0,3,1）x3 122.

21、4对线性规划问题max z 2x1 x2 5x3 6x42x1 x3 x4 8s.t.2x1 3x2 x3 2x4 12x1 , x2 , x3 , x4 0（1）写出该线性规划问题的对偶问题；（2）已知原问题的最优解为 (0,0,4,4) ，试用互补松弛定理求对偶问题的最优解。 解： （1）原问题的对偶问题为：min z 8y1 12y22y1 2y2 2y1 2y2 6s.t.y1 y2 5y1 0, y2无约束3y 12(2)利用互补松弛定理有 (yA c )x 00 有 (2,1,5,6) 0440 23 1220 11 (y1 , y2 ) 有 y1 2y2 6 y2 1 12y y

22、 5即 1y 4所以对偶问题的最优解为（4,1）2.5用对偶单纯形法求解下列线性规划问题：（1） min z 2x1 4x2 5x3x1 x2 3x3 1s.t.- x1 x2 6x1 , x2 , x3 0解：利用对偶单纯形，添加松弛变量 x4 , x5 ，原问题化为规范式123max z 2x 4x 5xs.t.x1 x2 x5 6x1 , x2 , x3 , x 4 , x5 0 x1 x2 3x3 x4 1则有对偶单纯形表以 x2 为换入量， x5 为换出量有x1x2x3x4x5-2-4-500 x4-1-1310-1x51-1001-6x1x2x3x4x5-60-50-4x4-203

23、1-15x2-1100-16由表可知。原问题的最优解为（0,6,0）（2） max z x1 x2 2x3x1 5x2 3x3 4x1 2x2 3x3 7x , x , x 0 1232x x 6x 10s.t.123解：利用对偶单纯形，添加松弛变量 x4 , x5 , x6 ，原问题化为规范式：123max z x x 2xx 0, i 1,2,3,4,5,6x1 2x 2 3x3 x6 7 i- 2x x 6x x 10 x1 5x2 3x3 x4 4s.t.1235，则有单纯形表以 x3 为换入量， x5 换出得以 x2 为换入量， x4 为换出量有x1x2x3x4x5x6-1-1-20

24、00 x41-531004x5-2-1-6010-10 x61-230017x1x2x3x4x5x6-1/3-2/300-1/30 x40-11/2011/20-1x31/31/610-1/605/3x60-5/2001/212由表知原问题无最优解。2.6设有线性规划min z 2x1 x2 x33x1 x2 x3 60 x , x , x 0 x1 x2 x3 20 123 12x x 2x 10s.t.3求出最优解，并进行以下分析（1） c2 在什么范围内变动而不影响最优解？（2） b3 从 20 变为 16，求最优解；（3） x3 的系数变为 (1,3,1) ,，其价值系数从 1 变为-

25、5，试问最优解是否会发生变化？（4）增加约束条件 2x1 x2 x5 31，最优解有何变化？ 解：引入松弛变量 x4 , x5 , x6 ，将原问题化为规范行：123max z 2x x xx 0, i 1,2.6x1 x 2 x3 x6 20 i 12x x 2x x 103x1 x2 x3 x4 60s.t.35，x1x2x3x4x5x6-1/3002/3-3/110 x2010-2/11-1/1102/11x31/3011/33-5/33054/33x6000-5/113/11127/11x1x2x3x4x5x6列单纯形表有以 x1 为换入变量， x5 为换出变量有以 x2 为换入变量，

26、 x6 为换出变量有所以原问题的最优解为（15,5,0,10,0,0）（1）因为 x2 是基变量，由书中（2.6）式有 max( 1 ) 1 ， min( 3 , 1 ) 322 2 2 2 2 17 7 3所以 1 c 7 时，最优解不变，即 2 c 4 ，所以当 4 c2 2 时，原问题最优33322解不变。2-1-1000 x431110060 x51-1201010 x611-100120 x1x2x3x4x5x601-50-20 x404-51-3030 x11-1201010 x602-30-1110 x1x2x3x4x5x600-7/20-3/2-1/2x40011-1-210

27、x1101/201/21/215x201-3/20-1/21/25（2） b B b 0 01/ 2 0 211 2 1/ 21/ 2 0 8 4 21/ 2 1所以5 23b b b 15 2 1381810此时原问题的最优解为（13,3,0,18,0,0）（3） 3 c3 cBB p3 1 (2,11)0 0所以原问题的最优解变。1/ 21/ 2 3 2 01/ 2 1/ 2 1 2 1111（4）添加松弛变量 x7 ，在原最终单纯形表中添加一行一列并计算有以 x3 为换入量， x7 为换出量有x1x2x3x4x5x6x700-7/20-3/2-1/2x40011-1-2010 x1101

28、/201/21/2015x201-3/20-1/21/205x700109-32-8x1x2x3x4x5x6x7000063/2-1213/2x40001-101-218x11000-42-119x2010013-43-7以 x6 为换入量， x3 为换出量有得最优解为（41/3,11/3,0,46/3,0,8/3,0）,最优值为-71/32.7某厂生产 A1 , A2 , A3 三种产品，需要 B1 , B2 , B3 三种设备加工，需要单位各种产品所需 要的设备台时、设备的现有加工能力及每件产品的预期利润如下表所示（1）求获利最大的产品生产计划；（2）每件产品 A3 的利润增加到多大时，才

29、值得安排生产？如果每件产品 A3 的利润增加到50/6，求最优计划的变化；（3）产品 A1 的利润在多大范围变化时原最优计划保持不变？（4）如设备 B1 的能力为100 10 ，确定保持最优基不变的 的变化范围；（5）如有一种新产品，加工一件需要设备 B1 , B2 , B3 的台时各为 1h,4h,3h 预期每件的利润 为 8 元，是否值得安排生产？台/hA1A2A3设备能力B1111100B21045600B3226300单位产品利润1064x300109-32-8x1x2x3x4x5x6x700-40-9/20-13/2x4001/31-701/346/3x110-2/30201/341

30、/3x201-4/30101/311/3x600-1/30-31-2/38/3a)如合同规定该厂至少生产 10 件 产品 A3 ，试确定最优计划的变化。解：设计划生产产品 A1 , A2 , A3 各 x1 , x2 , x3 件，则有max z 10 x1 6x2 4x3x1 x2 x3 1002x1 2x2 6x3 300 x , x , x 0 123（1）构造单纯形表如下：10 x 4x 5x 600s.t123以 x1 为换入量， x5 为换出量有以 x2 为换入量， x4 为换出量有x1x2x3x4x5x61064000 x4111100100 x51045010600 x6226

31、001300 x1x2x3x4x5x602-10-10-600 x403/51/21-1/10040 x112/51/201/10060 x606/550-1/51180 x1x2x3x4x5x6得最优生产计划，即 x* (100 / 3,200 / 3,0,0,0,100) 为最优解，获利 2200/3 元（2）由 于x3 为 非 基 变 量 ， 则 只 有 0 才 值 得 生 产 ， 即c ,即 c 8/3,即 c 20/3 时 A 才值得生产。而当 c 50 / 6 20 / 3 ，此时最优3333解发生变化，根据计算，当 c 50 / 6 时， 5 / 3 0 时，此时将 x 作为换入

32、变量，x 作336为换出变量，得此时生产最优计划为（175/6,275/6,25,0,0,0）(3）由于 x1 的生产量为基变量，则有 max 4 ， min 1/ 61/ 6 8 / 3 2 / 3 , 5 ，即 2 / 3 10 / 3 c1 4,5时，原最优生产计划保持不变。得 c1 6,15（4）若矩阵B p1 , p2 , p3 4 21 21100 ，其逆矩阵 B 2 / 3210 5 / 311/ 61/ 60 ，为使最优基不发生01 0改变，根据（2.7）有 ， b 40,50， 2 / 3 2 max 200 / 3 b min 100 / 3 , 100 5 / 311即

33、4,5时，最优基不发生改变。00-8/3-10/3-2/30-2200/3x2015/65/3-1/60200/3x1101/6-2/31/60100/3x6004-201100 x1x2x3x4x5x6000-5/2-2/3-5/12-2325/3x201025/12-1/6-5/24275/6x1100-7/121/6-1/24175/6x3001-1/201/425（5）经计算 0 1 1 1 B1p7，c B1p (6,10,0)0 6，1 B7 知 c c B1P 8 6 2 0 ,则此时最优解发生变化，且该产品值得生产。77B7（6）原最优解不满足新的约束条件， x3 10 ，即

34、x3 10 ，引入松弛变量 x7 ，在原最 终单纯形表中增加一行或一列有：将 x7 做为换出变量， x3 作为换入变量，利用对偶单纯形有得到此时最优生产计划 x* (95 / 3,175 / 3,10,0,0,60)2.8对所有 t 值，讨论以下参数线性规划问题最优解的变化范围；x1x2x3x4x5x6x700-8/3-10/3-2/300-2200/3x2015/65/3-1/600200/3x1101/6-2/31/600100/3x6004-2010100 x700-10001-10 x1x2x3x4x5x6x7000-10/3-2/30-8/3-22120/ 3x20105/3-1/6

35、05/6175/3x1100-2/31/601/695/3x6000-201460 x7000100-110max z (7 2t)x 1 (12 t)x2 (10 t)x3x1 x2 x3 20s.t.2x1 2x2 x3 30 x1 , x2 , x3 0, t 0解：将上述问题转化为标准型有max z (7 2t)x 1 (12 t)x2 (10 t)x3x1 x2 x3 x4 20s.t.2x1 2x2 x3 x5 30 x1 , x2 , x3 ,x 4 , x5 0, t 0令 t=0，用单纯法求解如下：将 t 的变化直接反应到最终的单纯形表中c j7121000CBXBbx1x2

36、x3x4x50 x42011110200 x5302210115-z071210000 x45001/21-1/21012x215111/201/230-z-180-5040-610 x3100012-112x210110-11-z-220-500-8-2c j7+2t12+t10-t00CBXBbx1x2x3x4x510-tx3100012-1512+tx210110-11T 开始增大，当 t8/3 时，首先出现 4 0 ，故当 0 t 8 时，得最优解（0，10,，10，0）3目标函数的最优值为 max z 220(0 t 8) 。 t 8 为第一临界点33 0 ， x4 作为换入变量，由

37、规则确定 x3 为换出变量，用单纯形法进行当 8 t 5时, 3迭代：4由表可知，t 继续增大，当 t5 时首先出现 1 0 ，故当 t 5 时，得最优解（0,15,0,5）38目标函数的最优值为 180+15t，t=5 为第二临界点。当 t5 时， 1 0 ， x1 作为换入变量，由规则确定 x2 为换出变量，用单纯形法进行迭 代：由表知当 t 继续增大时，所有检验数都非正，所以当 t5 时，得最优解（15，0，0，5） 目标函数的最优值为 105+30t2.9考虑下列问题：max z 3x1 x 2x1 x2 4s.t.2x1 x 2 4x1 , x2 0-z-220T-5003t-8-2

38、-2tc j7+2t12+t10-t00CBXBbx1x2x3x4x50 x45001/21-1/212+tx215111/201/215-z-180-15tT-504-3t/20-6-t/2c j7+2t12+t10-t00CBXBbx1x2x3x4x50 x45001/21-1/27+2tx115111/201/2-z-105-30t05-t13/2-2t0-7/2-t（1）用单纯形方法求出最优解；（2）将约束右端 b 改变为 t(t 0) ，对 t 的所有值求出问题的最优解。 4 4 41 4 2 解： （1）引入松弛变量 x3 , x4 ，把原问题化为标准形max z 3x1 x 2x

39、1 x2 x3 4s.t.2x1 x2 x4 4 ，建立初始单纯形表x1 , x2 , x3 , x 4 0以 x1 为换入变量， x4 为换出变量，有以 x2 为换入变量， x3 为换出变量有所以，原问题的最优解为（8/3 ，4/3） 2t （2） b B b 1/ 3，将其加在最终单纯表中有 t / 3 5t / 3 1/ 3 2 / 31/ 3 t1x1x2x3x43100 x311104x42-1014x1x2x3x405/20-3/2x3011-1/22x11-1/201/22x1x2x3x400-5/3-2/3x2012/3-1/34/3x1101/31/38/3由表可知当 0 t

40、 4 ，问题的最优解为（8/3 -t/3，4/3-5t/3）5当 t 4 时，利用对偶单纯形有5由表可知当时，问题的最优解为（4-2t，0） ，当 t2 时，原问题无解。x1x2x3x400-5/3-2/3x2012/3-1/34/3-5t/3x1101/31/38/3 -t/3x1x2x3x40-2-3/2/3x40-3-215t-4x111104-2t习题三3.1 用割平面法求解下列整数线性规划。（1） min z 2x1 - x2x1 - 3x2 1 s.t.x1 x2 4x1 , x2 0且为整数解：增加松弛变量 x3 , x4 ，将其化为标准形为x1 - 3x2 x3 1 min w

41、 -2x1 x2 s.t.x1 x2 x4 4x1 , x2 , x3 , x4 0且为整数形表如下先不考虑整数条件， 则对应线性规划单纯以 x4 为换出基， x2 为换入基，进一步得单纯形表所以，原线性规划问题的最优解为 x* (0,4) ，是整数解所以也是原整数规划的整数解。（2） max z 12x1 9x22x1 x2 103x1 2x2 3x1 , x2 0且为整数解：增加松弛变量 x3 , x4 , x5 ，将其化为标准形为：- x 5x 6s.t.12x1x2x3x4w-2100 x31-3101x411014x1x2x3x4w-300-1x3401313x211014max z

42、 12x1 9x2 s.t.3x1 2x2 x5 3x1 , x2 , x3 , x4 , x5 0且为整数- x1 5x2 x4 62x1 x2 x3 10先不考虑整数条件，则对应线性规划单纯形表如下以 x2 作为换入变量， x4 为换出变量得所以线性规划的最优解为（0,6/5,44/5,0,27/5）分量 44/5取整后分数最大，考虑单纯形表中该分量所对应的行约束 11 x x55 1 x 44 ，则有割5413平面方程 4 (1 x 4 x ) 0 ，增加松弛变量 x ，化为等式约束555146555 1 x 4 x x 4 并加入上面最后的单纯形表中有：146x1x2x3x4x5z-1

43、29000 x32110010 x4-150106x53-20013x1x2x3x4x5z-51/500-9/50 x311/501-1/5044/5x2-1/5101/506/5x513/5002/5127/5x1x2x3x4x5x6z-51/500-9/500利用对偶单纯形法有由表可知最优解为（0,1）最优值为 9.3.2用分支定界法求解下列整数线性规划问题：（1） max z x1 5x23x1 4x2 11s.t.7x1 6x2 42x1 , x2 0且为整数解： 先不考虑 x1 ，x 2 为整数的约束条件， 求的相应线性规划问题的最优解为 x (0,11/ 4) ,(0)目标函数的最

44、优值为 z(0) 55 / 4 ，由于 x(0) 2 3 / 4 ，构造两个线性规划子问题如下：1max z x1 5x2x311/501-1/50044/5x2-1/5101/5006/5x513/5002/51127/5x6-1/500-4/501-4/5x1x2x3x4x5x6z-203/200000-9/4x343/200100-1/49x2-4/2510001/41x55/200011/25x6-1/40010-5/41(1)x2 2x1 , x2 0且为整数和 max z x1 5x27x1 6x2 423x1 4x2 11s.t.(2)x2 3x1 , x2 0且为整数先不考虑整

45、数的约束条件，求解（1）所对应的线性规划子问题得到最优解 x1 (1,2) ，最优 值为 z1 11， （2） 所对应的线性规划子问题没可行解。 故原整数规划的最优解为 x1 (1,2) ， 最优值为 z1 11。7x1 6x2 423x1 4x2 11s.t.（2） min z 3x1 - 2x2 x1 2x 2 7s.t.4x1 x 2 9x1 , x2 0且为整数3.3求解下列 01 规划问题：（1） max z 2x1 x2 3x3 5x4x1 3x2 x3 x4 1xx1 x2 x3 x 4 3xs.t. 0或1， j 1,2,3,4 2x 2j23解：利用隐枚举法，显然（0,1,1

46、,0）是原问题的一个解，增加约束条件 2x1 x2 3x3 5x4 4则有表由表可知，原问题的最优解为（0,1,1,0） ，最大值是 4.（2） min z x1 x2 x3 x1 x 2 x3 2xx1 7x 2 x3 04x x 2x 3s.t. 0或1， j 1,2,3j123解：显然（1,0,1）是原问题的一个解，增加约束条件x1 x2 x3 1 ，建立下表：由表可知，原问题的最优解为（1,0,0） ，最优值为 1.点条件满足条件？ 是（）否（）Z 值（0,0,0,0）0(0,0,0,1)-53(0,0,1,0)312-1(0,0,1,1)-2(0,1,0,0)1(0,1,0,1)-4

47、(0,1,1,0)4-2204(0,1,1,1)-1(1,0,0,0)-2(1,0,0,1)-7(1,0,1,0)-1(1,0,1,1)-4(1,1,0,0)-1(1,1,0,1)-6(1,1,1,0)-2(1,1,1,1)-3点条件满足条件？ 是（）否（）Z 值（0,0,0）0(0,1,0)-111-7(0,1,1)0(1,0,0)1-1411(1,0,1)2(1,1,0)005-6(1,1,1)1-17-54.1已知某运输问题的产销需求和单位运 价如下表，求解运输最少的方案和总运价。4.2 某百货公司去外地采购 A,B,C,D4 种规 格的服装， 数量如下 A 为 1500 套， B 为

48、2000 套，C 为 3000 套，D 为 3500 套。有三个城 市可供应上述规格服装， 各城市供应数量如 下 1 为 2500 套，II 为 2500 套，III 为 500 套。由于这些城市的服装质量、运价和销售 情况不同预计售出的利润也不同如下表所 示， 请帮该公司确定一个预期盈利最大的采 购方案。4.3 甲乙、 丙三个城市每年分别需要煤炭 320 万吨，250 万吨，350 万吨，由 A,B 两处煤 矿负责供应，已知煤炭年供应量 A 为 400 万吨，B 为 450 万吨，由煤矿至各城市的单 位运价如下表。由于需大于供，经研究平衡 决定，甲城市供应量可减少 030 万吨，乙 城市需要

49、量应全部满足， 丙城市供应量不少 于 270 万吨， 试用付格尔法求出初始调运方 案。4.4求解下列最小值的指派问题（1） c 133683 11226 5811 103 5（2）3841523344592130475625314553272220c 2520264.5 求解下列最大值的指派问题9615 14 1020（1） c 1813 1319168122696510485 （2） c 7109126157169868 1710产地销地B1B2B3B4产量A159315A213418A382617销售181216城市规格ABCDI10567II8276III9348甲乙丙A151822B2

50、12516习题五5.1利用最优性条件求解min f ( x) 1 x3 1 x3 x2 x122133f (x)f (x)解： x2 1， x2 2x ，由 f (x) 0 得驻点122x1x2x(1) (1, 0), x(2) (1, 2), x(3) (1, 0), x(4) (1, 2) ，又 f 2 (x) 2x1 02x2 20，得驻点处的 Hesse 矩阵 2 f (x(1) ) 20 ， 2 f ( x( 2 ) ) 2 02 0 20 ， 2 f (x(3) ) ， 02 02 2 f ( x( 4 ) ) 20 。 02 根据定理（5-8）知，局部最优解为 x=(1,2)。5

51、.2试判断下列非线性规划是否为凸规划（1） min f ( x) x2 x2 812x1 x2 0s.t. x x2 212x1, x2 0解：由于等式约束 x x 2 2 不是线性函数，则有定义知原规划不是凸规划。12（2） min f (x) x1 x2 x3 x1 x2222x2 x2 412s.t. 5x2 x 1013x1,x2, x3 0解：同理由于 5x2 x 10 不是线性函数，则有定义知原规划不是凸规划。135.3分别利用二分法、Newton 法、试探法、黄金分割法、Fibonacci 方法在区间 0,3上求 解如下问题（1） min f (x) x3 6x2 3x 7（2）

52、 min f (x) x3 2x2 x 5解： （1） f (x) 3x2 12x 3 ， f (x) 6x 12 ，为了计算简单，取精度 0.05 ， 二分法：取初值 x0=1.5，计算过程如下：由表可知 b6-a6=0.0468750.05，所以此时 x*=2.9765625。 Newton 切线法：取初值 x0=2.25，计算过程如下：此时 f(x5)=0.04552030.05，达到精度要求，可得 x*=4.2394583。但所求的 x*并不在0,3区 间内。 试探法：取初值 x0=2.25，计算过程如下：由表可知 k=13 时，达到精度要求，所以 x*=4.2000000，也不在0,

53、3区间。根据高等数学的 相关知识，该问题在此区间是单调函数。另外 Newton 切线法和试探法在计算中并没有利用 区间的相关信息，所以这两种方法此时是不适用的。kakbkxkf(ak)f(xk)bk-ak00.00000003.00000001.5000000-3.0000000-12.00000003.000000011.50000003.00000002.2500000-14.2500000-12.00000001.500000022.25000003.00000002.6250000-14.8125000-12.00000000.750000032.62500003.00000002.8

54、125000-13.8281250-12.00000000.375000042.81250003.00000002.9062500-13.0195313-12.00000000.187500052.90625003.00000002.9531250-12.5361328-12.00000000.093750062.95312503.00000002.9765625-12.2746582-12.00000000.0468750kxkf(xk)f(xk)02.2500000-14.81250001.5000000112.1250000292.546875060.750000027.30941366

55、9.569617731.856481535.125568614.307536918.753411544.36263881.746185714.175832654.23945830.045520313.436749764.23607050.000034413.4164233kxkf(xk)h02.2500000-18.73437500.20012.4500000-21.65887500.40022.8500000-27.13587500.80033.6500000-35.25787501.60045.2500000-29.4218750-0.80052.8500000-27.13587500.4

56、0064.0500000-37.13487500.80074.8500000-34.6008750-0.40083.6500000-35.25787500.20094.2500000-37.35937500.400104.6500000-36.1403750-0.200114.0500000-37.13487500.100124.3500000-37.2721250-0.050134.2000000-37.35200000.025144.2750000-37.3504531 黄金分割法：得到此时 x*=(a9+b9)/2=2.9802763。 Fibonacci 法：因为精度 0.05 ，Fn

57、(b+a)/=60，所以取 n=10，计算结果如下：此时 x*=(a10+b10)/2=2.9791667。（2）为了计算简单，取精度 0.05 ， f (x) 3x2 4x 1， f (x) 6x 4 ， 二分法：取 x0=0.5（这是经过反复计算确定的，计算中发现初值的选择对后面的计算影 响很大。 ）易知，x*=0.3281250。但是根据高等数学先关知识，发现改点为 f(x)的一个极大值点，故此 算法在这里不适用或需重新选择初值。 Newton 切线法：取初值 x0=2.25，计算过程如下：kakbkxk1xk2f(xk1)f(xk2)bk-ak10.00000003.00000001.

58、14583331.8541667-2.8107006-12.81560153.000000021.14583333.00000001.85416672.2916667-12.8156015-19.35018811.854166731.85416673.00000002.29166672.5625000-19.3501881-23.25952151.145833342.29166673.00000002.56250002.7291667-23.2595215-25.54981370.708333352.56250003.00000002.72916672.8333333-25.5498137-2

59、6.92129630.437500062.72916673.00000002.83333332.8958333-26.9212963-27.71857820.270833372.83333333.00000002.89583332.9375000-27.7185782-28.23852540.166666782.89583333.00000002.93750002.9583333-28.2385254-28.49486400.104166792.93750003.00000002.95833332.9791667-28.4948640-28.74870700.0625000102.958333

60、33.00000002.97916672.9791667-28.7487070-28.74870700.0416667kakbkxkf(ak)f(xk)bk-ak00.00000003.00000000.50000001.0000000-0.25000003.000000010.00000000.50000000.25000001.00000000.18750000.500000020.25000000.50000000.37500000.1875000-0.07812500.250000030.25000000.37500000.31250000.18750000.04296880.1250