(运筹学习题集.doc

第一章 线性规划习题 将下列线性规划问题变换成标准型，并列出初始单纯形表。 1) minZ＝－3x1＋4x2－2x3＋5x4 s.t. 2) maxS＝zx／pk s.t. 分别用单纯法中的大M法和两阶段法求解下述线性规划问题： minZ＝2x1＋3x2＋x3 s.t. 并指出该问题的解属哪一类解。 【表1-6】是某求极大化线性规划问题计算得到单纯形表。表中无人工变量，a1, a2, a3, d, c1, c2为待定常数。试说明这些常数分别取何值时，以下结论成立。 表中解为唯一最优解； 表中解为最优解，但存在无穷多最优解； 该线性规划问题具有无界解； 表中解非最优，为对解进行改进，换入变量为x1，换出变量为x6。 表1-6 基 b x1 x2 x3 x4 x5 x6 x3 x4 x6 d 2 3 4 －1 a3 a1 －3 －5 1 0 0 0 1 0 a2 －1 －4 0 0 1 c1 c2 0 0 －3 0 某饲料厂用原料A、B、C加工成三种不同牌号的饲料甲、乙、丙。已知各种牌号饲料中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号的饲料的单位加工费及售价如【表1-7】所示。 表1-7 甲 乙 丙 原料成本 （元/千克） 每月限制用量（千克） A B C ≥60% ≤20% ≥15% ≤60% ≤50% 2.00 1.50 1.00 2000 2500 1200 加工费 （元/千克） 0.50 0.40 0.30 售价 3.40 2.85 2.25 问该厂每月应生产这三种牌号饲料各多少千克，使该厂获利最大？试建立这个问题的的线性规划的数学模型。 考虑下列问题 建立此问题的对偶问题，然后以观察法求出其最优解。 使用主对偶原理及对偶问题的最优解求出原问题的最优解目标函数值。 假设原问题中x1的系数为c1（c1可为任意实数）。当c1为何值时，此对偶问题无可行解？对这些值而言，原问题的解有什么意义？ 求下列问题的对偶问题 1) 2) 某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下： 表1-8 产品 项目 A B C D 单位产值 (元) 168 140 1050 406 单位成本 (元) 42 28 350 140 单位纺纱用时 (h) 3 2 10 4 单位织带用时 (h) 0 0 2 0.5 工厂有供纺纱的总工时7200h，织带的总工时1200h。 列出线性规划模型，以便确定产品的数量使总利润最大； 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？ 将下列线性规划化为极大化的标准形式 用单纯形法解下面的线性规划 用两阶段法解下面问题： 用大M法解下面问题，并讨论问题的解 写出下列线性规划问题的对偶问题 1) 2) 写出下问题的对偶问题，解对偶问题，并证明原问题无可行解 用对偶单纯形法求下面问题 下表是一线性规划最优解的单纯形表 Cj ? 21 9 4 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 21 x1 4 1 0 1/3 2/3 0 1/3 0 x5 2 0 0 ?2/3 ?4/3 1 1/3 9 x2 23 0 1 1/3 ?1/3 0 ?2/3 zj 21 9 10 11 0 1 cj ? zj 0 0 ?6 ?11 0 ?1 原问题为max型，x4，x5为松驰变量，x6为剩余变量，回答下列问题： 资源1、2、3的边际值各是多少？(x4，x5是资源1、2的松驰变量，x6是资源3的剩余变量) 求C1, C2 和C3的灵敏度范围； 求?b1，?b2的灵敏度范围。 第二章 动态规划习题 用动态规划求解下题动态规划 一个设备由三个元件串联，其可靠性可由每种元件上装得并联得备用元件来改进。设总投资为10，对第i中（i＝1, 2, 3）元件配个并联单件（＝1, 2, 3）后得可靠性与成本的数据如【表2-1】所示，求在投资范围内得总可靠性达到最高。 表2-1 资源分配问题 某工厂共有5单位的资源供给3个车间，由于各车间的设备条件不同，使用资源获得的收益的情况也不同，具体数据如【表2-2】所示，为使工厂获得收益最大，每个车间应分配的资源数为多少？ 表2-2 设某厂生产A、B两种产品，由于条件限制，这两种产品日产量分别为x1和x2，日生产成本为；，两产品的销售单价分别为10元和5元，工时消耗定额均为1小时每件，若每天工作不超过8小时，求产品A、B每天各应生产多少小时才能使总利润最大？ 用动态规划求解 带回收得资源分配问题 某厂新购某种