《运筹学 第四版 第二章 线性规划及单纯形法》由会员分享，可在线阅读，更多相关《运筹学 第四版 第二章 线性规划及单纯形法（249页珍藏版）》请在金锄头文库上搜索。
1、线性规划及 单纯形法,线性规划及单纯形法,线性规划问题及其数学模型 图解法 单纯形法原理 单纯形法的计算步骤,第一节 线性规划问题及其数学模型,一、问题的提出,线性规划主要解决：如何利用现有有限的资源，使得预期目标达到最优的问题。,例1 某工厂在计划期内要安排生产A、B两种产品（假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表1.1所示问该厂应如何安排生产使获利最大？,表1-1,问题要求给出一个方案(产品A生产多少；产品B生产多少),设该工厂生产A、B两种产品产量分别为,确定决策变量,表1-1,制定方案的目标是什么？,该厂获取的利润可表示为,问题的目标：,确定
2、目标函数,利润最大化,表1-1,方案的制定受到那些现实条件制约：,人力资源（劳动力）的限制：,设备工时的限制：,原材料资源的限制：,此外，决策变量的取值不应为负值即,确定约束条件,其中,目标函数,约束条件,资源约束,非负约束,约束条件可记 s.t (subject to), 意思为“以,为条件“、”假定“、”满足“之意。,综上所述，我们得到了这个问题的数学模型,建立问题的线性规划模型步骤,1 确定决策变量 决策变量是模型所要决定的未知量，也是模型最重要的参数 它用以表明规划中的用数量表示的方案、措施，可由决策者 决定和控制,2 确定目标函数 就是将决策者所追求的目标表示为决策变量的函数 它决定
3、了线性规划优化的方向，是线性规划的重要组成部分,3 确定约束条件 这些约束条件可用含有决策变量的等式或不等式来表示,例2 给海狸鼠配饲料 饲料中营养要求：Va每天至少700克，Vb每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：,问：应如何搭配饲料，使费用最小？,确定决策变量：设抓取饲料I x1kg;饲料II x2kg;饲料III x3kg确定目标函数：minZ=2x1+7x2+4x3+9x4+5x5确定约束条件：3x1+2x2+x3+6x4+18x5 700x1+0.5x2+0.2x3+2x4+0.5x5 300.5x1+x2+0.2x3+2x4+0.8x5 =
4、200x1 50,x2 60,x3 50,x4 70,x5 40x1 0,x2 0,x3 0,x4 0,x5 0,营养要求,用量要求,非负约束,综上所述，便得到如下的数学模型：,美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-2所示。问该公司应制造两种家电各多少件，使获取的利润最大？,课堂练习,表1-2,其数学模型为：,例3：捷运公司在下一年度的14月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1-3。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-4。租借仓库的合
5、同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。,表1-3,表1-4,单位：100m2,单位；元/100m2,表1-2,表1-3,单位：100m2,单位；元/100m2,解：设 表示捷运公司在第i (i=1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。,15,10,20,12,经过上面的讨论，得到下面的LP模型：,目标函数,约束条件,每一个问题都有一组变量-称为决策变量
6、，一般记为,下面从数学的角度来归纳上述三个例子的共同点。, 每个问题中都有决策变量需满足的一组约束条件-线性的等式或不等式。,对决策变量每一组值：,代表了,一种决策方案。通常要求决策变量取值非负，即,二。线性规划问题的数学模型, 都有一个关于决策变量的线性函数-称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。,我们将约束条件和目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linear programming)其数学模型为：,上述模型的简写形式为：,若令,线性规划问题可记为矩阵和向量的形式：,用向量表示时，上述模型可写为：,三。线性规划问
7、题的标准形式：,LP问题的数学模型的标准形式为：,其中常数项,LP问题标准形式的特征是：, 求目标函数的最大值； 约束条件为等式； 决策变量非负。,下面分析如何将LP问题标准化：, 若目标函数为,引进新的目标函数,则,的最小值即为,的最大值，即：,从而目标函数变换为：,（2）若约束条件为不等式，分为两种情况讨论：,加入松弛变量,加入剩余变量,（3）对于决策变量非负的要求，分为两种情况讨论： 非正变量：即xk 0 令xk= -xk即可 自由变量：即xk无约束令xk = xkxk,例1 将LP问题,化为标准形。,解：引进新的目标函数,于是原LP问题化为标准形式：,例2 将LP问题,化为标准形。,松
8、弛变量,例3 将LP问题,化为标准形。,剩余变量,例4 将LP问题,化为标准形。,课堂练习,例4 将LP问题,化为标准形。,我们得到例4的标准形为：,1.2 线性规划问 题的图解法,1. 2线性规划图解法,所谓图解法，就是在平面直角坐标上画出各个约束条件所允许变化的范围，通过图上作业法求出最优解和目标函数值。,一个线性规划问题有解，是指能找出一组xj(j=1,2,n),满足所有约束条件，称这组xj为问题的可行解。,通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域。 在用图解法求解时，可形象的看到可行域。 在可行域中使目标函数值达到最优的可行解称为最优解,对不存在可行解的线性规划问
9、题，称该问题无解,图解法背景知识,图解法背景知识,由中学知识可知：y=ax+b是一条直线。 同理(如果Z值固定) Z=70x1+120x2,x2= -70/120x1 + Z/120也是一条直线,x2= -70/120x1 + Z/120也是一组平行的等值线,1.2.1图解法的步骤,1、建立直角坐标系； 2、根据约束条件描绘可行域； 3、作目标函数的等高线； 4、求解最优点和最优目标函数值。,例题1生产计划问题,某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,问题：如何安排生产计划，使得获利最多？,例1 图解法,.,90 80 60 40 20,0
10、 20 40 60 80 100,x1,x2,9x1+4x2 360,4x1+5x2 200,3x1+10x2 300,Z=70x1+120x2,maxZ=70X1+120X29X1+4X23604X1+5X2 2003X1+10X2 300X10 X20,最优解(20,24),Z=4280,可行域,课堂练习,用图解法求解下述线性规划问题。,1）,2）,3）,答案：,1）,2）,3）,x1=1, x2=1.5 Z*=17.5,x1=15/4, x2=3/4 Z*=33/4,x1=2, x2=6 Z*=36,1.2.2求解的几种可能结局,1、无穷多最优解。 2、唯一最优解。 2、无界解。 3、无
11、解或无可行解。,解的可能性,多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。 唯一最优解：只有一个最优点。,解的可能性,无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）,解的可能性,无可行解：若约束条件相互矛盾，则可行域为空集,由图解法得到的启示,图解法虽然只能用来求解只具有两个变量的线性规划问题，但它的求解思路和几何上直观得到的一些概念判断，对于单纯形法有很大启示,1、求解线性规划问题时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行解,2、若线性规划问题的可行解存在，则可行域是一个凸集,3、若线性规划问题的最优
12、解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。,由图解法得到的启示,4、解题思路是： 先找出凸集的任一顶点，计算在顶点处的目标函数值。比 较周围相邻顶点的目标函数值是否比这个值大，如果为 否，则该顶点就是最优解的点或最优解的点之一；否则转 到比这个点的目标函数值更大的另一个顶点，重复上述过 程，一直到找出使目标函数值达到最大的顶点为止。,1.3 单纯形法 原 理,数学试验,LINDO软件包,LINDO软件包介绍,初试LINDO 用LINDO求解整数规划 注意事项,LINDO是一种专门用于求解数学规划问题的优化计算软件 包,版权现在由美国 LINDO系统公司(Lindo System
13、 Inc.) 所拥有.LINDO软件包的特点是程序执行速度很快,易于输 入、修改、求解和分析一个数学规划(优化问题),因此 LINDO在教育、科研和工业界得到广泛应用.有关该软件的 发行版 本、发行价格和其他最新信息都可以从LINDO系统公 司的INTERNET 网络站点http: /www. lindo. com获取, 该站 点还提供部分LINDO软件的演示版本或测试版本学生版和演 示版与发行版的主要区别在于对优化问题的规模(变量和约束 数) 有不同的限制.,LINDO是Linear Interactive and Discrete Optimizer 字首的缩 写形式,可以用来求解线性规划
14、(LP-Linear Programming )、 整数规划( IP -Integer Programming )和 二次规划(QP- Quadratic Programming )问题.LINDO学生版可求解多达 200 个变量和100个约束的规划问题.,初试 LINDO,如解如下LP 问题 :,LINDO 中己假设所有的变量都是非负的,所以非负约束条件不 必再输入到计算机中;LINDO 也不区分变量中的大小写字符 (实际上任何小写字符都将被转换为大写字符);约束条件中的 “=” 可用“” 代替.上述问题用键盘输入如下 :,：MAX 2X+3Y ? ST,( 说明:也可写成S.T., SUC
15、H THAT 或 SUBJECT TO 等）,? 4X+3Y10 ? 3X+5Y12 ? END：,注：目标函数为第1行,两个约束条件分别为第2,3行.,直接键入运行命令(GO) 就可得到解答,屏幕显示如下:,:GO LP OPTIMUM FOUND AT STEP 2OBJECTIVE FUNCTION VALUE 1 ） 7.4545450 VARIABLE VALUE REDUCED COST X 1.272727 .000000 Y 1.636364 .000000 ROW SLACK OR SURPLUS DUAL PRICES .000000 .090909 .000000 .545455 NO.ITERATIDNS=2 DO RANGE (SENSITIVITY)ANALYSIS ?,
