两阶段法（基本原理+例题解析）

基本思想：构造一个辅助线性规划问题（ALP）,通过求解它得到线性规则（LP）的初始可行基。

背对人潮

2150人浏览 · 2023-11-16 19:03:50

背对人潮 · 2023-11-16 19:03:50 发布

基本思想：构造一个辅助线性规划问题（ALP）,通过求解它得到线性规则（LP）的初始可行基。

基本概念：

例题分析：

基本概念：

对于标准形式的线性规则问题：

$\left\{\begin{matrix} minf(x)=c^{T}x\\s.t.Ax=b \\ x\geq 0 \end{matrix}\right.$

其中 $b\geq 0$ ,A 是 $m\times n$ 矩阵， $m< n$ ，但 A 不一定满秩。

$ALP\left\{\begin{matrix} minz=y_{1}+y_{2}+...+y_{m}\\ s.t.f-c_{1}x_{1}-c_{2}x_{2}-...-c_{n}x_{n}=0(*) \\ y_{1}+a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}=b_{1} \\ y_{2}+a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}=b_{1} \\ ... \\ y_{m}+a_{m1}x_{1}+a_{12}x_{2}+...+a_{mn}x_{n}=b_{1} \\y_{1},y_{2},...,y_{m},x_{1},x_{2},...,x_{n}>0 \end{matrix}\right.$

其中， $y_{1},y_{2},...,y_{m}$ 是人工变量

注意：（*）行只参与消元运算，不参与主元的确定。引入这一行的目的在于直接算出原问题的最优解和最优值。

例题分析：

例题：求解线性规则：

$\left\{\begin{matrix} minf(x)=4x_{1}+3x_{3}\\s.t.3x_{1}+6x_{2}+3x_{3}-4x_{4}=12\\6x_{1}+3x_{3}=12\\3x_{1}-6x_{2}+4x_{4}=0\\ x_{1},x_{2},x_{3},x_{4}\geq 0 \end{matrix}\right.$

解：构造辅助线性规划（ALP）

$\left\{\begin{matrix} minz=y_{1}+y_{2}+y_{3}\\s.t.f-4x_{1}-3x_{3}=0\\y_{1}+3x_{1}+6x_{2}+3x_{3}-4x_{4}=12\\y_{2}+6x_{1}+3x_{3}=12\\y_{3}+3x_{1}-6x_{2}+4x_{4}=0\\ x_{1},x_{2},x_{3},x_{4},y_{1},y_{2},y_{3} \geq 0 \end{matrix}\right.$

可以得到下列矩阵：

$A=\left [ \begin{smallmatrix} 1 &0 &0 &3 &6 &3 &-4 \\0 &1 &0 &6 &0 &3 &0 \\0 &0 & 1 &3 &-6 &0 & 4 \end{smallmatrix} \right ]$ ， $b=\bigl(\begin{smallmatrix} 12\\ 12 \\0 \end{smallmatrix}\bigr)$ ， $c=(1,1,1,0,0,0,0)^{T}$

ALP选取 $y_{1},y_{2},y_{3}$ 作为基的单纯形表如下：

		s	$y_{1}$	$y_{2}$	$y_{3}$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$
z	24	0	0	0	0	12	0	6	0
f	0	1	0	0	0	-4	0	-3	0
$y_{1}$	12	0	1	0	0	3	6	3	-4
$y_{2}$	12	0	0	1	0	6	0	3	0
$y_{3}$	0	0	0	0	1	3	-6	0	4

(*)对于目标函数 Z 来说： $c_{B}^{T}B^{-1}A-c^{T}=(1,1,1) I A-(1,1,1,0,0,0,0)=(0,0,0,12,0,6,0)$

(**)对于目标函数 Z 来说： $c_{B}^{T}B^{-1}A-c^{T}=(0,0,0) I A-(0,0,0,4,0,3,0)=(0,0,0,-4,0,-3,0)$

检验数有正数，此时并不是最优解，需要寻找离基变量和进基变量。

$Min\left \{ \frac{12}{3},\frac{12}{6},\frac{0}{3} \right \}=0$

离基变量： $y_{3}$ ，进基变量： $x_{1}$ ，得到主元，由主元做旋转变换，得到新的单纯形表：

检验数有正数，此时并不是最优解，需要寻找离基变量和进基变量。

$Min\left \{ \frac{12}{12},\frac{12}{12} \right \}=1$

离基变量： $y_{1}$ ，进基变量： $x_{2}$ ，得到主元，由主元做旋转变换，得到新的单纯形表：

检验数全部为正，Z=0，说明当前解为 ALP 最优解，将多余的划掉，得到 LP 的单纯形表：

		$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$
f	8	0	0	-1	0
$x_{2}$	1	0	1	1/4	-2/3
$x_{1}$	2	1	0	1/2	0

由于检验数全部非正，所以得到 LP 的最优解： $\bar{x}=(2,1,0,0)^{T}$ ，最优值为： $f(\bar{x})=8$ 。

（行文中若有纰漏，希望大家指正）

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

深度解析：提示工程架构师助力Agentic AI商业模式升级

Agentic AI不是简单的“对话机器人”，而是具备目标规划、任务分解、工具使用、环境交互能力的自主智能体。它能独立完成复杂任务：从“根据用户健康数据生成饮食计划”到“协调供应链中采购、仓储、物流多环节调度”，甚至“为企业设计完整的营销方案”。效率革命：客服Agent将人工响应成本降低60%（ McKinsey 2024）；体验升级：金融投顾Agent让用户投资决策时间从2小时缩短至15分钟（J

2048 AI社区

《火速收藏实用干货！提示工程架构师AI与提示设计跨行业应用的实用干货收藏》

关键：用“清单/步骤/表格”等结构化格式，让输出更符合你的使用场景。开头用“场景化短句”（比如“早八人救星！”）；中间用“卖点+场景”的结构（比如“0糖0卡无负担，早上赶地铁塞一瓶，3分钟搞定提神早餐”）；结尾加emoji和引导语。提示工程的本质是“用结构化语言传递需求”——TCFE架构是所有高效prompt的底层框架；跨行业提示设计的关键是“匹配行业需求与模型能力”——不同行业有不同的约束和格式

2048 AI社区

如何判定AI给出的模型是否正确？

针对赛中，无指导老师、无丰富的参赛经验、无模型基础的情况，其实我们需要做的就是判定模型是否适合于该题目、使用的模型是否完备。因此，我们赛中可以通过网上资料或者AI学习设计的三四个模型的适用范围、模型缺陷、模型原理即可。尤其是对于参赛学生而言，更是无法直接判定输出模型的正确性，比较建议可以同时尝试多个AI输出模型，选择公认可以使用的模型；具体的，我将常见模型分为数据预处理、时序预测、分类、评价、优化