算法设计与分析 作业13

第十三周作业

1. 构造一个线性规划问题，使得原始问题和对偶问题都没有可行解。分别写出原始问题和对偶问题。

原始问题$\min{z = x_1+x_2}$，约束条件$\begin{cases}x_1+x_2\leq -1\-x_1-x_2\leq -1\\x_1, x_2\geq0\end{cases}$，显然没有可行解

对偶问题$\max{w=-y_1-y_2}$，约束条件$\begin{cases} y_1-y_2\geq1 \\ y_1-y_2\geq1 \\ y_1, y_2\geq0 \end{cases}$，可行域无界

2. 使用线性规划对如下问题建模

1.

$\max{w=6x_1+8x_2}$，约束条件$\begin{cases}4x_1+4x_2\leq 40\\5x_1+10x_2\leq 60\\x_1, x_2\geq0\end{cases}$

2.

设$x_{i,j}$表示护士$i$是否在第$j$天值班。则目标为$\min{z=\sum\limits_{i=1}^m{\sum\limits_{j=1}^7{x_{i,j}}}}$；

约束条件为$\begin{cases} \sum\limits_{i=1}^m{x_{i,j}} \geq d_j \\ \sum\limits_{j=0}^7{x_{i,j}} \leq 5 \\ \sum\limits_{k=0}^4{x_{i,(j+k-1)\text{ mod }7+1}} \geq 3 \\ \exist j:x_{i,j} + x_{i,j\text{ mod }7 + 1}\leq0\end{cases}$

3.

设$t_i$为航班$i$降落的时间，那么目标为$\max{\min{t_i-t_{i-1}}}$

约束条件为$\begin{cases}t_i<t_{i+1}, i=1,2,\dots,n-1\\ t_i \geq a_i, i=1,2,\dots,n\\ t_i \leq b_i, i=1,2,\dots,n\end{cases}$

3. 下列约束是否是线性约束？如果不是线性约束，能否将其等价转换成线性约束？如果能转化，请展示；如果不能，说明原因。

1. $-3x_1-5x_2+22\geq18$

是线性约束

2. $2x_1^2-8\leq0$

不是，但可以转化成$\begin{cases}x_1\leq2\\x_1\geq-2\end{cases}$

3. $x_1x_2-3x_1-x_2+3=0$

不是，但可以转化，$\Rightarrow (x_1-1)(x_2-3)=0 \Rightarrow \begin{cases}x_1=1\\x_2=3\end{cases}$

4. $\frac{3x_1-2x_2}{2x_1+1}=4$

不是，但可以转化$\Rightarrow 5x_1+2x_2+4=0$

5. $e^{3x_1+5x_2}\geq12$

不是，但可以转化$\Rightarrow 3x_1+5x_2\geq \ln{12}$

6. $|x|<3$

不是，但可以转化成$\begin{cases}x_1 <3\\x_1>-3\end{cases}$

7. $\max{\left\{ x_1, -x_1+7x_2, x_2^3 \right\}} \leq 8$

不是，可以转化成$\begin{cases}x_1\leq8\\ -x_1+7x_2\leq 8\\ x_2 \leq 2\end{cases}$

8. $\min{\{2x_1, 3x_2\}}\geq\max{\{10-x_1, 6-x_2\}}$

不是，但是可以转化为$\begin{cases} x_1 \geq \frac{10}{3}\\ 2x_1+x_2\geq6\\ x_1+3x_2\geq10\\ x_2\geq\frac{3}{2}\end{cases}$

4. 转化为线性规划问题

1. 最小化最大化问题 $\min\limits_{x} \max\limits_{i=1,\ldots,n} \{c_i^T x + d_i\}$

转化成

$$\min_{x, z} z \\ \text{s.t. } c_i^T x + d_i \leq z \quad \forall i = 1, \ldots, n \\ \text{s.t. } Ax = b \\ \text{s.t. } x \geq 0 \\ z \in \mathbb{R}$$

2. 绝对值问题 $\min{\sum\limits_{i=1}^n{\left|x_i\right|}}$

(1). 转化为线性规划问题

对于每个$x_i$，引入两个非负变量$y_i^+=\max{\{0,x_i\}}, y_i^-=\max{\{0,-x_i\}}$，那么$x_i=y_i^+-y_i^-, |x|=y_i^++y_i^-$

转化成

$$\min{\sum\limits_{i=1}^n{\left(y_i^++y_i^-\right)}}\\ \text{s.t. } Ax = b \\ \text{s.t. } x_i=y_i^+-y_i^-\quad\forall i=1,2,\cdots,n\\ \text{s.t. } y_i^+,y_i^-\geq0\quad\forall i=1,2,\cdots,n\\$$

(2). max能不能转化？

不能。最大化绝对值和的问题是一个非凸优化问题。线性规划只能处理凸优化问题，因此直接使用线性规划求解器可能会得到局部最优解而不是全局最优解。

3. 线性分式规划

令$t=\frac{c^T x + d}{e^T x + f}$，也就是要满足$( c^T x + d) \geq t (e^T x + f)$

转化成

$$\min_{x, t} t \\ \text{s.t. } c^T x + d \geq t (e^T x + f) \\ \text{s.t. } Ax \leq b \\ \text{s.t. } e^T x + f > 0$$

5. 写出线性规划的对偶形式

1.

$$\min{5y_1+12y_2+8y_3}\\ \text{s.t. }1y_1+4y_3\leq5\\ y_1+3y_2-y_3\leq6\\ -4y_2\geq-1\\ -3y_1+2y_2+5y_3=2\\ y_1\leq0, y_2\geq0, y_3\text{ free}$$

2.

看不大懂 问AI的

将原问题视为一个零和博弈问题，借助于零和博弈中的鞍点理论来得到对偶问题。

考虑原问题的拉格朗日函数$L(t, \vec{p}, \lambda, \mu) = t + \lambda^T (t \cdot \vec{1} - M^T \vec{p}) + \mu (\vec{1}^T \vec{p} - 1)$，其中，$\lambda$和$\mu$是拉格朗日乘子。根据鞍点理论，我们需要找到使得拉格朗日函数在所有可能的$t$和$\vec{p}$上达到最大值，在所有可能的$\lambda$和$\mu$上达到最小值的点。

首先，对$t$和$\vec{p}$求偏导数并令其为零：

$$\frac{\partial L}{\partial t} = 1 + \lambda^T \vec{1} = 0 \implies \lambda^T \vec{1} = -1\\ \frac{\partial L}{\partial \vec{p}} = -M^T \lambda + \mu \vec{1} = 0 \implies M^T \lambda = \mu \vec{1}$$

其次，对$\lambda$和$\mu$求偏导数并令其为零：

$$\frac{\partial L}{\partial \lambda} = t \cdot \vec{1} - M^T \vec{p} \leq \vec{0}\\ \frac{\partial L}{\partial \mu} = \vec{1}^T \vec{p} - 1 = 0 \implies \vec{1}^T \vec{p} = 1$$

这样，对偶问题为

$$& \min_{\lambda, \mu} \mu \\ & \text{s.t. } M^T \lambda = \mu \vec{1} \\ & \text{s.t. } \lambda^T \vec{1} = -1 \\ & \text{s.t. } \lambda \geq \vec{0}$$