前言：目前在学习线性规划，这只是一个学习的记录，可能会有理解不正确的地方。随着理解的加深，本博客也将持续更新。此外，由于时间限制，这里只会讨论思想和算法流程，具体的证明在卜东波老师的课件Lec 8里已经非常详细了
线性规划问题
首先明确，线性规划是一个最优化算法，且优化的目标是一个线性函数。对于线性函数，如果不做任何约束是没有最值的。线性规划问题除了优化目标外，还有一系列的线性约束条件。所以线性规划问题由两部分组成：
- 优化目标
- 约束条件
线性规划问题的一般形式为：
$$
\begin{array}{r l r l r l r l r l r l r l r l}
\operatorname*{min} & c_1x_1 & + & c_2x_2 & + & \cdots & + & c_nx_n \\
\text{s.t.} & a_{11}x_{1} & + & a_{12}x_{2} & + & \cdots & + & a_{1n}x_{n} & \geq & b_{1} \\
& a_{21}x_{1} & + & a_{22}x_{2} & + & \cdots & + & a_{2n}x_{n} & \leq & b_{2} \\
& \cdots & & \cdots & & \cdots & & \cdots \\
& a_{m1}x_{1} & + & a_{m2}x_{2} & + & \cdots & + & a_{m n}x_{n} & = & b_{m} \\
& & & & & & & x_i & \geq & 0 & \text{ for } \forall i
\end{array}
$$
这种形式是等式和不等式混合的，且不等式方向也没有要求。
标准的线性规划形式是没有等式的，且不等式约束全部为$\leq$。写成矩阵的形式为：
$$
\begin{array}{c c c c}
\mathrm{min}&c^Tx \\
{s.t.}&A x&\leq&b\\
&x&\geq&0
\end{array}
$$
为了方便求解，我们一般使用线性规划的松弛形式。一个不等式通过添加松弛变量可以转化一个等式：
$$
\begin{array}{c}
a_{j1}x_{1} + a_{j2}x_{2} + \dots + a_{j n}x_{n} \leq b_{j} \Longrightarrow \
a_{j1}x_{1} \dots a_{j2}x_{2} + \dots + a_{j n}x_{n} + s \le b_{j}
\end{array}
$$
同时添加新的约束$s\geq 0$。
于是任何一个标准形式可以转化为松弛形式：
$$
\begin{array}{c c c c}
\mathrm{min}&c^Tx \\
{s.t.}&A x&=&b\\
&x&\geq&0
\end{array}
$$
为什么在求解中要转化成松弛形式？因为在求解过程中，我们需要对整个矩阵做高斯行变换，只有等式约束才能做这样的矩阵变换。
将实际问题转化为线性规划问题
Question 1
You want to determine the quantities $x_1, x_2, …, x_n$ of n different foods, each containing m types of nutrients. The amount of the $i$-th nutrient in the $j$-th food is represented as $a_{ij}$, and the prices of the $n$ foods are $c_1, c_2, …, c_n$. Your goal is to find a recipe where the content of each of the $m$ nutrients is at least $b_1,b_2\cdots b_m$, while minimizing the total cost.
Answer:
按照题意，优化目标为最小化购买食物的金额，即最小化$c_1x_1+c_2x_2+\cdots+c_{n}x_{n}$。
对于第$i$种食物，我们可以获得的营养为$a_{i1}x_1+a_{i2}x_{2}+\cdots+a_{in}x_{n}$，要求不小于$b_i$，于是可以列出线性规划方程：
$$
\begin{array}{r l r l r l r l r l r l r l r l}
{\operatorname*{min}}&{c_{1}x_{1}}&{+}&{c_{2}x_{2}}&{+}&{\cdots}&{+}&{c_{n}x_{n}} \\
s.t.&{a_{11}x_{1}}&{+}&{a_{12}x_{2}}&{+}&{\cdots}&{+}&{a_{1n}x_{n}}&{\geq}&{b_{1}}\\
&{a_{21}x_{1}}&{+}&{a_{22}x_{2}}&{+}&{\cdots}&{+}&{a_{2n}x_{n}}&{\geq}&{b_{2}}\\
&\cdots & &\cdots & &\cdots & &\cdots\\
&{a_{m1}x_{1}}&{+}&{a_{m2}x_{2}}&{+}&{\cdots}&{+} &{a_{m n}x_{n}}&{\geq}&{b_{m}}\\
&&&&&&&x_i&{\geq} &{0} & {\mathrm{for}\ \forall i}
\end{array}
$$
Question 2
You now need to pack dormitory items. You have m items and n boxes, with enough boxes to accommodate all items. The space occupied by the i-th item is $C_i$ , and the capacity of the j-th box is $S_j$ . Your goal is to pack all items using as few boxes as possible.
Answer:
设置01变量$x_{ij}$，$x_{ij}=0$表示第$i$个物品没有放在第$j$个盒子，$x_{ij}=1$表示第$i$个物品放在第$j$个盒子。
另外设置01变量$y_j$表示是否使用第$j$个盒子。可列出线性规划方程如下：
$$
\begin{array}{l l l l l r r l r l r l r l r l}
{\operatorname*{min}}&\sum_{i=1}^ny_i\\
{s.t.}&\sum_{k=1}^nx_{ik}&=&1&\mathrm{for}\ \forall i=1,2,\cdots m \\
&\sum_{k=1}^mx_{kj}&\leq& my_j&\mathrm{for}\ \forall j=1,2,\cdots n \\
&\sum_{k=1}^mC_kx_{kj}&\leq& S_jy_j&\mathrm{for}\ \forall j=1,2,\cdots n \\
&y_i &=&0/1&\mathrm{for}\ \forall i \\
&x_{i,j}&=&0/1&\mathrm{for}\ \forall i, j
\end{array}
$$
优化目标为$\sum_{i=1}^ny_i$，由于$y_i$为0或者1，这个式子可以表示使用最少的盒子数量。
第1个限制条件约束了对于任意物品，要求最多只能放在一个盒子里。
第2个限制条件约束了对于任何一个盒子，如果选择不使用，则放置的物品数量不超过0，如果选择使用，放置的物品数量不超过最大的物品数m。
第3个限制条件约束了每个使用的盒子放置物品的体积不能超过其最大容量。
第4,5个限制条件约束了$x,y$为01变量。
Question 3
On a farm, there are two different crops: wheat and soybeans. Planting one acre of wheat requires 5 units of fertilizer and 2 units of water, while planting one acre of soybeans requires 3 units of fertilizer and 4 units of water. The farm has 30 units of fertilizer and 20 units of water available. Each acre of wheat can be sold for 150 dollars, and each acre of soybeans can be sold for 120 dollars. The farm owner wants to maximize the total income.
Answer:
设置变量$x_1$,$x_2$分别表示种植wheat和soybeans的数量。可列出线性规划方程如下：
$$
\begin{array}{l l l l l r r l r l r l r l r l}
{\operatorname*{min}}&-(150x_1+120x_2)\\
{s.t.}&5x_1+3x_2&\leq&30\\
&2x_1 + 4x_2&\leq& 20\\
&x_1,x_2 &\geq&0
\end{array}
$$
优化目标为最小化$-(150x_1+120x_2)$，对应最大化收入。
限制条件1约束了种物消耗的化肥不能超过最大可用化肥30。
限制条件2约束了种物需要的水量不能超过最大可用水量20.
限制条件3约束了种植的数量是一个非负数。
Question 4
The company manufactures three products, A1, A2, and A3, utilizing resources such as metal sheets, labor, and machinery. The quantities of various resources required to manufacture one unit of each product are provided in the table below. Without considering fixed costs, the unit profits for each product are 40,000 yuan, 50,000 yuan, and 60,000 yuan, respectively. Available resources include 500 tons of metal sheets, 300 workers per month, and 100 machines per month. In addition to production, fixed costs must be paid: 1 million yuan for A1, 1.5 million yuan for A2, and 2 million yuan for A3. Develop a production plan for the company to maximize profits.
Resources A1 A2 A3 Metal sheets/t 2 4 8 Labor force (person/month) 2 3 4 Machinery (units/month) 1 2 3
Answer:
设置变量$x_1,x_2,x_3$分别表示$A_1,A_2,A_3$的生产数量，01变量$y_1,y_2,y_3$表示是否生产$A_1,A_2,A_3$。可列出线性规划方程如下：
$$
\begin{array}{l l l l l r r l r l r l r l r l}
{\operatorname*{min}}&-(40000x_1+50000x_2+60000x_3-1000000y_1-1500000y_2-2000000y_3)\\
{s.t.}&2x_1+4x_2+8x_3&\leq&500\\
&2x_1 + 3x_2 + 4x_3&\leq& 300\\
&x_1 + 2x_2 + 3x_3&\leq& 100\\
&x_1&\leq&100y_1\\
&x_2&\leq&100y_2\\
&x_3&\leq&100y_3\\
&x_1,x_2,x_3 &\geq&0\\
&y_1,y_2,y_3 &=&0/1
\end{array}
$$
优化目标为最大化生产收益，表现为利润($40000x_1+50000x_2+60000x_3$)-成本($1000000y_1-1500000y_2-2000000y_3$)。由于$y_i$为01变量，如果为0，表示不生产该产品，则不需要该产品的固定费用开销；如果为1，表示生产该产品，则需要对应固定费用开销。
第一个限制条件约束了生产使用的金属不能超过最大供应量500。
第二个限制条件约束了生产使用的人力不能超过最大供应量300。
第三个限制条件约束了生产使用的机器不能超过最大供应量100。
第四个限制条件约束了如果选择不生产$A_1$，则$A_1$的生产数量为0。对应$y_1=0$时，$x_1$取值为0。当$y_1=1$时，对应$x_1\leq100$。由于前三个限制已经限制了$x_1\leq100$，当$y_1=1$时，该限制条件不影响$x_1$的取值。
第五个限制条件约束了如果选择不生产$A_2$，则$A_2$的生产数量为0。对应$y_2=0$时，$x_2$取值为0。当$y_2=1$时，对应$x_2\leq100$。由于前三个限制已经限制了$x_2\leq100$，当$y_2=1$时，该限制条件不影响$x_2$的取值。
第六个限制条件约束了如果选择不生产$A_3$，则$A_3$的生产数量为0。对应$y_3=0$时，$x_3$取值为0。当$y_3=1$时，对应$x_3\leq100$。由于前三个限制已经限制了$x_3\leq100$，当$y_3=1$时，该限制条件不影响$x_3$的取值。
第七个限制条件约束了生产的数量为一个非负数。
第八个限制条件约束了$y$为01变量
单纯形法
未完待续……
