1、第 1 页 共 27 页 第一部分 线性规划问题的求解 一、两个变量的线性规划问题的图解法： 概念准备： 定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。 定义：达到目标的可行解为最优解。 图解法： 图解法采用直角坐标求解： x1 横轴； x2 竖轴。 1、将约束条件（取等号）用直线绘出； 2、确定可行解域； 3、绘出目标函数的图形（等值线），确定它向最优解的移动方向； 注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。 4、确定最优解及目标函数值。 参考例题：（只要求下面这些有唯 一最优解的类型） 例 1：某厂生产甲、乙两种产品，这两种产品均需在 A、
2、 B、 C 三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示： A B C 利润 （万元） 甲 乙 3 5 9 9 5 3 70 30 有效总工时 540 450 720 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？ （此题也可用“ 单纯形法 ”或化“ 对偶问题 ”用大 M 法求解） 设 备 消 耗 产 品 第 2 页 共 27 页 解：设 x1、 x2为生产甲、乙产品的数量。 max z = 70x1+30x2 s.t. 072039450555409321212
3、121xxxxxxxx，可行解域为 oabcd0，最优解为 b 点。 由方程组 72039450552121 xx xx 解出 x1=75， x2=15 X*= 21xx =（ 75， 15）T max z =Z*= 7075+3015=5700 、 第 3 页 共 27 页 例 2：用图解法求解 max z = 6x1+4x2 s.t. 0781022122121xxxxxxx，解： 可行解域为 oabcd0，最优解为 b 点。 由方程组 81022121 xx xx 解出 x1=2， x2=6 X*= 21xx =（ 2， 6）T max z = 62+46=36 、 第 4 页 共 27
4、 页 例 3：用图解法求解 min z = 3x1+x2 s.t. 08212523421212121xxxxxxxx，解： 可行解域为 bcdefb，最优解为 b 点。 由方程组12524211 xxx 解出 x1=4， x2=54 X*= 21xx =（ 4， 54 ）T min z = 34+54 = 11 51 、 第 5 页 共 27 页 二、标准型线性规划问题的单纯形解法： 一般思路： 1、用简单易行的方法获得初始基本可行解； 2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入 3； 3、根据 L规则确定改进解的方向； 4、根据可能改进的方向进行迭代得到新的解； 5
5、、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入 3，直至最优解。 具体做法（可化归 标准型 的情况）： 设已知 max z = c1x1+ c2x2+ c nxn s.t. njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn， . . .210. . . . . . . . . . . . . . .22112222212111212111对第 i 个方程加入松弛变量 xn+i， i =1， 2， ， m，得到 njxbxxaxaxabxxaxaxabxxaxaxajmmnnmnmmnnnnnn， . . .210. . . . . . . . . . .
6、. . . .2211222222121111212111列表计算，格式、算法如下： 第 6 页 共 27 页 CB XB b c1 c2 cn+m L x1 x2 xn+m cn+1 xn+1 b1 a11 a12 a1 n+m c n+2 xn+2 b2 a21 a22 a2 n+m . . . . . . . . . cn+m xn+m bn am1 am2 am n+m z1 z2 zn+m 1 2 n+m 注： zj =cn+1 a1j+ cn+2 a2j + cn+m amj= mi ijinac1，（ j=1， 2， ， n+m） j =cj zj ,当 j 0 时，当前解最优。
7、 注： 由 max j确定所对应的行的变量为“入基变量”； 由 L= 0m inikikii aab确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主 元素变为 1，此列其余元素变为 0。 例 1：用单纯形法求解 （本题即是本资料 P2“ 图解法 ”例 1 的单纯形解法 ； 也可化“ 对偶问题 ”求解） max z =70x1+30x2 s.t. 072039450555409321212121xxxxxxxx，解：加入松弛变量 x3， x4， x5，得到等效的标准模型： max z =70x1+30x2+0 x3+0 x4+0 x5 第 7 页 共 27 页 s.t.
8、5, . . . ,2,1,07 2 0394 5 0555 4 093521421321jxxxxxxxxxxj列表计算如下： CB XB b 70 30 0 0 0 L x1 x2 x3 x4 x5 0 x3 540 3 9 1 0 0 540/3 =180 0 x4 450 5 5 0 1 0 450/5 =90 0 x5 720 （ 9） 3 0 0 1 720/9 =80 0 0 0 0 0 70 30 0 0 0 0 x3 300 0 8 1 0 - 1/3 300/8 =37.5 0 x4 50 0 （ 10/3） 0 1 - 5/9 50/10/3 =15 70 x1 80 1
9、 1/3 0 0 1/9 80/1/3 =240 70 70/3 0 0 70/9 0 20/3 0 0 70/9 0 x3 180 0 0 1 12/5 1 30 x2 15 0 1 0 3/10 - 1/6 70 x1 75 1 0 0 - 1/10 1/6 5700 70 30 0 2 20/3 0 0 0 -2 20/3 X*=（ 75， 15， 180， 0， 0） T max z =70 75+30 15=5700 第 8 页 共 27 页 例 2：用单纯形法求解 max z =7x1+12x2 s.t. 0300103200543604921212121xxxxxxxx，解：加入
10、松弛变量 x3， x4， x5，得到等效的标准模型： max z =7x1+12x2+0 x3+0 x4+0 x5 s.t. 5, . . . ,2,1,03001032005436049521421321jxxxxxxxxxxj列表计算如下： 第 9 页 共 27 页 CB XB b 7 12 0 0 0 L x1 x2 x3 x4 x5 0 x3 360 9 4 1 0 0 360/4 =90 0 x4 200 4 5 0 1 0 200/5 =40 0 x5 300 3 （ 10） 0 0 1 300/10 =30 0 0 0 0 0 7 12 0 0 0 0 x3 240 78/10
11、0 1 0 - 2/5 240/78/10 =2400/78 0 x4 50 （ 5/2） 0 0 1 - 1/2 50/5/2 =20 12 x2 30 3/10 1 0 0 1/10 30/3/10 =100 18/5 12 0 0 6/5 17/5 0 0 0 6/5 0 x3 84 0 0 1 78/25 29/25 7 x1 20 1 0 0 2/5 - 1/5 12 x2 24 0 1 0 3/25 4/28 428 7 12 0 34/25 11/35 0 0 0 34/25 11/35 X*=（ 20， 24， 84， 0， 0） T max z =7 20+12 24=428
12、 三、非标准型线性规划问题的解法： 1、一般地，对于约束条件组： 若为“”，则加松弛变量，使方程成为“”； 若为“”，则减松弛变量，使方程成为“”。 我们在前面 标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为 非标准型 。可作如下处理： 第 10 页 共 27 页 由目标函数 min z=nj jjxc1变成等价的目标函数 max（ z） =nj jjxc1)( 令 z=z/， min z= max z/ 2、等式约束 大 M 法： 通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数为 M， M 是很大的正数，从原理上理解又称为“惩罚系数”。（课本 P29） 类型一 ：目标函数仍为 max z，约束条件组与。 例 1： max z =3x1+5x2 s.t. 018231224212121xxxxxx，解：加入松弛变量 x3， x4，得到等效的标准模型： max z =3x1+5x2 s.t. 4,3,2,1,018231224214231jxxxxxxxj其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量 x5，得到： max z =3x1+5x2 Mx5 s.t. 5, . . . ,2,1,0182312245214231jxxxxxxxxj
