内容提要 如何建立一个简单的线性规划模型 线性规划模.ppt

《内容提要 如何建立一个简单的线性规划模型 线性规划模.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、内容提要如何建立一个简单的线性规划模型线性规划模型的图解法单纯形法求线性规划模型的方法改进的单纯形法对偶问题的相关概念案例线性规划问题的单纯形解法的基本原理第2章线性规划2.1线性规划及其数学模型2.1.1案例例2.1某厂拟生产甲、乙两种适销产品，每件利润分别是300元和500元。甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、乙产品的部件分别需要A、B车间的生产能力1工时和2工时；两种产品的部件最后都要在C车间装配，装配每件甲、乙产品分别需要3工时和4工时。A、B、C三个车间每天可用于生产这两种产品的工时分别是8、12、36。应如何安排生产这两种产品

2、才能获利最大？2.1线性规划及其数学模型解设、分别是甲产品和乙产品的日产量，z为这两种产品每天总的利润。首先列出该问题的数据，如表2.1所示。表2.1例2.1数据表产品车间单耗/（工时/件）生产能力/（工时/天）甲乙x1x2ABC10023481236利润/（百元/件）352.1线性规划及其数学模型根据题意，建立模型如下：其中，max是英文maximize（最大化）的缩写2.1线性规划及其数学模型例2.2有A、B、C三个工地，每天A工地需要水泥17百袋，B工地需要用水泥1800袋，C工地需要水泥1500袋。为此，甲、乙两个水泥厂每天生产2300袋水泥和2700袋水泥专门供

3、应三个工地。两个水泥厂至工地的单位运价如表2.2所示。问：如何组织调运使总运费最省。2.1线性规划及其数学模型表2.2水泥厂至工地运价千元/百袋工地水泥厂ABC甲11.52乙2422.1线性规划及其数学模型解设xij为甲、乙两个水泥厂分别运到A、B、C三个水泥厂的水泥袋数，则可以做出如表2.3所示的数据表。表2.3例2.2数据表工地水泥厂ABC供应量/百袋甲x11x12x1323乙x21x22x2327需求量/百袋171815502.1线性规划及其数学模型由题意容易得到如下数学模型：其中，min是英文minimize（最小化）的缩写。2.1.2线性规划的一般模型一般线性规

4、划模型可以表示如下：（2-1）（2-2）2.1.2线性规划的一般模型建立一个实用的线性规划模型必须明确以下四个组成部分的含义：第一，决策变量。决策变量是模型中的可控而未知的因素，经常使用带不同下标的英文字母表示不同的变量，如式（2-2）中的xj。第二，目标函数。线性规划模型的目标是求系统目标的极值，可以是求极大值，如企业的利润和效率等，也可以是求极小值，如成本和费用等。式（2-1）即为最优化目标函数，简称目标函数。式中opt即optimize（最优化）的缩写，根据问题要求不同，可以表示为max（最大化）或min（最小化）。2.1.2线性规划的一般模型第三，约束条件。约束条

5、件是指实现系统目标的限制性因素，通常表现为生产力约束、原材料约束、能源约束、库存约束等资源性约束，也有可能表现为指标约束和需求约束，如式（2-2）中的前m个式子。第四，非负限制。由于在生产实际问题中，资源总是代表一些可以计量的实物或人力，因而一般不能是负数，如式（2-2）中的最后一个式子。2.2线性规划的图解法例2.3用图解法求例2.1中的线性规划模型的解，如图2.1所示。x2963O(0,0)z04z15812z303x14x236A(8,0)E(12,0)Z42RD(0,6)C(4,6)F(8,6)2x212x1B(8,3)G(0,9)Z法向x18图2

6、.1例2.3图2.2线性规划的图解法解首先，根据所有约束条件共同构成的图形是可行域图形。具体方法为：在Ox1x2平面直角坐标系中，由于x1≥0，x2≥0，所以指的是在第一象限；画出直线3x14x236，定出约束条件3x14x2≤36表示的区域；2.2线性规划的图解法为了找到3x14x2＜36的半平面，只要在某个半平面上找到一点，把该点的坐标代入不等式，若满足不等式，则该点所在半平面为所求，否则为另一半平面3x14x2＞36。为了计算简单起见，一般选取原点（0,0）代入不等式，因把原点坐标代入时能满足不等式3040＜36，所以原点所在半平面满足不等式，于是约

7、束条件3x14x2≤36代表含原点的半平面及直线3x14x236本身。2.2线性规划的图解法画出直线2x212，定出2x2≤12的平面。由于原点满足不等式2x2＜12，所以2x2≤12为含直线2x212在内的下半平面。画出直线x18，定出x1≤8的半平面，由于原点满足该不等式，所以x1≤8表示含原点在内的左半平面及直线x18本身。本模型的可行域图形如图2.1阴影部分所示，即标识为R的部分。2.2线性规划的图解法其次，画出目标函数z3x15x2的等值线。本模型的目标函数代表以z为参数的一簇平行线，由小到大适当地