精华内容
下载资源
问答
  • 线性规划线性规划 凸优化
    优化问题涉及关键词:
    凸优化、凸锥、凸集、线性规划、非线性规划(np)、拉格朗日chengzi、hessian矩阵、泰勒展开式、梯度、方向导数、牛顿法、凸二次优化、局部最小化、随机梯度、最速梯度、批量梯度、kkt条件、等高线 、共轭梯度、二次型、二次型矩阵、对偶问题


    一,前置条件:需要补充一下知识,才开启下面内容:

    方向导数 与 梯度的概念

    线性规划

    hession矩阵

    泰勒展开式

    共轭

    ————————————————————————————————————————————————
    二,凸集:
    http://www.hanlongfei.com/%E5%87%B8%E4%BC%98%E5%8C%96/2015/05/22/convexset/


    ————————————————————————————————————————————————

    三,线性规划求解:

    可以转化为线性规划对偶方式:http://blog.csdn.net/chunyun0716/article/details/52423991

    求解:
    无约束求解:导数、求极值
    有约束求解:
    1,图解法——最为简单直观,不需要转化为标准型
    2,单纯形表法:
        a,需要转化为标准型:min到max,将不等式变为等式:增加松弛变量
        b,找出所有基解,判断是否是基础可行解,并比较求出最大的那个

    ————————————————————————————————————————————————
    四,非线性规划内的凸优化求解:

    也可以转化为对偶方法:http://blog.csdn.net/chunyun0716/article/details/52423991

    1,无约束:(无论是否是凸函数、还是非凸函数均可使用)
    原理:需要先理解方向导数、梯度概念;
    方法:
    最速梯度下降(需要方向导数、梯度知识、偏导数原理),
    牛顿法(泰勒展开式知识、需要hession矩阵、偏导数原理、对称矩阵、二次型),
    随机梯度(由最速梯度衍生),
    批量梯度(由最速梯度衍生),
    共轭梯度(由最速梯度衍生、共轭概念、共轭矩阵)

    2,等式约束(限凸函数):拉格朗日乘子(需要等高线、法向量知识)将等式有约束变为无约束,之后使用无约束方法求解,拉格朗日乘子原理请查看:https://www.zhihu.com/question/38586401。

    3,不等式约束(需要满足kkt条件):kkt条件(广义拉格朗日乘子),原理:https://www.zhihu.com/question/23311674,如果求解困难,可考虑转化为拉格朗日对偶,之后通过无约束方法求解。

    4,对于有约束的优化问题,通过拉格朗日法可以将其转变为等价的无约束优化问题。在这个过程中,新构造的拉格朗日函数存在好玩的对偶性质,从而衍生出了对偶问题。原问题与对偶问题之间的特殊性质,为我们

    研究优化问题提供了新的方向和方法。因此,这部分的思路是:对4.1定义的优化问题,通过拉格朗日法构造拉格朗日函数,从而生成原问题Primal problem和对偶问题Dual problem,然后介绍一些引理,揭示原问题

    与对偶问题之间的关系。拉格朗日对偶问题,详情查看:https://www.cnblogs.com/90zeng/p/Lagrange_duality.html
    ————————————————————————————————————————————————

    五,凸优化:
    凸优化包含:线性规划 与 目标函数与条件函数都是凸函数的 非线性规划。
    详情查看:https://www.zhihu.com/question/24641575/answer/164397294

    凸优化特性:
    a,局部最优解=全局最优解
    b,效率高
    c,是目前科技比较确定的可以求解的非线性规划方式,
    d,许多非凸问题通过一定的手段,要么等价地化归为凸问题,要么用凸问题去近似、逼近。典型的如几何规划、整数规划,它们本身是非凸的,但是可以借助凸优化手段去解,这就极大地扩张了凸优化的应用范围。
    e,在非凸优化中,凸优化同样起到很重要的作用    1)当你要解决一个非凸优化问题时,可以先试图建立一个简化多凸优化模型,解出来以后作为非凸问题的一个起始点。    2)很多非凸优化问题的启发式算法的基础都是基于凸优化    3)你可以先建立非凸优化的松弛问题,使用凸优化算法求解,作为非凸优化问题的上限或下限(bound)


    求解凸函数的极小值(convex minimization)和凹函数的极大值(concave maximization)都是凸优化问题(convex optimization problem)。

    凸优化之所以‘容易’是因为任何可证明的局部最优解(Local Optimal Solution)都同时为全局最优解(Global Optimal Solution)。

    凸优化理论中最重要的工具是Lagrange对偶。近些年来关于凸问题的研究非常透彻,以至于只要把某一问题抽象为凸问题,就可以近似认为这个问题已经解决了。

    ————————————————————————————————————————————————

    六,关于非凸非线性规划求解:

    解决一个非凸优化问题时,可以先试图建立一个简化的多凸优化模型,解出以后作为非凸问题的一个起始点,很多非凸优化问题的启发式算法的基础都是基于凸优化,可以先建立非凸


    优化的松弛问题,使用凸优化算法求解,然后作为非凸优化问题的上限或下限

    a,先松弛,例如,某问题有一约束为 x^2+bx+c=0 ,就不构成一个凸集,但等价于 x^2+bx+c<= 0 和 x^2+bx+c>= 0 ,前一个不等式即构成凸集,因此我们可以将后一个不等式从约束中去除,就得到原问题的一个凸

    优化松弛问题。
    b,利用广义拉格朗日乘子 以及 拉格朗日对偶简化,
    c,通过凸优化的无约束条件规划求解。

    展开全文
  • Python关于线性规划问题

    千次阅读 2019-10-24 20:17:40
    相关函数:linprog()函数 函数功能: 用于寻找目标函数的最小值(如果求最大值需做相应变化) 注意事项: 1.目标函数f要写成列矩阵的形式 ... 2.... 3.... 参数1:所求目标函数未知数的系数 ...

    相关函数:linprog()函数

    函数功能:

        用于寻找目标函数的最小值(如果求最大值需做相应变化)

    注意事项

    • 1.目标函数f要写成列矩阵的形式

    • 2.约束要写成 <= 的形式

    • 3.函数是为求最小值设置的

     

    参数解释:

        参数1:所求目标函数未知数的系数                                           {一维数组}

        参数2 :A_up,此参数为不等式包含未知数一侧  未知数的系数  { 二维数组}

        参数3:B_up,此参数为不等式不包含未知数一侧  的数值         {一维数组}

        参数4:A_eq,此参数为等式 包含未知数一侧   未知数的系数    {二维数组}

        参数5:B_eq ,此参数为等式 不包含未知数一侧  的数值             {一维数组}

        参数6:每个系数的限制

    样例:

     

    import numpy as np
    from scipy import optimize as op
    np.set_printoptions(suppress=True)
    z = np.array([4, 3])
    A_ub = np.array([[2, 1], [1, 1]])
    B_ub = np.array([10, 8])
    x1 = (0, 8)
    x2 = (0, 7)
    res = op.linprog(-z, A_ub, B_ub, bounds = (x1,x2))#由于求解最大值,所以此处为-z,答案就是相反数
    print(res)

    结果:

    ***Repl Closed***
         con: array([], dtype=float64)
         fun: -25.9999999991197               # 最终结果
     message: 'Optimization terminated successfully.'
         nit: 5
       slack: array([0., 0.])
      status: 0
     success: True
           x: array([2., 6.])               #x1和x2的值
    
    ***Repl Closed***

    样例2:

    要点:

    不等式1为  大于等于,应该转换为小于等于:   -2X1 + 5X2 - X3 <= -10

    import numpy as np
    from scipy import optimize as op
    np.set_printoptions(suppress=True)
    z = np.array([2, 3, -5])
    A_up = np.array([[-2, 5, -1], [1, 3, 1]])
    B_up = np.array([-10, 12])
    A_eq = np.array([1, 1, 1])
    B_eq = np.array([7])
    x1 = (0, 7)
    x2 = (0, 7)
    x3 = (0, 7)
    res = op.linprog(-z, A_up, B_up, A_eq, B_eq, bounds=(x1, x2, x3))
    print(res)

    运行结果:

    ***Repl Closed***
         con: array([], dtype=float64)
         fun: -14.571428509517212                  #相反数即为所求最大值
     message: 'Optimization terminated successfully.'
         nit: 5
       slack: array([0.00000022, 3.85714293, 0.00000001])
      status: 0
     success: True
           x: array([6.42857145, 0.57142854, 0.        ])
    
    ***Repl Closed***

     

    展开全文
  • 求大佬帮忙弄个程序 1.将11个点走完,求最短路程 2.时间的条件约束下求
    求大佬帮忙弄个程序
    

    1.将11个点走完,求最短路程
    在这里插入图片描述

    在这里插入图片描述
    2.时间的条件约束下求
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 线性规划

    千次阅读 2019-07-11 21:12:20
    目的:学会用matlab、lingo软件求解线性规划问题。 二、实验要求: 1.熟悉线性规划问题的数学建模; 2.会用matlab、 lingo软件求解线性规划问题; 3.掌握线性规划的灵敏度分析。 三、实验内容: 1、求解下列线性规划...

    目的:学会用matlab、lingo软件求解线性规划问题。
    二、实验要求:
    1.熟悉线性规划问题的数学建模;
    2.会用matlab、
    lingo软件求解线性规划问题;
    3.掌握线性规划的灵敏度分析。
    三、实验内容:
    1、求解下列线性规划问题:
    (1) 给出lingo原始代码;
    (2) 计算结果(包括灵敏度分析,求解结果粘贴);
    (3) 回答下列问题:a) 最优解及最优目标函数值是多少;
    b) 资源的对偶价格各为多少,并说明对偶价格的含义;
    c) 为了使目标函数值增加最多,让你选择一个约束条件,将它的常数项增加一个单位,你将选择哪一个约束条件?这时目标函数值将是多少?
    d) 对x2的目标函数系数进行灵敏度分析;e) 对第2个约束的约束右端项进行灵敏度分析;f) 结合本题的结果解释“Reduced Cost”的含义
    2、 请写出调用函数linporg求解下述问题的matlab源代码,求解结果粘贴,并对结果分析。
    (1):matlab代码

    f=[3;2;1];
    A=[1 1 1;-1 0 1;0 -1 1];
    b=[6;-4;-3];
    lb=[0;0;0];
    [x,z]=linprog(f,A,b,[],[],lb,[])

    运行结果如下:

    Linprog stopped because
    no point satisfies the constraints.

    (2):matlab代码

    f=[-2;-2];
    A=[-1 1;-0.5 1];
    b=[1;2];
    lb=[0;0];
    [x,z]=linprog(f,A,b,[],[],lb,[])

    运行结果如下:

    Problem is unbounded.
    (3):matlab代码

    f=[1;-2];
    A=[-1 -1;1 -1;0 1];
    b=[-2;-1;3];
    lb=[0;0];
    [x,z]=linprog(f,A,b,[],[],lb,[])

    运行结果如下:

    Optimal solution found.

    x =
    0
    3
    z =
    -6
    (4):matlab代码

    f=[-1;-2;0;0;0];
    Aeq=[1 0 1 0 0;0 1 0 1 0;1
    2 0 0 1];
    beq=[4;3;8];
    lb=[0;0;0;0;0];
    [x,z]=linprog(f,[],[],Aeq,beq,lb,[])

    运行结果如下:

    Optimal solution found.
    x =
    4.0000
    2.0000
    0
    1.0000
    0
    z =
    -8

    3、(任务分配问题)某车间有甲、乙两台机床,可用于加工三种工件。假定这两台车床的可用台时数分别为800和900,三种工件的数量分别为400、600和500,且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。
    生产的工件3的件数为 (件),设乙生产的工件1的件数为(件),生产的工件2的件数为 (件),生产的工件3的件数为(件),设加工费用为W(元)。

       则线性规划如下:
    
       Min W=13+9+10+11+12+8
    

    (2)试选一数学软件计算上述模型,并给出程序源代码和计算结果报告。

    解:matlab代码:

    f=[13 9 10 11 12 8];
    A=[0.4 1.1 1 0 0 0;0 0 0 0.5 1.2 1.3];
    b=[800 900];
    Aeq=[1 0 0 1 0 0;0 1 0 0 1 0;0 0 1 0 0 1];
    beq=[400 600 500];
    LB=[0 0 0 0 0 0];
    [x,fval,exitflag]=linprog(f,A,b,Aeq,beq,LB)

    运行结果:

    Optimization
    terminated.

    x =
    0.0000
    600.0000
    0.0000
    400.0000
    0.0000
    500.0000
    val =.3800e+04];
    b=[800 900];
    Aeq=[1 0 0 1 0 0;0 1 0 0 1 0;0 0 1 0 0 1];
    beq=[400 600 500];
    LB=[0 0 0 0 0 0];
    [x,fval,exitflag]=linprog(f,A,b,Aeq,beq,LB)

    运行结果:
    Optimization
    terminated.

    x = 0.0000
    600.0000
    0.0000
    400.0000
    0.0000
    500.0000

    val =
    1.3800e+04
    1

    由运行结果得,此线性规划有最优值13800(元),满足最优解的=0,=600,=0,=400,=0,=500,即在甲机床上加工的工件2为600件,不加工的工件1和工件2,在乙机床上加工的工件1为400件,加工的工件3为500件,且不加工工件2时,其加工费用最低,为13800元。

    展开全文
  • MATLAB规划问题——线性规划和非线性规划

    万次阅读 多人点赞 2017-01-16 10:07:56
    1.线性规划线性规划问题的最优解有两种方法,一种方法是使用linprog命令,另一种是使用optimtool工具箱,下面分别介绍这两种方法. ①linprog命令 一般情况下,Linprog命令的参数形式为[x,fval] = linprog(f,A,b,...
  • 文章目录第一章 线性规划§1 线性规划1.1 线性规划的实例与定义1.2 线性规划的 Matlab 标准形式1.3 线性规划问题的解的概念1.4 线性规划的图解法1.5 求解线性规划的 Matlab 解法 (练习)1.6 可以转化为线性规划的...
  • 线性规划,整数规划,非线性规划,二次规划线性规划整数规划合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  • 线性规划

    2019-01-10 11:01:40
    线性规划 流程总图: 定义: 如果目标函数或者约束条件中至少有一个是非线性函数时的最优化问题叫非线性规划问题。 比如目标函数是 f(x)=kx+b x&gt;9 线性规划 f(x)=xlogx x&gt;9 非线性规划 线性规划 ...
  • 运筹学:线性规划和非线性规划

    千次阅读 2019-03-19 09:31:38
    运筹学:线性规划和非线性规划线性规划:二 非线性规划: 一 线性规划: 先根据问题要达到的目标选取适当的变量,使问题的目标通过用变量的函数形式表示(称为目标函数),对问题的限制条件用有关变量的等式或...
  • MATLAB求解线性规划(含整数规划和0-1规划)问题

    万次阅读 多人点赞 2015-08-28 21:09:12
    线性规划是数学规划中的一类最简单规划问题,常见的线性规划是一个有约束的,变量范围为有理数的线性规划。如: 对于这类线性规划问题,数学理论已经较为完善,可以有多种方法求解此类问题。但写这篇文章的目的并...
  • 目标函数和约束条件均为线性的最优化问题。约束为线性等式Or不等式 求解方法:单纯形法 分支:整数线性规划Iinteger Linear Programing
  • 线性规划与非线性规划的求解

    千次阅读 2020-04-18 17:56:08
    单纯形法求解线性规划 一、大M法求解线性规划的原理 (1)、大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I,那么已经得到了一个初始可行基。否则在约束方程组的左边加上若千个非负的人工...
  • 一、整数规划、 二、整数线性规划分类
  • Python之建模规划篇--非线性规划

    万次阅读 2021-01-22 10:40:32
    Python之建模规划篇--非线性规划线性规划基本介绍线性规划与非线性规划的区别非线性规划的Matlab解法Python 解决非线性规划1、等式约束下的拉格朗日乘子法2、Python实现对带约束的非线性规划求解Python编程实现...
  • 1 线性规划与非线性规划的区别 线性规划问题:目标函数与约束条件均为优化变量的线性函数,不涉及变量的耦合与高次。注意线性规划的约束条件也可以是不等式约束。表达式如下: 非线性规划问题:目标函数或约束...
  • 多目标线性规划求解方法及matlab实现

    万次阅读 多人点赞 2018-01-21 14:51:02
    求解多目标线性规划的基本思想是将多目标转化为单目标,常见的方法有理想点法、线性加权法、最大最小法、目标规划法、模糊数学解法等。这里就这几种方法进行举例说明,并用matlab实现。 一、多目标线性规划模型 ...
  • 一、线性规划 什么是线性规划问题? 线性规划是在一系列的线性条件的约束下,从而规定了可行解,在通过具体的目标函数,求得满足函数的最优解 。 例如平常的线性规划函数的例子: 在matlab中使用matlab标准的格式:...
  • 【数学建模】(十):Lingo使用:线性规划+非线性规划+整数规划线性规划运输问题整数规划非线性规划 线性规划 设x1x_1x1​桶牛奶生产A1A_1A1​, x2x_2x2​桶牛奶生产A2A_2A2​ model: max = 72*x1+64*x2; [milk] ...
  • 1 ,线性规划 :例子 已知 : 某工厂计划生产 A,B 两种产品,他们都需要机器,人工,材料才能完成。 求 : 两种零件各生产多少,才能使得利润最大 得到不等式 : 解 :见下面的 4 2 ,线性规划 : 一般形式 3 ...
  • 线性规划问题

    2020-04-07 11:07:51
    线性规划的可行解域是由一组线性约束条件形成的,从几何意义来说,就是由一些线性解面围割形成的区域。由于线性规划的目标函数也是线性的,因此,目标函数的等值域是线性区域。如果在可行解域中的某内点处目标函数...
  • 以整数线性规划为例 # -*- coding: utf-8 -*- import pulp as pulp def solve_ilp(objective , constraints) : print objective print constraints prob = pulp.LpProblem('LP1' , pulp.LpMaximize) prob +
  • 线性规划和线性回归

    千次阅读 2018-11-27 15:50:29
    线性规划 定义:研究线性约束条件下线性目标函数的极值问题的数学理论和方法(百度) 也就是说有几个线性约束条件,目标是对线性函数求极值。 基本模型结构: 目标函数z(决策变量x):minz=f(x)min \quad z=f(x...
  • 线性规划函数:linprog() 线性规划的标准形式 线性规划的目标函数可以是求最大值,也可以是求最小值,约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不方便,matlab规定线性规划的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 74,926
精华内容 29,970
关键字:

关于线性规划