运筹学作业王程信管1302130404026目录运筹学作业1第一章 线性规划及单纯形法3第二章 线性规划的对偶理论与灵敏度分析24第三章 运输问题53第四章 目标规划63第五章 整数规划72第六章 非线性规划84第七章 动态规划93第八章 图与网络分析96第九章 网络计划98第一章 线性规划及单纯形法1.1分别用图解法和单纯形法求下列线性规划问题，指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解；当具有限最优解时，指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。 解：图解法： 当经过点时，最小，且有无穷多个最优解。 图解法： 该问题无可行解。 图解法： 当经过点时，取得唯一最优解。 单纯形法： 在上述问题的约束条件中分别加入松弛变量， 化为标准型： 由线性规划问题的标准型可列出单纯初始形表逐步迭代，计算结果如下表所示： 图解法： 当经过点时，取得唯一最优解。1.2将下述线性规划问题化成标准形式。 1.3 对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。解：（1）该线性规划问题的全部基解见下表中的，打者为基可行解，注*者为最优解，z* =36。（2）该线性规划问题的标准形式为： 其全部基解见下表中的，打者为基可行解，注*者为最优解，z*=5。 1.4 题1.1（3）中，若目标函数变为，讨论的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。解：由目标函数可得： ，其中 。当 时，可行域的顶点A使目标函数达到最优；当 时，可行域的顶点B使目标函数达到最优；当 时，可行域的顶点C使目标函数达到最优；当或时，最优解为O点 。 1.6 分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解。 其中M是一个任意大的正数，据此可列出初始单纯形表如下： cj23100MMiCBXBbx1x2x3x4x5x6x7MMx6x786134220-100-1100123cj-zj2-4M3-6M1-2MMM003Mx2x7221/45/2101/2-1-1/41/20-11/4-1/20184/5cj-zj32x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5cj-zj0001/21/2M-1/2M-1/2由单纯形表的计算结果得：最优解 ,目标函数最优值 X存在非基变量检验数，故该线性规划问题有无穷多最优解。 据此可列出单纯初始形表如下：cj0000011iCBXBbx1x2x3x4x5x6x711x6x786134220-100-1100123cj-zj-4-6-2110001x2x7221/45/2101/2-1-1/41/20-11/4-1/20184/5cj-zj00x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5cj-zj0000011第一阶段求得的最优解，目标函数的最优值，因人工变量，所以是原线性规划问题的基可行解。于是可以进行第二阶段计算，将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，如下表：cj23100iCBXBbx1x2x3x4x532x2x19/54/501103/5-2/5-3/101/51/10-2/5 cj-zj0001/21/2由表中计算可知，原线性规划问题的最优解，目标函数的最优值，由于存在非基变量检验数，故该线性规划问题有无穷多最优解。 其中M是一个任意大的正数，据此可列出单纯形表如下：cj101512000-MiCBXBbx1x2x3x4x5x6x700-Mx4x5x791555-52361115110001000-10019/5-5/2cj-zj10+2M15+M12+M00-M0100-Mx1x5x79/5247/51003/59-1/51/5163/51/51-2/501000-100193/27/3cj-zj1012-Mx1x3x73/23/21/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001cj-zj0 由单纯性表的最终表可以看出，所有非基变量检验数 ，且存在人工变量 ，故原线性规划问题无可行解。据此可列出单纯初始形表如下：cj0000001iCBXBbx1x2x3x4x5x6x7001x4x5x791555-52361115110001000-10019/5-5/2cj-zj-2-1-100101001x1x5x79/5247/51003/59-1/51/5163/51/51-2/501000-100193/27/3cj-zj-1/53/5-2/51001x1x3x73/23/21/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001cj-zj0 7/163/801 第一阶段求得最优解，因人工变量 ，且非基变量检验数，所以原线性规划问题无可行解。1.5 考虑下述线性规划问题： 解：（1）上界对应的模型如下（c，b取大，a取小） 最优值（上界）为：21；（2）下界对应的模型如下（c，b取小，a取大） 最优值（下界）为：6.4。1.7 已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到表1-21，试求括弧中未知数的值。 1.8 若X,X(2)均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。 1.9 考虑线性规划问题 模型中为参数，要求： 组成两个新的约束，根据式和式，以为基变量，列出初始单纯形表；解： 在表中，假定 ，则 为何值时，为问题的最优基； 在表中，假定 ，则 为何值时，为问题的最优基。 1.10 试述线性规划模型中“线性”二字的含义，并用实例说明什么情况下线性的假设将被违背。答：线性的含义：一是严格的比例性，如生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例；二是可叠加性，如生产多种产品时，可获取的总利润使各项产品的利润之和，对某项资源的消耗量应等于各产品对该资源的消耗量之和；三是可分性，即模型中的变量可以取值为小数、分数或某一实数；四是确定性，指模型中的参数cj,aij,bi 均为确定的常数。 很多实际问题往往不符合上述条件，例如每件产品售价3元，但成批购买就可以得到折扣优惠。1.11 判断下列说法是否正确，为什么？ 含n个变量m个约束的标准型的线性规划问题，基解数恰好为个； 答：错误。基本解的个数=基的个数 线性规划问题的可行解如为最优解，则该可行解一定为基可行解； 答：错误。当有唯一最优解时，最优解是可行域顶点，对应基本可行解；当有无穷多最优解时，除了其中的可行域顶点对应基本可行解外，其余最优解不是基本可行解。 如线性规划问题存在可行域，则可行域一定包含坐标的原点； 答：错误。如果约束条件中有一个约束所对应的区域不包含坐标的原点，则即使有可行域，也不包含坐标的原点。 单纯形法迭代计算中，必须选取同最大检验数对应的变量作为换入基的变量。答：错误。若此时最大检验数，可是 ，则问题是无界解，计算结束。1.12 线性规划问题,如是该问题的最优解，又为某一常数，分别讨论下列情况时最优解的变化。 目标函数变为； 目标函数变为； 目标函数变为，约束条件变为 。解： 最优解不变； C为常数时最优解不变，否则可能发生变化； 最优解变为：X/。1.13 某饲养场饲养动物出售，设每头动物每天至少需要700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如表1-22所示。要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。 最优解为 1.14 辽源街邮局从周一到周日每天所需的职员人数如下表1-23所示。职员分别安排在周内某一天开始上班，并连续工作5天，休息2天。要求确定： 该邮局至少应配备多少职员，才能满足值班需要； 因从周一开始上班的，双休日都能休息；周二或周日开始上班的，双休日内只能有一天得