【运筹学】线性规划数学模型 ( 三要素 | 一般形式 | 向量形式 | 矩阵形式 )

I . 规划问题

规划问题 概念 : 在 生产 和 经营管理中 , 合理地 安排 人力 , 物力 , 资源 , 使它们能够得到充分利用 , 以达到获得最大的效益 ;

线性规划问题 :

• ① 减小资源消耗 : 任务 和 目标确定 , 统筹兼顾 , 合理安排 , 用最少的资源完成上述任务和目标 ; 资源包括 资金 设备 原料 人力 时间 等 ;
• ② 获得最大效益 : 资源是固定的 , 进行合理安排 , 获得最大的效益 ;

II . 线性规划示例

某工厂生产 甲 , 乙 两种产品 , 分别要使用 A , B , C , D 四种设备进行加工 , 按照工艺流程规定 , 每种产品 在不同设备上加工所需的时间如下表所示 , 如何安排生产 , 使总利润最大 ;

设备 A设备 B设备 C设备 D利润产品甲21402产品乙22043设备有效台时1281612

线性规划分析 : 1. x 1 x_1 x1​ 是产品甲的生产数量 , x 2 x_2 x2​ 是产品乙的生产数量 ;

2. 利润 : 甲乙两种产品的利润之和 , 产品甲 2 元 , 产品乙 3 元 , 利润要达到最大化 ; m a x Z = 2 x 1 + 3 x 2 max Z = 2x_1 + 3x_2 maxZ=2x1​+3x2​

3. 设备 A A A 的限制 : 设备 A A A 最多使用 12 小时 , 两种产品的使用时间不能超过 12 小时 ; 2 x 1 + 2 x 2 ≤ 12 2x_1 + 2x_2 \leq 12 2x1​+2x2​≤12

4. 设备 B B B 的限制 : 设备 B B B 最多使用 8 小时 ; x 1 + 2 x 2 ≤ 8 x_1 + 2x_2 \leq 8 x1​+2x2​≤8

5. 设备 C C C 的限制 : 设备 C C C 最多使用 16 小时 ; 4 x 1 ≤ 16 4x_1 \leq 16 4x1​≤16

6. 设备 D D D 的限制 : 设备 D D D 最多使用 12 小时 ; 4 x 2 ≤ 12 4x_2 \leq 12 4x2​≤12

7. 甲乙两种产品数量的限制 , 两个产品的数量必须大于等于 0 ; x 1 ≥ 0 , x 2 ≥ 0 x_1 \geq 0 , x_2 \geq 0 x1​≥0,x2​≥0

按照上述条件 , 计算出 Z Z Z 的最大值 , 就是生产甲乙两种产品的最大利润 ;

III . 线性规划数学模型三要素

线性规划数学模型三要素 :

• ( 1 ) 决策变量 : 上述 产品甲乙 的个数 x 1 , x 2 x_1 , x_2 x1​,x2​ 就是决策变量 , 直接关系到利润的多少 ;
• ( 2 ) 目标条件 : 多个决策变量的线性函数 , 通常是求 最大值 或 最小值 问题 ; 上述示例中的 m a x Z = 2 x 1 + 3 x 2 max Z = 2x_1 + 3x_2 maxZ=2x1​+3x2​ 就是目标条件 ;
• ( 3 ) 约束条件 : 一组多个 决策变量 的线性等式 或 不等式 组成 , 如上述 3 ~ 7 的四种设备的使用时间限制 和 决策变量的取值范围 ;

IV . 线性规划数学模型一般形式

目标函数 : m a x ( m i n ) z = c 1 x 1 + c 2 x 2 + ⋯ + c n x n max (min) z = c_1x_1 + c_2x_2 + \cdots + c_nx_n max(min)z=c1​x1​+c2​x2​+⋯+cn​xn​

约束条件 :

{ a 11 x 1 + a 12 x 2 + ⋯ a 1 n x n ≤ ( = ⋅ ≥ ) b 1 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ a m n x n ≤ ( = ⋅ ≥ ) b m x 1 ≥ 0 ⋯ x 2 ≥ 0 \begin{cases}a_{11}x_1 + a_{12}x_2 + \cdots a_{1n}x_n & \leq ( = \cdot \geq) & b_1\\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots a_{mn}x_n & \leq ( = \cdot \geq) & b_m \\ \\ \\x_1 \geq 0 \cdots x_2 \geq 0 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​a11​x1​+a12​x2​+⋯a1n​xn​⋮am1​x1​+am2​x2​+⋯amn​xn​x1​≥0⋯x2​≥0​≤(=⋅≥)≤(=⋅≥)b1​bm​

上述线性规划中 , 有 n n n 个决策变量 , m m m 个约束条件不等式 ;

简写形式 : 有 n n n 个变量 , m m m 个约束不等式 ;

m a x ( m i n ) z = ∑ j = 1 n c j x j ∑ j = 1 n a i j x j ≤ ( = ⋅ ≥ ) b i ( i = 1 , 2 ⋯ m ) x j ≥ 0 ( i = 1 , 2 ⋯ n ) \begin{array}{lcl}max (min) z = \sum_{j=1}^{n}c_j x_j\\ \\ \sum_{j=1}^{n} a_{ij}x_j \leq ( = \cdot \geq) b_i & (i = 1 , 2 \cdots m) \\ \\x_j \geq 0 & (i = 1 , 2 \cdots n) \end{array} max(min)z=∑j=1n​cj​xj​∑j=1n​aij​xj​≤(=⋅≥)bi​xj​≥0​(i=1,2⋯m)(i=1,2⋯n)​

V . 线性规划数学模型向量形式

向量形式 :

m a x ( m i n ) z = C X max ( min ) z = CX max(min)z=CX { ∑ p j x j ≤ ( = ⋅ ≥ ) B X ≥ 0 \begin{cases} \sum p_j x_j \leq ( = \cdot \geq ) B\\ \\ X \geq 0 \end{cases} ⎩⎪⎨⎪⎧​∑pj​xj​≤(=⋅≥)BX≥0​

公式相关说明 :

1. 矩阵 C C C 是 1 1 1 行 n n n 列矩阵 , 是一个 1 × n 1 \times n 1×n 矩阵 ; 该矩阵的元素是 目标条件中 决策变量的系数 ; C = [ c 1 , c 2 ⋯ c n ] C = \begin{bmatrix} c_1 , c_2 \cdots c_n\end{bmatrix} C=[c1​,c2​⋯cn​​]

2. 矩阵 X X X 是 n n n 行 1 1 1 列 的矩阵 , 是一个 n × 1 n \times 1 n×1 矩阵 ; 该矩阵的元素是决策变量 ;

X = [ x 1 ⋮ x n ] X = \begin{bmatrix}x_1 \\ \vdots \\ x_n \end{bmatrix} X=⎣⎢⎡​x1​⋮xn​​⎦⎥⎤​

3. 矩阵 P j P_j Pj​ 是 m m m 行 1 1 1 列 的矩阵 , 是一个 m × 1 m \times 1 m×1 矩阵 ; 该矩阵的元素是 第 j j j 个约束条件的 m m m 个决策变量前的系数 ;

P j = [ a 1 j ⋮ a m j ] P_j = \begin{bmatrix}a_{1j} \\ \vdots \\ a_{mj} \end{bmatrix} Pj​=⎣⎢⎡​a1j​⋮amj​​⎦⎥⎤​

4. 矩阵 B B B 是 m m m 行 1 1 1 列 的矩阵 , 是一个 m × 1 m \times 1 m×1 矩阵 ; 该矩阵的元素是 第 j j j 个约束条件的 m m m 个 右侧的不等式约束值 ;

B = [ b 1 ⋮ b m ] B = \begin{bmatrix}b_{1} \\ \vdots \\ b_{m} \end{bmatrix} B=⎣⎢⎡​b1​⋮bm​​⎦⎥⎤​

VI 线性规划数学模型矩阵形式

矩阵形式 :

m a x ( m i n ) Z = C X max ( min ) Z = CX max(min)Z=CX { ∑ A X ≤ ( = ⋅ ≥ ) B X ≥ 0 \begin{cases} \sum AX \leq ( = \cdot \geq ) B\\ \\ X \geq 0 \end{cases} ⎩⎪⎨⎪⎧​∑AX≤(=⋅≥)BX≥0​

公式相关说明 :

1. 矩阵 C C C 是 1 1 1 行 n n n 列矩阵 , 是一个 1 × n 1 \times n 1×n 矩阵 ; 该矩阵的元素是 目标条件中 决策变量的系数 ; C = [ c 1 , c 2 ⋯ c n ] C = \begin{bmatrix} c_1 , c_2 \cdots c_n\end{bmatrix} C=[c1​,c2​⋯cn​​]

2. 矩阵 X X X 是 n n n 行 1 1 1 列 的矩阵 , 是一个 n × 1 n \times 1 n×1 矩阵 ; 该矩阵的元素是决策变量 ;

X = [ x 1 ⋮ x n ] X = \begin{bmatrix}x_1 \\ \vdots \\ x_n \end{bmatrix} X=⎣⎢⎡​x1​⋮xn​​⎦⎥⎤​

3. 矩阵 A A A 是 m m m 行 n n n 列 的矩阵 , 是一个 m × n m \times n m×n 矩阵 ; 该矩阵的 i i i 行 j j j 列 元素 代表 第 i i i 个约束条件的 j j j 个决策变量前的系数 ;

A = [ a 11 ⋯ a 1 n ⋮ ⋮ ⋮ a m j ⋯ a m n ] A = \begin{bmatrix} &a_{11} & \cdots & a_{1n} & \\ &\vdots & \vdots & \vdots & \\ &a_{mj}& \cdots & a_{mn} \end{bmatrix} A=⎣⎢⎡​​a11​⋮amj​​⋯⋮⋯​a1n​⋮amn​​​⎦⎥⎤​

4. 矩阵 B B B 是 m m m 行 1 1 1 列 的矩阵 , 是一个 m × 1 m \times 1 m×1 矩阵 ; 该矩阵的元素是 第 j j j 个约束条件的 m m m 个 右侧的不等式约束值 ;

B = [ b 1 ⋮ b m ] B = \begin{bmatrix}b_{1} \\ \vdots \\ b_{m} \end{bmatrix} B=⎣⎢⎡​b1​⋮bm​​⎦⎥⎤​