第1章 线性规划.doc

第1章 线性规划 判断下列说法是否正确：01100011图解法同单纯形法虽然求解的形式不同，但从几何意义上理解，两者是一致的。01100021线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件 ，可行域的范围一般将扩大。01100031线性规划问题的每一个基解对应可行域的一个顶点。01100041如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。01100051单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少又一个基变量的值为负。01100061单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数值得到最快的增长。01100071一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。01100081线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。01100091对一个有n个变量、m个约束条件的标准型的线性规划问题，其可行域的顶点恰好为个。01100101若，分别是某一线性规划问题的最优解，则也是该线性规划问题的最优解，其中为正的实数。01100111 线性规划的所有可行解的集合试凸集，线性规划的最优解是否凸集简答题：01200011、用图解法求解线性规划对我们有什么启示？01200021、试述用单纯形法解线性规划模型的步骤01200031有的书上规定线性规划标准形式的目标函数是求极小值，还有的书上定义检验数为。试述这种不同规格定下的检验数最优解的判别法。01200041 对取值无约束的变量，通常令，其中，在用单纯形法求得的基可行解中是否有可能同时出现？01200051在单纯形迭代中，任何从基变量中替换出来的变量，在紧接着的下一次迭代中，会不会在进入基变量中？为什么？01200061判断下列说法是否正确？为什么？ a （1）在单纯形法迭代中，任何从基变量中替换出来的变量在紧接着的下一次迭代中可能会再进入基变量（2）在一次迭代中刚进入基变量的变量在紧接着的下一次迭代中可能会立即被替换出来。01200071为什么一个基本可行解的非零分量所对应的列向量一定线性无关？对一个非基本的可行解，它的非零分量所对应的列向量一定线性相关?为什么？01301011、填空并回答问题 （ ） （ ） （ ） （ ） （ ） b46 ( ) ( ) 1 1/2 0 2 -1 0 1/2 1 -1 1 2030-Z 0 -3 0 -2 -2 -260（1） 基变量：（2） 基B=（3） 目标数：（4） 此时问题的解X=（5） X是否为最优解？请说明之。标准化01302011将下列线性规划模型化为标准型。 01302021将下列线性规划模型化为标准型。 01302031将下列线性规划模型化为标准型。 01302041 将下列问题转化为标准形式 无符号限制 01302051将下列问题转化为标准形式 无符号限制 一般单纯形法求解01303011用单纯形法求解下列线性规划问题。 01303021用单纯形法求解下列线性规划问题。01303031用单纯形法求解下列线性规划问题 01303041用单纯形法求解下列线性规划问题01303051用单纯形法求解下列线性规划问题 01303061用单纯形法求解下列线性规划问题 01303071用单纯形法求解下列线性规划问题 01303081用单纯形法求解下列线性规划问题 01303091用单纯形方法求下列线性规划问题：01303101用单纯形方法求下列线性规划问题：a01303111用单纯形方法求下列线性规划问题：a01303121 将下列线性规划问题化为标准形式，并列出初始单纯形表。 无约束， 01303131 用单纯形法解01303141用单纯形法解01303151 用单纯形法解01303161用单纯形法解01303171单纯形方法解下列线性规划问题： a大M法、二阶段法01304012用大M法或二阶段法求解下列线性规划问题。 01304022用大M法或二阶段法求解下列线性规划问题 01304032用大M法或二阶段法求解下列线性规划问题 013040142用大M法或二阶段法求解下列线性规划问题 01304052用大M法或二阶段法求解下列线性规划问题 01304062用大M法或二阶段法求解下列线性规划问题 01304072用大M法或二阶段法求解下列线性规划问题 01304082用大M法或二阶段法求解下列线性规划问题01304092用大M法求解下列问题。 01304102用大M法求解下列问题。01304112设有线性规划问题用大M法证明最优解中包含一个取值为零的人工变量，因而推断出存在最优解01304122用两阶段法求解。01304132 设有线性规划问题用两阶段法求解01305011用单纯形法求解如下线性规划并判定解的类型 01305021将线性规划问题： （1） 以为基变量列出单纯形表；（2） 用单纯形表求最优解01305031设有线性规划问题 用单纯形法求解，并说明最优解是否退化？ 01305042 用作为初始基本可行解来解下面的问题01305052 用单纯形法求解如下问题，并说明有几个最优解。 01305062用单纯形法求解如下问题，并说明有几个最优解01305072找出下列线性规划问题的基本解、基本可行解及最优解： 01305081 找出如下线性规划问题的所有基本解，基本可行解，并确定最优解。 01305092设有线性规划问题 确定：（1）基本解的最大个数 （2）可行的极点。（3）最优基本可行解和最优目标函数值01305102 设有线性规划问题设R是第二个约束条件的一个人工变量。用和R作为一个初始基本解来解决这个问题。01305112 设有线性规划问题用作为初始基变量来求最优解 01305122 分别用单纯形法和图解法求解下述线性规划问题，并对照指出单纯形表中的基可行解对应图解法中的可行域的哪一个顶点？ 01305132设有线性规划问题 （1） 由观察写出初始基本可行解。（2） 使和 为零，使非基变量增大为1，试求：可行解及目标函数净改变是多少？（3） 在约束条件限制下，可能的极大增加量是多少？（4） 当增加至（3）中的极大植时，求出新的基本可行解。（5） 在（4）中求得的基本可行解是否最优？为什么？01305142 某线性规划的初始表和迭代后的表格如下： a -1 -2 0 0 b b c d 1 0 -1 3 e 0 161 g 2 -1 1/2 0f h i 1 1/2 1 4 0 -7 j k L9求a,b,c,d,e,f,g,h,I,j,k,l的值。建立数学模型01306012 某厂在今后四个月内需要租用仓库堆放物资。已知各月份所需仓库面积数字列于下表1。仓库租借费用随合同期限，限期越大折扣越大，具体数字见表2。租用仓库的合同每月初都可以办理，每份合同具体规定租用面积数和期限。因此该厂可以根据需要，在任何一个月办理租用手续。每次办理时可以签一份，也可以签若干份租用面积和租用期限不同的合同。总目标是使所付租金最少。试建立此问题的线性规划模型。表1月份1 2 3 4所需仓库面积/10015 10 20 12表2合同租用期限1个月 2个月 3个月 4个月合同期内的租金/（元. ）2800 4500 6000 7300 01306023 某厂生长甲，乙，丙三中产品，都分别经A,B两道工序加工。设A工序可以分别在设备或上完成，有，三种设备可以用于完成B工序。已知产品甲可以在A,B任何一种设备上加工；产品乙可在任何规格的A设备上加工，但完成工序B时，只能在设备上加工；产品丙只能在与设备上加工。加工单位产品所需要工序时间及其他各项数据见下表。试安排最优生产计划，使该厂获利最大。要求建立数学模型。设备产品甲 乙 丙设备有效台时设备加工费（元/小时）5 106000 0.057 9 1210000 0.036 8 40000.064 1170000.117 40000.05原料费/(元/件)0.25 0.35 0.50售价/（元/件）1.25 2.00 2.8001306031有两个煤厂A ,B，每月进煤分别不少于80吨，100吨。它们负担供应三个居民区的用煤任务，这三个居民区每月需用的煤分别为55吨，75吨和50吨。A场离这三个居民区分别为10千米，5千米和6千米。B场离这三个居民区分别为4千米，8千米和15千米。问这两个煤厂应如何把煤供应到三个居民区，才能使运输的吨.千米最小。 01306041某钢厂的两个炼钢炉同时各用一种方法炼钢。第一种炼法每炉要用a小时，耗费燃料m元；第二种炼法每炉要用b小时，耗费燃料n元；假定这两种炼法每炉都是出钢k吨，现在要在c小时内炼出的钢不少于d吨，问应该怎样分配这两种炼法才能使燃料费用最少。 01306053 某饭店日夜服务，一天24小时中所需的服务员人数如表所示时间所需服务员的最少人数时间所需服务员的最少人数2641418761081822121014102224 每个服务员每天连续工作8小时。现在目标使求出满足以上条件的最少人数，把这个问题表示成一个线性规划模型。01306061 假定某造纸厂接到三分定购卷纸的订单，其长和宽的要求如下表所示订单号码宽（米） 长（米）10.5100020.7300030.92000该厂生产l米和2米两种标准宽度的卷纸。假定卷纸的长度无限制，即可以连续起来达到所需要的长度，问应如何切割才能使切割损失的面积最小。设是第i种标准卷纸按照第j种方式切割的长度。说明目标函数可以写成下面的形式： 01306073 某商店要制定明年第一季度某种商品的进货和销售计划。已知该店的仓库容量最多可储存该种商品500件，而今年年底有200件存货。该店在每月月初进货一次。已知各个月份进货和销售该种商品的单价如表所示。 月 份 1 2 3 进货单价(元) 8 6 9 销售单价(元) 9 8 10 现在要确定每个月应该进货和销售多少件，才能使总利润最大，把这个问题表达成一个线性规划模型。 01306082一种产品包含三个部件，它们是由四个车间生产的，每个车间的生产小时总数是有限的。下表中给出三个部件的生产效率，目标是要确定每个车间应该把多少公式分配到各个部件上，才能使完成的产品件数最多。把这个问题表示成一个线性规划问题。设备产品甲 乙 丙设备有效台时设备加工费（元/小时）5 106000 0.057 9 1210000 0.036 8 40000.064 1170000.117 40000.05原料费/(元/件)0.25 0.35 0.50售价/（元/件）1.25 2.00 2.80 01306092 一个投资者打算把它的100 000元进行投资，有两种投资方案可供选择。第一种投资保证每l元投资一年后可赚7角钱。第二种投资保证每1元投资两年后可赚2元。但对第二种投资，辑资时间必须是两年的倍数才行。为了使投资者在第三年年底赚到最多，他应该怎样投资?把这个问题表示成一个线性规划问题。01306102 有A、B两种产品，都需要经过前后两道化学反应过程。每一个单位的A产品需要前道过程2小时和后道过程3小时。每一个单位的B产品需要前道过程3小时和后道过程4小时。可供利用的前道过程时间有16小时，后道过程时间有24小时。 每生产一个单位的B产品的同时，会产生两个单位的副产品C，且不需要外加任何费用。副产品C最多可售出5个单位，其余的只能加以销毁，每个单位的销毁费用是2元。 出售A产品每单位可获利4元，B产品每单位可获利10元，而出售副产品C每单位可获利3元。为了使获得的总利润达到最大，试建立这个问题的线性规划模型01306111某昼夜服务的公交线路每天各时间段所需司机和乘客人员数如表所示：班 次时 间所需人数16：0010：0060210：0014：0070314：0018：0060418：0022：0050522：002：002062：006：0030设司机和乘务员分别在各时间段一开始时上班，并连续工作八小时，问该公车线路至少配备多少司机和乘务人员，列出这个问题的线性规划模型。01306121、某房产公司有水泥100单位，木材160 单位和玻璃400单位，用以建造A型和B型住宅，建一栋A型住宅需要水泥、木材、玻璃分别为1，2，2单位，售价每栋100万元；建一栋B型住宅需要水泥、木材、玻璃分别为1，1，5单位，售价每栋150万元。该公司如何安排两种住宅的建设，才能使总售价最大?01306131文教用品厂，其经济结构为：产品范围：信封（以盒为单位），公文袋（以捆为单位），便条（以箱为单位）；工人总数：100人；原料情况：每天有30000公斤坯纸；生产定额：每个工人每天单独生产三种产品的任何一种定额都是30单位；消耗定额：1单位信封用坯纸10/3公斤，1单位公文袋用坯纸40/3公斤，1单位便条用坯纸79/3公斤；盈利情况：信封、公文袋、便条的单位利润分别为2元、3元、1元；试根据上述情况建立数学模型。01306142某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工单独完成，或由一个技工和两个力工俩完成。第二项工作可由一个技工或一个力工单独完成。第三项工作可由五个力工组成的小组来完成，或由一个技工领着三个力工俩完成。已知技工和力工每周工资分别为100元和80元，他们每周都工作48小时，但他们每人实际的有效工作小时数为：第一项工作1000小时，第二项工作2000小时，第三项工作3000小时。又能招收到的工人数为技工不超过400人，力工不超过800人。试建立数学模型，确定招收技工和力工各多少，使总的工资支出为最少。01306152某厂生成、三种产品。产品依次经A、B设备加工，产品依次经A、C设备加工，产品依次经C、B设备加工。已知有关数据如下表所示，请为该厂制订一个最优的生产计划。产品机器生产率（件/小时）原料成本（元）产品价格（元）A B C 155010 2025100 20 51045 10 20机器成本（元/小时）200 100 200每周可用小时数 50 45 6001306163某战略轰炸机群奉命摧毁敌人军事目标。已知该目标由四个要害部位，只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为48000升、重型炸弹48枚、轻型炸弹32枚。飞机携带重型炸弹时每升汽油可飞行2千米，带轻型炸弹时每升汽油可飞行3千米。又知每架飞机每次只能转载一枚炸弹，每出发轰炸一次除来回路程汽油消耗（空载时每升汽油可飞行4千米）外，起飞和降落每次各消耗100升。有关数据如下表所示：要害部位离机场距离（千米）摧毁可能性每枚重型弹每枚轻型弹12344504805406000.100.200.150.250.080.160.120.2001307012某 厂用两种原料生产三种成品，工厂现有原料生产，每吨成品所需的原料数量及每吨成品可得利润列表如下： b 每吨成品需原料原料成品现有原料（吨） 2 1 0300 2 450每吨成品可得利润3 2 1/2 问：(1)在现有条件下，应如何组织生产才能使该厂获利最大?(2)如果必须生产成品3吨，又应如何组织生产才能使该厂获利最大?（3）如果只要保证获利50万元以下，可以有哪些生产方式？01307023某饭店准备安排n天所需的餐巾，第 j 天的需要量为。餐巾交洗衣店洗净，正常洗净需p 天后才能送回，加快送洗需q（p）天即可送回；洗餐巾的单位费用分别为b元及c元。若无旧餐巾使用时，则需花a元一条买新餐巾。问如何安排才能使花费最小。建立此问题的线性规划模型。 c01307033设成年人每天的维生素需要量： A为12个单位；B为20个单位。某饮食公司现有甲、乙、丙三种食品材料，都含有这两种维生素，但含量各不相同，食品价格也不相同，其情况如下表。 c 食品材料维生素甲 乙 丙每天需要量A1 3 112B2 1 320单价（元）4 3 8 问：在不影响健康的条件下，应如何选配食品材料，才能使顾客购买饮食制成品所花的钱最省（总的购价最低）？01307042已知：某线性规划问题用单纯形法计算时，得到的初始单纯形表及最终单纯形表（见下表）。请将表中空白处数字填上。 2 -1 1 0 0 0 b000 3 1 1 1 0 01 -1 2 0 1 01 1 -1 0 0 1601020-Z2 -1 1 0 0 0 0: : : 1 -1 -2 0 1/2 1/2 0 -1/2 1/2-Z01307052.某化工厂生产两种产品，已知制造产品一万瓶要用原料：为5千克，为300千克，为12千克，可得利润为8000元。制造一万瓶要用原料：为3千克，为80千克，为4千克，可得利润为3000元。今该厂现有原料为500千克，为20000千克，为900千克，问：在现有条件之下，生产各为多少，才能使该厂获利润最大？01307062某养鸡厂有一万只鸡，用动物饲养和谷物饲料混合喂养。每天每只鸡平均吃混合饲料一斤，其中动物饲料占的比例不得少于1/5。动物饲料每斤0.1元，谷物饲料每斤0.08元。饲料公司每周只保证供应谷物饲料50000斤。问：饲料应怎样混合，才能使成本最低，请建模。01307072某钢筋车间制作一批钢筋（直径相同）：长度3米的90根，长度4米的60根。已知所用的下料钢筋为10米，问怎样下料最省？并建立此问题的线性规划模型。01307082某地区百货公司制定明年某种商品的流通计划。这种商品的季节性很强，各个季度的社会需求量、销售价格都不相同。据市场预测，已知明年各个季度的社会需求量。购进价格、销售价格和贮存一个商品的费用如下表所列。同时，预计明年年初库存为100，仓库最高容量为500。问：应如何确定各个季度的计划进货量、计划销售量、才能使利润额（毛利额减贮存费用）最大？项目季度社会需要量购进价格销售价格贮存一个单位商品的费用第