天大97-08试题分类

一、线性规划 二、运输问题 三、多目标规划 四、动态规划 五、图论 六、网络计划技术 七、决策论 八、存储论 九、排队论 十、对策论 十一、模拟技术 一、线性规划 （一）选择填空题 （二）线性规划建模 （三）互补松弛应用 （四）灵敏度分析 （五）证明题 （一）选择填空题 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)初表的出基变量为　　　　　，进基变量为　　　　　。 (3)填完终表。 (6)若原问题增加一个新的非负变量，则对偶问题的最优目标值将（变大、不变、变小）　　　　　。（2007） 解：1．(1)出基变量为x4；进基变量为x3。 (2) 。 (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) (5) (6) 变小 1．用图解法解线性规划时，以下几种情况中不可能出现的是（ ）。 A．可行域（约束集合）有界，无有限最优解（或称无解界） B．可行域（约束集合）无界，有唯一最优解 C．可行域（约束集合）是空集，无可行解 D．可行域（约束集合）有界，有多重最优解 （2006） 解：1． A 2．根据线性规划的互补松弛定理，安排生产的产品机会成本一定（ ）利润。 A． 小于 B． 等于 C． 大于 D． 大于等于 （2006） 解：2． B 1．用大M法求解Max型线形规划时，人工变量在目标函数中的系数均为____________，若最优解的_______________中含有人工变量，则原问题无解。（2005） 解：1、-M 基变量 1. 设线性规划问题 有最优解 和影子价格 ,则线性规划问题 的最优解= ​​​​​​​​​​​​ ，影子价格= 。 （2004） 解：1. x* 2y* 3. 某工程公司拟从1、2、3、4四个项目中选择若干项目。若令 请用 的线性表达式表示下列要求：（1）若项目2被选中，则项目4不能被选中： （2）只有项目1被选中，项目3才能被选中： 。（2004） 解：3. 一、简答（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 =y3* ⑷表明增加一个单位的运量会引起总运输费用的变化 1． 线性规划原问题中约束的个数与其对偶问题中的 变量 个数相等。若原问题第j个约束为等式，则对偶问题第j个 变量 自由。（2002） 解： 2． 设线性规划问题max:{cx|Ax≤bx≥0}有最优解，且最优解值z>0；如果c和b分别被v>1所乘，则改变后的问题 也有 （也有、不一定有）最优解；若有最优解，其最优解 大于 (大于、小于、等于)z。（2002） 1．下列数学模型中 a 是线性规划模型。(2001) 解： 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. 设有线性规划问题 ，有一可行基B（为A中的前m列），记相应基变量为 ，价格系数为CB，相应于非基变量为XN，价格系数为CN，则相应于B的基本可行解为X= ；用非基变量来表示基变量的表达式为XB= ；用非基变量表示目标函数的表达式为f= ，B为最优基的条件是 。（2000） 解： 3. 线性规划（Min型）问题有多重最优解时，其最优单纯形表上的特征为： （2000） 解： 6. 某足球队要从1，2，3，4，5号五名队员中挑选若干名上场。令 请用xi的线性表达式表示下列要求：（1）从1，2，3中至多选2名： （2）如果2号和3号都上场，则5号不上场： （3）只有4号上场,1号才上场：(2000) 解： 1．某工程公司拟从四个项目中选择若干项目，若令 请用xi的线性表达式表示下列要求： （1）从1，2，3项目中至少选择一个： ， （2）只有项目2被选中，项目4才能被选中 。（1999） 解：1、x1+x2+x3≥1 x2≥x4 2．考虑线形规划问题 用单纯型法求解，得其终表如下： 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+ 其中x4位松弛变量，x5为人工变量。 （1）上述模型的对偶模型为 ， （2）对偶模型的最优解为 ， （3）当两种资源分别单独增加一个单位时，目标函数值分别增加 和 ， （4）最优基的逆矩阵 （5）如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？（1999） 解：2．（1） （2）Y*=（ ，- ） （3） ，- （4） （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 表2 x2 x6 2/5 0 1/10 4/5 1/5 1 3/10 2/5 1 0 -1/2 10 1) 初表的出基变量为__________，进基变量为_________。 2) 填完表2，该表是否是终表?_________。若是，最优值 ________ 3) 此线形规划对偶问题的最优解 _______ (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 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 1/5 0 0 4/5 12/5 0 4) 初表的出基变量为_____x4_____，进基变量为___x3______。 5) 填完表2，该表是否是终表?____是_____。若是，最优值 __-11______ 此线形规划对偶问题的最优解 EMBED Equation.3 解： 解： 解： 解： 解： 解： （二）线性规划建模 二（20分）、某化学制药厂有m种有害副产品，它们的数量为bi（i=1，…，m）。按照，必须经过处理，制成n种无害物后才能废弃。设aij为每制成一单位第j（j=1，…，n）种无害物可以处理掉第i种有害物的数量，cj为制成一单位第j种无害物的费用。 1． 现欲求各无害物的产量xj以使总的处理费用为最小，请写出此问题的线性规划模型； 2． 写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。（2007） 解：1． 2． 经济意义： 为第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） 解：二、 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=30x1+20x2+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） （三）互补松弛应用 二（8%）、线性规划问题 已知其最优解x1，x2 0，而第1，4两种资源（相应于第1，4两约束）均有余量，应用互补松弛定理求出原问题和对偶问题的最优解。（2005） 解：二 对偶问题 （*） 代入（*）式， ， 由 综上，原问题最优解 对偶问题最优解 （四）灵敏度分析 三（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 -6.9375 (3) 写出此问题的对偶问题的模型，及对偶的最优解与最优值； (4) 写出成型时间的影子价格，求使该影子价格不变的成型时间的变化范围； (5) 若标准袋的利润可能发生变化，则其在何范围内变化时，可使原最优计划不改变？图示说明其几何意义。（2005） 解：三 设标准袋生产 ,高档袋生产 （1） （2） 10 9 0 0 0 0 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 0 0 -4.375 0 -6.9375 0 是终表 最优生产计划 ，即普通袋540个，高档袋252个 最大利润Z (美元) （3）对偶问题模型： 对偶问题最优解： 由对偶问题的强对偶性知，对偶问题与原问题的最优值相同W*=Z*=7668 (美元) （4）成型时间影子价格为6.9375 （5） 变化，可能影响检验数，故令 二（23%）、某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决定进行一次大规模的广告行动。表1给出了公司准备做广告的三种产品名称、估计每做一单位广告（一个广告标准批量）使每种产品的市场份额增加量、公司拟定的广告后每种产品市场份额增加量的最低目标和两种可选的广告方式的单价。 表1 单位增量 广告种类 产品 电视 印刷媒体 广告后市场份额最低增量 去污剂 0% 1% 3% 液体洗涤剂 3% 2% 洗衣粉 -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 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=100x1+200x2 标准型： 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) 最优广告计划 ，即电视广告数量为4，印刷广告数量为3，最低费用：W=1000 达成情况为去污剂增加3%，恰好达标 洗衣剂增加18%，恰好达标 洗衣粉增加8%，超额4%完成 (3) 对偶模型为： EMBED Equation.3 对偶最优解为：y=(400/3,100/3,0) 经济意义：yi代表三种产品的广告的投资，3，18，4为每种产品广告单位投资后的手机，100，200代表用于电视及印刷品的投资额，故该模型的含义为用每种产品的头则使其在不超过约束的条件下达到利润最大化。 (3)(30%)考虑线性规划问题 Min z=-4x1+x2+30x3-11x4-2x5+3x6+10x7 -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变为 时,对最优解有什么影响?当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 x5 60 -2 0 6 2 0 -3 1 -4 1 7 1 0 -1 0 0 0 -5 3 1 -1 0 检验数 20 0 -47 -26 0 32 0 =Cj-CBB-1Pj =-4-(10 1 -2) =-4+24=20 =3=(10 1 -2) =32 =30-(10 1 -2) =-47 =-11-(10 1 -2) =-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= B-1P3= EMBED Equation.DSMT4 = =1-(-4 -11 3) =0 ①不唯一，因为存在非基变量检验数为零，则有多个最优解 ②B-1b= EMBED Equation.DSMT4 = ≥0 无影响 B-1b= EMBED Equation.DSMT4 = ＜0 有影响 ③CBB-1=（-4 -11 3） =（3 1 -4） Y=（3 1 -4） 二、（17%）已知线性规划问题 max z = (c1+t1) x1 + c2x2 + c3x3 + 0x4 + 0x5 当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． 又由δj=Cj-CBB-1Pj，设 EMBED Equation.3 ∽ ∽ ∽ 对应得到a11=0,a12=1,a13=2,a21=3,a22=-1,a23=1 2．t1变化，将影响各检验数的变化，检验各非基变量检验数，若δj ≤0，则最优解不变 3．t2变化即b变化，要使最优基不变则B-1b≥0，因为 ，所以 采用单纯形法求得最优表格如下： 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） EMBED Equation.3 二（20％） 解 1 0 3 -1 0 1 -1 1 1 2 0 0 -3 -1 -8 设 为引入的松弛变量。得到最优单纯形表如上表，要求： （1）利用最优解求c1,c2. （2）利用最优解求b1,b2 （3） 能变化多少而不至影响最优解；当 时求最优解； （4）假定用b+λ 代替b,其中 ,求出使最优基保持不变的λ的范围. （5）求出各资源的剩余量和影子价格。(1997) 解：二 解 1 0 3 -1 1 0 1 -1 1 2 0 0 -3 -1 -8 （1） (2) (3) 的变化影响检验数，设 的变化量为 即 当 =1时 2 1 0 0 2 1 1 2 1 0 3 -1 0 1 -1 1 0 0 -5 1 2 3 0 2 1 1 2 0 0 1 -1 1 0 -1 -4 0 （4） EMBED Equation.DSMT4 （5） 第一种资源剩余为0 第二种资源剩余为0 影子价格分别为-3，-1 解： 解： 解： 解： （五）证明题 三（15分）、考虑下面两个线性规划： （2007） 解：三、 三（11%）、考虑线性规划问题（P） 1．若X1,X2均为（P）的可行解， ，证明 也是（P）的可行解； 2．写出（P）的对偶模型（仍用矩阵式表示）。（2006） 三、1证明：令 ，若 是（P）的可行解，则应满足 　　 　　 2．对偶模型 三（10%）、证明线性规划中的互补松弛定理：设（P）[max]z=CX,X {X|AX b,X 0},(D)[min]u=Yb,Y {YA b,Y 0},若 EMBED Equation.3 分别是（P）（D）的可行解， 分别是其相应的松弛变量，则 EMBED Equation.3 是（P），（D）的最优解的充要条件是： ； 并解释互补松弛定理的经济意义。（2004） 解： 三、 互补松弛定理的经济意义是：资源有剩余，则其影子价格为0，反之，影子价格为0说明资源恰好用完。 四、(21%)试证明线性规划原问题中第J个约束扩大K倍,其对偶规划最优解中第J个变量将缩小K倍（2003） 解：四、设原问题为maxZ=CX AX=b对偶 EMBED Equation.DSMT4 EMBED Equation.DSMT4 ≥ J EMBED Equation.DSMT4 = (kaj1,kaj2,…kajn) = 从而得出结论 二、（12%）有三个线性规划： 已知： ， ， EMBED Equation.3 ， 试证：（1） ；（2） 。（2000） 解：(1) (2) 2.在使用单纯形法求解线性规划问题 时，设当前基 证明：若 为某非基变量，检验数 ， 由此确定 为进基变量，则能保证新的基本可行解的目标值得以改善。(1998) 2. 一（14％） （1）请用数学方法证明，当所有非基变量检验数 时，当前基本可行解为最优。 （2）请从经济含义的角度出发，说明上述判断的正确性。(1997) 解： 一． （一）确定换出基的变量 因为总存在<0的 ，令 = EMBED Equation.DSMT4 ,其对应变量 为换出基的变量 基 b 1 0 0 0 1 0 0 0 1 0 0 （二）确定换入基变量 （1）为了使下一个表中第r行基变量为正值，因而只有对应 <0的非基变量才可以考虑作为换入基的变量 （2）为了使下一个表中对偶问题的解仍为可行解，令 称 为主元素， 为换入基的变量 设下一表中的检验数为 EMBED Equation.DSMT4 （a）对 时，因 故 有因为主元素 所以 所以 （b）对 因 故 解： 解： 解： 解： 解： 解： 解： 解： 解： 二、运输问题 ２．将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设的　　　　　，在模型中相当于增加若干个　　　　　变量。（2007）（2004） 解：2．产地或销地；松弛。 9．运用表上作业法求解运输问题时，计算检验数可以用 b ，确定初始可以用 a 。 （a）最小元素法 （b）比回路法 4. 用表上作业法求解m个发点和n个收点的平衡运输问题，其方案表上有数格的个数为 ，空格的个数为 ；若从检验数为-2的某空格调整，调量为2，则调后可使总运费下降 。(2000) 解：m+n-1, (m-1)(n-1), 4. 3．用表上作业法求解某运输问题，若已计算出某空格的检验数为-2，则其经济意义是 ，若从该空格出发进行调整，该调整量为2，则调后可使总运费下降 。（1999） 解：3、该处每增运一个单位，将使总成本降低2 二、（13%）用表上作业法求解下面的平衡运输问题 时，计算某方案的空格[i,j]检验数 ij可采用位势法，其主要步骤如下： （1）建立线形方程组Ui+Vj=Cij,其中Cij为所有有数个的运价，Ui，Vj分别称发地i和收地j的位势。 （2）令U1=0，求解得位势值Ui，Vj，i=1，……，m, j=1,……,n （3） ij= Cij-(Ui+Vj) 试证明该方法的正确性，即证明空格[i,j]的检验数为 ij= Cij-(Ui+Vj) （1999） 解： 解： 解： 解： 解： 解： 三、多目标规划 2．目标规划模型的一个主要特点是引入了______________变量，模型的目标就是这些变量的极_____（大还是小）化，模型的约束中也要包括用这些变量表示的_____________约束。（2005） 解：2、偏差 小 目标（软） 3． 目标规划模型的一个主要特点是引入了偏差变量，模型的目标就是这些变量的极 小 （大还是小化），模型的约束中也要包括用这些变量表示的目标约束。(2002) 1. 目标规划模型的特点是引入了 变量，模型的目标函数是这些变量的极 （大还是小）化，模型的约束中也含有用这种变量表示的 约束。(2000) 解：偏差变量；极小；目标（软）. 解： 解： 解： 解： 四、动态规划 四（25分）、某投资者拟对A与B两种基金进行投资，投资期限5年。该投资的收益有两部分：一是长期的至第5年末的红利收入，年利率分别为IA=0.06和IB=0.04，计复利且5年间利率不变（例如，第1年初投入A基金1元，5年后红利收入（1+0.06）5元）；二是短期的每年利息收入，两种基金在不同年份的利率iAK和iBK见下表（例如，第1年初投入A基金1元，除5年后的红利收入外，一年后还有0.02元的利息收入）。 年份 基金 1 2 3 4 5 A 0.020 0.023 0.024 0.026 0.030 B 0.050 0.050 0.055 0.045 0.055 该投资者第1年初投入资金50000元，以后第2至5年初每年还再投入10000元（不包括已投资的利息收入），收益计算方法相同（如第2年初投入A基金1元，第5年末红利收入（1+0.06）4元，同时第2至5年末还有年利息）。所有投入基金的资金（包括年利息）在第5年末之前不得支取。现投资者需决定每年初的资金（当年投入资金加已投资金的短期年利息）对基金A和B的分配额，以使第5年末总收入最大。 拟用动态规划方法解决此问题（按逆序递推），设：状态变量Sk为第k年初可分配的资金总量：决策变量xk为第k年初分配给基金A的资金量。 1． 写出：（1）状态转移方程；（2）阶段指标（提示：第5年的阶段指标因年末短期年利息收入不再投入需单独表示）；（3）基本（递推）方程。 2． 求出最优指标f5(s5)和f4(s4)以及相应的最优决策x*5(s5)和x*4(s4)。（2007） 四、 解: 1． 2． 四（18%）、某工厂生产N种产品，它们都要使用某种原材料，现该原材料共有a吨，若分配xj吨原材料给第j种产品，则可产生的收益为gj（xj），j=1，…，N。现工厂需拟定使总收益最大的原材料分配方案，试就以下1、2两小题选答一题。 1、（1）写出此问题的数学规划模型； （2）拟用动态规划方法求解，请写出此问题的阶段变量，状态变量、决策变量、状态转移、阶段指标、指标函数、基本方程（不解）。 2、若工厂生产N=3种产品（分别称为A、B、C），共有原材料a=3吨，各种产品被分配该原材料后产生的收益见表1，请用动态规划方法求解使总收益最大的分配方案。 （2006） 表1 A B C 0 0 0 0 1 10 6 8 2 17 17 11 3 20 18 11 解：四 2 阶段变量k=1，2，3 表示给3种产品分配原材料的过程 状态变量sk，表示给第k种产品分配原料时拥有的资源数 决策变量xk，表给第k中产品分配的原料量 状态转移方程： 阶段指标：vk为离散型，见下表 基本方程 EMBED Equation.3 k sk xk vk vk+fk+1(sK+1) fk(sK) pkn 3 0 0 0 0+0 0 0 1 1 10 10+0 10 1 2 2 17 17+0 17 2 3 3 20 20+0 20 3 2 0 0 0 0+0 0 0-0 1 0 0 0+10 10 0-1 1 6 6+0 2 0 0 0+17 17 0-2 或2-0 1 6 6+10 2 17 17+0 3 0 0 0+20 27 2-1 1 6 6+17 2 17 17+10 3 18 18+0 1 3 0 0 0+27 27 0-2-1 1 8 8+17 2 11 11+10 3 11 11+0 最大收益27，分配方案0-2-1，即给A分配0吨，B分配2吨，C分配1吨。 四（9%）、考虑下面的非线性整数规划 其中 现拟用动态规划方法解此问题（用通常的逆推解法），要求： (1) 写出以下表达式或集合的具体内容： ①本问题的状态转移方程 EMBED Equation.3 ②递推方程 ③第1阶段的状态集合 ④第2阶段状态为5时的允许决策 的集合 ={ }； (2) 计算第2阶段状态为12时的最优指标函数值 及相应的最优决策 。 （2005） 解：四 （1） ① ② ③ ④ （2） 第2阶段k=12,则3段k=8 Ⅱ2 k Sk xk vk Vkfk+1(Sk+1) Fk(Sk) pnk 2 12 0 0 0 3 0 12 1 1 1 3 3 2 2 2 3 6 3 3 3 3 9 4 4 4 3 12 5 5 5 3 15 6 6 6 3 18 7 7 7 3 21 8 8 8 3 24 9 9 9 3 27 10 10 10 3 30 11 11 11 3 33 12 12 12 3 36 四（15%）、某工厂购进100台机器，准备用于生产A，B两种产品。若生产产品A，每台机器每年可收入45万，损坏率为65%，若生产产品B每台机器年收入35万，损坏率为35%，估计三年后将有新的机器出现，旧的机器将全部淘汰。请在下列两问中任选一问： 1、 试问每年就如何生产，使三年内的收入最多？运用动态规划方法具体计算求解。 2、 写出用动态规划方法求解时的阶段变量、状态变量、决策变量、状态转移、阶段指标、指标函数、基本方程（递推公式），不必具体计算。但请简要说明当不能肯定三年后将有新的机器出现，而要求到第三年末保留一定数量的旧机器时求解过程将做何调整。（2004） 解：四、 阶段变量K=1,2,3表第K年，状态变量SK表第K年初的好机器数目，决策变量XK，表示第K年决定把XK台机器投入A产品的生产，状态转移方程SK+1=0.35XK+0.65（SK-XK） 阶段指标，VK=45XK+35（SK-XK） 递推方程： 具体计算如下： k=3时： k=2时： k=1时： 生产计划如下： 即前两年把所有机器投入B产品，最后一年全部投入A产品 最大收入： =7676.25元 2.某工厂考虑设备n年的更新计划,在每年初需作出设备是更新还是继续使用的决策,设备使用一年产生的利润,设备使用一年的维修费,以及设备的更新费用都与设备已使用的年数(设备年龄t)有关. 设r(t)为t年龄设备使用一年的利润 u(t)为t年龄设备使用一年的维修费用 c(t)为t年龄设备当年更新的费用 用动态规划方法求出n年内每年的最佳决策而使n年总利润最大.试引入0-1变量表示决策变量,并由此统一表示动态规划有关的概念和式子(不必求解):阶段,状态变量,决策变量,状态转移,阶段指标.（2003） 解：⒉设阶段变量k=1,2…n,状态变量 表示k年初设备的年龄 决策变量 表示更新， 表示继续使用 状态转移