线性规划线性规划(Linear Programming缩写LP )是数学规划的一个重要分支。
自1947年G. B. Dantzig提出求解线性规划单纯形方法以来，线性规划在理论上趋于成熟
目标函数约束条件被记为s.t .即subjectto(http://www.Sina.com/)，被称为线性规划问题。 线性规划的Matlab标准格式
[导出外链图像失败。 源站可能有防盗链机制。 我们建议您保存并直接上传图片。 (img-T01W3XxU-1633779106919 ) ) c :/users/23105/appdata/roaming/typo ra/typo ra
其中，c和x为n维的列向量，a、Aeq为适当维的矩阵，b、beq为适当维的列向量。
路线规划[导出外链图像失败。 源站可能有防盗链机制。 建议保存图片并直接上传。 (img-3XCl5pBy-1633779106921 ) c :/users/23105/appdata/roaming/typo ra/typo ra-user-images/images MATLAB 源站可能有防盗链机制。 我们建议您保存并直接上传图片。 (img-ioLtJwkS-1633779106923 ) ) c :/users/23105/appdata/roaming/typo ra/23105
目标函数及约束条件均为线性函数由所有可行解组成的集合表示为r。
如果整数计划中的部分或全部变量限制为整数，则称为整数计划。
在线性规划模型中，如果变量限制为整数，则称为整数线性规划。
解决方法分类：
分枝定界法——可求解纯整数或混合整数的线性规划。
将所有可行解空间反复分割为越来越小的子集称为分枝；
为每个子集内的解集合计算目标的下界。 这叫做边界
在每次分支时，边界超过已知可行解集目标值的子集不再分支，多数子集可以不考虑，这称为剪枝。
解决生产进度问题、旅游推销员问题、工厂选址问题、背包问题、分配问题等。 使用分支边界法求解整数规划(最大化)问题的步骤如下。
将求解的整数规划问题称为问题a，将与其对应的线性规划问题称为问题b。 要解决问题b，可以获得以下内容之一：
b中没有可行解，此时a中也没有可行解的情况下， b中有最佳解，且满足问题a的整数条件，b的最佳解为a的最佳解时，停止。 b具有最优解，但不满足问题a的整数条件。 将其目标函数值设定为z(up )。 用观察法寻找问题a的整数可行解，通常记为x(j )=0，j=1，…，n，加入探索，求出其目标函数值，z ) z(down )。 用z*表示问题a的最佳目标函数值时，z(up(z(*z ) down ) )重复。
第一步(分支第二步)各自的后续问题显示作为一个分支求解的结果，在与其他问题的求解结果中，找出最佳目标函数值最大的作为新的上界z(up )。 从满足整数条件的各分支中，将目标函数值最大的作为新的下界z[down]找到，如果没有作用的话z[down]不会改变。 步骤3 )与剪枝比较，如果各分枝的最佳目标函数中有小于z(down )的，则剪枝。 也就是说，以后不考虑。 z )如果大于down且不符合整数条件，则重复步骤1。 直到最后得到z*=z(down )。 得到最佳整数解x(j )，j=1，n。 切割平面法-可以求出纯或混合整数的线性规划。
枚举法-求解“0-1”整数规划
隐枚举法； 分枝枚举法。 匈牙利法-解决分配问题(“0-1”计划的特殊情况) ) ) )。
匈牙利算法主要用于解决有关可行解的若干问题。 http://www.Sina.com/(3358 www.Sina.com/)是特殊的http://www.Sina.com/
/strong>，它可以被划分为两个部分，每个部分内的点互不相连。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4G1QCaSM-1633779106926)(C:/Users/23105/AppData/Roaming/Typora/typora-user-images/image-20211009160212023.png)]匈牙利算法主要用来解决两个问题：求二分图的最大匹配数和最小点覆盖数。 一个二分图中的最大匹配数等于这个图中的最小点覆盖数。蒙特卡洛法—求解各种类型规划
蒙特卡罗方法是一种计算方法。原理是通过大量随机样本，去了解一个系统，进而得到所要计算的值。以概率统计理论为指导的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。 非线性规划如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。
如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。
由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点，但却并不一定是整个可行域上的全局最优解。
对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：
确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。凸集
在凸组合下闭合的仿射空间的子集。在欧氏空间中，凸集是对于集合内的每一对点，连接该对点的直线段上的每个点也在该集合内。令X是线性空间。如果对于X的子集S中的所有x和y，并且在区间[0,1]中的所有t，点(1-t)x+ty 也属于S，则S称为凸集。凸集的边界总是凸曲线。凸最小化是一个优化的子领域，研究了凸函数在凸集上的最小化问题。 用于凸集和凸函数属性研究的数学分支称为凸分析。性质 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xz9qcUh7-1633779106929)(C:/Users/23105/AppData/Roaming/Typora/typora-user-images/image-20211009162639341.png)] 凸包：矢量空间的每个子集A包含在最小的凸集（称为A的凸包）中，即包含A的所有凸集的交集。凸组合
凸组合是一类特殊的线性组合，是若干个点的某种特定意义下的非负线性组合。设向量{x(i)},i=1,2…,n，如有实数λ(i)>=0 ，且λ(1)+…+λ(n)=1 ，则称λ(1)x(1)+…+λ(n)x(n)为向量{x(i)} 的一个凸组合(凸线性组合）。凸函数
设 f (x) 为定义在 n 维欧氏空间 E(n) 中某个凸集 R 上的函数，若对任何实数α(0 <α <1) 以及 R 中的任意两点 x(1) 和 x(2) ，恒有f (αx(1) + (1−α)x(2) ) ≤αf (x(1) ) + (1−α) f (x(2) )则称 f (x)为定义在 R 上的凸函数。若对每一个α(0 <α <1) 和 x(1) ≠ x(2) ∈R 恒有f (αx(1) + (1−α)x(2) ) <αf (x(1) ) + (1−α) f (x(2) )则称 f (x)为定义在 R 上的严格凸函数。凸规划
假定其中 f (x)为凸函数，g(j)(x)( j =1,2,…,l) 为凸函数，这样的非线性规划称为凸规划。凸规划的可行域为凸集，其局部最优解即为全局最优解，而且其最优解的集合形成一个凸集。当凸规划的目标函数 f (x)为严格凸函数时，其最优解必定唯一（假定最优解存在）凸规划是一类比较简单而又具有重要理论意义的非线性规划一维搜索的方法
试探法（“成功—失败”，gtdxrk法，0.618 法等）插值法（抛物线插值法，三次插值法等）微积分中的求根法（切线法，二分法等）。二次插值法:
它的基本思想是：在搜索区间中，不断用低次（通常不超过三次）多项式来近似目标函数，并逐步用插值多项式的极小点来逼近最优解。解析法
梯度法（最速下降法） x*(k* +1) = x**k + t(k) p**k ,每一轮从点 x**k 出发沿最速下降方向 − ∇f (x**k ) 作一维搜索，来建立求解无约束极值问题的方法，称之为最速下降法。微积分的知识告诉我们，点 x**k 的负梯度方向p**k = −∇f (x**k ) ，是从点 x**k 出发使 f 下降最快的方向。称负梯度方向 − ∇f (x**k ) 为 f 在点 x**k 处的最速下降方向。 Newton 法变尺度法 它不仅是求解无约束极值问题非常有效的算法，而且也已被推广用来求解约束极值问题。它既避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著的优越性在 Matlab 工具箱中，用于求解无约束极值问题的函数有 fminunc 和 fminsearch
约束极值问题
带有约束条件的极值问题称为约束极值问题，也叫规划问题。二次规划 某非线性规划的目标函数为自变量 x 的二次函数，约束条件又全是线性的，就称这种规划为二次规划。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nllYVpm9-1633779106931)(C:/Users/23105/AppData/Roaming/Typora/typora-user-images/image-20211009172647008.png)]这里 H 是实对称矩阵， f ,b 是列向量， A 是相应维数的矩阵。Matlab 中求解二次规划的命令是[X,FVAL]= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS) 返回值 X 是决策向量 x 的值，返回值 FVAL 是目标函数在 x 处的值。 罚函数法 利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束最小化技术，简记为 SUMT (Sequential Unconstrained Minization Technique)。罚函数法求解非线性规划问题的思想是，利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。在 Matlab 优化工具箱中，用于求解约束最优化问题的函数有：fminbnd、fmincon、quadprog、fseminf、fminimax
fminbnd 函数：求单变量非线性函数在区间上的极小值 动态规划动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。
最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。
多阶段决策过程最优化问题的动态规划模型通常包含以下要素
阶段：通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。状态 状态（state）表示每个阶段开始时过程所处的自然状况它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。 决策：当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决（decision），在最优控制问题中也称为控制（control）。策略：决策组成的序列称为策略（policy）。状态转移方程：在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equation of state transition）表示这种演变规律指标函数和最优值函数 指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数，在 x（k） 给定时指标函数V(k ,n) 对 p(kn) 的最优值称为最优值函数（optimal value function） 最优策略和最优轨线递归方程 动态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子策略。建立起动态规划的数学模型：
将过程划分成恰当的阶段。正确选择状态变量 x（k） ，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合 X(k) 。选择决策变量u(k) ，确定允许决策集合U(k) (x(k) ) 。写出状态转移方程。确定阶段指标v(k) (x(k) ,u(k) ) 及指标函数V(kn) 的形式（阶段指标之和，阶段指标之积，阶段指标之极大或极小等）。写出基本方程即最优值函数满足的递归方程，以及端点条件。动态规划与静态规划的关系
动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条件下的函数极值问题。
静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。
动态规划可以看作求决策u1 ,u2 ,…,un 使指标函数V1n (x1,u1，u2 ,…,u**n ) 达到最优（最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解。
与静态规划相比，动态规划的优越性在于：
能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。能够利用经验提高求解效率。由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。动态规划的主要缺点是：
没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有m个取值，那么对于n 维问题，状态 x(k) 就有 m**n 个值，对于每个状态值都要计算、存储函数 f (k) (x（k） ) ，对于n 稍大的实际问题的计算往往是不现实的。典型问题的动态规划模型:
最短路线问题生产计划问题资源分配问题应用上的局限性。
> - 用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有m个取值，那么对于n 维问题，状态 x(k) 就有 m**n 个值，对于每个状态值都要计算、存储函数 f (k) (x（k） ) ，对于n 稍大的实际问题的计算往往是不现实的。
典型问题的动态规划模型:
最短路线问题生产计划问题资源分配问题