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

韩曙亮

发布于 2023-03-27 17:26:26

9530

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

I . 规划问题

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

线性规划问题 :

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

II . 线性规划示例

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

	设备 A	设备 B	设备 C	设备 D	利润
产品甲	2	1	4	0	2
产品乙	2	2	0	4	3
设备有效台时	12	8	16	12

线性规划分析 : 1.

x_1

是产品甲的生产数量 ,

x_2

是产品乙的生产数量 ;

2. 利润 : 甲乙两种产品的利润之和 , 产品甲 2 元 , 产品乙 3 元 , 利润要达到最大化 ;

max Z = 2x_1 + 3x_2

3. 设备

的限制 : 设备

最多使用 12 小时 , 两种产品的使用时间不能超过 12 小时 ;

2x_1 + 2x_2 \leq 12

4. 设备

的限制 : 设备

最多使用 8 小时 ;

x_1 + 2x_2 \leq 8

5. 设备

的限制 : 设备

最多使用 16 小时 ;

4x_1 \leq 16

6. 设备

的限制 : 设备

最多使用 12 小时 ;

4x_2 \leq 12

7. 甲乙两种产品数量的限制 , 两个产品的数量必须大于等于 0 ;

x_1 \geq 0 , x_2 \geq 0

按照上述条件 , 计算出

的最大值 , 就是生产甲乙两种产品的最大利润 ;

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

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

( 1 ) 决策变量 : 上述产品甲乙的个数

x_1 , x_2

就是决策变量 , 直接关系到利润的多少 ;

( 2 ) 目标条件 : 多个决策变量的线性函数 , 通常是求最大值或最小值问题 ; 上述示例中的

max Z = 2x_1 + 3x_2

就是目标条件 ;

( 3 ) 约束条件 : 一组多个决策变量的线性等式或不等式组成 , 如上述 3 ~ 7 的四种设备的使用时间限制和决策变量的取值范围 ;

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

目标函数 :

max (min) z = c_1x_1 + c_2x_2 + \cdots + c_nx_n

约束条件 :

\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}

上述线性规划中 , 有

个决策变量 ,

个约束条件不等式 ;

简写形式 : 有

个变量 ,

个约束不等式 ;

\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}

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

向量形式 :

max ( min ) z = CX

\begin{cases} \sum p_j x_j \leq ( = \cdot \geq ) B\\ \\ X \geq 0 \end{cases}

公式相关说明 :

1. 矩阵

是

行

列矩阵 , 是一个

1 \times n

矩阵 ; 该矩阵的元素是目标条件中决策变量的系数 ;

C = \begin{bmatrix} c_1 , c_2 \cdots c_n\end{bmatrix}

2. 矩阵

是

行

列的矩阵 , 是一个

n \times 1

矩阵 ; 该矩阵的元素是决策变量 ;

X = \begin{bmatrix}x_1 \\ \vdots \\ x_n \end{bmatrix}

3. 矩阵

P_j

是

行

列的矩阵 , 是一个

m \times 1

矩阵 ; 该矩阵的元素是第

个约束条件的

个决策变量前的系数 ;

P_j = \begin{bmatrix}a_{1j} \\ \vdots \\ a_{mj} \end{bmatrix}

4. 矩阵

是

行

列的矩阵 , 是一个

m \times 1

矩阵 ; 该矩阵的元素是第

个约束条件的

个右侧的不等式约束值 ;

B = \begin{bmatrix}b_{1} \\ \vdots \\ b_{m} \end{bmatrix}

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

矩阵形式 :

max ( min ) Z = CX

\begin{cases} \sum AX \leq ( = \cdot \geq ) B\\ \\ X \geq 0 \end{cases}

公式相关说明 :

1. 矩阵

是

行

列矩阵 , 是一个

1 \times n

矩阵 ; 该矩阵的元素是目标条件中决策变量的系数 ;

C = \begin{bmatrix} c_1 , c_2 \cdots c_n\end{bmatrix}

2. 矩阵

是

行

列的矩阵 , 是一个

n \times 1

矩阵 ; 该矩阵的元素是决策变量 ;

X = \begin{bmatrix}x_1 \\ \vdots \\ x_n \end{bmatrix}

3. 矩阵

是

行

列的矩阵 , 是一个

m \times n

矩阵 ; 该矩阵的

行

列元素代表第

个约束条件的

个决策变量前的系数 ;

A = \begin{bmatrix} &a_{11} & \cdots & a_{1n} & \\ &\vdots & \vdots & \vdots & \\ &a_{mj}& \cdots & a_{mn} \end{bmatrix}

4. 矩阵

是

行

列的矩阵 , 是一个

m \times 1

矩阵 ; 该矩阵的元素是第

个约束条件的

个右侧的不等式约束值 ;

B = \begin{bmatrix}b_{1} \\ \vdots \\ b_{m} \end{bmatrix}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度