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

2023-03-28 16:32:08 浏览数 (1)

文章目录

  • 一、工厂生产产品模型
  • 二、问题一 : 生产利润最大化
  • 三、问题二 : 设备出租问题
  • 四、对偶问题引入

一、工厂生产产品模型

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

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

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
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.tbegin{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.tbegin{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

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

变量 产品 函数 基础 模型

0 人点赞