《【清华】Exp-08【GHOE】》由会员分享，可在线阅读，更多相关《【清华】Exp-08【GHOE】（8页珍藏版）》请在金锄头文库上搜索。
1、1 大学数学实验大学数学实验 实验8 线性规划实验8 线性规划 清 华 大 学 数 学 科 学 系清 华 大 学 数 学 科 学 系 优化问题三要素 优化问题三要素 决策变量决策变量 目标函数目标函数 约束条件约束条件 约 束 条 件 约 束 条 件决策变量决策变量 优化问题的一般形式优化问题的一般形式 n j i Dx ljxg mixhts xf 1 0 1 0 min 当最优解在可行域边界上取得时 不能用无约束优化方法求解 当最优解在可行域边界上取得时 不能用无约束优化方法求解 目标函数目标函数 约束优化的分类约束优化的分类 线性规划线性规划 LP 目标和约束均为线性函数目标和约束均为线
2、性函数 非线性规划非线性规划 NLP 目标或约束中存在非线性函数目标或约束中存在非线性函数 二次规划二次规划 QP 目标为二次函数 约束为线性目标为二次函数 约束为线性 整数规划整数规划 IP 决策变量决策变量 部分部分 为整数为整数 整数整数线性线性规划规划 ILP 整数整数非线性非线性规划规划 INLP 0 1规划规划整数决策变量只取 或 整数决策变量只取 或 n j i Dx ljxg mixhts xf 1 0 1 0 min 连 续 优 化 连 续 优 化 离 散 优 化 离 散 优 化 本实验基本内容本实验基本内容 2 基本原理和算法基本原理和算法 3 MATLAB实现实现 1 实
3、例及其数学模型实例及其数学模型 4 LINGO实现实现 确定每种食物的用量 以最小费用满足营养需求确定每种食物的用量 以最小费用满足营养需求 实例实例1 食谱问题食谱问题 A的需求增加的需求增加1单位 是否改变食谱 成本增加多少 营养需求 人 天 单位 是否改变食谱 成本增加多少 营养需求 人 天背景背景 8222795 5个 44g 鸡蛋222795 5个 44g 鸡蛋 60578903 5杯 178g 枣汁578903 5杯 178g 枣汁 519202530 7个 72g 胡萝卜19202530 7个 72g 胡萝卜 157961 2个 118g 香蕉7961 2个 118g 香蕉 10
4、9 6730 3个 138g 苹果 价格 美分 钙 9 6730 3个 138g 苹果 价格 美分 钙 mg 维生素维生素A IU 蛋白质蛋白质 g 单位食物单位食物 50g蛋白质蛋白质 4000IU维生素维生素A 1000mg钙钙 胡萝卜价格增胡萝卜价格增1美分 是否改变食谱 成本增加多少 美分 是否改变食谱 成本增加多少 实例实例1 食谱问题食谱问题 5种食品数量 种食品数量 x1 x2 x3 x4 x5 满足 需求 满足 需求 决策 变量 目标 函数 决策 变量 目标 函数 费用费用 约束 条件 约束 条件 非负约束非负约束0 51 xx L 54321 86051510 xxxxxzM
5、in 505 55 37 02 13 0 54321 xxxxx LP 4000279890202539673 54321 xxxxx 100022571976 9 54321 xxxxx 22571976 9 279890202539673 5 55 37 02 13 0 A x x1 x2 x3 x4 x5 T c 10 15 5 60 8 T b 50 4000 1000 T 0 min x bAxts xcz T 2 1桶 牛奶 桶 牛奶 3千克千克A1 12小时小时 8小时小时 4千克千克A2 或 获利 或 获利12元元 千克千克 获利获利8元元 千克千克 0 8千克千克B1 2小时
6、小时 1 5元元 1千克 获利 千克 获利22元元 千克千克 0 75千克千克B2 2小时小时 1 5元元 1千克 获利 千克 获利16元元 千克千克 制订生产计划 使每天净利润最大制订生产计划 使每天净利润最大 15元可增加元可增加1桶牛奶 应否投资 桶牛奶 应否投资 50桶牛奶桶牛奶 480小时 至多 小时 至多100公斤公斤A1 B1 B2的获利经常有的获利经常有10 的波动 对计划有无影响 的波动 对计划有无影响 实例实例2 奶制品生产销售计划奶制品生产销售计划 聘用临时工人增加劳动时间 工资最多每小时几元 聘用临时工人增加劳动时间 工资最多每小时几元 1桶 牛奶 桶 牛奶 3千克千克
7、 A1 12小时小时 8小时小时 4千克千克 A2 或 获利 或 获利12元元 千克千克 获利获利8元元 千克千克 0 8千克千克 B1 2小时小时 1 5元元 1千克千克 获利获利22元元 千克千克 0 75千克千克 B2 2小时小时 1 5元元 1千克千克 获利获利16元元 千克千克 出售出售x1 千克千克 A1 x2 千克千克 A2 x3千克千克 B1 x4千克千克 B2 原料 供应 劳动 时间 加工能力原料 供应 劳动 时间 加工能力 决策 变量 目标 函数 决策 变量 目标 函数 利润利润 约束 条件 约束 条件 非负约束非负约束0 61 xx L x5千克千克 A1加工加工B1 x
8、6千克千克 A2加工加工B2 654321 5 15 11622812xxxxxxzMax 50 43 6251 xxxx 48022 2 4 65 6251 xx xxxx 100 51 xx 附加约束附加约束 53 80 x x 64 750 x x LP 实例3 供应与选址实例3 供应与选址 某公司有6个建筑工地 位置坐标为 ai bi 单位 公里 水泥日用量di 单位 吨 i a1 258 750 55 7537 25 b1 250 754 7556 57 75 d3547611 现有 2 料场 位于 A 5 1 B 2 7 记 xj yj j 1 2 日储量 ej各有 20 吨 假设
9、 料场和工地之间有直线道路 目标 制定每天的供应计划 即从 A B 两料场分别 向各工地运送多少吨水泥 使总的吨公里数最小 线性规划模型 决策变量 线性规划模型 决策变量 ci j 料场料场j到工 地 到工 地i的运量 的运量 12维维 2 1 6 1 0 2 1 6 1 min 6 1 2 1 2 1 6 1 2 122 jic jec idcts byaxc ij jij i iij j ji ijijij 求解线性规划求解线性规划 LP 的基本原理的基本原理 基本模型基本模型 0 min max xbAxts Rxxczor nT mnmn RbRARc 二维线性规划的图解法二维线性规划
10、的图解法 一般线性规划的单纯形算法一般线性规划的单纯形算法 线性规划的敏感性分析线性规划的敏感性分析 线性规划的对偶问题线性规划的对偶问题 线性规划的其他算法线性规划的其他算法 二维线性规划的图解法二维线性规划的图解法 x2 x10 L1 L2 L3 z1 0 z2 2 z3 6 z4 10 z5 13 grad z x 起作用约束 起作用约束 L2 L3 最优解 最优解 4 1 最优值 最优值zmax 13 L1 L2 L3 0 1423 22 2 3max 21 21 21 21 21 xx xx xx xxts xxz 2 21 xx 3 求解求解LP的基本思想的基本思想 从可行域的某一
11、顶点开始 只需在有限多个顶点中 一个一个找下去 一定能得到 从可行域的某一顶点开始 只需在有限多个顶点中 一个一个找下去 一定能得到最优解最优解 LP的约束和目标函数均为线性函数的约束和目标函数均为线性函数 2维 可行域 维 可行域 线段组成的凸多边形线段组成的凸多边形 目标函数目标函数 等值线为直线等值线为直线 最优解最优解 凸多边形的某个顶点凸多边形的某个顶点 n维维 超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点 算法 怎样从一点转到下一点 尽快找到最优解 超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点 算法 怎样从一点转到下一点 尽快找到最优解 x2 x10 L1
12、L2 L3 x2 x10 L1 L2 L3 x2 x10 L1 L2 求解LP的特殊情形求解LP的特殊情形 L1 L2 L3 无可行解无可行解无最优解无最优解 无界无界 最优解不唯一最优解不唯一 321 4123Lxx 3 L无 x2 x10 L1 L2 L3 z c 0 1423 22 2 3max 21 21 21 21 21 xx xx xx xxts xxz 2 21 xx 321 413Lxx 线性规划的标准形和基本性质线性规划的标准形和基本性质 nmRA xbAxts xcz nm T 0 min 标 准 形 标 准 形 加入松弛变量加入松弛变量 剩余变量将不等式变为等式剩余变量将
13、不等式变为等式 0 0 1423 0 22 0003min 21 5521 4421 54321 xx xxxx xxxx xxxxxz 0 2 3321 xxxxts 0 1423 22 2 3max 21 21 21 21 21 xx xx xx xxts xxz 2 21 xx 假设 假设 A行满秩行满秩 b非负非负 0 1423 22 2 0003min 54321 521 421 321 54321 xxxxx xxx xxx xxxts xxxxxz 0 1423 22 2 54321 521 421 321 xxxxx xxx xxx xxx 对标准形求解 先求可行解 对标准形求
14、解 先求可行解 nmRA xbAxts xcz nm T 0 min 0 xbAx 满足 再在有限个可行解中寻找最优解再在有限个可行解中寻找最优解 1423 22 2 521 421 321 xxx xxx xxx 10023 01021 00111 A 可逆 B NB AAAA T NB T xxx bxAxAAx NNBB 54321 ppppp bAxx BBN 1 0 x2 x1O T B xpppA 14 2 2 0 0 543 T B xpppA 8 0 4 0 2 531 T B xpppA 16 0 3 1 0 532 O点点 Q点点 R点点 Q R 基基 本本 可行解可行解x
15、 Ax b x 0 xB 0 xN 0 T B xpppA 0 0 5 1 4 321 P点点 P AB 基基 矩阵矩阵 x 基基 本本 解解xB 基变量基变量xN 非基变量非基变量 可行域存在时 必是凸多面体 最优解存在时 必在可行域的顶点取得 基本可行解对应于可行域的顶点 LP基本性质LP基本性质 基本解数量不超过基本解数量不超过 LP的通常解法是单纯形法的通常解法是单纯形法 G B Dantzig 1947 最优解只需在有限个可行解 基本可行解 中寻找最优解只需在有限个可行解 基本可行解 中寻找 mnm n m n 4 选取初始基可行解 顶点 选取初始基可行解 顶点 判断当前解是否最优
16、判断当前解是否最优 选择进基和出基变量 选择进基和出基变量 防止迭代过程出现循环 防止迭代过程出现循环 单纯形法的基本思路单纯形法的基本思路 用迭代法从一个顶点 基可行解 转换到另一个顶 点 称为一次 用迭代法从一个顶点 基可行解 转换到另一个顶 点 称为一次旋转旋转 每一步转换只将一个非基变 量 指一个分量 变为基变量 称为 每一步转换只将一个非基变 量 指一个分量 变为基变量 称为进基进基 同时将 一个基变量变为非基变量 称为 同时将 一个基变量变为非基变量 称为出基出基 进基和出基 的确定需要使目标函数下降 至少不增加 进基和出基 的确定需要使目标函数下降 至少不增加 r x 0 最优最优 检验基可行解的最优性检验基可行解的最优性 0 1 0 0 0 bA x x x B N B bAcxcxcxcz B T BN T NB T B T1 0 0 0 0 N B c c c N B x x x可行解可行解 NNBBB NNBB xAAbAx bxAxAAx 11 xrz xAAccbAc xcxAAbAcz T NNB T B T NB T B N T NNNBB T B 0 1
