下载文档原格式
摘要本文研究的是线性规划的可行点算法，一个由线性规划的内点算法衍生而来的算法．线性规划的内点算法是一个在线性规划的可行域内部迭代前进的算法．有各种各样的内点算法，但所有的内点算法都有一个共同点，就是在解的迭代改进过程中，要保持所有迭代点在可行域的内部，不能到达边界．当内点算法中的迭代点到达边界时，现行解至少有一个分量取零值．根据线性规划的灵敏度分析理论，对线性规划问题的现行解的某些分量做轻微的扰动不会改变线性规划问题的最优解．故我们可以用一个很小的正数赋值于现行锯中等于零的分量，继续计算，就可以解出线陛规划问题的最优解．这种对内点算法的迭代点到达边界情况的处理就得到了线性规划的可行点算法．它是一个在可行域的内部迭代前进求得线性规划的最优解的算法．在此算法中，只要迭代点保持为可行点．本文具体以仿射尺度算法和原始一对偶内点算法为研究对象，考虑这两种算法中迭代点到达边界的情况，得到相对应的’仿射尺度可行点算法’和’原始．对偶可行点算法，．在用理论证明线性规划的可行点算法的可行性的同时，我们还用数值实验验正了可行点算法在实际计算中的可行性和计算效果．关键词：线性规划，仿射尺度算法，原始一对偶内点算法，内点，可行点算法，步长可行点．ＡｂｓｔｒａｃｔｄｅｒｉｖｅｄＴｈｉｓＤａｐｅｒｆｏｃｕｓｅｓｏｎａｆｅａｓｉｂｌｅｐｏｉｎｔａｌｇｏｒｉｔｈｍｆｏｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ，ａｎａｌｇｏｒｉｔｈｍｆｒｏｍｔｈｅｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｆｏｒｌｉｎｅｚａ＂ｐｒｏｇｒａｍｍｉｎｇ．ＴｈｅｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｆｉｎｄｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｂｙｓｅａｒｃｈｉｎｇｗｉｔｈｉｎｔｈｅｆｅａｓｍｌｅＴｅ譬ｉｏｎｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ．ＴｈｅｒｅａｒｅａＵｋｉｎｄｓｏｆｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｌｒｍａｌｌｔｈｅｆｏｒｌｉｎｅａｒｐｒｏｇｒａｍｎｆｉｎｇ．Ｂｕｔａｌｌｔｈｅｓｅｉｎｔｅｒｉｏｒｐｏｉｎｔａｌｇｏｒｉｔｈｍｓｓｈａｒｅａｓｐｅｃｉａｌｉｔｙ，ｗｈｉｃｈｉｓｓｏｌｕｔｉｏｎ｜ｔｅｒａｔｉｖｅＤｏｉｎｔｓｃａｎｎｏｔｒｅａｃｈｔｈｅｂｏｕｎｄｓＡｃｃｏｒｄｉｎｇｔｏｔｈｅｓｅｎｓｉｔｉｖｉｔｙｔｈｅｏｒｙ，ｔｈｅｏｐｔｉｍａｌｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｗｉｌｌｎｏｔｂｅｃｈａｎｇｅｄｂｙｌｉｔｔｌｅｄｉｓｔｕｒｂａｎｃｅｓｏｆｔｈｅｐｒｅｓｅｎｔｓｏｌｕｔｉｏｎ·ＳｏＷｅｌｅｔｔｈｅ｛ｘｊＩｚＪ＝ｏ，Ｊ＝１，２，－··）ｎ）ｅｑｕａｌａｖｅｒｙｓｍａｌｌｐｏｓｉｔｉｖｅｎｕｎｌｂｅｒ，ｇｏｏｎｗｉｔｈｔｈｅｃｏｍｐｕｔａｔｉｏ“一ａｎｄｔｈｅｎｗｅｇｅｔｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｏｆｔｈｅｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ．Ａｌｌｔｈｅｓｅｌｅａｄｔｏｔｈｅｄｅｖｅｌｏｐｍｅｎｔ。
线性规划算法在运筹学中的应用1.引言：运筹学是一门以数学为基础，以各种现代科学技术和方法为工具的综合学科。
线性规划算法是运筹学中最基础的算法之一，它被广泛应用于生产、交通、金融、工程、电信等众多领域。
本文旨在介绍线性规划算法在运筹学中的应用，分析其优缺点以及未来的发展趋势。
2.线性规划算法的基本概念：2.1线性规划的定义：线性规划是一种优化问题，目标函数为线性函数，约束条件也为若干个线性不等式或等式，被优化的解为线性约束下的最优解。
2.2线性规划的形式化表示：设x = (x1，x2 ，…，xn）为决策变量，分别表示问题的n个方面，c = (c1，c2，…，cn) 为线性目标函数系数向量，a ij是线性方程组的系数矩阵，b = (b1，b2，…，bm)T是约束条件的值向量，则线性规划可表示为：maxCxs.t. A x≤b, xi≥0 (i = 1,2,…,n)实际上，线性规划的问题发生在许多领域，如工程、金融、物流和电信等领域，这些领域都可以用线性规划来解决问题。
3.线性规划算法的应用：线性规划算法在运筹学领域应用广泛，它可以用于计算许多实际问题的最优解。
下面分别为工程、金融、物流和电信四个领域分别阐述其应用。
3.1工程领域：线性规划算法可以帮助工程师设计和规划工程系统。
例如，建筑师可以通过线性规划算法设计出最优的建筑结构，使得建筑物的稳定性和安全性更高，同时可以减少建筑材料的浪费。
3.2金融领域：线性规划算法可以用于风险管理和投资决策。
在金融领域，投资者可以使用线性规划算法来优化他们的投资组合，以实现最大的回报并降低风险。
3.3物流领域：线性规划算法可以帮助调度员优化物流系统的运输成本和增加工作效率。
通过线性规划算法，可以确定最佳的运输路线和时机，以及最佳的物流方案和仓储选址。
3.4电信领域：线性规划算法也可以应用在电信领域。
例如，在通信网络规划过程中，线性规划算法可以帮助网络规划师优化网络拓扑结构，选择最佳的节点位置和路由，以实现最大的网络效率和覆盖范围。
运筹学第一部分规划论学习总结一、线性规划（LP）1.1线性规划的基本概念线性规划；目标函数，约束条件；可行解，可行域；最优解，最优值；1.2 用图解法解两个变量的LP知识要点：1）图解法解LP的目的是理解LP的几何性质，不是为了求解，因为它只适用于简单的LP。
2）图解法最适合两个决策变量的LP（约束可以是等式或不等式）。
对于一个变量的LP，图形在一维直线上，过分简单；对于三个变量的LP，图形在三维空间，过于复杂。
3）图解法的基本步骤：（1）依次画出适合各约束的区域。
重点是会画直线方程的图像。
对不等式约束，再判断是直线划分的哪一个半平面。
（2）找出适应各个约束的公共区域，即LP的可行域。
（3）对于目标函数，画出几条等值线，并判断等值线的值上升的方向。
（4）平移目标函数等值线，找出使目标函数最优的点，即LP的最优解。
若找不到最优点，为无界解。
重点或难点：画对应直线方程的直线，注意斜率的符号。
1.3线性规划的图解法的灵敏性分析，对偶价格（影子价格）。
1.4有关LP的基本定理：线性规划问题的可行域非空时（除无可行解时），其可行域是凸集。
（它是有界或无界的凸多边形）如果线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解；（一定可以在其顶点达到，但不一定只在其顶点达到，有时在两顶点的连线上得到，包括顶点）1.5 可行域与最优解及相互之间的关系：可行域：空集非空（有界、无界）最优解：无解唯一最优解无穷多最优解无界解1.6线性规划的标准化1）松弛量：对一个“≤” 约束条件中，没有使用完的资源或能力的大小称为松弛量（松弛或空闲能力）；加上一个松弛量2）约束方程左边为“≥”不等式时，则可在左边减去一个非负剩余变量，变成等式约束条件。
3)右边的常量Bj ≤0时，两边都要乘以-1。
4)当变量XK <0时，可令XK= - XK, , XK, >05)当变量XK为无约束时，可令XK= XK,- XK,,，其中，XK, , XK,, ≥0。
