第一节线性规划问题及其数学模型 ()目标函数是求极小值，即为： min Z=∑cx j=1 因为求解minZ等价于求解max(-Z),令 W=-Z,即化为： maxW=-∑c,X j-1 (2)右端项b<0时，只需将等式或不等式两 端同乘-1，则等式右端项必定大于零。 23
23 (1)目标函数是求极小值，即为： = = n j j j Z c x 1 min 因为求解min Z等价于求解max (–Z)，令 W＝ –Z，即化为： = = − n j j j W c x 1 max (2)右端项bi<0时，只需将等式或不等式两 端同乘 –1，则等式右端项必定大于零。 第一节 线性规划问题及其数学模型
第一节线性规划问题及其数学模型 (③)约束条件为不等式。当约束条件为“≤” 时，例如6x1+2x2≤24，可令：X3=24-6x1-2x2或 6x1+2x2+x3=24。显然，x320。当约束条件为“≥月 时，如有10x1+12x2218,可今：x4=10x1+12x2-18 或10x1+12x2X4=18,x420。X3和x4是新加上去的 变量，取值均为非负值，加到原约束条件中去的 目的是使不等式转化为等式，其中x称为松弛变 量，X4一般称为剩余变量 24
24 (3)约束条件为不等式。当约束条件为“≤” 时，例如6x1+2x2≤24，可令：x3 ＝24–6x1 –2x2或 6x1+2x2+x3 =24。显然，x3≥0。当约束条件为“≥” 时，如有10x1+12x2≥18，可今：x4 ＝10x1+12x2 –18 或10x1+12x2 –x4 =18，x4≥0。x3和x4是新加上去的 变量，取值均为非负值，加到原约束条件中去的 目的是使不等式转化为等式，其中x3称为松弛变 量，x4一般称为剩余变量。 第一节 线性规划问题及其数学模型
第一节线性规划问题及其数学模型 松弛变量或剩余变量在实际问题中分别表示未 被充分利用的资源和超出的资源数，均未转化为价 值和利润，所以引进模型后它们在目标函数中的系 数均为零。 (4)取值无约束的变量。如果变量x代表某产品 当年计划数与上一年计划数之差，显然x的取值可 能是正也可能为负，这时可令x=x1-X2,其中x20 x220,将其代入线性规划模型即可 ⑤)对x≤0的情况，令x1=-x,显然x1≥0 25
25 松弛变量或剩余变量在实际问题中分别表示未 被充分利用的资源和超出的资源数，均未转化为价 值和利润，所以引进模型后它们在目标函数中的系 数均为零。 (4)取值无约束的变量。如果变量x代表某产品 当年计划数与上一年计划数之差，显然x的取值可 能是正也可能为负，这时可令x = x1 – x2，其中x1≥o， x2≥0，将其代入线性规划模型即可。 (5)对x≤0的情况，令x1 = -x，显然x1≥0。 第一节 线性规划问题及其数学模型
第一节线性规划问题及其数学模型 例2将下述线性规划化为标准形： min Z x1+2 x2 3x3 2x1+x2+x3≤9 -3x1+x2+2x3≥4 4x1-2x2-3x3=-6 x1≤0，x2≥0，x取值无约束 解：令W=-Z,X11=-X1,3=31-32,其中x11, x31,3220,按上述规则，该问题的标准形为： 26
26 例2 将下述线性规划化为标准形: min Z = x1 + 2 x2 + 3x3 − − = − − + + + + 1 2 3 取值无约束 1 2 3 1 2 3 1 2 3 0, 0, 4 2 3 6 3 2 4 2 9 x x x x x x x x x x x x 解: 令W = -Z, x11 = -x1， x3 = x31 - x32, 其中x11， x31，x32≥0，按上述规则，该问题的标准形为： 第一节 线性规划问题及其数学模型
第一节线性规划问题及其数学模型 muxW=x11-2x2-3x31+3x32 21+x2+X31-X32+4=9 3x1+3+2x1-2xX2-X=4 -4x1+2x2+3X31-3x32=6 XX2?X31932?X4?X3≥0 (介绍范例的图解法) 27
27 − + + − = + + − − = + + − + = 0 4 2 3 3 6 3 2 2 4 2 9 1 1 2 3 1 3 2 4 5 1 1 2 3 1 3 2 1 1 2 3 1 3 2 5 1 1 2 3 1 3 2 4 x x x x x x x x x x x x x x x x x x x x ， ， ， ， ， max W = x11 – 2 x2 – 3x31+ 3x32 第一节 线性规划问题及其数学模型 （介绍范例的图解法）