线性规划(Ⅱncar Pr0gramming,LP)是运筹学的一个重要分支,自1947年丹捷格提出一般线性规划问题求解的单纯形法之后,线性规划在理论上趋于成熟。21世纪初期,一些学者开始使用线性规划求解集束型装备调度问题。FBMH1608HL221-T

   线性规划所研究的问题是:在一定条件下,合理安排人力、物力等资源,使经济效果达到最好。一般地,要解决的是求解线性目标函数在线性约束条件下的最大值或最小值的问题。

   线性规划方法有两种:单纯形法和对偶单纯形法。

   单纯形法

   适合求解的问题:约束条件全部为“≤”,右边常数全部为非负,对目标函数的系数没有要求。例如:

   求解步骤如下。

   第一步:将线性规划问题标准化。

   第二步:判断是否有明显的初始基础可行解,如果有∫转第四步,否则转第三步。

   第三步:构造辅助问题,用两阶段法求解辅助问题。如果辅助问题最优解的目标函数大于0,原问题没有可行解,算法终止,否则转第四步。

   第四步:写出单纯形表,将基变量在约束条件下的系数消为单位矩阵,将基变量在目标函数中的系数消为0,转至第五步。

   第五步:如果所有非基变量的检验数全为负数或0,则已获得最优解,算法终止,否则选择检验数为正数,并且选择绝对值最大的非基变量为进基变量,转第六步。

   第六步:如果进基变量在约束条件中的系数全为负数或0,目标函数无界,算法终止,否则根据右边常数和正的系数的最小比值确定离基变量,转第七步。

   第七步:进基变量列和离基变量行交叉的元素称为主元。对单纯表进行变换,将主元变为1,将主元所有列的其他元素变为0,转第五步。