实验6最优问题求解实验

《实验6最优问题求解实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、6．线形规划最优问题求解实验6.1实验目的本实验通过具体问题介绍一些线性最优问题的求解，同时介绍线性规划问题的图解法、软件解法以及当线性规划问题规模较小，并且存在最优解时的理论解法。6.2实验内容线性规划(LinearProgramming)是运筹学的一个重要分支，在科学实践中有着广泛的应用，不仅许多实际课题属于线性规划问题，而且运筹学其它分支中的一些问题也可转化为线性规划问题来计算，因此，线性规划在最优化学科中占有重要地位。本实验通过具体问题介绍线性规划的一些基本概念和性质，给出求解线性规划问题的图解法和软件解法以及当线性规划问题规模较小，并且存在最优解时

2、的理论解法。6.2.1实验问题问题1（生产计划问题）某工厂生产条件如表6-1所示：表6-1　生产条件车间　123生产单位甲产品需工时521生产单位乙产品需工时235一周可用工时170100150生产每一件产品的工序必须经过三个车间，生产单位甲产品工厂获利10元，生产单位乙产品工厂获利18元。问厂方如何安排生产才能使每周获得的利润最大？问题2（运输问题）某产品的产地、产量、需地、需求量、单位产品运输费用如表6-2所示：表6-2　单位产品运费产地产量需地1234需量30605060Ⅰ70运输费311310Ⅱ401929Ⅲ90741015问如何安排运输才能使运费最

3、少？问题3（人员安排问题）15为了城市居民和流动人口的安全，西安市110警察大队要求每天各个时间段都有一定数量的警员值班，随时处理突发事件的发生，由于精力高度集中每人上班时间是连续6小时，中间不休息。下表6-3是一天8个班次所需值班警员的人数情况统计，问：在不考虑时间段中间有警员上班和下班的情况下，西安市110警察大队至少需要多少警员才能满足值班需要？表6-3班次时间段人数班次时间段人数16:00∽9:0070518:00∽21:008029:00∽12:0080621:00∽24:00100312:00∽15:0065724:00∽3:00120415:0

4、0∽18:009083:00∽6:0090问题4（任务分配问题）某车间有甲、乙、丙三台车床可用于加工三种零件，这三台车床可用于工作的最多时间分别为700小时、800小时和900小时，需要加工的三种零件的数量分别为300、400和500，不同车床加工不同的零件所用的时间数和费用如下表6-4所示，问：在完成任务的前提条件下，如何分配加工任务才能使得加工费用最低？表6-4车床名称加工单位零件所需时数加工单位零件所需费用可用与工作的时数零件1零件2零件3零件1零件2零件3甲0.60.50.5788700乙0.40.70.5878800丙0.80.40.6798900

5、这里提出的问题虽然内容不同，但其涉及的数学知识具有相似之处，都是在一定的条件下求其最大值或者最小值，并且从下面的建立的数学模型也可看到，这些条件都是线性的。6.2.2建立数学模型问题1的数学模型设甲产品生产数量为，乙产品生产数量为，则工厂获利与变量，之间的关系以及变量应满足的条件可归纳成如下形式：；满足这样该问题就归结为在一定的约束条件下，求，使得最大的约束极值问题。问题2的数学模型设第个产地运往第个需地的数量为，单位运价为，第个产地的产量用表示，，第个需地的需求量用表示，，则总运费为，15约束条件，，，，，，这样该问题就归结为在一定的约束条件下，求，使得最

6、小的约束极值问题。问题3的数学模型可设第个班次开始上班的警员数为，那么根据题意可得下面的数学模型：，问题4的数学模型可设分配给车床甲加工三种零件的数量分别为，分配给车床乙加工三种零件的数量分别为，分配给车床丙加工三种零件的数量分别为，则根据问题的实际要求可得下面的数学模型：，上述四例具体意义虽不尽相同，但从数学模型来看，却有共同的特点：求一组非负变量，使得关于这组变量的线性函数在一定的约束条件（关于变量的线性等式或者不等式）下取得最大值或者最小值。我们可把这类问题用下面一般的数学模型表示：15，这类问题通常称为线性规划问题，常常简记为LP问题。也可以写成下面

7、的矩阵形式：，（6-1）这里为约束矩阵，为价值向量（赋权向量），一组非负变量通常称为决策变量，关于这组决策变量的线性函数通常称为目标函数。通常在解线性规划问题时都是先将它的一般形式化成下面的标准形式：，也可以写成下面的矩阵形式：，（6-2）将一般线性规划问题化成标准形式的线性规划问题，分下面三步完成。(1)目标函数的转换：标准形式的线性规划问题是求目标函数的最大值，如果实际问题要求目标函数的最小值，则可通过给目标函数乘以-1来转换。(2)约束条件的转换：标准形式线性规划问题的约束条件是一些线性等式，如果实际问题给出的约束条件是线性不等式，则可通过引入松驰变量

8、，将不等式化为等式这里也称为剩余变量。(3)15变量