运筹学的线性规划问题.doc

系（部） 专业 班 学号 姓名 密封线运筹学课程论文：线性规划问题（一）摘要线性规划是运筹学的一个基本分支，其应用及其广泛，其作用已为越来越多的人所重视，从线性规划诞生至今的几十年中，随着计算机的逐渐普及，它越来越急速地渗透于工农业生产、商业活动、军事行动和科学研究的各个方面.为了跟上时代的发展和高节奏生活的需要，对于掌握一些有关线性规划的问题可以为我们避免很多不必要的麻烦，也可以提高我们的生产工作效率，下面就探讨一下关于线性规划的一些简单的问题，及其在现实生活中的应用.（二）引言各类经济活动中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程使总的经济效益最好.这样的问题常常可以化成或近似的化成所谓的“线性规划”（Linear Programming ,简记为LP）问题.（三）相关理论与预备知识1、 线性规划的数学模型的一般形式： （1.1）约束条件：目目标函数中为价值系数；称为约束条件中为技术系数，为限额系数；（1.3）也称为变量的非负约束条件. 根据问题的实际背景，首先利用人的智慧，分析约束条件（1.3）中哪些约束应取等式可使目标最优，假设有个约束取等式；其次根据线性规划理论，n个决策变量中至少有个为零的决策变量.n必大于或等于，这样就将变量数降至最少，剩下个一般不为零（特殊情况其中也有可能为零）的决策变量，恰好由个等式约束方程求得其解.这就是线性规划问题的方法的思想和基点.2、 运筹学中的线性规划问题一般采用修正单纯形法和单纯形法求解，也可以采用图解法来求解，下面就探讨应用单纯形法解决线性规划问题的理论，基本计算步骤及具体实施运算的单纯形法.思想：单纯形法考虑的是标准形式的LP问题单纯形法的基本思想就是先找一个基本可行解，判别它是否为最优解，如不是，就找一个更好的基本可行解，再进行判别，如此迭代进行，直至找到最优解，或者判定该问题无界.（四）算法步骤步骤：第一步：找一个初始的可行基 B；第二步：求出对应的典式及检验数向量；第三步：求；第四步：若，停止；已找到最优解及最优值；第五步：若，停止，原问题无界；第六步：求；第七步：以代替得到新的基，转第二步.（五）算例求解线性规划问题解：把模型化为标准形式故初始单纯表为：RHS34-12000111110251120136以、为基变量可得一个基本可行解：此时,因为此时的基本可行解不是最优解又故为入基变量，为离基变量，进行迭代得：RHS10-3-20-2-72001711018,故此时的基本可行解不是最优解又故为入基变量，为离基变量，进行迭代：RHS00-4-2-2-1-8610102-1140101-1111以，为基变量可得一个基本可行解：此时，因为所有的检验数都小于等于0，故此时的基本可行解为最优解.（六）实际运用实例：某工厂在计划期内要安排生产I、II两种产品.已知生产产品所需的设备台时及A、B两种原材料的消耗，如下表所示.该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元.问I、II两种产品的产量各为多少时使该工厂取得最大利润？产品I产品II设备128台时原材料A4016kg原材料B0412kg分析：设，分别表示在计划期内产品I、II的产量.III汇总约束条件目标设备12原材料A40原材料B04产量单位利润23利润max建模：该生产计划问题可用数学模型表示为：目标函数 约束条件 求解：把模型化为标准形式则有初始单纯表为：RHS2300001210084001016000112此时以，为基变量可能一个基本可行解，此时，此时的基本可行解不是最优解；又，故以为离基变量，为入基变量，进行迭代得：RHS2000-3/4-9010-1/22400101601001/43以为，为基变量可得一个基本可行解：；此时，故此时的基本可行解不是最优解；又，故为入基变量，为离基变量，进行迭代得：RHS00-201/4-131010-1/2200-41801001/43以，为基变量可得一个基本可行解：；此时，故此时的基本可行解不是最优解；又，故为离基变量为入基变量进行迭代得：RHS00-3/2-1/80-141001/40400-2 1/214011/2-1/802以，为基变量可得一个基本可行解：；此时，因为所有的检验数都小于等于0，故此时的基本可行解为最优解.;故原问题的最优解为，最优值为.即I产品的产量为4，II产品的产量为2时该工厂取得最大利润，最大利润为14.（七）结束语线性规划最优化问题可以帮我们避开很多不必要的很多麻烦，可以提高我们的生产工作水平，运用最优化问题我们可以改进生产组织或计划，合理安排人力、物力资源，组织生产过程使总的经济效益最好.而单纯形法是求解线性规划问题的通用方法，也是目前为止最为成熟有效的解法.在具有第一可行基的情况下，用单纯形法求解比较简单，只涉及矩阵及初等变换理论；在无第一可行基的情况下，需要引入人工变量，借助辅助变量来求解，大大的增加了计算量，过程非常的繁琐，冗长，而且手算的话非常容易算错，如果用计算机来计算的话也会增加计算机的储存量，因此我们应该在现有的基础上运用我们的智慧去改良，可以设计出一个完美简单可行的解决方案，因此我们需要不断的努力