(4/23+5/17)x23x17简便计算
血色蔷薇TA676
(4/23+5/17)x23x17=4/23x23x17+5/17x23x17=4×17+5×23=68+115=183
为您推荐：
其他类似问题
扫描下载二维码当前位置： >>
运筹学习题及答案
运筹学习题答案 第一章（39 页） 1.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最 优解、无界解还是无可行解。 （1）max z = x1 + x2 5 x1 +10 x2 ≤ 50 x1 + x2 ≥ 1 x2 ≤ 4 x1 ， x2 ≥ 0 （2）min z= x1 +1.5 x2 x1 +3 x2 ≥ 3 x1 + x2 ≥ 2 x1 ， x2
≥ 0 （3）max z=2 x1 +2 x2 x1 - x2 ≥ -1 -0.5 x1 + x2 ≤ 2 x1 ， x2 ≥ 0 （4）max z= x1 + x2 x1 - x2 ≥ 0 3 x1 - x2 ≤ -3 x1 ， x2 ≥ 0 解： （1） （图略）有唯一可行解，max z=14 （2） （图略）有唯一可行解，min z=9/4 （3） （图略）无界解 （4） （图略）无可行解 1.2 将下列线性规划问题变换成标准型，并列出初始单纯形表。（1）min z=-3 x1 +4 x2 -2 x3 +5 x 4 4 x1 - x2 +2 x3 - x4 =-2 x1 + x2 +3 x3 - x4 ≤ 14 -2 x1 +3 x2 - x3 +2 x4 ≥ 2 x1 ， x2 ， x3 ≥ 0， x4 无约束 （2）max s =zk = ∑∑ aik xiki =1 k =1 n mzkpk∑ ?xk =1mik= ?1(i = 1,..., n) (i=1…n; k=1,…,m)x5 , x6 ≥ 0xik ≥ 0（1）解：设 z=- z ′ , x 4 = x5 - x6 , 标准型：Max z ′ =3 x1 -4 x2 +2 x3 -5( x5 - x6 )+0 x7 +0 x8 -M x9 -M x10 s. t . -4 x1 + x2 -2 x3 + x5 - x6 + x10 =2x1 + x2 +3 x3 - x5 + x6 + x7 =14-2 x1 +3 x2 - x3 +2 x5 -2 x6 - x8 + x9 =2x1 , x2 , x3 , x5 , x6 , x7 , x8 , x9 , x10 ≥ 0初始单纯形表: 3 cj →CB XB x10 x7-4x22x3-5x55x60x70x8-Mx9-Mx10θib 2 14x1-M 0-4 11 1-2 31 -1-1 10 10 00 01 02 14-Mx9 - z′2 4M-2[3]-12-20-1 -M1 00 02/33-6M 4M-4 2-3M 3M-5 5-3M 0(2)解：加入人工变量 x1 ， x2 ， x3 ，… xn ，得： Max s=(1/ pk ) ∑i=1 n∑k =1mα ik xik -M x1 -M x2 -…..-M xns.t.xi + ∑ xik = 1k =1 m(i=1,2,3…,n) (i=1,2,3…n; k=1,2….,m)xik ≥ 0, xi ≥ 0,CBM 是任意正整数 初始单纯形表： - -M … - a11 cj pk M M … b XB x1 x2 xn x11 1 1 … 1 n M 1 0 0 1 … 0 … 0 … … … … 1 0 … 0a11 +Ma12 x12…pka1m x1mpk… an1 …xn1pkan 2 xn 2…pkamnpkθi……xnm-M -M … -M -sx1 x211 0 … 0a12 +M… … … … … … 0a1m +M… 0 … 0 … … … 1 …an1 +M0 0 … 1an 2 +M… … … … …0 0 … 1amn +M…xn… … 0 0 0 0pkpkpkpkpkpk1.3 在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行 解，并代入目标函数，确定最优解。（1）max z=2 x1 +3 x2 +4 x3 +7 x42 x1 +3 x2 - x3 -4 x4 =8x1 -2 x2 +6 x3 -7 x4 =-3 x1 , x2 , x3 , x4 ≥ 0(2)max z=5 x1 -2 x2 +3 x3 -6 x4x1 +2 x2 +3 x3 +4 x4 =7 2 x1 + x2 + x3 +2 x4 =3 x1 x2 x3 x4 ≥ 0 （1）解： 系数矩阵 A 是： ? 2 3 ?1 ?4 ? ? 1 ?2 6 ?7 ? ? ? 令 A=( P ， P2 ， P3 ， P4 ) 1 P 与 P2 线形无关，以（ P ， P2 ）为基， x1 ， x2 为基变量。 1 1 有 2 x1 +3 x2 =8+ x3 +4 x4 x1 -2 x2 =-3-6 x3 +7 x4 令非基变量 x3 ， x4 =0 解得： x1 =1； x2 =2 基解 X (1) =（1，2，0，0 )T 为可行解 z1 =8 同理，以（ P ， P3 ）为基，基解 X (2) =（45/13，0，-14/13，0 )T 是非可行解； 1 以（ P ， P4 ）为基，基解 X (3) =（34/5，0，0，7/5 )T 是可行解， z3 =117/5； 1 以（ P2 ， P3 ）为基，基解 X (4) =（0，45/16，7/16，0 )T 是可行解， z4 =163/16； 以（ P2 ， P4 ）为基，基解 X (5) =（0，68/29，0，-7/29 )T 是非可行解； 以（ P4 ， P3 ）为基，基解 X (6) =（0，0，-68/31，-45/31 )T 是非可行解； 最大值为 z3 =117/5；最优解 X (3) =（34/5，0，0，7/5 )T 。 （2）解： 系数矩阵 A 是： ?1 2 3 4 ? ?2 1 1 2? ? ?令 A=( P ， P2 ， P3 ， P4 ) 1 P ， P2 线性无关，以（ P ， P2 ）为基，有： 1 1 x1 +2 x2 =7-3 x3 -4 x4 2 x1 + x2 =3- x3 -2 x4 令 x3 ， x4 =0 得 x1 =-1/3， x2 =11/3 基解 X (1) =（-1/3，11/3，0，0 )T 为非可行解； 同理，以（ P ， P3 ）为基，基解 X (2) =（2/5，0，11/5，0 )T 是可行解 z2 =43/5； 1 以（ P ， P4 ）为基，基解 X (3) =（-1/3，0，0，11/6 )T 是非可行解； 1 以（ P2 ， P3 ）为基，基解 X (4) =（0，2，1，0 )T 是可行解， z4 =-1； 以（ P4 ， P3 ）为基，基解 X (6) =（0，0，1，1 )T 是 z6 =-3； 最大值为 z2 =43/5；最优解为 X (2) =（2/5，0，11/5，0 )T 。 1.4 分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步 相当于图形的哪一点。 （1）max z=2 x1 + x2 3 x1 +5 x2 ≤ 15 6 x1 +2 x2 ≤ 24 x1 ， x2 ≥ 0 （2）max z=2 x1 +5 x2 x1 ≤ 4 2 x2 ≤ 12 3 x1 +2 x2 ≤ 18 x1 ， x2 ≥ 0解： （图略） （1）max z=33/4 单纯形法：最优解是(15/4,3/4)标准型是 max z=2 x1 + x2 +0 x3 +0 x4 s.t. 3 x1 +5 x2 + x3 =15 6 x1 +2 x2 + x4 =24 x1 , x2 , x3 , x4 ≥ 0 单纯形表计算：cj CB XB x3 x42 b 15 24 0 3 4 -8 3/4 15/4 -33/4x11x20x30x4θi0 0 -z 0 2 -z 1 2 -z3 [6] 2 0 1 0 0 1 05 2 1 [4] 1/3 1/3 1 0 01 0 0 1 0 0 1/4 -1/12 -1/120 1 0 -1/2 1/6 -1/3 -1/8 5/24 -7/245 4x3 x13/4 12x2 x1解为： （15/4，3/4，0，0 )T Max z=33/4 迭代第一步表示原点；第二步代表 C 点（4，0，3，0 )T ； 第三步代表 B 点（15/4，3/4，0，0 )T 。 （2）解： （图略） Max z=34 此时坐标点为（2，6） 单纯形法，标准型是： Max z=2 x1 +5 x2 +0 x3 +0 x4 +0 x5s.t.x1 + x3 =4 2 x2 + x4 =12 3 x1 +2 x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥ 0 (表略) 最优解 X=（2，6，2，0，0 )TMax z=34 迭代第一步得 X (1) =（0，0，4，12，18 )T 表示原点，迭代第二步得 X (2) =（0，6， 4，0，6 )T ，第三步迭代得到最优解的点。 1.5 以 1.4 题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约 束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。 解：目标函数：max z= c1 x1 + c2 x2 (1)当 c2 ≠ 0 时 x2 =-（ c1 / c2 ） x1 +z/ c2 k AB =-3/5， k BC =-3 k ? k BC 时， 其中，k=- c1 / c2c1，c2同号。当 c2 ? 0 时，目标函数在 C 点有最大值 当 c2 ? 0 时，目标函数在原点最大值。k BC ? ? k AB c c k 时， 1 ， 2 同号。当 c2 ? 0， 目标函数在 B 点有最大值； 当 c2 ? 0，目标函数在原点最大值。k AB ? ? c c k 0 时， 1 ， 2 同号。当 c2 ? 0 时，目标函数在 A 点有最大值 当 c2 ? 0 时，目标函数在原点最大值。c c k ? 0 时， 1 ， 2 异号。当 c2 ? 0，c1 ? 0 时，目标函数在 A 点有最大值；c 当 c2 ? 0， 1 ? 0 时，目标函数在 C 点最大值。k=k ABc c 时， 1 ， 2 同号当 c2 ? 0 时，目标函数在 AB 线断上任一点有最大值 当 c2 ? 0，目标函数在原点最大值。 k=k BC时，c1，c2同号。当 c2 ? 0 时，目标函数在 BC 线断上任一点有最大值 当 c2 ? 0 时，目标函数在原点最大值。c k=0 时， 1 =0当 c2 ? 0 时，目标函数在 A 点有最大值 当 c2 ? 0，目标函数在 OC 线断上任一点有最大值 （2）当 c2 =0 时，max z=c1x1c1 ? 0 时，目标函数在 C 点有最大值c1 c1? 0 时，目标函数在 OA 线断上任一点有最大值=0 时，在可行域任何一点取最大值。1.6 分别用单纯形法中的大 M 法和两阶段法求解下列线性问题， 并指出属于哪类 解。 （1）max z=2 x1 +3 x2 -5 x3 x1 + x2 + x3 ≤ 15 2 x1 -5 x2 + x3 ≤ 24 x1 ， x2 ≥ 0 （2）min z=2 x1 +3 x2 + x3x1 +4 x2 +2 x3 ≥ 8 3 x1 +2 x2 ≥ 6 x1 ， x2 ， x3 ≥ 0 （3）max z=10 x1 +15 x2 +12 x3 5 x1 +3 x2 + x3 ≤ 9 -5 x1 +6 x2 +15 x3 ≤ 15 2 x1 + x2 + x3 ≥ 5 x1 ， x2 ， x3 ≥ 0 （4）max z=2 x1 - x2 +2 x3 x1 + x2 + x3 ≥ 6 -2 x1 + x3 ≥ 2 2 x2 - x3 ≥ 0 x1 ， x2 ， x3 ≥ 0 解： （1）解法一：大 M 法 化为标准型： Max z=2 x1 +3 x2 -5 x3 -M x4 +0 x5 -M x6 s.t. x1 + x2 + x3 + x4 =7 2 x1 -5 x2 + x3 - x5 + x6 =10 x1 , x2 , x3 , x5 , x4 , x6 ≥ 0 单纯形表：cj CB XB x4M 是任意大整数。 3x22 b 7x1-5x3-Mx40x5-Mx6θi-M1111007-M -z -M 2 -z 3 2 -zx610 17M 2 5[2]-51 2M-5 1/2 1/20 0 1 0-1 -M 1/2 -1/21 0 -1/2 1/25x4 x13M+2 3-4M 0 [7/2] 1 -5/24/7 -2M-10 0 x2 x1 4/7 45/7 -102/7 0 1 0(7/2)M+8 0.5M-6 0 1 0 0 1/7 6/7 -50/7 2/7 5/70.5M+1 -1.5M-1 1/7 -1/7 -1/7 1/7 -M+1/7-M-16/7 -1/7最优解是： X=（45/7，4/7，0，0，0 )T 目标函数最优值 有唯一最优解。 解法二： max z=102/7第一阶段数学模型为 min w= x4 + x6 S.t. x1 + x2 + x3 + x4 =7 2 x1 -5 x2 + x3 - x5 + x6 =10 x1 , x2 , x3 , x4 ， x5 , x6 ≥ 0 （单纯形表略） 最优解 X=（45/7，4/7，0，0，0 )T 目标函数最优值 min w=0 第二阶段单纯形表为： 2 cj CB 3 2 XB x2 x1 b 4/7 45/7 x1 0 13 x2 1 0-5 x3 1/7 6/70 x5 1/7 -1/7θi-z 最优解是-102/700-50/7-1/7X=（45/7，4/7，0，0，0 )T Max z=102/7 （2）解法一：大 M 法 z ′ =-z 有 max z ′ =-min （- z ′ ）=-min z 化成标准形： Max z ′ =-2 x1 -3 x2 - x3 +0 x4 +0 x5 -M x6 -M x7 S.T. x1 +4 x2 +2 x3 - x4 + x6 =4 3 x1 +2 x2 - x5 + x7 =6 x1 , x2 , x3 , x4 ， x5 , x6 ， x7 ≥ 0 （单纯性表计算略） 线性规划最优解 X=（4/5，9/5，0，0，0 ，0 )T 目标函数最优值 min z=7 非基变量 x3 的检验数 σ 3 =0，所以有无穷多最优解。 两阶段法： 第一阶段最优解 X=（4/5，9/5，0，0，0，0 )T 是基本可行解,min w=0 第二阶段最优解（4/5，9/5，0，0，0，0 )T min z=7 非基变量 x3 的检验数 σ 3 =0，所以有无穷多最优解。 （3）解：大 M 法 加入人工变量，化成标准型： Max z=10 x1 +15 x2 +12 x3 +0 x4 +0 x5 +0 x6 -M x7 s.t. 5 x1 +3 x2 + x3 + x4 =9 -5 x1 +6 x2 +15 x3 + x5 =15 2 x1 + x2 + x3 - x6 + x7 =5 x1 , x2 , x3 , x4 ， x5 , x6 ， x7 ≥ 0 单纯形表计算略当所有非基变量为负数，人工变量 x7 =0.5，所以原问题无可行解。 两阶段法（略） （4）解法一：大 M 法 单纯形法， （表略） 非基变量 x4 的检验数大于零， 此线性规划问题有无界解。 两阶段法略 1.7 求下述线性规划问题目标函数 z 的上界和下界； Max z= c1 x1 + c2 x2 a11 x1 + a12 x2 ≤ b1 a21 x1 + a22 x2 ≤ b2 其中： ≤ c1 ≤ 3 ， ≤ c2 ≤ 6 ， ≤ b1 ≤ 12 ， ≤ b2 ≤ 14 ， 1 ≤ a11 ≤ 3 ， ≤ a12 ≤ 5 ， 1 4 8 10 ? 2 2 ≤ a21 ≤ 4 ， 4 ≤ a22 ≤ 6 解： 求 Z 的上界 Max z=3 x1 +6 x2 s.t. - x1 +2 x2 ≤ 12 2 x1 +4 x2 ≤ 14 x2 ， x1 ≥ 0 加入松弛变量，化成标准型，用单纯形法解的，最优解 X=（0，7/2，5，0 )T 目标函数上界为 z=21 存在非基变量检验数等于零，所以有无穷多最优解。 求 z 的下界 线性规划模型： Max Z= x1 +4 x2 s.t. 3 x1 +5 x2 ≤ 8 4 x1 +6 x2 ≤ 10 x2 ， x1 ≥ 0 加入松弛变量，化成标准型，解得：最优解为 X=（0，8/5，0，1/5 )T 目标函数下界是 z=32/5 1.8 表 1-6 是某求极大化线性规划问题计算得到的单纯形表。表中无人工变 量， a1 ， a2 ， a3 c c ，d， 1 ， 2 为待定常数，试说明这些常数分别取何值时，以下结论成立。 （1）表中解为唯一最优解； （2）表中解为最优解，但存在无穷多最优解； （3） 该线性规划问题具有无界解； 表中解非最优， （4） 对解改进， 换入变量为 x1 ， 换出变量为 x6 。 基b x3 x4 x6 d 2 3 x1 4 -1 a3c1x2x3 1 0 0 0x4 0 1 0 0x5 a2 -1 -4 -3x6 0 0 1 0a1-3 -5c2cj ? zj解： （1）有唯一最优解时，d ≥ 0， c1 ? 0， c2 ? 0 （2）存在无穷多最优解时，d ≥ 0， c1 ≤ 0， c2 =0 或 d ≥ 0， c1 =0， c2 ≤ 0. （3）有无界解时，d ≥ 0， c1 ≤ 0， c2 ? 0 且 a1 ≤ 0 （4）此时，有 d ≥ 0， c1 ? 0 并且 c1 ≥ c2 ， a3 ? 0 ，3/ a3 ? d/4 1.9 某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下： 班次 时间 所需人数 1 6 点到 10 点 60 2 10 点到 14 点 70 3 14 点到 18 点 60 4 18 点到 22 点 50 5 22 点到 2 点 20 6 2 点到 6 点 30 设司机和乘务人员分别在各时间区段一开始时上班，并连续上班 8 小时，问该公 交线路至少配备多少司机和乘务人员。列出线型规划模型。解 ： 设 xk （k=1，2，3，4，5，6）为 xk 个司机和乘务人员第 k 班次开始上班。 建立模型： Min z= x1 + x2 + x3 + x4 + x5 + x6 s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 1.10 某糖果公司厂用原料 A、B、C 加工成三种不同牌号的糖果甲乙丙，已知各 种糖果中 ABC 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单 位加工费用及售价如表所示： 原料 甲 乙 丙 原 料 每 月 成本（元/ 限 制 用 量 （千克） 千克） A ≥ 60% ≥ 15% 2 2000 B 1.5 2500 C ≤ 20% ≤ 60% ≤ 50% 1 1200 加工费 0.5 0.4 0.3 售价 3.4 2.85 2.25 问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模 型。 解: 解：设 x1 ， x2 ， x3 是甲糖果中的 A，B，C 成分， x4 ， x5 ， x6 是乙糖果的 A， B，C 成分， x7 ， x8 ， x9 是丙糖果的 A，B，C 成分。 线性规划模型： Max z=0.9 x1 +1.4 x2 +1.9 x3 +0.45 x4 +0.95 x5 +1.45 x6 -0.05 s.t. -0.4 x1 +0.6 x2 +0.6 x3 ≤ 0x7+0.45x8+0.95x9-0.2 x1 -0.2 x2 +0.8 x3 ≤ 0 -0.85 x4 +0.15 x5 +0.15 x6 ≤ 0 -0.6 x4 -0.6 x5 +0.4 x6 ≤ 0 -0.7x7-0.5x8+0.5x9≤0x1 + x4 + x2 + x5 +x7≤ 2000x8≤ 2500 ≤ 1200x3 + x6 +x9x1 , x2 , x3 , x4 , x5 , x6 ,x7 x8 x9 , , ≥01.11 某厂生产三种产品 I、∏ 、III。每种产品经过 AB 两道加工程序，该厂 有两种设备能完成 A 工序，他们以 A1 , A2 表示；有三种设备完成 B 工序，分别为 B1 ， B2 ， B3 ；产品 I 可以在 AB 任何一种设备上加工，产品 ∏ 可以在任何规格 的 A 设备上加工，但完成 B 工序时，只能在 B1 设备上加工；产品 III 只能在 A2 ， B2 上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化。 设备 A1 A2 B1 B2 B3 原料费 单价 解： 产品 1，设 A1 , A2 完成 A 工序的产品 x1 ， x2 件；B 工序时， B1 , B2 ， B3 完成 I 5 7 6 4 7 0.25 1.25 0.35 2.00 0.5 2.8 II 10 9 8 11 产品 III 设备有效台 满负荷时的 时 设备费用 00 00 321 250 783 20012B 工序的 x3 ， x4 ， x5 件，产品 ∏ ，设 A1 , A2 完成 A 工序的产品 x6 ， x7 件；B 工 序时， 工序的B1 x9完成 B 的产品为 件；x8件；产品 111，A2完成 A 工序的x9件，B2完成 Bx1 + x2 = x3 + x4 + x5 x6 +x7=x8建立数学模型： Max z=(1.25-0.25)*( x1 + x2 )+(2-0.35)*( x6 + x6 )300/ +9x7)+(2.8-0.5)x9-(5 x1 +10x7+12x9)321/1 +8x8)250/ +11x9)783/ *200/4000 s.t 5 x1 +10 x6 ≤
+9 6 x3 +8 4 x4 +11x7 x8+12x9≤ 10000≤ 4000 ≤ 7000x97 x5 ≤ 4000 x1 + x2 = x3 + x4 + x5 x6 +x7=x8 x7 x8 x9 , , ≥0x1 , x2 , x3 , x4 , x5 , x6 ,最优解为 X=（，0，859，571，0，500，500，324 )T 最优值 1147. 试题： 试题： 1. （2005 年华南理工大学）设某种动物每天至少需要 700 克蛋白质、30 克矿物 质、100 毫 克维生素。现有 5 种饲料可供选择，每种饲料每公斤营养成分的含量及单价 如下表所示： 试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模 型。维生素 （毫克） 价格（元/公 斤） 1 3 1 0.5 0.2 2 2 0.5 1 0.7 3 1 0.2 0.2 0.4 4 6 2 2 0.3 5 18 0.5 0.8 0.8 解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可。 解题过程： min z = 0.2 x1 + 0.7 x2 + 0.4 x3 + 0.3 x4 + 0.8 x5饲料蛋白质（克）表 1―1 矿物质（克）? 3 x1 + 2 x2 + x3 + 6 x4 + 18 x5 ≥ 700 ? x + 0.5 x + 0.2 x + 2 x + 0.5 x ≥ 30 ? 2 3 4 5 s.t. ? 1 ?0.5 x1 + x2 + 0.2 x3 + 2 x4 + 0.8 x5 ≥ 100 ? x1 , x2 , x3 , x4 , x5 ≥ 0 ?第二章（ 第二章（67 页） 2.1 用改进单纯形法求解以下线性规划问题。 （1）Max z=6 x1 -2 x2 +3 x3 ） 2 x1 - x2 +3 x3 ≤ 2 x1 +4 x3 ≤ 4 x1 ， x2 ， x3 ≥ 0 （2）min z=2 x1 + x2 3 x1 + x2 =3 4 x1 +3 x2 ≥ 6 x1 +2 x2 ≤ 3 x1 , x2 ≥ 0 解： （1） ） 先化成标准型： Max z=6 x1 -2 x2 +3 x3 +0 x4 +0 x5 s.t. 2 x1 - x2 +2 x3 + x4 =2x1 +4 x3 + x5 =4 x1 , x2 , x3 , x4 , x5 ≥ 0 ?1 0? 令 B0 =（ P4 ， P5 ）= ? ? ?0 1? ? 2 ?1 2 ? N 0 =( P , P2 , P3 )= ? 1 ? ?1 0 4?X B0 =（ x4 , x5 )T , CB0 =(0,0), X N0 =（ x1 ， x2 ， x3 )T?1 0? ? 2? C N0 =(6,-2,3)， B0 ?1 = ? ? , b0 = ? ? ?0 1? ? 4? 非基变量的检验数σN =0CN0 CB0 B0 ?1 N 0 CN0 = =(6,-2,3)因为 x1 的检验数等于 6，是最大值，所以， x1 为换入变量， ? 2? ? 2? B ?10 b0 = ? ? ； B ?10 P = ? ? 1 ? 4? ?1? 由 θ 规则得： θ =1x4 为换出变量。? 2 0? T B1 =( P4 ， P5 )= ? ? , X B1 =（ x1 , x5 ) ， CB1 =(6,0). ?1 1?N1 =( P4 , P2 , P3 ), X N1 =（ x4 ， x2 ， x3 )T? 0.5 0 ? ?1? CN1 =(0，-2，3)， B1?1 = ? ? , b1 = ? ? ? ?0.5 1 ? ? 3? 非基变量的检验数 σ N1 =（-3，1，-3） 因为 x2 的检验数为 1，是正的最大数。所以 x2 为换入变量； ? ?0.5 ? B ?10 P2 = ? ? ? 0.5 ? 由 θ 规则得： θ =6 所以 x5 是换出变量。? 2 ?1 ? T B2 =( P ， P2 )= ? 1 ? , X B2 =（ x1 , x2 ) ， CB2 =(6,-2). 1 0? ?N 2 =( P4 , P5 ， P3 ), X N2 =（ x4 ， x5 ， x3 )T? 0 1? ? 4? C N2 =(0，0，3)， B2 ?1 = ? ? , b2 = ? ? ? ?1 2 ? ?6? 非基变量的检验数 σ N 2 =（-2，-2，-9） 非基变量的检验数均为负数，愿问题已达最优解。 ? 4? 最优解 X= ? ? ?6? 即：X=（4,6,0 )T 目标函数最优值 max （2） ） 解 ： z=12Min z=2 x1 + x2 +0 x3 +M x4 +M x5 +0 x6 S.T. 3 x1 + x2 + x4 =3 4 x1 +3 x2 - x3 + x5 =6x1 +2 x2 + x6 =3 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0M 是任意大的正数。 （非基变量检验数计算省略） 原问题最优解是 X=（0.6，1.2，0） 目标函数最优值： z=12/5 2.2 已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见 表，试将空白处数字填上。 3 5 4 0 0 0 cjCB XB x2 x5b 8/3 14/3x1x2x3x4x5x65 02/3 -4/31 00 51/3 -2/30 10 00x6cj - z j20/35/3 -1/30 0 . . .4 4-2/3 -5/30 01 0x2 x3 x1cj - z j15/41 -6/41 -2/418/41 5/41 -12/41-10/41 4/41 15/41解：cj3 b 8/3 14/3 20/3x15x24x30x40x50x6CBXB x2 x5 x6cj - z j5 0 0. . . 5 4 3x2 x3 x1cj - z j80/41 50/41 44/410 0 1 01 0 0 00 1 0 015/41 -6/41 -2/41 -45/412.3 写出下列线性规划问题的对偶问题。 （1）min z= 2 x1 +2 x2 +4 x3 ）2 x1 +3 x2 +5 x3 ≥ 2 3 x1 + x2 +7 x3 ≤ 3 x1 +4 x2 +6 x3 ≤ 5 x1 , x2 , x3 ≥ 0 （1） 解：对偶问题是： Max w=2 y1 -3 y2 -5 y3 s.t. 2 y1 -3 y2 - y3 ≤ 2 3 y1 - y2 -4 y3 ≤ 2 5 y1 -7 y2 -6 y3 ≤ 4 y1 , y2 , y3 ≥ 0 (2)max z= x1 +2 x2 +3 x3 +4 x4 - x1 + x2 - x3 -3 x4 =5 6 x1 +7 x2 +3 x3 -5 x4 ≥ 8 12 x1 -9 x2 -9 x3 +9 x4 ≤ 20 x1 , x2 ≥ 0; x3 ≤ 0; x4 无约束 解： 对偶问题： Min w=5 y1 +8 y3 +20 S.t. - y1 +6 y3 +12 y1 +7 y3 -9y4y4 ≥ 1y4 ≥ 2 y4≤3 =4- y1 +3 y3 -9-3 y1 -5 y3 +9y4y1 无约束， y3 ≤ 0；m ny4 ≥ 0（3）min z= ∑∑ cij xiji ?1 j =1∑xj =1mnij= aii=1,…,m∑xi =1ij= bjj=1,…,nxij ≥ 0解：'' 对偶问题: max w= ∑ ai yi'' + ∑ b j ym + ji =1 j =1 m n'' s.t. yi'' + ym + j ≤ cijyi'' , ym + j 无约束 i=1,2,….m; j=1,2,….n(4) Max z= ∑ c j x jj =1 n''∑a xj =1 n ijnj≤ bi , i=1,…., m1 ≤ m∑a xj =1 ijj= bi , i= m1 + 1, m1 + 2,..., mx j ≥ 0,当 j=1，….， n1 ≤ nxj无约束，当 j= n1 + 1,..., nm解： Min w= ∑ b j yi''i =1s.t.∑ai =1mijyi'' ≥ c jj=1,2,3… n1∑ai =1mijyi'' ≥ c jj=n1+1,n1+2,….nyi'' ≥ 0i=1,2…. m1yi'' 无约束， i= m1 +1, m1 +2….m2.4 判断下列说法是否正确，并说明为什么. (1)如线性规划问题的原文题存在可行解， 则其对偶问题也一定存在可行解。 （2）如线性规划的对偶问题无可行解，则原问题也一定无可行解。 （3）如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划 问题一定有有限最优解。 (1)错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在； （2） 错误， 对偶问题没有可行解， 原问题可能有可行解也可能有无界解； （3）错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能 有无界解； 2.5 设线性规划问题 1 是： Max z1 = ∑ c j x jj =1 n∑a xj =1 ijnj≤ bi，i=1，2…，mx j ≥ 0, j = 1, 2...., n* （ y1* ,..., ym ）是其对偶问题的最优解。又设线性规划问题 2 是Max z2 = ∑ c j x jj =1 n∑a xj =1 ijnj≤ bi + ki ，i=1，2…，mx j ≥ 0, j = 1, 2...., n 其中 ki 是给定的常数，求证：max z2 ≤ max z1 + ∑ ki yi*i =1m解： 证明：把原问题用矩阵表示：Max z1 =CX s.t. AX ≤ b X≥0b=（ b1 , b2 ... bm )T 设 可行解为 X 1 ,对偶问题的最优解 Y1 =（ y1 ， y2 … ym ）已知。 Max z2 =CX s.t. AX ≤ b+k X≥0k=（ k1 , k2 ... km )T 设可行解为 X 2 ，对偶问题最优解是 Y2 ,对偶问题是， Min w=Y(b+k) S.t. YA ≥ C Y ≥0 因为Y2是最优解，所以Y2（b+k） ≤ Y1 （b+k）X2是目标函数 z2 的可行解，AX2≤ b+k ；Y2AX2≤Y2（b+k）≤ Y1 b+Yk原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。2.6 已知线性规划问题 Max z= c1 x1 + c2 x2 + c3 x3? a11 ? ? a ? x1 + ? 21 ?? a12 ? ? a ? x2 + ? 22 ?? a13 ? ? a ? x3 + ? 23 ??1 ? ?0 ? x4 + ? ?? b1 ? ?0? ?1 ? x5 = ?b ? ? ? ? 2?x j ≥ 0, j = 1,...,5用单纯形法求解，得到最终单纯形表如表所示，要求： （1） 求 a11 ， a12 ， a13 ， a21 ， a22 ， a23 ， b1 ， b2 的值； （2） 求 c1 , c2 , c3 的值；XBx3 b x1 x2 x3 x4 x53/21011/2-1/2x2cj ? zj21/2 -31 00 0-1 02 -4解： （1）初始单纯形表的增广矩阵是：? a11 C1 = ? ? a21a12 a22a13 a231 0 b1 ? 0 1 b2 ? ?最终单纯形表的增广矩阵为 ? 1 0 1 0.5 ?0.5 1.5? C2 = ? 2 2? ?0.5 1 0 ?1 ?C2是C1作初等变换得来的，将 的单位矩阵。有：C2作初等变换，使得C2的第四列和第五列的矩阵成为C2a11 =9/2； a12 =1； a13 =4； a21 =5/2； a22 =1； a23 =2； b1 =9； b2 =5由检验计算得：c1 =-3； c2 = c3 =02.7 已知线性规划问题 Max z=2 x1 + x2 +5 x3 +6 x4 s.t. 2 x1 + x3 + x4 ≤ 8 2 x1 +2 x2 + x3 +2 x4 ≤ 12x j ≥ 0，j=1,…4* * 对偶变量 y1 ， y2 ，其对偶问题的最优解是 y1 =4， y2 = 1 ，试应用对偶问题的性质，求原问题的最优解。 解： 对偶问题是：Min w=8 y1 +12 y2 s.t. 2 y1 +2 y2 ≥ 2 2 y2 ≥ 1y1 + y2 ≥ 5 y1 +2 y2 ≥ 6 y1 ， y2 ≥ 0? ? ? 互补松弛性可知，如 X ，Y 是原问题和对偶问题的可行解，那么，Y X S =0和? ? ? YS X =0，当且仅当 X ， Y 是最优解。设 X,Y 是原问题和对偶问题的可行解， YS =（ y3 ， 有：Yy4， y5 ， y6 ）XS=0; 且 YS X=0x5 = x6 =0，原问题约束条件取等号， x3 =4； x4 =4最优解 X=（0，0，4，4 )T 目标函数最优值为 44。2.8 试用对偶单纯形法求解下列线性规划问题。（1）min z= x1 + x2 ）2 x1 + x2 ≥ 4 x1 +7 x2 ≥ 7 x1 , x2 ≥ 0 (2) min z=3 x1 +2 x2 + x3 +4 x4 2 x1 +4 x2 +5 x3 + x4 ≥ 0 3 x1 - x2 +7 x3 -2 x4 ≥ 2 5 x1 +2 x2 + x3 +10 x4 ≥ 15 x1 , x2 , x3 , x4 ≥ 0解： （1 ） 取 w=-z，标准形式：Max w=- x1 - x2 +0 x3 +0 x4 s.t. -2 x1 - x2 + x3 =-4 - x1 -7 x2 + x4 =-7 x1 ， x2 ， x3 ， x4 ≥ 0 单纯形法求解（略） ： 最优解： X=（21/13，10/13，0，0 )T 目标函数最优值为 31/13。 （2）令：w=-z，转化为标准形式： Max w=-3 x1 -2 x2 - x3 -4 x4 +0 x5 +0 x6 +0 x7 s.t. -2 x1 -4 x2 -5 x3 - x4 + x5 =0 -3 x1 + x2 -7 x3 +2 x4 + x6 =-2 -5 x1 -2 x2 - x3 -6 x4 + x7 =-15 x1 ， x2 ， x3 ， x4 ， x5 ， x6 ， x7 ≥ 0 单纯形法略 原问题最优解： X=（3，0，0，0，6，7，0 )T 目标函数最优值为 9。 2.9 现有线性规划问题 max z=- 5 x1 +5 x2 +13 x3 - x1 + x2 +3 x3 ≤ 20 12 x1 +4 x2 +10 x3 ≤ 90 x1 ， x2 ， x3 ≥ 0 先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什 么变化？ （1） 约束条件 1 的右端常数 20 变为 30（2） 约束条件 2 的右端常数 90 变为 70 （3） 目标函数中 x3 的系数变为 8 ? ?1 ? （4） x1 的系数向量变为 ? ? ? 12 ? （5） 增加一个约束条件 2 x1 +3 x2 +5 x3 ≤ 50 （6） 将约束条件 2 变为 10 x1 +5 x2 +10 x3 ≤ 100 解： 把原问题化成标准型的： Max z=-5 x1 +5 x2 +13 x3 +0 x4 +0 x5 s.t - x1 + x2 +3 x3 + x5 =20 12 x1 +4 x2 +10 x3 + x5 =90 x1 ， x2 ， x3 ， x4 ， x5 ≥ 0 单纯形法解得： 最优解： X=（0，20，0，0，10 )T 目标函数最优值为 100。 非基变量 x1 的检验数等于 0，原线性问题有无穷多最优解。 （1）约束条件 θ 的右端常数变为 30 有 ?b′ = B ?1?b 因此 b′ = b + ?b′ 单纯形法解得： 最优解： X=（0，0，9，3，0 )T 目标函数最优值为 117。 2 （2）约束条件○右端常数变为 70 有 ?b′ = B ?1?b 因此 b′ = b + ?b′ 单纯形法解得，最优解： X=（0，5，5，0，0 )T目标函数最优值为 90。 （3） x3 的系数变成 8， x3 是非基变量，检验数小于 0，所以最优解不变。 ? 0? （4） x1 的系数向量变为 ? ? ? 5? x1 是非基变量，检验数等于-5，所以最优解不变。 3 （5）解：加入约束条件○ 用对偶单纯形表计算得： X=（0，25/2，5/2，0，15，0 )T 目标函数最优值为 95。 （6）改变约束条件， P3 , P4 , P5 没有变化， 线性规划问题的最优解不变。 2.10 已知某工厂计划生产 I,II,III 三种产品，各产品在 ABC 设备上加工，数 据如下表， 设备代号 I II III 每月设备 有效台时 A 8 2 10 300 B 10 5 8 400 C 2 13 10 420 2 2.9 单位产品利润 3 /千元 千元 （1）如何充分发挥设备能力，使生产盈利最大？ （2）如果为了增加产量，可借用其他工厂的设备 B，每月可借用 60 台时， 租金为 1.8 万元，问借用是否合算？ （3） 若另有两种新产品 IV,V， 其中 IV 为 10 台时， 单位产品利润 2.1 千元； 新产品 V 需用设备 A 为 4 台时，B 为 4 台时，C 为 12 台时，单位产品盈利 1.87 千元。如 A,B,C 设备台时不增加，分别回答这两种新产品投产在经济上是否划 算？ （4）对产品工艺重新进行设计，改进结构，改进后生产每件产品 I，需要 设备 A 为 9 台时， 设备 B 为 12 台时， 设备 C 为 4 台时， 单位产品利润 4.5 千元， 问这对原计划有何影响？ 解： （1）设：产品三种产品的产量分别为， x1 ， x2 ， x3 ，建立数学模型： Max z=3 x1 +2 x2 +2.9 x3 s.t.8 x1 +2 x2 +10 x3 ≤ 300 10 x1 +5 x2 +8 x3 ≤ 400 2 x1 +13 x2 +10 x3 ≤ 420 x1 , x2 , x3 ≥ 0 把上述问题化为标准型，用单纯形法解得： 最优解： X=（338/15，116/5，22/3，0，0，0 )T 目标函数最优值为 2029/15。 （2） 设备 B 的影子价格为 4/15 千元/台时，借用设备的租金为 0.3 千元每台时。 所以，借用 B 设备不合算。 （3） 设备 ΙV ,V 生产的产量为 x7 ， x8 ，系数向量分别为：P7 = (12,5,10)T P8 = (4, 4,12)T检验数 σ 7 =-0.06，所以生产 ΙV 不合算，σ 8 =37/300，生产 V 合算。单纯形法计算得： 最优解：X=（107/4，31/2，0，0，0，0，55/4 )T目标函数最优值为 10957/80。 （4）改进后,检验数 σ 1′ =253/300，大于零。 所以，改进技术可以带来更好的效益。2.11 分析下列参数规划中当 t 变化时最优解的变化情况。（1）Max z(t ) =(3-6t) x1 +(2-2t) x2 +(5-5t) x3 (t ≥ 0) ）s.t. x1 +2 x2 + x3 ≤ 430 3 x1 +2 x3 ≤ 460x1 +4 x2 ≤ 420 x1 ， x2 ， x3 ≥ 0 （2）Max z( t ) =(7+2t) x1 +(12+t) x2 +(10-t) x3 (t ≥ 0) s.t. x1 + x2 + x3 ≤ 20 2 x1 +2 x2 + x3 ≤ 30 x1 ， x2 ， x3 ≥ 0 （3）Max z( t ) =2 x1 + x2 (0 ≤ t ≤ 25) s.t. x1 ≤ 10+2t x1 + x2 ≤ 25-t x2 ≤ 10+2t x1 ， x2 ≥ 0 （4）Max z( t ) =21 x1 +12 x2 +18 x3 +15 x4 (0 ≤ t ≤ 59) s.t. 6 x1 +3 x2 +6 x3 +3 x4 ≤ 30+t 6 x1 -3 x2 +12 x3 +6 x4 ≤ 78-t 9 x1 +3 x2 -6 x3 +9 x4 ≤ 135-2t x1 ， x2 ， x3 ， x4 ≥ 0 解： （1）化成标准形式： Max z(t ) =(3-6t) x1 +(2-2t) x2 +(5-5t) x3 +0 x4 +0 x5 +0 x6 (t ≥ 0) s.t.x1 +2 x2 + x3 + x4 =4303 x1 +2 x3 + x5 =460x1 +4 x2 + x6 =420 x1 ， x2 ， x3 ， x4 ， x5 , x6 ≥ 0 令 t=0，用单纯形表计算， 3-6t 2-2t cj CB 2-2t 5-5t 0 -z XB x2 x3 x6 B 100 230 20 1350t -/4 3/2 2 t-4 x2 1 0 0 0 5-5t x3 0 1 0 0 0 x4 0.5 0 -2 t-1 0 x5 -1/4 1/2 [1] 2t-2 0 x6 0 0 1 0 460 20θit 增大，t 大于 1，首先出现 σ 4 ， σ 5 大于 0，所以当 0 ≤ t ≤ 1 时有最优解。 X=（0，100，230，0，0，20 )T 目标函数最优值为 1350（t-1） t=1 是第一临界点。 t 大于 1 时， x6 是换出变量。 t 大于 1，最优解是：X=（0，0， 0，430，460，420 )T 目标函数最优值为 Max z(t ) =0， （t 大于 1） （0 ≤ t ≤ 1） 。（2） 化成标准型，然后令 t=0，单纯形法解得： t 开始增大时，当 t 大于 8/3 时，首先出现 优解。 目标函数最优值 Max z( t ) =220， ≤ t ≤ 8/3） （0 所以，t=8/3 为第一临界点。 当 8/3&t&5 时，σ4大于 0，所以 0 ≤ t ≤ 8/3，得最σ4为换入变量，由 θ 规则， x3 为换出变量，使用单纯形法继续迭代，t 继续增大，当 t&5，首先 σ 1 大于 0，8/3&t ≤ 5 的时候，最优解为：X=（0，15，0，5 )T 目标函数最优值为 180+15t 所以，t=5 为第二临界点。 ， （8/3&t ≤ 5） 。当 t&5 时， x1 是换入变量， x2 为换出变量，单纯性法计算， 当 t 继续增大，所有检验数都非正，所以当 t&5，最优解： X=（15，0，0，5 )T 目标函数最优值为 105+30t， t〉0 (3)化成标准型，令 t=0,用单纯形法计算得： 当 t 开始增大，t 大于 5 时，首先出现 b2 小于 0，当 0 ≤ t ≤ 5，最优解为： X=（10+2t，0，10+2t，5-t，0 )T 目标函数最优值为 6t+30 所以 t=5 是第一临界点。 ， ≤ t ≤ 5） （0 。当 t 大于 5 时， x4 是换出变量， x5 是换入变量。用对偶单纯形法计算， 当 t 大于 5 时，最优解为： X=（10+2t，15+t，0，0，t-5 )T 目标函数最优值为 35+5t。 （4）解： 先化为标准型，令 t=0，用单纯形法计算，得： 当 t 开始增大，当 t 大于 6 时，首先出现 b2 小于 0，当 0 ≤ t ≤ 6，有最优解： X=（0，0，0，10+t/3，0，18-3t，45-5t )T 目标函数最优值为 150+5t （0 ≤ t ≤ 6） 。当 t 大于 6 时，首先出现 b2 小于 0， x6 是换出变量， x2 是换入变量，使用单 纯形法计算得：t 继续增大，当 t 大于 11 时， b3 首先小于零， x7 是换出变量， x3 为换入变量，对偶单纯形法迭代得： 当 t≤59，有最优解： X=（0，t/3-2，t/8-11/8，59/4-t/4，0，0，0 )T 目标函数最优值为 5t/2+345/2 ， （11&t≤59） 。 试题： 试题： 1. （2006 年西北工业大学）已知线性规划： max z = 3 x1 + 2 x2? ? x1 + 2 x2 ≤ 4 ?3 x + 2 x ≤ 12 ? 2 s.t. ? 1 x1 ? x2 ≤ 3 ? ? x1 , x2 ≥ 0 ?（1） 用单纯形法求解该线性规划问题的最优解和最优值； （2） 写出线性规划的对偶问题； （3） 求解对偶问题的最优解和最优值。 解题分析：本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。?18 解题过程： X = ? ?5*3 532 5? 0 0? ?Tmax z = 12 ，有无穷多解。 对偶问题为： min w = 4 y1 + 12 y2 + 3 y3? ? y1 + 3 y2 + y3 ≥ 3 ? s.t. ? 2 y1 + 2 y2 ? y3 ≥ 2 ? y ,y ,y ≥0 1 2 3 ?Y * = [ 0 1 0]w* = z * = 122. （2005 年东南大学）写出如下线性规划问题的对偶问题： max z = x1 + 2 x2 + x3? x1 + x2 ? x3 ≤ 2 ? x ? x + x =1 ? s.t. ? 1 2 3 ?2 x1 ? x2 + x3 ≥ 2 ? x1 ≥ 0, x2 ≤ 0, x3 无限制 ? 并利用弱对偶性说明 z 的最大值不大于 1。 解题过程：原问题的对偶问题为：min w = 2 y1 + y2 + 2 y3? y1 + y2 + 2 y3 ≥ 1 ? y ?y +y ≤2 ? 3 s.t. ? 1 2 ?? y1 + y2 + y3 = 1 ? y1 ≥ 0, y3 ≤ 0, y2 ? 由于（0，1，0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的 任一可行解X 都有C X ≤ Yb?2? 而 Yb = [ 0 1 0] ?1 ? = 1 ，所以 z 的最大值不大于 1。 ? ? ?2? ? ?第三章（ 第三章（86 页） 3.1 判断表中给出的调运方案能否作为用表上作业法求解时的最初解？为 什么？ 表 3―1 销 地 1 2 3 4 产量 产地1 2 3 销量 表 3―2 销 1 地 产地 1 2 3 4 5 销量0 5 5 215 15 15 3 15 4 10 10 515 25 5产量150 200 90 240 210 410 550 300 250250 50 80 330 20 70400 500 300 300 100解： 表 3―1 中， 5 个数字格， 有 作为初始解， 应该有 m+n-1=3+4-1=6 个数字格， 所以表 3-1 的调运方案不能作为用表上作业法求解时的初始解。 表 3-2 中，有 10 个数字格，而作为初始解，应该有 m+n-1=9 个数字格，所 以表 3-2 的调运方案不能作为表上作业法的初始解。 3.2 表 3-3 和表 3-4 中分别给出两个运输问题的产销平衡表和单位运价表， 试用 伏格尔法直接给出近似最优解。 表 3-3 销地 1 2 3 产量 产地 1 5 1 8 12 2 2 4 1 14 3 3 6 7 4 销量 9 10 11表 3-4 1 销 地 产地 1 2 3 4 销量2345产量10 5 15 20 202 20 5 15 203 15 14 13 3015 2 7 M 109 4 15 8 2525 30 20 30解： （1）在表 3-3 中分别计算出各行和各列的次最小运费和最小运费的差额， 填入该表的最右列和最下列。得到： 销地 1 2 3 行差额 产地 1 5 1 8 4 2 2 4 1 1 3 3 6 7 3 列差额 1 3 6 从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最小元素， 上表中，第三列是最大差额列，此列中最小元素为 1，由此可以确定产地 2 的产 品应先供应给销售地 3，得到下表： 销地 产量 1 2 3 产地 1 2 3 销量11 9 10 同时将运价表第三列数字划去，得 销地 1 2 1112 14 4产量产地 5 1 12 2 4 14 3 6 4 9 10 对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入 该表的最右列和最下列，重复上面的步骤，直到求出初始解，最终结果是： 1 2 3 销量销地 产地123产量2 10 12 3 11 14 4 4 9 10 11 （2）3-4 分别计算出各行和各列的次最小运费和最小运费的差额，填入该 表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者 列中的最小元素。 （方法同 3-3 相同） 最终得出原问题的初始解： 1 2 3 4 5 销地 产量 产地 1 2 3 4 销量 20 25 30 20 301 2 3 销量20 20 30 10 25 3.3 用表上作业法求给出运输问题的最优解（M 是任意大正数） （1） ） 销地 甲 乙 丙 丁 产量产地 1 2 3 销量 解：3 2 4 37 4 3 36 3 8 24 2 5 25 2 31 （1）○计算出各行和各列的次最小运费和最小运费的差额，填入该表的最 右列和最下列。 2 ○从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最 小元素， 丙列中的最小元素为 3， 由此可以确定产地 2 的产品应先供应丙的需要， 而产地 2 的产量等于丙地的销量，故在（2，丙）处填入 0，同时将运价表中的 丙列和第二行的数字划去，得到： 销地 甲 乙 丙 丁 产量 产地 137452 3 销量4 33 35 22 33 ○对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 1 2 填入该标的最右列和最下行，重复步骤○○，直到求出初始解为止。得到下表：销地 产地 1 2 3 销量甲乙丙丁产量3 2 0 3 3 3 使用位势法进行检验： 22 0 25 2 31 ○上表中，数字格处填入单位运价并增加一行一列，在列中填入 ui （i=1， 2，3） ，在行中填入 v j （j=1，2，3，4） ，先令 同）来确定 销地 产地 1 2 3ui vi + = cij （i，j ∈ B，B 为基，下uiv 和 i ，得到下表：甲 乙 丙 丁ui0 -2 13 3 4 3 2 ○由 σ ij = 3 2 54 2 4vicij-（ui vi + ） （i，j 为非基，下同）计算所有空格的检验数，并在丁每个格的右上角填入单位运价，得到下表 销地 甲 乙 丙 产地 1 0 2 1 3 0 4 0 2 4 3 2ui4 0 -2 13 57 1 4 06 0 3 0 8 02 5vi3254由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。 又因为 σ 34 =0，此问题有无穷多最优解。 总运费 min z=3*3+3*3+2*3+2*4=32 （2） 销地 产地 1 2 3 销量甲乙丙丁产量10 16 5 56 10 4 27 5 10 412 9 10 64 9 41 解： （2）○计算出各行和各列的次最小运费和最小运费的差额，填入该表 的最右列和最下列。 2 ○从行差额或者列差额中找出最大的， 选择它所在的行或者列中的最 小元素，甲列是最大差额列，甲列的最小元素是 5，所以产地 3 的产品先供应甲 的需求，同时将运价表中产地 3 所在行的数字划去。 3 ○对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 1 2 填入该标的最右列和最下行，重复步骤○○，直到求出初始解为止。得到下表： 销地 产地 1 2 3 销量 甲 乙 丙 丁 产量121 3 46 64 5 2 使用位势法进行检验：4 9 41 ○上表中，数字格处填入单位运价，并增加一行一列，在列中填入 ui （i=1， 2，3） ，在行中填入 v j （j=1，2，3，4） ，先令 u1 =0，由 为基，下同）来确定 2 ○由 σ ij =ui vi + = cij （i，j ∈ B，Buiv 和 i.cij-（ui vi + ） （i，j ∈ N）计算所有空格的检验数，并在每个格的右上角填入单位运价，得到下表销地 产地 1甲乙丙丁ui12 010 0 16 8 6 5 0 10 3 66 10 0 4 8 77 1 5 0 10 4 112 39-210 -5vi由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。 此问题有唯一最优解。 总运费 min z=118 （3） 销地 甲 乙 丙 丁 戊 产量 产地 1 2 3 4 销量 10 2 1 8 4 20 10 20 6 4 5 8 7 3 6 9 30 10 7 2 10 6 4 5 4 5 6 2 9解： （3）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售 地己，令单位运价为 0。销量为 2。这样就达到了产销平衡。 用伏格尔法求初始解： ○计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 1 和最下列。 ○从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 2 素，产地 1 所在的行是最大差额行，最小元素 0，说以一产地的产品应该优先供 应己的需要，同时划掉己列的数字。 ○对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 3 填入该标的最右列和最下行，重复步骤○○，直到求出初始解为止。得到下表： 1 2 销地 甲 乙 丙 丁 戊 己 产量 产地 1 2 3 4 销量 3 4 4 3 4 4 6 使用位势法进行检验： 2 2 2 2 4 2 2 5 6 2 91 ○上表中，数字格处填入单位运价，并增加一行一列，在列中填入 ui （i=1，2，3，4） ，在行中填入 v j （j=1，2，3，4，5，6） ，先令 u1 =0，由 j ∈ B，B 为基，下同）来确定 2 ○由 σ ij =ui vi + = cij （i，uiv 和 i.cij-（ui vi + ） （i，j ∈ N）计算所有空格的检验数，并在每个格的右上角填入单位运价。 由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。 又因为 σ 14 =0，此问题有无穷多最优解。 总运费 min z=90 （4） 销地 甲 乙 产地 1 2 3 4 5 销量 100 10 13 0 9 24 120 18 M 6 11 28 100丙 29 21 11 23 36丁 13 14 3 18 30 60戊 22 16 M产量 100 120 14019 80 34 60 80解： （4）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售 地己，令单位运价为 0。销量为 40。这样就达到了产销平衡。 用伏格尔法求初始解： ○计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 1 和最下行。 ○从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 2 素，同时划掉所在列或行的元素。 ○对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 3 填入该标的最右列和最下行，重复步骤○○，直到求出初始解为止。 1 2 并用位势法进行检验： 销地 甲 乙 丙 丁 戊 己 ui 产地 1 2 3 3 0 10 2 13 M-16 6 M 0 11 18 8 21 1 3 29 0 14 0 M 13 6 16 12 0 -10 22 12 0 0 0 00 4 4 5 24 2 10 90 11 0 28 0 160 23 7 36 3 210 18 10 30 5 13M-6 19 8 34 6 1622 0 17 0 -12 12 -5vi由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。 又因为 σ 31 =0，此问题有无穷多最优解。 总运费 min z= 已知运输问题的产销平衡表、单位运价表及最优调运方案如下表所示 表1 销 产量 B1 B2 B3 B4 5 0 5 5 表2 销地 15 15 10 10 15 10 15 25 5地 产地 A1 A2 A3 销量产地B110 12 2B21 7 14B320 9 16B411 20 18A1 A2 A3（1） （2）A2 A2到 到B2 B4的单位运价 c22 在什么范围变化时，上述最优方案不变？ 的单位运价变为何值时，有无穷多最优方案。除表 1 中方案外，至少写出其他两个。 解： 1 (1)○在对应表的数字格处（ c22 未知）填入单位运价，并增加一行，在列中 填入 ui （i=1，2，3） ，在行中填入 v j （j=1，2，3，4） ，先令 u1 =0，由ui vi + = cij（i，j ∈ B）来确定 2 ○由 σ ij =uiv 和 i.cij-（ui vi + ） （i，j ∈ N）计算所有空格的检验数，并在每个格的右上角填入单位运价（ c22 未知） 。 最优调运方案不变，则所有非基变量的检验数都是非负。所以： c22 -3 ≥ 0 c22 +10 ≥ 0 10- c22 ≥ 0 24- c22 ≥ 0 18- c22 ≥ 0 解得: 3 ≤ c22 ≤ 10 单位运价在此区间变化时，最优调运方案不变。 1 （2）○在对应表的数字格处（ c22 未知）填入单位运价，并增加一行，在 列中填入 ui（i=1， 3） 在行中填入 v j（j=1， 3， ， 2， ， 2， 4） 先令 u1 =0， 由 （i，j∈B）来确定 2 ○由 σ ij =ui vi + = cijuiv 和 i.cij-（ui vi + ） （i，j∈N）计算所有空格的检验数，并在每个格的右上角填入单位运价（ c22 未知） 。 有无穷多最优方案，则至少有一个非基变量的检验数为 0. 取 c24 -17=0，所以单价变为 17 时，该问题 有无穷多最优调运方案。 另外的两种调运方案： 1 ○ 销地 产地A1 A2 B1 B2 B3B40产量15 0 1515 2510A3 销量 2 ○ 销地 产地 A1 A2 A3 销量5 5 15 15 105B1B2 15B3B4产量15 15 10 25 50 5 501515103.5 某百货公司去外地采购 四种规格的服装，数量分别为： 某百货公司去外地采购 ABCD 四种规格的服装，数量分别为：A,1500 套； B，2000 套；C，3000 套；D，3500 套；有三个城市可以供应上述服装，分别为： 有三个城市可以供应上述服装，分别为： ， ， ， I，2500 套，II，2500 套；III，5000 套。已知下表，求预期盈利最大的采购方 已知下表， ， ， ， 案。 A B C D I 10 5 6 7 II 8 2 7 6 III 9 3 4 8 解： 因为利润表中的最大利润是 10， 所以令 M=10， M 减去利润表上的数字， 用 此问题变成一个运输问题，见下表： 销地 A B C D 产量 产地 I II III 销量0 5 4 3
使用伏格尔法计算初始解： ○计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列 1 和最下行。 ○从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元 2 素，同时划掉所在列或行的元素。 ○对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， 3 填入该标的最右列和最下行，重复步骤○○，直到求出初始解为止。 1 2销地 产地 I II III 销量ABCD产量1500500 500 00 3500001500 使用位势法检验：1 ○数字格处填入单位运价，并增加一行一列，在列中填入 ui （i=1，2，3） ， 在行中填入 v j （j=1，2，3，4） ，先令 u1 =0，由ui vi u + = cij （i，j ∈ B， ）来确定 iv 和 i.2 ○由 σ ij =cij-（ui vi + ） （i，j ∈ N）计算所有空格的检验数，并在每个格的右上角填入单位运价。 如果没有得到最优解，用逼回路法进行改进。 盈利最大方案： 销地 A B C 产地 I II 3 III 1 0 0 1 5Dui3 0 -1 10 0 2 45 0 8 0 7 1 44 2 3 4 6 14 2vi此时，总运费为 28000 元;最大盈利为 72000 元。 甲乙丙三个城市每年需要煤炭分别为： 万吨、 万吨、 万吨， 3.6 甲乙丙三个城市每年需要煤炭分别为：320 万吨、250 万吨、350 万吨， 两处煤矿供应。煤炭供应量分别为： 万吨； 万吨； 由 A、B 两处煤矿供应。煤炭供应量分别为：A,400 万吨；B,450 万吨；运价如下 万吨， 表，由于需大于供应，经研究平衡决定，甲城市供应量可以减少 0~30 万吨，乙 由于需大于供应，经研究平衡决定， 城市需要完全供应， 万吨。试求将供应量分配完又使总运 城市需要完全供应，丙城市供应不少于 270 万吨。试求将供应量分配完又使总运 费最低的调运方案。 费最低的调运方案。 甲 乙 丙A B15 2118 2522 16解： 此问题的供应量小于需求量，假设供应地 C，产量为 70 万吨。 用伏格尔法求解得： 销地 甲 甲‘ 乙 丙 丙‘ 供应 产地 A B C 需求 150 140 250 30 250 270 270 10 70 80 400 450 70290 30 使用位势法检验：1 ○数字格处填入单位运价，并增加一行一列，在列中填入 ui （i=1，2，3） ， 在行中填入 v j （j=1，2，3，4） ，先令 u1 =0，由ui vi u + = cij （i，j ∈ B， ）来确定 iv 和 i.2 ○由 σ ij =cij-（ui vi + ） （i，j ∈ N）计算所有空格的检验数，并在每个格的右上角填入单位运价。 如果没有得到最优解，用闭回路法进行改进。 最优解时，最小运费是 14650 万元。 3.7 某造船厂根据合同要从当年起连续三年末各提供三条规格型号相同的 大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下 表， 年度 正常生产时间内 加班生产时间内 正常生产时的 可 完 成 的 客 货 轮 可 完 成 的 客 货 轮 每艘成本/万元 数 数 1 2 3 500 2 4 2 600 3 1 3 550 已知加班生产时，每艘客货轮的成本比正常生产高出 70 万元，又知道造出 来的可货轮如当年不交货，每艘积压一年造成积压损失 40 万元，在签合同时， 该厂已经存储了 2 艘客货轮， 而该厂希望在第三年木完成合同后还能存储一艘备 用，问该厂如何安排每年的生产量，能够在满足上述要求的情况下，总的生产费 用加积压损失最少？ 解：设 A1 ，A2 ，A3 是三年的需求订货，B1 ，B2 ，B3 是三年的正常生产能力；B1′ ， ′ ′ B2 ， B3 是三年的加班能力，S 是事先积压产生的供货能力。第三年的需求量是 4 艘。此问题产销不平衡，增加设想销地 A4 ，运价 0，销量 7. 使用伏格尔法求初始解：并用位势法检验： 此问题有无穷多最优解， 总运费 min z=4730 万元 销地 产地 B1 B1′ B2 ′ B2 B3 ′ B3 S 需求量 40 500 540 550 620 0 600 A1 500 A2 540 0 0 0 A3A4供应量 0 60 60 60 -10 60 -460560-60试题： 试题：(2001 年上海大学) 某产品由产地 Ai 发往销地 Bj 的每吨运费如下表： 元/吨 B1 B2 B3 供应量（吨） A1 50 40 60 150 A2 45 30 65 200 A3 20 10 50 250 需求量 150 220 180 为满足各销地需求，应如何确定运输方案使总费用最小？ （1） 建立此运输问题的数学模型。 （2）将此问题化为产销平衡的运输问题，并求出一个初始基本可行解。 解： （1）设 xij 某产品为从 Ai 发往销地 Bj 的吨数，则此运输问题的数学模型为：max z = 50 x11 + 40 x12 + 60 x13 + 245 x 21 + 30 x 22 + 65 x 23 + 20 x31 + 10 x32 + 50 x33 ? x11 + x12 + x13 = 150 ? x 21 + x 22 + x 23 = 200 ? ? x31 + x32 + x33 = 250 ? s.t ? x11 + x 21 + x31 = 150 ? x12 + x 22 + x32 = 220 ? ? x13 + x 23 + x33 = 180 ? ? xij ≥ 0 , i , j = 1 , 2 , 3 （2）增加一个虚拟销地 B4，其需求量为 50 吨，各产地到虚拟销地 B4 的每吨运 费分别为 0，则可将此问题化为如下产销平衡的运输问题： 元/吨 A1 A2 A3 需求量 B1 50 45 20 150 B2 40 30 10 220 B3 60 65 50 180 B4 0 0 0 50 供应量 150 200 250由最小元素法可得到如下的一个初始基本可行解： 元/吨 A1 A2 A3 需求量 B1 120 30 150 B2 B3 100 80 180 B4 50 供应量 150 200 250220 22050第四章（98 页） 4.1 若用以下表达式作为目标规划的目标函数，试述其逻辑是否正确？ （1）max= d1? + d1+ （2）max z= d1? - d1+ （3）min z= d1? + d1+ （4）min z= d1? - d1+ 解： （1）不正确 （2）正确 （3）正确 （4）正确 4.2 试用图解法找出以下目标函数的满意解；（1）min z= P （ d1? + d1+ ）+ P2 （2 d 2+ + d3+ ） 1 s.t. x1 -10 x2 + d1? - d1+ =50? 3 x1 +5 x2 + d 2 - d 2+ =208 x1 +6 x2 + d 3? - d3+ =100? x1 ， x2 ， d1? ， d1+ ， d 2+ ， d 2 ， d 3? ， d3+ ≥ 0 ? ? （2）min z= P （ d3+ + d 4+ ）+ P2 d1+ + P3 d 2 + P4 ( d 3? +1.5 d 4 ) 1s.t. x1 + x2 + d1? - d1+ =40? x1 + x2 + d 2+ - d 2 =100x1 + d 3? - d3+ =30? x2 + d 4 - d 4+ =15 ? ? x1 ， x2 ， d1? ， d1+ ， d 2+ ， d 2 ， d 3? ， d3+ , d 4 , d 4+ ≥ 0 ? (3) min z= P （ d1? + d1+ ）+ P2 d 2 + P3 d3+ 1s.t. x1 + x2 + d1? - d1+ =10? 3 x1 +4 x2 + d 2 - d 2+ =508 x1 +10 x2 + d 3? - d3+ =300? x1 ， x2 ， d1? ， d1+ ， d 2+ ， d 2 ， d 3? ， d3+ ≥ 0解 （1）满意解是： （50，0） （2）满意解是： （25，15） （3）满意解是： （10，0） 4.3 使用单纯形法求解下列目标规划问题。? （1）min z= P d1? + P2 d 2+ + P3 （5 d 3? +3 d 4 ）+ P4 d1+ 1s.t. x1 + x2 + d1? - d1+ =80? x1 + x2 + d 2 - d 2+ =90x1 + d 3? - d3+ =70? x2 + d 4 - d 4+ =45 ? ? x1 ， x2 ， d1? ， d1+ ， d 2+ ， d 2 ， d 3? ， d3+ , d 4 , d 4+ ≥ 0 ? （2）min z= P d 2+ + P d 2 + P2 d1? 1 1s.t. x1 +2 x2 + d1? - d1+ =10? 10 x1 +12 x2 + d 2 - d 2+ =62.4x1 +2 x2 ≤ 8? x1 ， x2 ， d1? ， d1+ ， d 2+ ， d 2 ≥ 0（3）min z= P （ d1? + d 2+ ）+ P2 d 3? 1 s.t. x1 + x2 + d1? - d1+ =1? 2 x1 +2 x2 + d 2 - d 2+ =46 x1 -4 x2 + d 3? - d3+ =50? x1 ， x2 ， d1? ， d1+ ， d 2+ ， d 2 ， d 3? ， d3+ ≥ 0解： （1）把原问题转化为：? Min z= P d 2+ + P d 2 + P2 d1? 1 1S.T.x1 +2 x2 + d1? - d1+ =10? 10 x1 +12 x2 + d 2 - d 2+ =62.42 x1 + x2 + x3 =8? x1 ， x2 ， x3 ， d1? ， d1+ ， d 2+ ， d 2 ≥ 0x3 是松弛变量单纯形法计算得：cj000P20P 1P2θiCB P2 P 1 0 P 1 P2 迭代…XBd1?? d2b 10 62.4 8x1 1 10 2 -10 -1x2x3d1?d1+? d2d 2+【2】 0 12 1 -12 -2 0 1 0 01 0 0 0 0-1 0 0 0 10 1 0 0 00 -1 0 2 05 5.2 8x3原问题最优解 x1 =0， x2 =5.2，非基变量的的检验数是 0，所以有多重解； 继续迭代得到： x1 =0.6， x2 =4.7 也是满意解 （2） 使用单纯形法计算： x1 =70， x2 =20 （3）满意解是 x1 =1， x2 =0 4.4 有以下目标规划问题? min z= P d1? + P2 d 4+ + P3 （5 d 2 +3 d 3? ）+ P3 （5 d3+ +3 d 2+ ） 1s.t. x1 + x2 + d1? - d1+ =80? x1 + d 2 - d 2+ =70x2 + d 3? - d3+ =45? d1+ + d 4 - d 4+ =10 ? ? x1 ， x2 ， d1? ， d1+ ， d 2+ ， d 2 ， d 3? ， d3+ ， d 4 ， d 4+ ≥ 0（1）用单纯形法求解? （2）若目标函数变成 min z= P d1? + P3 d 4+ + P2 （5 d 2 +3 d 3? ）+ P2 （5 d3+ +3 d 2+ ） ， 1问原问题的解有什么变化？ （3）若第一个目标约束的右端改为 120，原满意解有何变化？ 解：（1） 单纯形法计算得到： x1 =70， x2 =45 是满意解 （2） 实际上是对优先因子 P2 ， P3 进行调换，最优解不变。 ?0 ?0 ′ = B ?1?b = ? （3） ?b ? ?1 ? ?0 0 1 0 ? ? 40 ? ? 0 ? 1 0 0? ? 0 ? ? 0 ? ?? ?? ? 1 1 0 ? ? 0 ? ? ?40 ? ?? ?? ? 0 0 1? ? 0 ? ? 0 ?b 列出现负数， d1+ 行的系数乘以-1，重新迭代， x1 =75， x2 =45 是满意解； 4.5 某工厂生产两种产品，产品 I 每件获利 10 元，产品 II 每件获利 8 元。每生产 1 件产品 I 需要 3 小时，生产产品 II 需要 2.5 小时，每周的有效时间 120 小时， 若加班生产，产品 I 每件利润少 1.5 元，每件产品 II 利润少 1 元，决策者希望在 允许的时间和加班时间获取最大利润，试建立该问题的目标规划模型，并求解？ 解：条件不足，无法建立模型。 4.6 某商标的酒是用三种等级的酒兑制而成。已知道三种酒的供应量和单位成本 如下表； 设该种牌号酒有三种商标（红黄蓝） ，各种商标的酒对原料酒的混合比及售价见 下表， 决策者规定： 首先必须严格按规定比例兑制各种商标的酒， 其次获利最大； 再次，红商标的酒每天至少生产 2000kg，列出数学模型。 解： 设 xi1 ， xi 2 ， xi 3（i=1，2，3）表示第 i 种等级的兑制红黄蓝三种商标的酒的数量， 数学模型： Max z= P ( d1? + d 2+ + d 3? + d 4+ + d 5? + d 6+ )+ P2 d8+ + P3 d 7+ 1 s.t.x31 -0.1（ x11 + x21 + x31 ）+ d1? - d1+ =0? x11 -0.5（ x11 + x21 + x31 ）+ d 2 - d 2+ =0x32 -0.7（ x12 + x22 + x32 ）+ d 3? - d 3+ =0? x12 -0.2（ x12 + x22 + x32 ）+ d 4 - d 4+ =0x33 -0.5（ x13 + x23 + x33 ）+ d 5? - d 5+ =0 x13 -0.1（ x13 + x23 + x33 ）+ d 6? - d 6+ =0 x11 + x21 + x31 + d 7? - d 7+ =2000 xij ≥ 0 (i=1,2,3;j=1,2,3)其中， z=5.5( x11 + x21 + x31 )+5( x12 + x22 + x32 )+4.8 （ x13 + x23 + x33 ） -6( x11 + x12 + x13 )-4.5( x21 + x22 + x23 )-3( x31 + x32 + x33 )+ d8? - d8+ 试题： 试题： 1. 某生产基地每天需从 A、B 两仓库中提取原材料用于生产，需提取的原材料 有：原材料甲不少于 240 件，原材料乙不少于 80 公斤，原材料丙不少于 120 吨。已知：从 A 仓库每部货车能运回生产基地甲 4 件，乙 2 公斤，丙 6 吨， 运费 200 元/部；从 B 仓库每部货车每天能运回生产基地甲 7 件，乙 2 公斤， 丙 2 吨，运费 160 元/部，问：为满足生产需要，生产基地每天应发往 A、B 两仓库多少部货车，并使总运费最少？ 解题过程：根据题意列出下表：单位 运量 仓库 原 材 料甲 （件） 4 7 240乙 （公斤） 2 2 80丙 （吨） 6 2 120运费 （元/部） 200 160A B 需求量设每天发往 A，B 两仓库的货车数分别为 x1 , x2 部，则有min z = 200 x1 + 160 x2?4 x1 + 7 x2 ≥ 240 ? 2 x + 2 x ≥ 80 ? 2 s.t. ? 1 ? 6 x1 + 2 x2 ≥ 120 ? x1 , x2 ≥ 且为整数 0 ?① ② ③ ⑤ ④* * 先不考虑整数约束，用图解法（如上图） ，得最优解为 x1 = 10, x2 = 30 ，恰好是整数解。故 x* = (10,30) 就是原问题的最优整数解，且 z * = 6800 。 故生产基地每天发往 A 仓库 10 部车，发往 B 仓库 30 部车，可使总运费最 少为 6800 元。 第五章答案 5.1 对下列整数规划问题，问：用先解相应的线性规划，然后凑整的办法，能否 求到最优整数解？ （1） max z=3 x1 +2 x2 s.t. 2 x1 +3 x2 ≤ 14.5 4 x1 + x2 ≤ 16.5 x1 , x2 ≥ 0 x1 , x2 是整数 （1） 解：将上述问题化为： Max z=3 x1 +2 x2 +0 x3 +0 x4 s.t. 2 x1 +3 x2 + x3 =14.5 4 x1 + x2 + x4 =16.5x1 , x2 , x3 , x4 ≥ 0 x1 , x2 ∈ N 用单纯形法求解：cj3 b 29/2 33/2 0 x1 2 【4】 32 x2 3 1 20 x3 1 0 0T0 x4 0 1 0θiCB 0 0XB x3 x429/4 33/8-z （迭代过程略）相应的线性规划问题最优解是 X * =T( 7 / 2, 5 / 2, 0, 0 ),目标函数的最优值 z=31/2凑整数时， X 1 = ( 4,3, 0, 0 ) ,是非可行解； X 2 = ( 4, 2, 0, 0 ) ，是非可行解；TX 3 = ( 3,3, 0, 0 ) ，是非可行解；TX 4 = ( 3, 2, 0, 0 ) ，是可行解，z=13；T使用分支定界法解整数规划问题。 令 z =31/2， x1 = x2 =0 是可行解。 所以 z =0，0 ≤ z * ≤ 31/2 把原问题分解为两个问题： （I）s.t. 2 x1 +3 x2 ≤ 14.5 4 x1 + x2 ≤ 16.5 0 ≤ x1 ≤ 3; x2 ≥ 0 max z1 =3 x1 +2 x2（II）s.t.max z2 =3 x1 +2 x22 x1 +3 x2 ≤ 14.5 4 x1 + x2 ≤ 16.5 4 ≤ x1 ; x2 ≥ 0 将上述问题化为标准型，使用单纯形法求解： x1 =3， x2 =2 是最优整数解，z=13. （2）max z=3 x1 +2 x2 s.t. 2 x1 +3 x2 ≤ 14 2 x1 + x2 ≤ 9 x1 , x2 ≥ 0 x1 , x2 是整数 （2） 解： 使用图解法或者单纯形法求解此问题，线性规划问题最优解是（13/4，5/2） 目标函数最优值 max z=59/4； 凑整数时， X 1 = (3, 2)T ,是可行解，z=13； X 2 = (3, 3)T ，是非可行解； X 3 = (4, 2)T ，是非可行解； X 4 = (4, 3)T ，是非可行解； 使用分支定界法求解原整数规划问题，令 令 z =59/4， x1 = x2 =0 是可行解。 所以 z =0，0 ≤ z * ≤ 59/4； 把原问题分解为两个问题： （a）max z1 =3 x1 +2 x2 s.t. 2 x1 +3 x2 ≤ 14 2 x1 + x2 ≤ 90 ≤ x1 ≤ 3; x2 ≥ 0 （b）max z2 =3 x1 +2 x2 s.t. 2 x1 +3 x2 ≤ 14 2 x1 + x2 ≤ 9 4 ≤ x1 ; x2 ≥ 0 解得：最优整数解是 x1 =4， x2 =1； 目标函数是 14. 5.2 用分支定界法解： Max z= x1 + x2 s.t. 2 x1 +9 x2 /14 ≤ 51/14 -2 x1 + x2 ≤ 1/3 x1 ， x2 ≥ 0 x1 x2 都是整数。 图解法解得：最优解是 B 点（51/46+7/69-1/6，51/23+14/69） 目标函数最优值为：58/23+51/46-1/6 使用分支定界法求解， 令 z =58/23+51/46-1/6， x1 = x2 =0 是可行解； 因此 z =0，故 0 ≤ z * ≤ 58/23+51/46-1/6 将原问题分解为下列问题： （I）Max z1 = x1 + x2 s.t. 2 x1 +9 x2 /14 ≤ 51/14 -2 x1 + x2 ≤ 1/3 x2 ≤ 1 x1 ， x2 ≥ 0（I）Max z1 = x1 + x2 s.t. 2 x1 +9 x2 /14 ≤ 51/14 -2 x1 + x2 ≤ 1/3 x2 ≥ 2 x1 ， x2 ≥ 0 按照以上步骤， 求解最终得到：最优解是（1，2） 目标函数最优值 z=3 5.3 用 Gomory 切割法解如下问题： （1）max z= x1 + x2 s.t. 2 x1 + x2 ≤ 6 4 x1 +5 x2 ≤ 20 x1 , x2 ≥ 0 x1 , x2 是整数 解： 将上述问题化成标准型： max z= x1 + x2 +0 x3 +0 x4 s.t. 2 x1 + x2 + x3 =6 4 x1 +5 x2 + x4 =20 x1 , x2 ， x3 ， x4 ≥ 0 x1 , x2 ， x3 ， x4 是整数 单纯形法求得最优解是： X * = ( 5 / 3,8 / 3, 0, 0 ) ，目标函数最优值 13/3T变量之间的关系： x1 +5 x3 /6- x4 /6=5/3 x2 -2 x3 /3+ x4 /3=8/3把系数和常数项都分解成为整数和非负真分数之和； 所以有： 2/3-5 x3 /6-5 x4 /6 ≤ 0 2/3-（ x3 + x4 ）/3 ≤ 0 加入松弛变量 x5 ，继续迭代得到最终结果： X * =4( 0, 4, 2, 0, 0 )T，目标函数最优值解得：最优整数解是 x1 =0， x2 =4； 目标函数是 4. （3） max z=3 x1 - x2s.t. 3 x1 -2 x2 ≤ 3 -5 x1 -4 x2 ≤ -10 2 x1 + x2 ≤ 5x1 , x2 ≥ 0 x1 , x2 是整数 解： 将原问题化成标准型，并使用单纯形法求解： 最优解为 X * = (13 / 7, 9 / 7, 0,31 / 7, 0 ) ，目标函数最优值 30/7T从单纯形表可以得到变量间的关系， 把系数和常数项都分解成整数和非负分数之 和，可以得知：6/7-（ x3 /7+2 x5 /7） ≤ 0加入松弛变量 x7 ，把新的约束条件加入后，继续迭代，得到最终的结果： 最优解是 x1 =1， x2 =2 目标函数最优值 1. 5.4 某城市的消防总部将全市划分为 11 个防火区， 设有四个防火站， 如图所示(课 本 P114)，其中①②③④是四个消防站，1，2，…11 是防火区域，根据历史资料 证实，各个消防站可在事先规定的允许时间内对所有负责的地区的火灾予以消 灭，虚线表示各地区是哪个消防站负责，现在总部提出：是否可以减少消防站的 数目，仍能够负责各个地区的防火任务，如果可以，关闭哪个？ 提示：对每个消防站定义一个 0-1 变量 xi ，令?1 xi = ? ?0 1 代表当某个防火区域由第 i 个消防站负责，0 代表不是它负责。然后对每个防 火区域列出约束条件； 解： ?1 令 xi = ? ?0 1 代表当某个防火区域由第 i 个消防站负责，0 代表不是它负责；i=1，2，3，4。 建立数学模型： Min z= ∑ xii =1 4s.t. x1 + x2 ≥ 1x1 ≥ 1 x1 + x3 ≥ 1 x3 ≥ 1 x1 + x3 + x4 ≥ 1 x1 + x4 ≥ 1 x1 + x2 + x4 ≥ 1 x2 + x4 ≥ 1 x4 ≥ 1 x3 + x4 ≥ 1有以上约束条件可以解得：x1 = x3 = x4 =1继续求解 当 x2 =0 时，是可行解，目标函数是 3； 当 x2 =1 时，是可行解，目标函数是 4； 比较可以得到，最优解是X * = (1, 0,1,1) ，目标函数最优值是 3.T所以，可以关闭消防站②。 5.5 在有相互排斥的约束条件的问题中，如果约束条件时 ≤ 型的，我们加 yi M（ yi 是 0-1 变量，M 是很大的常数）的方法统一在一个问题中。如果是 ≥ 型的，我们 将如何利用 yi 和 M 呢？ 解：在 m 个约束条件右端分别减去 yi M（ yi 是 0-1 变量，M 是很大的常数，i=1， 2…m） 并且 ∑ yi = m ? 1i =1 m5.6 解 0-1 规划：（1）max z=4 x1 +3 x2 +2 x3s.t. 2 x1 -5 x2 +3 x3 ≤ 4 4 x1 + x2 +3 x5 ≥ 3 x2 + x3 ≥ 1 x1 , x2 , x3 =0 或 1解： 将（0，0，0） 0，0，1） 0，1，0） 1，0，0） 0，1，1） 1，0，1） 1，1， （ （ （ （ （ （ 0） 1，1，1）分别带入到约束条件中，可以得到：原问题的最优解是（0，0，1） （ ， 目标函数最优值 2. （2）min z=2 x1 +5 x2 +3 x3 +4 x4s.t. -4 x1 + x2 + x3 + x4 ≥ 0 -2 x1 +4 x2 +2 x3 + x4 ≥ 4 x1 + x2 - x3 + x4 ≥ 1 x1 ， x2 ， x3 ， x4 =0 或 1解：X*=( 0,1, 0, 0 )T是一个可行解，目标函数数值是 4；所以可以增加约束条件：2 x1 +5 x2 +3 x3 +4 x4 ≤ 4把可能的解（0，0，0，0） （0，0，0，1）…（1，1，1，1）分别带入约束条件 的问题中，得到最优解 X * =( 0,1, 0, 0 )T，目标函数最优值 4.5.7 有四个工人，指派他们完成 4 种工作，每人做各种工作所消耗的时间如下表， 问指派哪个人去完成哪种工作，可以使得总耗时最小？ 任务 A B C D 人员 甲 15 乙 19 丙 26 丁 19 解：系数矩阵 C 为： ?15 ?19 ? ? 26 ? ?19 18 21 24 ? 23 22 18 ? ? 17 26 19 ? ? 21 23 17 ? 18 23 17 21 21 22 16 23 24 18 19 17① 系数矩阵的每行元素减去该行的最小元素得矩阵 B ② B 矩阵的每列元素减去该列的最小元素得到矩阵 A 此时，细数矩阵的每行每列都有元素 0. 先给 a11 加圈，然后给 a24 加圈，划掉 a44 。给 a32 加圈，划掉 a33 得： ? 0 2 6 9? ? 1 4 4 0? ? ? ?10 0 0 3 ? ? ? ? 2 3 6 0? 此时，画圈的数目是 3,少于 4 个，所以指派不成功，进入下一步， 给第四行打√号， 给第四列打√号， 给第二行打√号， 将第一， 第三行画一横线， 将第四列画纵线，变换矩阵得到 ?0 ?0 ? ?10 ? ?1 2 6 10 ? 3 3 0? ? 0 0 4? ? 2 5 0?给第一，第四列打√号，对第一，第二，第四行打√号，给第一，第四列画一纵 线，第三行画一横线，变换矩阵得到 甲 ?0 ?0 ? ?12 ? ?1 乙 丙 0 1 0 0 丁4 10 ? 1 1? ? 0 6? ? 3 0?得到最优指派方案为： 甲―B；乙―A; 丙―C；丁―D。 所消耗的总时间是 70. 试题： 试题： 1. （2006 年复旦大学）采用变量代换，试把非线性 0―1 整数规划max z = x12 + x2 x3 ? x1 x2 x3? ?3x + 4 x2 + x3 ≤ 3 s.t. ? 1 x1 , x2 , 为 0 或 1 x3 ?转换成一个 0―1 整数规划。 解题分析：0―1 规划即约束中自变量只能取值 0 或 1。当 ?1, x2 = x3 = 1 解题过程：令 y1 = ? 否则 ?0,，故有 x2 x3 = y1当 ?1, x1 = x2 = x3 = 1 再令 y2 = ? 否则 ?0,，故有 x1 x2 x3 = y2而 x12 与 x1 等价，故原问题可等价地写为max z = x1 + y1 ? y2? ?3 x1 + 4 x2 + x3 ≤ 3 ? y1 ≤ x2 ? ? y1 ≤ x3 ? y2 ≤ x1 ? ? s.t. ? y2 ≤ x2 ? y2 ≤ x3 ? ? x2 + x3 ≤ y1 + 1 ?x + x + x ≤ y + 2 2 ? 1 2 3 ? x1 , x2 , x3 , y1 , y2 0 或 1 ? 为2. （2005 年南京大学）现要在 5 个工人中确定 4 个人来分别完成四项工作中的 一项工作。由于每个工人的技术特长不同，他们完成各项工作所需的工时也 不同。每个工人完成每项工作所需工时如表 5―1 所示。 表 5 ―1所需工时 工人 工作ABCDⅠ Ⅱ Ⅲ9 4 54 6 43 5 77 6 5Ⅳ Ⅴ7 105 62 73 4试找出一个工作分配方案，使总工时最少。 解题分析：本题属“不平衡”指派问题，故应先虚拟一项工作，使其平衡，再按 常规求解即可。 解题过程：虚拟一项工作 E，设每人完成 E 所需时间都是“0” ，从而转化为五个 人完成五项工作的分配问题，再用匈牙利法求解。 最优解为：Ⅰ―C，Ⅱ―A，Ⅲ―B，Ⅳ―D，Ⅴ―E，即应安排工人Ⅰ、 Ⅱ、Ⅲ、Ⅳ分别完成工作 C、A、B、D，此时所用时间最少，为 3+4+4+3=14。
运筹学习题答案 第一章(39 页) 1.1 用图解法求解下列线性规划问题,并指出问题是具有唯一最优解、无穷多最 优解、无界解还是无可行解。 (1)max z ? x1 ...运筹学习题及答案_理学_高等教育_教育专区。运筹学习题及答案 第1 页共 31 页 第一章线性规划及单纯形法 1.某车间生产甲、乙两种产品,每件甲产品的利润是 2...运筹学试题及答案_工学_高等教育_教育专区。一、填空题: (每空格 2 分,共 16 分) 1、线性规划的解有唯一最优解、无穷多最优解、 无界解 四种。 2、在...2 6 32 0 6 4 24 0 5 2 48 0 11 5 38 0 0 40 0 75 0 运筹学(B卷)一、单项选择题(从下列各题四个备选答案中选出一个正确答案,答案选错或未...运筹学复习题及参考答案_经济学_高等教育_教育专区。运筹学复习题及参考答案中南大学网络教育课程考试复习题及参考答案运筹学一、判断题: 判断题 1.图解法与单纯形...最全的运筹学复习题及答案_管理学_高等教育_教育专区。四、把下列线性规划问题化成标准形式: 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1...最全运筹学习题及答案_理学_高等教育_教育专区。第 1 页共 1 页 运筹学习题答案 第一章(39 页) 1.1 用图解法求解下列线性规划问题,并指出问题是具有唯一最...运筹学习题答案一_管理学_高等教育_教育专区。习题一 1.1 讨论下列问题: (1...(1)1～6 月份产品 A 各生产与销售多少总利润最大,建立数学模型; (2)当 1...运筹学复习题及参考答案 8页 免费 运筹学复习题及参考答案 15页 1下载券 ...5 由题意可得整数规划模型如下: max Z=7x1+17x2+11x3+9x4+21x5 x1+x2...《运筹学》练习题及其解答(3) 运筹学》练习题及其解答( 解答试判断表 1 和表...3.11 表 3 示出一个运输问题及它的一个解, (1) 试问: 表中给出的解...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。