资源描述
一、线性规划 二、运输问题 三、多目标规划 四、动态规划 五、 图论 六、网络计划技术 七、决策论 八、存储论 九、排队论 十、对策论 十一、模拟技术 一、线性规划 （一）选择填空题 （二）线性规划建模 （三）互补松弛应用 （四）灵敏度分析 （五） 证明题 （一）选择填空题 1下面给出某线性规划问题的单纯形初表和终表（ Min 型）： CB XB B-1b 0 1 -3 0 2 0 x1 x2 x3 x4 x5 x6 0 x1 7 0 x4 12 0 x6 10 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 j CB XB B-1b x1 x2 x3 x4 x5 x6 x2 x6 2/5 0 1/10 0 1/5 1 3/10 0 1 0 -1/2 1 j (1)初表的出基变量为 ，进基变量为 。 1*)2( B最优基逆 (3)填完终表。 *)4( X最优解 *)5( y对偶问题最优解 (6)若原问题增加一个新的非负变量，则对偶问题的最优目标值将（变大、不变、变 小） 。 （ 2007） 解： 1 (1)出基变量为 x4；进基 变量为 x3。 (2) *1 21 0 5 10 13 0 5 10 111 2 B 。 (3) CB XB B-1b x1 x2 x3 x4 x5 x6 1 x2 4 -3 x3 5 0 x6 11 2/5 1 0 1/10 4/5 0 1/5 0 1 3/10 2/5 0 1 0 0 -1/2 10 1 j 1/5 0 0 4/5 12/5 0 (4) * (4 5 11)TX (5) * 14( 0)55Y (6) 变小 1 用图解法解线性规划时，以下几种情况中不可能出现的是（ ）。 A 可行域（约束集合）有界，无有限最优解（或称无解界） B 可行域（约束集合）无界，有唯一最优解 C 可行域（约束集合）是空集，无可行解 D 可行域（约束集合）有界，有多重最优解 （ 2006） 解： 1 A 2 根据线性规划的互补松弛定理，安排生产的产品机会 成本一定（ ）利润 。 A 小于 B 等于 C 大于 D 大于等于 （ 2006） 解： 2 B 1 用大 M法求解 Max型线形规划时，人工变量在目标函数中的系数均为 _， 若最优解的 _中含有人工变量，则原问题无解。（ 2005） 解： 1、 -M 基变量 1. 设线性规划问题 0m ax bxAxcx 有最优解 *x 和影子价格 *y ,则线性规划问题 02m ax bxAxcx 的最优解 = ，影子价格 = 。 （ 2004） 解： 1. x* 2y* 3. 某工程公司拟从 1、 2、 3、 4 四个项目中选择若干项目。若令 4101 ，个项目未选中，第 个项目被选中，第 iiix i 请用 ix 的线性表达式表示下列要求：（ 1）若项目 2 被选中，则项目 4 不能被选中： （ 2）只有项目 1 被选中，项目 3 才能被选中： 。（ 2004） 解： 3. 0,1 3142 xxxx 一、简答（ 18%） （ 1）请简述影子价格的定义。 （ 2）在使用单纯型表求解型线性规划时，资源的影子价格在单纯型表的什么位置上？ （ 3）写出影子价格的数学表达式并用其定义加以验证 （ 4）试述运输问题中检验数的经济意义（ 2003） 解：一、简答 当各资源增加一单位时引起的总收入的增量，影子价格大于零的资源一定没有剩余，有剩 余一定为零。 松弛变量检验数的负值，对 偶问题的最优解。 CBB-1 B 是原问题 maxz=CX AX b,X 0最优基 Z*= CBB-1b=Y*b Z*=y1*b1+y2*b2 ym*bm *zb =y3* 表明增加一个单位的运量会引起总运输费用的变化 1 线性规划原问题中约束的个数与其对偶问题中的 变量 个数相等。若原问题第 j 个约束 为等式，则对偶问题第 j 个 变量 自由。（ 2002） 解： 2 设线性规划问题 max:cx|Ax bx 0有最优解，且最优解值 z0；如果 c 和 b 分别被 v1 所乘，则 改变后的问题 也有 （也有、不一定有）最优解；若有最优解，其最优解 大 于 (大于、小于、等于 )z。（ 2002） 1下列数学模型中 a 是线性规划模型。 (2001) 3 2954 867m i nm a x)( 321321 xxxxxxZb 321 324m a x)( xxxZa 0, 120544 150637 . 321 321 321 xxx xxx xxx ts 0, 500896 300355 . 321 321 321 xxx xxx xxx ts 解： 2下列图形（阴影部分）中 b 是凸集。 (2001) （ a） （ b） （ c） 解： 3标准形式的线性规划问题，其可行解 b 是基本可行解，最优解 a 是可行解，最优 解 a 能在可行域的某顶点达到。 (2001) （ a）一定 （ b）不一定 （ c）一定不 解： 4目标函数取极小（ min Z）的线性规划问题可以转化为目标函数取极大 b 的线性规划 问题求解，原问题的目标函数值等于 c 。 (2001) （ a） max Z （ b） max（ -Z） （ c） -max（ -Z） （ d） -max Z （ a）最小元素法 （ b）比回路法 1. 线性规划单纯形算法的基本步骤是：（ 1） （ 2） (3) 每次迭代保持解的 ，改善解值的 。对偶单纯 形法每次迭代保持解的 ，改善解值的 。（ 2000） 解：确定一个初始基可行解；检验一个基可行解是否为最优解；寻找一个更好基可行解；可 行性；最优性。 2. 设有线性规划问题 0,|,m i n XbAXXRXCXf ，有一可行基 B（为 A 中的前 m 列），记相应基变量为 X ，价格系数为 CB，相应于非基变量为 XN，价格系数为 CN，则相应于 B 的基本可行解为 X= ；用非基变量来表示基变量的表达式为 XB= ；用非基变量表示目标函数的表达 式为 f= ， B 为最优基的条件 是 。（ 2000） 解： 1 1 1 1 1 1, , ( ) , 0 0 N B N B N N BBb B b B N X C B b C C B N X C C B N 3. 线性规划（ Min 型）问题有多重最优解时，其最优单纯形表上的特征为： （ 2000） 解： 0 , 0 .j k jx所 有 检 验 数 而 某 一 个 非 基 变 量 检 验 数 6. 某足球队要从 1， 2， 3， 4， 5 号五名队员中挑选若干名上场。令 54321ii0 i1 ，号不上场，第 号上场第ix 请用 xi的线性表达式表示下列要求：（ 1）从 1， 2， 3 中至多选 2 名： （ 2）如果 2 号和 3 号都上场，则 5 号不上场： （ 3）只有 4 号上场 ,1 号才上场： (2000) 解： 1 2 3 4 5 1 42 , 0 , 1 .x x x x x x x 1 某工程公司拟从四个项目中选择若干项目，若令 1, 1 , 2 , 3 , 4 .0, i ixii 第 个 项 目 被 选 中第 个 项 目 末 被 选 中 请用 xi 的线性表达式表示下列要求： （ 1）从 1， 2， 3 项目中至少选择一个： ， （ 2）只有项目 2 被选中，项目 4 才能被选中 。（ 1999） 解： 1、 x1+x2+x3 1 x2 x4 2 考虑线形规划问题 1 2 3 1 2 3 1 2 3 1 2 3 m a x 5 1 2 4 25 . . 2 3 2 , , 0 Z x x x x x x s t x x x x x x 用单纯型法求解，得其终表如下： Cj 5 12 4 0 -M CB XB B-1b x1 x2 x3 x4 x5 12 x2 8/5 5 x1 9/5 0 1 -1/5 2/5 -1/5 1 0 7/5 1/5 2/5 j 0 0 -3/5 -29/5 -M+2 5 其中 x4 位松弛变量， x5 为人工变量。 （ 1）上述模型的对偶模型为 ， （ 2）对偶模型的最优解为 ， （ 3）当两种资源分别单独增加一个单位时，目标函数值分别增加 和 ， （ 4）最优基的逆矩阵 1B （ 5）如果原问题 增加一个变量，则对偶问题的可行域将可能变大还是变小？ （ 1999） 解： 2（ 1） 12 12 12 12 12 m in 5 2 25 2 12 34 0, W y y yy yy yy yy 无 符 号 限 制 （ 2） Y*=（ 295 ， -25 ） （ 3） 295 ， -25 （ 4） 21 55 12 55 （ 5）变小 1下面给出某线形规划的单纯形初表（表 1）与某一中间表（ 表 2）（ Min 型）： 表 1 CB XB B-1b 0 1 -3 0 2 0 x1 x2 x3 x4 x5 x6 0 x1 7 0 x4 12 0 x6 10 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 j 表 2 x2 x6 2/5 0 1/10 4/5 1/5 1 3/10 2/5 1 0 -1/2 10 j 1) 初表的出基变量为 _，进基变量为 _。 2) 填完表 2，该表是否是终表 ?_。若是，最优值 *Z _ 3) 此线形规划对偶问题的最优解 *Y _ (1998) 解： 1.下面给出某线形规划的单纯形初表（表 1）与某一中间表（表 2）（ Min 型）： 表 1 CB XB B-1b 0 1 -3 0 2 0 x1 x2 x3 x4 x5 x6 0 x1 7 0 x4 12 0 x6 10 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 j 0 1 -3 0 2 0 表 2 1 x2 4 -3 x3 5 0 x6 11 2/5 1 0 1/10 4/5 0 1/5 0 1 3/10 2/5 0 1 0 0 -1/2 10 1 j 1/5 0 0 4/5 12/5 0 4) 初表的出基变量 为 _x4_，进基变量为 _x3_。 5) 填完表 2，该表是否是终表 ?_是 _。若是，最优值 *Z _-11_ 此线形规划对偶问题的最优解 *Y ,054,51 解： 解： 解： 解： 解： 解： （二）线性规划建模 二（ 20 分）、某化学制药厂有 m 种有害副产品，它们的数量为 bi（ i=1， m）。按照规定， 必须经过处理， 制成 n 种无害物后才能废弃。设 aij 为每制成一单位第 j（ j=1， n）种无 害物可以处理掉第 i 种有害物的数量， cj 为制成一单位第 j 种无害物的费用。 1 现欲求各无害物的产量 xj 以使总的处理费用为最小，请写出此问题的线性规划模型； 2 写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。（ 2007） 解： 1 1 1 1 1 1 2 2 1 1 2 1 1 2 2 2 2 2 1 1 2 2 12 m in . , , 0 n jj j nn nn m m m n n m n z c x a x a x a x b a x a x a x b st a x a x a x b x x x ， 2 1 1 1 1 2 1 2 1 1 1 2 1 2 2 2 2 2 1 1 2 2 12 m a x . , , 0 m ii i mm mm n n m n m n m z y b a y a y a y c a y a y a y c st a y a y a y c y y y ， 经济意义： iy 为第 i 种有害副产品不经处理直接废弃的费用。 二（ 10%）、某大型企业每年需要进行多种类型的员工培训。假设共有需要 培训的需求（如技术类、管理类）为 6 种，每种需求的最低培训人数为 ai， i=1, ,6, 可供选择的培训方式（如内部自行培训、外部与高校合作培训）有 5 种，每种的 最高培训人数为 bj, j=1, ,5。又设若选择了第 1 种培训方式，则第 3 种培训方 式也要选择。记 xij 为第 i 种需求由第 j 方式培训的人员数量， z 为培训总费用。 费用的构成包括固定费用和可变费用，第 j种方式的固定费用为 hj（与人数无关）， 与人数 xij 相应的可变费用为 cij（表示第 j 方式培训第 i 种需 求类型的单位费用）。 如果以成本费用为优化目标，请建立该培训问题的结构优化模型（不解）。（ 2006） 解：二、 ijx i j设 为 第 种 需 求 由 第 种 方 式 培 训 的 人 员 数 量 ，1j0jy 选 择 培 训 方 式否 则 5 6 5 1 1 1m in j j ij ijj i jz y h c x 6 1 5 1 13 ( 1 , 2 , , 5 ) ( 1 , 2 , , 6) 0 0 ( 1 , 6 , 1 , 2 , , 5 ) 0 1 ( 1 , 2 , , 5 ) ij j j i ij i j ij j x b y i x a i yy x i j yj 或 1.某厂使用 A、 B 两种原料生产甲、乙、丙三种产品，有关数据见下表： A B 生产成本（万元 /吨） 销售价格（万元 /吨） 甲 乙 丙 1.0 0.5 0.4 0.6 0.6 0.5 8 5 18 30 20 35 原料成本（万元 /吨） 5 7 原料可用数量（吨） 350 460 （ 1）请写出使总销售利润最大的线性规划模型（其中甲、乙、丙产产量分别记为 x1,x2,x3, 约束依 A,B 原料次序） : (2)写出此问题的对偶规划模型（ 2003） 解： maxz=30 x1+20 x2+35x3-8x1-5x2-18x3-5(x1+0.4x2+0.6x3)-7(0.5x1+0.6x2+0.5x3) 目标函数 maxz=13.5x1+8.8x2+10.5x3 约束条件 x1+0.4x2+0.6x3 350 0.5x1+0.6x2+0.5x3 460 x1 0,x2 0,x3 0 对偶规划模型 目标函数 minw=350y1+460y2 约束条件 y1+0.5y2 13.5 0.4y1+0.6y2 8.8 0.6y1+0.5y2 10.5 y1 0,y2 0 三、（ 10%）某服装厂制造大、中、小三种尺寸的防寒服，所用资源有尼龙绸、尼龙棉、劳动 力和缝纫设备。缝制一件防寒服所需各种资源的数量如表（单位已适当给定）。不考虑固定 费用，则每种防寒服售出一件所得利润分别为 10、 12、 13元，可用资源分别为：尼龙绸 1500 米，尼龙棉 1000 米，劳动力 4000，设备 3000 小时。此外，每种防寒服不管缝制多少件， 只要做都要支付一定的固定费用：小号为 100元，中号为 150元 ，大号为 200元。现欲制定 一生产计划使获得的利润为最大，请写出其数学模型（不解）。 (2002) 型号 资源 小 中 大 尼龙绸 1 6 1 8 1 9 尼龙棉 1 3 1 5 1 6 劳动力 4 4 5 5 缝纫设备 2 8 3 8 4 2 解：三、解：设三种防寒服分别生产 x1,x2,x3件。 z 表示获得的利润 ,y1,y2,y3 分别表示 0-1 变 量， yi=1 表示做第 xi种防寒服（ i=1,2,3） 321321 200150100131210m a x yyyxxxz 10, 0, 10000 10000 10000 30002.48.38.2 400055.44 10006.15.13.1 15009.18.16.1 . 321 321 33 22 11 321 321 321 321 或yyy xxx yx yx yx xxx xxx xxx xxx ts （三）互补松弛应用 二（ 8%）、线性规划问题 12 12 12 1 2 12 max 2 3 2 2 12 28 4 16 4 12 ,0 z x x xx xx x x xx 已知其最优解 x1， x2 0，而第 1， 4 两种资源（相应于第 1， 4 两约束）均有余量，应用互 补松弛定理求出原问题和对偶问题的最优解。（ 2005） 解：二 对偶问题 1 2 3 4 1 2 3 1 2 4 m in 1 2 8 1 6 1 2 2 4 2 2 2 4 3 0 , 1 , 2 , 3 , 4i W y y y y y y y y y y yi 3422 242,0,0 421 32121 yyy yyyxx 其对偶问题取严格等式 （ *） 14 1 4 ( 1 ) ( 4 )0 , 0yy 第 ， 两 种 资 源 有 剩 余 ， 即 原 问 题 约 束 、 取 严 格 不 等 式对 应 对 偶 问 题 变 量 代入（ *）式， 24 32 yy ， 32 2y 23,81 23 yy 14 0 8 1 2 3 0 1216812* W *14zw 由 1 2 1 12 2 8 44 1 6 2x x xxx 综上，原问题最优解 14,24 * Zx T 对偶问题最优解 14,0 81230 * Wy T （四）灵敏度分析 三（ 25%）、派公司是一个生产高尔夫器材的小型公司，近 期推出了高、中价位的高尔 夫袋新产品（标准袋和高档袋），经销商对此产品十分感兴趣，并订购了派公司下 3 个月的 全部产品。 该高尔夫袋的生产过程主要包括 4 道工序：切割并印染原材料、缝合、成型（插入支 撑架和球棒分离装置等）、检验和包装。有关数据如表 1。派公司须决定标准袋和高档袋各 生产多少可使公司的总利润最大。 表 1 时间单耗 产品 （小时） 工序 标准袋 高档袋 3 个月内最大生产能力（小时） 切割印染 7/10 1 630 缝合 1/2 5/6 600 成型 1 2/3 708 检验包装 1/10 1/4 135 产品单位利润（美元） 10 9 (1) 写出此问题的线性规划模型，约束依表 1 中次序； (2) 引入松弛变量（依约束次序）后用单纯形法计算得某单纯形表如表 2，请填完表中 空白，并判断其是否终表，如果是，请写出最优生产计划、最 大利润和资源剩余； 表 2 CB XB B-1b 10 9 0 0 0 0 x1 x2 x3 x4 x5 x6 9 x2 252 0 x4 120 10 x1 540 0 x6 18 1 1.875 0 -1.3125 0 0 -0.9375 1 0.15625 0 0 -1.25 0 1.875 0 0 -0.34375 0 0.140625 1 j -6.9375 (3) 写出此问题的对偶问题的模型，及对偶的最优解与最优值； (4) 写出成型时间的影子价格，求使该影子价格不变的成型时间的变化范围； (5) 若标准袋的利润可能发生变化，则其在何范围内变化时，可使原最优计划不改变 ？ 图示说明其几何意义。（ 2005） 解：三 设标准袋生产 1x ,高档袋生产 2x （ 1） 21 910m ax xxZ 0, 135 4 1 10 1 708 3 2 600 6 5 2 1 630 10 7 21 21 21 21 21 xx xx xx xx xx （ 2） bBXC BB 1 10 9 0 0 0 0 1x 2x 3x 4x 5x 6x 9 x2 252 0 x4 120 10 x1 540 0 x6 18 0 1 1.875 0 -1.3125 0 0 0 -0.9375 1 0.15625 0 1 0 -1.25 0 1.875 0 0 0 -0.34375 0 0.140625 1 j 0 0 -4.375 0 -6.9375 0 1j j B jC C B P 375.4 34375.0 25.1 9375.0 875.1 0100903133 pBC )6,1(0 jj 是终表 最优生产计划 1801200252540x ，即普通袋 540 个，高档袋 252 个 最大利润 Z 7668252540910* (美元 ) 3 4 5 60 1 2 0 0 1 82 4 1 2 0 1 8x x x x 因 为 松 弛 变 量 ， ， ，所 以 第 ， 种 资 源 有 剩 余 ， 分 别 为 ， 。 （ 3）对偶问题模型： 0,0 9 4 1 3 2 6 5 10 10 1 2 1 10 7 135708600630m i n 21 4321 4321 4321 yy yyyy yyyy yyyyW 对偶问题最优解： 09675.60375.4* y 由对偶问题的强对偶性知，对偶问题与原问题的最优值相同 W*=Z*=7668 (美元 ) （ 4）成型时间影子价格为 6.9375 1.875 0 1.3125 0 630 0.9375 1 0.15625 0 600 0 1.25 0 1.875 0 708 0.34375 0 0.140625 1 135 1 .875 630 1.3125 ( 708 ) 0 0.9375 630 1 600 0.15625 ( 708 ) 0 1.25 630 1 .87 b b b 使 该 影 子 价 格 不 变 的 成 型 时 间 的 变 化 范 围 应 满 足 即 5 ( 708 ) 0 0.34375 630 0.140625 ( 708 ) 1 135 0 b b （ 5） 1c 变化，可能影响检验数，故令 11 1 3 3 3 1 5 5 5 9 0 10 0 1.875 0.9375 0 9 0 10 0 0 1.25 0.34375 1.3125 0.15625 0 9 0 10 0 0 1.875 0.140625 j j B j j j B B C C B P C C B P C C B P C C C B P C 1 6 .8 7 5 1 .2 5 ( 1 0 ) 0 1 1 .8 1 2 5 1 .8 7 5 ( 1 0 ) 0 3 .7 5 3 .5 C C C 由 此 得 解 得 二（ 23%）、某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决 定进行一次大规模的广告行动。表 1 给出了公司准备做广告的三种产品名称、估计每做一单 位广告（一个广告标准批量）使每种产品的市场份额增加量、公司拟定的广告后每种产品市 场份额增加量的最低目标和两种可选的广告方式的单价。 表 1 单位增量 广告种 类 产品 电视 印刷媒体 广告后市场份额最低增 量 去污剂 0% 1% 3% 液体洗涤剂 3% 2% 18% 洗衣粉 -1% 4% 4% 广告单位成本（万元） 100 200 其中洗衣粉的市场份额出现负值是由于液体洗涤剂的份额增加会造成洗衣粉份额的减 少。 现公司需拟定使广告总费用最少的广告计划，即决定电视和印刷媒体的广告数量（分别 记为 x1 和 x2）。 1. 请写出此问题的线性规划模型（约束依表 1 中产品的次序），并将模型化为标准型。 2. 用（ Min 型）单纯形法求解此问题，得单纯形终表如表 2. 表 2 CB XB B-1b 100 200 0 0 0 M M M x1 x2 x3 x4 x5 x6 x7 x8 0 x5 4 1/3 1 14/3 -1/3 -1 100 x1 4 -1/3 0 -2/3 1/3 0 200 x2 3 0 0 1 0 0 j 400/3 100/3 M-400/3 M-100/3 M （ 1）请填完表中空白；（ 2）由表指出最优广告计划并求出相应的最低广告费用，此最优计 划使每种产品的市场份额最低增量目标达成情况如何？ 3. 写出此问题的对偶问题模型，由表 2 求出对偶最优解 Y*,并解释 Y*的实际意义。 （ 2004） 1. min Z=100 x1+200 x2 2 12 12 3 3 2 18 44 x xx xx 标准型： 0,0,0,0,0 44 1823 3 54321 521 421 32 xxxxx xxx xxx xx 2. (1) CB XB B-1b 100 200 0 0 0 M M M x1 x2 x3 x4 x5 x6 x7 x8 0 x5 4 0 0 -14/3 1/3 1 14/3 -1/3 -1 100 x1 4 1 0 2/3 -1/3 0 -2/3 1/3 0 200 x2 3 0 1 -1 0 0 1 0 0 j 0 0 400/3 100/3 0 M-400/3 M-100/3 M (2) 最优广告计划 Tx )3,4( ，即电视广告数量为 4，印刷广告数量为 3，最低费用： W=1000 达成情况为去污剂增加 3%，恰好达标 洗衣剂增加 18%，恰好达标 洗衣粉增加 8%，超额 4%完成 (3) 对偶模型为： 0,0,0 20042 1003 4183m a x 321 321 32 321 yyy yyy yy yyyf 对偶最优解为： y=(400/3,100/3,0) 经济意义： yi 代表三种 产品的广告的投资， 3， 18， 4 为每种产品广告单位投资后的手机， 100， 200 代表用于电视及印刷品的投资额，故该模型的含义为用每种产品的头则使其在不 超过约束的条件下达到利润最大化。 (3)(30%)考虑线性规划问题 Min z=-4x1+x2+30 x3-11x4-2x5+3x6+10 x7 -2x1+6x3+2x4-3x6+x7=20 -4x1+x2+7x3+x4-x6=10 -5x3+3x4+x5-x6=60 Xj 0(j=1,2, 7) 用单纯型法求解 ,初表及终表如下 : 初表 CB XB B-1b -4 1 30 -11 -2 3 10 X1 x2 x3 x4 x5 x6 x7 -2 0 6 2 0 -3 1 -4 1 7 1 0 -1 0 0 0 -5 3 1 -1 0 检验数 终表 -4 x1 5/4 45/2 3 x6 15/2 -7/24 0 1/24 1/12 1/12 1 5/12 -1/6 1/4 0 1/4 -1/2 检验数 1.填完初表和终表中各空 白 ,并说明所得最优解是否是唯一的 ,为什么 ? 2.考虑当 b 变为 1813 60 b 时 ,对最优解有什么影响 ?当 b 变为 1814 60 b 时 ,对最优解是否有影 响 ? 3.对偶问题最优解 ?（ 2003） 解： CB XB B-1b -4 1 30 -11 -2 3 10 X1 x2 x3 x4 x5 x6 x7 10 x7 20 1 x2 10 -2 0 6 2 0 -3 1 -4 1 7 1 0 -1 0 -2 x5 60 0 0 -5 3 1 -1 0 检验数 20 0 -47 -26 0 32 0 j =Cj-CBB-1Pj 1 =-4-(10 1 -2) 2 4 0 =-4+24=20 6 =3=(10 1 -2) 31 1 =32 3 =30-(10 1 -2) 67 5 =-47 4 =-11-(10 1 -2) 21 3 =-26 -4 x1 5/4 -11 x4 45/2 3 x6 15/2 1 -7/24 -7/4 0 1/24 0 1/12 0 1/12 -5/2 1 5/12 0 -1/6 0 1/4 -5/2 0 1/4 1 -1/2 检验数 0 0 3 0 2 0 10 B-1=B-1AN= 1 / 1 2 7 / 2 4 1 / 2 41 / 6 1 / 1 2 5 / 1 2 1 / 2 1 / 4 1 / 4 B-1P3= 1 / 1 2 7 / 2 4 1 / 2 41 / 6 1 / 1 2 5 / 1 2 1 / 2 1 / 4 1 / 4 6 7 5 = 7/45/2 5/2 2 =1-(-4 -11 3) 7/241/12 1/4 =0 不唯一，因为存在非基变量检验数为零，则有多个最优解 B-1b= 1 / 1 2 7 / 2 4 1 / 2 41 / 6 1 / 1 2 5 / 1 2 1 / 2 1 / 4 1 / 4 18 13 60 = 5/24 123 12 19 4 0 无影响 B-1b= 1 / 1 2 7 / 2 4 1 / 2 41 / 6 1 / 1 2 5 / 1 2 1 / 2 1 / 4 1 / 4 18 14 60 = 1/12/12 1/12 0 有影响 CBB-1=（ -4 -11 3） 1 / 1 2 7 / 2 4 1 / 2 41 / 6 1 / 1 2 5 / 1 2 1 / 2 1 / 4 1 / 4 =（ 3 1 -4） Y=（ 3 1 -4） 二、（ 17%）已知线性规划问题 max z = (c1+t1) x1 + c2x2 + c3x3 + 0 x4 + 0 x5 )51(0 3 . 225323222112 214313212111 ，jx tbxxaxaxa tbxxaxaxa ts j 当 t1=t2=0时，用单纯形法求得最终表如下： X1 X2 X3 X4 X5 X3 5/2 0 1/2 1 1/2 0 X4 5/2 1 1/2 0 1/6 1/3 Cj-Zj 0 4 0 4 2 要求： 1.确定 c1,c2,c3,b1,b2,a11,a12,a13,a21,a22,a23的值； 2当 t2=0 时， t1在什么范围内变化上述最优解不变； 3当 t1=0 时， t2在什么范围内变化上述最优基不变。 (2002) 解：二、 1 10 52/5 2/53/106/12/1 2 1 2 11 bbbbbB 又由 j=Cj-CBB-1Pj，设 10 2 6 3/1 0 )(02 6/1 2/1 )(04 2/1 2/1 )(4 3 2 1 13 13 132 C C C CC CC CCC 3/106/1 2/1012/1 2/110 2011023160 2001222160 1001121130 初表： 1001121130 对应得到 a11=0,a12=1,a13=2,a21=3,a22=-1,a23=1 2 t1 变化，将影响各检验数的变化，检验各非基变量检验数，若 j 0，则最优解不变 86 0 3/1 0 )610(0 0 6/1 2/1 )610(0 0 2/1 2/1 )610(2 1 15 14 12 t t t t 3 t2 变化即 b 变化，要使最优基不变则 B-1b 0，因为 3/106/12/11 B ，所以 153/50)10(3/1)35(6/1 0)35(2/1010 353/106/1 2/1 2 22 2 2 21 ttttttbB （行政管理约束） （劳动力约束） 技术服务约束 划模型，并 产量的线性规了使总利润最大的产品据公司实际情况，建立管理，公司经理助理根 力和行政种资源：技术服务，动需要种产品：分）某公司生产二、（ 300622 6005410 )(100 . 4610m a x 3,318 321 321 321 321 321 xxx xxx xxx ts xxxZ xxx 采用单纯形法求得最优表格如下： C8 X8 C8 b X8 10 6 4 0 0 0 Qj X1 X2 X3 X4 X5 X6 6 X2 400/6 0 1 5/6 10/6 -1/6 0 10 X1 200/6 1 0 1/6 -4/6 1/6 0 0 X5 100 0 0 4 -2 0 1 -Z 4400/6 0 0 -8/3 -10/3 -2/3 0 qj 在向总经理汇报时，总经理提出以下问题： 1 公司 3中资源的影子价格各是多少？ 2 若要现行解保持最优，则产品 X 1的单位利润不得低于何值？ 3 若产品 X3值得生产的话，它的单位利润应是多少？ 4 制造部门提出要生产一种新产品，该单位产品要技术服务 1小时，劳动力 4小时，行政 管理 3小时。销售部门预测这种产品出售时可获 8元的单位利润，管理部门是否考虑应 将此新产品投产？ 现请帮助经理助理回答以上 问题。（ 2001） 最优，则：的情况下，现行解保持，在保持 检验数变化将影响各非基变量 是基变量 的单位利润为种产品，产品对于第 ，劳动力：为：技术服务：种资源的影子价格分别公司解： 0 ,1.2 3 2 3 10 3.1 543 1 1 111 C x Cxx 应将新产品投产 ，则设新产品为 至少应为，即在单纯性表中应为基变量，值为生产，则若产品 ，现行解保持最优有影响，只要保证变化只对是非基变量，对于 ，现行解保持最优只要使： 检验数变化将影响各非基变量为基变量，同理的：对于 0682 3 4 1 102 0 6 1 6 4 0 6 1 6 10 01068.4 3 20 0.3 3 20 0 3 20 4 6 1 6 5 0106 0 104 0 6 10 6 1 0 3 20 6 10 0 6 5 3 7 186 0 6 1 1 0 6 1 6 1 060 0 6 4 10 2 6 4 6 10 060 0 6 1 1 4 6 1 6 5 064 77 3333 3333 33333 2 25 24 23 222 1 115 114 113 x Cxx CCC Cxx C C C C CxC C CC CC CC 4 6 1 6 5 01068.4 3 20 0.3 77 3333 ，则设新产品为 至少应为，即在单纯性表中应为基变量，值为生产，则若产品 x Cxx 二（ 20） 1 1 2 2 11 1 12 2 1 21 1 22 2 2 12 s.t a x x b a x a x b x ,x 0 M a x z c x c x a 有 一 线 性 规 划 为 设 43,XX 为引入的松弛变量。得到最优 单纯形表如上表，要求： （ 1）利用最优解求 c1,c2. （ 2）利用 最优解求 b1,b2 （ 3） 2C 能变化多少而不至影响最优解；当 12C 时求最优解； （ 4）假定用 b+b 代替 b,其中 )( 11 b ,求出使最优基保持不变的 的范 围 . （ 5）求出各资源的剩余量和影子价格。 (1997) 解：二 BX 1X 2X 3X 4X 解 1X 2X 1 0 3 -1 0 1 -1 1 1 2 J 0 0 -3 -1 -8 Bx 1x 2x 3x 4x 解 1x 1 0 3 -1 1 2x 0 1 -1 1 2 j 0 0 -3 -1 -8 1 1 2 2 11 1 12 2 13 3 1 21 1 22 2 23 4 2 1 2 3 4 m a x , , , 0 z c x c x a x a x a x b a x a x a x b x x x x （ 1） 13 3 3BC C B P 12 330 1CC 14 4 4BC C B P 12 110 1CC 122, 3CC (2) 11 2 3 1 11 1 2bBb b 12 12 3 12bbbb 112 12 2 3 31 2 27 2 bbb bb b (3) 2C 的变化影响检验数，设 2C 的变化量为 C 3 30 2 , 3 01C 即 6 3 0C 4 10 2 , 3 01C 2 3 0C 13C 当 2C =1 时 2 1 0 0 BC BX 1Bb 1X 2X 3X 4X 2 1X 1 1 2X 2 1 0 3 -1 0 1 -1 1 J 0 0 -5 1 2 1X 3 0 4X 2 1 1 2 0 0 1 -1 1 J 0 -1 -4 0 11 44 m in 1 950 11 80 k k k k kf S V f S fS 3,0,0,2X 2 3 0 1 6Z （ 4） 1* 3 3 1 12 0 1 1 7 1 2 B b b
展开阅读全文