§2 4二次规划QP.ppt

优化建模与LINDO/LINGO软件 §2.4* 二次规划(QP) 例2.9 在LINDO模型窗口中输入模型 例2.10 THE END 优 化 建 模 第二章 LINDO软件的基本使用方法 ［原书相关信息］ 谢金星, 薛毅编著, 清华大学出版社, 2005年7月第1版. /~jxie/lindo LINDO可用于求解二次规划(QP)问题，但输入方式比较复杂，因为在LINDO中不许出现非线性表达式。我们需要为每一个实际约束增加一个对偶变量（或LAGRANGE乘子），通过在实际约束前增加有关变量的一阶最优条件，从而转化二次型为线性互补型（对线性互补型有兴趣的读者，需要参阅其他一些专门书籍）；并要使用QCP命令指明实际约束开始的行号，然后才能求解。下面仅通过两个例子进行说明。 求解如下二次规划问题 : 用RT, ONE和UL作为对偶变量， 问题输入格式应该如下: MIN X+Y+RT+ONE+UL ST 6X - Y - 1.2RT + ONE 0. - X + 2Y - .9RT + ONE + UL -.4 1.2X + .9Y 1.1 X + Y = 1 Y .7 END QCP 4 输入中的第一行(目标函数)只用于给出模型中相应变量的出现顺序：X，Y，RT，ONE，UL，用加号连接。 输入中的第二、三行约束是在实际约束前增加的有关变量的一阶最优条件，即LAGRANGE函数 : 分别对x，y求偏导数，令其大于 0 所得第二、三行约束（一阶最优条件）。 “END”后面的语句“QCP 4”表示原来的二次规划问题真正的约束是从输入的第4行开始的。 求解得到输出如下（只列出需要的部分结果）： QP OPTIMUM FOUND AT STEP 7 OBJECTIVE FUNCTION VALUE 1) 1.3555560 VARIABLE VALUE REDUCED COST X .666667 .000000 Y .333333 .000000 RT 10.888890 .000000 ONE 9.399998 .000000 UL .000000 .366667 ROW SLACK OR SURPLUS DUAL PRICES 2) .000000 -.666667 3) .000000 -.333333 4) .000000 -10.888890 5) .000000 9.399998 6) .366667 .000000 NO. ITERATIONS= 7 同整数规划时的情况类似，二次规划也没有敏感性分析结果，因此LINDO对应的敏感性分析输出结果也是没有意义的，不能被利用。 经过7次迭代，到了最优解:X=0.666667，Y=0.333333，最优值为:1.3555560 求解第1章1.2.2节例1.2给出的如下二次规划问题： 需要用对偶变量（LAGRANGE乘子）写出其LAGRANGE函数。 设两个约束的LAGRANGE乘子分别是LAG1，LAG2， 则其LAGRANGE函数为： （注意：我们把目标函数取了负号，因此把原来的最大化问题变成了最小化问题） 分别对原问题的决策变量x1 ，x2求偏导数，令其大于等于0（这实际上是一阶最优条件），可得两个新约束如下： QP问题输入LINDO软件求解时，第一行(目标函数)只用于给出模型中相应变量的出现顺序：X1，x2，lag1,lag2，用加号连接；在实际约束前增加刚刚得到的有关变量的一阶最优条件。 此外，必须在“END”语句后面用“QCP n”语句说明这是一个二次规划，同时指出实际约束是从第n行开始的。 最后，这个问题的输入如下： （注意：我们这里故意假设产量必须为整数，所以最后