线性规划案例.ppt
Linear Programming,运 筹 学 课 件,线 性 规 划,线性规划问题 可行区域与基本可行解 单纯形算法 初始可行解 对偶理论 灵敏度分析 计算软件 案例分析,线 性 规 划 问 题,线性规划实例 生产计划问题 运输问题 线性规划模型 一般形式 规范形式 标准形式 形式转换 概念,某工厂用三种原料生产三种产品，已知的条件如表2.1.1所示，试制订总利润最大的生产计划,生 产 计 划 问 题,问 题 分 析,模 型,计 算 结 果,运 输 问 题,问 题 分 析,模 型,一 般 形 式,目标函数,约束条件,注 释,规 范 形 式,标 准 形 式,概 念,模 型 转 换,约束转换 实例,目标转换,变量转换,约 束 转 换,不等式变等式 不等式变不等式,等式变不等式,不 等 式 变 等 式,松弛变量,剩余变量,不等式变不等式,例2.1.3 把问题转化为标准形式,可行区域与基本可行解,图解法 可行域的几何结构 基本可行解与基本定理,图 解 法,例2.2.1 解线性规划,注 释,可能出现的情况： 可行域是空集 可行域无界无最优解 最优解存在且唯一，则一定在顶点上达到 最优解存在且不唯一，一定存在顶点是最优解,可行域的几何结构,基本假设 凸集 可行域的凸性,基 本 假 设,凸 集,可 行 域 的 凸 性,问 题,基 本 可 行 解 与 基 本 定 理,定义 基本定理 问题,基 本 可 行 解 定 义,基 本 定 理,问 题,单 纯 形 算 法,理论方法 算法步骤 单纯形表 算例,理 论 方 法,定理2.3.1,定 理 2.3.2,定 理 2.3.3,算 法 步 骤,单 纯 形 表,算 例,初 始 单 纯 形 表,迭 代 1,迭 代 2,初 始 解,两阶段法 大M法 说明,两 阶 段 法,基本思想 第一阶段：通过求解辅助问题的最优基可行 解得到原问题的初始基可行解。 第二阶段：求原问题的最优解 算例,辅 助 问 题,原 辅 助 题 问 与 题 的 关 系,求 辅 助 问 题 的 三 种 情 况,算 例,第 1 阶 段,第 1 阶 段,第 1 阶 段,第 1 阶 段,第 1 阶 段,第 2 阶 段,大 M 法,说 明,对 偶 理 论,对偶规划 对偶理论 对偶单纯形算法,对 偶 规 划,标准形式线性规划的对偶规划 规范形式线性规划的对偶规划 一般形式线性规划的对偶规划 实例,标准形式的对偶规划,规 范 形 式 的 对 偶 规 划,一般形式的对偶规划,实 例,对 偶 理 论,定 理 2.5.1,定 理 2.5.2,定 理 2.5.5,对偶单纯形算法,基本思想 算法过程 算例,基 本 思 想,单 纯 形 算 法,对 偶 单 纯 形,正 则 解,正则解,对偶可行解,正则解的单纯性表,规划无可行解,保持正则性,入基变量,否,算 法 过 程,初始正则解,是则停止,得最优解,选出基变量,检查 是否无可 行解,是则停止,否,无最优解,选入基变量,计算典式检验数,算 例,迭 代,迭 代,迭 代,灵 敏 度 分 析,概况 改变价值向量 改变右端向量,概 况,信息的不确定性 信息的变化： 价值向量市场变化 右端向量资源变化 系数矩阵技术进步 认知的误差 分析方法 静态分析- 比较静态分析-动态分析,改变价值向量,一般改变情况 改变非基变量的价值向量 改变基变量的价值向量 算例,一 般 改 变,非 基 变 量,基 变 量,算 例,改变右端向量,基本思想 算例,基 本 思 想,算 例,计 算 软 件,LinDo LinGo Matlab,LinDo,输入模型 求解 点击求解按钮 即可 结果,输 入 模 型,!注释内容，可用中文 !目标函数：最大-max,最小-min,大小写不分 max 3 x1+5 x2+4 x3 !约束，以subject to开始 subject to 2 x1+3 x2<=1500 2 x2+4 x3<=800 3 x1+2 x2 +5 x3<=2000 end,注 意 事 项,变量以字母开头，下标写在后面，系数与边量之间加空格 不等号为:=( ) , =, <=与 <等同 变量非负约束可省略 结束时以end标示,结 果,LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 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 2) 0.000000 1.050000 3) 0.000000 0.625000 4) 0.000000 0.300000,LinGo,输入模型 LinDo模式 LinGo模式 求解 点击求解按钮 即可 结果,LinDo 输 入 模 式,model: MAX=3*x1+5*x2+4*x3; 2*x1+3*x2<=1500; 2*x2+4*x3<=800; 3*x1+2*x2+5*x3<=2000; end,注意与LinDo的区别,目标函数中加等号 变量与系数之间用“*” Model:-end可省略,LinGo 模式,集 合 部 分,model: ！开始 sets: ！定义集合 ve/1.3/:c,x; co/1.3/:b; ma(co,ve):a; endsets ！注：集表达式：名称/成员/：属性 名称（初始集）：属性,定 义 数 据,data:！定义数据 c=3 5 4; b=1500 800 2000; a=2 3 0 0 2 4 3 2 5; Enddata ！注：数据的大小与集合定义中一致，分量中间用空格或逗号分开，数据结束后用分号；,调 用 函 数,max=sum(ve(j):c(j)*x(j); for(co(i):sum(ve(j):a(i,j)*x(j)<=b(i); 主要函数： for(set(set_index_list)|condition:expression) sum(set(set_index_list)|condition:expression) min(max)(set(set_index_list)|condition:expression),结 果,Global optimal solution found at iteration: 3 Objective value: 2675.000 Variable Value Reduced Cost C( 1) 3.000000 0.000000 C( 2) 5.000000 0.000000 C( 3) 4.000000 0.000000 X( 1) 375.0000 0.000000 X( 2) 250.0000 0.000000 X( 3) 75.00000 0.000000,B( 1) 1500.000 0.000000 B( 2) 800.0000 0.000000 B( 3) 2000.000 0.000000 A( 1, 1) 2.000000 0.000000 A( 1, 2) 3.000000 0.000000 A( 1, 3) 0.000000 0.000000 A( 2, 1) 0.000000 0.000000 A( 2, 2) 2.000000 0.000000 A( 2, 3) 4.000000 0.000000 A( 3, 1) 3.000000 0.000000 A( 3, 2) 2.000000 0.000000 A( 3, 3) 5.000000 0.000000,Row Slack or Surplus Dual Price 1 2675.000 1.000000 2 0.000000 1.050000 3 0.000000 0.6250000 4 0.000000 0.3000000,Scilab 函数,命令1：x,lagr,f=linpro(p,C,b ,x0) 命令2：x,lagr,f=linpro(p,C,b,ci,cs ,x0) 命令3：x,lagr,f=linpro(p,C,b,ci,cs,me ,x0) 命令4：x,lagr,f=linpro(p,C,b,ci,cs,me,x0 ,imp) 命令5： x1,crit=karmarkar(a,b,c,x0) 注意事项,命令1,问题形式 min p*x s.t. C*x <= b,x,lagr,f=linpro(p,C,b ,x0）,命 令 2,命 令 3,命 令 4,x,lagr,f=linpro(p,C,b,ci,cs,me,x0 ,imp) 问题形式 min p*x s.t. C(j,:) x = b(j), j=1,.,me C(j,:) x <= b(j), j=me+1,.,me+md ci <= x <= cs 指定初始可行解x0,命 令 5,x1,crit=karmarkar(a,b,c,x0) 问题形式 min c*x s.t. a*x = b x=0,注 意 事 项,命令2和3中x0可省略，但命令4和5中不可省略 向量都是列向量，参数的顺序不可换 命令3中等式约束必须在前面,人力资源分配问题,某个中型百货商场对售货人员（周工资200元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？,模 型 假 设,每天工作8小时，不考虑夜班的情况； 每个人的休息时间为连续的两天时间； 每天安排的人员数不得低于需求量，但可以超过需求量,问 题 分 析,因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用； 方案：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。 变量：每天开始休息的人数 约束条件 ： 1.每人休息时间2天，自然满足。 2. 每天工作人数不低于需求量，第i天工作的人数就是从第i-2天往前数5天内开始工作的人数，所以有约束：,3.变量非负约束：,目标函数：总费用最小，总费用与使 用的总人数成正比。由于每个人必然在 且仅在某一天开始休息，所以总人数等 于,模 型,计 算,注 解,该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。 定义整数变量用函数gin(x1) gin(x7); 0-1整数变量为bin(x1),配 料 问 题,某化工厂要用三中原料混合配置 三种不同规格的产品各产品的规格 单价如表1，,问如何安排生产使得生产利润最大？,原料的单价与每天最大供应量如表2,配 料 问 题 案 例,问题 问题分析 模型 求解 结果分析,问 题 分 析,变量 约束条件 目标函数,变 量,生产计划就是要确定每天生产三种产品的数量以及非中产品中三中原料的数量。而由于每种产品的数量等于三种原料数量之和，所以只要确定每天生产三种产品分别含有的原料数量即可。所以变量就是每天生产三种产品所用的原料数，设用于生产第 i 种产品的第 j 种原料数为,约 束 条 件,规格约束,资源约束,约 束 条 件,目标函数,总产值,总成本,总利润=总产值-总成本,模 型,求 解,
