单纯形法例题

单纯形法例题

单纯形法例题

1、 例1、目标函数 max z=2𝒙𝟏+3𝒙𝟐

约束条件：{ 𝒙𝟏+𝟐𝒙𝟐≤𝟖𝟒𝒙𝟏≤𝟏𝟔𝟒𝒙𝟐≤𝟏𝟐𝒙𝟏，𝒙𝟏≥𝟎}

解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量，𝒙𝟑，𝒙𝟒，𝒙𝟓，并且它们都大于等于𝟎.得到的标准形式为：

max z=2𝒙𝟏+3𝒙𝟐+

0𝒙𝟑+0𝒙𝟒+0𝒙𝟓

{ 𝒙𝟏+𝟐𝒙𝟐+𝒙𝟑＝𝟖𝟒𝒙𝟏+𝒙𝟒=𝟏𝟔𝟒𝒙𝟐+𝒙𝟓＝𝟏𝟐𝒙𝟏，𝒙𝟐，𝒙𝟑，𝒙𝟒，𝒙𝟓≥𝟎}

然后要将其初始的单纯形表画出来：

𝒄𝒋 2 3 0 0 0 𝜽𝒊 𝑪𝑩 𝑿𝑩 b 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓

0 𝒙𝟑 8 1 2 1 0 0 4

0 𝒙𝟒 16 4 0 0 1 0 -

0 𝒙𝟓 12 0 [𝟒] 0 0 1 3

𝒄𝒋−𝒛𝒋 2 3 0 0 0

由初始单纯形表可以看出，𝒙𝟐为换入变量， 𝒄𝒋−𝒛𝒋 2 0 0 0 -3/4

由于在检验数中仍然存在大于等于0的数，而且P1，P5的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1，换入变量为𝒙𝟏，换出变量为𝒙𝟑，故得到的单纯形表如下：

𝒄𝒋 2 3 0 0 0 𝜽𝒊 𝑪𝑩 𝑿𝑩 b 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓

2 𝒙𝟏 2 1 0 1 0 -1/2 -

0 𝒙𝟒 8 0 0 -4 1 [𝟐] 4

3 𝒙𝟐 3 0 1 0 0 1/4

12

𝒄𝒋−𝒛𝒋 0 0 -2 0 1/4

由于检验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代(换入变量为𝒙𝟓，换出变量为𝒙𝟒：得到单纯形表如下：

𝒄𝒋 2 3 0 0 0 𝜽𝒊 𝑪𝑩 𝑿𝑩 b 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓

2 𝒙𝟏 4 1 0 0 1/4 0

0 𝒙𝟓 4 0 0 -2 1/2 1

3 𝒙𝟐 2 0 1 1/2 -1/8 0

𝒄𝒋−𝒛𝒋 0 0 -3/2 -1/8 0

此时可以发现检验数中没有大于0的数，表明已经得到了最优解，所以最优解是：

（4,2,0,0,4），故目标函数值z=2*4+2*3=14

2、 合理利用线材问题，现在要做100套钢架，每套用长为2.9m，2.1m，和1.5m的钢各一根，已知原料长7.4m，问应如何下料，使用的原材料最省；

解：首先我们必须要清楚该问题的需要设立的变量是什么。我们分析一下问题，做100套钢架，需要2.9m长的钢100根，2.1m的钢100根，1.5m的钢100根。而一份原料长度是7.4m，它的截取的方法有多少种，我们可以用表格列举出来：

长度/m

下料根数

截取方案

1 2 3 4 5

2.9 1 1 2

2.1 2 1 2

1.5 3 1 3 2

所用长7.4 7.1 7.3 6.6 7.2

度

剩余长度 0 0.3 0.1 0.8 0.2

求解的问题是关于如何去进行下料，使得原材料最省，也就是说如何搭配使用这些方案，使得剩余的总长度最少。由此，我们可以将目标函数和约束条件表述出来：

目标函数：min

z=0.3𝒙𝟐+0.1𝒙𝟑+0.8𝒙𝟒+0.2𝒙𝟓

约束条件{ 𝒙𝟏+𝒙𝟐+𝟐𝒙𝟑=𝟏𝟎𝟎𝟐𝒙𝟐+𝒙𝟒+𝟐𝒙𝟓=𝟏𝟎𝟎𝟑𝒙𝟏+𝒙𝟑+𝟑𝒙𝟒+𝟐𝒙𝟓=𝟏𝟎𝟎𝒙𝟏，𝒙𝟐，𝒙𝟑，𝒙𝟒，𝒙𝟓≥𝟎}

首先可以写出线性方程组的矩阵形式：[𝟏𝟏𝟐𝟎𝟎𝟎𝟐𝟎𝟏𝟐𝟑𝟎𝟏𝟑𝟐]发现不存在单位矩阵，所以要采用人造基的方式，也就是要添加人工变量：𝒙𝟔，𝒙𝟕，𝒙𝟖，那么线性方程组可以表示为：

{ 𝒙𝟏+𝒙𝟐+𝟐𝒙𝟑+𝒙𝟔=𝟏𝟎𝟎𝟐𝒙𝟐+𝒙𝟒+𝟐𝒙𝟓+𝒙𝟕=𝟏𝟎𝟎𝟑𝒙𝟏+𝒙𝟑+𝟑𝒙𝟒+𝟐𝒙𝟓+𝒙𝟖=𝟏𝟎𝟎𝒙𝟏，𝒙𝟐，𝒙𝟑，𝒙𝟒，𝒙𝟓，𝒙𝟔，𝒙𝟕，𝒙𝟖≥𝟎}

，目标函数可以表示为：min

z=𝟎𝒙𝟏+0.3𝒙𝟐+0.1𝒙𝟑+0.8𝒙𝟒+0.2𝒙𝟓+M𝒙𝟔+𝑴𝒙𝟕+𝑴𝒙𝟖

转换为求目标最大化max

Z=−𝟎𝒙𝟏−0.3𝒙𝟐−0.1𝒙𝟑−0.8𝒙𝟒−0.2𝒙𝟓−M𝒙𝟔−𝑴𝒙𝟕−𝑴𝒙𝟖

然后列出初始单纯形表：(注意，加入人工变量之后，它所对应的系数为-M，而非0)

𝒄𝒋 0 -0.3 -0.1 -0.8 -0.2 -M -M -M 𝜽𝒊

𝑪𝑩 𝑿𝑩 b 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔 𝒙𝟕 𝒙𝟖

-M 𝒙𝟔 100 1 1 2 0 0 1 0 0 100

-M 𝒙𝟕 100 0 2 0 1 2 0 1 0

-

-𝒙𝟖 1[𝟑] 0 1 3 2 0 0 1 10

M 00 0/3

𝒄𝒋−𝒛𝒋 4M -0.3+3M -0.1+3M -0.8+4M -0.2+4M 0 0 0

换入变量为𝒙𝟏，换出变量为𝒙𝟖，得到单纯形表为：

𝒄𝒋 0 -0.3 -0.1 -0.8 -0.2 -M -M -M 𝜽𝒊

𝑪𝑩 𝑿𝑩 b 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔 𝒙𝟕 𝒙𝟖

-M 𝒙𝟔 200/3 0 1 5/3 -1 -2/3 1 0 -1/3 200/3

-M 𝒙𝟕 100 0 [𝟐] 0 1 2 0 1 0 100/2

0 𝒙𝟏 100/3 1 0 1/3 1 2/3 0 0 1/3 -

𝒄𝒋−𝒛𝒋 0 -0.-0.--0.0 0 -

3+3M 1+5/3M 0.8 2+4/3M 4/3M

换入变量为𝒙𝟐，换出变量为𝒙𝟕，得到的单纯形表为：

𝒄𝒋 0 -0.3 -0.1 -0.8 -0.2 -M -M -M 𝜽𝒊

𝑪𝑩 𝑿𝑩 b 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔 𝒙𝟕 𝒙𝟖

-M 𝒙𝟔 50/3 0 0 5/3 -3/2 -5/3 1 -1/2 -1/3 10

-0.3 𝒙𝟐 50 0 1 0 1/2 1 0 1/2 0

-

0 𝒙𝟏 100/3 1 0 1/3 1 2/3 0 0 1/3 -100

𝒄𝒋−𝒛𝒋 0 0 -0.1+5/3M -0.65-3/2M 0.1-5/3M 0 0.15-3/2M -4/3M

换入变量为𝒙𝟑，换出变量为𝒙𝟔，得到的单纯形表为：

𝒄𝒋 0 -0.3 -0.1 -0.8 -0.2 -M -M -M 𝜽𝒊

𝑪𝑩 𝑿𝑩 b 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔 𝒙𝟕 𝒙𝟖

-0.1 𝒙𝟑 10 0 0 1 -9/10 -1 3/5 -3/10 -1/5

-𝒙𝟐 50 0 1 0 1/1 0 1/0

0.3 2 2

0 𝒙𝟏 30 1 0 0 13/10 1 -1/5 1/10 2/5

𝒄𝒋−𝒛𝒋 0 0 0 -0.74 0 -M+0.06 -M+0.12 -M-0.02

所以，最优解为：（30,50,10，0,0,0,0,0）。也就是说最优的下料方案为：按照第一个方案下料30根，第二种方案下料50根，按照第三种方案下料10根。即需要90根原材料可以制造出100套钢架。

3、 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下表：

班次 时间 所需人数

1 6:00-10:00 60

2 10:00-14:00 70

3 14:00-18:00 60

4 18:00-22:00 50

5 22:00-2:00 20

6 2:00-6:00 30

设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八个小时，问该公交线路至少配备多少名司机和乘务人员，列出这个问题的线性规划模型。

解：

目标函数：min z=𝒙𝟏+𝒙𝟐+𝒙𝟑+𝒙𝟒+𝒙𝟓+𝒙𝟔

约束条件:{ 𝒙𝟏+𝒙𝟔≥𝟔𝟎𝒙𝟏+𝒙𝟐≥𝟕𝟎𝒙𝟐+𝒙𝟑≥𝟔𝟎𝒙𝟑+𝒙𝟒≥𝟓𝟎𝒙𝟒+𝒙𝟓≥𝟐𝟎𝒙𝟓+𝒙𝟔≥𝟑𝟎𝒙𝟏，𝒙𝟐，𝒙𝟑，𝒙𝟒，𝒙𝟓，𝒙𝟔≥𝟎}

4、 利用单纯形算法求解线性规划问题

目标函数为：Max Z=4𝒙𝟏+3𝒙𝟐

约束条件为：{𝟐𝒙𝟏+𝟐𝒙𝟐≤𝟏𝟔𝟎𝟎𝟓𝒙𝟏+𝟐.𝟓𝒙𝟐≤𝟐𝟓𝟎𝟎𝒙𝟏≤𝟒𝟎𝟎𝒙𝟏,𝒙𝟐≥𝟎 }

解：首先将线性方程组化为标准形式：添加松弛变量：𝒙𝟑，𝒙𝟒，𝒙𝟓，得到的方程式为：

目标函数：Max Z=4𝒙𝟏+3𝒙𝟐+0𝒙𝟑+0𝒙𝟒+0𝒙𝟓

约束条件为：{𝟐𝒙𝟏+𝟐𝒙𝟐+ 𝒙𝟑=𝟏𝟔𝟎𝟎𝟓𝒙𝟏+𝟐.𝟓𝒙𝟐+𝒙𝟒=𝟐𝟓𝟎𝟎𝒙𝟏+𝒙𝟓 =𝟒𝟎𝟎𝒙𝟏,𝒙𝟐,𝒙𝟑,𝒙𝟒,𝒙𝟓≥𝟎 }

接着将初始单纯形表列出：

𝒄𝒋 4 3 0 0 0 𝜽𝒊 𝑪𝑩 𝑿𝑩 b 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓