+线性规划(%C).pptVIP

计算 所有 基变量中含非零的人工变量 存在非基变量检验数为零 惟一 最优解 迭代运算 1、用xk替换xl 2、列出新的单纯形表 求出初始基可行解 列出初始单纯形表 是 否 否 无界解 无可行解 无穷多最优解 是 是 是 否 否 第七节 应用举例 1 建模 2 给出初始基可行解。（引入松弛和人工变量） 3 计算非基变量的 。 若所有 均非 正，这个解就是最优解。否则，转下一步。 4 在检验数为正的那些非基变量中，选检验数最大的那个变量为引入变量，例如说这个变量是xk ，它对应系数列向量为Pk. 五 用单纯形法求解线性规划问题的步骤 5 查看 Pk 的各个分量aij ，i =1，2，----,m ，若所有 aik≤0 ，则该线性规划问题无界。否则，转下一步。 6 按最小比值规则确定θ 即: θ= min{ |aik0,i=1,2,……,m}= (1.40) 7 以相应于θ的那个变量xBl （基变量中的第l个变量）为退出变量，以alk为主元素，对约束方程组按式（1.7）进行变换，从而得一新的基可行解。 8 转回第3步，继续进行检验和变换，直至得出最优解或查明目标函数无界。 第四节 单纯形表 单纯形表格式如下： cj cBi xBi c1 c2 . cm c1 … cm x1 … xm x1 x2 . xm 1 … 0 0 … 1 . . 0 … 1 cm+1 … cn xm+1 … xn a1 , m+1 … a1n a2 , m+1 … a2n . . am , m+1 … amn bi bi/aik b1 b2 . bm b1/a1k b2/a2k . bm/amk 0 … 0 矩形交叉相乘示意图 -----aij--------------------------aik--------- i行 -----alj----------------------- alk ----- l行 (退出） j列 k列（引入） 主元素 欲计算 之元素 用单纯形法求解线性规划： Max z=12x1+16x2+12x3 2x1+4x2+x3 ≤ 2 2x1+2x2+3x3 ≤ 3 x1 , x2 , x3 = 0 解： cj 12 16 12 0 0 bi bi/aik cBi xBi x1 x2 x3 x4 x5 0 x4 2 4 1 1 0 2 1/2 0 x5 2 2 3 0 1 3 3/2 　 12 16 12 0 0 0 　 16 x2 1/2 1 1/4 1/4 0 1/2 2 0 x5 1 0 5/2 -1/2 1 2 4/5 　 4 0 8 -4 0 -8 　 16 x2 2/5 1 0 3/10 -1/10 3/10 3/4 12 x3 2/5 0 1 -1/5 2/5 4/5 2 　 4/5 0 0 -12/5 -16/5 -72/5 　 12 x1 1 5/2 0 3/4 -1/4 3/4 　 12 x3 0 -1 1 -1/2 1/2 1/2 　 　 0 -2 0 -3 -3 -15 　 Max z= 7x1+5x2 3x1+2x2≤90 4x1+6x2 ≤200 7x2 ≤210 x1≥0,x2≥0 例.用单纯形法求解线性规划 Max z = 7x1+5x2+0x3+0x4+0x5 3x1+2x2+x3 =90 4x1+6x2 +x4 =200 7x2 +x5 =210 xj≥0, j=1,2,3,4,5 其标准型为: cj 7 5 0 0 0 　 bi 　 bi/aik cBi xBi x1 x2 x3 x4 x5 0 x3 3* 2 1 0 0