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

2023-03-27 17:26:26 浏览数 (1)

文章目录

  • I . 规划问题
  • II . 线性规划示例
  • III . 线性规划数学模型三要素
  • IV . 线性规划数学模型一般形式
  • V . 线性规划数学模型向量形式
  • VI 线性规划数学模型矩阵形式

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. 设备

A

的限制 : 设备

A

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

2x_1 2x_2 leq 12

4. 设备

B

的限制 : 设备

B

最多使用 8 小时 ;

x_1 2x_2 leq 8

5. 设备

C

的限制 : 设备

C

最多使用 16 小时 ;

4x_1 leq 16

6. 设备

D

的限制 : 设备

D

最多使用 12 小时 ;

4x_2 leq 12

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

x_1 geq 0 , x_2 geq 0

按照上述条件 , 计算出

Z

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

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}

上述线性规划中 , 有

n

个决策变量 ,

m

个约束条件不等式 ;

简写形式 : 有

n

个变量 ,

m

个约束不等式 ;

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. 矩阵

C

是

1

行

n

列矩阵 , 是一个

1 times n

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

C = begin{bmatrix} c_1 , c_2 cdots c_nend{bmatrix}

2. 矩阵

X

是

n

行

1

列 的矩阵 , 是一个

n times 1

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

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

3. 矩阵

P_j

是

m

行

1

列 的矩阵 , 是一个

m times 1

矩阵 ; 该矩阵的元素是 第

j

个约束条件的

m

个决策变量前的系数 ;

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

4. 矩阵

B

是

m

行

1

列 的矩阵 , 是一个

m times 1

矩阵 ; 该矩阵的元素是 第

j

个约束条件的

m

个 右侧的不等式约束值 ;

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. 矩阵

C

是

1

行

n

列矩阵 , 是一个

1 times n

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

C = begin{bmatrix} c_1 , c_2 cdots c_nend{bmatrix}

2. 矩阵

X

是

n

行

1

列 的矩阵 , 是一个

n times 1

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

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

3. 矩阵

A

是

m

行

n

列 的矩阵 , 是一个

m times n

矩阵 ; 该矩阵的

i

行

j

列 元素 代表 第

i

个约束条件的

j

个决策变量前的系数 ;

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

4. 矩阵

B

是

m

行

1

列 的矩阵 , 是一个

m times 1

矩阵 ; 该矩阵的元素是 第

j

个约束条件的

m

个 右侧的不等式约束值 ;

B = begin{bmatrix}b_{1} \ vdots \ b_{m} end{bmatrix}
vi 变量 产品 管理 函数

0 人点赞