1、 运筹学的课后习题1.化为标准形式预备知识标准形式为设 0ibmax1.212221210,zccxnstaabnaxaxaxbmmnmini 这类题的做法：1）查看与标准型有哪些不一样的地方，把它们先找出来2）然后再一一化为标准形式即可（min 令；若出现不等式，则引入松弛变量，若 ，加上一个松弛zf 变量，若 ，减去一个松弛变量；若变量 ，则令 带入；若变量 无非负限制，令ix0iixix， 代入）ii,i（1） 引入松弛变量 ，令5656,(,0)xx其 中 33x12 4512 4333 536312 4456max 2026 183, 9, ,0xxxzx xx （2）引入松弛变量
2、，令 ； ，令x2x33xzf12331234512345ma3469,0zxxxx（3）首先查看与标准型中有多少不一样的12341234. 12314241m5,20,in,37fxxstxxxx注 意 无 非 负 限 制分别令 ，有三个不等式所以引入三个松弛变量 （zf 567,x） ，567,0x33x4x12341233456133472 41345672. 1215,0,amxstxxxxxzx2、图解法解题方法：（1）建立直角坐标系：以决策变量 x1 ,x2 为坐标轴。 （2）绘制可行域：对每个约束条件（包括 xi 0） ，先取其为等式，并在坐标系中作出相应的直线，判定不等式所决定
3、的半平面。若各约束半平面交出的区域存在，则其中的点称为线性规划的可行解，所有可行解组成的集合称为可行域或可行集。若不存在，线性规划无可行解。（3）绘制目标函数等值线，并移动求解 做一条目标函数的等值线。 （最好穿过可行域） 查看目标函数，若求 max ，确定函数值增加的方向；若求 min ，确定函数值减少的方向；最后，依据目标函数的要求在可行域内平移等值线（平移到等值线与可行域的最后交点（一个或多个） ）线性规划解的种类：有唯一的最优解；有无穷多个最优解；没有有限的最优解；没有可行解，没有最优解；线性规划的可行域与最优解的关系：（参见 22 页，图 2-5）1.可行域为封闭的有界区域:1有唯一
4、的最优解；2有无穷多个最优解；2.可行域为非封闭的无界区域:1有唯一的最优解；2有无穷多个最优解；3没有有限的最优解；（目标函数随着可行域无限的增大或减少，可以看作目标函数与可行域的最后的交点在无穷远处）3.可行域为空集:没有可行解，没有最优解；线性规划解的性质：1.如何找最优解：1在可行解中，找目标函数值最大的；2 在有限个极点上，找目标函数值最大的；（24 页）3 在基本可行解中，找目标函数值最大的那个。 （线性规划的基本定理：线性规划的基本可行解就是可行域的极点）三.求基（参考例 2.10）1先化为标准形式max213. 461435,2,0zxstxx2 ，任选其中的两列12140A,
5、BP,3P,4B1,5P2,3BP627258930453先判断是否是基？只有基才有基变量和非基变量，才能求出基本解。因为 ， ，所以 为线性规划的基0iB1,20i iB对于 ， 为 的基变量，令非基变量 ，1,Px1 3450x则可得到 基本解，非可行解。(1)/3/0对于 ， 为 的基变量，令非基变量 ，2,B,x1B2x则可得到 基本可行解 ， 为可行基。(2)4/2/ B同理，基本可行解有为基本可行解， 为可行基。(3)402x3B为基本可行解， 为可行基。(5)1/9/05为基本可行解， 为可行基。(6)5x 6为基本可行解， 为可行基。(9)0379B为基本可行解， 为可行基。(
6、1)64x 10基本解 (4)02(7)x(8)414.求出基本可行解的目标函数值，目标函数值最大的那个基本可行解为最优解，其目标函数值为最优值，对应的基为最优基。，(2)6/3Z()8(5)2/3Z(6)1Z(9)3(10)Z所以最优解为 ，最优值为 26/3，最优基()140/x为 。2B四，单纯形法步骤：1 首先找到一个基本可行解（如标准型中有单位矩阵，选择为基，此时得到的基本解一定是基本可行解） ，将基变量和目标用非基变量来表示。2判断是否最优， （目标函数用非基变量表示以后，目标函数中非基变量对应的系数称为检验数） ，若所有的检验数都小于等于零，则此时的基本可行解为最优解，结束计算。
7、否则，不是最优解，转入33 判断进基变量，原则上选择检验数大于零中任何一个都可以，但是为了更快的达到最优解，一般选择大于零中最大的那个对应的非基变量作为进基变量。4.若检验数大于零中，某个检验数对应的变量系数都小于等于零，则线性规划无有限的最优解，计算结束，否则转 55 选择出基变量，当进基变量从零开始增加时，查看那个基变量首先减少为零，选择首先降为零的那个变量为出基变量。6.这样得到了新的基变量、非基变量。将新基变量及目标函数用新的非基变量来表示，再令非基变量为零，可以得到新的基本可行解，然后重复 2-6 过程，直到最终结果算出来为止。例如4（2）法一先化为标准形式（引入松弛变量 ）4x，m
8、ax23.141,0zst34021A1 取可行基为 ， （原则上任找一个基本可行解都可以，但14BP是如果标准型中有单位矩阵，选单位矩阵作为基，那么得到的基本解一定是基本可行解） 。将基变量 及 用非基变量 来14,xZ32,x表示： 231(4)4zxx令非基变量 ，则得到 ， 。320x(0)2,1)x(0)Z2 判断是否是最优解？因为检验数中 ，所以 不是最优解。1(0)x选择进基变量， （原则上选择检验数大于 0 中的任何一个都可以，但为了使得达到最大值更快一些，一般选择检验数中大于零里最大的那个非基变量进基） ， 2max1x进 基3 查看检验数大于零的非基变量所对应的约束系数是否
9、都小于等于零。若是，则该问题无有限的最优解。若不是，选择出基变量。当进基变量开始增加时，选择首先降为 0 的基变量作为出基变量。 112min,30,4x出 基4 将新基变量 及目标函数 用新的非基变量 来表示24,xZ31,x13241304()Zxxx令非基变量 ，则新基本可行解 ，再转 2310x()(1)0,4,4Z因为检验数 ，所以该解为最优解。,法二取基为 ，则建立单纯形表如下：14()BPE单 位 矩 阵0 1 -2 0BCBXb1x2x3x4x1 3 4 0001x41212 0 2 -1 14*6-Z 0 0 1* -2 01/3 1 4/3 0 102x444 -2/3 0
10、 -11/3 1-Z -4 -1/3 0 -10/3 0注意：1/3 1 0 4a102x41a4 -2/3 0 -11/3 1-Z -4 0 02 3判断 取何值时，有最优解，唯一的最优解，有无穷多个最优ia解，没有有限的最优解。课后习题：求最优解：1212312max.4,0zxstx5. 利用大 M 法和两阶段法来求解下列模型 1212min3.,0fxstx1化为标准形式，123124ma.,0zstx101A2引入人工变量 ，5x123451,x，法一 构造新目标函数 125max3zxM-3 -1 0 0 -MBCBXb1x2x34x5-1 1 1 0 0 0-M3x521 1 1 0 -1 121*-Z M M-3 M-1* 0 -M 0
