第章 线性规划的解法.pptVIP

§3 线性规划的解法 内容: §3.1 线性规划的图解法 §3.2 单纯形原理 §3.3 表格形式的单纯形方法 §3.4 单纯形法的进一步讨论 §3.5 改进的单纯形法 §3.1 线性规划问题的图解法 例1 用图解法求解： 图解法的解题步骤 1 在平面直角坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中的点称为可行解。 2 标出目标函数值增加的方向。 3 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。 4 将最优解代入目标函数，求出最优值。 由图解法的例可看出： 线性规划的最优解在顶点上 §3.1.3 线性规划问题的标准型 内容： 1、线性规划模型的一般形式 2、线性规划模型的标准形式 3、把线性规划模型转化为标准形式 4、例题 注 释 规 范 形式（用矩阵表示） 标准形式（用矩阵表示） 3、把线性规划模型转化为标准形式 松弛变量? 例3 化下面的模型为标准型. 例4 化下面的模型为标准型. 例 化下面的模型为标准型. 把问题转化为标准形式的方法 (1)如果目标函数是minZ=cx ,只须令 -Z=Z′,化为maxZ′= -cx. (2)如果约束方程为不等式： “≥”约束：不等式左端 － 某松弛变量=右端 “≤ ”约束：不等式左端＋某松弛变量=右端 其中松弛变量≥ 0且它的价值系数为0. 3) 可行解、可行解集（可行域） 最优解、最优值 基、基向量、基变量 基解、基可行解 可行基、最优基 基 本 假 设 概 念 下面讨论线性规划标准形式的基、基本解、基本可行解的概念。 考虑线性规划标准形式的约束条件： Ax=b，x≥0 其中A为m×n的矩阵，n≥m，秩(A) = m，b ? Rm 。 设B是A矩阵中的一个非奇异（可逆）的m×m子矩阵，则称B为线性规划的一个基。用前文的记号，A=( p1 ，p2 ，…，pn ) ，其中 pj=( a1j ，a2j ，…，amj )T ? Rm ，任取A中的m个线性无关列向量 pj ? Rm 构成矩阵 B=( pj1 ，pj2 ，…，pjm )。那么B为线性规划的一个基。 基B中的列向量称为基向量,基B中含有m个基向量. 我们称对应于基B的变量xj1 ，xj2，…，xjm为基变量；而其他变量称为非基变量。 可以用矩阵来描述这些概念。 设B是线性规划的一个基，则A可以表示为 A=[ B , N ] x也可相应地分成 xB x= xN 其中xB为m维列向量，它的各分量称为基变量，与基B的列向量对应；xN为n-m列向量，它的各分量称为非基变量，与非基矩阵N的列向量对应。这时约束等式Ax=b可表示为 xB B,N = b xN 或 BxB + NxN = b 如果对非基变量xN取确定的值，则xB有唯一的值与之对应 xB = B-1b - B-1NxN 特别，当取xN = 0，这时有xB=B-1b。关于这类特别的解，有以下概念。 线性规划问题的基本解、基本可行解和可行基： 对于线性规划问题，设矩阵B = ( pj1，pj2，…，pjm ) 为一个基，令所有非基变量为零，可以得到m个关于基变量xj1 ，xj2 ，…，xjm的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解；若得到的基变量的值均非负，则称为基本可行解，同时称这个基B为可行基。 矩阵描述为，对于线性规划的解 xB B-1b x= = xN 0 称为线性规划与基B对应的基本解。若其中B-1b?0，则称以上的基本解为一基本可行解，相应的基B称为可行基。 例: 考虑线性规划模型 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x