线性规划及其解法

1、第一章 线性规划及其解法1 线性规划问题及其一般数学模型（掌握）2 线性规划问题的图解法（掌握）3 线性规划问题的单纯形解法（了解）3.1 单纯形法的基本思路确定初始基本可行解检查是否为最优解？求最优解的目标函数值确定改善方向求新的基本可行解是否3.2 单纯形法的计算步骤第一步：求出LP的初始基本可行解，列出初始单纯形表。确定初始基本可行解：约束条件全部是“”时，为每个约束条件加上一个松弛变量，化为标准形，则系数矩阵中含有一个单位矩阵，以此为基，得到初始基本可行解为： X=（0，0，b1,b2,bm)约束条件为=或时，化标准形后，一般不含单位矩阵，可以添加人工变量构造一个单位矩阵作为基（人工基

2、）。如例1：系数矩阵为： 1 1 1 0 0 2 1 0 1 0 初始可行基 0 1 0 0 1X=（0，0，300，400，250）基本可行解初始单纯形表：cj50100000CBXBbx1x2x3x4x50 x3300111000 x4400210100 x525001001zj00000j =cj-zj50100000第二步：最优性检验最优解判别定理： max型问题，对于某个基本可行解，如果所有检验数j0，则现有基本可行解为最优解。第三步：基变换确定入基变量 若j 0，对应的变量xj就可作为入其变量，当有一个以上检验数大于零时，从中找出最大的一个。k=maxj|j 0 。确定出基变量 x

3、l称为出基变量 alk称为主元素迭代。 用入基变量替换出基变量，得到一个新的基和基本可行解，画出一个新的单纯形表。行变换：初始单纯形表：cj50100000CBXBbx1x2x3x4x50 x3300111000 x4400210100 x525001001zj00000j =cj-zj50100000第四步：重复二、三步直到计算结束为止。cj50100000CBXBbx1x2x3x4x50 x3501010-10 x41502001-1100 x22500 1001zj010000100j =cj-zj50000-100cj50100000CBXBbx1x2x3x4x550 x1501010

4、-10 x45000-211100 x22500 1001zj5010050050j =cj-zj00-500-50习题1：下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxz=5x1+3x2，约束形式为，x3,x4为松驰变量，表中解代入目标函数后得z=101、求a-g的值；2、表中给出的解是否为最优解？a=2,b=0,c=0,d=1,e=4/5,f=0,g=-5表中给出的解为最优解。习题2：目标函数为max Z =28x4+x5+2x6，约束形式为“”，且x1，x2，x3为松弛变量，表中的解代入目标函数中得Z=14，求出a-g的值，并判断是否最优解？Cj0002812XBC

5、BbX1X2X3X4X5X6X62a30-14/3011X2056d205/20X42800ef100Cj-Zjbc00-1ga=7,b=-6,c=0,d=1,e=0,f=1/3,g=0最优解。 复习单纯型法的几种特殊情况作业：P25（6）第6小题当c1值从2变为2.5，c2值从3变为2.5时，其最优解是否变化？为什么?正确方法用只有当计算机求解时，才用百分百法则。P36（4）最优解为x1=8.5 x2=1.5 x3=0 x4=0目标函数为：maxZ=2x1+x2-x3+x4(4)当c1,c2,c4值不变时，C3在-到5.5范围内变化时，最优解不变，此时最优目标函数值不变。因为x3=0，目标函

6、数系数变化，不影响目标函数值的变化。（5）当c2, c3,c4值不变时， c1在0到+范围内变化时，最优解不变，此时最优目标函数值改变。 在一个已得到最优解的单纯形表中，如果存在某个非基变量的检验数为零，说明有无穷多最优解。一、无穷多最优解 若j0，线性规划的最优解里还有人工变量，则此线性规划问题无可行解。二、 存在一个大于零的检验数j，并且该列系数向量每个元素都0，则线性规划问题是无界的。一般地说此类问题的出现是由于建模错误所引起的。三、无界解 在单纯形法计算过程中，基变量有时存在两个以上相同的最小比值，这称之为退化。四、 如果是退化现象，可能经过6次迭代后得到的单纯形表与第0次单纯形表一样

7、，这样就出现了循环。 为了避免这种现象，当存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。1、表中解为唯一最优解2、表中解为最优解，但存在无穷多最优解3、该线性规划问题具有无界解4、表中解非最优，为对解改进，换入变量为x1，换出变量为x5。习题一、下表是求某极大化线性规划问题计算得到的单纯形表，表中无人工变量，a1,a2,d,c1,c2为待定常数，试说明这些常数分别取何值时，以下结论成立。4-a012a-221Z-a+80-12a014x11-201-1101x22-1121002x50 x6x5x4x3x2x1bxBcB000221cj1、把表中缺少的项目填上适当的数或式子2

8、、要使上表成为最优表，a应满足什么条件3、何时有唯一最优解4、何时有无穷多最优解5、何时以x3替换x1习题二、下表是求某极大化线性规划问题计算得到的单纯形表，表中无人工变量，a为待定常数， a取何值时，以下结论成立。1Z-a+8-12a4x1-21-11x22-1212x5x6x5x4x3x2x1bxBcB22cj1、把表中缺少的项目填上适当的数或式子2、要使上表成为最优表，a应满足什么条件3、何时有唯一最优解4、何时有无穷多最优解5、何时以x3替换x12、2a 43、2a44、 2a 4 a=2或a=45、1a4/2a 0a0无界解无可行解无穷多最优解找出主元素，迭代是是否否否是是3.5 单

9、纯形法的灵敏度分析-目标函数中ck的灵敏度分析当ck变成ck +ck原规划最优解不变的条件是： j 0在最终的单纯形表中，xk是非基变量时k = ck+ck- zk= ck +k 0即： ck -k 例在最终的单纯形表中，xk是基变量时j = cj-zj=cj-（zj+ckakj ）0 即：j+ckakj0 例C3变化：cj50100c300CBXBbx1x2x3x4x550 x1501010-10 x45000-211100 x22500 1001zj5010050050j =cj-zj00C3-500-50C1变化：cjc1100000CBXBbx1x2x3x4x5c1x1501010-1

10、0 x45000-211100 x22500 1001zjc1100c10100-c1j =cj-zj00-c10c1-100C2变化：cj50c2000CBXBbx1x2x3x4x550 x1501010-10 x45000-211c2x22500 1001zj50c2500C2-50j =cj-zj00-50050-c2约束方程右端常数项灵敏度分析原规划最优基不变的条件：B-1(b+b)= B-1 b+ B-1 b0原规划最优基改变的条件：B-1(b+b)至少有一个分量小于零。约束方程系数矩阵A灵敏度分析非基变量xk的系数pk变成pk k =ck-cB B-1 pk 0 最优解不变，否则继

11、续进行迭代。基变量的系数发生变化 通常需要重新计算复习：关于灵敏度分析当目标函数系数ck变化时： 原规划最优解不变的条件是： j 0 （情况一；情况二）P30图3-4当右端项bi变化时： 原规划最优基不变的条件是： 新解的每一个分量大于等于零。即： B-1(b+b)= B-1 b+ B-1 b0系数矩阵A变化时 非基变量系数变化时，最优解不变的条件是k 0 基变量系数变化时，需重新计算软件中如何识别无穷多最优解情况P112如果在最终表上检验数为零的非基变量是松弛变量或剩余变量： 计算机输出的约束条件栏中有一个约束条件的松弛变量或剩余变量为零，且其对偶价格也为零，表明有无穷多最优解。如果在最终单纯形表上，检验数为零的非基变量是一般决策变量。 在计算机输出中，若有一个取值为零的决策变量其相差值也为零，说明有无穷多最优解。对偶价格：约束条件右端项增加一个单位而使最优目标函数值得到改进的数量，称为这个约束条件对偶价格（yi)。约束条件中的松弛变量（剩余变量）不为零时，这个约束条件对偶价格为零。单纯形表中对偶价格： 约束类型 对偶价格的取值 等于对应的松弛变量的zj值 等于对应的剩余变量的zj值相反数 等于对应的人工变量的zj值对偶价格大于零，会使最优目标函数值得到改进。（求最大时更大，求最小时更小）对偶价格小于零，会使最优目标函数值变坏。 （求最大时变小，求最小时变大）