线性规划 —数学建模与系统仿真 主讲:王晓峰 E-mail:xfwang8280126.com
线 性 规 划 ——数学建模与系统仿真 主讲：王晓峰 E-mail:xfwang828@126.com
1.基本概念 ◆什么是最优化? 最优化模型 >最优化模型的分类 ◆如何得到最优解? 常用求解方法(算法) 常用求解软件 2021/12/12
◆什么是最优化？ ➢ 最优化模型 ➢ 最优化模型的分类 ◆如何得到最优解? ➢ 常用求解方法（算法） ➢ 常用求解软件 1.基本概念 2021/12/12
引例1:有边长为3m的正方形铁板,在四个角剪去 相等的正方形以制成方形无盖水槽,问如何剪法使 水槽的容积最大? 这是一个优化问题,首先确定优化的目标是什么, 寻求的决策是什么,决策受到哪些条件的限制(如 果有的话),然后用数学工具(变量,函数,常数 等)表示出来
引例1：有边长为3m的正方形铁板，在四个角剪去 相等的正方形以制成方形无盖水槽，问如何剪法使 水槽的容积最大？ 这是一个优化问题，首先确定优化的目标是什么， 寻求的决策是什么，决策受到哪些条件的限制（如 果有的话），然后用数学工具（变量，函数，常数 等）表示出来
引例:有迦长为3m的正方形铁板,在四个角剪去相 等的正方形以制成方形无盖水槽,问如何剪浤使水 槽的容积最大? 用数学工具描述: 决策(如何剪法):x表示剪去的正方形边长决策变量 目标(容积最大):maxV=(3-2x)2x 目标函数 限制(边长3m):0<x<1.5 约束条件
引例：有边长为3m的正方形铁板，在四个角剪去相 等的正方形以制成方形无盖水槽，问如何剪法使水 槽的容积最大？ 决策（如何剪法）：x表示剪去的正方形边长 用数学工具描述： x 目标（容积最大）：max V= (3-2x) 2x 限制（边长3m): 0<x<1.5 如何剪法 边长为3m 容积最大 决策变量 目标函数 约束条件
该问题用数学的语言描述为 max v=(3-2x)x st.0<x<1.5 即为一个简单的优化模型,归结为微积分中的 极值问题
max V= (3-2x) 2x s.t. 0<x<1.5 该问题用数学的语言描述为 即为一个简单的优化模型，归结为微积分中的 极值问题
什么是最优化? 最优化是从所有可能方案中选择最合理的一种 以达到最优目标的学科。 2.在各种科学问题、工程问题、生产管理、社会 经济问题中,人们总是希望在有限的资源条件 下,用尽可能小的代价,获得最大的收获。 3.最优化已经广泛的渗透到工程、经济、电子技 术等领域
1.最优化是从所有可能方案中选择最合理的一种 以达到最优目标的学科。 2.在各种科学问题、工程问题、生产管理、社会 经济问题中，人们总是希望在有限的资源条件 下，用尽可能小的代价，获得最大的收获。 3.最优化已经广泛的渗透到工程、经济、电子技 术等领域。 什么是最优化？
最优化模型的一般描述 般形式:minf(X) g(X)≥0i=1,2 st h、(X)④b 其中X=(x,x2…,x)∈R"为决策变量向量,fg1,h 是定义在R上的实值函数f(X)为目标函数,gX)>=0, bX)=0为约束条件。 其它情况:求目标函数的最大值或约束条件为小于等于零 的情况,都可通过取其相反数化为上述一般形式
最优化模型的一般描述 一般形式: （1） 其中 为决策变量向量， 是定义在 Rn 上的实值函数. f（X）为目标函数，gi (X)>=0, hj (X)=0为约束条件。 min f (X ) ( ) ( ) 0 1,2,...,m; . . 0 1,2,..., . i j g X i s t h X j l = = = ( 1 2 , , , ) T n X x x x R = n gi hj f , , 其它情况: 求目标函数的最大值或约束条件为小于等于零 的情况，都可通过取其相反数化为上述一般形式． 7
规划模型的分类 ●根据是否存在约束条件:有约束问题和无约束问题 根据设计变量的性质:静态问题和动态问题。 ●根据目标函数和约束条件表达式的性质:线性规划,非 线性规划,二次规划,多目标规划等。 ●根据设计变量的允许值:整数规划,0-1整数规划。 ●根据变量具有确定值还是随机值:确定规划和随机规划。 线性规划:目标函数和约束条件都是线性的则称为线 性规划。 非线性规划:目标函数和约束条件如果含有非线性的 ,则称为非线性规划。 2021/12/12
2021/12/12 线性规划：目标函数和约束条件都是线性的则称为线 性规划。 规划模型的分类 ⚫根据是否存在约束条件：有约束问题和无约束问题。 ⚫根据设计变量的性质：静态问题和动态问题。 ⚫根据目标函数和约束条件表达式的性质： 线性规划，非 线性规划，二次规划，多目标规划等。 ⚫根据设计变量的允许值：整数规划，0-1整数规划。 ⚫根据变量具有确定值还是随机值：确定规划和随机规划。 非线性规划：目标函数和约束条件如果含有非线性的 ，则称为非线性规划
规划模型的求解 minf(r) g1(X)≥0i=12 s t b(x)=07 (2) 定义1:记D={和g(X)=,h(X)=0},即D为满足 约束条件(2)的变量组成的集合,称为最优化 问题的可行域。若X∈D,则称其为可行解。 定义2:X*∈D,且对任意的X∈D,都有f(X)=F(X*), 称X*为该最优化问题的最优解
规划模型的求解 9 min f (X ) ( ) ( ) 0 1,2,...,m; . . 0 1,2,..., . i j g X i s t h X j l = = = （1） （2） 定义2：X * D,且对任意的X D,都有f(X) f(X*)， 称X *为该最优化问题的最优解。 定义1：记D={X|gi (X) 0, hj (X)=0}，即D为满足 约束条件（2）的变量组成的集合，称为最优化 问题的可行域。若X D,则称其为可行解。
优化方法 针对不同的模型有不同的算法,如求解线性规划 的单纯形法;求解非线性规划的最速下降法,牛顿法 罚函数法等;求解整数线性规划的分支定界法和割平 面法。 常用软件 Lindo/ Lingo:专业,强大 Matlab:常用,有些功能使用不便(如整数规划) ●1 stopt:易写程序 ●EXce:直观,但有限制(如约束方式)
⚫Lindo/Lingo：专业，强大 ⚫Matlab：常用，有些功能使用不便（如整数规划） ⚫1stopt: 易写程序 ⚫Excel：直观，但有限制（如约束方式） 二. 常用软件 针对不同的模型有不同的算法，如求解线性规划 的单纯形法；求解非线性规划的最速下降法，牛顿法， 罚函数法等；求解整数线性规划的分支定界法和割平 面法。 一. 优化方法