第1章线性规划及单纯形法 11 max(min)2=c11+c22+...+Cnn s.t. a11x1+a12x2+…+a1nxn≤(=，≥)b1 a21x1+a22x2+·+a2nxn≤(=，≥)b2 (1-1-3) 。。。。 amlx1+am2x2+·+AmnEn≤(=，≥)bm x1≥0(i=1,2,…,n） 在模型(1-1-3)中，称z=c1x1+c2x2+…+cmxn为目标函数，对于该函数可能是求极 大(max),也可能是求极小(min)。模型中写成max(min)是为了将两种情况写在一起以便 于说明，并非同时求极大和极小。称a1工1+a2x2+…+anxn≤(=，≥)b(位=1,2，·，m) 为约束条件。同样，式(1-1-3)右边的≤(=，≥)是将可能的3种约束情况写在一起以 便于说明。最后≥0（位=1,2，·，）称为决策变量的非负约束。由于线性规划问题 在经济学上的含义，称c(位=1,2，…，n)为价值系数：b行=1,2，·，m)为资源系 数：a(位=1,2，…，m;j=1,2,…,n)为技术系数。值得注意的是，今后所遇到的问题并 不全是经济学问题，但仍然这样称呼这些参数。 求解线性规划问题(1-1-3)只能通过算法（没有解析解的方法）进行。也就是说，不 能通过将上述参数代入某个公式然后求得该问题。因此，必须指定一种表达形式为标准 形式，这种标准形式必须是能很容易地将其他非标准形式化为该标准形式。本书规定的 线性规划问题的标准形式为： maxz=C1x1+C2r2+···+CnEn S.t. a111 a1272+...+ainIn b1 a2171 a222+...+a2ntn b2 (1-1-4) amlx1+am2x2+··+amnIn=bm x1≥0(i=1,2,·,n) 它有3个特点： (1)目标函数求极大。由于对于任何函数均有minz=-max(-z),可见，如果原问 题是对目标函数z求极小，则可以先求其相反函数（即一z)的极大，得到极大值之后，再 将函数值反号即可。 (②)所有约束条件都是等式约束。实际上，若第i个约束条件是“≤”，即 ai1x1+ai2x2+…+anxn≤b:第 1 章 线性规划及单纯形法 11 max(min) z = c1x1 + c2x2 + · · · + cnxn s.t.    a11x1 + a12x2 + · · · + a1nxn 6 (=, >)b1 a21x1 + a22x2 + · · · + a2nxn 6 (=, >)b2 · · · · · · am1x1 + am2x2 + · · · + amnxn 6 (=, >)bm xi > 0(i = 1, 2, · · · , n) (1-1-3) 在模型 (1-1-3) 中，称 z = c1x1+c2x2+· · ·+cnxn 为目标函数，对于该函数可能是求极 大 (max)，也可能是求极小 (min)。模型中写成 max(min) 是为了将两种情况写在一起以便 于说明，并非同时求极大和极小。称 ai1x1 +ai2x2 +· · ·+ainxn 6 (=, >)bi(i = 1, 2, · · · , m) 为约束条件。同样，式 (1-1-3) 右边的 6 (=, >) 是将可能的 3 种约束情况写在一起以 便于说明。最后 xi > 0(i = 1, 2, · · · , n) 称为决策变量的非负约束。由于线性规划问题 在经济学上的含义，称 ci(i = 1, 2, · · · , n) 为价值系数；bj (j = 1, 2, · · · , m) 为资源系 数；aij (i = 1, 2, · · · , m; j = 1, 2, · · · , n) 为技术系数。值得注意的是，今后所遇到的问题并 不全是经济学问题，但仍然这样称呼这些参数。 求解线性规划问题 (1-1-3) 只能通过算法 (没有解析解的方法) 进行。也就是说，不 能通过将上述参数代入某个公式然后求得该问题。因此，必须指定一种表达形式为标准 形式，这种标准形式必须是能很容易地将其他非标准形式化为该标准形式。本书规定的 线性规划问题的标准形式为： max z = c1x1 + c2x2 + · · · + cnxn s.t.    a11x1 + a12x2 + · · · + a1nxn = b1 a21x1 + a22x2 + · · · + a2nxn = b2 · · · · · · am1x1 + am2x2 + · · · + amnxn = bm xi > 0(i = 1, 2, · · · , n) (1-1-4) 它有 3 个特点： (1) 目标函数求极大。由于对于任何函数均有 min z = − max(−z)，可见，如果原问 题是对目标函数 z 求极小，则可以先求其相反函数 (即 −z) 的极大，得到极大值之后，再 将函数值反号即可。 (2) 所有约束条件都是等式约束。实际上，若第 i 个约束条件是“6”，即 ai1x1 + ai2x2 + · · · + ainxn 6 bi