精华内容
下载资源
问答
  • ipopt是一个解决非线性规划最优化问题的工具集,当然,它也可以用于解决线性规划问题的求解。它提供了c/c++接口,非常易于使用。

    IPOPT工具解决非线性规划最优化问题使用案例

    By Andrew( justastriver@gmail.com

    2013-08-07

    简介

      ipopt是一个解决非线性规划最优化问题的工具集,当然,它也可以用于解决线性规划问题的求解。它提供了c/c++接口,非常易于使用。


    问题

    解决类似下面的非线性问题:


    Ipopt工具采用内点法求解非线性优化问题。

    求解前的准备

    需要计算

    1. 梯度

    计算目标函数的梯度,和约束条件Jacobian矩阵

    2. Hessian矩阵

    delta and lambda are parameters for object function and constraints functions (lambda is multiplier of  Lagrangian)

     

    示例

    求解下面的最优化问题:

    第一步:

    求解目标函数的梯度:

    第二步:

    求解约束条件的Jacobian矩阵:

    第三步:

    求解目标函数和约束条件的Hessian矩阵,即求解

    得到

     

    至此,准备工作已经就绪,接下来调用Ipopt API接口进行计算。

    1.get_nlp_info设置下面的参数

    a)         n=4;//变量x个数

    b)        m=2;//约束条件个数

    c)         nnz_jac_g=8;//Jacobian非零个数

    d)        Nnz_h_lag=10;//Hessian非零个数

    2.get_bounds_info 设置下面的参数

    a)         x_l[i]设置xi的下界值

    b)        x_u[i]设置xi的上界值

    c)         g_l[i]设置约束i的下界值

    d)        g_u[i]设置约束i的上界值

    3.get_start_point设置下面参数

    a)         x[i]设置第i个变量的初始迭代值

    4.eval_f设置下面参数

    a)         object_value设置目标函数计算方式(本例:object_value=x0*x3*(x0+x1+x2) + x2

    5.eval_grad_f设置目标函数的梯度

    a)         grad_f[i]设置目标函数对第i个变量的偏导,本例如下:

    6.eval_g设置约束条件

    a)         G[i]约束条件i,本例如下:

    7.eval_jac_g设置Jacobian矩阵

    a)         iRowjCol设置非零行列的坐标

    b)        Values设置矩阵迭代值,如果values==NULL,即尚未初始化时,需要设置Jacobian矩阵哪些下标位置非零,如下图:

            

    Value==NULL(左);value != NULL(右)

    8.eval_h设置Hessian矩阵

    a)         iRowjCol设置非零行列的坐标

    b)        obj_factor为目标函数系数

    c)         lambda[i]为第i个约束的拉格朗日乘子

    d)        values设置矩阵的迭代求值,本例只有目标函数和两个约束条件,因此如所示。

    i.          目标函数

    ii.        约束1

    iii.      约束2

     

     

    9.finalize_solution求解

    a)         status为返回的求解状态

    b)        obj_value:最优值

    c)         x:最优解变量取值

    d)        z_l 拉格朗日乘子下界

    e)         z_u 拉格朗日乘子上届

    f)         lambda 最优解拉格朗日乘子取值

    C++ API

    Svn地址:https://projects.coin-or.org/svn/Ipopt/stable/3.11

    示例程序位于源代码:Ipopt/test路径下。

     

    自定义类继承于TNLP (public TNLP),使用命名空间:Ipopt (using namespace Ipopt)

     

    程序实现以下虚函数即可。

      /**@name Overloaded from TNLP */

      //@{

      /** Method to return some info about the nlp */

      virtual bool get_nlp_info(Index& n, Index& m, Index& nnz_jac_g,

                                Index& nnz_h_lag, IndexStyleEnum& index_style);

     

      /** Method to return the bounds for my problem */

      virtual bool get_bounds_info(Index n, Number* x_l, Number* x_u,

                                   Index m, Number* g_l, Number* g_u);

     

      /** Method to return the starting point for the algorithm */

      virtual bool get_starting_point(Index n, bool init_x, Number* x,

                                      bool init_z, Number* z_L, Number* z_U,

                                      Index m, bool init_lambda,

                                      Number* lambda);

     

      /** Method to return the objective value */

      virtual bool eval_f(Index n, const Number* x, bool new_x, Number& obj_value);

     

      /** Method to return the gradient of the objective */

      virtual bool eval_grad_f(Index n, const Number* x, bool new_x, Number* grad_f);

     

      /** Method to return the constraint residuals */

      virtual bool eval_g(Index n, const Number* x, bool new_x, Index m, Number* g);

     

      /** Method to return:

       *   1) The structure of the jacobian (if "values" is NULL)

       *   2) The values of the jacobian (if "values" is not NULL)

       */

      virtual bool eval_jac_g(Index n, const Number* x, bool new_x,

                              Index m, Index nele_jac, Index* iRow, Index *jCol,

                              Number* values);

     

      /** Method to return:

       *   1) The structure of the hessian of the lagrangian (if "values" is NULL)

       *   2) The values of the hessian of the lagrangian (if "values" is not NULL)

       */

      virtual bool eval_h(Index n, const Number* x, bool new_x,

                          Number obj_factor, Index m, const Number* lambda,

                          bool new_lambda, Index nele_hess, Index* iRow,

                          Index* jCol, Number* values);

     

      //@}

     

     /** @name Solution Methods */

      //@{

      /** This method is called when the algorithm is complete so the TNLP can store/write the solution */

      virtual void finalize_solution(SolverReturn status,

                                     Index n, const Number* x, const Number* z_L, const Number* z_U,

                                     Index m, const Number* g, const Number* lambda,

                                     Number obj_value,

                                     const IpoptData* ip_data,

                                     IpoptCalculatedQuantities* ip_cq);

      //@}


    展开全文
  • Lingo安装完后在其目录下有一些实例项目可以学习如下图所示,实例中讲的是关于线性规划:生产电脑最大利润问题,本章节进行改编:整形非线性规划问题。 目标函数: min=(x1-80)^2 + (x2-10)^2 + (x3-10)^2 约束...

    Lingo安装完后在其目录下有一些实例项目可以学习如下图所示,实例中讲的是关于线性规划:生产电脑最大利润问题,本章节进行改编:整形非线性规划问题。

    (请注意,吐槽开始!!!!!
    VS2010下,适用于控制台命令窗口,winform, webform 下述是以控制台窗口调用实例。
    当遇到以下情况,改一下目标平台为anycpu,控制台命令窗口,winform即可解决并VS运行正常,但是webform仍然出错,网上查了好多解决方法,如IIS应用池32,64 适配true; 项目.csproj 添加

    <Prefer64Bit>false</Prefer64Bit> 或<Prefer32Bit>false</Prefer32Bit> 
    

    最后才发现其实没有问题,虽然在VS上运行出错,但是项目发布后正常运行,真是兜兜转转一大圈花费了1个星期才发现什么都不用改。)
    在这里插入图片描述以下是lingo自带项目实例:
    在这里插入图片描述
    本次要解决的是以下二次整数规划问题求解:

    目标函数:
    min=(x1-80)^2 + (x2-10)^2 + (x3-10)^2
    约束条件:
    -x1 * 0.216 -x2 * 0.392 +x3 * 2.120 = y1;
    -x1 * 0.0020-x2 * 0.176 + x3 * 0.336 =y2;
    -x1 * (1-0.0943)* 0.282 -x2 (1-0.0833) 0.462 + x3 * (1-0.087)* 0.296 = y3;
    1< x1,x2,x3<99; 其为整数!!!!!
    -0.5<y1,y2,y3<0.5;
    x1+x2+x3 =100;


    目标函数改成:
    min= 1* x1^2 + 1* x2^2 + 1* x3^2 -160x1 -20x2 -20x3 + 840;
    约束条件,进行转换成小于等于的形式。例如y1条件如下,
    -x1 * 0.216 -x2 * 0.392 +x3 * 2.120 <= 0.5;
    x1 * 0.216 -x2 * -0.392 +x3 * -2.120 <= 0.5;

    首先解决通过Lingo软件如何求最优解:
    c1:目标函数二次项的系数 上述目标函数x1,x2,x3 分别为:1,1,1
    c2:目标函数一次项的系数
    a:约束条件等式左边的系数:共6行3列,(必须是计算后的值,c#项目中可以带式子,不用全部计算出来)
    b:约束条件等式右边的系数
    gin(x) 限制整数
    bnd() 限制范围

    在这里插入图片描述

    接下来是在c# 项目中将上述的c1,c2,a,b手动输入,调用lingo解决。

    首先lingo改成如下:
    pointer(n):1-4: 需要动态输入。 5-7:返回的结果
    在这里插入图片描述

    c#项目中代码如下:
    代码有点多,请耐心观看。
    本例是根据例子改变而成,主要的区别是在于c1,c2,a,b的书写格式。一般的流程就是调用dll方法打开指定目录的lng文件,成功后输入参数,在打印结果。
    @pointer 内存开辟,方便双方交互,注意c#项目插入时的顺序一一对应。
    @status是状态码,可能值:0-9,如果不是0.4.6时将不可信。原例中值判断status为0,即全局最优才输出,其余不打印并报错。而在本例中c#调用Lingo,可能为6,即局部最优,所以也打印。

    
    using System;
    using System.IO;
    using System.Runtime.InteropServices;
    
    // Our data structure to pass to the callback function
    //[StructLayout(LayoutKind.Sequential)]
    public struct CallbackData
    {
        public int nCallbacks;
        public int nIterations;
        public double dObjective;
    }
    
    public class Class1
    {
    
        //我们需要内存指针来向行话传递数据。
        //为了使用指针,必须将例程声明为“不安全”。 
    
        public unsafe static void Main(string[] args)
        {
            int nError = -1, nPointersNow = -1;
            const string strModelFile = "\\lingo64_17\\programming samples\\c#net\\simple1\\simple.lng"; // Model file name
    
            // Make sure model file exists
            if (!File.Exists(strModelFile))
            {
               Console.WriteLine("*** Unable to find model file: {0}\n", strModelFile);
               goto FinalExit;
            }
    
            // Get a pointer to a Lingo environment
            IntPtr pLingoEnv; 
            pLingoEnv = lingo.LScreateEnvLng();
            if (pLingoEnv == IntPtr.Zero)
            {
                Console.WriteLine( "Unable to create Lingo environment.\n");
                goto FinalExit;
            }
    
            // Open LINGO's log file  
            nError = lingo.LSopenLogFileLng( pLingoEnv, "\\lingo64_17\\programming samples\\c#net\\simple1\\lingo.log");
            if (nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
    
            //在下面的代码中,我们建立回调函数。解算器模型处理时,解算器周期性地调用回调。
            //每当Lingo遇到错误时,都会调用错误回调。
            //回调是可选的——如果不是,则不必声明它们需要。
            //可选地,声明回调数据(在全局上分配防止gc重新定位的堆)
    
            CallbackData cbData;
            cbData.nCallbacks = 0;
            cbData.nIterations = -1;
            cbData.dObjective = 0.0;
            IntPtr myData = Marshal.AllocHGlobal( Marshal.SizeOf( cbData));
            Marshal.StructureToPtr(cbData, myData, true);
    
            // Pass a pointer to the solver callback and our data
            lingo.typCallback cb = new lingo.typCallback( Class1.MyCallback);
            nError = lingo.LSsetCallbackSolverLng( pLingoEnv, cb, myData);
            if ( nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
    
            // Pass a pointer to the error callback and our data
            lingo.typCallbackError cbError = new lingo.typCallbackError(Class1.MyErrorCallback);
            nError = lingo.LSsetCallbackErrorLng(pLingoEnv, cbError, myData);
            if (nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
    
            //必须将lingo的传输区域固定在内存中,以防止GC重新定位。C类#
            //是一种内存管理语言。这意味着垃圾收集器可以重新定位
            //行话的转移区域,如果他们没有被钉住。
            //下面的每个内存位置都由Lingo的@POINTER(n)函数访问
            //在Lingo模型中,n是感兴趣的内存位置的索引。
    
            fixed (double* c1 = new double[3] { 1, 1, 1 })  
            fixed (double* c2 = new double[3] { -160, -20, -20})
            fixed (double* a = new double[6, 3]{ { -0.216,-0.392,2.120 }, 
                                                { 0.216,0.392,-2.120 },
                                                {-0.02,-0.176,0.336 },
                                                {0.02,0.176,-0.336 },
                                                { -(1-0.0943)*0.282,-(1-0.0833)*0.462,(1-0.087)*2.698 },
                                                { (1-0.0943)*0.282,(1-0.0833)*0.462,-(1-0.087)*2.698 }
    
                                               })
            fixed (double* b = new double[6] { 0.5, 0.5, 0.5, 0.5, 0.5, 0.5 }) 
            fixed (double* pdObjective = new double[1] {-1})
            fixed (double* pdStatus = new double[1] {-1})
            fixed (double* x = new double[3] {1,1,1})
            {
    
                // Pass /Lingo the addresses of the transfer areas for input and output data:
                // Pass Lingo the pointer to the objective coefficients (refer to the template model, simple.lng)
    
                //将输入和输出数据传输区域的地址用行话传递给:
                //将指针传递给目标系数(请参阅模板模型simple.lng)
    
                nError = lingo.LSsetPointerLng(pLingoEnv, c1, ref nPointersNow);
                if (nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
    
                // Pass a pointer to the production limits //将指针传递到生产限制
                nError = lingo.LSsetPointerLng(pLingoEnv, c2, ref nPointersNow);
                if (nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
    
                // Pointer to the labor utilization coefficients      //指向劳动利用系数的指针 
                nError = lingo.LSsetPointerLng(pLingoEnv, a, ref nPointersNow);
                if (nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
    
                nError = lingo.LSsetPointerLng(pLingoEnv, b, ref nPointersNow);
                if (nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
    
                // Point to dObjective, where Lingo will return the objective value     //指向dObjective,其中Lingo将返回目标值 
                nError = lingo.LSsetPointerLng(pLingoEnv, pdObjective, ref nPointersNow);
                if (nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
    
                // Pointer to the solution status code      //指向解决方案状态代码的指针 
                nError = lingo.LSsetPointerLng(pLingoEnv, pdStatus, ref nPointersNow);
                if (nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
    
                // Point to the variable value array      //指向变量值数组 
                nError = lingo.LSsetPointerLng(pLingoEnv, x, ref nPointersNow);
                if (nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
                
                //这是我们要运行LINGO的脚本。这个“take”命令加载
                //从外部文件建模。或者,cScript可以被加载通过使用模型文本,来避免文件访问。 
    
                string cScript = "set echoin 1 \n";
                cScript += "take \\lingo64_17\\programming samples\\c#net\\simple1\\simple.lng \n";
                cScript += "go \n"; 
                cScript += "quit \n";
    
                // Clear out the status value;
                pdStatus[ 0] = -1;
    
                //运行脚本。这里的错误代码只与脚本是否已成功加载以进行处理。我们检查
                //下面的解决方案是检查pdStatus中行话返回的状态值。 
    
    
                nError = lingo.LSexecuteScriptLng( pLingoEnv, cScript);
                if ( nError != lingo.LSERR_NO_ERROR_LNG) goto ErrorExit;
    
                // Close the log file
                lingo.LScloseLogFileLng( pLingoEnv);
    
                // Any problems?
                if ( nError != 0 ||
                // Check for optimal solution
                pdStatus[ 0] != lingo.LS_STATUS_GLOBAL_LNG)
                {
                    // Had a problem   
                    Console.WriteLine("Unable to solve! status:" + pdStatus[0]);
                    Console.WriteLine(
                    "\nx11: {0} \nx21: {1} \nx31: {2} \nx4: {3} \n\nProfit: {4}",
                     x[0], x[1], x[2], x[3], pdObjective[0]);
                } else  {
                    // Everything went OK ... print results
                    Console.WriteLine("-----------:" + pdStatus[0]);
                    Console.WriteLine(
                     "\nx11: {0} \nx21: {1} \nx31: {2}  \n\nProfit: {3}",
                      x[0], x[1], x[2], pdObjective[0]);
                }
            }
    
            Console.WriteLine();
    
            // Marshal callnack data back to the structure
            cbData = (CallbackData) Marshal.PtrToStructure(myData,typeof(CallbackData));
            Console.WriteLine( "Total callbacks : {0}" , cbData.nCallbacks);
    
            // free user data in global heap
            Marshal.FreeHGlobal( myData);
    
            goto NormalExit;
    
        ErrorExit:
            Console.WriteLine( "LINGO Error Code: {0}\n", nError);
    
        NormalExit:
            // Free Lingo's envvironment to avoid a memory leak
            lingo.LSdeleteEnvLng(pLingoEnv);
    
        FinalExit:
            Console.WriteLine("\nPress enter...");
            String sTemp = Console.ReadLine();
        }
         
        public static int MyCallback(IntPtr pLingoEnv, int nLoc, IntPtr myData)
        {
            // copy the user data in the unmanaged code into a local structure
            CallbackData cb = (CallbackData)Marshal.PtrToStructure(myData, typeof(CallbackData));
    
            // increment the number of calls to the callback function
            cb.nCallbacks++;
    
            // get iteration count
            int nIterations = -1, nErr;
            nErr = lingo.LSgetCallbackInfoLng(pLingoEnv,
             lingo.LS_IINFO_ITERATIONS_LNG, ref nIterations);
            if (nErr == lingo.LSERR_NO_ERROR_LNG && nIterations != cb.nIterations)
            {
                cb.nIterations = nIterations;
                Console.WriteLine("Current iteration count in callback={0}", nIterations);
            }
    
            // get current objective
            double dObjective = 0.0;
            nErr = lingo.LSgetCallbackDblInfoLng(pLingoEnv,
             lingo.LS_DINFO_OBJECTIVE_LNG, ref dObjective);
            if (nErr == lingo.LSERR_NO_ERROR_LNG && dObjective != cb.dObjective && dObjective > 0.0)
            {
                cb.dObjective = dObjective;
                Console.WriteLine("Current objective in callback={0}", dObjective);
            }
    
            // copy the user data in the local structure back to the unmanaged code
            Marshal.StructureToPtr(cb, myData, false);
    
            // can return -1 here to interrupt the solver
            return 0;
        }
    
        public static int MyErrorCallback(IntPtr pLingoEnv, IntPtr myData, int nErrorCode, string strErrorMessage)
        {
           // copy the user data in the unmanaged code into a local structure
           CallbackData cb = (CallbackData)Marshal.PtrToStructure(myData, typeof(CallbackData));
           Console.WriteLine("*** Lingo Error Message: ");
           Console.WriteLine( strErrorMessage + "\n");
           return 0;
        }
    
    }
    
    

    c#运行结果如下:
    在这里插入图片描述

    lingo单独运行如下:
    在这里插入图片描述
    以上就是整个流程,写的有些简单,lingo文件的语法需要查阅资料,不在详细解释。主要是思路,希望对大家有帮助。
    上述的满足条件要注意:
    1:目标函数为非线性函数中的二次函数
    2:约束条件线性函数等式和不等式。

    展开全文
  • 术语解释 整数规划:规划中的变量(全部或部分)限制为整数,...非线性规划:目标函数或约束条件中至少有一个是非线性函数的最优化问题。 多目标规划:研究多于一个目标函数在给定区域上的最优化。 动态规划:是...

    术语解释

    • 整数规划:规划中的变量(全部或部分)限制为整数,称为整数规划。(很多的单位是不能拆分成小数的)
    • 0-1规划:决策变量仅取值0或1的异类特殊的整数规划。(决策变量要么取0,要么取1)(可以解决快递员问题、协作效率最优化问题、解决流程化问题效果很多好)
    • 非线性规划:目标函数或约束条件中至少有一个是非线性函数的最优化问题。
    • 多目标规划:研究多于一个目标函数在给定区域上的最优化。
    • 动态规划:是运筹学的一个分支,是求解决策过程最优化的数学方法。

    整数规划及0-1规划模型

    概述

    • 首先0-1其实也是整数规划。
    • 整数规划指的是决策变量为非负整数值的一类线性规划。
    • 在实际问题的应用中,整数规划模型对应着大量的生产计划或活动安排等决策问题,整数规划的解法主要有分枝定界解法及割平面解法。
    • 在整数规划问题中,0-1型整数规划则是其中较为特殊的一类情况,它要求决策变量的取值仅为0或1,在实际问题的讨论中,0-1型整数规划模型也对应着大量的最优决策的活动与安排讨论,我们将列举一些模型范例,以说明这个事实。

    例题1:原油采购与加工

    在这里插入图片描述
    目标:你现在要使收益最大,如何安排原油的采购和加工。

    • 市场上可买到不超过1500t的原油A:
    • 购买量不超过500t时的单价为10000元/t;
    • 购买量超过500t但不超过1000t时,超过500t的部分8000元/t;
    • 购买量超过1000t时,超过1000t的部分6000元/t.

    问题分析:

    • 利润:销售汽油的收入-购买原油A的支出。
    • 难点:原油A的购价与购买量关系复杂。
    • 决策变量:支出 = 原油A的购买量
      在这里插入图片描述
    • Max  =4.8(x11+x21)+5.6(x12+x22)c(x)Max \space \space = 4.8(x_{11}+x_{21})+5.6(x_{12}+x_{22})-c(x)
    • c(x)~购买原油A的支出
    • c(x)={10x(0x500)8x+1000(500x1000)6x+3000(1000x1500)c(x) = \begin{cases} 10x&amp;(0\leq x\leq 500)\\8x+1000&amp;(500\leq x\leq 1000)\\ 6x+3000&amp;(1000\leq x \leq 1500)\end{cases}
    • 原油供应
    • x11+x12500+xx_{11}+x_{12}\leq 500+x 库存500t
    • x21+x221000x_{21}+x_{22}\leq 1000 库存1000t
    • x1500x\leq 1500不能卖超过1500
    • x11x11+x210.5\frac{x_{11}}{x_{11}+x_{21}}\geq 0.5,A要大于50%。
    • x12x12+x220.6\frac{x_{12}}{x_{12}+x_{22}}\geq 0.6,B要大于60%。
    • 目标函数c(x)不是线性函数,是非线性规划。
    • 对于用分段函数定义的c(x),一般的非线性规划软件也难以输入和求解。

    模型求解

    • x1,x2,x3x_1,x_2,x_3以价格10,8,6(千元/t)采购A的吨数。这对于任何一种情况都成立。
    • 于是有x=x1+x2+x3, c(x)=10x1+8x2+6x3x = x_1+x_2+x_3,\space c(x) = 10x_1+8x_2+6x_3
    • Max  =4.8(x11+x21)+5.6(x12+x22)10x1+8x2+6x3Max \space \space = 4.8(x_{11}+x_{21})+5.6(x_{12}+x_{22})-10x_1+8x_2+6x_3
    • 然而只有当x1=500x_1 = 500的时候,x2x_2才能有值,同理当x1+x21000x2=500x_1+x_2\geq 1000 x_2=500时,x3x_3才能有值
    • 所以约束等价于(x1500)x2=0(x_1-500)*x_2 = 0【这个太牛逼了】
    • 同理(x2500)x3=0(x_2-500)x_3 = 0
    • 0x1,x2,x35000\leq x_1,x_2, x_3\leq 500

    求解代码

    Model:
    Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3;
    x11+x12 < x + 500;
    x21+x22 < 1000;
    x11 - x21 > 0;  
    2*x12 - 3*x22 > 0;
    x=x1+x2+x3;     
    (x1 - 500) * x2=0; 
    (x2 - 500) * x3=0; 
    x1 < 500;
    x2 < 500;
    x3 < 500;
    end 
    

    最终结果

     Local optimal solution found.
      Objective value:                            4800.000
      Total solver iterations:                          14
         Variable           Value        Reduced Cost
                X11        500.0000            0.000000
                X21        500.0000            0.000000
                X12        0.000000           0.2666667
                X22        0.000000            0.000000
                  X1        0.000000           0.4000000
                  X2        0.000000            0.000000
                  X3        0.000000            0.000000
                    X        0.000000            0.000000
    

    这里分段函数的处理非常经典,需要反复仔细看。

    分派问题(0-1规划)

    • 若干项任务分给一些候选人来完成,每人的专长不同,完成每项任务取得的效益或需要的资源不同,如何分派任务使获得的总效益最大,或付出的总资源最少?
    • 若干种策略供选择,不同的策略得到的收益或付出的成本不同,各个策略之间有相互制约关系,如何在满足一定条件下作出抉择,使得收益最大或成本最小?
    • 指派(Assignment)问题:有若干项任务, 每项任务必有且只能有一人承担,每人只能承担一项,不同人员承担不同任务的效益(或成本)不同,怎样分派各项任务使总效益最大(或总成本最小)?一般情况分为三种
      • 人员数量与任务数量相等
      • 人员数量大于任务数量(本例)
      • 人员数量小于任务数量 ?

    0-1规划数学模型

    Max(Min)z=c1x1+x2x2+.....+cnxn Max(Min)z = c_1x_1+x_2x_2+.....+c_nx_n
    {a11x1+a12x2+...a1nxn(,=)b1a21x1+a22x2+...a2nxn(,=)b2..............am1x1+am2x2+...amnxn(,=)b2x1,x2,......,xn=01\begin{cases} a_{11}x_1+a_{12}x_2+...a_{1n}x_n\leq (\geq ,=)b_1 \\a_{21}x_1+a_{22}x_2+...a_{2n}x_n\leq (\geq ,=)b_2 \\.............. \\a_{m1}x_1+a_{m2}x_2+...a_{mn}x_n\leq (\geq ,=)b_2 \\x_1,x_2,......,x_n = 0|1\end{cases}

    案例:混合泳接力队的选拔

    在这里插入图片描述

    • 问题:如何选拔队员组成4*100混合泳接力队?
    • 讨论:丁的蛙泳成绩退步到1‘15’‘2;戊的自由泳成绩进步到57’‘5 , 组成接力队的方案是否应该调整?
      在这里插入图片描述
    • 若选择队员i参加泳姿j的比赛,记xij=1x_{ij} = 1,否则记xij=0x_{ij} = 0
    • 这里面的约束相当复杂,队员只能游一种泳姿,并且每种泳姿也只能由一名队员游。
    • 目标函数:min Z=j=14i=15cijxijmin\space Z = \sum^4_{j=1}\sum^5_{i=1}c_{ij}x_{ij}
    • 约束条件:j=14xij1,i=1,...,5             1\sum^4_{j=1}x_{ij}\leq 1,i = 1,...,5 \space \space \space \space \space \space \space \space \space \space \space \space \space (1)
      i=15xij=1,j=1,...,4             2\sum^5_{i=1}x_{ij} = 1,j = 1,...,4\space \space \space \space \space \space \space \space \space \space \space \space \space (2)
    • 一式:每人最多入选泳姿。
    • 二式:每种泳姿有且只有一个人。

    模型求解代码Lingo

    MODEL:
    sets:
      person/1..5/;
      position/1..4/;
      link(person,position): c, x;
    endsets
    data:
      c=  66.8, 75.6, 87, 58.6,
        57.2,  66, 66.4, 53,
         78, 67.8, 84.6, 59.4,
         70, 74.2, 69.6, 57.2,
         67.4, 71, 83.8, 62.4;
    enddata
    min=@sum(link: c*x);
    @for(person(i):  
       @sum(position(j):x(i,j))<=1;);
    @for(position(i):
       @sum(person(j):x(j,i))=1;);
    @for(link: @bin(x));
    END 
    

    案例2 选课策略(0-1多目标复杂规划)

    在这里插入图片描述

    • 要求至少选两门数学课、三门运筹学课和两门计算机课
    • 为了选修课程门数最少,应学习哪些课程?
    • 选修课程最少,且学分尽量多,应学习哪些课程?

    决策变量

    • xi=1x_i = 1~选课好i的课程,0为不选,1为选择。

    目标函数

    • 选修课程总数最少:min Z=i=19ximin\space Z = \sum^9_{i=1}x_i

    约束条件1:至少选两门数学课、三门运筹学课和两门计算机课

    • 最少2门数学课: x1+x2+x3+x4+x52x_1+x_2+x_3+x_4+x_5\geq 2

    • 3门运筹学课:x3+x5+x6+x8+x93x_3+x_5+x_6+x_8+x_9\geq 3

    • 2门计算机课:x4+x6+x7+x92x_4+x_6+x_7+x_9\geq 2

    • 要有最优化方法、那么必须要学微积分和线性代数,x3x1,x3x2&ThickSpace;&ThickSpace;2x3x1x20x_3\leq x_1, x_3\leq x_2 \iff2x_3-x_1-x_2\leq 0

    • 要选数据结构,必须选计算机编程,x4x7&ThickSpace;&ThickSpace;x4x70x_4\leq x_7\iff x_4-x_7\leq 0

    • 要选应用统计,必须学微积分和线性代数,x5x1,x5x2&ThickSpace;&ThickSpace;2x5x1x20x_5\leq x_1, x_5\leq x_2 \iff2x_5-x_1-x_2\leq 0

    • 要选预测理论,必选引用统计,x7x80x_7-x_8\leq 0

    • 要选数学实验,必选微积分、线性代数x9x1,x9x2&ThickSpace;&ThickSpace;2x9x1x20x_9\leq x_1, x_9\leq x_2 \iff2x_9-x_1-x_2\leq 0

    • 基本的方法论就是把约束条件转化为不等式

    约束条件2:课程最少、学分尽量多

    min  Z=i=19ximin\space \space Z = \sum^9_{i = 1}x_imax  W=5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9max\space \space W = 5x_1+4x_2+4x_3+3x_4+4x_5+3x_6+2x_7+2x_8+3x_9

    • 目标加权组合
      • ※※双目标规划方法可转化为min{Z,W}min\{Z,-W\},这样可以转化成单目标优化
    • 把一个目标作为约束,解另一个目标的规划
      • 先以课程最少为目标,不管学分多少,最优解已经可以通过上面的不等式算出,6门课程,总学分21。
      • 以学分最多,不管课程最多\rightarrow肯定是选完所有的课程。
      • 先求出一个作为约束条件,课程最小一定是6,我们把它作为约束条件,再来看怎么选学分最高。

    总结

    • 用0-1变量表示策略选择是常用的方法
      • “要选甲 (x1)必选乙 (x2)” 可用x1x2x1\leq x2描述.
      • “要选甲 (x1)必不选乙 (x2)” 怎样描述?
      • “甲乙二人至多选一人” 怎样描述?
      • “甲乙二人至少选一人” 怎样描述?
    • 双(多)目标规划的处理方法
      • 加权组合成一个新目标, 化为单目标规划.
      • 一个目标作为约束, 解另一个目标的规划.
    展开全文
  • 非线性规划问题 概念理解 :除去线性规划,则为非线性规划 其中,凸规划、二次规划、几何规划都是一种特殊的非线性规划。 数学模型 : 凸规划 :目标函数是凸函数,局部最小值 也是全局最小值。 参考 ...

    各种规划一直神秘的不敢去触碰,也一直是个疙瘩在脑子里,为此今天特意了解了一下。

    规划论

    规划论又称数学规划,运筹学的一个分支。 规划论是指在既定条件(约束条件)下,按照某一衡量指标(目标函数)在多种 方案中寻求最优方案(取最大或最小值)。规划论包括线性规划非线性规划动态规划


    线性规划问题

    概念理解:当目标函数与约束条件都是线形的,则称为线性规划。

    线性规划问题是在一组线性约束条件的限制下,求一线性目标函数最大或最小的问题。 在解决实际问题时,把问题归结成一个线性规划数学模型是很重要的一步,但往往也是困难的一步,模型建立得是否恰当,直接影响到求解。而选适当的决策变量,是我们建立有效模型的关键之一。 建立数学模型的步骤(1)分析实际问题;(2)确定决策变量;(3)找出约束条件;(4)确定目标函数;(5)整理写出数学模型。

    应用举例:某一企业内部,如何配合产品的销售时间、在各部门的原料、产品的存储、分配的数量等(决策变量) 来组织生产,使经济效益最高(目标)。 数学模型image.png

    求解方法图解法、单纯形法、对偶单纯形法等

    非线性规划问题

    概念理解:除去线性规划,则为非线性规划

    其中,凸规划、二次规划、几何规划都是一种特殊的非线性规划。

    数学模型image.png

    凸规划:目标函数是凸函数,局部最小值 也是全局最小值。参考 举个例子, 我们考虑下面的极小化问题: image.png

    设f(x)是凸函数, gi(x)是凸函数, hj(x)是线性函数.

    二次规划:一类特殊的非线性规划。它的目标函数是二次函数,约束条件是线性的。

    几何规划:略

    求解方法:拉格朗日乘子法、可行方向法、制约函数法等。

    无约束优化问题

    去除带约束的规划问题,则为无约束优化问题。 求解方法: 1、 最速下降法(也叫梯度下降) 2、 共轭梯度下降 3、 牛顿法 4、 拟牛顿法

    动态规划问题

    概念理解:若规划问题与时间有关,则称为动态规划;

    把多阶段过程转化为一系列单阶段问题,逐个求解,解决这类问题的方法称为动态规划,它是一种方法、考察问题的一种途径,但不是一种特殊的算法。 没有统一的标准模型,也没有构造模型的通用方法,甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析,构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性,这就带来了应用上的局限性。参考

    动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。 线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等; 区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等; 树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等; 背包问题:背包问题,完全背包问题,分组背包问题,二维背包,装箱问题,挤牛奶

    举例最短路径问题举例ppt

    组合规划问题:

    若规划问题与有限个事物的排列组合有关,则称为组合规划

    随机规划问题:

    若规划问题与随机变量有关,则称为随机规划。

    转载于:https://my.oschina.net/u/3851199/blog/1941726

    展开全文
  • 线性规划 1.1举例说明 形如上述这样的数学公式就叫线性规划 此时我们写出它的matlab代码 f=[-5,-4,-6]; a=[1,-1,1;3,2,4;,3,2,0]; b=[20;42;30]; lb=zeros(3,1); [x,y]=linprog(f,a,b,[],[],lb) Optimization ...
  • 动态规划线性规划

    千次阅读 多人点赞 2012-11-04 23:08:19
    1.快速区分 ...线性规划和非线性规划在某些地方被称作静态规划,但未找到权威的参考文献。 2.动态规划(DP) DP的两个重要性质:最优子结构(问题的最优解包含了其子问题的最优解)、重叠子问题
  • 蒙特卡洛模型——有约束的非线性规划问题 题目: 例:求f(x)=x1⋅x2⋅x3的最大值s.t{−x1+2x2+2x3⩾0x1+2x2+2x3⩽72  10⩽x2⩽20  x1−x2=10 \text{例:求}f\left( x \right) =x_1\cdot x_2\cdot x_3\text{的最大...
  • 可以由此确定该问题是非线性规划问题。 (3)构建模型:为了保证调整幅度最小,目标函数应设置为:Min z = ∑|△Θi| (i=1、2、3、4、5、6)为了保证飞机在题设条件下不相撞,约束条件设置为:Min
  •  规划问题分为线性规划问题和非线性规划问题,线性规划问题目前用单纯形法可以很好的解决,而非线性规划问题则没有很好的解法,根据实际问题具体分析(从编程的角度我采用过动态规划,搜索,分支限定法,以及计算...
  • 引言 最优化理论研究的是如何从众多的可行方案中选出最优的方案。由于其常与与实际生活中...1939年,前苏联数学家提出了解决运输问题线性规划的求解方法。如今,最优化理论更是被广泛应用于工业系统的控制、公司...
  • 动态规划线性动规

    千次阅读 多人点赞 2018-06-20 11:48:55
    动态规划线性动规一、动态规划的基本概念动态规划是一种用途很广的问题求解方法,它本身并不是一个特定的算法,而是一种思想,一种手段。它的设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不像...
  • 一、非线性规划和线性规划不同之处 1、含有非线性的目标函数或者约束条件 2、如果最优解存在,线性规划只能存在可行域的边界上找到(一般还是在顶点处),而非线性规划的最优解可能存在于可行域的任意一点达到。...
  • 数学规划模型之线性规划

    千次阅读 2020-07-23 16:59:01
    线性规划模型(LP)、非线性规划模型(NLP)、整数规划模型(IP)、0-1规划模型、动态规划模型(DP)、非动态规划模型、单目标规划模型、多目标规划模型。 模型的要素: 决策变量、目标函数、约束条件 二、线性规划...
  • 动态规划研究的问题 内容 动态规划思想 问题举例一:最短路问题 问题举例二:资源分配问题 例 5.1.2 离散变量的资源分配问题 多阶段决策问题 动态规划的最优子结构性质 动态规划的子问题重叠性质 前向优化 后向优化 ...
  • 算法-动态规划-解决01背包问题

    千次阅读 2019-01-23 16:33:57
    二、总体思路:根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现;...
  • 理解动态规划 动态规划中递推式的求解方法不是动态规划的本质。 我曾经作为省队成员参加过NOI,...0. 动态规划的本质,是对问题状态的定义 和状态转移方程 的定义。 引自维基百科 dynamic programming is a metho
  • 动态规划

    2017-04-14 17:01:13
    动态规划动态规划(Dynamic progamming...动态规划适合求解多阶段(状态转换)决策问题的最优解,也可用于含有线性或非线性递推关系的最优解问题,但是这些问题必须满足必须满足最优化原理和子问题的“无后向性”。 最优化
  • 用Python求解线性规划问题

    千次阅读 2020-03-15 10:31:00
    线性规划简介及数学模型表示线性规划简介一个典型的线性规划问题线性规划模型的三要素线性规划模型的数学表示图解法和单纯形法图解法单纯形法使用python求解...
  • 动态规划 核心思想 将问题分解为多个子问题,求解出多个子问题的解,然后将子问题的解存储起来,这些子问题的解相互是有关系的所以一般用迭代来解决,最后将子问题的解合并得到最终问题的解。 一般有以下性质: 最...
  • 线性规划作为运筹学中的重要部分有着...很多实际优化问题都可以通过建模转化为线性规划问题。部分线性规划问题人工求解较为困难,可以采用计算机计算出来。本文将介绍线性规划的基本概念,并给出几道相关的例题来求解。
  • 什么是动态规划二.动态规划术语三.简单递归问题四.经典背包问题五.线性DP5.1数字三角形5.2子序列问题(LIS、LCS)六.区间DP6.1原理6.2模板6.3实战6.3.1 石子合并问题6.3.2 其他区间DP问题(思路和代码详解)七.树形DP7.1...
  • 动态规划思想求旅行商问题

    千次阅读 2014-10-27 16:54:31
    1. 旅行商问题 1.1 旅行商问题描述 旅行商问题(TSP问题)是...解决旅行商问题有很多的求解方法,如蛮力法、动态规划法、贪心法和分支限界法等。主要研究用动态规划算法求解TSP问题,并对算法的性能进行了分析。 1.2
  • 动态规划典型例题解析

    千次阅读 2018-12-20 23:09:08
    什么是动态规划 动态规划的主要思想就是把问题划分为一个...在解决动态规划问题的时候,我们往往会把问题建模为一个一维数组或是二维数组,处理完边界值之后,就可以通过前一个状态和后一个状态的递推关系循环解...
  • 1 Yalmip工具箱的下载与安装 Yalmip的下载(建议在我给的这个链接里下载,官网下载的速度实在是emmmm) Yalmip的安装 2 Yalmip的使用实例 需要求解两个规划问题 变量说明 如果想学习更多关于Yalmip的使用方法,可以看...
  • 巧解动态规划问题

    千次阅读 2020-02-05 09:11:40
    本文是对动态规划问题的总结,看完之后会对类似的题目有所了解。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,793
精华内容 6,717
关键字:

动态规划解决非线性规划问题