运筹学讲解习题

1、1对于常数项发生变化时：将改变量乘以，其中为原线性规划问题所引入变量在最终单纯型表中的系数组成的矩阵，若，最优解无变化，否则，利用对偶单纯型法进行基变换求最优解；2对于决策变量xi的价值系数发生变化，i）若xi为非基变量，则只检验xi检验数若最优解无变化，否则，利用单纯型法进行基变换求最优解；ii）若xi为基变量，则要检验每一个非基变量xj检验数若最优解无变化，否则，利用单纯型法进行基变换求最优解；同时将基变量的价值系数变为；3对于决策变量xi的系数发生变化，i）若xi为非基变量，则只检验xi检验数若最优解无变化，否则，将xi的系数变为利用单纯型法进行基变换求最优解；ii）若xi为基变量，将x

2、i的系数变为，同时化为单位向量。并检验，若最优解无变化， 否则，利用单纯型法进行基变换求最优解；4对于增加一个约束条件：将约束条件化为等式，要求含有单位基决策变量，放入原线性规划问题最终单纯型表中最后一行，并将基变量的系数化为零。若最优解无变化，否则，利用对偶单纯型法进行基变换求最优解；1现有线性规划问题 求出该问题的最优解，然后分别分析在下列各条件中，最优解有什么变化？（1）第一个约束条件的常数有20变为30；（2）目标函数中x3的价值系数有13变为8；（3）x1系数列向量由(-1, 12) 变为(0, 5);（4）增加一个约束条件；2写出下列线性规划的对偶规划模型3. 喜庆食品公司有三个生

3、产面包的分厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？ 销地产地B1B2B3B4产量A13113107A219284A3741059销量365620204高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300

4、人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。5某公司生产并销售三种产品A，B，C，再组装时要经过同一条组装线，三种产品装配时间分别为 30h，40h 和 50h。 组装线每个月工作时间为600h. 这三种产品的销售利润分别为：25千元/台，32.5千元/台和40千元/台。每月销售预计为 A 8台，B 6台，C 4台。该公司决策者有如下考虑：首先，争取利润指标为每月90千元；第二，要充分利用生产能力，不使组装线空闲；第三，如果加班，那么加班时间不得超过2

5、4h;第四，努力按销量来完成生产数量。试建立生产计划的数学模型，并列出相应的单纯型表。6某集团公司要向国外派出若干项目的考察组，现有候选的考察组6个，记为 Aj （j=1,6），各组人数为 nj, 考察工作所需费用为cj，预期创造的成果折成标准分数为rj。由于总人数要限制在 N，总费用限制在C内，所以只能派其中的若干考察组。要求各考察组不能拆散，同时有下列限制：（1）A1与A4 至多派1组。（2）A2与A6 至少派1组。（3）A3与A5 要么同时派出，要么都不派出。试建立满足上述条件，并使考察成果的预期总标准分最高的数学模型。解：这是一个整数规划的问题。设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi = 1(当生产第 i种容器, 即 xi 0 时) 或0（当不生产第 i种容器即 xi = 0 时）。引入约束xi M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。 这样我们可建立如下的数学模型：max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3