《数学建模----线性规划及单纯型法》由会员分享，可在线阅读，更多相关《数学建模----线性规划及单纯型法（71页珍藏版）》请在金锄头文库上搜索。
1、数学系-阮周生,线性规划,2011-7-12,目录,一.线性规划问题及其模型 二.线性规划的基本算法单纯形法 三.线性规划数学软件求解 四.线性规划应用举例,线性规划问题的提出线性规划的基本概念线性规划的数学模型,一 线性规划问题及其数学模型,问题的提出,例: 生产计划问题,决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions） 可行域（Feasible region) 最优解（Optimal solution),基本概念,问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定
2、和控制。,它是决策变量的函数,指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。,满足约束条件的决策变量的取值范围,可行域中使目标函数达到最优的决策变量的值,是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,第1步 -确定决策变量,设 I的产量II的产量利润,第2步 -定义目标函数,Max Z = x1 + x2,Max Z = 2 x1 + 3 x2,第2步 -定义目标函数,第3步 -表示约束条件,x1 + 2 x2 8 4 x1 164 x2 12x1、 x2 0,该计划的数学模型,目标函数 Max Z = 2x1 + 3x2约
3、束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0,x1,x2,线性规划问题的共同特征,一组决策变量X表示一个方案,一般X大于等于零。 约束条件是线性等式或不等式。 目标函数是线性的。 求目标函数最大化或最小化,线性规划模型的一般形式,线性规划模型建立步骤,从实际问题中建立数学模型一般有以下三个步骤； 1.根据影响所要达到目的的因素找到决策变量；2.由决策变量和所在达到目的之间的函数关系确定目标函数；3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。,1.线性规划的标准形式：,用单纯法求解时，常将标准形式化为：,2. 线性规划的基本算法单纯形法,二.线性规划的基
4、本算法单纯形法,引入松弛变量x3, x4, x5, 将不等式化为等式, 即单纯形标准形:,显然A的秩ran(A)=3, 任取3个线性无关的列向量,如P3 P4 P5称为 一组基, 记为B. 其余列向量称为非基, 记为N .,于是 f = cBxB + cNxN , Ax = BxB + NxN = b,则 xB = B-1b-B-1NxN , f = cBB-1b + (cN cBB-1N)xN,若可行基进一步满足: cN cBB-1N0, 即: cBB-1N - cN0 则对一切可行解x, 必有f(x) cBB-1b, 此时称基可行解x = (B-1b, 0) T 为最优解.,3. 最优解的
5、存在性定理,将A的列向量重排次序成A = (B, N), 相应x = (xB, xN) T, c = (cB, cN) 基对应的变量xB称为基变量, 非基对应的变量xN称为非基变量.,定理1 如果线性规划(1)有可行解，那么一定有基可行解.,定理2 如果线性规划(1)有最优解，那么一定存在一个基可行解是最优解.,4. 基可行解是最优解的判定准则,因为 f = cBB-1b + (cN cBB-1N)xN， 即 f - 0xB + (cBB-1N- cN )xN = cBB-1b,检验数,5.基可行解的改进,改进方法：,返 回,练习建立LP数学模型 一、有两个煤厂A、B，每月分别供应三个居民区X
6、、Y、Z。求运费最少的方案。,供需平衡,1、LINGO使用简介 LINGO软件是美国的LINDO系统公司（Lindo System Inc）开发的一套用于求解最优化问题的软件包.LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解.LINGO软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快.LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果，这里简单介绍LINGO的使用方法.,LINGO可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模
7、型中的最优化问题等. 一个LINGO程序一般会包含集合段、数据输入段、优化目标和约束段、初始段和数据预处理段等部分，每一部分有其独特的作用和语法规则，读者可以通过查阅相关的参考书或者LINGO的HELP文件详细了解，这里就不展开介绍了.,三.线性规划软件求解,LINGO的主要功能特色为：既能求解线性规划问题，也有较强的求解非线性规划问题的能力；输入模型简练直观；运算速度快、计算能力强；内置建模语言，提供几十个内部函数，从而能以较少语句，较直观的方式描述大规模的优化模型；将集合的概念引入编程语言，很容易将实际问题转换为LINGO模型；并且能方便地与Excel、数据库等其他软件交换数据.,第一步：
8、启动Lingo,屏幕显示如下：标记LINGO的外窗口是主框架窗口，主框架窗口的上面包含所有的命令菜单和命令工具栏；标记LINGO MODEL-LINGO1的子窗口是一个新的、空白的模型窗口。,第二步：在模型窗口中输入模型,model: max = 2*x1+3*x2; 4*x1+3*x210; 3*x1+5*x212; end,Max 2x1+3x2 St. 4x1+3x2=10 3x1+5x2=；,Lingo无严格小于，欲使ab， 可以适当选取小的正常数e 表示成a+eb，,(9) LINGO编辑器用蓝色显示LINGO关键字; 绿色显示注释 ;其他文本用黑色匹配的括号用红色高亮度显示,(10
9、)标准运算符,算术运算符： * / + -,逻辑运算符：#EQ# #NE# (相等，不等）为真#GE# #GT#（左边大于或等于，左边大于）为真#LE# #LT#（左边小于或等于，左边小于）为真#NOT# #AND# #OR#（取反，取交（积），取并（和）),(11). 变量界定函数,lingo变量默认域为非负实数 free(variable)取消默认域，使变量可以取任意实数 gin(variable) 限制变量取整数值 bin(variable) 限制变量取值为0，1 bnd(low,variable,up) 限制变量于一个有限的范围,例题1： 某工厂在计划期内要安排生产A、B两种产品，已知
10、生产单位产品所需设备台时及对甲、乙两种原材料的消耗，有关数据如表1.1.问：应如何安排生产计划，使工厂获利最大？,建立线性规划问题的数学模型，用LINGO求出最优解并做相 应的分析.,问题1.1设计划生产A,B两种产品分别为x1,x2，则建立线性规划问题数学模型,模型：max S=2x1+ 3x2,在LINGO的MODEL窗口内输入如下模型： model: max=2*x1+3*x2; x1+2*x2=8; 4*x1=16; 4*x2=”的不等式，左边减右边的差值为Surplus（剩余），当约束条件两边相等时，松弛或剩余的值等于零.“Dual Price”的意思是对偶价格（或称为影子价格），上述报告中Row2的松弛值为0，表明生产甲产品4单位、乙产品2单位，所需设备8台时已经饱和，对偶价格1.5的含义是：如果设备增加1台时，能使目标函数值增加1.5.报告中Row4的松弛值为4，表明生产甲产品4单位、乙产品2单位，所需原材料乙8公斤还剩余4公斤，因此增加原材料乙不会使目标函数值增加，所以对偶价格为0.,
