爱华网线性规划的基本概念
一、线性规划模型
关键在于把实际问题转变为一个生产计划数学模型。
决策变量：模型要决定的未知量
目标函数：决定线性规划优化方向
约束方程：反映客观条件的限制
非负约束：变量取值的限制
例：一家具厂生产桌子和椅子，桌子售价50元、椅子售价30元，生产桌子需要木工4小时，油漆工2小时，生产椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时120小时，油漆工工时50小时。问该厂如何生产才能使每月销售收入最大？
生产计划问题的完整模型：
例：一个成年人每天从食物中获取3000卡热量，55克蛋白质和800毫克的钙。市场上只有4中食品可供选择，如下表问如何选择才能在满足营养需求的前提下是花费最少。
| 序号 | 名称 | 热量 | 蛋白 | 钙 | 价格 |
| 1 | 猪肉 | 1000 | 50 | 400 | 14 |
| 2 | 鸡蛋 | 800 | 60 | 200 | 6 |
| 3 | 大米 | 900 | 20 | 300 | 3 |
| 4 | 白菜 | 200 | 10 | 500 | 2 |
营养配餐问题的完整模型：
线性规划是求一个线性函数在满足一组线性等式或不等式方程条件下极值的数学问题的统称。模型主要由三部分组成：
1、一个反映决策目标的目标函数
2、一组线性等式、不等式约束方程
3、限制决策变量取值范围的非负约束
二、线性规划的一般形式：
…………………
三、线性规划隐含的假定
线性规划要求目标函数和约束方程必须是线性函数隐含了如下假定：
1、比例性假定
目标函数的改变量与决策变量的改变量成比例（在实际中的折扣会使该假定不成立）；
由决策变量变化引起的约束方程左端值的改变量和该变量的改变量成比例；比例性假定
意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常熟。
2、可加性假定
每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决
策变量对目标函数贡献的总和。
3、连续性假定
线性规划问题中的决策变量应取连续值（可取小数）。
4、确定性假定
线性规划中的所有参数都是确定的参数，线性规划问题是确定性的问题，不包含随机因
素。
众所周知，我们的世界是非线性的，对于线性规划的假定几近苛刻。在处理问题时一定要考虑到这些假设，如果不满足假设，应通过进一步的技术来使其变得符合。
四、线性规划的标准型
所有的约束必须是等式约束，所有的变量为非负变量，目标函数求最大化。
将线性规划转化为标准型
1、min f(x) = max{-f(x)}
2、变量取值限制约束的转化：
x为自由变量（可正可负）做变量代换：
3、不等式约束转化为等式约束：
引入松弛变量将"<="约束转化为标准形式：
引入剩余变量将">="约束转换为标准形式：
例：将下式转变为标准形式
矩阵表达形式
max cX
s.t. AX = b;
五、线性规划的图解法
图解法简单、直观，通过线性规划基本原理和几何意义来了解。对于第一个例子中的生产问题
阴影部分就是该问题的可行域
在目标函数即将离开可行域时所接触的最后一个点，就是要求的点。
注：如果目标函数线平行与一个约束线，线性规划问题有无穷多个最优解
线性规划的基本理论
一、线性规划的解
定义：
1、满足线性规划问题所有约束条件的解是该问题的可行解
2、线性规划问题全部可行解的集合构成线性规划问题的可行域
3、使用目标函数达到极值的可行解称为线性规划问题的最优解
表达形式：S = {x| Ax=b, x>=0}
如果S为一空集，线性规划不可行或无可行解；如果S不为空集，该线性规划一定有可行解
但不一定有最优解；如果S为一有界集合，则线性规划一定存在最优解。
二、线性规划的基和基本可行解
1、基的定义：给定线性规划问题P：max {cx| Ax=b, x>=0}
A是m*n的满秩矩阵，n>m，如果B是其中任一个m*m的满秩子矩阵，则称B是P的一个基
2、基变量与非基变量：
假定B由A中前m个列向量构成，约束矩阵可划分为 A=(B,N)
4、基本可行解：满足非负条件的基本解为基本可行解，该解对应的基为可行基。
下图中所标注的所有点都是线性规划的基本解（包括原点），但是只有点b c e g I o是基本可行解
5、退化基本可行解与退化基
一基本可行解中如果存在取零值的基变量，则该解为退化的基本可行解，该解对应的基为退化基
如果基变量都不为零，则基本可行解为非退化的，对应的基为非退化可行基
退化基会引起无效迭代和死循环，需要更深的理论知识来解决，此处只了解即可。
三、线性规划的基本定理
所谓凸组合，就是对应两个点，连接它们的线段称为凸组合。
即对任意的x y都在凸集中，那么由它们两点所构成的凸组合的所有点都在此凸集中
例如：前三个对比后三个
凸集没有凹陷部分，该集合内任取两点连线上的任何点都应该在集合内
定理：x是线性规划问题基本可行解的充要条件是x为可行域S={x| Ax=b,x>0}的极点
即基本可行解是可行域上的极点。
本定理给出了线性规划基本可行解与线性规划可行域极点的等价关系，建立了线性规划基本解代数和集合意义之间的联系。
接下来一个定理给出了极点和最有点之间的关系：
1、若P存在可行解，则必存在基本可行解
2、若P存在最优解，则必存在最优基本可行解
根据以上定理，只需将注意力放在数量有限的基本可行解上，寻找一种计算方法，从一个基本可行解跳到另一个基本可行解并保持目标函数的改善，就可以在有限次的迭代后找到最优基本可行解。
