默认值为100秒可以满足大多数小型规划求解的需要。
2）迭代次数。在此设定求解过程中迭代运算的次数，限制求解过程所花费的时间。可输入的最大值为32767，默认值为100次，可以满足大多数小型规划求解的需要。
3）精度。在此输入用于控制求解精度的数字，以确定约束条件单元格中的数值是否满足目标值的上下限。精度必须为小数（0到1之间），输入数字的小数位越少，精度越低。
4）收敛度。在此输入收敛度数值，当最近五次迭代时，目标单元格中数值的变化小于“收敛度”编辑框中设置的数值时，“规划求解”停止运算。收敛度只运用于非线性规划问题，并且必须由一个0到1之间的小数表示。设置的数值越小，收敛度就越高。
5）采用线性规划模型。当模型中所有的关系都是线性的，并且希望解决线性优化问题时，选中此复选框可加速求解进程。
6）显示迭代结果。如果选中此复选框，每进行一次迭代后都将中断“规划求解”过程，并显示当前的迭代结果。
7）假定非负。对于在“添加约束”对话框的“约束值”编辑框中没有设置下限的可变单元格，假定其下限为0。
（6）求解
对定义好的问题进行求解。单击“规划求解参数”对话框上的“求解”按钮，会弹出“规划求解结果”对话框。当规划求解得到答案时，“规划求解结果”对话框中会给出下面两条求解结果信息：
1）“规划求解”找到一个解，可满足所有的约束及最优化要求。这表明按照“规划求解选项”对话框中设置的精度，所有约束条件都已经满足，并且只要有可能，目标单元格中将得到极大值或极小值。
2）“规划求解”收敛于当前结果，并满足所有约束条件。这表明目标单元格中的数值在最近五次求解过程中的变化量小于“规划求解选项”对话框中“收敛度”设置的值。“收敛度”中设置的值越小，“规划求解”在计算时就会越精细，但求解过程将花费更多的时间。
当规划求解不能得到最佳结果时，在“规划求解结果”对话框中就会显示下述信息：
1）满足所有约束条件。“规划求解”不能进一步优化结果。这表明仅得到近似值，迭代过程无法得到比显示结果更精确的数值，或是无法进一步提高精度，或是精度值设置得太小，请在“规划求解选项”对话框中试着设置较大的精度值，再运行一次。
2）求解达到最长运算时间后停止。这表明在达到最长运算时间限制时，没有得到满意的结果，如果要保存当前结果并节省下次计算的时间，请单击“保存
13
规划求解”或“保存方案”选项。
3）求解达到最大迭代次数后停止。这表明在达到最大迭代次数后时，没有得到满意的结果，增加迭代次数也许有用，但是应该先检查结果数值来确定问题的原因。如果要保存当前结果并节省下次计算的时间，请单击“保存规划求解”或“保存方案”选项。
4）目标单元格中数值不收敛。这表明即使满足全部约束条件，目标单元格数值也只是有增有减但不收敛。这可能是在设置问题时忽略了一项或多项约束条件。请检查工作表中的当前值，确定数值发散的原因，并检查约束条件，然后再次求解。
5）规划求解未找到合适的结果。这表明在满足全部约束条件和精度要求的条件下，“规划求解”无法得到合理的结果，这可能是约束条件不一致所致。请检查约束条件公式或类型选择是否有误。
6）规划求解在目标或约束条件单元格中发现错误值。这表明在最近一次运算中，一个或多个公式的运算结果有误。须找到包含错误值的目标单元格或约束条件单元格，修改其中的公式或内容，以得到合理的运算结果。还有可能是在“添加约束”的对话框中键入了无效的名称或公式，或在“约束”编辑框中直接键入了“integer”或”binary”。如果要将数值直接约束为整数，须在“添加约束”的对话框的“关系运算符”中单击”int”。如果要将数值约束为二进制数，要单击”bin”。
§3.2 主要解题方法和典型例题分析
一般地，线性规划问题的解根据情况共有四种：
?有唯一最优解有最优解:?
?有无穷多个最优解?无界解（有可行解但无最优解）无最优解: ?
无可行解?线性规划问题如果有最优解，则可行域的某个顶点必定是最优解。因此，要求最优解，可以先计算可行域某个顶点处的目标函数值，再考察它周围相邻顶点的目标函数值是否比这个值更优。如果为否，则该顶点就是最优解(或最优解之一)，否则转到比这个点的目标函数值更优的另一顶点，重复上述过程，直到找出对应最优解的顶点。
关于线姓规划问题最优解是否唯一，有如下定理
非退化的基可行解x0是唯一最优解的充分必要条件是，这个基可行解x0所有非基变量的检验数?j?CBB?1Pj?Cj均大于零。
14
这说明，非退化的基可行解x0不是唯一最优解(从而问题有无穷多最优解)的充分必要条件是这个基可行解x0的某个非基变量的检验数等于零。实际应用中，有时要用到该结论。
题型I 线性规划问题解的概念与理论
例3-1 找出如下线性规划问题的所有的基本解，指出哪些是基本可行解。
minZ?x1?2x2?x3?3x4?x1?2x2?x3?3x4?4 ?s.t?x1?3x2?2x3?x4?3?x?0(j?1,2,3,4)?j?1213?解: A??1,P2,P3,P4)， ??(P?1321?因为 |PP12|?1213
?1?0，
所以，B1?(P1,P2)构成基。令x3?x4?0，
x1,x2,b?124??124??106?
????????13301?1?????01?1?得基本解：X1?(6,?1,0,0)T。
同理可得：
X2?(5,0,?1,0)T51X3?(,0,0,)T22X4?(0,5,?6,0)T 56X5?(0,,0,)T77X6?(0,0,1,1)T其中X3,X5,X6为基本可行解。
例3-2 线性规划问题是否可算作条件极值问题，它与微积分中讲的条件极值问题有何不同?
解: 线性规划问题也可以看成是条件极值问题，即要在满足所有约束的条件下，求目标函数的极值。它与微积分中讲到的条件极值是不同的：(I)它的约束条件中可以有不等式约束，而后者的限制条件都是等式；(2)它的约束条件的个
15
数一般地都多于变量的个数，而后者恰恰相反；(3)它的目标函数与约束条件都是线性的，而后者不必如此。 例3-3 X0是线性规划问题
maxZ?CX?AX=b s.t??X?0的最优解。以上问题中若目标函数中的C换成C*后，则问题的最优解变为X*求证：(C*-C)(X*-X0)?0。
证明: X*、X0在目标函数的系数变化之前之后都是问题的可行解，故有
CX0?CX*， 即
C(X0?X*)?0,或?C(X*?X0)?0①
同理，C*X*?C*X0即有
C*(X*?X0)?0②
①+②则有 (C*-C)(X*-X0)?0 题型II 用图解法求解线性规划问题
图解法仅适用于两个变量的线性规划问题，求解时按原来题目对目标函数的优化要求去求解即可．不必将求极小值化为求极大值。
三个变量的线性规划问题用图解法求解时，可行域是三维空间的多面体，很难用平面上的图形画得清晰准确，目标函数对应的是三维空间中的平面，难以通过平面上画出的立体图形求出最优解。所以，从理论上讲，三个变量的线性规划也有图解法，但实际上不可行。多于三个变量的线性规划涉及到在高于三维的向量空间中求解优化问题，而三维以上的空间已无直观的几何意义，故不存在相应的图解法
例3-4 设线性规划问题为
maxZ?4x1?5x2?2x1?3x2?30?x?x?12 ?12s.t??2x1?x2?20?xj?0(j?1,2)?(1) 用图解法找出最优解；
(2) 若目标函数变为Z?4x1?7x2，最优解如何变化？ (3) 若第三个约束变为2x1?x2?15，最优解又将如何变化？
16
相关推荐：
loading