1、概要

本文以一个实例直观地介绍simplex method算法的步骤，直观地介绍每步为啥要那样做，然后介绍该场景的对偶问题及该场景的线性代数语言描述

2、原问题

2.1、场景描述

一个车间生产一个门获利56元，一个窗获利30元，
一个门需要木工4小时，油漆工2小时。
一个窗需要木工3小时，油漆工1小时。
每天可用木工120小时，油漆工50小时，
如何安排生产才能利润最大化

假设生产x1个门和x2个窗
$max\ z = 56x_1 + 30x_2 \\ s.t. \left\{\begin{matrix} \ 4x_1+3x_2 \leq 120 \\ 2x_1+x_2 \leq 50 \\ x_1,x_2 \geq 0 \\ \end{matrix}\right. \\$

添加松弛变量(slack variable,将不等式转换为等式)
$4x_1+3x_2 + s_1 =120 \\ 2x_1+x_2 + s_2 = 50$

2.2算法步骤

1. 初始化。将问题转化为标准格式，选择松弛变量构成初始可行解
2. 测试目标行是否所有系数都非负，非负结束
3. 根据目标行绝对值最大的元素确定pivot column和entering variable
4. 根据solution/pivot最小值确定departing variable 和pivot row
5. 进行初等行变换，更换basic列中的标签。然后进入步骤2

说明：
各个约束条件构成一个feasible region（可行域），从几何意义上看确定了一个凸多边形，根据定义最优解一定出现在凸多边形的某个顶点上。simplex method选定一个初始可行解，迭代一次前往正收益的邻接顶点（extreme point,极值点），如果没有邻接顶点可以选择那么当前顶点为最优解。
,
步骤1中松弛变量构成一个m阶的单位矩阵，目标行中系数之所以为负，是因为初等行变换操作只有乘以一个标量和加上某行的n倍，如果系数为正，进行初等行变换需要加上别的行的-n倍，那么目标行的solution为负 。
步骤3选择"选择目标行绝对值最大元素"的依据是系数越大， 那么该变量+1，那么目标函数增加量越大。
步骤4选择"solution/pivot最小值"的依据是从线性角度看，solution列是前面各列的线性组合，要是选择"solution/pivot最大值" 会导致其他列左右不平衡

初始化表格

最后一行为目标行（objective row）
basic 这列表示选定的基（basic）,本例有四个可供选择的候选基(x1|x2|s1|s2)
但是两个基确定一个平面，为了简单,初始时选择松弛变量s1和s2确定的单位正交基
solution 列表示每个基的组合系数，初始时120s1+50s2， 目标值=0
根据"目标行绝对值最大"-56确定进入变量为x1, 根据"solution/pivot最小值", min(120/4, 50/2) 确定pivot row = 2,那么departing variable = s2 ,将第二行前面basic的标签改为x1。
根据初等行变换，将第二行每个元素除以2，第一行和第三行分别加上第二行的-4倍和56倍，得到下面的表格

第一次迭代后表格

根据"目标行绝对值最大"-2确定进入变量为x2, 根据"solution/pivot最小值", min(20/1, 25/.5) 确定pivot row = 1,那么departing variable = s1,将第一行前面basic的标签改为x2
根据初等行变换，支点元素已经为1，第二行和第三行分别加上第一行的-1/2倍和2倍，得到下面的表格

再次迭代后表格

目标行所有系数非负，结束，最优解为x2=20, x1=15, 目标值为1440， (2, 24)是对偶问题的解

3、对偶问题

假设有个老板要租赁该车间，最少需要支付的费用
设w1为木工每小时工钱， w2为油漆工每小时工钱
$min \ f = 120w_1 + 50w_2 \\ s.t. \left\{\begin{matrix} 4w_1 + 2w_2 \geq 56 \\ 3w_1 + w_2 \geq 30 \\ w_1\ w_2 \geq 0 \\ \end{matrix}\right. \\ f^* = 1440 w^* = (2, 24)$
对偶问题是一个最小值问题， 将在下一篇文章中使用dual simplex method 规划

4、用线性代数语言描述

原问题
$z=c^T\mathbf{x}\\ Ax=b\\ x_1,x_2 \geq0$

对偶问题
$f=b^T\mathbf{w}\\ A^Tw = c\\ w_1,w_2 \geq 0$

打赏

如果觉得对你有帮助，请杯啤酒分享你快乐把！，谢谢

参考文档

https://brainkart.com/article/The-Simplex-Method_8052/

Posted in: IT人生