SHUFE 线性规划问题的图解法 解的可能性 唯一最优解:只有一个最优点。 多重最优解 两个顶点同是最优解,其连线上的每一点都是最优解,即无穷 多个最优解。 判据:最优单纯形表中存在非基变量的检验数等于=0。 无界解 LP问题的可行域无界,目标函数无限增大,缺乏必要的约束。 判据:若某个k20所对应的系数列向量Pk≤0(有进基变量但无离 基变量),则是无界解。 无可行解 n若约束条件相互矛盾,则可行域为空集。 判据:最终单纯形表中人工变量仍没有置换出去,则没有可行 解 6上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 6 线性规划问题的图解法 • 唯一最优解：只有一个最优点。 • 多重最优解 ▪ 两个顶点同是最优解，其连线上的每一点都是最优解，即无穷 多个最优解 。 ▪ 判据：最优单纯形表中存在非基变量的检验数等于k= 0。 • 无界解 ▪ LP问题的可行域无界，目标函数无限增大，缺乏必要的约束 。 ▪ 判据：若某个k ≥0所对应的系数列向量Pk ′≤0（有进基变量但无离 基变量），则是无界解。 • 无可行解 ▪ 若约束条件相互矛盾，则可行域为空集。 ▪ 判据：最终单纯形表中人工变量仍没有置换出去，则没有可行 解。 • 解的可能性
SHUFE 线性规划标准型 标准型 目标函数极大化, 约束条件为等式, 右端常数项b≥0, 决策变量非负。 maxz=cux+Cxx,+.+crrn maze aurr +aj2x2+. +aurn=b pta,x,+. tern >Gir;=b;( x≥0(产=1,2,…,n) amrxtam2x2t. +amn b xx2…xn≥0 7上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 7 线性规划标准型 • 标准型 ▪ 目标函数极大化， ▪ 约束条件为等式， ▪ 右端常数项bi≥0， ▪ 决策变量非负。 maxZ=c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn ＝b1 a21x1+a22x2+…+a2nxn ＝b2 … … … … … am1x1+am2x2+…+amnxn ＝bm x1 ,x2 ,…,xn ≥0 maxZ= cjxj aijxj＝bi ( i=1,2,…,m) xj≥0 ( j=1,2,…,n) = n j 1 = n j 1 简记