01-第一章 线性规划与单纯形法.ppt

计算结果为 1.5 初始可行基的求法 在4．2中已经提到可以采用人造基的方法得到初始基本可行解。现在就来讨论这种方法。 设LP问题的约束条件是 分别给每个约束方程引入人工变量(artificial variable) xn＋1，…，xn＋m得到 以xn＋1，…，xn＋m作为基变量，并以它们对应的系数列向量构成一个m×m阶 的单位矩阵作为初始可行基，从而得到一个初始基本可行解 * International Business School of Shaanxi Normal University * 1.5 初始可行基的求法 由于人工变量是后加入约束条件中的虚拟变量，要求将它们从基变量中逐个替换出来。若经过换基迭代，基变量中不再含有非零的人工变量，这就表明原问题有解；若在最优表中还有某个人工变量仍在基变量中，这就表明原问题无可行解。下面介绍两种处理人工变量的方法。 5．1 大M法 在约束条件中加入人工变量后，要求人工变量对目标函数取值不产生影响，为此对最大化问题需假定人工变量的价值系数为“﹣M”(M为任意大的正数)，对最小化问题需假定人工变量的价值系数为“M”。迭代中若某一人工变量已变为非基变量，即可在单纯形表中将它所在列消去，不再参与以后运算。 例1—15 求解 * International Business School of Shaanxi Normal University * 1.5 初始可行基的求法 解 先将约束方程化成标准型 在第二、三个约束方程中分别加人人工变量y1，y2，原问题化为 用单纯形进行计算，其过程见表1—12。从最优表得知最优解 最优值为 zmin＝﹣2。 * International Business School of Shaanxi Normal University * 1.5 初始可行基的求法 我们注意到，约束中每增加一人工变量，可行域增加一维，原可行域SD可理解 为加入人工变量后的可行域SM在人工变量取值为零的子集合，所以SD上任一 可行解均不优于SM上的最优解。 * International Business School of Shaanxi Normal University * 1.5 初始可行基的求法 例I—16 用大M法求解 解 原问题化为 * International Business School of Shaanxi Normal University * 1.5 初始可行基的求法 用单纯形法计算过程列于表l—13中。 检验数符合最优性要求，但基变量中有非零人工变量y＝4，所以原问题无可行解。 * International Business School of Shaanxi Normal University * 1.5 初始可行基的求法 5．2 两阶段法 大M 法存在这样一个缺点：由于规定M是一个任意大的正常数，所以在电 子计算机上解算线性规划问题时，常常会因为计算机舍入误差的影响或计算机 字长的限制，造成计算上的错误。因此我们介绍处理入工变量的两阶段法，这 种方法是目前常用的解法，即使手算两阶段法也是很有效的。 第一阶段，判断原LP问题是否存在基本可行解。办法是引进辅助问题．其目标函数W是人工变量y1，y2，…，ym的和，并要求实现最小化。因为目标函数 ，在可行域上显然有下界 ，故辅助问题必有最优解。因而，当辅助问题的w=0 ，显然每一个非负的yi＝0就得到辅助问题的最优解，而且这个最优解就为原LP问题提供了第一个基本可行解，于是转向第二阶段。否则，若辅助问题的w0 。那么，人工变量yi中至少有一个不为零，则原LP问题就不存在可行解，这时不必进行第二阶段的计算。 第二阶段，把第一阶段辅助问题的基本最优解，作为原LP问题的初始基本可行解，用单纯形法继续求解。 * International Business School of Shaanxi Normal University * 1.5 初始可行基的求法 例1—17 用两阶段法求解例1—15。 解 引入辅助问题 利用单纯形法求解辅助问题的过程，见表l—14．（见下页） * International Business School of Shaanxi Normal University * 1.3线性规划问题的解 * International Business School of Shaanxi Normal University * 矩阵