数学模型1-2单纯形法.pdf

§1.2 单纯形法 MaxZ=C X + C X +…+C X 1 1 2 2 n n a X + a X +…+ a X =b 11 1 12 2 1n n 1 a X + a X +…+ a X =b 21 1 22 2 2n n 2 … … … … a X + a X +…+ a X =b m1 1 m2 2 mn n m Xj ≥0(j =1,2,…,n) 1 可行解集 • “定义域”是什么？即由约束方程AX=b所定 义的点集，称之为可行解集。 – 空集：约束条件存在矛盾； – 无界集合，目标函数没有有限最优解； – 非空有界集合－有界闭凸集。 • 凸集：连接集合中任意两点的直线仍然在集 合之中。 2 基本思想 • 凸集的顶点：一个点不能够成为集合中两 点的中点。 • 线性目标函数显然是连续函数； • 目标函数在顶点上达到最优值。 • 如何检查各个顶点上的值以找到最优解？ 单纯形法实现了从顶点到使目标函数更大 的顶点上的跳跃，最终导致一个最优解。 3 几个定义 • 线性方程组AX=b基本解：设A 的秩为m， 线性方程组AX=b 的解向量X=(X , X , L, 1 2 Xn) ，n-m个分量为0，其余m个分量对应于 A 的m个线性无关列。取0的n-m个分量称为 非基本变量（自由变量），其余的分量称 为基本变量。 • 基本可行解：约束方程Ax=b 的基本解。 4 一个定理 基本可行解 可行解集合顶点 • 证明概要 1、证明基本可行解必然是顶点。若不然， x=ay+(1-a)z ，可得到x=y=z得到矛盾。 2、证明可行解集顶点x是基本可行解，即要 说明在矩阵A 中，顶点的所有正分量所在的列 线性无关。若相关，可以构造两个点y, z，使 得 x=(y+z)/2与x为顶点矛盾。 5 定理证明 • 基本可行解是顶点 不妨设x=(x ,L,x ,0,L,0) 。若不然，如果 1 m x=αy+(1-α) z，由非负性，可以得到y和z 也有类似的形式，且非0分量对应于A 的m 个线性无关列；又Ax=Ay=Az=b ，所以 x=y=