运筹学习题集.doc

.例：将下面的线性规划化为标准型无非负限制解1.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下：班次时间所需人数16点到10点60210点到14点70314点到18点60418点到22点50522点到2点2062点到6点30设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。解：设（k=1，2，3，4，5，6）为个司机和乘务人员第k班次开始上班。建立模型：Min z=+s.t. +60+70+60+50+20+30,01.10某糖果公司厂用原料A、B、C加工成三种不同牌号的糖果甲乙丙，已知各种糖果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如表所示：原料甲乙丙原料成本（元/千克）每月限制用量（千克）A60%15%22000B1.52500C20%60%50%11200加工费0.50.40.3售价3.42.852.25问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模型。解:解：设，是甲糖果中的A，B，C成分，是乙糖果的A，B，C成分，是丙糖果的A，B，C成分。线性规划模型：Max z=0.9+1.4+1.9+0.45+0.95+1.45-0.05+0.45+0.95s.t. -0.4+0.6+0.60 -0.2-0.2+0.80 -0.85+0.15+0.150 -0.6-0.6+0.40 -0.7-0.5+0.50+2000+2500+1200,01.11某厂生产三种产品I、III。每种产品经过AB两道加工程序，该厂有两种设备能完成A工序，他们以,表示；有三种设备完成B工序，分别为，；产品I可以在AB任何一种设备上加工，产品可以在任何规格的A设备上加工，但完成B工序时，只能在设备上加工；产品III只能在，上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化。设备产品设备有效台时满负荷时的设备费用IIIIII5106000300791210000321684000250411700078374000200原料费0.250.350.5单价1.252.002.8解：产品1，设,完成A工序的产品，件；B工序时，,，完成B工序的，件，产品，设,完成A工序的产品，件；B工序时，完成B的产品为件；产品111，完成A工序的件，完成B工序的件；+=+ = 建立数学模型：Max z=(1.25-0.25)*(+)+(2-0.35)*(+ )+(2.8-0.5) -(5+10)300/6000-(7+9 +12 )321/10000-(6+8 )250/4000-(4+11 )783/7000-7*200/4000s.t 5+1060007+9 +12 100006+8 40004+11 700074000+=+ = ,0用单纯形法求解线性规划极大化MAX解引入松弛变量，得到原规划的标准型极大化单纯形表为所以，最优解为最优解值为21.解：最优解例：设线性规划求：1.最优解; 2.确定的范围,使最优解不变; 取,求最优解; 3.确定的范围,使最优基不变, 取求最优解; 4.引入求最优解;解 1.由单纯形方法得即,原问题的最优解为例求下面运输问题的最小值解：12341311310721923437410593656解：由最小元素法得到初始解：v1=2v2=9v3=3v4=101934u1=01311310743u2=-121923431u3=-53741059633656则：，最小值为-6，非基变量为，闭回路，最大调整量为1，得新解：，重新计算位势及影响系数，得下表：v1=8v2=9v3=3v4=101234u1=01311310752u2=-721923431u3=-53741059633656，最小值为-5，非基变量为，闭回路，最大调整为2，得新解：重新计算位势及影响系数，得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=03741059633656，此时，故当前解为最优解。最优解值为：。3.2表3-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔法直接给出近似最优解。表3-3销地产地123产量15181222411433674销量91011表3-4销地产地12345产量11023159252520152430315514715204201513M830销量2020301025解：（1）在表3-3中分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。得到：销地产地123行差额151842241133673列差额136从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，上表中，第三列是最大差额列，此列中最小元素为1，由此可以确定产地2的产品应先供应给销售地3，得到下表：销地产地123产量1111221434销量91011同时将运价表第三列数字划去，得销地产地12产量15112224143364销量910对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列，重复上面的步骤，直到求出初始解，最终结果是：销地产地123产量121012231114344销量91011（2）3-4分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素。（方法同3-3相同）最终得出原问题的初始解：销地产地12345产量12522030320430销量20203010253.3用表上作业法求给出运输问题的最优解（M是任意大正数）（1）销地产地甲乙丙丁产量137645224322343853销量3322解：（1）计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，丙列中的最小元素为3，由此可以确定产地2的产品应先供应丙的需要，而产地2的产量等于丙地的销量，故在（2，丙）处填入0，同时将运价表中的丙列和第二行的数字划去，得到：销地产地甲乙丙丁产量137452234353销量332对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤，直到求出初始解为止。得到下表：销地产地甲乙丙丁产量132522023033销量3322使用位势法进行检验：上表中，数字格处填入单位运价并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令+=（i，jB，B为基，下同）来确定和，得到下表：销地产地甲乙丙丁1340232-234313254由=-（+）（i，j为非基，下同）计算所有空格的检验数，并在每个格的右上角填入单位运价，得到下表销地产地甲乙丙21443020-234030825013254由上表可以看出，所有的非基变量检验数0，此问题达到最优解。又因为=0，此问题有无穷多最优解。总运费min z=3*3+3*3+2*3+2*4=32（2）销地产地甲乙丙丁产量110671242161059935410104销量5246解：（2）计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，甲列是最大差额列，甲列的最小元素是5，所以产地3的产品先供应甲的需求，同时将运价表中产地3所在行的数字划去。对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤，直到求出初始解为止。得到下表：销地产地甲乙丙丁产量112142369344销量5246使用位势法进行检验：上表中，数字格处填入单位运价，并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由+=（i，jB，B为基，下同）来确定和.由=-（+）（i，jN）计算所有空格的检验数，并在每个格的右上角填入单位运价，得到下表销地产地甲乙丙丁11006712102 1681065090-235043108104-5106711由上表可以看出，所有的非基变量检验数0，此问题达到最优解。此问题有唯一最优解。总运费min z=118（3）销地产地甲乙丙丁戊产量11020591052210830663120710424863759销量44624解：（3）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为2。这样就达到了产销平衡。用伏格尔法求初始解：计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，产地1所在的行是最大差额行，最小元素0，说以一产地的产品应该优先供应己的需要，同时划掉己列的数字。对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤，直到求出初始解为止。得到下表：销地产地甲乙丙丁戊己产量1325242632244329销量446242使用位势法进行检验：上表中，数字格处填入单位运价，并增加一行一列，在列中填入（i=1，2，3，4），在行中填入（j=1，2，3，4，5，6），先令=0，由+=（i，jB，B为基，下同）来确定和.由=-（+）（i，jN）计算所有空格的检验数，并在每个格的右上角填入单位运价。由上表可以看出，所有的非基变量检验数0，此问题达到最优解。又因为=0，此问题有无穷多最优解。总运费min z=90（4）销地产地甲乙丙丁戊产量1 1018291322100213M211416120306113M1404911231819805242836303460销量1001201006080解：（4）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为40。这样就达到了产销平衡。用伏格尔法求初始解：计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下行。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，同时划掉所在列或行的元素。对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤，直到求出初始解为止。并用位势法进行检验：销地产地甲乙丙丁戊己1 1018229813022601202133MM-1621014116001203006011030MM-6022-104941102371810198017-552422803633053460121016211316-12由上表可以看出，所有的非基变量检验数0，此问题达到最优解。又因为=0，此问题有无穷多最优解。总运费min z=5520有四个工人，指派他们完成4种工作，每人做各种工作所消耗的时间如下表，问指派哪个人去完成哪种工作，可以使得总耗时最小？任务人员ABCD甲15182124乙19232218丙26171619丁19212317解：系数矩阵C为： 系数矩阵的每行元素减去该行的最小元素得矩阵B B矩阵的每列元素减去该列的最小元素得到矩阵A此时，细数矩阵的每行每列都有元素0.先给加圈，然后给加圈，划掉。给加圈，划掉得：此时，画圈的数目是3,少于4个，所以指派不成功，进入下一步，给第四行打号，给第四列打号，给第二行打号，将第一，第三行画一横线，将第四列画纵线，变换矩阵得到给第一，第四列打号，对第一，第二，第四行打号，给第一，第四列画一纵线，第三行画一横线，变换矩阵得到甲乙丙丁得到最优指派方案为：甲B；乙A; 丙C；丁D。所消耗的总时间是70.2. 现要在5个工人中确定4个人来分别完成四项工作中的一项工作。由于每个工人的技术特长不同，他们完成各项工作所需的工时也不同。每个工人完成每项工作所需工时如表51所示。表51工作所需工时工人943746565475752310674试找出一个工作分配方案，使总工时最少。解题分析：本题属“不平衡”指派问题，故应先虚拟一项工作，使其平衡，再按常规求解即可。解题过程：虚拟一项工作E，设每人完成E所需时间都是“0”，从而转化为五个人完成五项工作的分配问题，再用匈牙利法求解。最优解为：C，A，B，D，E，即应安排工人、分别完成工作C、A、B、D，此时所用时间最少，为3+4+4+3=14。1、用标号法求下图所示的最大流问题，弧上数字为容量和初始可行流量。解：最大流f*=152.试找出AF间的最短路线及距离。19B1245534168E19435FC2AB2265E274145247D1C1D3C3D2B3解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：144519B131245541490168E15943FC2AB2117265E2741425247D1C1D3C3D2B31287最佳策略为：AB2C1D1E2F此时的最短距离为5+4+1+2+2=14v5v283.221732v7v4v174431v6v3求v1到v7的最短路径和最短距离。解：此为网络分析之“最短路问题”，可用顺向追踪“TP标号法”解决如下：94v2v5852217732v7v4v1744310v6v314v1到v7的最短路径是：v1v3v4v7，最短距离为1+4+2=7。v3v14、求下图所示网络的最大流：（4，0）（5，0）（3，0）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2图中为（Cij，fij）解：此为网络分析之“寻求网络最大流问题”，可用“寻求网络最大流的标号法（福特富克尔逊算法）”解决如下：标号过程：1、给vs标上（0，）；2、检查vs，在弧（vs，v1）上，fs1=0，Cs1=3，fs1Cs1，给v1标号(s，(v1)，其中，（s，3）v1v3（4，0）（5，0）（3，0）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（s，5）同理，给v2标号(s，(v2)，其中，3、检查v1，在弧（v1，v3）上，f13=0，C13=4，f13C13，给v3标号(1，(v3)，其中，（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（2，2）（s，5）检查v2，同理，给v4标号(2，(v4)，其中，4、检查v4，在弧（v4，vt）上，f4t=0，C4t=2，f13C13，给vt标号(4，(vt)，其中，vt得到标号，标号过程结束。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（4，2）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（2，2）（s，5）调整过程：从vt开始逆向追踪，找到增广链。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（2，2）（s，）（3，0）（1，0）（1，0）vtvs（2，0）（5，0）（2，0）v4v2（2，2）（s，5）（vs，v2，v4，vt），=2，在上进行流量=2的调整，得可行流f 如图所示：（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（1，0）（4，2）（s，）（3，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（2，2）（s，5）去掉各点标号，从vs开始，重新标号。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（3，3）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（t，2）（s，3）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。（1，3）（s，3）v1v3（4，0）（5，0）（3，0）（3，3）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（t，2）（s，3）（vs，v1，v3，vt），=3，在上进行流量=3的调整，得可行流f 如图所示：（1，3）（s，3）v1v3（4，3）（5，3）（3，3）（3，3）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（t，2）（s，3）去掉各点标号，从vs开始，重新标号。（1，1）（2，1）v1v3（4，3）（5，3）（3，3）（3，1）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（s，3）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。（1，1）（2，1）v1v3（4，3）（5，3）（3，3）（3，1）（s，）（3，0）（1，0）（1，0）vtvs（2，2）（5，2）（2，2）v4v2（s，3）（vs，v2，v1，v3，vt），=1，在上进行流量=1的调整，得可行流f 如图所示：（1，1）（2，1）v1v3（4，4）（5，4）（3，3）（3，1）（s，）（3，0）（1，0）（1，1）vtvs（2，2）（5，3）（2，2）v4v2（s，3）去掉各点标号，从vs开始，重新标号。v1v3（4，4）（5，4）（3，3）（s，）（3，0）（1，0）（1，1）vtvs（2，2）（5，3）（2，2）v4v2（s，2）标号至点v2：标号过程无法进行，所以f 即为最大流。v1v3（4，4）（5，4）（3，3）（s，）（3，0）（1，0）（1，1）vtvs（2，2）（5，3）（2，2）v4v2（s，2）=vs，v2，=v1，v3，v4，vt截集（，）=（vs，v1），（v2，v1），（v2，v4）V（ f ）=C（，）=3+1+2=6v3v16、求下图所示网络的最大流：（9，5）（5，5）（8，6）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（9，7）v4v2图中为（Cij，fij）解：此为网络分析之“寻求网络最大流问题”，可用“寻求网络最大流的标号法（福特富克尔逊算法）”解决如下：标号过程：1、给vs标上（0，）；2、检查vs，在弧（vs，v1）上，fs1=6，Cs1=8，fs1Cs1，给v1标号(s，(v1)，其中，v3v1（s，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（s，3）（9，7）v4v2同理，给v2标号(s，(v2)，其中，3、检查v1，在弧（v1，v3）上，f13=5，C13=9，f13C13，给v3标号(1，(v3)，其中，v3v1（1，2）（s，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（2，2）（s，3）（9，7）v4v2检查v2，同理，给v4标号(2，(v4)，其中，4、检查v3，在弧（v3，vt）上，f3t=C3t=5，不满足标号条件，v3v1（1，2）（s，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（2，2）（s，3）（9，7）v4v2检查v4，在弧（v4，vt）上，f4t=5，C4t=10，f13C13，给vt标号(4，(vt)，其中，vt得到标号，标号过程结束。调整过程：从vt开始逆向追踪，找到增广链。（s，2）v1v3（1，2）（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，5）（7，4）（9，7）v4v2（2，2）（s，3）（vs，v2，v4，vt），=2，在上进行流量=2的调整，得可行流f 如图所示：（1，2）（s，2）v3v1（9，5）（5，5）（8，6）（0，）（6，2）（2，2）（5，1）vtvs（10，7）（7，6）v4v2（9，9）（2，2）（s，3）去掉各点标号，从vs开始，重新标号。（1，2）（s，2）v3v1（9，5）（5，5）（8，6）（4，2）（0，）（6，2）（2，2）（5，1）vtvs（10，7）（7，6）v4v2（9，9）（3，2）（s，1）vt又得到标号，标号过程结束。再次从vt开始逆向追踪，找到增广链。（1，2）（s，2）v3v1（9，5）（5，5）（8，6）（4，2）（0，）（6，2）（2，2）（5，1）vtvs（10，7）（7，6）v4v2（9，9）（3，2）（s，1）（vs，v1，v3，v4，vt），=2，在上进行流量=2的调整，得可行流f 如图所示：（1，2）（s，2）v3v1（9，7）（5，5）（8，8）（4，2）（0，）（6，0）（2，2）（5，1）vtvs（10，9）（7，6）v4v2（9，9）（3，2）（s，1）去掉各点标号，从vs开始，重新标号。（1，1）（2，1）v3v1（9，7）（5，5）（8，8）（0，）（6，0）（2，2）（5，1）vtvs（10，9）（7，6）v4v2（9，9）（s，1）标号至点v3：标号过程无法进行，所以f 即为最大流。v1v3（2，1）（1，1）（9，7）（5，5）（8，8）（0，）（6，0）（2，2）（5，1）vtvs（10，9）（7，6）（9，9）v4v2（s，1）=vs，v2，v1，v3，=v4，vt截集（，）=（v2，v4），（v3，vt）V（ f ）=C（，）=9+5=143、公司拟建一预制构件厂，一个方案是建大厂，需投资300万元，建成后如销路好每年可获利100万元，如销路差，每年要亏损20万元，该方案的使用期均为10年；另一个方案是建小厂，需投资170万元，建成后如销路好，每年可获利40万元，如销路差每年可获利30万元；若建小厂，则考虑在销路好的情况下三年以后再扩建，扩建投资130万元，可使用七年，每年盈利85万元。假设前3年销路好的概率是0.7，销路差的概率是0.3，后7年的销路情况完全取决于前3年；试用决策树法选择方案。解：这个问题可以分前3年和后7年两期考虑，属于多级决策类型，如图所示。403销路好0.7P=1P=1后7年前3年建大厂(300)100103010建小厂（170）销路好0.7销路差0.31-2010扩建(130)不扩建8574072销路差0.334决策树图示考虑资金的时间价值，各点益损期望值计算如下：点：净收益100(P/A，10，10)0.7+(-20)（P/A，10，10）0.3-300=93.35(万元)点：净收益85(P/A，10，7)1.0-130=283.84(万元)点：净收益40(P/A，10，7)1.0=194.74(万元)可知决策点的决策结果为扩建，决策点的期望值为283.84+194.7447