精华内容
下载资源
问答
  • 线性规划-pulp-复杂矩阵

    千次阅读 2019-04-07 16:50:43
    线性规划-pulp-复杂矩阵 1. 简介-线性规划 在数学中,线性规划(Linear Programming,简称LP)特指目标函数和约束条件皆为线性的最优化问题。线性规划是最优化问题中的一个重要领域。在作业研究中所面临的许多实际...

    线性规划-pulp-复杂矩阵

    1. 简介-线性规划

    在数学中,线性规划(Linear Programming,简称LP)特指目标函数和约束条件皆为线性的最优化问题。线性规划是最优化问题中的一个重要领域。在作业研究中所面临的许多实际问题都可以用线性规划来处理,特别是某些特殊情况。最简单情况就,解线性方程组。

    举个最简单的例子:

    工厂生产A和B两种物品,需要原料配比分别是1:2:1和2:1:3.

    现有原料是100,40,8。A和B的价格分别是5和10。

    请问如何分配原材料才能获益最大?

    求解一个线性方程组即可

    2. pulp 包

    • Python中有很多的工具可以解决线性规划问题。由于pulp因其常用和方便性,故这里介绍pulp包的使用。pulp能够解决大部分的线性规划问题,如""整数规划(Integer Program)、01规划(Binary Program)还是混合整数线性规划(MILP),都能很好的解决。

    • pulp的github网址和官方文档,说实话官方文档做的并不好,但是里面介绍的例子还是很好的,如果只做最简单的线性规划可以看看学习一下。

    • 安装:按照一般套路pip install pulp 即可。

    3. pulp使用流程

    • 获得问题的描述:求解最大值还是最小值,这个要明确了。输入是的数据是什么。
    • 确定需要的决策变量:需要求解的变量,定义好,大小,数据类型。
    • 制定约束条件:决策变量和输入数据之间存在什么样的约束条件。
    • 输入数据,求解得到结果。

    那个实际例子来说明:

    1. 获得问题的描述:我们有矩阵X和矩阵Y,大小是1008*6。如图最上面的例子:是1008个产品,在6+6个指标上的需求。拆分成6+6两部分可以说明更加复杂的关系,以便更具有扩展性。

      目标,我们要求最大值:maxj=1nφj=j=1nr=16μjryjr\max \sum_{j=1}^{n} \varphi_{j}=\sum_{j=1}^{n} \sum_{r=1}^{6} \mu_{j r} y_{j r}其中n=1008n=1008,$ \mu_{j r} $是要求解的决策变量

    2. 制定约束条件如下:

      1. i=16vjixji=1,j\sum_{i=1}^{6} v_{j i} x_{j i}=1, \forall j ,$v_{j i} $是要求解的决策变量

      2. r=16μjrykri=16vjixki0,j,k\sum_{r=1}^{6} \mu_{j r} y_{k r}-\sum_{i=1}^{6} v_{j i} x_{k i} \leq 0, \forall j, k,$ \mu_{j r} v_{j i} $是要求解的决策变量

      3. 1/nj=1nvji=ρi,i=1,,61 / n \sum_{j=1}^{n} v_{j i}=\rho_{i}, i=1, \ldots, 6ρi\rho_{i}是要求解的决策变量

      4. 1/nj=1nμjr=5ρr,r=1,,61 / n \sum_{j=1}^{n} \mu_{j r}=5*\rho_{r}, r=1, \ldots, 6ρr\rho_{r}是要求解的决策变量

      5. 0.15<=ρr<=0.180.15<=\rho_{r}<=0.18……

      6. $ \mu_{j r} >=0v_{j i}>=0 $

    3. 输入数据矩阵X和Y进行求解,即可。

    4. 转换为代码求解

    废话不多说,直接上代码。

    # -*- coding: UTF-8 -*-
    import pulp
    import numpy as np
    
    def assignment_problem(matrix_x,matrix_y):
        row_matrix_x = len(matrix_x) 
        col_matrix_x = len(matrix_x[0]) 
    
        row_matrix_y = len(matrix_x)
        col_matrix_y = len(matrix_x[0])
        
        #这里是将变量拉成一条直线,方便求解
        flatten = lambda x: [y for l in x for y in flatten(l)] if type(x) is list else [x] 
        
        #这是说明了是求最大值:LpMaximize,如果需要求最小值:LpMinimize。
        m = pulp.LpProblem('task_name', sense=pulp.LpMaximize)    
    
        #这里是mu和v2个决策变量的定义,是个矩阵形式,所以需要使用的dict这个函数,lowBound说明了下界大于等于0,和约束条件6对应
        #这里的数据类型默认是浮点型,也可以换成Ingredients,cat=’Ingredients‘就是整数, cat=pulp.LpBinary这是离散型数据就是整数了。
        var_mu = pulp.LpVariable.dicts("mu", (range(row_matrix_x), range(col_matrix_x)), lowBound = 0) 
        var_vi = pulp.LpVariable.dicts("vi", (range(row_matrix_x), range(col_matrix_x)), lowBound = 0) 
      
        #这里是6个变量,由于约束条件5中说明了上下届
        rho1 = pulp.LpVariable('rho1', lowBound = 0.15, upBound = 0.18) 
        rho2 = pulp.LpVariable('rho2', lowBound = 0.02, upBound = 0.17) 
        rho3 = pulp.LpVariable('rho3', lowBound = 0.15, upBound = 0.33) 
        rho4 = pulp.LpVariable('rho4', lowBound = 0.25, upBound = 0.33) 
        rho5 = pulp.LpVariable('rho5', lowBound = 0.08, upBound = 0.17) 
        rho6 = pulp.LpVariable('rho6', lowBound = 0.01, upBound = 0.18)  
        
    
        #对应这求解最大值,即目标。pulp.lpDot相乘操作
        m += pulp.lpDot(matrix_y.flatten(), flatten(var_mu)) 
       
        #对应这约束条件1,pulp.lpSum当成求和用即可。
        for j in range(row_matrix_x):
            m +=(pulp.lpSum(var_vi[j][i]*matrix_x[j][i] for i in range(col_matrix_x))==1)  
        
        #对应这约束条件2,看起来有点长。
        for j in range(row_matrix_x):
            for k in range(row_matrix_x): 
                m+=(pulp.lpSum(var_mu[j][i]*matrix_y[k][i] for i in range(col_matrix_x))-pulp.lpSum(var_vi[j][i]*matrix_x[k][i] for i in  range(col_matrix_x))<=0.0)
        
        #对应这约束条件3和4,为了方便就展开来写了。也可以改成上述的for循环。
        m += (pulp.lpSum(var_mu[j][0] for j in range(row_matrix_x))==rho1*row_matrix_x) 
        m += (pulp.lpSum(var_mu[j][1] for j in range(row_matrix_x))==rho2*row_matrix_x) 
        m += (pulp.lpSum(var_mu[j][2] for j in range(row_matrix_x))==rho3*row_matrix_x) 
        m += (pulp.lpSum(var_mu[j][3] for j in range(row_matrix_x))==rho4*row_matrix_x) 
        m += (pulp.lpSum(var_mu[j][4] for j in range(row_matrix_x))==rho5*row_matrix_x) 
        m += (pulp.lpSum(var_mu[j][5] for j in range(row_matrix_x))==rho6*row_matrix_x)  
    
        m += (pulp.lpSum(var_vi[j][0] for j in range(row_matrix_x))==row_matrix_x*rho1*5)
        m += (pulp.lpSum(var_vi[j][1] for j in range(row_matrix_x))==row_matrix_x*rho2*5)
        m += (pulp.lpSum(var_vi[j][2] for j in range(row_matrix_x))==row_matrix_x*rho3*5)
        m += (pulp.lpSum(var_vi[j][3] for j in range(row_matrix_x))==row_matrix_x*rho4*5)
        m += (pulp.lpSum(var_vi[j][4] for j in range(row_matrix_x))==row_matrix_x*rho5*5)
        m += (pulp.lpSum(var_vi[j][5] for j in range(row_matrix_x))==row_matrix_x*rho6*5)  
        
        #求解目标,就这么简单。不用怀疑
        m.solve()
        #可以打印出来各个约束条件,拆分开的很多,可以注释掉。
        print(m)
        
        #把求解的值,取出来的操作。 
        result_mu=[[pulp.value(var_mu[i][j]) for j in range(col_matrix_x)] for i in range(row_matrix_x)]
        result_vi=[[pulp.value(var_vi[i][j]) for j in range(col_matrix_x)] for i in range(row_matrix_x)]
        result_rho1=pulp.value(rho1)
        result_rho2=pulp.value(rho2)
        result_rho3=pulp.value(rho3)
        result_rho4=pulp.value(rho4)
        result_rho5=pulp.value(rho5)
        result_rho6=pulp.value(rho6)
     
        return {'objective':pulp.value(m.objective), 'result_mu':result_mu,'result_vi':result_vi}
     
    #构造数据,我们这里为了方便直接写0,自己进行替换即可。
    matrix_x=np.zeros((1008,6))
    matrix_y=np.zeros((1008,6))
    #输入数据求解,打印结果.  
    res = assignment_problem(matrix_x,matrix_y) 
    print('{res["objective"]}')
    print(res['result_mu'])
    

    5. 思考

    • 在代码中我们在m上加上不同的约束添加,看起来不可思议。pulp为了能够这么方便的使用,使用了操作符重载的操作。感谢大佬,让线性求解如此简单。

    • pulp是做线性规划的,所以不支持2个决策变量相乘。例如:ρ1ρ2\rho_{1}*\rho_{2}是不支持。查阅了很多发现真的不支持,这样好像就是非线性规划了,所以做不了。

    • 关系式中>=,<=。但是不支持>和<,请注意。

    • 一些参考链接,感谢下列的博客。

      例子很多,适合小白开始,这里举了常见的三个例子,如果不需要我上面这么复杂可以先看这个链接,当然其中代码存在一点问题,就是定义决策变量如果是个矩阵会出错,可能博客中是以前的版本吧。如果需要定义决策变量请参考我的代码,所有的都可以。

      官网数独求解这个例子很有意思。

    展开全文
  • Python之建模规划篇--非线性规划

    万次阅读 2021-01-22 10:40:32
    Python之建模规划篇--非线性规划线性规划基本介绍线性规划与非线性规划的区别非线性规划的Matlab解法Python 解决非线性规划1、等式约束下的拉格朗日乘子法2、Python实现对带约束的非线性规划求解Python编程实现...

    基本介绍

    如果目标函数或约束条件中包含非线性函数,就称这种规划问题为非线性规划问
    题。一般说来,解非线性规划要比解线性规划问题困难得多。而且,也不象线性规划有
    单纯形法这一通用方法,非线性规划目前还没有适于各种问题的一般算法,各个方法都
    有自己特定的适用范围。
    这是一个非线性规划问题的一般形式
    在这里插入图片描述

    对于一个实际问题,在把它归结成非线性规划问题时,一般要注意如下几点:
    (i)确定供选方案:首先要收集同问题有关的资料和数据,在全面熟悉问题的基础上,确认什么是问题的可供选择的方案,并用一组变量来表示它们。
    (ii)提出追求目标:经过资料分析,根据实际需要和可能,提出要追求极小化或极大化的目标。并且,运用各种科学和技术原理,把它表示成数学关系式。
    (iii)给出价值标准:在提出要追求的目标之后,要确立所考虑目标的“好”或“坏”的价值标准,并用某种数量形式来描述它。
    (iv)寻求限制条件:由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果,因此还需要寻找出问题的所有限制条件,这些条件通常用变量之间的一些不等式或等式来表示。

    线性规划与非线性规划的区别

    如果线性规划的最优解存在,其最优解只能在其可行域的边界上达到(特别是可行域的顶点上达到);而非线性规划的最优解(如果最优解存在)则可能在其可行域的任意一点达到。

    非线性规划的Matlab解法

    在这里插入图片描述
    它的返回值是向量x,其中 FUN 是用M 文件定义的函数 f (x);X0是x的初始值;A,B,Aeq,Beq 定义了线性约束 A* X ≤ B, Aeq * X = Beq ,如果没有线性约束,则A=[],B=[],Aeq=[],Beq=[];LB 和UB 是变量x 的下界和上界,如果上界和下界没有约束,则LB=[],UB=[],如果x 无下界,则LB 的各分量都为-inf,如果x 无上界,则UB的各分量都为 inf;NONLCON 是用M 文件定义的非线性向量函数C(x),Ceq(x);OPTIONS定义了优化参数,可以使用Matlab 缺省的参数设置。

    下面给一个例子
    在这里插入图片描述
    多余的我就不多说了,matlab的可以详细看书
    现在我们来看看再仔细看看非线性规划问题的解法到底有什么

    Python 解决非线性规划

    • 非线性规划可以简单分两种,目标函数为凸函数or非凸函数
    • 凸函数的非线性规划,比如fun= x2 +y2 +xy,有很多常用库完成,比如cvxpy
    • 非凸函数的非线性规划(求极值),可以尝 试以下方法:
      • 纯数学方法,求导求极值
      • 神经网络、深度学习(反向传播算法中链式求导过程)
      • scipy. opt imize. minimize

    scipy . optimize .minimize (fun, x0, args= () , method=None,jaC=None, hess=None, hes sp=None, bounds=None, constaints= (),tol =None, callback=None, options=None)
    fun:求最小值的目标函数
    args:常数值
    method:求极值方法,一般默认。
    constraints:约束条件
    x0:变量的初始猜测值,注意minimize是局部最优

    1、等式约束下的拉格朗日乘子法

    <font size=3公式推导:这里只是简单的放了一张图片对等式约束下拉格朗日乘子法的求解步骤进行了讲解。
    在这里插入图片描述

    2、Python实现对带约束的非线性规划求解

    <font size=3求解实际例题
    在这里插入图片描述

    Python编程实现求解

    #导入sympy包,用于求导,方程组求解等等
    from sympy import *
    #设置变量
    x1 = symbols("x1")
    x2 = symbols("x2")
    alpha = symbols("alpha")
    #beta = symbols("beta")
    
    #构造拉格朗日等式
    L = 60 - 10*x1 - 4*x2 + x1*x1 + x2*x2 - x1*x2 - alpha * (x1 + x2 - 8)
    
    #求导,构造KKT条件
    difyL_x1 = diff(L, x1) #对变量x1求导
    difyL_x2 = diff(L, x2) #对变量x2求导
    difyL_alpha = diff(L, alpha) #对alpha求导
    #求解KKT等式
    aa = solve([difyL_x1, difyL_x2, difyL_alpha], [x1, x2, alpha])
    print(aa)
    

    在这里插入图片描述

    python使用SciPy库实现求解问题

    from scipy.optimize import minimize
    import numpy as np
    #目标函数:
    def func(args):
        fun = lambda x: 60 - 10*x[0] - 4*x[1] + x[0]**2 + x[1]**2 - x[0]*x[1] 
        return fun
    
    #约束条件,包括等式约束和不等式约束
    def con(args):
        cons = ({'type': 'eq', 'fun': lambda x: x[0]+x[1]-8})
        return cons
    
    if __name__ == "__main__":
        args = ()
        args1 = ()
        cons = con(args1)
        x0 = np.array((2.0, 1.0)) #设置初始值,初始值的设置很重要,很容易收敛到另外的极值点中,建议多试几个值
    
        #求解#
        res = minimize(func(args), x0, method='SLSQP', constraints=cons)
        print(res.fun)
        print(res.success)
        print(res.x)
    

    在这里插入图片描述

    结果对比

    1.普通法求结果
    在这里插入图片描述
    2.scipy库求结果
    在这里插入图片描述
    通过两个Python程序的求解结果对比分析,两个的求解结果相差不大,并且误差都在一定范围内,所以可以认为两个的求解结果是一致的。

    样例1

    计算1/x+x的最小值
    如果我们足够熟悉这个函数的性质,我们可以很容易得出来,在x>0的时候,他的最小值为2,因为这是一个双勾函数,为奇函数,可以由基本不等式得到他的最小值,但是我们怎么用程序去实现呢

    from scipy.optimize import minimize
    import numpy as np
    #计算 1/x+x 的最小值
    def fun(args):
        a=args
        v=lambda x:a/x[0] +x[0]
        return v
    if __name__ == "__main__":
        args = (1) #a
        x0 = np.asarray((2)) # 初始猜测值
        res = minimize(fun(args), x0, method='SLSQP')
        print(res)
    #     print(res.fun)
    #     print(res.success)
    #     print(res.x)
    

    可以得到如下结果,我们可以得到函数的最小是为2点多,可以看出minimize求的局部最优
    在这里插入图片描述

    样例2

    计算(2+x1)/ (1+x2) - 3x1 + 4x3的最小值,其中x1、x2、x3范围在0.1到0.9之间

    from scipy.optimize import minimize
    import numpy as np
    
    # 计算(2+x1)/ (1+x2) - 3x1 + 4x3的最小值,其中x1、x2、x3范围在0.1到0.9之间
    
    def fun(args):
        a,b,c,d = args
        v = lambda x: (a+x[0])/(b+x[1]) - c*x[0] + d*x[2]
        return v
    
    def con(args):
        # 约束条件 分为eq 和ineq
        #eq表示 函数结果等于0 ; ineq 表示 表达式大于等于0
        x1min,x1max,x2min,x2max,x3min,x3max = args
        cons = ({'type':'ineq','fun':lambda x:x[0]-x1min},\
        {'type':'ineq','fun': lambda x:-x[0]+x1max},\
        {'type':'ineq','fun': lambda x:x[1]-x2min},\
        {'type':'ineq','fun': lambda x:-x[1]+x2max},\
        {'type':'ineq','fun': lambda x:x[2]-x3min},\
        {'type':'ineq','fun': lambda x:-x[2]+x3max})
        return cons
    if __name__ == "__main__":
        #定义常量值
        args = (2,1,3,4) #a,b,c,d
        #设置参数范围/约束条件
        args1 = (0.1,0.9,0.1,0.9,0.1,0.9) #x1min, x1max, x2min, x2max
        cons = con(args1)
        #设置初始猜测值
        x0 = np.asarray((0.5,0.5,0.5))
        res = minimize(fun(args),x0,
        method='SLSQP',constraints=cons)
        print(res)
        print(res.fun)
        print(res.success)
        print(res.x)
    

    可以看出对于这类简单函数,局部最优解与真实最优解相差不大,但是对于复杂的函数,x0的初始值设置,会很大程度影响最优解的结果。
    在这里插入图片描述
    ADD:
    全局最优的函数: scipy.optimize.basinhopping
    有一个缺点是无法设置约束,求全局的最优解的函数
    https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.basinhopping.html

    每日一句
    Don’t try so hard, the best things come when you least expect them to.
    (不要着急,最好的总会在最不经意的时候出现)

    展开全文
  • 目标函数和约束条件均为线性的最优化问题。约束为线性等式Or不等式 求解方法:单纯形法 分支:整数线性规划Iinteger Linear Programing

    生产实践中,经常会遇到很多资源分配的问题,如何分配各种资源以获得最大经济效益,这就形成了运筹学的一个分支——数学规划。

    离散系统的优化问题一般都用规划模型求解

    而matlab提供了很多强大的规划问题求解命令,使得求解非常简单

    基础知识

    规划问题的数学模型的三个要素

    • 决策变量
    • 目标函数
    • 约束条件

    • 可行解 满足约束条件的解
    • 可行域 所有可行解构成的集合,R
    • 最优解 使目标函数达到最小值的可行解

    线性规划Linear Programing

    理论

    目标函数和约束条件均为线性的最优化问题。约束为线性等式Or不等式

    线性规划问题的通用的求解方法:单纯形法(由美国数学家,线性规划之父:George Bernard Dantzig(1914-2005)于1947年提出),正是这个单纯形为线性规划的整个学科打下了基础。

    总之现在线性规划问题非常好求解,就用单纯形,MATLAB的linprog就是用的单纯形。
    在这里插入图片描述

    分支:整数线性规划Iinteger Linear Programing(全部决策变量都必须取整数值)

    1947年J.von诺依曼提出了对偶理论,开创了线性规划的新领域, 他在1946年提出经典的计算机体系架构(程序和数据一样存储起来),世界上第一台计算机ENIAC也是他参与设计的。

    “对偶”不是“等价”
    “对偶”不是“等价”
    “对偶”不是“等价”

    具体定义
    在这里插入图片描述
    不等式方向相反,即原问题的约束不等式是大于等于则对偶问题的对应条件则是小于等于

    优化方向相反,即原问题max对偶问题就是min
    在这里插入图片描述
    行约束是变量范围的约束条件,如x0x\geq0,这种条件不变号

    在这里插入图片描述
    上面的定义看起来仍然很迷,尤其说啥行列转置······但下面这几个性质就能让我们明白对偶问题想干啥了

    第二点,原问题是最大化问题,对偶是最小化问题,而原问题的任意可行解小于对偶问题的任意可行解, 这不就说明对偶问题的下界就是原问题的上界麽,这和第四点呼应了,当两个可行解相遇(相等)时,就是原问题和对偶问题的最优解。

    类似于这么个意思,仅供理解大致思想,不准确不严谨的地方请忽略

    在这里插入图片描述

    在这里插入图片描述

    由于现在的计算机可以处理有成千上万的约束和决策变量的规划问题, 所以线性规划已经是现代管理中常用的基本方法了。
    在这里插入图片描述

    示例

    这几个线性规划的例子除了是变量多了一些以外,都类似于初中数学最基本的练习题(一般只有俩变量,便于在二维坐标系画图手动求解),都上不了期末考试台面的那种
    在这里插入图片描述

    注意使用matlab求解一定要化为上面说的标准型:
    在这里插入图片描述

    c=[2;3;1];
    a=[1 4 2;3 2 0];
    b=[8;6];
    [x,fval]=linprog(c,-a,-b,[],[],zeros(3,1));
    % x向量是使得目标函数取得最小值的那组决策变量
    % fval是最小值
    % [],[]是等式约束,本问题中没有
    % zeros(3,1)是x向量的下限,是第三个约束条件
    % 初始值和控制变量参数没写
    
    x =
    
        0.8066
        1.7900
        0.0166
    
    >> fval
    
    fval =
    
        7.0000
    

    在这里插入图片描述
    就这么一点点代码!!so easy有没有,比自己手算快多了,正在上初中的朋友们应该学习一下

    c=[-5;-4;-6];
    a=[1 -1 1;3 2 4;3 2 0];
    b=[20;42;30];
    [x,fval,exitflag,output,lambda]=linprog(c,a,b,[],[],zeros(3,1))
    % exitflag是收敛标志,取1则问题收敛
    % output可以显示迭代总次数和使用的算法等
    % lambda是问题求解中用到的拉格朗日乘子
    
    警告: Your current settings will run a different algorithm ('dual-simplex') in a
    future release.
     
    > In linprog (line 204)
      In me_test (line 6) 
    Optimization terminated.
    
    x =
    
        0.0000
       15.0000
        3.0000
    
    
    fval =
    
      -78.0000
    
    
    exitflag =
    
         1
    
    
    output = 
    
      包含以下字段的 struct:
    
             iterations: 6
              algorithm: 'interior-point-legacy'
           cgiterations: 0
                message: 'Optimization terminated.'
        constrviolation: 0
          firstorderopt: 5.8704e-10
    
    
    lambda = 
    
      包含以下字段的 struct:
    
        ineqlin: [3×1 double]
          eqlin: [0×1 double]
          upper: [3×1 double]
          lower: [3×1 double]
    
    >> 
    
    help linprog
    
      1  linprog converged to a solution X.
          0  Maximum number of iterations reached.
         -2  No feasible point found.
         -3  Problem is unbounded.
         -4  NaN value encountered during execution of algorithm.
         -5  Both primal and dual problems are infeasible.
         -7  Magnitude of search direction became too small; no further
              progress can be made. The problem is ill-posed or badly
              conditioned.
    

    不明白拉格朗日乘子可以参看我的这篇博客我的另一篇博客

    再来个有等式约束的:
    在这里插入图片描述

    c=[2;3;-5];
    a=[2 -5 1];
    b=10;
    aeq=[1 1 1];
    beq=7;
    % 注意matlab标准形式
    [x,fval,exitflag,output,lambda]=linprog(-c,-a,-b,aeq,beq,zeros(3,1))
    
    警告: Your current settings will run a different algorithm ('dual-simplex') in a
    future release.
     
    > In linprog (line 204)
      In me_test (line 8) 
    Optimization terminated.
    
    x =
    
        6.4286
        0.5714
        0.0000
    
    
    fval =
    
      -14.5714
    
    
    exitflag =
    
         1
    
    
    output = 
    
      包含以下字段的 struct:
    
             iterations: 6
              algorithm: 'interior-point-legacy'
           cgiterations: 0
                message: 'Optimization terminated.'
        constrviolation: 1.5099e-14
          firstorderopt: 8.5009e-12
    
    
    lambda = 
    
      包含以下字段的 struct:
    
        ineqlin: 0.1429
          eqlin: 2.2857
          upper: [3×1 double]
          lower: [3×1 double]
    

    整数规划

    理论

    示例

    非线性规划

    理论

    只要目标函数和约束条件包含非线性函数,就是非线性规划

    求解非线性规划比线性规划难很多很多很多,没有适用于各类问题的通用方法,(线性规划的单纯形就是通用解法)

    示例

    展开全文
  • 线性规划算法详解

    万次阅读 多人点赞 2018-07-29 15:41:05
    线性规划 首先什么是线性规划,大致的定义我总结为在线性的目标和约束中,找出一个最优解。 举个例子:  M1和M2两种原料用于生产内外墙涂料,M1日最大可用量24吨,M2日最大可用量为6吨,外墙涂料每吨需要6吨M1,...

    线性规划

    首先什么是线性规划,大致的定义我总结为在线性的目标和约束中,找出一个最优解。

    举个例子:

     M1和M2两种原料用于生产内外墙涂料,M1日最大可用量24吨,M2日最大可用量为6吨,外墙涂料每吨需要6吨M1,1吨M2,内墙涂料每吨需要4吨M12,吨M2,外墙涂料每吨利润5个单位,内墙涂料每吨利润4个单位。且市场需求调查数据得出,内墙日需求量不超过外墙的日需求量+1吨,内墙最大日需求量为2吨

    怎样在这样的各个线性的条件中,得到最优的内外墙生产吨数,就是我们线性规划算法要做的事情。

    设外墙生产x1吨,内墙生产x2吨,设利润为z,要得到z的最大化,也就是最优解,上述条件罗列为公式可得出

    1. 6x1+4x2<=24
    2. x1+2x2<=6
    3. -x1+x2<=1
    4. x2<=2
    5. x1,x2>0
    6. z=5x1+4x2

    如何从这个公式中求出最优解?有以下两大方法

    图解法

    我们将上述约束条件画图,y轴为x2,x轴为x1,得出如下:

    圈红色的部分就是所有的可行解,表示这个区间内都的x1x2能满足约束条件

    对于我们的z函数,其实表示的是一条截距为z斜率为-(5/4)的线性直线,我们要求z最大化的最优解,就是在所有的可行区域内找到可以满足z曲线截距最大的点

    最后我们发现,可行区域内能让z函数达到最大截距的点就是我圈出来的那个角点,z再增大的话,就超出可行区域了,所以不满足要求,所以最终得出最优解为x1=3,x2=1.5

    这就是图解法的做法,一个定理就是,线性规划的最优解总是发生在约束几何平面的角点上,例如上面圈出来的点,先当做是个定理,我也不知道怎么证明这个定理。

    以上就是线性规划的图解法,优点是简单明了,缺点就是当参数超过3个时,我们很难直观画出一个jihe几何平面来找角点,所以我们需要下面的另一种解法。

    单纯形法

    当超过3个参数时,单纯形法就派上用场了,单纯形法首先要做的就是把方程化为标准形式:

    1. 所有的变量都是非负数
    2. 所有的约束都是等式(非负限制除外),且具有非负的右端项

    像上述的方程,如果化为标准形式,将会是如下

    1. 6x1+4x2+s1=24
    2. x1+2x2+s2=6
    3. -x1+x2+s3=1
    4. x2+s4=2
    5. z=5x1+4x2+0s1+0s2+0s3+0s4

    新加入的s1-4表示的是松弛变量(非负),根据大于号小于号来决定他们的正负号

    对于标准化形式,我们设有n个参数,设列举出的约束方程个数m,当m=n时,方程组就只有唯一的解,当m<n时,说明有无穷个可行解,也就是解是一个区域。

    例如y=x+1单独这个约束方程,那么可行解就是这条直线上的所有点,这个就是m=1,n=2的情况,如果再加上一个方程使得m=2,例如y=-x,则是唯一的解了,解为(-0.5,0.5)

    由上面的定理,最优可行解必然出现在几何空间上的角点

    几何角点的代数定义

    对于一个m*n的方程组,我们另n-m个变量为0,再去在m个方程中求出其余的m个变量的值,如果有可行解,则这m个变量得出的点就是这个超几何平面的角点。

    例如y=x+1,xy都非负,这里m=1我们就有两种角点情况,一种是x=0的角点,一种是y=0的角点,画图上便可只管看出。对于超3维的几何面也是如此类推,虽然我不知道如何直观证明,但这就是个定理。

    所以我们线性规划最终zu做的事就是,找出适合的角点,并代入最优的z方程,哪个得出的z最优,哪个角点就是我们的最优解

    但当参数十分多时,角点的数量就十分庞大,所以我们需要一个智能的搜索过程,来寻找出最优角点的位置。

    进基离基

    我们每一次的寻找角点称之为迭代,每一次我们都从原点,也就是非松弛变量全为0的时候开始

    我们称令(n-m)个变量为0的这些变量为非基变量,令其余的m个变量为基变量

    从原点开始,我们计算完z值后,就要选择下一个角点来计算z,那么就需要迭代,选择一个基变量进行离基操作,并选择一个非基变量代替它,进行进基操作,从而得到下一个角点来计算z。

    对于如何选择进基变量和离基变量,我们遵照如下条件

    最优条件确定进基变量,在z方程上,选择一个能让z最可能往最优方向发展的变量进基,例如max z=3x1+5x2,x2的系数更高,x2非基(即非0)的话更能使z趋于最大化。

    可行性条件确定离基变量,找出约束最小的那个进行离基,因为超过最小约束表明有约束不满足了,所以不能再往外扩展了。(具体操作是进行最小非负比计算,后面会继续讲)

    通过这两个条件,我们就可以不用暴力穷举出所有的角点进行z计算,大大减少了计算量,最后直到无最优条件可选了,再迭代时z反而会适得其反时,最优解已经得到了,求解完成。

    高斯-若尔当行运算

    上面讲述的只是单纯形法的思路,具体的计算步骤就是高斯-若尔当行计算

    回到上面的原料公式:

    1. 6x1+4x2+s1=24
    2. x1+2x2+s2=6
    3. -x1+x2+s3=1
    4. x2+s4=2
    5. z=5x1+4x2+0s1+0s2+0s3+0s4

    由于最初我们从原点开始,所以基变量是s1-4,我们把基变量写在左侧则为

    1. s1=24-6x1-4x2
    2. s2=6-x1-2x2
    3. s3=1-x2+x1
    4. s4=2-x2

    右边的系数为非基变量,左边为基变量,因为非基变量为0,所以左边的基变量的解值就是右边的常系数,也就是截距

    x1的系数为5 最能达到z最大化  x1在s1的方程中系数为-6,s1行的解值/进基变量系数的非负比最小(24/6 这里为了明显显示基变量,所以把一些参数挪到了右边,挪到左边过来就是6而不是-6,这个比值代表了新的角点的截距),所以选择x1进基,s1出基

    假设我们错误的选择了s2离基,那么xi新角点上,x1的值就是6,而x1等于6超过了约束,因为24-6*6<0,而s1是非负的,所以必须选择最小非负比进行离基。

    以s1离基,x1进基 其实就是把右边的变量挪到左边以达到左边全基,右边全非基,也就是用x1去替代s1,s1也替代x1,以得出

    1. x1=4-(1/6)s1-(2/3)x2
    2. s2=2+(1/6)x1-(4/3)x2
    3. s3=5-(1/6)s1-(5/3)x2
    4. s4=2-x2

    这就是我们手动完成的一次进基出基操作,现在基变量在左边为x1和s2-4,解分别为4,,2,5,2,剩下的为非基变量,我们可以就此解出新的z

    这是我们手算的进基离基,当参数非常庞大的时候,手算十分蛋疼,所以我们需要得出一个规律,然后可以进行编程让计算机运算。这个运算规律就叫高斯-若尔当行运算

    首先要把各个参数转到一个矩阵里,换位标准形式的原料公式的矩阵如下,一个规律是z行基本变量系数均为0

    基变量 z系数 x1系数 x2系数 s1系数 s2系数 s3系数 s4系数 解值
    z 1 -5 -4 0 0 0 0 0
    s1 0 6 4 1 0 0 0 24
    s2 0 1 2 0 1 0 0 6

    s3

    0 -1 1 0 0 1 0 1
    s4 0 0 1 0 0 0 1 2

    z不属于基变量 但为了方便表示还是写在了一起

    高斯若尔当行运算规则,根据这个矩阵,选出进基离基变量后

    进基变量所在列为枢纽列,离基变量所在行为枢纽行,行列交叉位置为枢纽元素,例如我上面标蓝色的6

    1. 对于迭代后的新枢纽行的计算规则为:在基列中,以进基变量替换离基变量,新的枢纽行=当前枢纽行/枢纽元素
    2. 其他所有行,包括Z行的计算规则为,新的行=当前行-当前行枢纽列的系数*新的枢纽行

    其实这只是对我们刚才的手算的一个推导整理,上述矩阵进行一次迭代后如下

    基变量 z系数 x1系数 x2系数 s1系数 s2系数 s3系数 s4系数 解值
    z 1 0 -2/3 5/6 0 0 0 20
    x1 0 1 2/3 1/6 0 1 0 4
    s2 0 0 4/3 -1/6 1 0 0 2

    s3

    0 0 5/3 1/6 0 1 0 5
    s4 0 0 1 0 0 0 1 2

    对比我们刚手算的迭代 你可以看到规律

    1. x1=4-(1/6)s1-(2/3)x2
    2. s2=2+(1/6)x1-(4/3)x2
    3. s3=5-(1/6)s1-(5/3)x2
    4. s4=2-x2

    一直不停循环迭代 直到没有最优条件时,z就是最优解,基变量的值,也就是解,在最后的最优解中,松弛变量如果大于0,说明该资源是充足的,如果等于0说明该资源是匮乏的

    至此我们的线性规划代数解法就完成了绝大部分

    特殊情况

    上面讲述的是基本通用的线性规划解法,但存在一些特殊情况需要特殊处理

    无法直接标准化

    当所有约束都是<=或者>=时,进行标准化直接加上松弛变量即可,但存在一些既有<=又有=,>=的方程时,就会出现个别的方程没有松弛变量,这时就出现了无法标准化的坏状态。

    做法是在没有松弛变量的行里加入人工变量Ri,并在z函数中给人工变量加一个惩罚系数M,M为无穷大或无穷小(根据z是max还是min决定),使人工变量在一次次迭代后化为0,若化不为0,说明无解

    这里需要进行两个阶段

    第一个阶段

    先不求z,而是求min r=人工变量和 若能产生r=0 则这个阶段产生了基本可行解,人工变量可以直接去掉然后进入第二阶段

    第一步min r行的计算,就会遇到z行(这里是r行)基本变量系数不为0的情况,会导致z行等式不成立,所以第一步要先进行替换(假设人工变量有R1 R2两个)

    正确r行=原始r行+(1*R1行+1*R2行)   进行系数化0

    最后r=0时,得到的基本解,人工变量必须是非基本解,才能完全不让他进入第二阶段,万一出现人工变量为基本解但值为0导致得出r=0时,需要再选择一个0基本人工变量进行离基,选择任意一个非人工非基变量进行进基,直到迭代到所有0人工变量do都被去掉。

    第二阶段

    开始求z行 阶段一最后一步得出的基本变量继续作为阶段二的基本变量

    同样 如果出现z行基本变量系数不为0,会导致z行等式不成立,需要进行系数化0,新行=旧行+(对应非零系数*对应基本变量行)

    最后再一次迭代即可进行求z最优解

    个人觉得人工变量是比较复杂而且特殊步骤比较多的,我后面会继续完善例子

    退化

    两次以上得出z的值是相同的,则为退化现象,退化有时候会产生死循环的可能,退化的出现意味着至少有一个基变量在下一次迭代中变为0,基变量出现0会导致最小非负比循环出现(都是0),而且z的下次迭代继续保持原值。

    实际生活的条件约束中,出现一直死循环的情况很少,几乎不会发生。

    无穷多个解

    按图解法来看,当z的斜率和某个边界线的斜率相同时,则会出现一段直线上的点都是最优解,即是无穷多个解

    按代数法的思路,就是出现非基变量的系数为0,这种情况下,这个非基变量可以随意进基但不改变z值,但会改变各个变量系数,这同样表现出有无限多个解的情况

    无界解

    按图解法来看,就是有个地方没有约束,z可以不断增加或者减少下去

    代数法上的表现是,最小非负比不存在,无法选择离基变量,解和系数的比值都是0或负数,导致可以无限增大进基变量而不破坏约束,也就是无界的情况

    不可行解

    人工变量>0

    总结

    以上是我对线性规划的理解,纯手打,篇幅较大,如果有什么理解错误或者改进欢迎留言。后续我会继续完善一些例子以便理解和编写相应的代码实现。

     

    展开全文
  • 线性规划对偶问题

    千次阅读 多人点赞 2021-04-28 23:49:31
    线性规划对偶问题线性规划及单纯形法〇. 前言一. 对偶问题的提出二. 对称形式下对偶问题的一般形式三. 非对称形式的原-对偶问题关系四. 对偶问题的基本性质五. 对偶问题的单纯形法描述六. 影子价格七. 利用...
  • 数学规划模型之线性规划

    千次阅读 2020-07-23 16:59:01
    线性规划模型(LP)、非线性规划模型(NLP)、整数规划模型(IP)、0-1规划模型、动态规划模型(DP)、非动态规划模型、单目标规划模型、多目标规划模型。 模型的要素: 决策变量、目标函数、约束条件 二、线性规划...
  • matlab解决线性规划

    千次阅读 2020-03-11 17:41:26
    线性规划 线性规划(Linear programming,简称LP),是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学...
  • matlab中的线性规划

    万次阅读 2019-06-26 13:20:49
    matlab中的线性规划 版权声明:该篇由特慢的一七原创,转载请联系创作者。 目前本人基于matlab做了一些建模入门的基础教程,可以在这里分享给大家, 昨日推送:matlab中的线性规划 近期来,好多童鞋面临着数学建模这...
  • 线性规划模型详解及实际应用反思

    万次阅读 多人点赞 2018-09-02 18:49:45
    一、线性规划的定义  线性规划一般用于求解最优化问题。线性规划问题是在一组线性约束条件的限制下,求一线性目标函数最大或最 小的问题。该方法在建立方程时非常简单快速,但不利于人工计算。但随着计算机技术...
  • 术语解释 整数规划:规划中的变量(全部或部分)限制为整数,...非线性规划:目标函数或约束条件中至少有一个是非线性函数的最优化问题。 多目标规划:研究多于一个目标函数在给定区域上的最优化。 动态规划:是...
  • :除去线性规划,则为非线性规划 其中,凸规划、二次规划、几何规划都是一种特殊的非线性规划。 数学模型 : 凸规划 :目标函数是凸函数,局部最小值 也是全局最小值。 参考 举个例子, 我们考虑下面的极...
  • python 非线性规划(scipy.optimize.minimize)

    万次阅读 多人点赞 2018-08-09 13:48:34
    背景:现在项目上有一个用python 实现非线性规划的需求。非线性规划可以简单分两种,目标函数为凸函数 or 非凸函数。 凸函数的 非线性规划,比如fun=x^2+y^2+x*y,有很多常用的python库来完成,网上也有很多资料,...
  • 线性规划问题建模技巧与求解方法

    千次阅读 2019-01-10 01:52:02
    数学规划中最简单的一类问题是线性规划问题,它是整数规划及一些非线性规划问题的求解基础; 本篇就详细讲解下线性规划,问题建模的方法和技巧是最重要的部分会重点讲解,文末会用Python和OR-tools工具求解一个线性...
  • 接上三篇文章: 数学规划模型(一):数学规划模型的基本知识 数学规划模型(二):线性规划模型 数学规划模型(三):整数规划模型 ...一般说来,求解非线性规划模型要比求解线性规划模型困难得多...
  • 到底什么是非线性规划

    万次阅读 多人点赞 2018-04-27 17:23:02
    本文转自新浪博客《到底什么是非线性优化?》作者:那些年的那些偏执 ... 作者系在读博士生。...你是否也对非线性规划这个领域望而却步?​​​ 你是否也在思索非线性规划求解方法的根源?​​​ ...
  • 1、线性规划问题 在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划,而线性规划(Linear Programming 简记LP)则是数学规划的...
  • 使用scipy.optimize.linprog求解线性规划问题线性规划模型问题求解结果分析 使用scipy.optimize.linprog求解线性规划问题方法如下: 线性规划模型 问题求解 在这里我们将使用scipy中的linprog进行求解,其用法如下...
  • Matlab 中的线性规划函数

    千次阅读 2017-01-19 14:19:25
    线性规划  LP(Linear programming,线性规划)是一种优化方法,在优化问题中目标函数和约束函数均为向量变量的线性函数,LP问题可描述为: min x s.t.  A·x b  Aeq·x=beq  vlb x vub 其中 ,b,beq均为向量...
  • 混合整数线性规划问题 Matlab

    万次阅读 2017-05-02 19:53:26
    一般来说可以使用simplex算法计算正实数范围内的线性规划问题,但是在实际生活中我们常常会遇到带有相关整数要求的线性规划问题,我们称之为整数线性规划问题,而更复杂的情况下,问题中既有实数又需要整数,这时...
  • Matlab 中的线性规划函数使用方法

    千次阅读 2016-09-18 20:28:40
    中的线性规划函数使用方法 摘自:http://blog.csdn.net/qin_zhangyongheng/article/details/7883612 线性规划  LP(Linear programming,线性规划)是一种优化方法,在优化问题中目标函数和约束函数均为向量变量的...
  • 线性规划和约束满足问题的思考

    万次阅读 2016-09-18 11:19:41
    本文写给对线性规划和约束满足问题的使用有困惑的朋友,如果你曾经在这方面存在一些疑问,这篇文章对你来说就再适合不过了,如果有对线性规划的解法感兴趣,那么也推荐你看一看我的思考~ *注:之前一直以为约束满足...
  • matlab解决线性规划问题

    千次阅读 2020-02-14 13:44:33
    文章目录线性规划标准型:例题一例题二例题三例题四linprog函数怎么用类型一:x = linprog(f,A,b)类型二:x = linprog(f,A,b,Aeq,beq,lb,ub) 线性规划标准型: 例题一 例题二 x为最优解,fval为最优值 例题三 ...
  • 线性规划、动态规划等几个概念

    千次阅读 2015-03-16 11:52:50
    线性规划: 在数学中,线性规划(Linear Programming,简称LP)问题是目标函数和约束条件都是线性的最优化问题。 动态规划: 动态规划(英语:Dynamic programming,DP)是一种在数学、计算机科学和经济学...
  • 线性规划 概述 重点概念提炼 “规划” 就是使用某种数学方法使有效资源的运用达到最优化。 规划就是计算,以数学形式表达的一定条件下的一组方程式和/或一组不等式中求某些未知量。 线性规划的模型结构 线性规划的...
  • 蒙特卡洛方法解非线性规划问题

    千次阅读 2016-07-23 11:39:50
    蒙特卡洛方法解非线性规划问题 蒙特卡洛算法定义: 当所求解问题是某种随机事件出现的概率,或者是某个随机变量的期望值时,通过某种“实验”的方法,以这种事件出现的频率估计这一随机事件的概率,或者得到这个随机...
  • Matlab线性规划(Linear Programming)

    千次阅读 2014-11-29 22:07:52
    bintprog:0-1规划 linprog:线性规划 quadprog optimtool 整数规划第三方工具箱: YALMIP http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Main.Download
  • 目标函数和约束条件中至少有一个非线性规划函数的数学规划问题称为非线性规划问题(UP问题) 2 MATLAB软件求解 函数 fmincon (1)建立M文件fun.m function f = fun(x) f =F(x); (2)若约束条件中有非线性约束 G...
  • C#的线性规划代码

    千次阅读 2019-07-04 09:33:42
    using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; ...namespace Dispatch.linprog ... 单纯形法是解线性规划问题的一个重要方法。 其原理...
  • (三)非线性规划

    千次阅读 2017-08-07 17:33:40
    第三章——非线性规划线性规划背景非线性规划目前还没有适于各种问题的一般算法,各个方法都有自己特定的适用范围注意事项 确定供选方案:首先要收集同问题有关的资料和数据,在全面熟悉问题的基础上,确认什么是...
  • python求解各种复杂线性/非线性方程组

    千次阅读 多人点赞 2020-03-16 17:32:53
    如何用Python求解各种复杂的方程组Python求解各种复杂的方程组线性方程组。非线性方程组。scipy求解sympy求解scipy和sympy的优缺点分析。总结 Python求解各种复杂的方程组 本文将要介绍几种方法去求解各种复杂的方程...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 259,379
精华内容 103,751
关键字:

复杂线性规划