1、运筹学 Operational Research Lec. 3 代数解法的预备 Changan University ZHU TongAutumn 2012 in Xian City 复习与预习l 第二次课讲述两个问题l 什么是线性规划（ LP）l 图解法 ，只能解决二变量线性规划l下节课将讲述线性规划的 代数解法 ，能解决普遍问题l 三方面的准备l 线性规划的 标准形式（统一的形式）l 代数解的基本概念： 基与解（概念）l 几个几何概念与基本定理（知其所以然）从图解法到代数解l 为了使用代数解，先要确定 标准的代数形式l 再搞清标准型的解法l 从此，解题分两步：l 把非标准型化成标准型l
2、解标准型线性规划的标准形式l 目前的形式l 目标函数有 max有 minl 约束条件有大于、小于、等于；约束常数大于、小于、等于零l 决策变量 Xi有的大于零，有的无要求l 标准形式l 目标函数 maxl 约束条件全部用等式表示；约束常数非负l 决策变量非负线性规划的标准形式l标准型：lmax z=c1x1+c2x2+cnxnls.t. a11x1+a12x2+a1nxn=b1l l am1x1+am2x2+amnxn=bml xj0l bm 0标准形式的一些习惯称谓l 矩阵式l Max Z=CXl s.t. AX=b， X0l 其中， A、 b、 C、 X， 0。 P9l 向量形式l LP的
3、标准形式中的习惯称谓l C 称价值向量，因为在实际问题中经常表示成本和利润的价值l B 称资源向量l A 称约束矩阵转化标准形式共三步l 第一步： 处理 目标函数l 第二步： 处理 决策变量l 第三步： 处理 约束条件转化标准形式的第一步l 求目标函数最小值化为求最大值l 目标函数两端乘 1，再令 f zl 如： min z c1x1 c2x2 cnxnl 两端乘 1l max z c1x1 c2x2 cnxn l 令 f zl max f c1x1 c2x2 cnxn 转化标准形式的第二步l 决策变量为非负 xi 0，即 0， )l 不为非负的情况l xi a， 0， a0 xi = xi-xi” l a, b, a0 xi=xi-a l (a, +), a0 xi=xi-a 转化标准形式的第三步l变右端约束常数非负l 可以两边同乘以 -1l约束条件变为l 右端约束 “” 变为 =l 如要变为 =，应在左端加上非负的松弛（ Slack）变量l 如： 6X1+4X2 24，化为 6X1+4X2+S1=24，其中 S10l 右端约束 “ ” 变为 =l 如要变为 =，左端减去非负的剩余（ Surplus）变量l 如： X1+X2 800，化为 X1+X2-S1=800，其中 S10
