数模讲义之线性规划模型..doc

数模讲义之线性规划模型 目标函数与约束条件都是线性函数的优化问题叫做线性规划（Linear Programming）。例如，下面就是一个线性规划问题： 其中“s. t.”表示“subject to” ，意思是“受约束于” 。 线性规划问题可以用LINDO软件包求解（见后面第6章）。本章介绍如何用Mathematica 软件包求解。 §1 线性规划问题的求解 线性规划问题在Mathematica 软件包求解有两种方法： （I）直接输入表达式求解，命令格式如下： 目标函数求最小时，使用下列命令 ConstrainedMin[目标函数，{ 限制条件 }，{ 变量表 } ] 目标函数求最大时，使用下列命令 ConstrainedMax[目标函数，{ 限制条件 }，{ 变量表 } ] 注意：在输入限制条件时，（1）等号要写两次；（2）所有变量都要转化为非负的形式，Mathematica 软件系统自动在第一象限求解，所以x11 ≥ 0之类的约束条件可以不输入。 例如，求解下列问题 第一步，通过变量替换，将所有变量化为非负的形式。 令 x1 = y11-y12，x2 = y21 – y22，x3 = y31 –y32，x4 = y41 – y42，x5 = y51 – y52， 其中所有变量yij≥0，代入原问题。 第二步，在Mathematica 软件包中编写程序如下： ConstrainedMin[ 7( y21 – y22 ) – 5（y31 – y32） – 53（y41 – y42） – 6（y51 – y52）, { -（ y11 - y12 ） + 6( y21 – y22 ) – 4（y41 – y42）– 3（y51 – y52） ≥ 6, y31 –y32 + 2（y41 – y42）– 5（y51 – y52） ≤ 10, 4（y11 - y12） – 5（y31 –y32） + 2 ( y61 – y62 ) == 7, y11 - y12 ≥ 2, y11 - y12 ≤ 10, y21 – y22 ≥ 7, y31 –y32 ≤ 5 }, { y11, y12, y21, y22, y31, y32, y41, y42, y51, y52, y61, y62 } ] 程序运行之后，得到结果 说明此题无最优解。 （II）将线性规划问题转化为矩阵形式求解，命令格式如下： Mathematica系统提供的求解矩阵形式的线性规划问题的命令是： LinearProgramming[ c, A, b ] 它要求必须首先将线性规划问题转化为以下“大于等于求最小”的形式： 例如，有线性规划问题： max f = 3x1 + 2x2 s. t. 2x1 – x2 ≥ -2 x1 +2 x2 ≤ 8 x1 + x2 = 5 x1, x2 ≥ 0 首先将其转化为符合程序要求的标准形式： 第一步 转化如下： min ( -f ) = -3x1 –2x2 s. t. 2x1 – x2 ≥ -2 -x1 – 2x2 ≥ -8 x1 + x2 ≥ 5 -x1 – x2 ≥ -5 x1, x2 ≥ 0 第二步 转化为矩阵形式： 于是，得到目标函数的系数向量为c = （-3, -2 ） 约束条件的系数矩阵为 约束条件的常数向量为： 最后在Mathematica中输入以下程序： c = { -3, -2}; A = { { 2, -1 }, { -1, -2 }, { 1, 1 }, { -1, -1 } }; b = { -2, -8, 5, -5 }; x = LinearProgramming[ c, A, b ]; Print[ “ x = ”, x ] f = - c.x; Print[ “ fmax = ”, f ] 其中“c.x”表示向量的内积。程序运行之后，得到以下结果： x = { 5, 0 } fmax = 15 （III）用矩阵形式求解线性规划问题及其对偶问题的解 设有线性规划问题： 及其对偶问题： 第一步 将其对偶问题转化为程序要求的标准形式： 第二步 编程序求解。注意，在Mathematica系统中，向量与它的转置（Transpose）是等价的，但矩阵与它的转置不等价。求解程序以及格式如下： c = { … }; A = { … }; b = { … }; x = LinearProgramming[ c, A, b ]; Print[ “ x = ”, x ] f = c.x; Print[ “ fmin = ”, f ] B = Transpose[ A ]; y = LinearProgrammi