线性规划中的等价性证明

参考书目：

[1] 数学规划与组合优化. 浙江大学出版社, 2001. [Online]. Available: https://books.google.com.sg/books?id=ZmSSAAAACAAJ

[2] 组合优化与博弈论. 浙江大学出版社, 2015. [Online]. Available: https://books.google.com.sg/books?id=6w44swEACAAJ

线性规划标准形转化

标准形及转化：

• 目标函数最小化$\min$, 若原规划问题为最大化$\max$, 可取负号转化为$\min$

• 约束条件为等式约束 , 若原规划问题的约束条件为不等式, 可以通过引入松弛变量将不等式转化为等式；

  $\leq$ 需加上引入的松弛变量,$\geq$ 需减去引入的松弛变量；

  ​$eg:$

  $$s.t. \ \ \sum_{j=1}^{n}a_{ij}x_j \leq b_i$$

  ​$\Rightarrow$ 引入松弛变量$s_i$$s.t. \ \ \sum_{j=1}^{n}a_{ij}x_j+s_i = b_i$$s_i \geq 0 (i=1,2,3,...,m)$

  $$s.t. \ \ \sum_{j=1}^{n}d_{ij}y_j \geq b_i$$

  ​$\Rightarrow$ 引入松弛变量$v_i$$s.t. \ \ \sum_{j=1}^{n}d_{ij}y_j-v_i = b_i$$s_i \geq 0 (i=1,2,3,...,m)$

  约束条件右端常数项$b_i\geq0$ , 若$b_i \leq 0$, 可取$-b_i$

• 决策变量非负 , 若决策变量$x_i \leq 0$ , 可定义新的决策变量$x_j=-x_i$；若决策变量无范围限制, 可引入两个非负决策变量$x_i^+$ ,$x_i^-$$\Rightarrow$$x_i=x_j^+-x_i^-$ ,$s.t. \ \ x_i^+,x_i^- \geq 0$

实例

​$eg:$
​ 一种商品在一年中四个季度的 单件价格分别为$p_i\ , \ \ i=1,2,3,4$ , 一家仓库可容纳$C$ 件商品。每件商品在仓库中每存放一个季度的存储费用为$s$ 。现仓库准备通过低价买进、高价售出的方式获取最大利润。试建立数学规划模型, 确定仓库在 每年初 的存货量和每季度的买卖数量。若建立的数学规划为线性规划, 试将其转化为标准型。

解：$

Tips：

• $p_i$为市场价格, 该商品需要以此价格在市场进行买入和卖出, 题目中的利润最大化与“择时”有点像；

• 商品成本：购买成本 + 仓储成本$Cost=\sum_{i=1}^4(x_{i-1}-y_{y-1})s+x_ip_i$, 其中$y_0=0$；

  商品营利：卖出所得$Return=\sum_{i=1}^4 y_i p_i$;

• 约束条件：仓库容纳量$C$ ;

• 隐含条件：年末剩余量与年初存量相等

$\Rightarrow$ 优化问题建模：

设: 每年初存货量为$x_0$, 每季度买入数量为$x_i$, 卖出数量为$y_i$, 利润为$R$

$$\max R=\sum_{i=1} ^4 y_i p_i-(x_ {i-1}-y_{i-1} )s-x_ip_i$$

$$s.t. \ \ x_0 \leq C$$

$$x_0+\sum_{i=1}^n(x_i-y_i) \leq C ,\ \ n=1,2,3,4$$

$$x_0+\sum_{i=1}^n(x_i-y_i) \geq 0 ,\ \ n=1,2,3,4$$

$$x_i,y_i \geq 0 ,\ \ i=1,2,3,4$$

$$x_0 \geq 0$$

$$y_0=0$$

$\Rightarrow$ 标准形转化：引入松弛变量$z_i$

$$W=-R$$

$$\min W=(x_ {i-1}-y_{i-1} )s+x_ip_i-\sum_{i=1} ^4 y_i p_i$$

$$s.t. \ \ x_0+z_1 = C$$

$$x_0+\sum_{i=1}^n(x_i-y_i)+z_{i+1} = C ,\ \ n=1,2,3,4$$

$$x_0+\sum_{i=1}^n(x_i-y_i)-z_{i+4} = 0 ,\ \ n=1,2,3,4$$

$$x_i,y_i \geq 0 ,\ \ i=1,2,3,4$$

$$x_0 \geq 0$$

$$y_0=0$$

$$z_i \geq 0 , \ \ i=1,2,3,4,5,6,7,8,9$$

松弛变量：指在线性规划中引入的一种人工变量, 用于将不等式约束转化为等式约束

标准形转化前后的等价性证明

证明两个线性规划等价

​ 两个线性规划解的情况是相同的, 当且仅当约束条件和目标函数是等价的。

• 两个规划问题的可行域相同, 即约束条件是等价的, 可以将一个问题的约束条件转化为另一个问题的约束条件；

​$eg:$

​ 式约束转化为不等式

​ 不等式约束转化为等式约束$\Rightarrow$ 引入松弛变量或人工变量

​ 限制条件转化为非负条件$\Rightarrow$ 将变量分解负部和正部

• 两个规划问题的目标函数相同, 可以将一个问题的目标函数转化为另一个问题的目标函数；
  ​$eg:$

​ 最大化目标函数与最小化目标函数之间的正负变换

实例

​ 设有线性规划
​$\min \sum^n_{j=1} c_j x_j$
​$\text{s.t.} \sum^n_{j=1}a_{ij}x_j=b_i$$i=1,2,...,m$
​ 试将其转化为含$n+1$ 个非负变量的等价线性规划

解：

​ Tips：

• 该规划问题中决策变量缺少范围限制, 可将变量分解为正部与负部, 转化为非负约束, 但转化前后的变量数量需要进一步思考；
• 其次是需要说明转化前后的等价性；

$\Rightarrow$ 引入新的决策变量$x_j^+$ 及$x^-$ ,$then$$x_j=x_j^{+} -x^-$ , n 个变量$x_j^+$ 共用一个负部$x^-$ , 其中$x_j^+,x^- \geq 0$

​ (若不共用一个负部, 而是分解为$x_j^+,x_j^-$ , 变量数量会变成$2n$ 个, 与题目要求不符)

$$x_j=x_j^{+} - x^-$$

$$\min \sum_{j=1}^n c_j(x_j^{+} - x^-)$$

$$s.t. \ \ \sum_{j=1}^n a_{ij} (x_j^{+} - x^-) = b_i , \ \ i=1,2,...,m$$

$$x_j^+ , x^- \geq 0$$

$\Rightarrow$ 使用连加号不方便证明等价性

​ 原式：

$$\min c_1 x_1+c_2 x_2+...+c_n x_n$$

$$s.t. \ \ a_{11}x_1+a_{12}x_2+...+a_{1n}x_n=b_1$$

$$a_{21}x_1+a_{22}x_2+...+a_{2n}x_n=b_2$$

$$...$$

$$a_{m1}x_1+a_{1m2}x_2+...+a_{mn}x_n=b_m$$

​ 转化后：

$$\min c_1(x_1^{+} - x_1^-)+c_2(x_2^{+} - x_2^-)+...+c_n(x_n^{+} -x_n^-)$$

$$s.t. \ \ a_{11} (x_1^{+} - x_1^-)+a_{12}(x_2^{+} - x_2^-)+...+a_{1n}(x_n^{+} - x_n^-)=b_1$$

$$a_{21} (x_1^{+} - x_1^-)+a_{22}(x_2^ {+} - x_2^-)+...+a_{2n}(x_n^{+} - x_n^-)=b_2$$

$$...$$

$$a_{m1} (x_1^{+} - x_1^-)+a_{m2}(x_2^{+} - x_2^-)+...+a_{mn}(x_n^{+} - x_n^-)=b_m$$

​$Then$

$$x_1^{+} - x^- = \frac{b_1-a_{12}x_2-...-a_{1n}x_n } {a_ {11} } = x_1$$

$$x_2^{+} - x^- = \frac{b_2-a_{21}x_1-...-a_{2n}x_n } {a_ {22} } = x_2$$

$$...$$

$$x_n^{+} - x^- = \frac{b_n-a_{n2}x_2-...-a_{nn}x_n } {a_ {nn} } = x_n$$

​ 将其带入转化后的目标函数

$$\min c_1(\frac{b_1-a_{12}x_2-...-a_{1n}x_n } {a_ {11} } )+c_2(\frac{b_2-a_{21}x_1-...-a_{2n}x_n } {a_ {22} })+...+c_n(\frac{b_n-a_{n2}x_2-...-a_{nn}x_n } {a_ {nn} } )$$

目标函数的最优值同时满足原始规划问题与转化后规划问题的可行域(约束条件), 转化后的最优值同时也是原始规划问题的最优值；

变量共用一个负部

在数学中, 如果多个变量共用一个负部, 通常意味着它们共享相同的约束条件或限制条件。这通常在线性规划或最优化问题中使用, 其中变量需要满足一些限制条件以使目标函数最小或最大化。共享相同的负部可以简化问题的表示和求解过程, 使得问题更容易理解和解决。

推导及证明有误之处欢迎批评指正~