【运筹学】对偶理论 : 对偶问题引入 ( 生产产品线性规划 | 设备租赁线性规划 | 对偶问题引入 )

韩曙亮

发布于 2023-03-28 16:32:08

7410

发布于 2023-03-28 16:32:08

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

文章目录

一、工厂生产产品模型

工厂生产甲 , 乙两种产品 ;

生产每种产品 , 都需要使用

4

种设备按照

A , B , C , D

顺序进行加工 ;

产品 / 设备	A A A	B B B	C C C	D D D	利润 ( 元 / 件 )
甲	2 2 2	1 1 1	4 4 4	0 0 0	2 2 2
乙	2 2 2	2 2 2	0 0 0	4 4 4	3 3 3
设备可用时间 ( 小时 )	12 12 12	8 8 8	16 16 16	12 12 12

A

B

C

D

利润 ( 元 / 件 )甲

2

1

4

0

2

乙

2

0

4

3

设备可用时间 ( 小时 )

12

8

16

12

生产甲产品 , 每件产品利润

2

元 , 需要按顺序使用设备如下 :

A

设备

2

小时

B

设备

1

小时

C

设备

4

小时

D

设备

0

小时

生产乙产品 , 每件产品利润

3

元 , 需要按顺序使用设备如下 :

A

设备

2

小时

B

设备

2

小时

C

设备

0

小时

D

设备

4

小时

二、问题一 : 生产利润最大化

充分利用上述

4

台设备 , 生产甲乙产品 , 各多少件 , 能获得最大利润 ;

决策变量 : 设甲产品生产

x_1

件 , 乙产品生产

x_2

件 ;

目标函数 : 最终目的是获得利润 , 引入目标函数是利润总和 , 甲产品的利润为

2x_1

, 以产品的利润为

3x_2

, 最终目标函数为 :

maxZ = 2x_1 + 3x_2

;

约束方程 :

设备

1

的约束方程 : 设备

1

的使用时长 , 不能超过

12

小时 , 甲产品需要使用设备

1

两个小时 , 乙产品需要使用设备

1

两个小时 , 生成约束方程

2x_1 + 2x_2 \leq 12

;

设备

2

的约束方程 : 设备

2

的使用时长 , 不能超过

8

小时 , 甲产品需要使用设备

2

一个小时 , 乙产品需要使用设备

2

两个小时 , 生成约束方程

x_1 + 2x_2 \leq 8

;

设备

3

的约束方程 : 设备

3

的使用时长 , 不能超过

16

小时 , 甲产品需要使用设备

3

四个小时 , 乙产品不需要使用设备

3

, 生成约束方程

4x_1 \leq 16

;

设备

4

的约束方程 : 设备

4

的使用时长 , 不能超过

12

小时 , 甲产品不需要使用设备

4

, 乙产品需要使用设备

4

四个小时 , 生成约束方程

4x_2 \leq 12

;

变量约束 : 产品

1

和产品

2

的个数必须是大于等于

0

, 肯定没有负数 ;

x_1 \geq 0 , x_2 \geq 0

最终生成的线性规划数学模型为 :

\begin{array}{lcl} maxZ = 2x_1 + 3x_2 \\ \\ s.t\begin{cases} 2x_1 + 2x_2 \leq 12 \\\\ x_1 + 2x_2 \leq 8 \\\\ 4x_1 \leq 16 \\\\ 4x_2 \leq 12 \\ \\x_j \geq 0 & (j = 1 , 2 ) \end{cases}\end{array}

三、问题二 : 设备出租问题

如果不生产甲乙两种产品 , 转而出租设备 , 制定四种机器的最佳出租价格 ;

隐含条件 :

不吃亏原则 : 出租设备的利润 , 不能低于生产产品的利润 ;
竞争原则 : 在不吃亏的基础上 , 尽量降低机器的总收费 , 提高市场竞争力 ;

企业拥有的资源是

A

设备

12

小时可用时间

B

设备

8

小时可用时间

C

设备

16

小时可用时间

D

设备

12

小时可用时间

决策变量 : 将上述设备出租 , 四种设备 , 每种设备都有一个租赁价格 , 分别是

y_1 , y_2 , y_3 , y_4

, 单位是元 / 小时 ;

约束方程分析 :

产品甲利润约束 : 四种设备的租赁价格 , 不能低于生产甲产品带来的利润 , 如果生产产品甲 , 需要使用

A

设备

2

小时 ,

B

设备

1

小时 ,

C

设备

4

小时 ,

D

设备

0

小时 , 四种设备的租赁价格是

2y_1 + y_2 + 4y_3 + 0y_4

, 该租赁价格总和不能少于

2

, 因此有约束方程 :

2y_1 + y_2 + 4y_3 + 0y_4 \geq 2

产品已利润约束 : 四种设备的租赁价格 , 不能低于生产甲产品带来的利润 , 如果生产产品乙 , 需要使用

A

设备

2

小时 ,

B

设备

2

小时 ,

C

设备

0

小时 ,

D

设备

4

小时 , 四种设备的租赁价格是

2y_1 + 2y_2 + 0y_3 + 4y_4

, 该租赁价格总和不能少于

3

, 因此有约束方程 :

2y_1 + 2y_2 + 0y_3 + 4y_4 \geq 3

变量约束 : 四种设备的租赁价格必须是大于等于

0

, 肯定没有负数 ;

y_i \geq 0 \quad ( i = 1, 2, 3, 4 )

目标函数 : 根据竞争原则 , 设备的租赁价格在不吃亏的前提下 , 尽量最低 , 这里需要求租赁价格的最小值 :

min W = 12 y_1 + 8y_2 + 16y_3 + 12y_4

, 求最大值没有任何意义 , 该租赁价格可以无限大 ;

线性规划模型为 :

\begin{array}{lcl} min W = 12 y_1 + 8y_2 + 16y_3 + 12y_4 \\ \\ s.t\begin{cases} 2y_1 + y_2 + 4y_3 + 0y_4 \geq 2 \\\\ 2y_1 + 2y_2 + 0y_3 + 4y_4 \geq 3 \\ \\y_j \geq 0 & (j = 1 , 2 , 3, 4 ) \end{cases}\end{array}

四、对偶问题引入

上述问题从不同角度出发 , 得到了两个线性规划 :

生产利润最大化线性规划模型 : 有

2

个变量 ,

4

个约束条件 , 目标函数求最大值 ;

设备租赁线性规划模型 : 有

4

个变量 ,

2

个约束条件 , 目标函数求最小值 ;

两个线性规划之间的对比 :

生产利润最大化线性性规划模型 中的

x_1

系数是

\begin{pmatrix} \quad 2 \quad \\\\ \quad 1 \quad \\\\ \quad 4 \quad \\\\ \quad 0 \quad \end{pmatrix}

, 对应 设备租赁线性规划模型 中的约束方程

2y_1 + y_2 + 4y_3 + 0y_4 \geq 2

系数 ;

生产利润最大化线性性规划模型 中的

x_2

系数是

\begin{pmatrix} \quad 2 \quad \\\\ \quad 2 \quad \\\\ \quad 0 \quad \\\\ \quad 4 \quad \end{pmatrix}

, 对应 设备租赁线性规划模型 中的约束方程

2y_1 + 2y_2 + 0y_3 + 4y_4 \geq 3

系数 ;

生产利润最大化线性性规划模型 中的约束方程右侧的常数是

\begin{pmatrix} \quad 12 \quad \\\\ \quad 8 \quad \\\\ \quad 16 \quad \\\\ \quad 12 \quad \end{pmatrix}

, 对应 设备租赁线性规划模型 中的目标函数

min W = 12 y_1 + 8y_2 + 16y_3 + 12y_4

系数 ;

生产利润最大化线性性规划模型 中的目标函数系数

maxZ = 2x_1 + 3x_2

, 对应 设备租赁线性规划模型 中的约束方程右侧的常数

\begin{pmatrix} \quad 2 \quad \\\\ \quad 3 \quad \end{pmatrix}

;

两个线性规划之间有上述特征 , 称这两个线性规划问题是对偶问题 ;

生产利润最大化线性性规划模型是原问题 , 记作

LP

, 设备租赁线性规划模型是原问题的对偶问题 , 记作

DP

; 这两个问题之间是有一定联系的 ;

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

原始发表：2020-07-31，如有侵权请联系 cloudcommunity@tencent.com 删除

变量

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

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

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

登录后参与评论

0 条评论

热度