运筹学数学建模7-9.ppt

运筹学理论与建模;主要内容;第一部分 线性规划建模方法;例1 加工奶制品的生产计划;1桶牛奶 ;模型分析与假设 ;;线性规划模型标准型:;1.线性规划的一般形化为标准型的一般步骤;例 将下述线性规划问题化为标准型;合理下料问题;例.某小区一个24小时营业便利店,一天各时段所需服务员最少人数如下表.根据实际情况,要求每个服务员必须连续工作八小时,试建立需服务员总人数最少的排班方案数学模型.;连续投资问题;二、线性规划模型的求解;max z= c x ;制订生产计划,使每天获利 最大. ;（一）图解法（n?3时）;引入松弛变量x3, x4, x5, 化为标准形:;显然A的秩为3, 任取3个线性无关的列向量,如P1 , P2 , P3称为一 组基, 记为B =(P1 , P2 , P3 ).P1 , P2 , P3 称为基向量 , 基向量对应 的变量 x1 ,x2 ,x3称为基变量, 其余列向量 P4 , P5 称为非基向量 , 记为N= (P4 , P5 ). 非基对应的变量 x4 ,x5 称为非基变量. A = (B, N), 相应X = (XB, XN) T, c = (cB, cN);令非基变量XN = 0, 解得基变量XB = B-1b, 称(XB, XN)为基本解.;另一个基 本可行解; 即从可行域的一个顶点(基本可行解)开始, 转移到另一个顶 点(另一个基本可行解)的迭代过程, 转移的条件是使目标函数 值得到改善(逐步变优), 当目标函数达到最优值时, 问题也就得 到了最优解. 顶点转移的依据？ 根据线性规划问题的可行域是凸多边形或凸多面体, 一个 线性规划问题有最优解, 就一定可以在可行域的顶点上找到. 于是, 若某线性规划只有唯一的一个最优解, 这个最优解 所对应的点一定是可行域的一个顶点; 若该线性规划有多个最 优解, 那么肯定在可行域的顶点中可以找到至少一个最优解.; 转移条件？ 转移结果？ 使目标函数值得到改善 得到LP最优解，目标函数达到最优值 （单纯形法的由来？ ） 2．需要解决的问题： (1)为了使目标函数逐步变优，怎么转移？ (2)目标函数何时达到最优——判断标准是什么？ ;2.单纯形法原理（用代数方法求解LP）;;②用非基变量表示目标函数的表达式;② 选哪一个非基变量进基？ 选x2为进基变量（换入变量） 问题：能否选其他的非基变量进基？;? 现在的非基变量是哪些？ ? 具体如何确定换出变量？; 这种用来确定出基变量的规则称为 “最小比值原则” （或θ原则). 如果P1≤0，会出现什么问题？最小比值原则会失效！;⑤ 写出用非基变量表示目标函数的表达式:;——分析: 用非基变量表示目标函数的表达式, 如果让负检验数 所对应的变量进基，目标函数值将下降！;（2）表格设计依据： 把目标函数表达式改写成方程的形式，和原有的m个约束 方程组成一个具有n+m+1个变量、m+1个方程的方程组：;取出系数写成增广矩阵的形式： ;其中， j=1，2，…，n ； ;2. 例1的表格单纯形法计算过程： ;表格单纯形法求解步骤;;该迭代过程直至下列情况之一发生时停止 ? 检验数行全部变为非正值； （得到最优解）或 ?主元列≤ 0 （最优解无界）;自来水输送与货机装运;其他费用:450元/千吨 ;总供水量：160;供应限制;目标函数 ;如何装运，使本次飞行获利最大？ ;决策变量 ;货舱容积 ;约束条件;第二部分 整数规划建模方法;2.1 整数规划简介;2.2 整数规划的分枝定界法;表2.2.1 分枝问题解可能出现的情况; 2.2.2 分枝定界法举例; 表2.2.3 分枝问题的松弛解;例.某厂拟用集装箱托运甲,乙两种货物。已知;分枝定界法(branch and bound method);应如何安排原油的采购和加工 ？ ;决策变量 ;原油供应 ; 目标函数中c(x)不是线性函数，是非线性规划； 对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解； 想办法将模型化简，用现成的软件求解.;整数规划应用举例;1. 整数变量;表示决策之间的逻辑关系，如决策 i 必须以决策 j 的结果为前提： xi ? xj 或 xi = xj 描述互斥的选择，从多种方案中选一个方案： ?j xj = 1;例 某公司有600万元资金用于投资，有5个项目列入投 资计划