本篇文章给大家谈谈线性规划法，以及线性规划法怎么算对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、什么是线性规划法
• 2、线性规划法的特点是什么？
• 3、线性规划的解法

什么是线性规划法

线性规划法是解决多变量最优决策的方法,是在各种相互关联的多变量约束条件下,解决或规划一个对象的线性目标函数最优的问题,即给与一定数量的人力、物力和资源,如何应用而能得到最大经济效益.其中目标函数是决策者要求达到目标的数学表达式,用一个极大或极小值表示.约束条件是指实现目标的能力资源和内部条件的限制因素,用一组等式或不等式来表示.

线性规划是决策系统的静态最优化数学规划方法之一.它作为经营管理决策中的数学手段,在现代决策中的应用是非常广泛的,它可以用来解决科学研究、工程设计、生产安排、军事指挥、经济规划；经营管理等各方面提出的大量问题.

线性规划法一般采取三个步骤：

第一步,建立目标函数.

第二步,加上约束条件.在建立目标函数的基础上,附加下列约束条件

第三步,求解各种待定参数的具体数值.在目标最大的前提下,根据各种待定参数的约束条件的具体限制便可找出一组最佳的组合.

线性规划法的特点是什么？

此法的特点是：（1）目标只有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=ζ，即达到最优值。所以，此时可以得到最优解。

若σ = 0不成立

可以采用单纯形表变换。

σ中存在分量0。这些负分量对应的决策变量编号中，最小的为j。N中与j对应的列向量为Pj。

若Pj =0不成立

则Pj至少存在一个分量ai，j为正。在规划问题4的约束条件（1）的两边乘以矩阵T。

T=

则变换后，决策变量xj成为基变量，替换掉原来的那个基变量。为使得T b = 0，且T Pj=ei（其中，ei表示第i个单位向量），需要：

l ai，j0。

l βq+βi*(-aq,j/ai,j)=0，其中q!=i。即βq=βi/ ai,j * aq,j。

n 若aq,j=0，上式一定成立。

n 若aq,j0，则需要βq / aq,j =βi/ ai,j。因此，要选择i使得βi/ ai,j最小。

如果这种方法确定了多个下标，选择下标最小的一个。

转换后得到规划问题4的形式，继续对σ进行判断。由于基解是有限个，因此，一定可以在有限步跳出该循环。

若对于每一个i，ai,j=0

最优值无解。

若不能寻找到初始基解

无解。

若A不是行满秩

化简直到A行满秩，转到若A行满秩。