第2章线性规划 22模型与基本定理 20211/27
2021/1/27 第2章 线性规划 2.2 模型与基本定理
第2章线性规划 ●线性规划问题 ●可行区域与基本可行解 单纯形算法 ●初始可行解和两阶段法 ●对偶理论和对偶单纯形法 ●灵敏度分析 ●计算软件 ●案例分析 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 2 第2章 线性规划 线性规划问题 可行区域与基本可行解 单纯形算法 初始可行解和两阶段法 对偶理论和对偶单纯形法 灵敏度分析 计算软件 案例分析
§2.1线性规划问题 1.线性规划实例 1.生产计划问题 2.运输问题 2.线性规划模型 1.一般形式 2.规范形式 3.标准形式 4.形式转换 5.概念 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 3 §2.1 线性规划问题 1. 线性规划实例 1. 生产计划问题 2. 运输问题 2. 线性规划模型 1. 一般形式 2. 规范形式 3. 标准形式 4. 形式转换 5. 概念
生产计划问题 某工厂用三种原料生产三种产品,给定三种原料的可用量, 试制订总利润最大的生产计划 单位产品所需原料数产品 产品 产品 原料可用量 量(公斤) Q1 Q2 (公斤/日) 原料P1 1500 原料P2 2033 3225 0454 800 原料P3 2000 单位产品的利润 (千元) 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 4 某工厂用三种原料生产三种产品，给定三种原料的可用量， 试制订总利润最大的生产计划 单位产品所需原料数 量（公斤） 产品 Q1 产品 Q2 产品 Q3 原料可用量 （公斤/日） 原料P1 2 3 0 1500 原料P2 0 2 4 800 原料P3 3 2 5 2000 单位产品的利润 （千元） 3 5 4 生产计划问题
问题分析 可控因素:每天生产三种产品的数量,分别设为x1,x2,x3 目标:每天的生产利润最大。利润函数3x1+5x2+4x3 受制条件: ●每天原料的需求量不超过可用量: ■原料1:2x1+3x2≤1500 原料2:2x2+4x3≤800 ■原料3:3x1+2x2+5x3≤2000 ●蕴含约束:产量为非负数x1,x2,x320 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 5 可控因素：每天生产三种产品的数量，分别设为 x1, x2, x3。 目标：每天的生产利润最大。利润函数 3x1 + 5x2 + 4x3。 受制条件： ⚫每天原料的需求量不超过可用量： ◼原料 1：2x1 + 3x2 1500 ◼原料 2：2x2 + 4x3 800 ◼原料 3：3x1 + 2x2 + 5x3 2000 ⚫蕴含约束：产量为非负数 x1 , x2 , x3 0 问题分析
线性规划模型(LP) max 3x,+5x2+4* st 2x1+3x,≤1500 2r,+4x,<800 3r,+2x,+5x,<2000 x,≥0 192,3 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 6 max 3 1 5 2 4 3 x + x + x s.t.2x1 + 3x2 1500 2x2 + 4x3 800 3x1 + 2x2 + 5x3 2000 x1 , x2 , x3 0 线性规划模型(LP)
计算结果 OBJECTIVE FUNCTION VALUE 2675.000 VARIABLE VALUE REDUCED COST XI 375000000 0.000000 250.000000 0.000000 75000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 0.000000 1.050000 0.000000 0.625000 0.000000 0.300000 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 7 OBJECTIVE FUNCTION VALUE 2675.000 VARIABLE VALUE REDUCED COST X1 375.000000 0.000000 X2 250.000000 0.000000 X3 75.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 1) 0.000000 1.050000 2) 0.000000 0.625000 3) 0.000000 0.300000 计算结果
运输问题( Hitchcock问题) 实例:(1)一个制造厂要把若干单位的同一种产品从 两个仓库A;i=1,2发送到零售点B;j=1,2,3,4。 (2仓库A能供应的产品数量为4;=12,零售点B 所需要的产品的数量为b=12,34。 (假设总供和总需求量b 相等,且已知 从仓库A运一个单位产品往B的运价为C。 询问:应如何组织运输才能使总运费最小? 2021/1/27 山东大学软件学院 8
2021/1/27 山东大学 软件学院 8 实 例：(1)一个制造厂要把若干单位的同一种产品从 两个仓库 Ai ;i = 1,2发送到零售点 Bj ; j = 1,2,3,4 。 (2)仓库 Ai 能供应的产品数量为 ai ;i =1,2 ，零售点 Bj 所需要的产品的数量为bj ; j =1,2,3,4。 (3)假设总供给量= 2 i 1 ai 和总需求量= 4 j 1 bj 相等，且已知 从仓库 Ai 运一个单位产品往 Bj 的运价为 ij c 。 询问：应如何组织运输才能使总运费最小？ 运输问题（Hitchcock问题）
问题分析 可控因素:从仓库4运往B的产品数量设为x,1≤i≤2, 1≤j≤4 目标:总运费最小。费用函数 ∑∑Cx i=l j=l 约束条件:从每个仓库运出总量不超过其可用总量, 运入每个零售点的数量不低于其需求量。 由于总供给量等于总需求量,所以都是等号。即 x;+x2+xa3+x;4=1;i=1,2 x1+x2=b;j=1,2,3,4 蕴含约束:数量非负x≥0;i=12,=1,2,3,4 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 9 可控因素：从仓库 Ai 运往 Bj 的产品数量设为 xij, 1 i 2, 1 j 4。 目标：总运费最小。费用函数= = 2 1 4 i j 1 ij xij c 约束条件：从每个仓库运出总量不超过其可用总量， 运入每个零售点的数量不低于其需求量。 由于总供给量等于总需求量，所以都是等号。即 xi1 + xi2 + xi3 + xi4 = ai ;i = 1,2 x1 j + x2 j = bj ; j = 1,2,3,4 蕴含约束：数量非负 xi j 0;i = 1,2, j = 1,2,3,4 问题分析
运输问题的LP mm∑∑cx S t x1+x2+x3+x4=a1,i=1,2 + b 1.2.3.4 i=1,2,j=1,2,3,4 说明:当变量为整数变量、a;和b,都等于1时,运输 问题即变为二分图上的最小权重匹配问题,称为 Assignment(指派)问题。 可证明,最小权重匹配问题和最大权重匹配问题是 等价的。 2021/1/27 山东大学软件学院 10
2021/1/27 山东大学 软件学院 10 0, =1,2, =1,2,3,4 + = , =1,2,3,4 s.t. + + + = , =1,2 min 1 2 1 2 3 4 2 =1 4 =1 x i j x x b j x x x x a i c x i j j j j i i i i i i j i j i j ≥ ∑∑ 运输问题的LP 说明：当变量为整数变量、ai 和 bj 都等于1时，运输 问题即变为二分图上的最小权重匹配问题，称为 Assignment（指派）问题。 可证明，最小权重匹配问题和最大权重匹配问题是 等价的