运筹学总复习一.docVIP

基本要求 一、将线性规划化为标准型和写出相应的对偶规划； 二、用图解法求解具有两个决策变量的线性规划问题； 三、用单纯形方法及人工变量法求解线性规划问题； 四、灵敏度分析； 五、求解产销平衡的运输问题和产销不平衡的运输问题； 六、求解指派问题； 七、求解最短路问题、投资分配问题。 例题选讲 例：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定：产品Ⅰ和Ⅱ在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是12、8、16和12。该工厂每生产一件产品Ⅰ可得利润2圆，每生产一件产品Ⅱ可得利润3圆，问：应如何安排生产，可获得最大利润。 设备 产品 A B C D Ⅰ 2 1 4 2 Ⅱ 3 2 1 4 解 设生产产品Ⅰ和Ⅱ分别为和件，则由条件可得关系 ⑴标准型的概念： ①目标函数为极大化； ②资源常数； ③约束条件关系为等式； ④决策变量。 例： 将下面的线性规划化为标准型 无非负限制 解 二、图解法 例 用图解法求解线性规划问题 极大化 解：最优解 三、单纯形方法 对于具有两个以上决策变量的线性规划问题，我们采用单纯形方法进行求解。具体过程是： ⑴建立单纯形表，在单纯形表中，务必使基变量的价值系数为零，则检验数行是价值系数行的相反数； ⑵若检验数则当前解为最优解（当前解是基变量取相应的资源常数，非基变量取为零）；若存在检验数，则要进行相应的换基，即：迭代； ⑶①进基：进基变量 ： ②出基：出基变量为第行所对应的基变量，由下面的关系确定 ③以主元进行迭代，目标：主元化为1，该列的其余元化为零。 ⑷再一次判定当前解是否为最优解。 例 用单纯形法求解线性规划 极大化 解 引入松弛变量，得到原规划的标准型 极大化 单纯形表为 所以，最优解为最优解值为21. 人工变量法 对于约束条件中没有阶单位阵的线性规划，通过引入适当的人工变量，再加以求解。 1. 大法 在大法中，引入的人工变量的价值系数为，而相应的约束条件系数向量为单位向量。 2.二阶段法 例 用人工变量法求解线性规划。 s.t. 符号不限。 例 求解规划 建立对偶规划的要点 ⑴原规划是极大化，则对偶规划是极小化； ⑵原规划的价值系数是对偶规划中的资源常数； ⑶原规划与对偶规划的约束条件系数矩阵为矩阵的转置关系； ⑷原规划中的第个决策变量无非负限制，则对偶规划中的第个约束条件为等式； ⑸原规划中的第个决策变量非正，则对偶规划中的第个约束条件取反向不等式； 例 求下面问题的对偶规划 极大化 无非负限制。 解 极小化 对偶单纯形法 基本要求：检验数；资源常数存在负值。 解法： 列出对偶单纯形表； 将基变量在目标函数中系数化为零，检验数为新目标函数中系数的相反数； 判断，若，则当前解为最优解； 若中存在负项，则进行迭代，确定出基和进基变量； 出基：记为第r行对应的变量； 进基：，为进基变量； 以为主元进行迭代。目标：将主元化为1，该列的其余元化为0。 灵敏度分析 灵敏度分析的任务：确定各个变量使得最优解保持不变的变化范围；以及在最优解改变的时候求出相应的最优解。 ⑴非基变量的价值系数的变化范围，使最优解保持不变。 ⑵基变量的价值