《运筹学》复习参考资料知识点及习题

《运筹学》复习参考资料知识点及习题第一部分：线性规划问题的求解一、两个变量的线性规划问题的图解法：1.概念准备：可行解是指满足所有约束条件的解，可行解的全体称为可行（解）域。达到目标的可行解为最优解。2.图解法：图解法采用直角坐标求解，其中x1为横轴，x2为竖轴。具体步骤如下：步骤1：将约束条件（取等号）用直线绘出；步骤2：确定可行解域；步骤3：绘出目标函数的图形（等值线），确定它向最优解的移动方向。如果要求极大值，则沿价值系数向量的正向移动；如果要求极小值，则沿价值系数向量的反向移动。步骤4：确定最优解及目标函数值。3.参考例题：例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工。每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：设备消耗品利润（万元）有效总工时A甲703x1+9x2≤540B甲305x1+5x2≤450C甲—12x1+12x2≤720A乙603x1+9x2≤540B乙405x1+5x2≤450C乙5012x1+12x2≤720问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？解：设x1、x2为生产甲、乙产品的数量。则目标函数为：maxz=70x1+30x2约束条件为：3x1+9x2≤5405x1+5x2≤45012x1+12x2≤720x1，x2≥0可行解域为oabcd0，最优解为b点。由方程组5x1+5x2=4509x1+3x2=720解出x1=75，x2=15因此，最优解为（75，15），最大利润为5700万元。例2：用图解法求解maxz=6x1+4x2s.t.2x1+x2≤10x1+x2/2≤8x1≤7x1，x2≥0可行解域为oabcd0，最优解为b点。由方程组2x1+x2=10x1+x2/2=8解出x1=2，x2=6因此，最优解为（2，6）。例3：使用图解法解决以下线性规划问题：minz=-3x1+x2s.t.⑴x1≤4x2≤32x1+5x2≥12x+2x≤8x1，x2≥0解：可行解区域为bcdefb，最优解为点b。解方程组得到x1=4，x2=2计算可得最小值为-11。二、单纯形法解决标准型线性规划问题：1.获得初始基本可行解；2.检验解是否为最优解，如果是则停止迭代，否则进行下一步；3.根据θL规则确定改进解的方向；4.迭代计算新解；5.检验新解是否为最优解，如果是则停止迭代，否则回到第3步，直到获得最优解。具体做法如下：maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+...+a1nxn≤b1a21x1+a22x2+...+a2nxn≤b2...am1x1+am2x2+...+amnxn≤bmxj≥0，j=1，2，...，n将每个方程加入松弛变量xn+i（i=1，2，…，m），得到：a11x1+a12x2+...+a1nxn+xn+1=b1a21x1+a22x2+...+a2nxn+xn+2=b2...am1x1+am2x2+...+amnxn+xn+m=bmxj≥0，j=1，2，...，n+m然后进行列表计算，得到最优解。单纯形法是一种常用的线性规划求解方法。其基本思想是通过不断迭代，不断寻找目标函数值更大（或更小）的解，直到找到最优解为止。具体来说，每次迭代都选择一个“入基变量”和一个“出基变量”，并将主元素变为1，使得目标函数值得以增加（或减少）。迭代结束的条件是所有的“σj”均小于等于0，此时当前解为最优解。例如，我们考虑以下线性规划问题：maxz=70x1+30x2s.t.3x1+9x2≤5405x1+5x2+12x3≤4509x1+3x2≤720x1,x2≥0我们可以通过引入松弛变量x3、x4和x5，将其转化为标准模型：maxz=70x1+30x2+0x3+0x4+0x5s.t.3x1+9x2+x3=5405x1+5x2+x4=4509x1+3x2+x5=720x1,x2,x3,x4,x5≥0然后，我们可以使用单纯形法求解该问题。具体来说，我们需要构造一个“表格”，其中第一行为“Cj-Zj”，第一列为“B”，其余元素为系数。然后，我们需要不断迭代，直到找到最优解为止。在每次迭代中，我们需要选择一个“入基变量”和一个“出基变量”，并将主元素变为1，使得目标函数值得以增加（或减少）。具体来说，我们需要找到“σj”最大的那一列，然后找到对应的“θL”，即“Bi/Aik”最小的那一行。然后，我们将该行除以对应的主元素，使得该主元素变为1，并将该列的其余元素变为0。最后，我们更新“Cj-Zj”和“B”，并继续迭代，直到找到最优解为止。在本例中，我们可以得到以下表格：7030CB703070XBx3x4x5b54045072030050801801575x135970/320/31/3x295330810/3x3111300/950/970/9x411-12/56-2/5-1/5x51-1/3-5/91/970/9-70/9σj-2/3-1/30θL1809080从上表可以看出，当前解不是最优解，因为存在“σj”大于0的列。我们选择“σj”最大的那一列，即第一个列，然后找到对应的“θL”，即第一行的“Bi/Aik”最小的那个元素，即“180/3=60”。因此，我们将第一行除以3，使得主元素变为1，并将该列的其余元素变为0。更新“Cj-Zj”和“B”，得到以下表格：7010/3CB60300XBx1x4x5b180300/2=150120203010x31-2/31/35010/310/3x204/3-5/320-10/3-10/3x301/32/320/320/950/9x41/31/3-4/152/3-2/15-1/15x50-1/3-2/91/920/9-20/9σj000θL15020120/4=30从上表可以看出，当前解仍然不是最优解，因为存在“σj”大于0的列。我们选择“σj”最大的那一列，即第二个列，然后找到对应的“θL”，即第二行的“Bi/Aik”最小的那个元素，即“20/4=5”。因此，我们将第二行除以5，使得主元素变为1，并将该列的其余元素变为0。更新“Cj-Zj”和“B”，得到以下表格：7010/3CB60300XBx1x4x5b180150120203010x31-2/31/35010/310/3x204/3-5/320-10/3-10/3x301/32/344/326/3x41/31/3-4/152/3-2/15-1/15x50-1/3-2/91/920/9-20/9σj000θL150/3=5010120/4=30从上表可以看出，当前解仍然不是最优解，因为存在“σj”大于0的列。我们选择“σj”最大的那一列，即第一个列，然后找到对应的“θL”，即第一行的“Bi/Aik”最小的那个元素，即“20/1=20”。因此，我们将第一行除以1，使得主元素变为1，并将该列的其余元素变为0。更新“Cj-Zj”和“B”，得到以下表格：7010/3CB7000XBx1x4x5b20050100104020x31-2/31/32010/310/3x204/3-5/310/3-10/3-10/3x301/32/34/34/926/9x41/31/3-4/152/15-2/15-1/15x50-1/3-2/91/92/3-2/3σj0-10/30θL5010100/2=50从上表可以看出，当前解是最优解，因为所有的“σj”均小于等于0。因此，我们得到最优解为“z=200”，此时“x1=40”，“x2=0”，“x3=20”，“x4=0”，“x5=0”。2s.t.3x1+5x2≤5409x1+5x2≤9502x1+6x2≤720x1,x2≥0对偶问题——设y1、y2、y3为A、B、C设备的单位时间内的成本。minz=540y1+950y2+720y3s.t.3y1+9y2+2y3≥705y1+5y2+6y3≥30y1,y2,y3≥0对偶问题的解法：1、列出对偶问题；2、将对偶问题转化为标准形式；3、用单纯形法求解对偶问题，得到对偶问题的最优解；4、根据对偶定理，原问题的最优解等于对偶问题的最优解；5、求出原问题的最优解。对偶问题的标准形式：minz=cTys.t.Ay≥by≥0其中，c、b、y分别表示原问题的系数向量、常数向量和变量向量；A为原问题的约束系数矩阵的转置矩阵。在本例中，对偶问题的标准形式为：minz=540y1+950y2+720y3s.t.3y1+5y2+2y3≥709y1+5y2+6y3≥30y1,y2,y3≥0通过单纯形法求解对偶问题，得到最优解为y1=5,y2=0,y3=10/3，即z*=6050/3。根据对偶定理，原问题的最优解等于对偶问题的最优解，即z*=6050/3。因此，该厂应生产5个甲产品和10/3个乙产品，才能使得总利润最大，最大总利润为6050/3