摘要：本文主要研究线性规划问题解的退化情形。回顾了线性规划问题的研究现状，介绍了线性规划中退化现象的含义，讨论了退化情形在原问题和对偶问题中的情形，每种情形都配以相关的例题分析。最后介绍了两种特殊退化情形的处理方法。94610

毕业论文关键词：线性规划，退化问题，退化解

Abstract：In this paper, we study the degradation of linear programming solution。 We retrospect the status of researching linear programming problem。 Then we explain the meaning of degradation phenomenon in linear programming。 And we discuss the degradation situation in the original problem and the dual problem of classification by using the relevant examples and  detailed analysis。 Finally, we introduce two kinds of special degradation situation。

Keywords：Linear programming, the degradation phenomenon,Degenerate solution

目   录

1 前言 4

2 线性规划中退化解的含义 4

3 退化的基可行解的产生原因分析 5

3。1 右端常数项含有零分量 5

3。2 迭代过程出现相同 值 6

4 退化解的情形分类 7

4。1 唯一最优解的情形 7

4。2 无穷多最优解的情形 8

5 对偶问题中的退化情形 9

6 特殊情形的退化现象的处理 10

6。1 两阶段法的解的退化情形 10

6。2 用匈牙利法进行求解分配问题 12

结论 15

参考文献 16

致谢 17

1。前言

本文主要研究线性规划的解的退化问题。对于线性规划问题的研究一直在持续当中，除了线性规划这个问题的现象之外，各路研究者们更热衷于研究如何解决线性规划问题，即研究解决线性规划问题的方法。这也是解决线性规划问题方法一直在进步的原因，从单纯形法、对偶单纯形法，到椭圆法、内点法，解决线性规划问题的方法一直在不断的补充、发展和完善。在这些方法中，最主要的其实还是单纯形法。但是在退化的线性规划问题中，单纯形法就有了局限性，因为在迭代的过程中会出现循环。为了解决这个问题，各路研究者们研究出了各种方法，包括摄动法、字典序法、Bland法则，这些方法都能有效地避免迭代循环的出现。本文研究的方向主要是讨论线性规划中出现的几种退化现象，并对它们进行了一定的分类，并且列举了这些现象对应的现实问题，以及如何解决这些现实问题，研究的结果对于很多经济决策者都具有重要的指导意义。本论文前面从原问题和对偶问题的角度来研究几种退化情形，后面加上两种特殊情形的退化现象的处理，包括用两阶段法进行求解的情形，以及用匈牙利法对高度退化的分配问题进行求解的情形。

2。 线性规划中退化解的含义

退化解的含义奠定在基变量的含义之上。

线性规划的原问题与对偶问题之间存在互为对偶的关系，也就是说，线性规划的对偶问题的对偶即是原问题。假设原问题为

那么，其对偶问题就为