爱华网线性规划（Linear programming，简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。决策变量、约束条件、目标函数是线性规划的三要素。
线性规划_线性规划 -简介
可解的问题会有一个简单多边形的可行域
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。
线性规划_线性规划 -标准型
描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分：
一个需要极大化的线性函数:
线性规划
以下形式的问题约束：
线性规划
和非负变量：
其他类型的问题，例如极小化问题，不同形式的约束问题，和有负变量的问题，都可以改写成其等价问题的标准型。
线性规划_线性规划 -模型建立
从实际问题中建立数学模型一般有以下三个步骤；
1.根据影响所要达到目的的因素找到决策变量；
2.由决策变量和所在达到目的之间的函数关系确定目标函数；
线性规划难题解法
3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。
所建立的数学模型具有以下特点：
1、每个模型都有若干个决策变量（x1，x2，x3……，xn），其中n为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。
2、目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。
3、约束条件也是决策变量的线性函数。
当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。
例：
生产安排模型：某工厂要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示，表中右边一列是每日设备能力及原材料供应的限量，该工厂生产一单位产品Ⅰ可获利2元，生产一单位产品Ⅱ可获利3元，问应如何安排生产，使其获利最多？
解：
1、确定决策变量：设x1、x2分别为产品Ⅰ、Ⅱ的生产数量；
2、明确目标函数：获利最大，即求2x1+3x2最大值；
3、所满足的约束条件：
设备限制：x1+2x2≤8
原材料A限制：4x1≤16
原材料B限制：4x2≤12
基本要求：x1，x2≥0
用max代替最大值，s.t.（subject to 的简写）代替约束条件，则该模型可记为：
max z=2x1+3x2
s.t. x1+2x2≤8
4x1≤16
4x2≤12
x1，x2≥0
线性规划_线性规划 -解法
求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。
图解法解线性规划问题
对于一般线性规划问题： Min z=CX
S.T.
AX =b
X>=0
其中A为一个m*n矩阵。
若A行满秩
则可以找到基矩阵B，并寻找初始基解。
用N表示对应于B的非基矩阵。则规划问题1可化为：
规划问题2：
Min z=CB XB+CNXN
线性规划法解题
S.T. B XB+N XN = b （1）
XB>= 0， XN>= 0 （2）
（1）两边同乘于B-1，得
XB + B-1 N XN = B-1 b
同时，由上式得XB = B-1 b - B-1 N XN，也代入目标函数，问题可以继续化为：
规划问题3：
Min z=CB B-1 b + （ CN - CB B-1 N ） XN
S.T.
XB+B-1N XN = B-1 b （1）
XB>= 0， XN>= 0 （2）
令N：=B-1N，b：= B-1 b，ζ= CB B-1b，σ= CN - CB B-1 N，则上述问题化为规划问题形式4：
Min z= ζ + σ XN
S.T.
XB+ N XN = b （1）
XB>= 0， XN>= 0 （2）
在上述变换中，若能找到规划问题形式4，使得b>=0，称该形式为初始基解形式。
上述的变换相当于对整个扩展矩阵（包含C及A） 乘以增广矩阵 。所以重在选择B，从而找出对应的CB。
若存在初始基解
若σ>= 0
则z>=ζ。同时，令XN = 0，XB = b，这是一个可行解，且此时z=ζ，即达到最优值。所以，此时可以得到最优解。
若σ>= 0不成立
可以采用单纯形表变换。
σ中存在分量
若Pj
则Pj至少存在一个分量ai，j为正。在规划问题4的约束条件（1）的两边乘以矩阵T。
T=
则变换后，决策变量xj成为基变量，替换掉原来的那个基变量。为使得T b>= 0，且T Pj=ei（其中，ei表示第i个单位向量），需要：
l ai，j>0。
l βq+βi*（-aq，j/ai，j）>=0，其中q!=i。即βq>=βi/ ai，j * aq，j。
n 若aq，j
n 若aq，j>0，则需要βq / aq，j>=βi/ ai，j。因此，要选择i使得βi/ ai，j最小。
如果这种方法确定了多个下标，选择下标最小的一个。
转换后得到规划问题4的形式，继续对σ进行判断。由于基解是有限个，因此，一定可以在有限步跳出该循环。
若对于每一个i，ai，j
最优值无界。
若不能寻找到初始基解
无解。
若A不是行满秩
化简直到A行满秩，转到若A行满秩。
线性规划_线性规划 -发展
可解的问题会有一个简单多边形的可行域
法国数学家J.- B.- J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提
出线性规划的想法，但未引起注意。
1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。
1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。
1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。
1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。
50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。
线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。
1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。
1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。 建立线性规划模型的方法
线性规划_线性规划 -高校教材
・出版社：武汉大学出版社
・页码：370 页
・出版日期：2008年06月
・ISBN：7307041014/9787307041011
・条形码：9787307041011
・版本：第2版
・装帧：平装
・开本：16
・正文语种：中文
・丛书名：高等学校数学系列教材
线性规划
内容简介
线性规划是运筹学的重要分支，它是一门实用性很强的应用数学学科。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有限资源制订最佳决策的有力工具。《线性规划》系统地介绍了线性规划知识，包括单纯形方法、对偶原理与对偶算法、灵敏度分析、分解算法、内点算法，以及整数线性规划等。《线性规划》适于用做高等院校、师范院校有关专业的线性规划课教材。
目录
前言
第一章 线性规划问题
1.1 线性规划问题的实例
1.2 线性规划问题的数学模型
1.3 二变量线性规划问题的图解法
本章小结
复习题
第二章 单纯形方法
2.1 基可行解
2.2 最优基可行解的求法
2.3 单纯形法的计算步骤、单纯形表
2.4 退化情形的处理
2.5 初始基可行解的求法
2.6 单纯形法的几何意义
2.7 改进单纯形法
本章小结
复习题
第三章 对偶原理与对偶算法
3.1 对偶线性规划问题
3.2 对偶定理
3.3 对偶单纯形法
3.4 初始正则解的求法
3.5 原-对偶单纯形法
本章小结
复习题
第四章 运输问题
4.1 运输问题的特性
4.2 初始方案的求法
4.3 检验数的求法
4.4 方案的调整
4.5 不平衡的运输问题
4.6 分派问题
本章小结
复习题
第五章 有界变量线性规划问题
5.1 基解的特征
5.2 有界变量单纯形法
5.3 有界变量对偶单纯形法
本章小结
复习题
第六章 灵敏度分析与参数线性规划问题
6.1 灵敏度分析
6.2 参数线性规划问题
本章小结
复习题
第七章 整数线性规划
7.1 几个典型的整数线性规划问题
7.2 割平面法
7.3 分枝定界法
7.4 隐枚举法
7.5 建立整数规划模型的一些技巧
本章小结
复习题
第八章 分解算法
8.1 可行解的分解表达式
8.2 二分算法
8.3 p分算法
本章小结
复习题
第九章 内点算法
9.1 原仿射尺度法
9.2 对偶仿射尺度法
9.3 对数障碍函数法
本章小结
复习题
习题答案
索 引
编者语
线性规划_线性规划 -序言
本教材主要为管理学、经济学等专业本科生而编写，也可以作为其他专业的学习参考书.在本书的编写过程中，主要体现了如下几个特点：
1.线性规划已经具有成熟的理论与方法，本书既力争在内容形式上保持理论体系的完整性，也尝试使用几何直观来解释其概念与方法，努力做到推导严谨、通俗易懂。
2.内容由浅入深、理论结合实际。比如通过实例讨论，引入逐步逼近最优解的迭代思想与方法，并由此导出单纯性方法原理；在单纯性方法的基础上，给出了不同的优化求解方法，并分析了各种方法之间的联系与差别。
3.突出课程特点，注重实际应用。例题、习题选取新颖，紧密结合经济与管理专业的实际需要，为学生学以致用、理论联系实际，培养学生解决实际问题的能力奠定基础。对于手工计算求解的题目，则重点突出方法训练，而尽量避免复杂运算或大量重复运算的现象。
4.本书安排了必修内容和选修内容，可满足40学时或48学时的教学要求。每章内容之后配有适量练习题，并在全书后面安排了总练习题。既满足基本概念、基本方法的训练，也为学生全面复习提供了基本素材。
本书在编写中受到了教研室同仁的大力支持，浙江大学出版社为本书的顺利出版付出了大量劳动，在此表示衷心感谢！
由于水平有限，书中可能存在一定的错误或不足之处，敬请读者或同行批评指正。
线性规划_线性规划 -作者简介
唐晓文，福建工程学院数理系教授。主要研究方向为矩阵理论。主持“高等代数”福建省省级精品课程。参与“车辆橡胶配件动态性能测试设备的研发”等福建省科技厅项目，主持“广义严格对角占优矩阵与非奇M-矩阵的判定及应用的研究”、“几类特殊矩阵的判定及其应用研究”等项目。主编《线性代数》等教材多部。撰写、发表的论文有Stable，Analysis of a Pedalor-prev，SIRS Model with Saturation Infectious Force、《数学教学观的转变与发展创新》、 《相互竞争的两种群中具有饱和传染率的sIRs模型的稳定性分析》等多篇。刘海英，福建广播电视大学电子信息与计算机系副教授。主要研究方向为计算数学。参加工作以来发表论文十余篇，主要有《基于多传感器信息融合技术》、《信息融合在空间点目标识别中的应用》、《基于信息融合理论的空间点目标识别实验结果分析》、《最短路径问题在管理中的应用》等。主持课题“BP神经网络算法研究”、“基于Dijkstra算法的最短路径改进算法”、“利用Excel软件优化企业资源配置”、“线性规划方法的应用”等十余项。
