《运筹学》线性规划部分练习题 一、思考题 1． 什么是线性规划模型，在模型中各系数的经济意义是什么？ 2． 线性规划问题的一般形式有何特征？ 3． 建立一个实际问题的数学模型一般要几步？ 4． 两个变量的线性规划问题的图解法的一般步骤是什么？ 5． 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6． 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7． 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8． 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9． 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？
10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？
11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1． 线性规划问题的最优解一定在可行域的顶点达到。 2． 线性规划的可行解集是凸集。 3． 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4． 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5． 线性规划问题的每一个基本解对应可行域的一个顶点。 6． 如果一个线性规划问题有可行解，那么它必有最优解。 7． 用单纯形法求解标准形式（求最小值）的线性规划问题时，与0
>j σ对应的变量都可以被选作换入变量。 8． 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9． 单纯形法计算中，选取最大正检验数k σ对应的变量k x 作为换入变量，可使目 标函数值得到最快的减少。
10． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1． 某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到
第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？
2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：
设有某种原料的三个产地为321,,A A A ，把这种原料经过加工制成成品，再运往销售地。假设用4吨原料可制成1吨成品，产地1A 年产原料30万吨，同时需要成品7万吨；产地2A 年产原料26万吨，同时需要成品13万吨；产地3A 年产原料24万吨，不需要成品。又知1A 与2A 间距离为150公里， 1A 与3A 间距离为100公里，2A 与3A 间距离为200公里。原料运费为3千元 / 万吨公里，成品运费为2.5千元 / 万吨公里；在
1A 开设工厂加工费为5.5千元 / 万吨，在2A 开设工厂加工费为4千元 / 万吨，在3A 开设工厂加工费为3千元 / 万吨；又因条件限制，在2A 设厂规模不能超过年产成品5
万吨，1A 与3A 可以不限制（见表2——2），问应在何地设厂，生产多少成品，才使生产费用（包括原料运费、成品运费和加工费）最少？
工作八小时，为满足每班所需要的最少服务员数，这个旅馆至少需要多少服务员。
53500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元 / 人日，秋冬季收入为20元 / 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季
为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季
0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500
只鸡，牛栏允许最多养200头。三种作物每年需要的人工及收入情况如表2 — 4所示
6．市场对Ⅰ、Ⅱ两种产品的需求量为：产品Ⅰ在1 — 4月份每月需1万件，5—9月份每月需3万件，10 — 12月份每月需10万0件；产品Ⅱ在3 — 9月份每月需1.5万件，其它每月需5万件。某厂生产这两种产品的成本为：产品Ⅰ在1 — 5月份内生产时每件5元，6 — 12月份内生产时每件4.50元；产品Ⅱ在在1 — 5月份内生产时每件8元，
6 — 12月份内生产时每件7元；该厂每月生产两种产品能力总和不超过12万件。产品
Ⅰ容积每件0.2立方米，产品Ⅱ容积每件0.4立方米。该厂仓库容积为1万5千立方米，要求：（1）说明上述问题无可行解；（2）若该厂仓库不足时，可从外厂租借。若占用本厂仓库每月每立方米需1元，而租用外厂仓库时上述费用增加为1.5元，试问在满足市场需求情况下，该厂应如何安排生产，使总的生产加库存费用最少？（建立模型，不求解）
7．某工厂Ⅰ、Ⅱ、Ⅲ三种产品在下一年个季度的合同预定数如表 2 —5所示，该三种产品第一季度初无库存，要求在在第四季度末每种产品的库存为150件。已知该厂每季度生产工时为15000小时，生产产品Ⅰ、Ⅱ、Ⅲ每件需3，4，3小时。因更换工艺装备，产品Ⅰ在第二季度无法生产。规定当产品不能按期交货时，产品Ⅰ、Ⅱ每件每迟交一个季度赔偿20元，产品Ⅲ赔偿15元，又生产出来的产品不在本季度交货的，每件每季度的库存费为5元。问应如何安排生产，使总的赔偿加库存费用最小。
8
60
个为一箱。每箱玩具在不同的机器上加工所需的时间（天）如表2 —6 所示，本月可供使用的机器的时间为：Ａ为15天，Ｂ为20天，Ｃ为２４天。每箱玩具的价格为Ⅰ：1500元；Ⅱ：1700元；Ⅲ：2400元。问怎样安排生产，使总的产值最大。
产值，可变成本（即材料、人工等随产品数量变化的直接费用），加工工时等由表２—７给出，工厂有供纺纱的总工时7200h，织带的总工时1200h
（1）列出线性规划模型，以便确定产品数量，使总的利润最大。
（2）如果组织这次生产的固定成本（即与产品数量无关的间接费用）为20万元，线性规划模型有何变化？
10
产效率（每天制作的服装件数）等有关数据如表2—8所示，试确定各种服装的生产
数量，使总的加工费用最小。
11．某制衣厂生产两种服装，现有100名熟练工人。已知一名熟练工人每小时生产10件服装Ⅰ或6件服装Ⅱ。据销售部门消息，从本周开始，这两种服装的需求量将持续上升。见表2 — 9，为此，该厂决定到第8周末需培训出100名新工人，两班生产。已知一名工人一周工作40小时，一名熟练工人每周时间可培训出不多余5名的新工人（培训期间熟练工人和培训人员不参加生产）熟练工人每周工资400元，新工人在培训期间工资每周80元，培训合格后参加生产每周工资260元，生产效率同熟练工人。在培训期间，为按期交货，工厂安排部分工人加班生产每周工作50小时，工资每周600元。又若所定的服装不能按期交货，每推迟交货一周的赔偿费为：服装Ⅰ每件10元，服装Ⅱ每件20元。工厂应如何安排生产，使各项费用总和最少。
12．某家具制造厂生产五种不同规格的家具。每种家具都要经过机械成型、打磨、上漆几种主要工序。每种家具的每道工序所用时间及每道工序的可用时间，每种家具的利润由表2—10给出。问工厂应如何安排生产，使总的利润最大？
13．某混合饲料场饲养为某种动物配置。已知此动物的生长速度和饲料中的三种营养成分甲、
乙、丙有关，且每头动物每天需要营养甲85克，乙5克，丙18克。现有五种饲料都含有这三种营养成分，每种饲料每公斤所含营养成分及每种饲料成本如表 2—11所示，求即满足动物成长需要又使成本最低的饲料配方。
14A 可以按单位售价8元出售，也可以在第二车间继续加工，单位生产费用要增加6元，加工后单位售价增加9元。产品B 可以按单位售价7元出售，也可以在第三车间继续加工，单位生产费用要增加4元，加工后单位费用可增加6元。原料N 的单位购入价为2元，上述生产费用不包括工资在内。3个车间每月最多有20万工时，每工时工资0.5元，每加工1单位N 需1.5个工时，如A 继续加工,每单位需3工时，如B 继续加工，每单位需2个工时。原料N 每月最多能得到10万单位。问如何安排生产，使工厂获利最大。 15．某公司有30万元可用于投资，投资方案有下列几种：
方案Ⅰ：年初投资1元，第二年年底可收回1．2元。5年内都可以投资，但投资额不能超过１５万元。
方案Ⅱ：年初投资1元，第三年年底可收回1．3元。5年内都可以投资。 方案Ⅲ：年初投资1元，第四年年底可收回1．4元。5年内都可以投资。
方案Ⅳ：只在第二年年初有一次投资机会，每投资1元，四年后可收回1.7元。但最多投资额不能超过10万元。
方案Ⅴ：只在第四年年初有一次投资机会，每投资1元，年底可收回1.4元。但最多投资额不能超过20万元。
方案Ⅵ：存入银行，每年年初存入1元，年底可收回1.02元.
投资所得的收益及银行所得利息也可用于投资.求使公司在第五年底收回资金最多的投资方案.
16.某工厂生产Ⅰ、Ⅱ、Ⅲ、Ⅳ四种产品，产品Ⅰ需依次经过A 、B 两种机器加工，产品Ⅱ需依次经过A 、C 两种机器加工，产品Ⅲ需依次经过B 、C 两种机器加工，产品Ⅳ需依次经过A 、B 机器加工。。有关数据如表2—12所示，请为该厂制定一个最优生产计划。
1．
212max x x Z += 2．2122max x x Z +=
⎪⎩⎪⎨⎧≥≤+≤+0
,12261553212121x x x x x x ⎪⎩⎪⎨⎧≥≤+--≥-0,2
5.01212121x x x x x x 3．2132min x x Z += 4．21102min x x Z -= ⎪⎩⎪⎨⎧≥≥+≥+0,233212121x x x x x x ⎪⎩⎪⎨⎧≥-≥-≥-0,532212121x x x x x x 5．2193max x x Z += 6．21max x x Z += ⎪⎪⎪⎩⎪
⎪⎪⎨
⎧≥≤-≤≤+-≤+0,0
5264
3232121
22121x x x x x x x x x
⎪⎪⎩⎪⎪⎨
⎧≥≥≥+≤+0,51020
22112121x x x x x x x
五、用单纯形法解下列线性规划问题。（可用大M 法或两阶段法）。 （1）3212max x x x Z
+-= （2）3212max x x x Z ++=
⎪⎪⎩⎪⎪⎨⎧≥≤-+≤+-≤++0,,20102603321321321321x x x x x x x x x x x x ⎪⎪⎩⎪⎪⎨⎧≥≤++≤+≥++0,,1628420424
22432132121321x x x x x x x x x x x
(3)32133max x x x Z ++= (4)432142max x x x x Z +++= ⎪⎪⎩⎪⎪⎨⎧≥≤++≤++≤++0,,62253222321321321321x x x x x x x x x x x x ⎪⎪⎩⎪⎪⎨⎧≥≤++≤+≤++0,,,343243432143221421x x x x x x x x x x x x
(5)432132max x x x x Z -++= （6）3211004030max x x x Z -+= ⎪⎪⎩⎪⎪⎨⎧≥=+++=++=++0,,,1020
52153243214321
3
21321x x x x x x x x x x x x x x ⎪⎩⎪⎨⎧≥=-+=-+0,,1233034321321321x x x x x x x x x
(7) 43216max x x x x Z +-+= (8) 2134max x x Z +=
⎪⎪⎩⎪⎪⎨⎧≥=+++=+=++0
,,,1042185215243214321
313
21x x x x x x x x x x x x x ⎪⎪⎩⎪⎪⎨
⎧≥=+-=+=-++0,,,046312361243634321421314321x x x x x x x x x x x x x (9) 43218423min x x x x Z +++= (10)32125max x x x Z +-=
⎪⎩⎪⎨⎧≥≤-++-≥+++0,,,353528652432143214321x x x x x x x x x x x x ⎪⎩⎪⎨⎧
≥≥++≤++符号不限
321321321,,23264x x x x x x x x x
(11)432132max x x x x Z +-+= (12)321635max x x x Z ++= ⎪⎪
⎪⎩⎪
⎪⎪⎨⎧≥≥+-≤+-+-≤-+≥++-0,,,3132529243213143214324321x x x x x x x x x x x x x x x x x
⎪⎪⎩⎪⎪⎨
⎧
≥=++≤++≤++符号不限321321321321,0,101632182x x x x x x x x x x x x
六、表2—13中给出求极大化问题的单纯形表，问表中d c c a a ,,,,2121为何值时以及表中
变量属于哪一种类型时有：
（1）表中解为唯一最优解； （2）表中解为无穷多最优解之一； （3）表中解为退化的可行解；（4）下一步迭代将以1x 代替基变量5x ； （5）该线性规划问题具有无界解；（6）该线性规划问题无可行解。
七、某医院的护士分四个班次，每班工作12 h 。报到的时间分别是早上 6点 ，中午12点,下午 6 点，夜间 12点。每班需要的人数分别为19人，21人，18人，16人。问： （1）每天最少需要派多少护士值班？
（2）如果早上6点上班和中午12点上班的人每月有120元加班费，下午6点和夜间12
点上班的人每月分别有100元和150元加班费，如何安排上班人数，使医院支付的加班费最少？
八、某石油公司有两个冶炼厂。甲厂每天可生产高级、中级和低级的石油分别为200，300和200桶，乙厂每天可生产高级、中级和低级的石油分别为100，200和100桶。公司需要这三种油的数量分别为 14000，24000和14000桶。甲厂每天的运行费是5000元，乙厂是4000元。问：
（1）公司应安排这两个厂各生产多少天最经济？
（2）如甲厂的运行费是2000元，乙厂是5000元。公司应如何安排两个厂的生产。 列出线性规划模型并求解。
《运筹学》习题解答
第二章 线性规划模型及其单纯形法
二、(1) X (2) √ (3) √ (4) √ (5) X (6) X (7) √ (8) √(9) X (10) √ 三、
1．解：设决策变量1211,x x 分别表示第一年投资到项目Ⅰ、Ⅱ的资金额；2321,x x 分别表
示第二年投资到项目Ⅰ、Ⅲ的资金额；3431
,x x 分别表示第三年投资到项目Ⅰ、Ⅳ的资
金额。则得线性规划模型如下：
3423123121114.06.05.02.02.02.0max x x x x x x Z +++++=
⎪⎪
⎪
⎪⎩⎪
⎪⎪
⎪⎨
⎧
≥≤≤≤≤++-+--≤+++-≤+0,,,,,1000001500002000003000005.02.02.03000002.0300000342312312111342312342312312111231221111211x x x x x x x x x x x x x x x x x x x x x
2．解：设五种饲料分别选取54321,,,,x x x x x 公斤，则得下面的数学模型： 543218.03.04.07.02.0min x x x x x Z ++++=
⎪⎪⎩⎪⎪⎨
⎧=≥≥++++≥++++≥++++)5,4,3,2,1(01008.022.05.0305.022.05.0700
12623543215432154321j x x x x x x x x x x x x x x x x j ；
3．解：设j i x 表示由i A 运往j A
的原料数（单位：万吨）（)3,2,1,
=j i 。其中j i =时，
表示i A 留用数；j i y 表示由i A 运往j A
的成品数（单位：万吨）（)3,2,1,=j i 。其中j i =时，表示i A 留用数；i z 表示在i A 设厂的年产成品数（单位：万吨）（)3,2,1=i 。
则这一问题的数学模型为：
3
2132312321
1312323123211312345.5)(5.2)(3min z z z y y y y y y x x x x x x Z ++++++++++++++=
⎪⎪
⎪⎪⎪⎪⎪⎪⎪⎩⎪
⎪⎪⎪⎪⎪
⎪⎪⎪⎨⎧=≥≥≥≤=++=++=++=++=++=++=++=++=++=++=++)3,2,1,(0,0,05137
4442413
30232221231
2111
33332312232221
1131211333231323222121312111333231232221
131211j i z y x z y y y y y y z y y y z
y y y z y y y z x x x z x x x z x x x x x x x x x x x x i j i j
i 4．解：设=i x i (1，2，3，4，5，6）为第i 班开始上班的服务员人数。则数学模型： 654321min x x x x x x Z +++++=
⎪⎪⎪⎪⎩⎪
⎪⎪⎪⎨⎧=≥≥+≥+≥+≥+≥+≥+)6,,1(030
40
708090
80655
4
433221
16 j x x x x x x x x x x x x x j
5．用321,,x x x 分别表示大豆、玉米、麦子的种植公顷数；54,x x 分别表示奶牛和鸡的饲养数；76,x x 分别表示秋冬季和春夏季的劳动力（人日）数，则有 7654321252020900460041003000max x x x x x x x Z ++++++=
⎪⎪
⎪
⎪⎩⎪
⎪⎪
⎪
⎨⎧=≥≤≤≤+++++≤+++++≤+≤+++)7,,2,1(0)(1500)(200)(40003.0504017550)(35006.010*******)(150003400)(1005.154754321654321544
321 j x x x x x x x x x x x x x x x x x x x x x j
鸡舍限制牛栏限制劳动力限制劳动力限制资金限制土地限制
6．解：（1）因为10 — 12月份市场需求总计45万件，这三个月最多生产36万件，故需10月初有9万件的库存，超过该厂的最大仓库容积，故按上述条件，本题无解。
（2）考虑到生产成本、库存费用和生产能力，该厂１０— １２月份需求的不足只需在７
— ９月份生产出来留用即可，故设：i x 为第i 个月生产的产品Ⅰ的数量；i y 为第i 个月生
产的产品Ⅱ的数量；i i u z ,分别为第i 个月末产品Ⅰ、Ⅱ的库存数，i i s
s 21,分别为用于第（i ＋１）个月库存的原有及租用的仓库容积（立方米），则所求问题的数学模型为：
∑∑∑===+++++=126
11
7
2151
)
()75.4()85(min i i i i i i i i i s s y x y x Z
⎪⎪⎪
⎪⎪⎪
⎪⎪⎩⎪⎪
⎪⎪⎪
⎪⎪⎪⎨
⎧≥=≤=+=+=≤+=+=+=-+=-+=-+=-+=-+=-+=-+=-+=-=-========0,,,,,)12,11,10,9,8,7(15000
)12,11,10,9,8,7(4.02.0)12,11,10,9,8,7(120000500001000005000010000050000100000150003000015000300001500030000)6,5,4,3(15000)2,1(50000)6,5(30000)4,3,2,1(10000211211112111211
10111110111091010
9109899898
788787777i i i i i i i i i i i i i i i
i i s s u z y x i s i s s u z i y x u y z x u u y z z x u u y z z x u u y z z x u u y z z x u y z x i y i y i x i x
7．解：设
j i x 为第i 个季度生产的产品j 的数量；
j i s 为第i
个季度末需库存的产品j 的数量；
j
i t 为第i 个季度不能交货的产品j 的数量；j i y
为第i 个季度对产品j 的预定数量，则有：
[]
∑∑∑===+++=4
1
313
1
321515)(20min i i j j
i i i i s t t t Z
⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥===-+=+===≤++∑∑∑∑====0,,)3,2,1;4,3,2,1()3,2,1(1500)4,3,2,1(15000114
14
1
1
2321j i j i j i i
k i k j k j i j i j k i i j i j i i i i t s x j i y s t x j y x x i x x x ８．设j x
为第)3,2,1(=j j 种玩具的生产数量，则有：
321240017001500max x x x Z ++=
⎪⎪⎩⎪⎪⎨
⎧≥≤+≤++≤++为整数0,,24252022315
623212
1321321x x x x x x x x x x x
９．解：（１）设Ａ、Ｂ、Ｃ、Ｄ四种产品的生产数量分别为4321,,,x x x x ，则有：
4321)140406()3501050()28140()42168(max x x x x Z -+-+-+-=
⎪⎩⎪⎨⎧≥≤+≤+++0,,,12005.027200410234321434321x x x x x x x x x x （２）当增加固定资本２０万元时，线性规划模型没有变化。
10．解：设j
i x )3,2,1;4,3,2,1(==j i 为第j 台制衣机生产第i 种服装的天数，则有： ∑∑∑===++=41413241115010080min i i i i i i x x x Z
⎪⎪⎪⎩⎪⎪⎪⎨⎧==≥≤++≤++≤++≤++)3,2,1;4,3,2,1(080004504101507000
680350200900070045028010000800600300434241333231232221131211j i x x x x x x x x x x x x x j i 11．解：设i i y x ,分别表示第i 周用于生产服装Ⅰ或服装Ⅱ的工人数，i z 表示第i 周开始加班的工人数，i w 为从第i 周开始参加培训新工人的熟练工人数，i u 表示第i 周起开始接受培
训的新工人数，1i v 和2i v 分别为第i 周末没能按期交货的服装Ⅰ或服装Ⅱ的数量，1i M 和
2i M 分别为第i 周对服装Ⅰ或服装Ⅱ的定货量，则有：
∑∑∑===-++++=81812181
)]8(26080[)2010(600min i i i
i i i i u i v v z Z [][]⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎨⎧≥≤≤≤=≤≤++=+++=++==+==+∑∑∑∑∑∑======0
,,,,,,)81(5100)82(25.010025.0100)8,,2,1(240)8,,2,1(40021811111111221111i i i i i i i i i i i i t i t i i i k i k i i i i k i k i i i i v v u w z y x i w u u i z u w y x z w y x k M v y k M v x
12．解：设五种家具的产量分别为54321,,,,x x x x x 件，则有 5432135.25.437.2min x x x x x z ++++= ⎪⎪⎩⎪⎪⎨⎧≥≤++++≤++++≤++++0,,,,2800
5433239504653436003264354321543215432154321x x x x x x x x x x x x x x x x x x x x
13．解：设j
x )5,4,3,2,1(=j 为每公斤混合饲料中所含五种饲料的重量，则有 5432134562min x x x x x z ++++=
⎪⎪⎩⎪⎪⎨⎧≥≥++++≥++++≥++++0,,,,18
02.025.035.070.008.0520.015.004.006.010.08580.050.100.300.250.054321543215432154321x x x x x x x x x x x x x x x x x x x x
14．解：设1x ：产品A 的售出量；2x ：A 在第二车间加工后的售出量；
3x ：产品B 的售出量；4x ：B 在第三车间加工后的售出量； 5x ：第一车间所用的原料数量。则有
5432175.2875.98max x x x x x z -+++=
⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=-+=-+≤++≤0,,,,020********.123100000543215435215425x x x x x x x x x x x x x x x 15．解：设j i x 为第i 种投资方案在第j 年的投资额)5,,2,1;6,,2,1( ==j i ，则有： 6542231402.17.13.12.1max x x x x z +++=
⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧≥≤=≤++++=++=+++=++≤=++++=+++0200000)
4,3,2,1(1500002.14.14.13.12.102.13.12.102.12.110000002.130000054
1645431221365
632112645414621163231342616242322212
61312111j i j x x j x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 16．解：设)4,3,2,1(=j x j 为第j 种产品的生产数量，则有
43214321256.295.325.2752385549max x x x x x x x x Z ----+++=
⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≤++≤++0,,,70
1510120101020150
2020104
32132431421x x x x x x x x x x x x 其中：49=65-16 ；27.5=200/20 + 150/10 ，依次类推。
四、解：
1．有唯一最优解，
3,0,621*===x x z ； 2．有可行解，但Z max 无界；
3．有唯一最优解，
21,23,2921*===x x z ； 4．无可行解；
5．有无穷多个最优解，66*=z ；
6．有唯一最优解，
10,5,1521*===x x z . 五、解：1．
0,5,15,25321*====x x x z 2．有无穷多个最优解 ，例如0,0,4321===x x x ；或
8,0,0321===x x x 等 ，此时8*=z .
3．
6.1,0,2.0,4.5321*====x x x z . 4．
5.0,1,1,5.6321*====x x x z 5.
0,5.2,5.2,5.2.154321=====*x x x x z . 6.
0,2,6.260321====*x x x z . 7. 无可行解。
8.
0,4,0,0.04321=====*x x x x z . 9.
21.0,35.1,0,0.08.74321=====*x x x x z . 10.
10,0,16.70321-====*x x x z . 11.
4.3,0,2.4,8.9.6.354321=====*x x x x z 12.
4,0,14.46321-====*x x x z 六、解：(1) 0,0,021<<≥c c d ；
(2)
0,0,021≤≤≥c c d , 但 21,c c 中至少有一个为零 ；
（3）0=d ，或 0>d ，而01>c ，且234a d =；
（4）01>c ，234a d >； （5）0,012≤>a c ； （6）5x 为人工变量，且0,021≤≤c c .
七、解：设4321,,,x x x x 分别表示早上 6点 ，中午12点,下午 6 点，夜间 12点
开始上班的人数。则有
（1）
4321min x x x x Z +++=；（2）
4321150100)(120min x x x x Z +++=
⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥+≥+≥+≥+0,,,161821194
32143322141x x x x x x x x x x x x ； ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥+≥+≥+≥+0,,,16182119432143322141x x x x x x x x x x x x 解得：（1）
0,16,2,19,374321=====*x x x x z ； （2）
0,16,2,19,41204321=====*x x x x z 。 八、解：（1）解得
60,40,44000021===*x x z ； （2）解得 60,40,38000021===*x x z 。
《运筹学》练习卷（一）－答案 一、填空题（每空1分，共8分） 1、在线性规划问题中，若存在两个最优解时，必有相邻的顶点是最优解。 2、树图中，任意两个顶点间有且仅有一条链。 3、线性规划的图解法适用于决策变量为两个的线性规划模型。 4、在线性规划问题中，将约束条件不等式变为等式所引入的变量被称为松弛变量。 5、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。 6、运输问题中求初始基本可行解的方法通常有最小费用法与西北角法两种方法。 7、称无圈的连通图为树，若图的顶点数为p，则其边数为 p－1 。 二、单项选择题（每题2分，共10分） 1、最早运用运筹学理论的是（A） A 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署 B 美国最早将运筹学运用到农业和人口规划问题上 C 二次世界大战期间，英国政府将运筹学运用到政府制定计划 D 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上 2、下列哪些不是运筹学的研究范围（D） A 质量控制 B 动态规划 C 排队论 D 系统设计 3、对于线性规划问题，下列说法正确的是（D） A 线性规划问题可能没有可行解 B 在图解法上，线性规划问题的可行解区域都是“凸”区域 C 线性规划问题如果有最优解，则最优解可以在可行解区域的顶点上到达 D 上述说法都正确 4、下面哪些不是线性规划问题的标准形式所具备的（C）A所有的变量必须是非负的 B 所有的约束条件（变量的非负约束除外）必须是等式 C 添加新变量时，可以不考虑变量的正负性 D 求目标函数的最小值 5、在求解运输问题的过程中运用到下列哪些方法（D） A 西北角法 B 位势法 C 闭回路法 D 以上都是 三、名词解释（每题3分，共12分） 1、需求：对存储来说，需求就是输出。最基本的需求模式是确定性的，在这种情况下，某一种货物的未来需求都是已知的。
《运筹学》试题及答案 第二章线性规划的基本概念 一、填空题 1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。2．图解法适用于含有两个变量的线性规划问题。 3．线性规划问题的可行解是指满足所有约束条件的解。 4．在线性规划问题的基本解中，所有的非基变量等于零。 5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关 6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。 7．线性规划问题有可行解，则必有基可行解。 8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。 9．满足非负条件的基本解称为基本可行解。 10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。 11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。 12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。13．线性规划问题可分为目标函数求极大值和极小_值两类。 14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。 15．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16．在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。 17．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。 18.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。
19.如果某个变量X j为自由变量，则应引进两个非负变量X j′,X j〞,同时令X j ＝X j ′－X j 。 20.表达线性规划的简式中目标函数为max(min)Z=∑c ij x ij。 21..(2.1 P5))线性规划一般表达式中，a ij表示该元素位置在i行j列。 二、单选题 1．如果一个线性规划问题有n个变量，m个约束方程(m 《运筹学》试题及答案 19、简述线性规划模型主要参数（p11） （1）、价值系数：目标函数中决策变量前的系数为价值系数 （2）、技术系数：约束条件中决策变量前的系数 （3）、约束条件右边常数项 15、简述线性规划解几种可能的结果（情形）（ppt第二章39或89页） （1）.有唯一最优解 (单纯形法中在求最大目标函数的问题时，对于某个基本可行解，所有δj≤0) （2）.无可行解，即可行域为空域，不存在满足约束条件的解，也就不存在最优解了。 （3）.无界解，即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小，一般来说，这说明模型有错，忽略了一些必要的约束条件 （4）.无穷多个最优解，则线段上的所有点都代表了最优解 （5）退化问题，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，用图解法无退化解 1、简述单纯形法的基本思路（p70） 从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。 17、简述线性规划中添加人工变量的前提（p85） 在系数矩阵中直接找不到初始可行解，进而通过添加人工变量的方法来构造初始可行基，得出初始基本可行解 10、简述线性规划对偶问题的基本性质（p122） （1）对称性（2）弱对偶性（3）强对偶性（4）最优性（5）互补松弛型原函数与对偶问题的关系 1）求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。 《运筹学》试题参考．． 答案 一、填空题（每空2分，共10分） 1、在线性规划问题中，若存在两个最优解时，必有 相邻的顶点是 最优解。 2、树图中，任意两个顶点间有且仅有 一条链 。 3、线性规划的图解法适用于决策变量为 两个 线性规划模型。 4、在线性规划问题中，将约束条件不等式变为等式所引入的变量被称为 松弛变量 。 5、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点，化为供求平衡的标准形式 。 6、运输问题中求初始基本可行解的方法通常有 最小费用法 与 西北角法 两种方法。 7、称无圈的连通图为树，若图的顶点数为p ，则其边数为 p －1 。 二、（每小题5分，共10分）用图解法求解下列线性规划问题： 1）max z = 6x 1+4x 2 ?????? ?≥≤≤+≤+0 7810 22122121x x x x x x x ， ⑴ ⑵ ⑶ ⑷ ⑸、⑹ 2）min z =2x 1+x 2 ???????≥≤≤≥+≤+-0 1058244212121x x x x x x 解： 从上图分析，可行解域为abcde ，最优解为e 点。 由方程组 ???==+58 1 21x x x 解出x 1=5，x 2=3 ∴X * =??? ? ??21x x =（5，3） T ∴min z =Z *= 2×5+3=13 三、（15分）一家工厂制造甲、乙、丙三种产品，需要三种资源——技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示： ⑴ ⑵ ⑶ ⑷、⑸ ⑹ 1）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分） 2）用单纯形法求该问题的最优解。（10分） 解：1）建立线性规划数学模型： 设甲、乙、丙三种产品的生产数量应为x 1、x 2、x 3，则x 1、x 2、x 3≥0，设z 是产品售后的总利润，则 max z =10x 1+6x 2+4x 3 s.t. ???????≥≤++≤++≤++0 3006226005410100 321321321321x x x x x x x x x x x x ，， 2）用单纯形法求最优解： 加入松弛变量x 4，x 5，x 6，得到等效的标准模型： max z =10x 1+6x 2+4x 3+0 x 4+0 x 5+0 x 6 s.t. ?? ? ????=≥=+++=+++=+++6,...,2,1,03006226005410100632153214 321j x x x x x x x x x x x x x j 列表计算如下： 第一章线性规划 习题1.1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？ 解：设x1、x2分别代表甲、乙两种产品的生产数量（件），z表示公司总利润。依题意，问题可转换成求变量x1、x2的值，使总利润最大，即 ma x z=50x1+100x2 且称z=50x1+100x2为目标函数。 同时满足甲、乙两种产品所消耗的A、B、C三种资源的数量不能超过它们的限量，即可分别表示为 x1 + x2≤300 2x1 + x2≤400 x2≤250 且称上述三式为约束条件。此外，一般实际问题都要满足非负条件，即x1≥0、x2≥0。 这样有 ma x z=50x1+100x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x1、x2≥0 习题1.2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m 3，在两个工厂之间有一条流量为200万m 3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m 3和1.4万m 3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m 3和800元/万m 3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。 解：设x 1、x 2分别代表工厂1和工厂2处理污水的数量(万m 3)。则问题的目标可描述为 min z =1000x 1+800x 2 约束条件有 第一段河流（工厂1——工厂2之间）环保要求 (2－x 1)/500 ≤0.2% 第二段河流（工厂2以下河段）环保要求 [0.8(2－x 1) +(1.4－x 2)]/700≤0.2% 此外有 x 1≤2； x 2≤1.4 化简得到 min z =1000x 1+800x 2 x 1 ≥1 0.8x 1 + x 2 ≥1.6 x 1 ≤2 x 2≤1.4 x 1、x 2≥0 习题1.3 ma x z =50x 1+100x 2 x 1 + x 2≤300 2x 1 + x 2≤400 x 2≤250 图1—1 x 2 一、填空题：（每空格2分，共16分） 1、线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。 2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明 如果在该空格中增加一个运量运费将增加4 。 3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错 4、如果某一整数规划： MaxZ=X 1+X 2 X 1+9/14X 2≤51/14 -2X 1+X 2≤1/3 X 1,X 2≥0且均为整数 所对应的线性规划（松弛问题）的最优解为X 1=3/2，X 2=10/3，MaxZ=6/29，我们现在要对X 1进行分枝，应该分为 X 1≤1 和 X 1≥2 。 5、在用逆向解法求动态规划时，f k (s k )的含义是： 从第k 个阶段到第n 个阶段的最优解 。 6. 假设某线性规划的可行解的集合为D ，而其所对应的整数规划的可行解集合为B ，那么D 和B 的关系为 D 包含 B 7. 已知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条 X B b X 1 X 2 X 3 X 4 X 5 X 4 3 0 0 -2 1 3 X 1 4/3 1 0 -1/3 0 2/3 X 2 1 0 1 0 0 -1 C j -Z j 0 0 -5 0 -23 问：（1）写出B -1 =???? ? ??---1003/20.3/131 2 (2)对偶问题的最优解： Y ＝（5，0，23，0，0）T 8. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______； 9. 极大化的线性规划问题为无界解时，则对偶问题_无解_________； 10. 若整数规划的松驰问题的最优解不符合整数要求，假设X i =b i 不符合整数要求，INT （b i ）是不超过b i 的最大整数，则构造两个约束条件：Xi ≥INT （b i ）＋ 运筹学试题及答案 运筹学试题及答案 《运筹学》复习试题及答案(一) 一、填空题 1、线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。 2、图解法适用于含有两个变量的线性规划问题。 3、线性规划问题的可行解是指满足所有约束条件的解。 4、在线性规划问题的基本解中,所有的非基变量等于零。 5、在线性规划问题中,基可行解的非零分量所对应的列向量线性无关 6、若线性规划问题有最优解,则最优解一定可以在可行域的顶点(极点)达到。 7、线性规划问题有可行解,则必有基可行解。 8、如果线性规划问题存在目标函数为有限值的最优解,求解时只需在其基可行解_的集合中进行搜索即可得到最优解。 9、满足非负条件的基本解称为基本可行解。 10、在将线性规划问题的一般形式转化为标准形式时,引入的松驰数量在目标函数中的系数为零。 11、将线性规划模型化成标准形式时,“?”的约束条件要在不等式左_端加入松弛变量。 12、线性规划模型包括决策(可控)变量,约束条件,目标函数三个要素。 13、线性规划问题可分为目标函数求极大值和极小_值两类。 14、线性规划问题的标准形式中,约束条件取等式,目标函数求极大值,而所有变量必须非负。 15、线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解 16、在用图解法求解线性规划问题时,如果取得极值的等值线与可行域的一段边界重合,则这段边界上的一切点都是最优解。 17、求解线性规划问题可能的结果有无解,有唯一最优解,有无穷多个最优解。 18、 19、如果某个变量Xj为自由变量,则应引进两个非负变量Xj , Xj,同时令 Xj=Xj- Xj。 20、表达线性规划的简式中目标函数为ijij 21、、(2、1 P5))线性规划一般表达式中,aij表示该元素位置在 二、单选题 1、如果一个线性规划问题有n个变量,m个约束方程(m<n),系数矩阵的数为m,则基可< p=""> 行解的个数最为_C_。′〞′ A、m个 B、n个 C、Cn D、Cm个 2、下列图形中阴影部分构成的集合是凸集的是 A mn 3、线性规划模型不包括下列_ D要素。 A、目标函数 B、约束条件 C、决策变量 D、状态变量 4、线性规划模型中增加一个约束条件,可行域的范围一般将_B_。 A、增大 B、缩小 C、不变 D、不定 5、若针对实际问题建立的线性规划模型的解是无界的,不可能的原因是B__。 A、出现矛盾的条件 B、缺乏必要的条件 C、有多余的条件 D、有相同的条件 6、在下列线性规划问题的基本解中,属于基可行解的是 D A、(一1,0,O) B、(1,0,3,0) C、(一4,0,0,3) 0,5) 《运筹学》前8周课程参考习题 一、考虑下列线性规划模型 某企业生产甲、乙、丙三类特种钢材，每吨甲，乙，丙钢材需要加入金属材料A，B， 求使得总利润最高的生产方案。使用《运筹学》教学软件，得到结果如下： 他们的关系及含义是什么？ b．解释松弛/ 剩余变量的含义。如果原料A、B、C、D可以用相同的价格购买补充，你将优先考虑哪一种，为什么？购买价格在什么范围内，你可以接受？ c．当钢材甲的利润由12千元／吨变为10千元／吨的同时，产品乙的利润由9千元／吨变为9.5千元／吨，这时原来的最优方案变不变？为什么？ d．当其它金属原料的供应量不变时，金属原料C的供应量在什么范围内可以保证对偶价格不变？试解释其含义。 ●参考解答： a．最优解：( 87.273，19.091,0 )T； 最优值：1219.091； 对偶价格：( 1.273，0,0,1.545 )T； 对偶价格分量表示相应资源增加（或减少）1个单位，最优值增加（或减少）的数量。 b．解释松弛/ 剩余变量的含义：实际使用的资源与资源限额的差； 如果原料A、B、C、D可以用相同的价格购买补充，将优先考虑D，因为D的影子 价格最高。D的购买价格在1.54千元以下时可以接受。 c．根据百分之一百法则： 原来的最优方案不变。 d．当其它金属原料的供应量不变时，金属原料C的供应量大于等于201.818kg时，可以保证对偶价格不变。其含义是：在这个范围内，原料C的增加或减少都不会应影响最优利润，因为C在这个范围内对偶价格为0。 二、某企业生产三种仪器A、B、C，所需要的加工时间分别为10小时、8小时和13小时，每月的正常加工时间为600 小时；生产成本分别为12万元、15万元和10万元，每月可支付生产成本的资金为700万元；各产品可获得的利润均为成本的10％。根据调查分析，市场对仪器A、B、C的需求分别为30台、20台和18台。决策者考虑： 首先，要尽可能达到产品数量的需求；其次，要充分发挥企业的加工能力；第三，要求尽可能获得较多的利润；最后，要求加班时间最少。问应如何安排生产？(建模，不求解) ●参考解答 设x1, x2, x3分别为仪器A、B、C的产量 三、某企业生产甲、乙、丙三种产品，其每单位所消耗工时分别为1.6、2.0、2.5小时，每单位所需原料A分别为24、20、12 kg，所需原料B分别为14、10、18 kg。生产线每月正常工作时间为240 小时，原料A、B的总供应量限制为2400kg和1500kg 。生产一个甲、乙、丙产品各可获利润525、678、812元，试分别建立以下两种情况下的数学模型，不需要计算。 a．由于每单位丙产品的生产会产生5kg 副产品丁，这些副产品丁一部分可以销售，利润为300元/kg，剩下的会造成污染，每kg需要排污费200元。副产品丁的需求量为每月不超过150kg。应如何确定生产计划，可使总利润最大？ b．工厂考虑到产品丙有污染，决定不生产丙而准备在另外的三种产品W、Q、G中选择1种或2种来进行生产，它们所消耗工时、所需原料A、B及利润如下表： 应如何确定生产计划，可使总利润最大？ 第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量） ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量 的检验数 （标准形为 求最小值），其经济意义是什么？ 8．将 的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量 ，说明在最优生产计 划中，第 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量 ，说明在最优生产计 划中，第 种资源一定还有剩余。 8．对于 来说，每一个都有有限的变化范围，当其改变超出了这个范围之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为 ，则在其它资源数量不变的情况下，该资源增加 个单位，相应的目标函数值增加 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量 ，且 所在行的 所有元素都大于或等于零，则其对偶问题具有无界解。 三、写出下列线性规划的对偶问题 （1） （2） ； 第一章 线性规划及单纯形法 一、写出下列线性规划的标准形式，用单纯形法求解，并指出其解属于哪种情 况。 1、P55,1.3(a) 21510m ax x x Z += ⎪⎩⎪ ⎨⎧≥≤+≤+0x ,x 8x 2x 59x 4x 3. t .s 2 12121 解：将模型化为标准型 21510x x Z Max += ⎪⎩⎪ ⎨⎧≥=++=++0,,,825943. .4 32142 13 21x x x x x x x x x x t s 单纯形表如下 因所有检验数0j ≤σ，已达最优解，最优解是)2,1(*=X ，最优目标值为2 。由 检验数的情况可知，该问题有唯一最优解。 2、 P55,1.3(b) 21x x 2Z m ax += s.t ⎪⎪⎩⎪⎪⎨ ⎧ ≥≤+≤+≤0 ,5 24261552121212x x x x x x x 解：将模型化为标准型 21x x 2Z Max += t s . ⎪⎪⎩⎪⎪⎨ ⎧ ≥=++=++=+0 x ,...,x ,x ,5x x x ,24x x 2x 6,15x x 552152142 132 单纯形表如下 因所有检验数0j ≤σ，已达最优解，最优解是)0,0,2 ,2,2(X *=，最有目标值为 2 17 。由检验数的情况可知，该问题有唯一最优解。 3、 3212x x x Z Min -+=， t s . ⎪⎪⎩⎪⎪⎨ ⎧≥≤++≤+-≤-+0 ,,,5,822,4223213213 21321x x x x x x x x x x x x 解：将模型化为标准型： 3212x x x Z Min -+= t s . ⎪⎪⎩⎪⎪⎨ ⎧≥=+++=++-=+ -+0 ,,,5,822,42232163 2153 214 321x x x x x x x x x x x x x x x 用单纯形法迭代 《运筹学》试题及答案（A卷） 一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题1分，共10分） 1．线性规划具有唯一最优解是指 A．最优表中存在常数项为零 B．最优表中非基变量检验数全部非零 C．最优表中存在非基变量的检验数为零 D．可行解集合有界 2．设线性规划的约束条件为 则基本可行解为 A．(0, 0, 4, 3)B．(3, 4, 0, 0) C．(2, 0, 1, 0)D．(3, 0, 4, 0) 3．则 A．无可行解B．有唯一最优解medn C．有多重最优解D．有无界解 4．互为对偶的两个线性规划, 对任意可行解X 和Y，存在关系 A．Z > W B．Z = W C．Z≥W D．Z≤W 5．有6 个产地4个销地的平衡运输问题模型具有特征 A．有10个变量24个约束 B．有24个变量10个约束 C．有24个变量9个约束 D．有9个基变量10个非基变量 6.下例错误的说法是 A．标准型的目标函数是求最大值 B．标准型的目标函数是求最小值 C．标准型的常数项非正 D．标准型的变量一定要非负 7. m+n－1个变量构成一组基变量的充要条件是 A．m+n－1个变量恰好构成一个闭回路 B．m+n－1个变量不包含任何闭回路 C．m+n－1个变量中部分变量构成一个闭回路 D．m+n－1个变量对应的系数列向量线性相关8．互为对偶的两个线性规划问题的解存在关系A．原问题无可行解，对偶问题也无可行解 B．对偶问题有可行解，原问题可能无可行解 C．若最优解存在，则最优解相同 D．一个问题无可行解，则另一个问题具有无界解9.有m个产地n个销地的平衡运输问题模型具有特征 A．有mn个变量m+n个约束…m+n-1个基变量 B．有m+n个变量mn个约束 C．有mn个变量m+n－1约束 D．有m+n－1个基变量，mn－m－n－1个非基变量 2020年运筹学考试复习题及答案 5、线性规划数学模型具备哪几个要素？答：（1）.求一组决策变量x i或x ij的值（i =1，2，…m j=1，2…n）使目标函数达到极大或极小；（2）.表示约束条件的数学式都是线性等式或不等式；（3）.表示问题最优化指标的目标函数都是决策变量的线性函数 第二章线性规划的基本概念 一、填空题 1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。 2．图解法适用于含有两个变量的线性规划问题。 3．线性规划问题的可行解是指满足所有约束条件的解。4．在线性规划问题的基本解中，所有的非基变量等于零。5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关 6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。 7．线性规划问题有可行解，则必有基可行解。 8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。9．满足非负条件的基本解称为基本可行解。 10．在将线性规划问题的一般形式转化为标准形式时，引入的 松驰数量在目标函数中的系数为零。 11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。 13．线性规划问题可分为目标函数求极大值和极小_值两类。14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。 15．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解 16．在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。17．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。 18.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。 19.如果某个变量X j为自由变量，则应引进两个非负变量X j′,X j〞,同时令X j＝X j′－X j。 20.表达线性规划的简式中目标函数为max(min)Z=∑c ij x ij。 21..(2.1 P5))线性规划一般表达式中，a ij表示该元素位置在i 行j列。 二、单选题 1．如果一个线性规划问题有n个变量，m个约束方程(m 《运筹学》线性规划部分练习题 一、思考题 1． 什么是线性规划模型，在模型中各系数的经济意义是什么？ 2． 线性规划问题的一般形式有何特征？ 3． 建立一个实际问题的数学模型一般要几步？ 4． 两个变量的线性规划问题的图解法的一般步骤是什么？ 5． 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6． 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7． 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8． 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9． 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1． 线性规划问题的最优解一定在可行域的顶点达到。 2． 线性规划的可行解集是凸集。 3． 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4． 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5． 线性规划问题的每一个基本解对应可行域的一个顶点。 6． 如果一个线性规划问题有可行解，那么它必有最优解。 7． 用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量都可以被选作换入变量。 8． 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9． 单纯形法计算中，选取最大正检验数k σ对应的变量k x 作为换入变量，可使目 标函数值得到最快的减少。 10． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1． 某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示： 最全运筹学习题及答案 共1 页 运筹学习题答案 ） 1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。 （1）max z?x1?x2 5x1+10x2?50 x1+x2?1 x2?4 x1，x2?0 （2）min z=x1+1.5x2 x1+3x2?3 x1+x2?2 x1，x2?0 （3）+2x2 x1-x2?-0.5x1+x2x1，x2?0 （4）max z=x1x2 x1-x2?0 3x1-x2?-3 x1，x2?0 （1）（图略）有唯一可行解，max z=14 （2）（图略）有唯一可行解，min z=9/4 （3）（图略）无界解 （4）（图略）无可行解 1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。共2 页 （1）min z=-3x1+4x2-2x3+5x4 4x1-x2+2x3-x4=-2 x1+x2+3x3-x4?14 -2x1+3x2-x3+2x4?2 x1，x2，x3?0，x4无约束（2 zk?i??x k?1 m xik?（1Max s. t . -4x1xx1,x2 共3 页 (2)解：加入人工变量x1，x2，x3，…xn，得：Max s=(1/pk)? i?1n ? k?1 m ?ikxik-Mx1-Mx2-…..-Mxn m （1）max z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x4=8 x1-2x2+6x3-7x4=-3 x1,x2,x3,x4?0 (2)max z=5x1-2x2+3x3-6x4 共4 页 x1+2x2+3x3+4x4=7 2x1+x2+x3+2x4=3 x1x2x3x4?0 （1）解： 系数矩阵A是： ?23?1?4??1?26?7? ?? 令A=(P1，P2，P3，P4) P1与P2线形无关，以（P1，P2有2x1+3x2=8+x3+4x4 x1-2x2=-3-6x3+7x4 令非基变量x3，x4解得：x1=1；x2=2 基解0，0)T为可行解 z1=8 (2)同理，以（P=（45/13，0，-14/13，0)T是非可行解；3以（P1，P4X(3)=，，7/5)T是可行解，z3=117/5； (4)以（P2，P=（，45/16，7/16，0)T是可行解，z4=163/16；3以（P2， 《运筹学》试题及答案 (代码：8054) 一、填空题(本大题共8小题，每空2分，共20分) 1．线性规划闯题中，如果在约束条件中出现等式约束，我们通常用增加_人工变量__的方法来产生初始可行基。 2．线性规划模型有三种参数，其名称分别为价值系数、_技术系数__和_限定系数__。3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是_无非负约束(或无约束、或自由__变量。 4．求最小生成树问题，常用的方法有：避圈法和 _破圈法__。 5．排队模型M／M／2中的M，M，2分别表示到达时间为__负指数_分布，服务时间服从负指数分布和服务台数为2。 6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为__不确定__型决策。 7．在风险型决策问题中，我们一般采用__效用曲线_来反映每个人对待风险的态度。 8．目标规划总是求目标函数的_最小__信，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的_优先因子(或权重)___。 二、单项选择题(本大题共l0小题，每小题3分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。多选无分。 9．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题【 D 】 A．有唯一的最优解 B．有无穷多最优解 C．为无界解 D．无可行解 10．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中【 D 】 A．b列元素不小于零 B．检验数都大于零 C．检验数都不小于零 D．检验数都不大于零 11．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为【 A 】 A．3 B．2 C．1 D．以上三种情况均有可能 第一章 线性规划 1、 由图可得：最优解为 2、用图解法求解线性规划： Min z=2x 1+x 2 ⎪⎪⎩⎪⎪ ⎨⎧≥≤≤≥+≤+-01058 2442 12121x x x x x x 解： 由图可得：最优解x=1.6,y=6.4 Max z=5x 1+6x 2 ⎪ ⎩⎪ ⎨⎧≥≤+-≥-0 ,23222212 121x x x x x x 解： 由图可得：最优解Max z=5x 1+6x 2, Max z= +∞ Maxz = 2x 1 +x 2 ⎪⎪⎩⎪⎪ ⎨ ⎧≥≤+≤+≤0,5242261552121211x x x x x x x 由图可得：最大值⎪⎩⎪⎨⎧==+35121x x x ， 所以⎪⎩⎪⎨⎧==2 3 21x x max Z = 8. 12 12125.max 2328416412 0,1,2maxZ .j Z x x x x x x x j =+⎧+≤⎪ ≤⎪⎨ ≤⎪⎪≥=⎩如图所示，在（4，2）这一点达到最大值为2 6将线性规划模型化成标准形式： Min z=x 1-2x 2+3x 3 ⎪⎪⎩⎪⎪ ⎨⎧≥≥-=++-≥+-≤++无约束 321 321321321,0,05232 7x x x x x x x x x x x x 解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中 x 3’≥0,x 3’’≥0 Max z ’=-x 1+2x 2-3x 3’+3x 3’’ ⎪⎪⎩⎪⎪ ⎨ ⎧≥≥≥≥≥≥-=++-=--+-=+-++0 ,0,0'',0',0,05 232 '''7'''543321 3215332143321x x x x x x x x x x x x x x x x x x x《运筹学》试题及答案(二)
运筹学试题参考答案
运筹学_第1章_线性规划习题
运筹学试题及答案
运筹学试题及答案
运筹学线性规划习题有参考解答
《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案
运筹学习题解答(chap1 线性规划及单纯形法)
《运筹学》试题及答案(三)
2020年运筹学考试复习题及答案
《运筹学》 习题 线性规划部分练习题及 答案
最全运筹学习题及答案
《运筹学》试题及答案大全(三)
运筹学课后习题答案 .
相关主题
文本预览