系统工程与运筹学2.ppt

第四章 静态线性最优化模型 第一节 最优化及最优化模型的建立 典型应用： 下料问题：合理利用线材问题； 配料问题：在原料供应量的限制下如何获取最大利润； 投资问题；从投资项目中选取方案，使投资回报最大； 产品生产计划：合理利用人力、物力、财力等，使获利最大； 劳动力安排：用最少的劳动力来满足工作的需要； 运输问题：如何制定调运方案，使总运费最小； ………… 例：生产计划模型 某工厂生产甲、乙两种产品，两种产品分别由两道工序，即由机床A和机床B加工，每件产品的加工时间如下表所示。在一定时间内，两台机床可利用的时间：机床A为1000小时，机床B为600小时。生产产品甲每件利润250元，生产产品乙每件利润500元。 例：合理配料模型 用三种原料A1、A2、A3配制一种食品，要求该食品中蛋白质、脂肪、碳水化合物和维生素的含量分别不低于150、200、250、300个单位，这三种原料的单价及每单位原料所含各种成份的数量如表所示。问如何配制这种食品，使成本最低? 例：货物运输模型 某建筑公司有三个搅拌站，砼生产能力分别为700吨、400吨、900吨，准备向四个建筑工地供应砼，各工地的需要量为300吨、600吨、500吨、600吨，各供应站向各工地调运砼的单位运价见表，现制定调运计划使运输费用最省。 例：任务分配模型 设有四件工作A、B、C、D，要分配给四个人甲、乙、丙、丁去做。每个人的工作效率不同，希望每件工作都由最合适的人员去做。每个人做每件工作的效率如下表所示，规定一个人只分配做一件工作。问如何分配才能使总的工作效率最大? P159 某队有n名工人，现准备从事n项工作，每种工作只能由一个人承担，每人只能承担一项工作。当不同的人从事各种工作的效益不同时，如何分配人员，才能使全队总收益最大。 建立目标函数及约束条件应注意的问题： 1、目标的选择： 深刻理解指标的内涵； 合理处理主要指标和次要指标的关系； 注意量纲和数量级； 尽量采用综合指标； 注意处理线性与非线性目标函数的关系。 建立目标函数及约束条件应注意的问题： 2、约束条件的确定： 依据系统目标研究约束条件； 尽量减少无用约束数量； 注意结构性约束； 避免矛盾约束； 综合考虑目标与约束条件的关系。 线性规划一般形式 目标函数 Max(Min) Z=c1x1+c2x2+……+cnxn 约束条件 a11x1+a12x2+……+a1nxn≤(＝≥) b1 a21x1+a22x2+……+a2nxn≤(＝≥) b2 … … … … … … am1x1+am2x2+……+amnxn≤(＝≥) bm xi 非负约束 第二节 标准型与图解法 一、标准型及标准型的矩阵表示 　　 二、化任一线性规划模型为标准型 1、变量非负 2、资源向量b 3、技术约束条件 4、目标函数 三、线性规划的图解法 四、线性规划解的定理 1、定义： (1) 可行解。 凡满足约束条件AX = b，X ≥ 0的解称为可行解。 (2) 可行域。 可行解的集合称为可行区域。 (3) 基矩阵。 约束条件AX=b中，A是m×n阶矩阵（m ≤ n），它的秩为m，选其中任意m列所形成的非奇异m×m子矩阵B，称为基矩阵。 (4) 基 解。 AX = b中，令不与基矩阵B的列相对应的（n－m）个变量为零，所形成的方程组为基方程组，变量为基变量，所得的解称为基矩阵B的基解，即BX = b的解。 (5) 基可行解。 凡满足非负条件的基解为基可行解。 (6) 退化解。 基解中有一个或多于一个基变量为零时，这个解称为退化基解，否则为非退化解。 (7) 退化基可行解。 若基可行解中有一个或多于一个基变量为零时，这个解称为退化基可行解。 (8) 最优解。 使目标函数Z达到最大值的基可行解叫最优解。 2、解的存在定理 对应于线性规划标准型，若存在可行解，则必存在一个基可行解；若存在一个最优可行解，则必存在一个最优基可行解。 五、线性规划解的几种情况 （1）唯一最优解； （2）多穷多个最优解； （3）无可行解； （4）没有有限最优解。 第三节 单纯形法 一、高斯消元法与旋转变换 例： x1 +2x2 +3x3 =6 （1） 2x1 +3x2 + x3 = -1 （2） 3x1 + x2 + 2x3 = 7 （3） 高斯消元法：由初等线性变换可知，把一个线性方程组中的任何一个方程Et，乘以一个不为零的常数k，方程组的另一个方程Ei用（Ei+kEt）代替后，所得的方程组与原方程组同解。 二、单纯形法 1、基本思想：根据线性规划的标准型，从可行域