21x11+25x12+7x13+15x14+51x21+51x22+37x23+15x24
的最小值。显然x11, x12, x13, x14, x21, x22, x23, x24不能任意取值，我们还有“甲地调出物资2000吨”、“供给A地1700吨”等条件限制。总结需求及条件限制，得到下面的完整数学模型：
?min??t?s..???????????f?21x11?25x12?7x13?15x14?51x21?51x22?37x23?15x24x11?x12?x13?x14?2000,x21?x22?x23?x24?1100,x11?x21?1700,x12?x22?1100,x13?x23?200,x14?x24?100,xij?0,i?1,2,j?1,2,3,4
该模型的现实含意为：在x11+x12+x13+x14 = 2000等条件下，求
f = 21x11+25x12+7x13+15x14+51x21+51x22+37x23+15x24
的最小值。(这里先做出数学模型，以后再考虑求解方法)
例2 某工厂用3种原料P1，P2，P3生产3种产品Q1，Q2，Q3。已知单位产品需要的原料数、单位产品的利润、原料总量等条件如下表所示，制定出总利润最大的生产计划。
单位产品所 产 需原料kg 品 原料 Q1 2 0 3 3 Q2 3 2 2 5 Q3 0 4 5 4 原料可用量 （kg /日） 1500 800 2000 P1 P2 P3 单位产品利润 (千元)
2
解：设三种产品的生产量分别为x1, x2, x3时可以得到最大利润
3x1+5x2+4x3，则由题意，我们可以得到完整的模型为
?maxz?3x1?5x2?4x3?s..t2x1?3x2?1500,??2x2?4x3?800, ??3x1?2x2?5x3?2000,?xj?0,j?1,2,3??
总结这两个例子，可以看到其共同点：都是在对未知量做出线性约束的前提下，求未知量线性组合的最值。我们将最大、最小值统一为最小值，假设线性约束有等式、有不等式，未知量有些必须非负、有些不受限制，可以得到下面的一般线性规划模型：
线性规划（LP）问题的一般形式
?minz?c1x1?c2x2???cnxn?s..tai1x1?ai2x2???ainxn?bi,i?1,?,p??ai1x1?ai2x2???ainxn?bi,i?p?1,?,m ??xj?0,j?1,2,?,q?xj任意,j?q?1,?,n??（等式不都在前面怎么办？非负变量不都在前面怎么办？调
一调。）
LP模型中的术语：
目标函数(指标函数、指标)： z?c1x1?c2x2???cnxn 价值系数： c1,c2,?,cn， 价值向量： c?[c1,c2,?,cn]T
3
决策变量： x1,x2,?,xn， 决策向量： x?[x1,x2,?,xn]T 上述记法可以使指标写成：z?cTx
ai1x1?ai2x2???ainxn?bi,i?1,?,pai1x1?ai2x2???ainxn?bi,i?p?1,?,m xj?0,j?1,2,?,qxj任意,j?q?1,?,n约束：
约束矩阵：
?a11?a??21????am1a12a22?am2?a1n??a2n?? ?????amn?m?nA?(aij)m?n右端向量： b?[b1,b2,?,bm]T 非负约束： xj?0,j?1,2,?,q 自由变量： xj,j?q?1,?,n
可行解、可行点： 即满足约束的点，也就是满足约束的一组未知量的取值，该组值不一定能使得指标达到最小值。
可行域D：可行解集合
最优解：使得指标最小的可行解(不一定唯一，甚至不一定存在)。
利用上面的一些记法，在某些条件下，可以得到LP模型的特殊形式，至少在形式上显得简炼一些，实际上今后的许多分析是基于这些简炼形式的。
LP问题的规范形式
4
一般形式中p=0, q=n 时，称为规范形式。
??mincTx?s..tAx?b
??x?0
一般形式与规范形式的转化 将ai1x1?ai2x2???ainxn?bi化为
??ai1x1?ai2x2???ainxn?bi??ai1x1?ai2x2???a inxn??bi令x???j?x?j-xj，xj?0，xj?0,j?q?1,?,n. 例：将下面的线性规划转化为规范形式
??maxz??x1?x2-2x3??s..t2x1?x2??2?x?1 ?2x2?3 ?x1,x2?0??x3自由解：
??minz?x1-x2?2x3?s..t2x1?x2?0x3??2??minz?x1-x2?2x4?2x5???-2xs..t2x1?x2?0x4-0x5?1+x2-0x3?2???2-2x?-x，?1+x2-0x4+0x5?21 ?2x2?-3???x-x1 ?2x2?0x4-0x1,x2?0?5?-3??xx1,x2,x4,x5?3自由??0c?[1,-1,2,?2]T，x?[x1,x2,x4,xT5]，
5
?2－100??，b?[?2, 2, -3]T A??－2100????－1200??
LP问题的标准形式
一般形式中p=m, q=n 时，称为标准形式。
?mincTx?tAx?b ?s..?x?0?
一般形式与标准形式的转化 对ai1x1?ai2x2???ainxn?bi
ai1x1?ai2x2???ainxn?xis=bi，xis?0，i?p?1,?,m.
???令xj?x?-x，x?0，x,?,n. jjjj?0,j?q?1这里的xis称为剩余变量。
例：将下面的线性规划转化为标准形式
?maxz??x1?x2-2x3?s..t2x1?x2??2??x1 ?2x2?3 ??x1,x2?0?x3自由??解：
6