Lecture on Linear Programming 1

规划问题的数学模型三要素

1. 决策变量
2. 目标函数
3. 约束条件

线性规划

1. 定义

1. 目标函数式决策变量的线性函数
2. 约束条件是决策变量的线性不等式或线性等式

2. 标准型

$max{c}^{T}xmax\backslash \; c^Tx$

$s\mathrm{.}t\mathrm{.}Ax=bs.t.\backslash \; Ax=b$

$x\ge 0x\backslash geq\; 0$

1. 极大化目标
2. 全部约束为等式约束，且右端为非负
3. 决策变量非负

3. 转换成标准型的操作

1. 不等约束的转换：
   • 加松弛变量
   • 减剩余变量
   • 松弛变量和剩余变量在目标函数中的系数为0
2. 乘负号操作
   • min2max
   • 变量为负
   • b为负
3. 无约束变量的双替换