運籌學(xué)教學(xué)|快醒醒,你的熟人拉格朗日又來了!!

拉

格朗日松弛算法，啥，怎么運籌學(xué)也有拉格朗日了??？為什么哪里都有他？那么拉格朗日松弛算法到底講了什么呢？本期，小編將帶你走進(jìn)拉格朗日松弛的世界。

約瑟夫·路易斯·拉格朗日

★ 目錄 ★

01

拉格朗日松弛方法簡介

02

拉格朗日松弛方法基礎(chǔ)

03

求解拉格朗日界的次梯度方法

04

一個算例求解

拉格朗日松弛方法簡介

當(dāng)遇到一些很難求解的模型，但又不需要去求解它的精確解，只需要給出一個次優(yōu)解或者解的上下界，這時便可以考慮采用松弛模型的方法加以求解。

對于一個整數(shù)規(guī)劃問題，拉格朗日松弛放松模型中的部分約束。這些被松弛的約束并不是被完全去掉，而是利用拉格朗日乘子在目標(biāo)函數(shù)上增加相應(yīng)的懲罰項，對不滿足這些約束條件的解進(jìn)行懲罰。

拉格朗日松弛之所以受關(guān)注，是因為在大規(guī)模的組合優(yōu)化問題中，若能在原問題中減少一些造成問題“難”的約束，則可使問題求解難度大大降低，有時甚至可以得到比線性松弛更好的上下界。

拉格朗日松弛方法基礎(chǔ)

為了方便各位讀者理解，我們直接放上流程圖如下

其中各個參數(shù)的計算方式參照第二節(jié)中給出的公式來計算。

MainFrame.java

package lagranger;
import java.io.IOException;import ilog.concert.IloException;
public class MainFrame {  double best_ub;  double best_lb;  double best_mu;  double[] best_sl;  Subproblem sp;  public MainFrame()   {    best_lb = 0;    best_ub = 1e10;    sp = new Subproblem();    best_sl = new double[4];  }  // 次梯度方法求解拉格朗日對偶  public void solve(double min_step_size, int max_iter) throws IOException, IloException  {    int iter = 0;    int non_improve = 0;    int max_non_improve = 3;      double lambda = 2;          double step_size = 1;        double mu = 0;         // 初始化拉格朗日乘子    sp.construct(mu);      // 松弛第一個約束條件的拉格朗日松弛    while(iter++ < max_iter)    {      sp.changeObj(mu);      if (sp.solve() == false)       {        System.out.println("The Lagrangian problem solve wrong!");        System.exit(0);      }      // 更新上界      if(sp.opt_cost < best_ub)      {        best_ub = sp.opt_cost;        best_mu = mu;        for(int i = 0; i < best_sl.length; i++)          best_sl[i] = sp.opt_x[i];        non_improve = 0;      }      else        non_improve++;      System.out.println("iter " + iter + "******************************");      System.out.println("best lb " + best_lb);      System.out.println("best ub " + best_ub);      System.out.println("current ub " + sp.opt_cost);      System.out.println("mu " + mu);      double subgradient = 8*sp.opt_x[0] + 2*sp.opt_x[1] + sp.opt_x[2] + 4*sp.opt_x[3] - 10;      mu = Math.max(0, mu + step_size * subgradient);      // 滿足原問題約束的可行解可以作為原問題的下界      if (subgradient <= 0)       {        double current_lb = 16*sp.opt_x[0] + 10*sp.opt_x[1] + 4*sp.opt_x[3];        if (current_lb > best_lb)           best_lb = current_lb;      }      // 上界未更新達(dá)到一定次數(shù)      if(non_improve >= max_non_improve)      {        lambda /= 2;        non_improve = 0;      }      double dist = Math.pow(subgradient, 2);
      // 迭代停止條件2和3      if(dist <= 0.0 || best_lb >= best_ub - 0.0000001)        break;      step_size = lambda * (sp.opt_cost - best_lb) / dist;
      // 迭代停止條件4      if(step_size < min_step_size)        break;    }  }  public static void main(String[] args) throws IOException, IloException   {    MainFrame mf = new MainFrame();    mf.solve(0.01, 10);    System.out.println("result: ");    System.out.println("best_lb: " + mf.best_lb);    System.out.println("best_ub: " + mf.best_ub);    double gap = Math.round((mf.best_ub - mf.best_lb) *  10000 / mf.best_ub) / 100;    System.out.println("gap: " + gap + "%");  }}

Subproblem.java

package lagranger;
import ilog.concert.*;import ilog.cplex.IloCplex;
public class Subproblem {  IloCplex cplex;  double opt_cost;  double mu;  double[] opt_x;  IloNumVar[] X;  public void construct(double cmu) throws IloException {    cplex = new IloCplex();    cplex.setOut(null);    mu = cmu;    // 4個變量    X  = new IloNumVar[4];    for(int i = 0; i < X.length; i++)      X[i] = cplex.numVar(0.0, 1, IloNumVarType.Int, "X" + i);    // 初始目標(biāo)函數(shù)    IloLinearNumExpr obj = cplex.linearNumExpr();    obj.addTerm(16-8*mu, X[0]);    obj.addTerm(10-2*mu, X[1]);    obj.addTerm(0-mu, X[2]);    obj.addTerm(4-4*mu, X[3]);    cplex.addMaximize(obj);    // 約束條件    IloLinearNumExpr expr1 = cplex.linearNumExpr();    expr1.addTerm(1, X[0]);    expr1.addTerm(1, X[1]);    cplex.addLe(expr1, 1);    IloLinearNumExpr expr2 = cplex.linearNumExpr();    expr1.addTerm(1, X[2]);    expr1.addTerm(1, X[3]);    cplex.addLe(expr2, 1);  }  public void changeObj(double cmu) throws IloException {    // 目標(biāo)函數(shù)    mu = cmu;    IloLinearNumExpr new_obj = cplex.linearNumExpr();    new_obj.addTerm(16-8*mu, X[0]);    new_obj.addTerm(10-2*mu, X[1]);    new_obj.addTerm(0-mu, X[2]);    new_obj.addTerm(4-4*mu, X[3]);    cplex.getObjective().clearExpr();    cplex.getObjective().setExpr(new_obj);  }  public boolean solve() throws IloException {    if(this.cplex.solve())    {      opt_cost = cplex.getObjValue() + 10*mu;      opt_x = new double[X.length];      for (int i = 0; i < X.length; i++)         opt_x[i] = cplex.getValue(X[i]);      return true;    }    cplex.exportModel("model.lp");    return false;  }}

運行之后我們可以得到如下結(jié)果

有興趣的小伙伴一定要下載代碼自己運行一遍哦~代碼和參考資料將會在留言區(qū)給出~注意，在這個代碼中，我們使用了之前講到的Cplex工具，如果有不會使用的小伙伴請點擊下方傳送門

干貨|十分鐘快速掌握CPLEX求解VRPTW數(shù)學(xué)模型（附JAVA代碼及CPLEX安裝流程）

參考文獻(xiàn)

【1】Marshall L. Fisher, The Lagrangian Relaxation Method for Solving Integer Programming Problems. ?Management Science, Vol. 27, No. 1 (Jan., 1981), pp. 1-18

【如對代碼有疑問，可聯(lián)系小編，可以提供有償輔導(dǎo)服務(wù)】

【有償輔導(dǎo)純屬個人行為，與團(tuán)隊無關(guān)】

-The End-

文案 / 排版 / 代碼 蘇鍔（研一）

指導(dǎo)老師 / 秦虎 華中科技大學(xué)管理學(xué)院 [email protected]

審稿老師/劉林冬 中國科學(xué)技術(shù)大學(xué) 管理學(xué)院 ldliu(at)ustc.edu.cn

如對代碼有疑問，可聯(lián)系小編，無償提供服務(wù)。

蘇鍔（華中科技大學(xué)管理學(xué)院、[email protected])