By Ne0 — Mar 6, 2024

运筹学笔记线性规划与单纯形法

线性规划作为运筹学的一个重要分支，是研究较早、理论较完善、应用最广泛的一个学科。它所研究的问题主要包括两个方面：
1.是在一项任务确定后，如何以最低成本（如人力、物力、资金和时间等）去完成这一任务；
2.是如何在现有资源条件下进行组织和安排，以产生最大收益。

文章目录

线性规划模型的建立

例1 某军工厂生产甲、乙、丙三种产品，生产三种产品需要A、B两种资源，其单位需求量及利润由下表1给出，问每天生产甲、乙、丙三种产品各多少，可使总利润最大？

第一步：假设每天生产甲、乙、丙三种产品各x₁，x₂ ，x₃件可使总利润最大
第二步：建立目标函数
Max z =40x₁+45x₂ +24x₃
第三步：寻找约束条件

例2（营养问题)某部队需要购买A、B二食品，已知食品含有的人体每日必须的营养成份元素1、2、3的多少及每日该三种营养成份每日必需量如下表，试问该部队应如何制定选购食品的计划，使得在满足要求的情况下总的费用最少。

总结线性规划模型建立的步骤：
1.假设决策变量；
2.建立目标函数；
3.寻找约束条件。

线性规划的标准形式

一、线性规划模型的一般形式与规范形式

（1）每一个问题都用一组决策变量（x₁,x₂,…,x_n）表示某一方案，这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的。
（2）存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。
（3）都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示，按问题的不同，要求目标函数实现最大化或最小化。

满足以上3个条件的数学模型称为线性规划的数学模型。
因此，我们将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linear programming)。

二、线性规划的标准形式

特点：目标最大化、约束为等式、决策变量均非负、右端项非负。

线性规划模型的矩阵表示：

三、标准形式的转换

解：步骤
（1）在第一个约束不等式“≤”号的左端加入松弛变量
（2）在第二个约束不等式“≥”号的左端减去剩余变量
（3）把目标函数最小化改成最大化

解：步骤
（1）用x4-x5代替x3
（2）在第一个约束不等式“≤”号的左端加入松弛变量
（3）在第二个约束不等式“≥”号的左端减去剩余变量
（4）把目标函数最小化改成最大化

线性规划图解法

图解法求解线性规划问题的步骤
（1）分别取决策变量x₁，x₂为坐标向量建立直角坐标系。
（2）对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面。
（3）任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(若相交于无穷远处，则称无有限最优解）。若有交点时，此目标函数等值线与可行域的交点即最优解，此目标函数的值即最优值。

线性规划数学模型三要素：
决策变量、目标函数、约束条件

例1：某基地有甲、乙两种飞机和A、B、C 三种类型导弹，已知每种飞机能够携带的导弹数、每种导弹的总数以及各种飞机单次任务毁伤敌方目标的概率如下：

该基地应该如何安排飞机配置导弹，才能最大平均期望数地毁伤敌方目标？

线性规划问题解的概念

举例：

几个解的概念，它们之间的关系可以用下图表示：

线性规划问题的几何意义

如：实心圆，实心球体，实心立方体等都是凸集，圆周不是凸集

定理1: 若线性规划问题存在可行域，则其可行域:

是凸集。
引理：可行解X为基可行解的充分必要条件是X的正分量对应的列向量线性无关。
定理2：线性规划问题的基可行解X对应于可行域D的顶点。
定理3：若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。

几点结论：
线性规划问题的可行域是凸集。
基可行解与可行域的顶点一一对应，可行域有有限多个顶点。
最优解必在顶点上得到。

由上讨论可得以下结论：
1 . 若线性规划的可行域非空，则可行域必定为一凸集。
2 . 若线性规划的可行域非空，则至多有有限个顶点。
3 . 若线性规划有最优解，则至少有一个顶点是最优解（此称为线性规划的基本定理）。

单纯形法的基本原理

单纯形法的基本思想：
若（LP）的可行域D非空，则先取D的一个顶点x作为我们注视的顶点，再把当前的注视顶点x与它的相邻顶点做比较，若有某个相邻顶点x’比当前注视的顶点x的目标函数值还优，就把我们注视的顶点转移到x’.在重复上述步骤，直到注视顶点x的所有相邻顶点都不比x 更优，此时x*就是（LP）的一个最优解。