第一章 线性规划习题1. 将下列线性规划问题变换成标准型，并列出初始单纯形表。

1) min Z ＝－3x 1＋4x 2－2x 3＋5x 4s.t.⎪⎪⎩⎪⎪⎨⎧≥≥+-+-≤-++-=-+-.,0,,22321432244321432143214321无约束x x x x x x x x x x x x x x x x 2) max S ＝z x ／p ks.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧==≥=-=-=∑∑∑===).,...,2,1;,...,2,1(0),,...,2,1(1,111m k n i x n i x x a z ik mk ik n i mk ik ik k 2. 分别用单纯法中的大M 法和两阶段法求解下述线性规划问题：min Z ＝2x 1＋3x 2＋x 3s.t.⎪⎩⎪⎨⎧≥≥+≥++.0,,,623,82432121321x x x x x x x x 并指出该问题的解属哪一类解。

3. 【表1-6】是某求极大化线性规划问题计算得到单纯形表。

表中无人工变量，a 1, a 2, a 3, d , c 1, c 2为待定常数。

试说明这些常数分别取何值时，以下结论成立。

1) 表中解为唯一最优解；2) 表中解为最优解，但存在无穷多最优解； 3) 该线性规划问题具有无界解；4) 表中解非最优，为对解进行改进，换入变量为x 1，换出变量为x 6。

表1-64. 某饲料厂用原料A 、B 、C 加工成三种不同牌号的饲料甲、乙、丙。

已知各种牌号饲料中A 、B 、C 含量，原料成本，各种原料的每月限制用量，三种牌号的饲料的单位加工费及售价如【表1-7】所示。

表1-7问该厂每月应生产这三种牌号饲料各多少千克，使该厂获利最大？试建立这个问题的的线性规划的数学模型。

5. 考虑下列问题⎩⎨⎧≥≥≤-+=0,01.42)(max 212121x x x x tS x x x f 1) 建立此问题的对偶问题，然后以观察法求出其最优解。

2) 使用主对偶原理及对偶问题的最优解求出原问题的最优解目标函数值。

3) 假设原问题中x 1的系数为c 1（c 1可为任意实数）。

当c 1为何值时，此对偶问题无可行解？对这些值而言，原问题的解有什么意义？ 6. 求下列问题的对偶问题 1)⎪⎩⎪⎨⎧≥≥≥=++-≥-++=0,0,07531263063.352)(max 32132121321x x x x x x x x t S x x x x f 2) ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥=+++≤+≥+-≤+++≥++++-+-=无限制1432432121421432143214321,0,,20222021040231023.342)(min x x x x x x x x x x x x x x x x x x x x x t S x x x x x f 7. 某织带厂生产A 、B 两种纱线和C 、D 两种纱带，纱带由专门纱线加工而成。

这四种产品的产值、成本、加工工时等资料列表如下：表1-8工厂有供纺纱的总工时7200h ，织带的总工时1200h 。

1) 列出线性规划模型，以便确定产品的数量使总利润最大；2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？ 8. 将下列线性规划化为极大化的标准形式⎪⎪⎩⎪⎪⎨⎧±≥≤+-=-+--≥-+++=不限321321321321321 ,0,13|5719|169765 ..532)(min x x x x x x x x x x x x t s x x x x f 9. 用单纯形法解下面的线性规划⎪⎪⎩⎪⎪⎨⎧≥≤++-≤++-≤-+++= ,0,,4205.021253661023 ..352)(max 321321321321321x x x x x x x x x x x x t s x x x x f 10. 用两阶段法解下面问题：⎪⎩⎪⎨⎧≥≥+≥++=0,753802 ..64)(min 21212121x x x x x x t s x x x f11. 用大M 法解下面问题，并讨论问题的解⎪⎪⎩⎪⎪⎨⎧≥≥++≤++-≤++++= ,0,,52151565935 ..121510)(max 321321321321321x x x x x x x x x x x x t s x x x x f12. 写出下列线性规划问题的对偶问题 1)⎪⎪⎩⎪⎪⎨⎧±≥≤=++≤+≥+-+-+=不限4321432314321321 ,0,,06 4 2 5..532)(max x x x x x x x x x x x x x t s x x x x f 2)⎪⎪⎩⎪⎪⎨⎧±≥≤=++≤+≥+-+-+=不限4321432314321321 ,0,,06 4 2 5..532)(max x x x x x x x x x x x x x t s x x x x f13. 写出下问题的对偶问题，解对偶问题，并证明原问题无可行解⎪⎪⎩⎪⎪⎨⎧≥≤+--≤-≤+--=,0, 121 1 ..34)(max 212122121x x x x x x x t s x x x f14. 用对偶单纯形法求下面问题⎪⎩⎪⎨⎧≥≥+≥++=0,753802 ..64)(min 21212121x x x x x x t s x x x f15. 下表是一线性规划最优解的单纯形表原问题为max 型，x 4，x 5为松驰变量，x 6为剩余变量，回答下列问题： 1) 资源1、2、3的边际值各是多少？(x 4，x 5是资源1、2的松驰变量，x 6是资源3的剩余变量) 2) 求C 1, C 2 和C 3的灵敏度范围； 3) 求∆b 1，∆b 2的灵敏度范围。

第二章 动态规划习题1. 用动态规划求解下题动态规划⎪⎩⎪⎨⎧≥≤≤++=0,4604302..52)(max 2122121x x x x x t S x x x f 2. 一个设备由三个元件串联，其可靠性可由每种元件上装得并联得备用元件来改进。

设总投资为10，对第i 中（i ＝1, 2, 3）元件配i x 个并联单件（i x ＝1, 2, 3）后得可靠性i x i R ,与成本i x i C ,的数据如【表2-1】所示，求在投资范围内得总可靠性达到最高。

表2-13. 资源分配问题某工厂共有5单位的资源供给3个车间，由于各车间的设备条件不同，使用资源获得的收益的情况也不同，具体数据如【表2-2】所示，为使工厂获得收益最大，每个车间应分配的资源数为多少？表2-24. 设某厂生产A 、B 两种产品，由于条件限制，这两种产品日产量分别为x 1和x 2，日生产成本为211113)(x x x C +=；2222224)(x x x C +=，两产品的销售单价分别为10元和5元，工时消耗定额均为1小时每件，若每天工作不超过8小时，求产品A 、B 每天各应生产多少小时才能使总利润最大？ 5. 用动态规划求解⎩⎨⎧=≥≤++=)3,2,1(06.)(max 32133221k x x x x tS x x x x f k 6. 带回收得资源分配问题某厂新购某种新机床125台。

据估计，该设备5年后将被其他心设备所代替，此机床如在高负荷下工作，年损坏率为1/2，年利润为10万元，如在低负荷下工作，年损坏率为1/5，年利润为6万元。

问应如何安排这些机床的生产，才能使5年内获得的利润最大？ 7. 用动态规划求解下面非线性规划问题2.)(max 221221≤+=x x tS x x x f8. 某公司将在一个竞争激烈的市场推出一种新产品。

该公司已经决定分三个阶段进行营销策略。

第一阶段以低价向大家推销，以吸引初买者；第二阶段大举从事广告，以促使初买者以正常价格购买该产品，约于第二阶段末期另一公司将推出一种竞争性新产品，故在第三阶段从事加强性广告策略，以使购买者不转而购买竞争对手的产品。

该公司已经拨出四百万元的预算用于此项活动。

现求如何在这三个阶段分配款项使该产品获得最大的市场占有率。

令m 表示第一阶段达成的最初市场占有率，f 2、f 3分别为第二、三阶段策略对市场占有率的影响，也即求得m f 2f 3最大。

1) 假定该款项以一百万元的整数倍用于每一阶段，【表2-3】表示各阶段的支出效果。

表2-32) 假定在四百万元预算额度内各阶段支出额可以为任意实数，而在阶段k (k ＝1, 2, 3)支出x k 百万元的支出效果为：332221107.06.01.04.010x f x f x x m +=+=-=9. 用动态规划求解下面极大值问题。

⎩⎨⎧=≥=++=)3,2,1(0432.)(max 3213221i x x x x tS x x x x f i10. 用动态规划求解下面非线性规划问题。

⎩⎨⎧≥≤+--++=0,3.3693636)(max 212132312121x x x x tS x x x x x x f11. 某厂生产一种产品，以后四个月的订单如【表2-4】所示。

合同规定在月底前缴获，生产每批产品的固定成本为3千元，每批生长的产品件数不限。

每件产品的可变成本为1千元，每批产品的最大生产能力是5件。

产品每级每月的存储费为0.5千元。

设1约初又库存产品1件，4月底不再留下产品。

试求在满足需求的前提下，如何组织生产才能使总的成本费用最低。

12. 某公司有9个推销员在全国三个不同市场里推销货物，这三个市场里推销员人数与收益的关系如下表，做出各市场推销人员数的分配方案，使总收益最大。

13. 设某工厂要在一台机器上生产两种产品，机器的总运转时间为5小时。

生产这两种产品的任何一件都需占用机器一小时。

设两种产品的售价与产品产量成线性关系，分别为(12-x 1)和(13-2x 2)。

这里x 1和x 2分别为两种产品的产量。

假设两种产品的生产费用分别是4x 1和3x 2，问如何安排两种产品的生产量使该机器在5小时内获利最大。

(要求用连续变量的动态规划方法求解)第三章 匹配问题 判断题1. 任务分配问题效率矩阵的每一个元素都乘上同一个常数k ，将不影响最优分配方案。

( ) 2. 任务分配问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。

( )练习题1. 用匈牙利算法求解下述任务分配问题。

1) ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡161512111514161517161213121097 2) ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡10961095324857246792783102833) ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡71011151314129651214101178241110 4) ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡59859301346298345590162482. 有四个工人。