Mathematica解线性规划

线性规划（英语：Linear Programming，简称 LP）特指目标函数和约束条件皆为线性的最优化问题。线性规划在工程、经济、管理等领域广泛应用，例如生产计划、资源分配、运输问题、物流优化、金融风险管理、投资组合优化等问题都可以用线性规划来建模和求解。在微观经济学和商业管理领域中，线性规划亦被大量应用于例如降低生产过程的成本等手段，最终提升产值与营收。对线性规划有早期贡献的列昂尼德·维塔利耶维奇·康托罗维奇和特亚林·科普曼斯于1975年共同获得诺贝尔经济学奖。

线性规划问题的基本形式如下：

目标函数：一个或多个线性函数（最小化或最大化）
约束条件：一系列线性等式或不等式约束
优化变量：目标函数中的一项或多项，可以变化，目标是最优解。

解决线性规划问题通常包括以下步骤：

1. 确定问题：首先明确问题的目标函数和约束条件。
1. 构造线性规划标准形式：将原始问题转化为标准形式。目标函数 $或$ ，其中是常数，是变量。约束条件可以是等式也可以是不等式， $或或$ 。
1. 寻找最优解：通过一些数学方法（例如，单纯形法）求解上述线性规划问题，得到最优解。

线性规划可以通过各种方法求解，其中最常用的方法包括单纯形法（Simplex Method）、内点法（Interior Point Method）和对偶法（Duality Method）等。这些方法都旨在有效地寻找最优解，尽可能减少计算量和时间。Mathematica 提供了这些方法的实现，可以方便地解决线性规划问题。

线性规划的几何含义

从上图可以清楚地看出，目标函数和和黄色可行域有一个交点的时候能够取到最大值，虚线和可行区域有交集但不是最大值，点线和可行区域没有交集。下面用两个例子说明怎么在 Mathematica 中求解线性规划。

Mathematica

例 1：炼油厂使用三种原料油 1、2、3 混合加工成 A、B、C 三类不同的汽油产品有关数据如下表所示。另外，由于市场原因，A 的产量不得低于产品总量的40%。问该厂应如何安排生产才能使其总利润最大?

原料	产品			原料成本（元/吨）	原料限量（吨）
原料	A	B	C	原料成本（元/吨）	原料限量（吨）
1	>= 60%	>= 15%		1800	2000
2				1350	2500
3	<= 20%	<= 60%	<= 50%	900	1200
加工费（元/吨）	450	360	270
售价（元/吨）	3060	2565	2025

解：设 A、B、C 三类不同的汽油产品需要的 1、2、3 三种原料分别为 , , ，则利润为：

$售价原料加工$

约束有：

下面利用 Mathematica 求解：

In[]:=

Maximize[{3060 (xA1 + xA2 + xA3) + 2565 (xB1 + xB2 + xB3) + 2025 (xC1 + xC2 + xC3)
   - (1800 (xA1 + xB1 + xC1) + 1350 (xA2 + xB2 + xC2) + 900 (xA3 + xB3 + xC3))
   - (450 (xA1 + xA2 + xA3) + 360 (xB1 + xB2 + xB3) + 270 (xC1 + xC2 + xC3)),
  
  xA1 >= 0, xA2 >= 0, xA3 >= 0, xB1 >= 0, xB2 >= 0, xB3 >= 0, xC1 >= 0, xC2 >= 0, xC3 >= 0,
  
  xA1 >= 0.6 (xA1 + xA2 + xA3),
  xB1 >= 0.15 (xB1 + xB2 + xB3),
  
  xA3 <= 0.2 (xA1 + xA2 + xA3),
  xB3 <= 0.6 (xB1 + xB2 + xB3),
  xC3 <= 0.5 (xC1 + xC2 + xC3),
  
  xA1 + xB1 + xC1 <= 2000,
  xA2 + xB2 + xC2 <= 2500,
  xA3 + xB3 + xC3 <= 1200,
  
  (xA1 + xA2 + xA3)/(xA1 + xA2 + xA3 + xB1 + xB2 + xB3 + xC1 + xC2 + xC3) >= 0.4},
 {xA1, xA2, xA3, xB1, xB2, xB3, xC1, xC2, xC3}]

Out[]:=

第一行为求解出来的最大值，第二第三行是变量的取值。

例 2：造纸厂生产宽度为 3 米的卷筒纸，再将这种大卷筒切成宽度分别为 1.6 米、1.1 米和 0.7 米的小卷筒。市场对这三种小卷筒的需求分别是 100、200 和 400 个。应以怎样的方法切割，可使耗用的大卷筒最少而又能满足市场的需求?

解：3 米的大卷筒纸切成宽度分别为 1.6 米、1.1 米和 0.7 米的小卷筒，有下面几种切割方案，并假设第 n 种方案需要个大卷筒纸：

方案	x1	x2	x3	x4	x5
1.6	0	1	1	0	0
1.1	0	1	0	1	2
0.7	4	0	2	2	1

其他方案已经包含在上面的方案中了。比如 3 米的卷筒纸只切割成 1 个 1.6 米的小卷筒，已经包含在方案 2 和 3 中。

需要大卷筒纸的总数为：

约束有：

下面利用 Mathematica 求解：

In[]:=

Minimize[{x1 + x2 + x3 + x4 + x5,
  
  x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0, x5 >= 0,
  x1 \[Element] Integers, x2 \[Element] Integers, 
  x3 \[Element] Integers, x4 \[Element] Integers, 
  x5 \[Element] Integers,
  
  x2 + x3 >= 100,
  x2 + x4 + 2 x5 >= 200,
  4 x1 + 2 x3 + 2 x4 + x5 >= 400}, 
  {x1, x2, x3, x3, x4, x5}]

Out[]:=

第一行为求解出来的最小值，第二行是变量的取值。