线性规划教学课件、 .ppt

第一章线性规划 linearprogramming 线性规划的基本特点 lp是运筹学中应用最广泛的方法之一 lp是运筹学中最基本的方法之一 网络分析 整数规划 目标规划和多目标规划等都是以lp为基础的 解决稀缺资源最优分配的有效方法 是付出的费用最小或获得的收益最大 线性规划的研究对象 有一定的人力 财力 资源条件下 如何合理安排使用 效益最高 某项任务确定后 如何安排人 财 物 使之最省 典型应用合理利用线材问题 如何下料 使用材最少 配料问题 在原料供应量的限制下 如何获得最大利润 投资问题 从投资项目中选取方案 使投资回报最大产品生产计划 合理利用人力 物 财等 使获利最大劳动力安排 用最少的劳动力来满足工作的安排运输问题 如何制定调整方案 使总运费最小 第一节线性规划问题及其数学模型 引例 配比问题 用浓度为45 和92 的硫酸配置100t浓度为80 的硫酸 取45 和92 的硫酸分别为x1和x2t 则有 求解二元一次方程组得解 一 线性规划问题的提出 目的相同 但有5种不同浓度的硫酸可选 30 45 73 85 92 会出现什麽情况 取这5种硫酸分别为x1 x2 x3 x4 x5t 则有 有多少种配比方案 为什麽 何为最好 5种硫酸价格分别为 400 700 1400 1900 2500元 t 则有 例1 1 已知某企业生产资料如下表所示 问如何安排生产才能企业使利润最大 数学模型 x1 0 x2 0 s t 设甲产品的生产量为x1 乙产品的生产量为x2 则 例1 2 设某种动物每天需要摄入的蛋白质 矿物质 维生素的最低量及a b c d e五种饲料每公斤营养成分的含量及单位价格如下表所示 要求既满足该种动物每天营养成分的需要量 又使总的费用最省 目标函数 满足约束条件 设为第j种饲料的每天使用量 则 1 定义 对于求取一组变量 j 1 2 n 使之既满足线性约束条件 又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题 简称线性规划linerprogramming lp 二 线性规划问题数学模型的一般形式 2 配比问题和生产计划问题的线性规划模型的特点 用一组未知变量表示要求的方案 这组未知变量称为决策变量 存在一定的限制条件 且为线性表达式 有一个目标要求 最大化 当然也可以是最小化 目标表示为未知变量的线性表达式 称之为目标函数 对决策变量有非负要求 3 线性规划问题数学模型的组成要素 1 变量 或称决策变量 它们是问题中所要解决的未知量 表明规划中用数量表示的方案 措施 可由决策者决定和控制 2 目标函数 是决策变量的函数 按问题的目标不同分别在这个函数前加上max或min 3 约束条件 由一组含决策变量的等式或不等式组成 表明决策变量取值时所受到的各种资源条件的限制 假定线性规划问题中含有n个决策变量xj j 1 n 在目标函数中xj的系数为cj cj通常称为价值系数 有m种资源的限制 每种资源数量用bi i 1 m 表示 用aij表示变量xj取值为1个单位时所消耗或含有的第i种资源的数量 通常称aij为技术系数或消耗系数 目标函数 约束条件 线性规划问题的数学模型的一般形式 为目标函数 为资源约束 为非负约束 xj 决策变量 cj 价值系数 aij 技术 消耗 系数 bi 资源常量 bi 0 线性规划模型的简写形式为 目标函数 约束条件 式中 用向量形式表达时 模型可写为 矩阵形式为 其中 a为约束方程组 约束条件 的系数矩阵 1 lp标准型的概念 1 什麽是lp的标准型 2 lp标准型的特点目标函数约定是极大化max 或极小化min 约束条件均用等式表示 决策变量限于取非负值 右端常数均为非负值 三 线性规划问题的标准形式 化一般形式为标准形式的方法 1 目标函数为求极小值 即为 因为求minz 等价于求max z 令z z 即化为 2 右端项bi 0 只需将等式或不等式两端同乘 1 则等式右端项必大于零 3 约束条件为不等式 当约束条件为 时 需将约束条件左端加松弛变量 当约束条件为 时 需将约束条件左端减去剩余变量 4 取值无约束的变量 可令x x x 其中x 0 x 0 5 对x 0的情况 令x x 显然x 0 例1 3 将下述线性规划化为标准形式 解 上述问题中令 得到 在第一个约束条件的左端加入一个松弛变量 在第二个约束条件是左端减去一个剩余变量 将第三个约束条件两端同乘 1 该问题的标准形式为 第二节线性规划图解法 一 什么是图解法 线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程 求解的思路是 先将约束条件加以图解 求得满足约束条件的解的集合 即可行域 然后结合目标函数的要求从可行域中找出最优解 图解法虽然只能用于解二维 两个变量 的问题 但其主要作用并不在于求解 而是在于能够直观地说明线性规划解的一些重要性质 二 图解法步骤 例1 4 用图解法求解下列线性规划问题 三 图解法举例 图解法的步骤可概括为 一 建立平面直角坐标系 二 利用约束条件 确定线性规划问题解的可行域 三 绘制目标函数的等值线和法线 四 沿法线方向移动目标函数等值线至可行域的边缘 寻求问题最优解 若该问题存在最优解 则在可行域的边缘得到问题的最优解 a b c 4 12 最优解 x1 4 x2 12 最优目标函数值 z 1200 四 线性规划问题解的可能结果 一 无穷多最优解 二 无界解 三 无解 五 图解法求解线性规划问题给我们的启示 线性规划的可行域是一个什么形状 多边形 而且是 凸 形的多边形 最优解在什么位置获得 在边界 而且是在某个顶点获得 思考 结论 线性规划的约束集 即可行域 是一个凸多面体 凸多面体是凸集的一种 所谓凸集是指 集中任两点的连线仍属此集 线性规划的最优解 若存在的话 必能在可行域的顶点获得 因为 由图解法可知 只有当目标直线平移到边界时 才能使目标函数值z达到最大限度的优化 问题 本性质有何重要意义 它使得在可行域中寻优的工作由 无限 上升为 有限 从而为线性规划的算法设计提供了重要基础 线性规划解的几种情况1 可行域为封闭的有界区域 a 有唯一的最优解 b 有一个以上的最优解 2 可行域为非封闭的无界区域 a 有唯一的最优解 b 有一个以上的最优解 c 目标函数无界 即虽有可行解 但在可行域中 目标函数可以无限增大或无限减小 因而没有最优解 3 可行域为空集 因而没有可行解 第三节线性规划问题解的性质 一 线性规划问题解的概念 一 可行解 最优解1 可行解 满足所有约束条件 包括非负条件 的解 可行解的集合称为可行集 或可行域 2 最优解 使目标函数达到极值的解 理应属于可行解集 可行解 可行域 最优解 二 基及其相关概念 m为约束方程的个数 n为变量的个数 约束方程组的系数矩阵a m n 且m n m为矩阵a的秩 仍以上图中的lp问题为例 1 基 设b为a的一个m m满秩子矩阵 且 b 0 b中的行或列向量线性无关 或行或列不全为0 这时 b就为该lp的一个基 取b1 b1 9 5 0 4 0 3 4 10 1 3 5 1 4 4 0 4 10 1 0 2 基向量 基变量 基向量 对应于上述基b 组成b的向量称为基向量 记作pj j 1 2 m 基变量 基向量对应的决策变量xj为基变量 记作xb如xb1 x1 x2 x3 t 3 非基向量 非基变量 非基向量 基向量以外的其他向量为非基向量 即nm 1 nn 以n表示 非基变量 非基向量对应的决策变量xj为基变量 记作xn如xn1 x4 x5 t 练习 任意给出该lp问题的三个基 对于给出的基b1 写出其基向量 基变量 非基向量 非基变量 三 基解 基可行解 可行基 基解 确定基b后 令非基变量xn 0 所得方程组axb b的解称为lp关于b的基解 或基本解 基础解 基可行解 满足基变量为非负约束的基解可行基 对应于基可行解的基 或者表述为 使基解满足非负约束的基 基解的特征 基可行解 基解不一定可行 可行解不一定是基解 可行解 基解 非基变量 0的解 注 基解的基变量有可能小于0 如 约束x1 x2 1取x2为基变量 即令x1 0 解得x2 1 满足所有约束的解 注 可行解中没有基变量的概念 因此就有可能解中所有变量值都不为0 一般地 m n阶矩阵a中基的个数最多有多少个 问题 本例的a中一共有几个基 例4 在上例中 求相应于基b1和b2的基本解 它们是否基本可行解 二 线性规划的基本定理 定义1 1设k是n维欧氏空间的一个点集 若对于k中的任意两点和 均有 则称k为凸集 定义1 2设k为凸集 若x不能用k中任意两点和的线性组合表示为 则称x为凸集k的一个顶点 或称为极点 定理1 1若线性规划问题存在可行域 则其可行域是凸集 定理1 3若线性规划问题的可行域非空有界 则线性规划问题的最优解一定可以在其可行域的某个顶点上得到 定理1 2线性规划问题的基可行解x对应于可行域r的顶点 这个定理是线性规划的基本定理 它的重要性在于把可行域的极点这一几何概念与基础可行解这一代数概念联系起来 而可以通过求基础可行解的线性代数的方法来得到可行域的一切极点 从而有可能进一步获得最优极点 上述定理的一些有意义的启示 lp的可行域一定是凸集 但是凸集不一定成为lp的可行域 而非凸集一定不会是lp的可行域 为什麽 能举例说明吗 线性规划的基本可行解和可行域的顶点是一一对应的 类似于坐标与点的对应关系 在可行域中寻找lp的最优解可以转化为只在可行域的顶点中找 从而把一个无限的问题转化为一个有限的问题 若已知一个lp有两个或两个以上最优解 那麽就一定有无穷多个最优解 第四节单纯形法 学习了线性规划解的性质定理后 我们会很自然地想到用 枚举法 来求解线性规划问题 但对于一个m n阶的线性规划问题 计算次数最多可达次 当m n较大时 枚举法就无法实施了 因此 我们需要寻求一种可行的求解方法 图解法的局限性 1947年g b dantzig提出的单纯形法提供了方便 有效的通用算法求解线性规划 lp解的性质回顾 maxz 2x1 x25x2 15s t6x1 2x2 24x1 x2 5x1 x2 0 求出b1的基解 它是可行解吗 是基可行解吗 基b1是可行基吗 你能找出一个该lp问题的不是基解的可行解吗 你能找出一个该lp问题的不是可行解的基解吗 最显而易见的一个基可行解 初始基可行解 是什么 任意给出该问题的三个基 对于给出的基b1 写出其基向量 基变量 非基向量 非基变量 找出上例的全部基解 指出其中的基可行解 确定最优解 找出上例的全部基解 指出其中的基可行解 确定最优解 用作图法求解该问题 指出上题中的基解各对应于图中哪些点 结论1 基解与所有约束线的交点一一对应 结论2 基可行解与可行域的顶点一一对应 由作图法可知 唯一最优解对应的是可行域的某一个顶点 结论3 唯一最优解是基可行解中的一个 结论4 唯一最优解只需在基可行解中寻找 所以 我们从某一个基可行解出发 沿边界搜索下一个顶点 判断目标函数值是否最优 若否 继续 直到最优 这就是单纯形法求解的基本思想 所以 单纯形法求解的基本条件是找到一个基可行解 可行基 而最显然易见的一个可行基就是一个单位矩阵 一 单纯形法的基本思想1 顶点的逐步转移即从可行域的一个顶点 基本可行解 开始 转移到另一个顶点 另一个基本可行解 的迭代过程 转移的条件是使目标函数值得到改善 逐步变优 当目标函数达到最优值时 问题也就得到了最优解 顶点转移的依据 根据线性规划问题的可行域是凸多边形或凸多面体 一个线性规划问题有最优解 就一定可以在可行域的顶点上找到 于是 若某线性规划只有唯一的一个最优解 这个最优解所对应的点一定是可行域的一个顶点 若该线性规划有多个最优解 那么肯定在可行域的顶点中可以找到至少一个最优解 转移条件 转移结果 使目标函数值得到改善得到lp最优解 单纯形法的由来 2 需要解决的问题 1 为了使目标函数逐步变优 怎麽转移 2 目标函数何时达到最优 判断标准是什麽 目标函数达到最优值 二 单纯形法原理 用代数方法求解lp 第一步 引入非负的松弛变量x4 x5 将该lp化为标准型 第二步 寻求初始可行基 确定基变量 x4 x5 对应的基变量是 第三步 写出初始基本可行解和相应的目标函数值 两个关键的基本表达式 用非基变量表示基变量的表达式 用非基变量表示目标函数的表达式请解释结果的经济含义 不生产任何产品 资源全部节余 x4 3 x5 9 三种产品的总利润为0 第四步 分析两个基本表达式 看看目标函数是否可以改善 分析用非基变量表示目标函数的表达式非基变量前面的系数均为正数 所以任何一个非基变量进基都能使z值增加通常把非基变量前面的系数叫 检验数 选哪一个非基变量进基 选x1为进基变量 换入变量 问题讨论 能否选其他的非基变量进基 任意一个 任意一个正检验数对应的非基变量 最大正检验数对应的非基变量 排在最前面的正检验数对应的非基变量 确定出基变量 问题讨论x1进基意味着其取值从0变成一个正数 经济意义 生产a产品 能否无限增大 当x1增加时 x4 x5如何变化 现在的非基变量是哪些 具体如何确定换出变量 由用非基变量表示基变量的表达式当x1增加时 x4 x5会减小 但有限度 必须大于等于0 以保持解的可行性 于是 当x1的值从0增加到3时 x4首先变为0 此时x5 6 0因此选x4为出基变量 换出变量 这种用来确定出基变量的规则称为 最小比值原则 或 原则 如果p1 0 会出现什麽问题 最小比值原则会失效 基变换新的基变量 x1 x5 新的非基变量x2 x3 x4 写出用非基变量表示基变量的表达式 可得新的基本可行解x 1 3 0 0 0 6 t 写出用非基变量表示目标函数的表达式 第五步 上述过程何时停止 当用非基变量表示目标函数的表达式中 非基变量的系数 检验数 全部非正时 当前的基本可行解就是最优解 为什麽 分析用非基变量表示目标函数的表达式 如果让负检验数所对应的变量进基 目标函数值将下降 基本思路 先找出一个基可行解 判断其是否为最优解 如果为否 则转换到相邻的基可行解 并使目标函数值不断增大 直到找到最优解为止 二 单纯形法的求解步骤 1 确定初始基可行解 对于标准形的线性规划问题 约束条件的变量的系数矩阵中总会存在一个单位矩阵 当约束条件均为 号时 加上松弛变量xs1 xs2 xsm的系数矩阵即为单位矩阵 用非基变量表示基变量可得到 令所有非基变量等于零 即可找到一个解 简写为 1 5 2 最优性检验 将 1 5 式代入目标函数 设 则 设 则 定理1 5 无穷多最优解 设为对应于基b的一个基可行解 且对于一切有 同时又存在某个非基变量的检验数 则线性规划问题存在无穷多最优解 定理1 4 最优解 设为对应于基b的一个基可行解 且对于一切有 则为线性规划问题的最优解 定理1 6 无界解 设为对应于基b的一个基可行解 存在某个非基变量的检验数 且有 则线性规划问题具有无界解 3 寻找新的基可行解 确定进基变量 对应的变量为进基变量 确定离基变量 对应的变量为离基变量 迭代计算 对于列向量 以为主元素 将变为1 其余变为0 即将向量变换为单位向量 重复2 3直到所有的检验数小于等于0为止 则问题得到最优解 第1步 确定初始基可行解 列出初始单纯形表 为了书写规范和便于计算 对单纯形法的计算设计了一种专门表格 称为单纯形表 二 单纯形表 第2步 最优性检验 如表中所有检验数 j 0 且基变量中不含有人工变量时 表中的基可行解即为最优解 计算结束 对基变量中含人工变量时的解的最优性检验将在下一节中讨论 当表中存在 j 0又pj 0 则问题为无界解 计算结束 否则转下一步 第3步 列出新的单纯形表 寻找新的基可行解 只要有检验数 j 0 对应的变量xj就可作为换入基的变量 当有一个以上检验数大于零时 一般从中找出最大一个 k 作为进基变量 也称换入变量 确定进基变量 确定离基变量 根据最小 的规则确定 元素决定了从一个基可行解到相邻基可行解的转移去向 取名主元素 以ah m l 为主元素进行迭代 迭代计算 第4步 重复第2 3两步 直到所有的检验数小于等于0时 计算结束 例1 5 用单纯形法求解线性规划问题 解 将上述问题化为标准形式有 其约束条件系数矩阵为 列出初始单纯形表为 36 3 16 1 90 0 70 0 0 0 65 12 1 5 0 0 1 0 0 1 3 2 3 4 0 1 3 1 1 3 0 0 10 0 30 0 12 18 13 12 0 1 3 1 0 5 0 0 15 5 1 4 1 0 2 1 0 0 30 0 20 1 2 例 利用单纯形法求解下列问题 化为标准型 24 6 5 1 2 0 1 0 0 0 1 4 1 2 3 0 1 6 1 0 0 1 6 1 3 15 0 5 1 0 0 0 1 3 0 1 3 0 3 12 3 2 15 2 0 0 1 5 4 15 2 3 2 0 1 0 1 4 3 2 7 2 1 0 0 1 4 1 2 0 0 0 1 4 1 2 建立初始单纯形表如下 第五节单纯形法的其他问题讨论 一 关于标准形为最小化问题 目标函数为最小化的标准形式 最优性检验的判别定理 定理1 7 最优解 设为对应于基b的一个基可行解 且对于一切有 则为线性规划问题的最优解 定理1 8 无穷多最优解 设为对应于基b的一个基可行解 且对于一切有 同时又存在某个非基变量的检验数 则线性规划问题存在无穷多最优解 定理1 9 无界解 设为对应于基b的一个基可行解 存在某个非基变量的检验数 且有 则线性规划问题具有无界解 二 人工变量法 例1 6 用单纯形法求解线性规划问题 解 将其化成标准形式有 上述标准化模型中 不存在单位矩阵 为构造单位矩阵 则需要通过添加人工变量的方法 人为构造一个单位矩阵 该方法即所谓的人工变量法 1 大m法 大m法又称惩罚法 其基本思想是 约束条件加入人工变量后 为使目标函数取值不受影响 给定它们在求最大值 max 的目标函数中的系数为 m 称为惩罚因子 m为任意大的正数 以作为对基变量中存在人工变量的惩罚 从而迫使人工变量从基变量中分离出来 否则目标函数将不能实现最大化 添加人工变量后 例1 6的数学模型形式变为 列出初始单纯形表如下 3 8 6 0 1 0 1 1 3 3 0 0 1 0 2 2 1 0 0 0 1 1 2m 5 6m 5m m 0 0 0 2 1 3 5 8 3 6 5 3 5 1 0 1 5 0 1 5 1 5 31 5 0 0 3 5 1 3 5 7 5 11 5 2 5 0 1 2 5 0 2 5 3 5 5 0 0 0 0 m 1 m 5 3 5 31 3 计算机处理数据时 只能用很大的数代替m 可能造成计算机上的错误 故多采用两阶段法 2 两阶段法 第一阶段 添加人工变量 重新构造目标函数 将原问题加入人工变量 构造仅含人工变量的新的目标函数 并要求实现最小化 新的目标函数形式如下 求解上述线性规划问题 若w 0 则原线性规划问题存在基可行解 计算转入第二阶段 若w 0 则原线性规划问题无可行解 计算停止 第二阶段 对原目标函数求解 在第一阶段的最终单纯形表中 将才cj行的数字换为原目标函数的系数 并且去掉表中含有人工变量的列 继续求解 将例1 6问题利用两阶段法进行求解 第一阶段 添加人工变量 重新构造目标函数 例1 6用两阶段法求解时 第一阶段的线性规划问题可写为 将上述数学模型标准化后 用单纯形法求解过程见下表 3 8 6 0 1 0 1 1 3 3 0 0 1 0 2 2 1 0 0 0 1 2 6 5 1 0 0 0 1 3 5 8 3 6 5 3 5 1 0 1 5 0 1 5 1 5 31 5 0 0 3 5 1 3 5 7 5 11 5 2 5 0 1 2 5 0 2 5 3 5 0 0 0 0 0 1 1 5 3 5 可以看出 w 0 该问题有解 转入第二阶段 第二阶段 得最优解 将第一阶段得到的最终单纯形表的人工变量列去掉 将目标cj行换为原怒表函数的系数 再进行迭代 31 3 三 单纯形法计算中退化与循环问题 1 单纯形法计算中按最小比值来确定离基变量时 有时存在两个以上相同的最小比值 这样在下一次迭代中就会出现一个或多个基变量等于零的情形 这就出现了所谓的退化解 当存在退化解时 就有可能出现迭代计算的循环 勃兰特规则 1 当存在多个且相等时 选取中下标值最小的变量作为进基变量 2 当按 规则计算出现两个或两个以上相同的最小比值时 选取下标值最小的变量作为离基变量 2 为确定出基变量要计算比值 该比值 解答列元素 主元列元素 对于主元列的0元素或负元素是否也要计算比值 此时解的可行性自然满足 不必计算 如果主元列元素全部为0元素或负元素 则最小比值失效 线性规划无 有限最优解 3 选择进基变量时 同时有若干个正检验数 怎麽选 最大正检验数或从左至右第1个出现的正检验数所对应的非基变量进基 四 解的其它情况 练习1 单纯形表求解下列线性规划问题 练习2 用单纯形法表求解下面的线性规划问题 五 单纯形法小结 第六节线性规划应用举例 合理利用线材问题 如何下料使用材最少 配料问题 在原料供应量的限制下如何获取最大利润 投资问题 从投资项目中选取方案 使投资回报最大 建模 线性规划 产品生产计划 合理利用人力 物力 财力等 使获利最大 劳动力安排 用最少的劳动力来满足工作的需要 运输问题 如何制定调运方案 使总运费最小 数学规划的建模有许多共同点 要遵循下列原则 1 容易理解 建立的模型不但要求建模者理解 还应当让有关人员理解 这样便于考察实际问题与模型的关系 使得到的结论能够更好地应用于解决实际问题 2 容易查找模型中的错误 这个原则的目的显然与 1 相关 常出现的错误有 书写错误和公式错误 3 容易求解 对线性规划来说 容易求解问题主要是控制问题的规模 包括决策变量的个数和约束条件的个数 这条原则的实现往往会与 1 发生矛盾 在实现时需要对两条原则进行统筹考虑 建立线性规划模型的过程可以分为四个步骤 1 设立决策变量 2 明确约束条件并用决策变量的线性等式或不等式表示 3 用决策变量的线性函数表示目标 并确定是求极大 max 还是极小 min 4 根据决策变量的物理性质研究变量是否有非负性 一 混合配料问题 例1 7 某工厂要用三种原材料c p h混合调配出三种不同规格的产品a b d 已知产品的规格 产品单价 每天能供应的原材料数量及原材料单价如表1 10 表1 11所示 问该厂如何安排生产 利润收入最大 解 设ac表示a产品中c的成分 其数量用x1表示 ap表示a产品中p的成分 其数量用x2表示 ah表示a产品中h的成分 其数量用x3表示 bc表示b产品中c的成分 其数量用x4表示 bh表示b产品中h的成分 其数量用x6表示 bp表示b产品中p的成分 其数量用x5表示 dc表示d产品中d的成分 其数量用x7表示 dh表示d产品中h的成分 其数量用x9表示 dp表示d产品中p的成分 其数量用x8表示 依据题意 得 依据产品规格要求得 整理得 依据原材料每天供应量限制得 该问题的线性规划数学模型为 二 生产计划安排问题 例1 8 某厂生产 三种产品 都分别经a b两道工序加工 设a工序可分别在设备a1或a2上完成 有b1 b2 b3三种设备可用于完成b工序 已知产品 可在a b任何一种设备上加工 产品 可在任何规格的a设备上加工 但完成b工序时 只能在b1设备上加工 产品 只能在a2与b2设备上加工 加工单位产品所需工序时间及其它各项数据见下表 试安排最优生产计划 使该厂获利最大 解 设产品 的产量分别为x1 x2 x3件 产品 有6种加工方案 分别利用设备 a1 b1 a1 b2 a1 b3 a2 b1 a2 b2 a2 b3 各方案加工的产品 数量用xll x12 x13 x14 x15 x16表示 产品 有2种加工方案 即 a1 b1 a2 b1 加工数量用x21 x22表示 产品 只有1种加工方案 a2 b2 加工数量等于x3 工厂的盈利为产品售价减去相应的原料费和设备加工费 产品加工量只受设备有效台时的限制 故可建立如下线性规划模型 三 生产与存贮问题 解 设xij为i种产品j月份在正常时间内生产的数量 为第i种产品j月份在加班时间内生产的数量 该厂盈利总额为生产的5种产品销售价减去成本和库存费用 问题的限制条件有两项 一是各个月的正常和加班的允许工时 二是满足交货要求 本例的线性规划模型可表示为 例1 9 某厂签订了5种产品 i 1 5 上半年的交货合同 已知各产品在第j月 j 1 6 的合同交货量dij 该月售价sij 成本价cij及生产1件时所需工时aij 该厂第j月的正常生产工时为tj 但必要时可加班生产 第j月允许的最多加班工时不超过 并且加班时间内生产出来的产品每件成本增加额外费用元 若生产出来的产品当月不交货 每件库存1个月交存贮费pi元 试为该厂设计一个保证完成合同交货 又使上半年预期盈利总额为最大的生产计划安排 解 设为i种产品j月份在正常时间内生产的数量 为第i种产品j月份在加班时间内生产的数量 本例的线性规划模型可表示为 某厂在今后四个月内需租用仓库堆放物资 已知各月份所需仓库面积数字列于1 1表中 仓库租借费用随合同期定 期限越长折扣越大 具体数字见表1 2 租借仓库的合同每月初都可办理 每份合同具体规定租用面积数和期限 因此该厂可根据需要 在任何一个月初办理租借合同 每次办理时可签一份 也可签若干份租用面积和租借期限不同的合同 总目标是使所付租借费用最小 试建立上述问题的线性规划模型 表1 1 表1 2 若该医院值班护士分别在各时间段开始时上班 并连续工作8小时 问该医院最少需要多少护士 才能满足工作需要 解 设xi表示第i班