第八章-线性规划初步课件.ppt

1、第八章第八章 线性规划初步线性规划初步线性规划作为运筹学的一个重要分支，它从上世纪40年代末期开始发展，虽然只有短暂的几十年时间，但在生产组织管理，交通运输，国防工业以及国民经济的许多领域内，都有着广泛而重要的应用它常用于解决在现有的资源和利用方式下，在现有的人力，物力，财力的条件下，怎样更有效地发挥其作用以达到最大的经济效益；或者是如何利用最少的人力，物力，财力去完成预定的任务一般说来，它是研究有限资源的最优配置，以实现给定的目的，取得最有经济效益的一门学科第八章第八章 线性规划初步线性规划初步8.1 线性规则问题的数学模型8.2 线性规则的图解法8.3 线性规则问题的标准型8.4 单纯形方

2、法8.1 线性规则问题的数学模型8.1.1 实例8.1 线性规则问题的数学模型8.1 线性规则问题的数学模型8.1.2 线性规则的一般模型8.1 线性规则问题的数学模型 建立一个实用的线性规划模型必须明确以下四个组成部分的含义：1决策变量：决策变量是模型中可控而未知的因素，经常使用带不同下标的英文字母表示不同的变量 2目标函数：线性规划模型的目标是求系统目标的极值，可以是求极大值，如企业的利润和效率等，也可以是求极小值，如成本和费用等 3约束条件：约束条件是指实现系统目标的限制性因素，通常表现为生产力约束、原材料约束、能源约束、库存约束等资源性约束，也可能表现为指标约束和需求约束 4非负限制：

3、由于在实际生产问题中，资源总是代表一些可以计量的实物或人力，因而一般不能为负数8.2 线性规则的图解法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示其有关概念，并求解8.2 线性规则的图解法8.2 线性规则的图解法 图解法只能适用于仅含有两个变量的线性规划问题的求解，因而图解法的实际用途并不广泛但是，通过图解法可以得到以下结论：1线性规划的可行域为凸集，即集合中任意两点连线上的一切点仍然在该集合中这样的凸集平面几何上表现为一个凸多边形，在空间上必将是一个凸几何体 2线性规划的最优解在凸集的某一个顶点上达到（存在凸集的某一条边界上达到的可能性）3线性规划的可行域若有界，则一

4、定有最优解 线性规划的最优解不可能在可行域的内点取得，而只能在凸集的某一个顶点上达到（特殊情况为在凸集的某一条边界上达到）由于可行域的顶点个数是有限的，所以在求解线性规划模型的最优解时，只要在可行域的有限个顶点范围内一一寻找.8.3 线性规则问题的标准型8.3.1 线性规则问题标准型8.3 线性规则问题的标准型线性规划问题的标准型的四个特点：线性规划问题的标准型的四个特点：1目标函数为最大化型；目标函数为最大化型；2所有约束条件均为所有约束条件均为“=”型；型；3决策变量均为非负的；决策变量均为非负的；4各约束条件右端向量非负各约束条件右端向量非负8.3 线性规则问题的标准型8.3.2 线性规则问题标准型8.4 单纯形方法8.4 单纯形方法8.4 单纯形方法8.4 单纯形方法8.4 单纯形方法8.4 单纯形方法8.4 单纯形方法8.4 单纯形方法8.4 单纯形方法8.4 单纯形方法8.4 单纯形方法