运筹学的课后习题.doc

运筹学的课后习题1.化为标准形式预备知识标准形式为设这类题的做法：1）查看与标准型有哪些不一样的地方，把它们先找出来 2）然后再一一化为标准形式即可（min 令；若出现不等式，则引入松弛变量，若，加上一个松弛变量，若，减去一个松弛变量；若变量，则令带入；若变量无非负限制，令，代入）（1） 引入松弛变量，令（2）引入松弛变量，令；，令（3）首先查看与标准型中有多少不一样的 分别令，有三个不等式所以引入三个松弛变量（），2、图解法解题方法：（1）建立直角坐标系：以决策变量x1 ,x2 为坐标轴。 （2）绘制可行域： 对每个约束条件（包括xi 0），先取其为等式，并在坐标系中作出相应的直线，判定不等式所决定的半平面。若各约束半平面交出的区域存在，则其中的点称为线性规划的可行解，所有可行解组成的集合称为可行域或可行集。 若不存在，线性规划无可行解。（3）绘制目标函数等值线，并移动求解 做一条目标函数的等值线。（最好穿过可行域） 查看目标函数，若求max ，确定函数值增加的方向；若求min ，确定函数值减少的方向；最后，依据目标函数的要求在可行域内平移等值线（平移到等值线与可行域的最后交点（一个或多个）线性规划解的种类：有唯一的最优解；有无穷多个最优解；没有有限的最优解；没有可行解，没有最优解；线性规划的可行域与最优解的关系：（参见22页，图2-5）1.可行域为封闭的有界区域:1有唯一的最优解；2有无穷多个最优解；2.可行域为非封闭的无界区域:1有唯一的最优解；2有无穷多个最优解；3没有有限的最优解；（目标函数随着可行域无限的增大或减少，可以看作目标函数与可行域的最后的交点在无穷远处）3.可行域为空集:没有可行解，没有最优解；线性规划解的性质：1.如何找最优解：1在可行解中，找目标函数值最大的；2 在有限个极点上，找目标函数值最大的；（24页）3 在基本可行解中，找目标函数值最大的那个。（线性规划的基本定理：线性规划的基本可行解就是可行域的极点）三.求基（参考例2.10）1先化为标准形式2，任选其中的两列3先判断是否是基？只有基才有基变量和非基变量，才能求出基本解。 因为，所以为线性规划的基对于，为的基变量，令非基变量，则可得到 基本解，非可行解。对于，为的基变量，令非基变量，则可得到 基本可行解 ， 为可行基。同理，基本可行解有为基本可行解，为可行基。为基本可行解，为可行基。为基本可行解，为可行基。为基本可行解，为可行基。为基本可行解，为可行基。基本解4.求出基本可行解的目标函数值，目标函数值最大的那个基本可行解为最优解，其目标函数值为最优值，对应的基为最优基。，所以最优解为，最优值为26/3，最优基为。四，单纯形法步骤：1首先找到一个基本可行解（如标准型中有单位矩阵，选择为基，此时得到的基本解一定是基本可行解），将基变量和目标用非基变量来表示。2判断是否最优，（目标函数用非基变量表示以后，目标函数中非基变量对应的系数称为检验数），若所有的检验数都小于等于零，则此时的基本可行解为最优解，结束计算。否则，不是最优解，转入33 判断进基变量，原则上选择检验数大于零中任何一个都可以，但是为了更快的达到最优解，一般选择大于零中最大的那个对应的非基变量作为进基变量。4.若检验数大于零中，某个检验数对应的变量系数都小于等于零，则线性规划无有限的最优解，计算结束，否则转55 选择出基变量，当进基变量从零开始增加时，查看那个基变量首先减少为零，选择首先降为零的那个变量为出基变量。6.这样得到了新的基变量、非基变量。将新基变量及目标函数用新的非基变量来表示，再令非基变量为零，可以得到新的基本可行解，然后重复2-6过程，直到最终结果算出来为止。例如4（2）法一先化为标准形式（引入松弛变量），1 取可行基为，（原则上任找一个基本可行解都可以，但是如果标准型中有单位矩阵，选单位矩阵作为基，那么得到的基本解一定是基本可行解）。将基变量及用非基变量来表示：令非基变量，则得到，。2 判断是否是最优解？因为检验数中，所以不是最优解。选择进基变量，（原则上选择检验数大于0中的任何一个都可以，但为了使得达到最大值更快一些，一般选择检验数中大于零里最大的那个非基变量进基），3 查看检验数大于零的非基变量所对应的约束系数是否都小于等于零。若是，则该问题无有限的最优解。若不是，选择出基变量。当进基变量开始增加时，选择首先降为0的基变量作为出基变量。4 将新基变量及目标函数用新的非基变量来表示令非基变量，则新基本可行解，再转2因为检验数，所以该解为最优解。法二取基为，则建立单纯形表如下：0 1 -2 0 0012121 3 4 04*60 2 -1 1-Z00 1* -2 010441/3 1 4/3 0 -2/3 0 -11/3 1-Z-4-1/3 0 -10/3 0注意：1041/3 1 0 -2/3 0 -11/3 1-Z-4 0 0判断取何值时，有最优解，唯一的最优解，有无穷多个最优解，没有有限的最优解。课后习题：求最优解：5. 利用大M法和两阶段法来求解下列模型1化为标准形式，2引入人工变量，法一 构造新目标函数-3 -1 0 0 -M 0-M21-1 1 1 0 0 21*1 1 0 -1 1-ZMM-3 M-1* 0 -M 00111-2 0 1 1 -11 1 0 -1 1-Z1-2 0 0 -1 1-M所以，此问题的最优解为，最优值为-1，因为，所以为原问题的最优解，原问题的最优值为1。法二 构造新目标函数0 0 0 0 -1 0-121-1 1 1 0 0 -1*1 1 0 -1 1-Z11* 1 0 -1 000310 2 1 -1 11 1 0 -1 1-Z00 0 0 0 -1所以此时最优解为，因为因为，所以为原问题的基本可行解。-3 -1 0 0 0-3310 2 1 -1 3/21*1 1 0 -1 -Z30 2* 0 -3 0-111-2 0 1 1 1 1 0 -1 -Z1-2 0 0 -1 所以为原问题的最优解，最优值为1。第二章，课后习题选解一、如何来求对偶规划1.化为这种对称形式可相互转化模式为 可相互转化 2、原问题（对偶）对偶问题（原问题）目标 max z变 n个 量 目标 min f约 n个束条件约束右端目标系数目标系数约束右端约 m个束 条 件 变 m个 量 做这类题时，可以直接用上面的表格（这种容易出错）；一般是将原问题为max（min）,首先化为，然后利用上面的表格得到对偶问题；1.2.(P) 3.Max值形式，先化为 p (D) 4.因为min,所以先将约束条件尽量化为 2.判断原问题是否有最优解，此类问题的知识点:考察推论2：1.（0,0,0）为原问题的可行解，其对偶问题为：，显然对偶问题没有可行解，所以原问题没有有限的最优解。2.（2,2,0）为原问题的可行解，其对偶问题为，显然（1，3）为对偶问题的可行解，所以原问题有最优解。3.准形式：4.应用对偶性质，直接写出原问题的最优值这里主要考察：对偶问题：，显然，所以对偶问题的最优解为，则对偶问题的最优值为，所以由定理3.2，原问题的最优值为。5.对偶单纯形法：1.首先化为标准形式：建立对偶单纯形表： -5 -2 -4 0 0 0-4-3 -1 -2 1 00-10-6 -3 -5 0 10-5 -2 -4 0 0 0-2/3-1 0 -1/3 1 -1/3-210/32 1 5/3 0 -1/3-Z20/3-1 0 -2/3 0 -2/3进基-52/31 0 1/3 -1 1/3-220 1 1 2 1/322/30 0 -1/3 -1 -1/3所以标准型的最优解为，最优值为-22/3原问题的最优解为，最优值为22/32. 先化为标准形式：-1-2-30000-4*-21-1100081120100201-1001-z0-1-2-3000出基进基-1-2-3000-121-1/21/2-1/2000601/25/2-1/2100201-1001-z20-5/2-5/2-1/200所以标准型的最优解为，最优值为-2原问题的最优解为，最优值为2 用对偶单纯形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 0解：max z = -2x1 - 3x2 - 4x3 + 0x4 + 0x5 - x1 - 2x2 - x3 + x4 = -1 -2x1 + x2 - 3x3 + x5 = -4 x1,x2,x3,x4,x5 0-2-3-400CBXBbx1x2x3x4X50x4-1-1-2-1100x5-4*-21-301-z0-2-3-400进基0x410-5/21/21-1/2-2x121-1/23/20-1/2-z40-4-10-1所以标准型的最优解为，最优值为-4原问题的最优解为，最优值为46.初始单纯形表：23000001222100008120100016400010012040001-z0230000最优单纯形表23000000001-1-1/402410001/4004000-21/21320101/2-1/80-z-14000-3/2-1/80怎样找初始基矩阵？只要在最优单纯形表中将基变量按顺序找到（），然后按顺序在初始单纯形表中将这些变量对应的系数向量写下来即可。怎样找其逆矩阵？只要在初始单纯形表中找到单位矩阵所在的变量（也要注意顺序）（），然后按顺序在最优单纯形表中将这些变量对应的系数向量写下来即可。， 设，1）为基变量的目标系数，则变化会改变非基变量的检验数，不会影响基变量的检验数。保持最优解不变的条件：。为基变量的目标系数，则变化会改变非基变量的检验数，不会影响基变量的检验数。保持最优解不变的条件：。，则2) 设，则则，5)增加一个约束条件：，对最优解产生的影响，加入到原最优单纯形表中，得到230000000001-1-1/4002410001/40004000-21/210320101/2-1/8000 1222.400001-z-14000-3/2-1/80230000000001-1-1/4002410001/400