《《精编》线性规划》由会员分享，可在线阅读，更多相关《《精编》线性规划（25页珍藏版）》请在金锄头文库上搜索。
1、1线性规划 1 1线性规划问题及其数学模型1 1 1问题的提出1 1 2图解法1 1 3线性规划问题的标准型1 2线性规划问题的求解 单纯形法1 2 1基本概念1 2 2单纯形法1 2 3单纯形法计算机软件1 3线性规划应用举例1 3 1线材的合理利用问题1 3 2配料问题1 3 3连续投资问题 1 1线性规划问题及其数学模型1 1 1问题的提出 一 例某工厂在计划期内要安排生产 两种产品 已知生产单位产品所需的设备台时和原料A B的消耗量如下表 该工厂每生产一件产品 可获利2元 每生产一件产品 可获利3元 问应如何安排生产计划能使该厂获利最多 这个问题可以用下面的数学模型来描述 设计划期内产
2、品 的产量分别为x1 x2 可获利润用z表示 则有 MaxZ 2x1 3x2 x1 2x2 8 4x1 16 4x2 12 x1 x2 0 1 1 1问题的提出 二 例靠近某河流有两个化工厂 流经第一化工厂的河流流量为每天500万m3 两工厂之间有一条流量为每天200万m3的支流 见图 第一化工厂每天排放污水2万m3 第二化工厂每天排放污水1 4万m3 污水从工厂1流到工厂2前会有20 自然净化 根据环保要求 河水中污水的含量应不大于0 2 而工厂1和工厂2处理污水的成本分别为1000元 万m3和800元 万m3 问两工厂各应处理多少污水才能使处理污水的总费用最低 设工厂1和工厂2每天分别处理
3、污水x1和x2万m3 则有 Minz 1000 x1 800 x2 2 x1 500 0 002 0 8 2 x1 1 4 x2 700 0 002 x1 2 x2 1 4 x1 x2 0 1 1 1问题的提出 三 以上两例都有一些共同的特征 用一组变量表示某个方案 一般这些变量取值是非负的 存在一定的约束条件 可以用线性等式或线性不等式来表示 都有一个要达到的目标 可以用决策变量的线性函数来表示 满足以上条件的数学模型称为线性规划模型 线性规划模型的一般形式如下 1 1线性规划问题及其数学模型1 1 2图解法 唯一最优解 无穷多最优解 解无界 无可行解 线性规划问题如果有最优解 则最优解一定
4、在可行域的边界上取得 特别地 一定可在可行域的顶点上取得 1 1线性规划问题及其数学模型1 1 3线性规划问题的标准型 线性规划问题的标准型maxz c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0其中 bi 0 i 1 2 m 令xj xj xj 对模型中的进行变量代换 不符合标准型的几个方面 目标函数为minz c1x1 c2x2 cnxn 令z z 变为maxz c1x1 c2x2 cnxn 约束条件为a11x1 a12x2 a1nxn b1 加入非负变量xn 1 称
5、为松弛变量 有a11x1 a12x2 a1nxn xn 1 b1 约束条件为a11x1 a12x2 a1nxn b1 减去非负变量xn 1 称为剩余变量 有a11x1 a12x2 a1nxn xn 1 b1 变量xj无约束 1 2线性规划问题的求解 单纯形法1 2 1基本概念 可行解满足约束条件 包括非负条件 的一组变量值 称可行解 所有可行解的集合称为可行域 最优解使目标函数达到最大的可行解称为最优解 基本解对于有n个变量 m个约束方程的标准型线性规划问题 取其m个变量 若这些变量在约束方程中的系数列向量线性无关 则它们组成一组基变量 确定了一组基变量后 其它n m个变量称为非基变量 令非基
6、变量都为0 解约束方程 可唯一得到基变量的值 从而得到一个满足约束方程的解 称为基本解 由此可见 一个基本解的非零分量个数不超过m个 基本可行解满足非负条件的基本解称为基本可行解 基本可行解既是基本解 又是可行解 它对应于线性规划问题可行域的顶点 1 2线性规划问题的求解 单纯形法1 2 2单纯形法 一 要找到线性规划问题的最优解 只要在基本可行解中寻找就可以了 虽然基本可行解的数目是有限个 不超过Cnm个 但当m n较大时 要用 穷举法 求出所有基本可行解也是行不通的 因此 必须寻求一种更有效的方法 单纯形法的基本思路是 从线性规划问题的一个基本可行解开始 转换到另一个使目标函数值增大的基本
7、可行解 反复迭代 直到目标函数值达到最大时 就得到了最优解 为了便于单纯形法的实施 我们用单纯形表来描述线性规划问题的一个基本可行解的情况 不妨设x1 x2 xm组成一组基变量 且对应一个基本可行解 用高斯消去法把等式约束和目标函数变形为x1 a 1m 1xm 1 a 1nxn b 1x2 a 2m 1xm 1 a 2nxn b 2 xm a mm 1xm 1 a mnxn b m z m 1xm 1 nxn z0把其系数列成数据表即单纯形表 1 2 2单纯形法 二 按照单纯形法的思路求解线性规划问题 要解决三个技术问题 给出第一个基本可行解 检验一个基本可行解是否是最优解 转换到另一个基本可
8、行解 把线性规划问题变成标准型后 观察是否每个约束方程中都有独有的 系数为1的变量 如果是 则取这些变量作为基变量 变得到一个基本可行解 否则 就给没有这种变量的约束条件添加一个人工变量 同时修改目标函数 见例题 如果单纯形表最后以行中的 j都满足 j 0 则对应的基本可行解是最优解 否则就不是最优解 j称为检验数 第一 确定换入变量 在大于0的检验数中找最大的为 k 对应变量xk为换入变量 第二 确定换出变量 取 min bi a ik a ik 0 bl a lk 对应的第l行的基变量为换出变量 第三 旋转运算 换入变量所在的行与换出变量所在的列交叉点的元素称为中心元素 用高斯削去法把中心
9、元素化成1 同列的其他元素化成0 得到一个新的单纯形表 也就得到一个新的基本可行解 1 2 2单纯形法 三 用单纯形法求解线性规划问题的具体步骤如下 找出初始可行基 确定初始基本可行解 建立初始单纯形表 转 检验对应于非基变量的检验数 j 若 j 0 xj为非基变量 都成立 则当前单纯形表对应的基本解就是最优解 停止计算 否则转 在所有 j 0中 若有一个 k对应的xk的系数a ik 0 i 1 2 m 则此问题为无界解 无解 停止计算 否则转 根据max j 0 k确定xk为换入变量 根据 规则 min b i a ik 1 i m a ik 0 b l a lk确定相应的换出变量 并得到中
10、心元素a lk 转 以a lk为枢轴元素进行转轴运算 得到新的单纯形表 转 用单纯行法求解线性规划问题后 应回答下面几个问题 是否解无界 上面的步骤已作出回答 是否无可行解 求解后 若人工变量都已取0 则有可行解 否则 无可行解 唯一最优解还是无穷多最优解 在最后的单纯形表中 若所有非基变量的检验数都严格小于0 则为唯一最优解 若存在某个非基变量的检验数等于0 则有无穷多最优解 1 2 22单纯形法 四 此问题的最优解为 x1 4 x2 2 x5 4 x3 x4 x1 0 z 2 4 3 2 14 1 2 2单纯形法 五 此问题的最优解为 x1 4 x2 1 x3 9 x4 x5 x6 x7
11、0 z 3 4 9 1 2 1 2 3用计算机软件求解线性规划问题 关于线性规划问题的求解 有许多好的专业软件和商务软件 通过计算机可十分方便地完成求解过程 最简便易行的求解软件是Excel 下面介绍其使用方法 1 建立Excsl工作表 用一组单元格表示变量 作为可变单元格 空 用几组单元格分别表示各约束条件和目标函数的系数 用一些单元格输入公式表示各组系数和变量的关系 2 打开工具栏中的 规划求解 对话框 指定存有目标函数的单元格为目标单元格 指定表示变量的单元格为可变单元格 建立约束条件 3 在规划求解对话框中按下 求解 按钮 即可求出最优解和最优值 推出规划求解对话框 1 3应用举例 一
12、 解先看有多少种裁料方案 再进行组合和选择 方案 例合理利用线材问题现要做一百套钢管 每套要长为2 9m 2 1m和1 5m的钢管各一根 已知原料长7 4m 问应如何下料 使用的原料最省 设用方案 分别裁原料钢管x1 x2 x8根 则 例某工厂要用三种原材料C P H混合调配出三种不同规格的产品A B D 已知产品的规格要求 单价和原料的供应量 单价如下表 该厂应如何安排生产 能使利润最大 1 3应用举例 二 根据产品要求有 AC 0 5A AP 0 25ABC 0 25B BP 0 5BAC AP AH ABC BP BH B根据原料供应量有 AC BC DC 100AP BP DP 100
13、AH BH DH 60 设AC AP DH分别为x1 x2 x9 有Maxz 50 x1 x2 x3 35 x4 x5 x6 25 x7 x8 x9 65 x1 x4 x7 25 x2 x5 x8 35 x3 x6 x9 x1 0 5 x1 x2 x3 x2 0 25 x1 x2 x3 x4 0 25 x4 x5 x6 x5 0 5 x4 x5 x6 x1 x4 x7 100 x2 x5 x8 100 x3 x6 x9 60 xj 0 j 1 2 3 4 5 6 7 8 9 解 记产品A B D中C P H的含量分别为AC AP AH BC BP BH DC DP DH 1 3应用举例 三 例
14、成批生产企业年度生产计划的按月分配 在年度计划按月分配时一般要考虑 从数量和品种上保证年度计划的完成 成批的产品尽可能集中在几个月内生产 由于技术方面的原因 某些产品在某个月后才能生产 某些产品要求年初交货 批量小的产品尽量集中在一个或几个月内生产出来 以便减少各月内的品种数量 考虑以上条件 使设备负荷均衡并使利用率最大化 假定工厂有m类设备 用i表示 i 1 2 m 生产n种产品 用j表示 j 1 2 n 各产品的全年计划量用dj表示 用aij表示加工单位j种产品所需要的第i类设备的台时数 bik表示k月份第i类设备的生产能力 台时 k 1 2 12 再假定第5 8两种产品下半年投产 第4号
15、产品要求二月底前完成全年计划 如要对全年12个月同时考虑 会使模型非常复杂 我们根据上述条件从1月到12月份 一个月一个月地分别建模计算 设k月份计划生产j种产品的数量为xjk 一月份模型为 n aijxj1 bi1 i 1 2 m j 1 xj1 dj j 1 2 n x51 x81 0 xj1 0 j 1 2 n 二月份模型为 n aijxj2 bi2 i 1 2 m j 1 xj2 dj xj1 j 1 2 n x52 x82 0 xj2 0 j 1 2 n 1 3应用举例 四 例连续投资问题 某单位有资金10万元 在今后5年内可考虑下列投资项目 已知 项目A 从第1到第4年每年初可投资
16、 并于次年末回收本利115 项目B 第3年初需要投资 到第5年末回收本利125 但最大投资额不超过4万元 项目C 第2年初需要投资 到第5年末能回收本利140 但最大投资额不超过3万元 项目D 5年内每年初可购买公債 当年末回收本利106 问它应该如何安排每年的投资 使到5年末拥有的资金最多 x2A x2C x2D 1 06x1D 解 每年的投资额应不超过手中的资金 由于项目D每年都可投资 且当年末就可收回 所以该单位每年必然把资金全部投出去 即投资额等于手中的资金数 设第i年投资各项目的资金为xiA xib xiC xiD 数学模型为 Maxz 1 15x4A 1 4x2C 1 25x3B 1 06x5D x1A x1D 10 x3A x3B x3D 1 15x1A 1 06x2D x4A x4D 1 15x2A 1 06x3D x5D 1 15x3A 1 06x4D xiA xib xiC xiD 0
