线性规划
线性规划问题包含线性目标函数、线性约束条件、线性规划问题、可行解、可行域、最优解。满足约束条件的解 X = {x1,x2...xn} 为线性规划问题的可行解,所有可行解构成的集合称为问题的可行域,记为R,使得目标函数达到最小值的可行解称为最优解。非标准的线性规划问题可以转换为标准的线性规划问题。基于“若线性规划问题有有限最优解,则一定有某个最优解是可行域的一个极点”,1947年,G.B. Dantzig提出了单纯形法:先找出可行域的一个极点,根据一定规则判断其是否最优,否则转换到与之相邻的另一个极点,并使目标函数值更优,依次做下去,直到找到某一个最优解。
非标准性转换为标准型:
名词举例介绍:
解决线性规划问题的基本步骤:
例题:
注:
有些实际问题可能会有一个约束条件:决策变量只能取整数,如x1、x2取整数。这类问题实际上是整数线性规划问题。如果把它当成一个线性规划来解,求得其最优解刚好是整数时,故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数,将其取整后不一定是相应整数规划的最优解,这样的整数规划应用专门的方法求解(如割平面法、分支定界法)。