中科大考研运筹学05-09.doc

一、线性规划建模1、某公司现有大米、玉米、面粉1820吨，1760吨和1700吨，拟调入对上述粮食物资有需求的甲，乙，丙，丁四个地区。已知：甲，乙，丙，丁四个地区对上述物资的总需求为1300吨，1280吨，1290吨和1350吨，各种物资调往各地区可以获得的利润如表1所示。问该公司应如何安排调运计划，才能使得公司获得的利润最大？ （运输问题）（1998年，2009年） 大米玉米面粉甲250300320乙240280290丙280340310丁220260275表1解：参考课本p90产1820+1760+1700=5280销1300+1280+1290+1350=52202、某昼夜服务的公交线路每天各时间区段内所需要的司乘人员如表2：班次时间所需人数16：00-10：0070210：00-14：0080314：00-18：0070418：00-22：0060522：00-2：002062：00-6：0030表2设司乘人员分别在各时间区段一开始上班，并连续工作八小时，问该公交线路至少应配置多少司乘人员才能满足上述要求，建立这个问题的线性规划模型。（1999，2007）p46解：设xi为第i阶段开始工作的人。3、清华大学修订版P42，例13。（2006年）4、某公司拟在下一个年度的1-4的4个月内需租用仓库堆放物资，每个月份所需仓库的面积于表3.仓库租借费用随合同期而定，期限越长，折扣越大，具体数字参见表4.租借仓库的合同每月初都可办理。每份合同具体租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租借合同，每次办理时可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。（2005）月份1234所需仓库面积（100m2）27223224表3合同租借期限（个月）1234合同租借期内费用（元/100 m2）4000570072008500表4解：设xij为第i个月开始的期限为j个月的租借合同所租借的面积（100m2）。5某厂在计划期内生产甲、乙、丙三种产品，产品甲一次经A、B设备加工，产品乙经A、C设备加工，产品丙经C、B设备加工，已知有关数据如下表所示，请为该厂制定一个最优的生产计划。（建模并求解，2004） 机器产品机器生产率（件/小时）原料成本（元）产品价格（元）ABC甲10201550乙20525100丙10201045机器成本（元/小时）200100200每周可用小时数504060解：设生产甲产品件，乙产品件，丙产品件，则该线性问题可以表示为6、三年内有五项工程可以考虑施工，每项工程的期望收入和年度费用以及每年可用的金额（万元），如下表所示，假定每一项已选定的工程要在整个三年内完成，试选出使得总收入为最大的那些工程（建模并求解）（2002）工程费用收入第一年第二年第三年一51820二471040三39220四74115五861030每年可用金额252525解：设，模型为7、某化工厂用原料ABC加工成三种不同的化工产品甲乙丙，已知各种产品中ABC含量，原料成本各种原料每月限制用量以及三种产品的单位加工费和售价如下表所示，问该厂每月应生产这三种产品各多少千克，才能使该厂的获利最大，试建立这个线性规划问题的数学模型（2001）甲乙丙原料成本（元/千克）每月限制用量（千克）A60%15%10%22000B1.52500C20%60%50%11300加工费（元/千克）0.500.400.30售价（元/千克）3.402.852.25二、线性规划相关证明1、 若某一线性规划问题同时在其可行域D上的两个顶点取得最优解，证明该线性规划问题有无穷多个最优解。证明：设线性规划的标准型为设X1与X2为该线性规划问题可行域D上的两个最优解，令X0 =X1 +(1-) X2，其中0,1.已知，则2、证明：若线性规划问题的可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点处达到最优。证明：p193、线性规划问题的可行域D是个凸集。（1999,2004）4、若f(x)为定义在凸集D上的凸函数，证明：f(x)在D上任一极小值点就它在D上的最小值点（全局最小值点）（2002，2001）5、设有线性规划问题，为该问题的最优解，若目标函数中的C用代替后，其最优解变为，试证明（2002）6、参考书76页，2.5（2000）三、单纯形法，对偶问题及灵敏度分析1、试分析下面问题中最优解随参数的变化（）(2008年，2000年)解：标准型运用单纯型法求解（1） 初始基可行解将相关数字填入单纯形表得到cjb2-54-200CBXBx1x2x3x40x3411100x43-2101-z02-54-200（2） 检验数：填入上表中。（3.1）当时，无可行解。（3.2）当，即且时，最优解为，目标函数取值为：（3.3）当，即时，有检验数大于0，且P1，P2有正分量存在。此时x2为换入变量。计算1=4/1，2=（3-）/1，则min（1，2）=3-，因此x4为换出变量。cjb2-54-200CBXBx1x2x3x40x34111040x43-21013-z02-54-200cjb2-54-200CBXBx1x2x3x40x31+-101-14-2x23-2101-z0-6-000最后一行检验数全为负或零，因此当时，最优解为，目标函数取值：。（3.4）当，即时，检验数大于0，且P1，P2有正分量存在。此时,因此x1为换入变量.计算1=4/1，2=（3-）/2.（3.4.1）当时，min（1，2）=（3-）/2，因此x4为换出变量。cjb2-54-200CBXBx1x2x3x40x34111040x43-2101(3-)/2-z02-54-200cjb2-54-200CBXBx1x2x3x40x3(5+)/201/21-1/25+2-5x1(3-)/211/201/23-z003-/205/2-1因为3-/20,且5/2-13-时，即时，min（1，2）=3-，因此x1为换出变量。cjb2-54-200CBXBx1x2x3x40x3(5+)/201/21-1/25+2-5x1(3-)/211/201/23-z003+/205/2-1cjb2-54-200CBXBx1x2x3x40x31+-101-14-2x23-2101-z0-6-00-2+5最后一行检验数全为负或零, 因此当时最优解为,目标函数取值：。(3.4.1.2) 当，有5+3-，min（1，2）=5+，因此x3为换出变量。cjb2-54-200CBXBx1x2x3x40x3(5+)/201/21-1/25+2-5x1(3-)/211/201/23-z003+/205/2-1cjb2-54-200CBXBx1x2x3x44-2x2-1-012-12-5x1(3-)/210-11-z000-6-2+3最后一行检验数全为负或零，因此当时最优解为，目标函数取值：。（3.4.2）当时，min（1，2）=4，因此x3为换出变量。cjb2-54-200CBXBx1x2x3x40x34111040x43-2101(3-)/2-z02-54-200cjb2-54-200CBXBx1x2x3x42-5x1411100x4-5-0-1-21-z002+3-2+50最后一行检验数全为负或零, 因此当时最优解为,目标函数取值：。2、设有线性规划问题： (1)试求：（1）该问题的对偶问题；（2）最优解；（3）若目标函数中x1的系数由2变为2+，试讨论最优解的变化；（4）在保持现行最优基不变的前提下，假如要把一个约束条件的右端扩大，应扩大哪个最有利？（2005）解：（1）令，则原规划问题变为： (2)因此对偶问题为： （2）用单纯形法求最优解（P32）cjb2-530-M-MCBXBx1x2x3x4x5x6-Mx51021-5-1105-Mx671110017-z2+3M-5+2M3-4MM00cjb2-530-M-MCBXBx1x2x3x4x5x62x1511/2-5/2-1/21/20-Mx6201/27/21/2-1/214/7-z0-6+M/28+7M/21+ M/2-M/2-10cjb2-530-M-MCBXBx1x2x3x4x5x62x145/716/70-1/71/75/73x34/701/711/7-1/72/7-z0-50/70-1/7-M+1/7-M-16/7因此模型（2）的最优解为，目标函数值为模型（1）的最优解为，目标函数值为（3） 模型（2）变为 (3)cjb2+-530-M-MCBXBx1x2x3x4x5x6-Mx51021-5-1105-Mx671110017-z2+3M-5+2M3-4MM00cjb2+-530-M-MCBXBx1x2x3x4x5x62+x1511/2-5/2-1/21/20-Mx6201/27/21/2-1/214/7-z0-6-/2+M/28+5/2+7M/21+/2+ M/2-/2-M/2-10cjb2+-530-M-MCBXBx1x2x3x4x5x62+x145/716/70-1/71/75/73x34/701/711/7-1/72/7-z0-50/7-6/70-1/7+/7-M+1/7-/7-M-16/7-5/7当，即时，最优解不变。当，即时，cjb2+-530-M-MCBXBx1x2x3x4x5x62+x145/716/70-1/71/75/715/23x34/701/711/7-1/72/74-z0-50/7-6/70-1/7+/7-M+1/7-/7-M-16/7-5/7cjb2+-530-M-MCBXBx1x2x3x4x5x62+x1310-6-11-1-5x240171-12-z0040+67+-M-7-M+12+因此模型(3)的最优解为，目标函数值为模型（1）的最优解为，目标函数值为（4）变化第一个约束条件时：cjb2-530-M-MCBXBx1x2x3x4x5x6-Mx510+s21-5-1105+s/2-Mx671110017-z2+3M-5+2M3-4MM00，即时cjb2-530-M-MCBXBx1x2x3x4x5x62x15+s/211/2-5/2-1/21/20-Mx62-s/201/27/21/2-1/214/7-s/7-z0-6+M/28+7M/21+ M/2-M/2-10cjb2-530-M-MCBXBx1x2x3x4x5x62x145/7+s/716/70-1/71/75/73x34/7-s/701/711/7-1/72/7-z0-50/70-1/7-M+1/7-M-16/7此时最优解为，目标函数最大值为变化第二个约束条件时：cjb2-530-M-MCBXBx1x2x3x4x5x6-Mx51021-5-1105-Mx67+t1110017+t-z2+3M-5+2M3-4MM00，即cjb2-530-M-MCBXBx1x2x3x4x5x62x1511/2-5/2-1/21/20-Mx62+t01/27/21/2-1/214/7+2t/7-z0-6+M/28+7M/21+ M/2-M/2-10cjb2-530-M-MCBXBx1x2x3x4x5x62x145/7+5t/716/70-1/71/75/73x34/7+2t/701/711/7-1/72/7-z0-50/70-1/7-M+1/7-M-16/7此时最优解为，目标函数最大值为很明显当扩大第二项约束时最有利。3、已知线性规划问题：（2000,2004）其最优解为：（1） 写出该问题的对偶问题，并求出对偶问题的最优解；（2） 求出k的值解：（1）由及互补松弛性质得得到，得到k=1.4、设有线性规划问题（2002）试求（1）该问题的对偶问题 （2）写出该问题的标准型，并写出单纯性法求解的初始单纯型表。解：5、设有线性规划问题：（2002）已知该问题的最优解为：，试根据对偶理论直接求出其对偶问题的最优解。解：对偶问题为由互补松弛性得，解的四、指派问题1、一个公司要分派5个推销员去5个地区推销某种产品，5个推销员在各个地区推销这种产品的预期利润如下表所示，问应如何分派这5个推销员才能使得公司总的利润最大。（2003，2005）解：引入变量，并令则该问题的数学模型为：该模型的目标函数可变化为其中。然后采用匈牙利法求解。因此相应的解矩阵为：2、 分配甲