该线性规划是一种数学方法被用于优化（最大化或最小化适当的）的函数，其变量被限制，如只要函数和约束是线性相关的变量。
通常，要优化的功能可以模拟实际情况，例如制造商的利润，其制造商的投入，劳动力或机械受到限制。
图1.线性编程被广泛用于优化利润。资料来源：Piqsels。
最简单的情况之一是要最大化的线性函数，它仅取决于两个称为决策变量的变量。它可以是以下形式：
Z = k 1 x + k 2 y
k 1和k 2恒定。此功能称为目标功能。当然，有些情况需要研究两个以上的变量，而且更为复杂：
Z = k 1 x 1 + k 2 x 2 + k 3 x 3 +…。
约束条件还可以通过方程式或不等式在数学上建模，这些方程式或不等式在x和y中均等线性。
该系统中的解决方案集称为可行解或可行点。在可行点中，至少有一个可以优化目标函数。
第二次世界大战后不久，线性编程由美国物理学家和数学家乔治·丹茨格（George Dantzig，1914-2005年）和俄罗斯数学家和经济学家列昂尼德·坎托罗维奇（Leonid Kantorovich，1912-1986年）独立开发。
解决问题的方法称为单纯形方法，是Dantzig的创意，他曾在美国空军，伯克利大学和斯坦福大学工作。
图2.数学家George Dantzig（左）和Leonid Kantorovich（右）。资料来源：F. Zapata。
线性规划模型
建立适用于实际情况的线性规划模型所需的要素是：
目标功能
-决策变量
-限制
在目标函数中，定义要实现的目标。例如，假设您想使某些产品的制造利润最大化。然后，根据产品的销售价格，建立“利润”功能。
用数学术语来说，该函数可以用求和符号缩写表示：
Z = ∑k i x i
在这个等式中，k i是系数，x i是决策变量。
决策变量是拥有控制权的系统元素，其值是正实数。在建议的示例中，决策变量是要获得最大利润的每种产品的数量。
最后，我们具有约束条件，这些约束条件是线性方程或决策变量方面的不等式。他们描述了该问题的局限性，这些局限性是已知的，例如可以是制造中可用的原材料数量。
限制类型
您可以有M个限制，从j = 1到j =M。从数学上讲，限制分为三种类型：
- A j = ∑ a ij。X 我
- 乙Ĵ ≥Σb IJ。X 我
- ç Ĵ ≤ΣÇ IJ。X 我
第一限制是线性方程类型的，并且意味着必须遵守已知的值A j。
剩下的两个约束是线性不等式，这意味着当出现的符号≥（大于或等于）或尊重或不超过（如果符号≤）时，可以尊重或超过已知值B j和C j（小于或等于）。
型号范例
应用领域非常广泛，从企业管理到营养，但是为了理解该方法，下面提出了一个具有两个变量的实际情况的简单模型。
当地的糕点店以两个特色菜而闻名：黑森林蛋糕和番石榴蛋糕。
在准备过程中，他们需要鸡蛋和糖。对于黑森林，您需要9个鸡蛋和500克糖，而对于皂角膜，您需要8个鸡蛋和800克糖。出售价格分别为8美元和10美元。
问题是：要知道面包店有10公斤的糖和144个鸡蛋，要使利润最大化，每种面包店必须制造多少个蛋糕？
决策变量
决策变量是“ x”和“ y”，它们取实值：
-x：黑森林蛋糕的数量
-y：sa骨型蛋糕。
限制条件
这些限制是由于蛋糕的数量是正数，而制备蛋糕的原料数量有限。
因此，以数学形式，这些限制采用以下形式：
- x≥0
- 且≥0
- 9x + 8y≤144
- 0.5 x + 0.8y≤10
约束1和2构成了先前暴露的非负性条件，并且所有提出的不等式都是线性的。限制3和4中的值不得超过：144个鸡蛋和10公斤糖。
目标功能
最后，目标函数是制造“ x”数量的黑森林蛋糕加“ y”数量的sa肉时获得的利润。它是通过将价格乘以制作的蛋糕数量并为每种类型添加的数量来构建的。这是一个线性函数，我们将其称为G（x，y）：
G = 8x + 10y
解决方法
各种解决方案方法包括图形方法，单纯形算法和内部点方法，仅举几例。
-图形或几何方法
当您遇到上一部分中的二变量问题时，约束条件将确定xy平面中的多边形区域，称为可行区域或可行性区域。
图3.可行区域，找到优化问题的解决方案。资料来源：维基共享资源。
使用限制线构造该区域，限制线是从限制的不等式获得的线，仅适用于等号。
对于要优化利润的面包店，约束线为：
- x = 0
- y = 0
- 9x + 8y = 144
- 0.5 x + 0.8y = 10
这些线包围的区域中的所有点都是可能的解决方案，因此它们无限多。除了在可行区域变为空的情况下，所提出的问题没有解决方案。
幸运的是，对于糕点问题，可行区域不为空，我们在下面进行了介绍。
图4.糕点问题的可行区域。增益为0的线穿过原点。资料来源：F. Zapata与Geogebra。
借助目标函数可以找到最佳解决方案（如果存在）。例如，当尝试找到最大利润G时，我们有以下行，称为等利润线：
G = k 1 x + k 2 y→y = -k 1 x / k 2 + G / k 2
通过这条线，我们获得提供给定增益G的所有线对（x，y），因此根据G的值存在一系列线，但所有线都具有相同的斜率-k 1 / k 2，所以它们是平行线。
最佳解决方案
现在可以证明，线性问题的最优解始终是可行区域的极点或顶点。所以：
如果最接近原点的线具有与可行区域相同的整个线段，则说存在无限解。如果等利润线的斜率等于限制该区域的其他任何一条线的斜率，就会发生这种情况。
对于我们的糕点，候选顶点为A，B和C。
-Dantzig的单纯形法
图形或几何方法适用于两个变量。但是，如果存在三个变量，则更为复杂，并且无法用于大量变量。
当处理两个以上变量的问题时，将使用单纯形法，该方法由一系列算法组成，以优化目标函数。经常使用矩阵和简单算术来进行计算。
单纯形法首先选择可行的解决方案，然后检查其是否最佳。如果是这样，我们已经解决了问题，但是如果不是，我们将继续寻求更接近于优化的解决方案。如果解决方案存在，则算法将在几次尝试中找到它。
应用领域
线性和非线性编程被应用在许多领域，以在降低成本和增加利润方面做出最佳决策，而这并不总是金钱，因为可以及时进行测量，例如，如果您希望将所需时间减至最少进行一系列操作。
以下是一些字段：
-在市场营销中，它用于查找媒体（社交网络，电视，新闻媒体等）的最佳组合来宣传某种产品。
-用于将适当的任务分配给公司或工厂的人员或安排他们的时间表。
-在畜牧业中选择最有营养的食品，并且成本最低。
解决的练习
-练习1
以图形方式解决前面几节中提出的线性编程模型。
解
有必要绘制由问题中指定的限制系统确定的一组值：
- x≥0
- 且≥0
- 9x + 8y≤144
- 0.5 x + 0.8y≤10
由不等式1和2给出的区域对应于笛卡尔平面的第一象限。关于不等式3和4，我们首先找到限制线：
9x + 8y = 144
0.5 x + 0.8y = 10→5x + 8y = 100
可行区域是一个四边形，其顶点是点A，B，C和D。
最低利润为0，因此线8x + 10y = 0为下限，等利润线的斜率为-8/10 =-0.8。
该值不同于其他限制线的斜率，并且由于可行区域是有界的，因此存在唯一解。
图5.练习1的图形化解，显示了可行区域和该区域一个顶点处的解点C。资料来源：F. Zapata。
此解决方案对应于-0.8的一条直线，该直线穿过点A，B或C，其坐标为：
A（11; 5.625）
B（0; 12.5）
C（16，0）
最佳解决方案
我们为以下各点计算G的值：
-（11; 5.625）：G A = 8 x 11 + 10 x 5.625 = 144.25
- （0; 12.5）：G ^ 乙 = 8×0 + 10×12.5 = 125
-（16，0）：G C = 8 x 16 + 10 x 0 = 128
生产11个黑森林蛋糕和5,625个番红花蛋糕的利润最高。该解决方案与通过该软件找到的解决方案一致。
-练习2
通过使用大多数电子表格（例如Excel或LibreOffice Calc）中可用的求解器功能来验证上一练习的结果，该电子表格包含用于线性编程优化的Simplex算法。
解
图6.从练习1到Libre Office Calc电子表格的解决方案详细信息。资料来源：F. Zapata。
图7.从练习1到Libre Office Calc电子表格的解决方案详细信息。资料来源：F. Zapata。
参考文献
- 辉煌。线性规划。摘自：brilliant.org。
- Eppen，G.2000。《行政科学运筹学》。5号 版。学徒大厅。
- Haeussler，E.，1992年。《管理与经济学的数学》。2号 版。Grupo编辑Iberoamericana。
- Hiru.eus。线性规划。从以下位置恢复：hiru.eus。
- 维基百科。线性规划。从以下位置恢复：es。 wikipedia.org。