4.1 数学规划.pdf

例例1 加工奶制品的生产计划加工奶制品的生产计划 35元可买到元可买到1桶牛奶 买吗 若买 每天最多买多少桶牛奶 买吗 若买 每天最多买多少 可聘用临时工人 付出的工资最多是每小时几元可聘用临时工人 付出的工资最多是每小时几元 A1的获利增加到的获利增加到 30元元 公斤 应否改变生产计划 公斤 应否改变生产计划 问题 一奶制品加工厂用牛奶生产问题 一奶制品加工厂用牛奶生产A1 A2两种奶制品 两种奶制品 1 桶牛奶在设备甲上用桶牛奶在设备甲上用12小时加工小时加工3公斤公斤A1 或 或在设备乙 上用 在设备乙 上用8小时加工小时加工4公斤公斤A2 A1获利获利24元元 公斤 公斤 A2获利获利16 元元 公斤 每天供应公斤 每天供应50桶牛奶 每天总的工作时间桶牛奶 每天总的工作时间480小 时 在设备甲上至多加工 小 时 在设备甲上至多加工100公斤公斤A1 试制订生产计 划 使每天获利最大 试制订生产计 划 使每天获利最大 并进一步讨论以下三个问题 并进一步讨论以下三个问题 例例1 加工奶制品的生产计划加工奶制品的生产计划 1桶 牛奶 桶 牛奶 3公斤公斤A1 12小时小时 8小时小时 4公斤公斤A2 或 获利 或 获利24元元 公斤公斤 获利获利16元元 公斤公斤 50桶牛奶桶牛奶时间时间480小时小时至多加工至多加工100公斤公斤A1 制订生产计划 使每天获利最大制订生产计划 使每天获利最大 35元可买到元可买到1桶牛奶 买吗 若买 每天最多买多少桶牛奶 买吗 若买 每天最多买多少 可聘用临时工人 付出的工资最多是每小时几元可聘用临时工人 付出的工资最多是每小时几元 A1的获利增加到的获利增加到 30元元 公斤 应否改变生产计划 公斤 应否改变生产计划 每天 每天 1桶 牛奶 桶 牛奶 3公斤公斤A1 12小时小时 8小时小时 4公斤公斤A2 或 获利 或 获利24元元 公斤公斤 获利获利16元元 公斤公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2 获利获利 24 3x1获利获利 16 4 x2 原料供应原料供应50 21 xx 劳动时间劳动时间 480812 21 xx 加工能力加工能力 1003 1 x 决策变量决策变量 目标函数目标函数 21 6472xxzMax 每天获利每天获利 约束条件约束条件 非负约束非负约束 0 21 xx 线性 规划 模型 线性 规划 模型 LP 时间时间480小时小时50桶牛奶每天桶牛奶每天至多加工至多加工100公斤公斤A1 第四章数学规划模型第四章数学规划模型 y 4 1 线性规划线性规划 4 2 单纯形算法单纯形算法 4 3 奶制品的加工与生产奶制品的加工与生产 4 4整数规划整数规划 4 5非线性规划非线性规划 4 6多 目标规划多 目标规划 教材教材2 数学规划及其应用 第 数学规划及其应用 第3版 范玉妹 徐尔版 范玉妹 徐尔 教材教材1 运筹学 第 运筹学 第2版 熊伟版 熊伟机械工业出版社机械工业出版社 4 1 线性规划4 1 线性规划 1 1 数学模型数学模型 1 2 图解法图解法 1 3 线性规划的标准形线性规划的标准形 1 4线性规划的有关概念线性规划的有关概念 1 5单纯形方法单纯形方法 例例1 1 生产计划问题生产计划问题 某企业在计划期内计划生产 甲 乙两种产品 按工艺资料规定 每件产 品甲需要消耗材料 某企业在计划期内计划生产 甲 乙两种产品 按工艺资料规定 每件产 品甲需要消耗材料A 2公斤 公斤 B 1公斤 每件 产品乙需要消耗材料 公斤 每件 产品乙需要消耗材料A 1公斤 公斤 B 1 5公斤 已 知在计划期内可供材料分别为 公斤 已 知在计划期内可供材料分别为40 30公斤公斤 每 生产一件甲 乙产品 企业可获得利润分别 为 每 生产一件甲 乙产品 企业可获得利润分别 为300 400元 假定市场需求无限制 元 假定市场需求无限制 甲甲乙乙资源资源 材料材料 A2140 材料材料 B 11 530 利润元利润元 件件 300400 问 企业决策者应如何安 排生产计划 即甲 乙各生产多少件可使 企业所得利润最大 问 企业决策者应如何安 排生产计划 即甲 乙各生产多少件可使 企业所得利润最大 4 1 1 应用模型举例应用模型举例 解 设计划期内甲 乙产 量分别为件 解 设计划期内甲 乙产 量分别为件 12 xx 12 max300400 s t Zxx 12 12 12 240 1 530 0 xx xx xx 目标函数目标函数 约束条件约束条件 数学模型 数学模型 决策变量决策变量 例例1 甲甲乙乙资源资源 材料材料 A2140 材料材料 B 11 530 利润元利润元 件件 300400 线性规划数学模型线性规划数学模型 求出的值 称为最优解 使得目标函数达到 最大值 于是得到一个最优生产计划方案 求出的值 称为最优解 使得目标函数达到 最大值 于是得到一个最优生产计划方案 12 xx 例例人力资源安排问题人力资源安排问题 例例合理用料问题合理用料问题 例例配料问题配料问题 例例投资问题投资问题 4 1 1 应用模型举例应用模型举例 例2 最优国民经济计划问题 假设国民经济分三个 部门 每个部门生产单位产值所消耗的各部门的 产值 占用的资金数量及消耗的劳动量如下表 已知三个部门现有资金700个单位 劳动力200个 单位 例2 最优国民经济计划问题 假设国民经济分三个 部门 每个部门生产单位产值所消耗的各部门的 产值 占用的资金数量及消耗的劳动量如下表 已知三个部门现有资金700个单位 劳动力200个 单位 部门部门1部门部门2部门部门3 部门部门10 01090 1518 0 0038 部门部门20 13180 1822 0 0845 部门部门30 05500 0599 0 0647 资金占用量资金占用量2 02 51 8 劳动力消耗量劳动力消耗量0 20 30 2 问 问 三个部门总产值 最终产品产值各为多少时可 使国民经济的最终产品总值最大 三个部门总产值 最终产品产值各为多少时可 使国民经济的最终产品总值最大 700 200 例 例 部门部门1部门部门2部门部门3 部门1部门10 0109 0 15180 0038 部门部门20 1318 0 18220 0845 部门部门30 0550 0 05990 0647 资金资金2 02 51 8 劳动力劳动力0 20 30 2 解 解 Smax 321 yyy 13211 0038 01518 00 0109yxxxx 23212 0845 01822 00 1318yxxxx 33213 0647 00599 00 0550yxxxx 7008 15 22 321 xxx 2002 03 02 0 321 xxx 3 2 10 jyx jj 最终产品总值最大最终产品总值最大 1 y 2 y 3 y 1 x 2 x 3 x 700 200 设是第设是第j 个部门的总产值个部门的总产值 j x 设是第设是第j 个部门的最终产 品产值 个部门的最终产 品产值 j y 目标函数的变量系 数用表示 称为 目标函数的变量系 数用表示 称为 价值系数价值系数 约束条 件的变量系数用 表示 称为 约束条 件的变量系数用 表示 称为工艺系 数 工艺系 数 约束条件右端 常数用表示 称 为 约束条件右端 常数用表示 称 为资源限量资源限量 一般地 假设线性规划数学模型中 有一般地 假设线性规划数学模型中 有m个约束 有个约束 有n个决 策变量 即 个决 策变量 即 LP 11212111 bxaxaxa nn L 22222121 bxaxaxa nn L mnmnmm bxaxaxa L 2211 LLLLLLLLLLLL njx j 2 10L 1122 max nn Zc xc xc x L L min Linear Programming 4 1 2 线性规划的一般模型线性规划的一般模型 j c ij a i b 则称为 则称为 LP 的最优解 的最优解 可行解 可行解 LP 可行域 可行域 XDXDCXCX 若 若 且且 对对有有 最优解 最优解 最优值 最优值 CXS n j jj xcS 1 min 1 n ijji j a xb mi 2 1L njx j 2 10L CX 21n cccCL n x x x X M 2 1 若若满满足所有的约束条件 足所有的约束条件 则称则称X为可行解 为可行解 12 T n Xx xx LL LP 可行解的全体构成的集合称为可行域 可行解的全体构成的集合称为可行域D X 第一章 线性规划第一章 线性规划 1 1 数学模型数学模型 1 2 图解法图解法 1 3 线性规划的标准形线性规划的标准形 1 4线性规划的有关概念线性规划的有关概念 1 5单纯形方法单纯形方法 例例3用用图解法图解法求解例1 1的最优解求解例1 1的最优解 12 max300400 s t Zxx 12 12 12 240 1 530 0 xx xx xx 1 1 求可行域 求可行域 可行域 可行域 分别求出满足每 个约束条件的区 域 其交集就是可 行解集合 称为 分别求出满足每 个约束条件的区 域 其交集就是可 行解集合 称为可 行域 可 行域 20 0 0 40 30 0 0 20 1 x 2 x 0 例例3用用图解法图解法求解例1 1的最优解求解例1 1的最优解 12 max300400 s t Zxx 12 12 12 240 1 530 0 xx xx xx 1 1 求可行域 求可行域 2 2 绘制目标函数等值线 绘制目标函数等值线 12 300400Zxx 21 3 4400 Z xx 目标函数等值线 目标函数等值线 1 x 2 x 0 0 400 800 0 400 800 例例3用用图解法图解法求解例1 1的最优解求解例1 1的最优解 12 max300400 s t Zxx 12 12 12 240 1 530 0 xx xx xx 1 1 求可行域 求可行域 2 2 绘制目标函数等值线 绘制目标函数等值线 21 3 4400 Z xx 目标函数等值线 目标函数等值线 3 3 移动目标函数等值线 移动目标函数等值线 求最优解 求最优解 15 10 15 10 8500 T X Z 12 300400Zxx 最优解唯一最优解唯一 1 x 2 x 0 maxZ 0 400 800 例例3用用图解法图解法求解例1 1的最优解求解例1 1的最优解 12 max300400 s t Zxx 12 12 12 240 1 530 0 xx xx xx 1 1 求可行域 求可行域 2 2 绘制目标函数等值线 绘制目标函数等值线 3 3 移动目标函数等值线 求最优解 移动目标函数等值线 求最优解 注 注 图解法只能求解两个 变量的线性规划问题 图解法只能求解两个 变量的线性规划问题 15 10 15 10 8500 T X Z 最优解唯一最优解唯一 1 x 2 x 0 maxZ 线性规划问题解的几种情况 线性规划问题解的几种情况 1 有唯一的最优解1 有唯一的最优解 2 x 1 x0 0 X 两点间线段上所有可行解两点间线段上所有可行解 例4 例4 21 2maxxxS 0 2 1223 62 21 2 21 21 xx x xx xx 1 画出可行域1 画出可行域 2 画出目标函数等值线2 画出目标函数等值线 3 移动等值线求最优解3 移动等值线求最优解 21 2xxS 22 1 12 S xx 6 S 02 4 3 3 2 2 2 maxS 线性规划问题解的几种情况 线性规划问题解的几种情况 1 有唯一的最优解1 有唯一的最优解 2 有无穷多个最优解2 有无穷多个最优解 图解法 例5 图解法 例5 21 minxxS 0 1 22 21 21 21 xx xx xx 2 x 1 x 0 0 21 xxS Sxx 12 1 2 3 minS 0 1 1 1 0 S X T 线性规划问题解的几种情况 线性规划问题解的几种情况 1 有唯一的最优解1 有唯一的最优解 2 有无穷多个最优解2 有无穷多个最优解 图解法 例6 图解法 例6 21 maxxxS 0 1 22 21 21 21 xx xx xx 21 xxS Sxx 12 Smax 2 x 1 x 0 0 称为称为没没有有限的有有限的 最优解最优解 21 minxxS 0 1 22 21 21 21 xx xx xx 例例 5 5 1 2 3 线性规划问题解的几种情况 线性规划问题解的几种情况 1 有唯一的最优解1 有唯一的最优解 2 有无穷多个最优解2 有无穷多个最优解 3 没有有限的最优解3 没有有限的最优解 图解法 例7 图解法 例7 21 23minxxS 0 632 1 21 21 21 xx xx xx 2 x 1 x 0 0 没有可行解 没有可行解 故没有最优解故没有最优解 D 空集 空集 线性规划问题解的几种情况 线性规划问题解的几种情况 1 有唯一的最优解1 有唯一的最优解 2 有无穷多个最优解2 有无穷多个最优解 3 没有有限的最优解3 没有有限的最优解 4 没有可行解 故没有最优解4 没有可行解 故没有最优解 无解无解 凸集的几何定义 凸集的几何定义 若一个集合的任意两点的连线 直线 仍在这个集合中 则称 这个集合为凸集 若一个集合的任意两点的连线 直线 仍在这个集合中 则称 这个集合为凸集 结论 结论 1 1 LP 的可行域是为凸集 的可行域是为凸集 2 2 LP 若有有限的最优解 则一定可以在可行域若有有限的最优解 则一定可以在可行域 的某个顶点上达到 的某个顶点上达到 自学 自学 第一章 线性规划第一章 线性规划 1 1 数学模型数学模型 1 2 图解法图解法 1 3 线性规划的标准形线性规划的标准形 1 4线性规划的有关概念线性规划的有关概念 1 5单纯形方法单纯形方法 一般地 假设线性规划数学模型中 有一般地 假设线性规划数学模型中 有m个约束 有个约束 有n个决 策变量 即 个决 策变量 即 LP 11212111 bxaxaxa nn L 22222121 bxaxaxa nn L mnmnmm bxaxaxa L 2211 LLLLLLLLLLLL njx j 2 10L 1122 max nn Zc xc xc x L L min Linear Programming 4 1 2线性规划的一般模型线性规划的一般模型 11212111 bxaxaxa nn L 22222121 bxaxaxa nn L mnmnmm bxaxaxa L 2211 LLLLLLLLLLLL njx j 2 10L 1122 max nn Zc xc xc x L L LP 线性规划的标准型 线性规划的标准型 1 目标函数求最大 最小 2 约束条件均为等式约束 3 变量均为非负 4 右端常数非负 1 目标函数求最大 最小 2 约束条件均为等式约束 3 变量均为非负 4 右端常数非负 注释 注释 单纯形法是针对线性规划问题的标准形进行 求解的 单纯形法是针对线性规划问题的标准形进行 求解的 maxZCX 线性规划的标准型 线性规划的标准型 12 n Cc cc LL 1 2 n x x X x M M 1 2 12 n n x x CXc cc x L M L M 11212111 bxaxaxa nn L 22222121 bxaxaxa nn L mnmnmm bxaxaxa L 2211 LLLLLLLLLLLL njx j 2 10L 1122 max nn Zc xc xc x L L maxZCX AXb 线性规划的标准型 线性规划的标准型 12 n Cc cc LL 11121 21222 12 n n mmmn aaa aaa A aaa L L LLLL L L L LLLL L 1 2 m b b b b M M 11212111 bxaxaxa nn L 22222121 bxaxaxa nn L mnmnmm bxaxaxa L 2211 LLLLLLLLLLLL njx j 2 10L 1122 max nn Zc xc xc x L L 1112111 2122222 12 n n mmmnnm aaaxb aaaxb AX aaaxb L L LLLLMM L L L LLLLMM L 1 2 n x x X x M M maxZCX AXb 0X 线性规划的标准型 线性规划的标准型 12 n Cc cc LL 11121 21222 12 n n mmmn aaa aaa A aaa L L LLLL L L L LLLL L 11212111 bxaxaxa nn L 22222121 bxaxaxa nn L mnmnmm bxaxaxa L 2211 LLLLLLLLLLLL njx j 2 10L 1122 max nn Zc xc xc x L L maxZCX AXb 0X 1 2 m b b b b M M 1 2 n x x X x M M 矩阵形式矩阵形式 将一般的线性规划数学模型化为标准形将一般的线性规划数学模型化为标准形 123 min3Zxxx 123 123 123 123 28 3 325 0 xxx xxx xxx x xx 任意任意 称为称为剩余变量剩余变量 5 x 称为称为松弛变量松弛变量4 x Z Z X 例例7 123 max 3Zxxx 1234 1235 123 12453 28 3 325 0 xxxx xxxx xxx x x x xx 任意任意 将一般的线性规划数学模型化为标准形将一般的线性规划数学模型化为标准形 123 min3Zxxx 123 123 123 123 28 3 325 0 xxx xxx xxx x xx 任意任意 例例7 123 max 3Zxxx 1234 1235 123 12453 28 3 325