线性规划的基本的内容和线性规划数学模型
- 格式：docx
- 大小：12.80 KB
- 文档页数：5
线性规划的基本的内容和线性规划数学模型
定义：
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。
数学模型
(1)列出约束条件及目标函数 线性规划步骤
(2)画出约束条件所表示的可行域
(3)在可行域内求目标函数的最优解及最优值
解法求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 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=ζ，即达到最优值。所以，此时可以得到最优解。
