优化建 1桶 12小时 3公斤A1→获利24元公斤 牛奶或 8小时4公斤A2 获利16元/公斤 每天50桶牛奶时间480小时至多加工100公斤A1 决策变量x1桶牛奶生产A1x2桶牛奶生产A2 目标函数获利24×3x1获利16×4x2 每天获利Maxz=72x1+64x2 线性 原料供应 x,+x<50 规划 约束条件劳动时间 12x1+8x,≤480 模型 加工能力 3x,<100 (LP 非负约束 XI 0
优 化 建 模 1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 24×3x1 获利 16×4 x2 原料供应 x1 + x2 50 劳动时间 12x1 +8x2 480 加工能力 3x1 100 决策变量 目标函数 72 1 64 2 每天获利 Max z = x + x 约束条件 非负约束 x1 , x2 0 线性 规划 模型 (LP) 时间480小时 至多加工100公斤A1 每天 50桶牛奶
优化建 模型分析与假设 线性规划模型 比x对目标函数的 A1,A2每公斤的获利是与各 例“贡献”与x取值 自产量无关的常数 性 x对约束条件的每桶牛奶加工出A1,A2的数量 “贡献”与x,取值和时间是与各自产量无关的常 数 可x对目标函数的 A1,A2每公斤的获利是与相 加贡献”与x取值互产量无关的常数 性x,对约束条件的每桶牛奶加工出A,A2的数量和 “贡献”与x取值时间是与相互产量无关的常数 连续性x取值连续 加工A1,A2的牛奶桶数是实数
优 化 建 模 模型分析与假设 比 例 性 可 加 性 连续性 xi对目标函数的 “贡献”与xi取值 成正比 xi对约束条件的 “贡献”与xi取值 成正比 xi对目标函数的 “贡献”与xj取值 无关 xi对约束条件的 “贡献”与xj取值 无关xi取值连续 A1 ,A2每公斤的获利是与各 自产量无关的常数 每桶牛奶加工出A1 ,A2的数量 和时间是与各自产量无关的常 数 A1 ,A2每公斤的获利是与相 互产量无关的常数 每桶牛奶加工出A1 ,A2的数量和 时间是与相互产量无关的常数 加工A1 ,A2的牛奶桶数是实数 线性规划模型
优化建 模型求解图解法 x1+x,≤50口 x1+x2=50 约束条件 12x+8x2≤480口l2:12x+8x2=480 B 3x,<100 3:3x1 100 Z=3600 ≥0 0.l 0 目标 max 72x1+64x2 I5 D x1 函数 =02=2400 zc(常数)~等值线在B(20,30)点得到最优解 目标函数和约束条件是线性函数 最优解一定在凸多边 可行域为直线段围成的凸多边形形的某个顶点取得。 目标函数的等值线为直线
优 化 建 模 模型求解 图解法 x1 x2 0 A B C D l1 l2 l3 l4 l5 x1 + x2 50 12x1 +8x2 480 3x1 100 x1 , x2 0 约 束 条 件 l 1 : x1 + x2 = 50 l 2 :12x1 +8x2 = 480 l 3 :3x1 =100 l 4 : x1 = 0, l 5 : x2 = 0 72 1 64 2 Max z = x + x 目标 函数 Z=0 Z=2400 Z=3600 z=c (常数) ~等值线 c 在B(20,30)点得到最优解 目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边 形的某个顶点取得
优化建 LP的约束和目标函数均为线性函数 2维 n维 可行域线段组成的凸多边形超平面组成的凸多面体 目标函数等值线为直线等值线是超平面 最优解凸多边形的某个顶点凸多面体的某个顶点 求解LP的基本思想 思路:从可行域的某一顶点开始,只需在有限多个 顶点中一个一个找下去,一定能得到最优解。 LP的通常解法是单纯形法(G.B. Dantzig,1947)
优 化 建 模 求解LP的基本思想 思路：从可行域的某一顶点开始，只需在有限多个 顶点中一个一个找下去，一定能得到最优解。 LP的约束和目标函数均为线性函数 2维 可行域 线段组成的凸多边形 目标函数 等值线为直线 最优解 凸多边形的某个顶点 n维 超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点 LP的通常解法是单纯形法(G. B. Dantzig, 1947)