最优化笔记
\(\mathcal{Author:gpf}\)
基本单纯形方法
例题： \[ \max\ z=2x_1+3x_2\\ s.t.\ x_1+2x_2\le8\\ 4x_1\le16\\ 4x_2\le12 \] 转化为等式约束形式。有大于等于则再加人工变量
\[ x_1+2x_2+S_1=8\\ 4x_1+S_2=16\\ 4x_2+S_3=12 \] 画出单纯形表，对应列即为约束条件中的系数，解列为等号右边的数字
| 基 | \(x_1\) | \(x_2\) | \(S_1\) | \(S_2\) | \(S_3\) | 解 |
|---|---|---|---|---|---|---|
| Z | -2 | -3 | 0 | 0 | 0 | 0 |
| \(S_1\) | 1 | 2 | 1 | 0 | 0 | 8 |
| \(S_2\) | 4 | 0 | 0 | 1 | 0 | 16 |
| \(S_3\) | 0 | 4 | 0 | 0 | 1 | 12 |
确定进基变量和离基变量：Z行绝对值最大的负值是进基变量，确定进基变量后解列除以进基变量列，最小非负比的行是离基变量。此处为S3行，x2列
随后进行高斯-？？运算
- 进基变量行（S3）除以（S3，x2）的元素（要写出来Z行和离基变量行、最小非负比）
- 其他行减去新的离基变量行*进离基变量列对应的系数
得到第二个单纯形表
| 基 | \(x_1\) | \(x_2\) | \(S_1\) | \(S_2\) | \(S_3\) | 解 |
|---|---|---|---|---|---|---|
| Z | -2 | 0 | 0 | 0 | 3/4 | 9 |
| \(S_1\) | 1 | 0 | 1 | 0 | -1/2 | 2 |
| \(S_2\) | 4 | 0 | 0 | 1 | 0 | 16 |
| \(x_2\) | 0 | 1 | 0 | 0 | 1/4 | 3 |
重复上述步骤，得到第三个表
| 基 | \(x_1\) | \(x_2\) | \(S_1\) | \(S_2\) | \(S_3\) | 解 |
|---|---|---|---|---|---|---|
| Z | 0 | 0 | 2 | 0 | -1/4 | 13 |
| \(x_1\) | 1 | 0 | 1 | 0 | -1/2 | 2 |
| \(S_2\) | 0 | 0 | -4 | 1 | 2 | 8 |
| \(x_2\) | 0 | 1 | 0 | 0 | 1/4 | 3 |
第四个表
| 基 | \(x_1\) | \(x_2\) | \(S_1\) | \(S_2\) | \(S_3\) | 解 |
|---|---|---|---|---|---|---|
| Z | 0 | 0 | 3/2 | 1/8 | 0 | 14 |
| \(x_1\) | 1 | 0 | 0 | 1/4 | 0 | 4 |
| \(S_3\) | 0 | 0 | -2 | 1/2 | 1 | 4 |
| \(x_2\) | 0 | 1 | 1/2 | -1/8 | 0 | 2 |
最后解列为x1=4，x2=2，Z=14
检验方法：每次确定最小非负比*单位改善率（离基变量系数）=每次改善多少
评分：等式形式、单纯性表+高斯？？运算、结果
两阶段单纯形法
例题： \[ \min\ z=4x_1+x_2\\ s.t.\ 3x_1+x_2\le3\\ 4x_1+3x_2\ge6\\ x_1+2x_2\le4 \] 转化为等式约束：大于等于号要加R1人工变量，而且前面的x4是负号 \[ 3x_1+x_2+x_3=3\\ 4x_1+3x_2-x_4+R_1=6\\ x_1+2x_2+x_5=4 \] ### 阶段1：
\[ \min\ r=R_1\\ s.t.\ 3x_1+x_2+x_3=3\\ 4x_1+3x_2-x_4+R_1=6\\ x_1+2x_2+x_5=4 \]
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(R_1\) | \(x_5\) | 解 |
|---|---|---|---|---|---|---|---|
| r | 0 | 0 | 0 | 0 | -1 | 0 | 0 |
| \(x_3\) | 3 | 1 | 1 | 0 | 0 | 0 | 3 |
| \(R_1\) | 4 | 3 | 0 | -1 | 1 | 0 | 6 |
| \(x_5\) | 1 | 2 | 0 | 0 | 0 | 1 | 4 |
与r=0矛盾，调整r行：将人工变量R1,R2等加到r行上
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(R_1\) | \(x_5\) | 解 |
|---|---|---|---|---|---|---|---|
| r | 4 | 3 | 0 | -1 | 0 | 0 | 6 |
| \(x_3\) | 3 | 1 | 1 | 0 | 0 | 0 | 3 |
| \(R_1\) | 4 | 3 | 0 | -1 | 1 | 0 | 6 |
| \(x_5\) | 1 | 2 | 0 | 0 | 0 | 1 | 4 |
由于求r的最小值，因此寻找r行系数为正且绝对值最大的列为进基变量，即x1。最小非负比为x3
进行高斯-？？运算，列出数据
新的表如下
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(R_1\) | \(x_5\) | 解 |
|---|---|---|---|---|---|---|---|
| r | 0 | 5/3 | -4/3 | -1 | 0 | 0 | 2 |
| \(x_1\) | 1 | 1/3 | 1/3 | 0 | 0 | 0 | 1 |
| \(R_1\) | 0 | 5/3 | -4/3 | -1 | 1 | 0 | 2 |
| \(x_5\) | 0 | 5/3 | -1/3 | 0 | 0 | 1 | 3 |
重复上述操作，新表如下（x2、R1）
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(R_1\) | \(x_5\) | 解 |
|---|---|---|---|---|---|---|---|
| r | 0 | 0 | 0 | 0 | -1 | 0 | 0 |
| \(x_1\) | 1 | 0 | 3/5 | 1/5 | -1/5 | 0 | 3/5 |
| \(x_2\) | 0 | 1 | -4/5 | -3/5 | 3/5 | 0 | 6/5 |
| \(x_5\) | 0 | 0 | 1 | 1 | -1 | 1 | 1 |
无法继续改善，r=0，说明有最优解（正数则无解）
阶段2
沿用上一阶段的系数 \[ \min\ Z=4x_1+x_2\\ s.t.\ x_1+0x_2+3/5x_3+1/5x_4+0x_5=3/5\\ 0x_1+x_2-4/5x_3-3/5x_4+0x_5=6/5\\ 0x_1+0x_2+x_3+x_4-x_5=1 \] 单纯形表：
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | 解 |
|---|---|---|---|---|---|---|
| Z | -4 | -1 | 0 | 0 | 0 | 0 |
| \(x_1\) | 1 | 0 | 3/5 | 1/5 | 0 | 3/5 |
| \(x_2\) | 0 | 1 | -4/5 | -3/5 | 0 | 6/5 |
| \(x_5\) | 0 | 0 | 1 | 1 | 1 | 1 |
与z=0矛盾，调整z行：z行对应列（如x1）的系数乘以对应行（x1）
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | 解 |
|---|---|---|---|---|---|---|
| Z | 0 | 0 | 8/5 | 1/5 | 0 | 18/5 |
| \(x_1\) | 1 | 0 | 3/5 | 1/5 | 0 | 3/5 |
| \(x_2\) | 0 | 1 | -4/5 | -3/5 | 0 | 6/5 |
| \(x_5\) | 0 | 0 | 1 | 1 | 1 | 1 |
进基变量：x3，离基：x1、x5均可，不妨取x1
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | 解 |
|---|---|---|---|---|---|---|
| Z | -8/3 | 0 | 0 | -1/3 | 0 | 2 |
| \(x_3\) | 5/3 | 0 | 1 | 1/3 | 0 | 1 |
| \(x_2\) | 4/3 | 1 | 0 | -1/3 | 0 | 2 |
| \(x_5\) | -5/3 | 0 | 0 | 2/3 | 1 | 0 |
x1=0,x2=2,z=2
评分点：
等式约束、表+高斯？？、第一阶段结果（R=0，r=0，几个变量的值）、新的规划函数、
对偶问题
例题： \[ \min\ Z=15x_1+12x_2\\ x_1+2x_2\ge3\\ 2x_1-4x_2\le8\\ x_1,x_2\ge0 \] 原始问题的等式约束如下（无需加人工变量） \[ \min\ Z=15x_1+12x_2+0x_3+0x_4\\ x_1+2x_2-x_3=3(对应对偶变量y_1)\\ 2x_1-4x_2+x_4=8(对应对偶变量y_2)\\ x_1,x_2,x_3,x_4=0 \] 对偶问题 \[ \max\ w=3y_1+8y_2\\ s.t.\ y_1+2y_2\le15\\ 2y_1+4y_2\le12\\ -y_1+0y_2\le0\\ 0y_1+y_2\le0\\ y_1,y_2无限制 \] 评分点：
运输模型
例题：
求初始解、最优解
| 10 | 4 | 2 | 8 |
| 2 | 3 | 4 | 6 |
| 2 | 3 | 1 | 5 |
| 7 | 6 | 6 | 供应/需求 |
评分点：求初始解
目标规划
整数规划
动态规划
其实就是经典动态规划的倒序
例题（背包问题）：
货船最多装6吨
| 货物i | wi | ri |
|---|---|---|
| 1 | 4 | 70 |
| 2 | 1 | 20 |
| 3 | 2 | 40 |
阶段3 \(f_3(x_3)=\max\limits_{m_3=0,1,..,3}\{40m_3\}\)
| x3 | 40m3 | 最优解 | ||||
|---|---|---|---|---|---|---|
| （背包容量） | \(m_3=0\) | \(m_3=1\) | \(m_3=2\) | \(m_3=3\) | \(f_3(x_3)\) | \(m_3^*\) |
| 0 | 0 | - | - | - | 0 | 0 |
| 1 | 0 | - | - | - | 0 | 0 |
| 2 | 0 | 40 | - | - | 40 | 1 |
| 3 | 0 | 40 | - | - | 40 | 1 |
| 4 | 0 | 40 | 80 | - | 80 | 2 |
| 5 | 0 | 40 | 80 | - | 80 | 2 |
| 6 | 0 | 40 | 80 | 120 | 120 | 3 |
阶段二 \(f_2(x_2)=\max\limits_{m_2=0,1,...,6}\{20m_2+f_3(x_2-m_2)\}\)
| x2 | 20m2+f3(x2-m3) | 最优解 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| （背包容量） | \(m_2=0\) | \(m_2=1\) | \(m_2=2\) | \(m_2=3\) | \(m_2=4\) | \(m_2=5\) | \(m_2=6\) | \(f_2(x_2)\) | \(m_2^*\) |
| 0 | 0+0=0 | - | - | - | - | - | - | 0 | 0 |
| 1 | 0+0=0 | 20+0=20 | - | - | - | - | - | 20 | 1 |
| 2 | 0+40=40 | 20+0=20 | 40+0=40 | - | - | - | - | 40 | 0,2 |
| 3 | 0+40=40 | 20+40=60 | 40+0=40 | 60+0=60 | - | - | - | 60 | 1,3 |
| 4 | 0+80=80 | 20+40=60 | 40+40=80 | 60+0=60 | 80+0=80 | - | - | 80 | 0,2,4 |
| 5 | 0+80=80 | 20+80=100 | 40+40=80 | 60+40=100 | 80+0=80 | 100+0=100 | - | 100 | 1,3,5 |
| 6 | 0+80=120 | 20+80=100 | 40+80=120 | 60+40=100 | 80+40=120 | 100+0=100 | 120+0=120 | 120 | 0,2,4,6 |
阶段三 \(f_1(x_1)=\max\limits_{m_1=0,1}\{70m_1+f_2(x_1-4m_1)\}\)
| x1 | 70m1+f2(x1-4m1) | 最优解 | ||
|---|---|---|---|---|
| （背包容量） | \(m_1=0\) | \(m_1=1\) | \(f_1(x_1)\) | \(m_1^*\) |
| 0 | 0+0=0 | - | 0 | 0 |
| 1 | 0+20=20 | - | 20 | 0 |
| 2 | 0+40=40 | - | 40 | 0 |
| 3 | 0+60=60 | - | 60 | 0 |
| 4 | 0+80=80 | 70+0=0 | 80 | 0 |
| 5 | 0+100=100 | 70+20=90 | 100 | 0 |
| 6 | 0+120=120 | 70+40=110 | 120 | 0 |
网络优化模型
例题：
表1
| 节点 | 距离 | 状态 | |
|---|---|---|---|
| 1 | [0,-] | 永久 | |
| 2 | [100,1] | 暂时 | |
| 3 | [30,1] | 暂时 | 永久 |
表2
| 节点 | 距离 | 状态 | |
|---|---|---|---|
| 1 | [0,-] | 永久 | |
| 2 | [100,1] | 暂时 | |
| 3 | [30,1] | 永久 | |
| 4 | [40,3] | 暂时 | 永久 |
| 5 | [90,3] | 暂时 |
表3
| 节点 | 距离 | 状态 | |
|---|---|---|---|
| 1 | [0,-] | 永久 | |
| 2 | [100,1] | 暂时 | |
| 3 | [30,1] | 永久 | |
| 4 | [40,3] | 永久 | |
| 5 | [85,4] | 暂时 | 永久 |
min Z=85
1-3-4-5