2012年8月数学建模修改讲稿

如：2x1?3x2?8?2x1?3x2?x3?8，其中x3?0，并称x3为松弛变量

如：5x1?3x2?4?5x1?3x2?x3?4 ，其中x3?0，并称x3为松弛（或剩余）变量

③ 化决策变量满足非负约束；

如：xi?0，则令 xi???xi，并用?xi?去代替xi

??xk??，其中xk?,xk???0，并用xk??xk??去代替xk 如：xk符号不限，则令xk?xk 如：xj??j，则令x?j?xj??j，此时有x?j?0

???r?xr，此时有xr??0，并用?r?xr?去代替xr 如：xr??r，则令xr 练习题 minZ?5x1?2x2?4x3?3x4

?x1?2x2?x3?4x4??2 s?t

?x1?3x2?x3?x4?142x1?x2?3x3?x4?2

x3,x4?0,x2?0,x1符号不限4. 线性规划问题中有关解的概念及线性规划问题的重要性质：

① 可行解：满足所有约束条件的解； ② 可行域：所有可行解构成的集合；

③ 最优解：使目标函数值达到最优时的可行解；

④ 基矩阵，基变量，非基变量，基本解，基本可行解。 为了了解上述概念，我们先看如下例题

maxZ?x1?2x2?11x3?7x4?6x5x1?2x3?x4?2x5?10x2?3x3?3x4?x5?6x1,x2,x3,x4,x5?0

s?t

对于线性规划问题：maxZ?CX,AX?b,X?0.

其中A为m?n矩阵，且R(A)?m?n，B为A的任意一个m阶满秩子方阵，则称B为线性规划问题的一个基矩阵；B中列向量所对应的决策变量称为基变量，其余的决策变量称为非基变量；令非基变量的取值为0，得基变量相应的取值，由此得到的解称为规划问题的一个基本解；如果基本解满足非负约束，则称它为基本可行解。

⑤ 重要性质：如果线性规划问题存在可行解，则一定存在基本可行解；

如果线性规划问题存在有界最优解，则它一定存在有界的最优基本可行解，即线性规划问题的最优解可以在基本可行解处得到。

5. 线性规划问题的求解方法—单纯形法

1）单纯形法的基本思想

从线性规划问题的一个基本可行解出发，判断它是否为最优解；如果不是，则将它进行迭代，迭代至下一个基本可行解，每次迭代，要使目标函数值有所改善；这样经过有限次迭代后，最终可以找到最优解或判断问题无界。

2）基本可行解的迭代过程

maxZ?x1?2x2?11x3?7x4?6x5x1?2x3?x4?2x5?10x2?3x3?3x4?x5?6x1,x2,x3,x4,x5?0 下面通过实例来介绍 例

s?t

5

?x3??x1??10??， x 选取一个基矩阵 B??，对应的基变量为 XB??，非基变量为XN??4?????01??x2???x5?? 令非基变量的取值为0，得初始基本可行解 X0?(10,6,0,0,0)T，相应的目标函数值为 Z0?22 . 所谓基本可行解的迭代，指的就是：让一个基变量出基，再让一个非基变量进基。 ⅰ）现在x3,x4,x5都是非基变量，那么让哪一个非基变量进基呢？

考察 ：让x3的取值增加一个单位，即让x3的取值从0增加到1，其它非基变量取值不变，仍为0，得可行解 X1?(8,3,1,0,0)T，此时目标函数值为 Z1?25 ；目标函数值的改变量为 ?Z1?25?22?3

这个数值3称为非基变量x3的检验数，记作?3，即?3?3。它表示当非基变量x3的取值增加一个单位时，可使目标函数值增加3个单位。 同样可得 ?4?0 ，?5?2

让x3的取值增加一个单位，可使目标函数值增加3个单位；让x4的取值增加一个单位，目标函数值没有改变；让x5的取值增加一个单位，可使目标函数值增加2个单位；针对极大化问题，我们自然希望目标函数值增加得越多越好，因此选x3作为进基变量。

针对极大化问题，我们选取最大正检验数所对应的非基变量进基

ⅱ）x1,x2之中，哪一个基变量出基呢？

?x?2x3?10 由于x4,x5仍是非基变量，取值为0，故此时的约束条件变为 ?1

x?3x?63?2 让x3的取值增加一个单位，可使目标函数值增加3个单位；x3的取值增加二个单位，可使目标函数值增加6个单位；如此一来，我们希望x3的取值增加得越多越好；但由于要保证x1,x2的取值非负，故x3的取值不能无?106?,限增大，最多可增加到 min???2；当x3?2时，便有x2?0，于是x2出基。 23?? 此时新的基本可行解为 X?(6,0,2,0,0)T，新的目标函数值为 Z新?28 ⅲ）最优解判别定理

从上面的分析可知，如果所有的检验数?j?0，则说明，让任何非基变量的取值增加，都将使目标函数值有所减少，此与极大化目的相违背，由此的最优解判别定理：

针对极大化问题，如果所有非基变量的检验数?j?0，则此时的基本可行解便是最优解。 ⅳ）单纯形表格

对于线性规划问题LP：maxZ?CX,AX?b,X?0.

设B是LP的一个可行基矩阵，在可行基B之下，将矩阵和向量A、X、C分解成：

6

A?(B,N) ，X?(XB,XN)T ，C?(CB,CN) . 则线性规划问题LP化成： maxZ?CBB?1b?(CN?CBB?1N)XN,s?tXB?B?1NXN?B?1b,XB,XN?0.

现将上式中的变量与系数分离，建立如下形式的单纯形表格 XB XB XN B?1b I 0 B?1N 检验数? CN?CBB?1N CBB?1b 其中非基变量xj的检验数?j?cj?CBB?1Pj

maxs?tZ?5x1?4x2x1?3x2?902x1?x2?80x1?x2?45x1,x2?0收益或产值（资源1）（资源2)（资源3) 例题： 用表格单纯形法解如下线性规划：

?J CB XB x3 5 4 0 0 0 B?1b x1 1 2 1 5↑ x2 3 1 1 4 52 12 12 x3 1 0 0 0 1 0 0 0 1 0 0 0 x4 0 1 0 0 ?12 12 ?12 x5 0 0 1 0 0 0 1 0 ?5 0 0 0 90 80→ 45 50 40 5→ 25 35 10 Z*?215 x4 x5 ?j 0 5 0 x3 x1 x5 0 1 0 0 ?j 0 5 4 x3 x1 x2 32↑ ?52 0 1 0 0 0 0 1 0 2 1 ?1 2 ?1 ?1 ?j ?3 从最优单纯形表得知，最佳生产方案为：甲产品生产35件，乙产品生产10件，工厂获利最多，最大利润为Z*?215

6. 用LINDO软件求解线性规划问题

直接输入

max 5x1+4x2

st x1+3x2<90 2x1+x2<80 x1+x2<45 end

将文件存储并命名后，选择菜单“Solve”，并对提示“DO RANGE (SENSITIVITY) ANALYSIS”（灵敏度分析）回答“是”或“否”。即可得到如下输出结果。

LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 215.0000

VARIABLE VALUE REDUCED COST X1 35.000000 0.000000 X2 10.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 25.000000 0.000000 3) 0.000000 1.000000 4) 0.000000 3.000000 NO. ITERATIONS=

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 5.000000 3.000000 1.000000 X2 4.000000 1.000000 1.500000 RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 90.000000 INFINITY 25.000000 3 80.000000 10.000000 12.500000 4 45.000000 5.000000 5.000000

注意：① LINDO软件中已经规定所有决策变量非负；

② 输入时，乘号省略，式子中不能有括号，右端不能有数学符号； ③ 模型中符号“≤”用“＜＝”形式输入，它与“＜”等效；“≥”用“＞＝”

形式输入，它与“＞”等效；

④ 输入文件中第1行为目标函数，2）、3）、4）是为了标示各约束条件，便于从输出结果中查找相应信息。

LINDO输出结果中若干单词的含义

⑴ DO RANGE (SENSITIVITY) ANALYSIS --- 询问是否作灵敏度分析

⑵ LP OPTIMUM FOUND AT STEP 2 --- 单纯形法在两次迭代后得到最优解 ⑶ OBJECTIVE FUNCTION VALUE 1) 3360.000 --- 最优目标函数值为 3360.00 ⑷ VARIABLE --- 变量 ⑸ VALUE --- 数值

⑹ REDUCED COST --- 表示的检验数，即当该决策变量的取值增加一个单位时，目标 8