精品课程《高等数学》（线性代数部分）电子教案
ax?ax?...?ax?b(或?b，或?b)ax?ax?...?ax?b(或?b，或?b)1111221nn1112112222nn222........................................
n22max?ax?...?ax?b(或?b,或?bx?0(i?1,2,...,n)m1i1m22mn)我们称这种形式的线性规划模型为一般形式。其中，Cj为目标函数系数约束方程系数；bi为约束方程常数项；(i=1,……,m;j=1,……,n).
由此可见，一个线性规划问题问题的数学模型，必须含有三个要素：决策变量、约束条件和目标函数。
由上面的例子可知，线性规划问题的数学模型的一般形式很多。目标函数有求最大值和最小值；约束条件有“≤”，“≤”，“＝”三种情况。这种多样性给问题的讨论带来很大的不便。为此，我们介绍线性规划问题的一种统一形式—标准形式。规定线性规划问题的数学模型的标准形式为：
minS?C1x1?C2x2?...?Cnxn
ax?ax?...?ax?bax?ax?...?ax?b1111221nn12122222nn2.....................S.t ..........
mnnmax?ax?...?ax?bx?0(j?1,2,...,n)m11m22i线性规划问题的标准（13.1）也可写成矩阵形式
minS?CX
s.t AX?bX?0
其中C?(c1,c2,......,cn)，
?a12a12?a1n??x1??b1??????????????X＝?x2? ，A＝?a21a22a2n? ，B＝?b2?
????...?????aa...a??x??b?mn??m1m2?3??m?对于线性规划问题的一般形式，可以按如下方法化成标准形：
（1）如果线性规划问题是求目标函数的最大值，即求maxS?c1x1????cnxn，只要令S???S，即可化为求目标函数的最小值，即求minS???c1x1?c2x2???cnxn （2）如果某个约束条件为线性不等式，则可将其化为线性议程式的形式。
第 6 页 共 10 页
精品课程《高等数学》（线性代数部分）电子教案
设第k个约束条件为ak1x1?ak2x2???akmxn?bk： 则加入一个新变量，将其约束条件改为：
ax?ax??ax?xk11k22knnn?k?bk
这个所加的变量称为松弛变量。
若第l个约束条件为：al1x1?al2x2??alnxn?bl 则加入一个新变量，将上述约束条件变为：
ax?ax???ax?xl11l22lnnn?l?bl
（3）若对某变量没有非负限制，则引进两个非负变量x?j?0,x??j?0
令xj?x?j?x??j 代入约束条件和目标函数，可化为全部变量都有非负限制。 例4 将下列线性规划模型化为标准形 maSx??2x1?3x2
?x2?x2?5?? S.t?3x1?x2?2
???x1?0,x2为非负限制
解 引入松驰变量x3?0,x4?0，令S???S,x2?x?2?x??2且x?2?0,x??2?0
??2x1?3x?2?3x?即可得标准形式如下 miSn?2
?x?2x??2x???x?51223?? S.t?3x1?x?2?x??2?x4?2
??0,x??2?0,xj?(j?1,3,4)??x2
§3 线性规划问题解的性质及图解法 一、 线性规划问题的解的性质 对于线性规划问题（13.2）： minS?CX
?AX?b S.t?
X?0?
1．几个概念
第 7 页 共 10 页
精品课程《高等数学》（线性代数部分）电子教案
TX?(,?,)（1）可行解：满足线性规划问题所有约束条件的向量x1xn称为可行．．．
(0)(0)解，所有可行解构成的集合称为可行域，记为R，则R＝｛x|Ax?b,x?0｝ （2）基础可行解：若可行解X＝0，或X的非零分量所对应的系数列向量线性无关，．．．．．则称X为基础可行解。
（3）最优解：使目标函数取最小值的可行解称为最优解。 ．．．
（4）基础最优解：使目标函数取最小值的基础可行解称为基础最优解。 ．．．．．
（5）凸集：若连接n维点集S中任意两点x1,x2的线段仍要S内，则称S为凸集。．．换言之，若
?x|x??x??1???x,0???1,x,x?S??S,S?E1212n
则称S为凸集。 （6）极点：若凸集S中的点x,不能成为S中任何线段的内点，则称x为S的极点。．．换言之，若对任意不同两点x1,x2?S,不存在?(0??1)，使 x??x1?(1??)x2?S
则称x为S的极点。例如，圆周上的点都是极点。 （7）凸集合：设xi?E，实数．．．
n??0,i?1,2,??,s,且??ii?1si?1,则称
x??x??x?????112ss
为点x1,x2,??,xs的一个凸组合。
2．线性规划问题的解
由线性代数求解议程组的方法及上述概念可知，线性规划问题（LP）的解有如下几种情况：
有唯一最优解
有可行解 有无穷多最优解 无最优解
无可行解
3．线性规划问题解的性质
性质1 线性规划问题（LP）的可行域R??X|AX?b,X?0?是凸集。
性质2 可行域R中的点x是极点的充要条件是x是基础可行解。
性质3 若（LP）问题的可行域R≠Φ，则R至少有一极点，且极点的个数有限。 性质4 最优值可以在极点上达到。
这几条性质实际上给我们指出了线性规划问题求解的思路和方向：由于线性规划问题的最优解一定能在可行解集的极点达到，而极点的数目中有限的。所以，总可以想办法在有限的极点中经过有限次寻找，得到最优解。因而，就有了求解线性规划问题的图解法和单纯形法。由于篇幅所限，下面仅介绍图解法的应用。有兴趣
第 8 页 共 10 页
精品课程《高等数学》（线性代数部分）电子教案
的读者可以学习一下单纯形法。
二、图解法（又称几何法）
图解法是对于只是两个决策变量的线性规划问题，在平面内建立直角坐标系，使每个决策变量的取值在一个数轴上表示出来，可行解就成为平面上的点，可行域就是平面上的一个共域，从而最优解必定是在这个平面区域内（包括边界上）的点。根据目标函数在这个平面区域内的取值找出使目标函数取得最优值的点（即最优解）。
图解法便于我们理解和了解线性规划问题的一些概念、理论及解的一些特性，也为我们进一步学习单纯方法提供一个直观图形。 例5 求解线性问题 miSn?7x1?5x2
?x1?2x2?28??S.t?4x1?x2?42 ???x1,x2?0解 第一步，在平面直角坐标系Ox1x2上绘出约束条件图（图13－2） ①画出这条直线x1?2x2?28，再定出x1?2x2?28区域。
把（0，0）代入不等式得0＋2〃0＜28，所以，原点所在半平面及直线本身就是
x?2x12?28代表的区域。
②画出4x1?x2?42这条直线，定出4x1?x2?42代表的区域，有（0，0）代入不等式得0〃4＋0＜42所以，4x1?x2?42代表的区域是包括原点的下半平面与直线本身。
③定出x1?0,x2?0的区域，它就是第一象限。从图
7x1?5x2?106 13－2看出，满足全部约束条件的点所构成的区域（即
7x1?5x2?50 可行域），就是凸多边形OABC。
4x1?x2?42 第二步，绘制目标函数图形。对于目标函数S?7x1?5x2 将S看作参数，即得到一簇平行直线（图13－2中虚线所
示），直线上每一点的目标函数值为S。由图可见，直线离 原点越远，S值越大，我们寻找的是在可行域内使S值最大 点。可见，B点即为可行域内使目标函数最大的点，即为最 优解。
第三步，确定最优解。B点是直线x1?2x2?28与4x1＋x2＝42 交点，所以
?x1?2x?28?2解方程组?得到x1?8,x2?10 ??4x1?x2?42第 9 页 共 10 页
x?2x?28 117x1?5x2?0精品课程《高等数学》（线性代数部分）电子教案
这就是最优解。将其代入目标函数，得最优解maxS?7?8?5?10?106
例5有可行解且有唯一最优解将目标函数改为
S?x1?2x2或S?4x1?x2仍求其最大值，则BC或AB上每一点的坐标均为最优解，最优解有无穷多个，而它们对应的目标函数数值是28或42。读者可以证明习题中第4题的（1）小题有可行解但无最优解（2）小题没有可行解。这就说明了线性规划问题解的情况。
习题十三 1．写出下列问题的数学模型：
（1） 某工厂生产甲、乙两种产品，每件纯利为5元和4元，生产这两种产品每件
需机器工作时间2小时和3小时，需人力工时4小时和2小时。已知该工厂每天能提供300小时的机器工作和320小时的人力工时，问应如何安排生产，才能使工厂获利最多？
（2） 某产品需经两道工序加工才能完成，共有工人30名，按照过去的经验，第一
道工序每个工人每天能加工产品100件，第二道工序每个工人每天能加工产品200件，问应如何安排生产才能使连续生产过程中出成品最多？ 2．将下列线性规划问题的数学模型化为标准形式
（1）maxS?2x1?3x2 （2）minS?2x1?x2
?x1?x2?1?x1?x2?4????S.t??x1?2x2?2 S.t?x1?x2?5 ???0,?0??x2?x1?x1?0,x2?03．用图解法解第1题。
4．用图解法解第2题。
第 10 页 共 10 页