运筹学和仿真的单纯形法

单纯形法的最大优点是其简单性，是一种非常实用的方法，因为它仅适用于目标函数的系数和约束。

我们将通过一个示例来说明其操作，但之前我们将展示决定规则，以确定输入的变量，离开的变量，大M以及如何确定我们处于最佳状态。所有这些决策规则均源自代数方法，仅在此处将它们安排为以要使用的单纯形板类型使用。

单纯形法研究模拟与操作1

限制类型

限制条件

添加了一个松弛变量，目标函数中的成本（或利润）等于0。

Ejm：

2X1-4X2 <= 1，它仍然是：

目标函数中X3的2X1-4X2 + X3 = 1 Cj将为0。

限制³

在目标函数的成本（或利润）等于0的情况下减去一个多余变量，然后根据成本是最大化还是最小化，添加一个成本+ M或–M的人工变量。

Ejm：

2X1 + 3X2> = 1，它仍然是：

2X1 + 3X2-X3 + X4 = 1目标函数中X3的Cj将为0。而X4（人工）的Cj为±M

约束=

根据成本是最大化还是最小化，添加了成本为+ M或–M的人工变量。

Ejm：

2X1 + 3X2 = 8，它仍然是：

目标函数中X3的2X1 + 3X2 + X3 = 8 Cj为±M

此外，还提供以下注意事项：

如果在最优解的单纯形板上，基本变量中至少有一个剩余变量或人工变量，其值> 0，则问题无解，这意味着至少有两个排他性限制，因此没有可行的解决方案领域，而解决方案则更少，在这种情况下，应审查问题的表述，如果在选择出现的变量时，没有一个基本变量会限制选择输入的非基本变量的增长，则问题在于不确定的解决方案和配方应进行审查，以寻找初始配方中未考虑的新限制如果在最优单纯形图中，至少一个非基本变量的函数系数为零（0）目标，这是您的Zj-Cj = 0，该问题有多种解决方案，其中一种正在提供给我们。

例子1

Xi是要生产的产品i的数量。

最大化Z = X1 + X2 {鞋底总增益}

南非

5X1 + 3X2 <= 15 {小时可用深度至}

3X1 + 5X2 <= 15 {小时可用深度 B}

Xj> = 0; j = 1，2

具有所有限制<=且具有非负条件的最大化问题称为标准形式或标准形式

在这里，我们必须使用松弛和/或人工变量来获得可行的基本解决方案，从而使方程组像这样：

最大化Z = X1 + X2

南非

5X1 + 3X2 + X3 = 15

3X1 + 5X2 + X4 = 15

Xj> = 0; j = 1,2,3,4

基本变量是那些其系数构成单位矩阵的变量。

在这种混乱中偶然地是松弛变量X3和X4。

目标函数Z的值在Zj-Cj的框前面，在这种情况下，它的值为零（0），并且通过乘以行向量来计算（在表中，该列是紧接基本变量VB的列））通过独立项b的列向量包含原始目标函数中基本变量的系数

CX _B =当前基本变量的原始目标函数中系数的行向量，其值在电路板的第一列中。

b =约束的独立项的列向量，同时是当前基本变量的值，它们的值在称为b的列下

CX _B =（0.0）; b =（15,15）' Z = CX _B * b =（0）（15）+（0）（15）= 0

通过将行向量CX _B乘以第j个变量的列的指针向量aj减去Cj来计算Zj-Cj的值，即：

Zj-Cj = CX _B. aj-Cj;

计算过程如下：

Z1-C1 = CX _B a1-C1 =（0,0）。（5,3）'-1 =（0）（5）+（0）（3）-1 = -1

Z2-C2 = CX _B a2-C2 =（0,0）。（3,5）'-1 =（0）（3）+（0）（5）-1 = -1

Z3-C3 = CX _B a3-C3 =（0,0）。（1,0）'-0 =（0）（1）+（0）（0）-0 = 0

Z4-C4 = CX _B a4-C4 =（0,0）。（0,1）'-0 =（0）（0）+（0）（1）-0 = 0

下面列出了输出的变量和输入的变量：

j	之一	之一	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
0	X3	十五	5	3	之一	0	15/5 = 3
0	X4	十五	3	5	0	之一	15/3 = 5
Zj-Cj	0	-之一	-之一	0	0

变量输入X1

可变输出X3

Zj-Cj值最大的变量是X1或X2。X1是随机选择的。

在这个迭代中，b / a给出：15/5 = 3和15/3 = 5；

这意味着基本变量X3将输入变量X1的增长限制为3（不允许其取高于3的值），而基本变量X4则将输入变量X1的增长限制为5（不是让我们取高于5的值）。

当然，最限制输入变量X1增长的基本变量是X3，因此，它是选择离开的基本变量。

选择退出的基本变量的行除以该行与输入变量的列的交点处的元素，所得行是数据透视表行，并放置在新板上，枢轴行的倍数以这样的方式添加到前一个板的其他行中，即从每个行中消除选择输入的变量，在我们的情况下，称为X1，此过程称为在交叉点处加一（1）其余的列为零（0），因此单位向量将出现在该列中，该过程在每次迭代中重复进行，直到在最大化或小于最大值的情况下所有Zj-Cj都等于或大于零。或在最小化的情况下等于零。

下面是所有迭代，在每一行中将它们相乘的值相乘以添加到其他行中，这表示为从一行到另一行的倍数。

请注意，将多个约束添加到目标函数以从中消除基本变量。

j	之一	之一	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
之一	X1	3	之一	3/5	1/5	0	5
0	X4	6	0	16/5	-3/5	之一	8/15
Zj-Cj	3	0	-2/5	1/5	0

变量输入X2

可变输出X4

j	之一	之一	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
之一	X1	8/15	之一	0	5/16	0
之一	X2	8/15	0	之一	-3/16	5/16
Zj-Cj	15/4	0	0	1/8	1/8

最佳解决方案：

X1 * = 15/8

X2 * = 15/8

Z * = 15/4

该解决方案是唯一的：X1 * = 15/8; X2 * = 15/8; Z * = 14/4

例子2

最小化 Z = 6X1 + 4X2 + 2X3

南非

6X1 + 2X2 + 6X3> = 6

6X1 + 4X2 = 12

2X1-2X2 <= 2

Xj> = 0; j = 1，2，3

最小化Z = 6X1 + 4X2 + 2X3 + MX5 + MX6

南非

6X1 + 2X2 + 6X3-X4 + X5 = 6

6X1 + 4X2 + X6 = 12

2X1-2X2 + X7 = 2

Xj> = 0; j = 1、2、3、4、5、6、7

基本变量为X5 = 6，X6 = 12，X7 = 2

最佳解决方案：

决策变量：

X1 = 0，X2 = 3，X3 = 0，Z = 12

松弛变量：X4 = 0，X7 = 8

人工变量：X5 = 0，X6 = 0

后优化分析的突破

最大化Z = X1 + X2 {鞋底总增益}

南非

5X1 + 3X2 <= 15 {小时可用深度至}

3X1 + 5X2 <= 15 {小时可用深度 B}

Xj> = 0; j = 1，2

最佳板：

j	之一	之一	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
之一	X1	8/15	之一	0	5/16	0
之一	X2	8/15	0	之一	-3/16	5/16
Zj-Cj	15/4	0	0	1/8	1/8

最佳解决方案：

X1 * = 15/8

X2 * = 15/8

Z * = 15/4

降低成本：

单位=（货币单位）/（产品单位）=（总数量）/（上升）=与Cj相同的单位

双重价格：

单位=（货币单位）/（资源单位）=（um）/（ur）

解释降低的成本：

当生产未生产的产品的单位时，目标功能以多少货币单位恶化。

最小化：（Dz / Dx）最大化：（Ñz/ Dx）

如果该变量是基本变量，则降低的成本为0。如果该变量为非基本变量，则其> =0。当该变量为0时，表示替代解决方案。

双重价格的解释：

目标函数将通过限制资源单位的变化而变化多少货币单位。

大于0时：（Dz / Db）或（Ñz/Ñb）

<0时：（Dz /Ñb）或（Ñz/ Db）

甲约束限制时，它限制了目标函数。当满足约束的相等性时会发生这种情况。

如果约束是非限制性的，则对偶价格为0。

如果约束是限制性的，则可以采用任何正值，负值或0值。

解剖动物

一家填充动物公司正在生产鸽子和鹰。在目前的市场环境下，他可以卖鹰和鸽子，分别获利20美元和12.00美元。

鹰的皮比鸽子的皮更坚韧，需要更多的时间来工作。皮草机每分钟可以处理4头鹰皮，而鸽子则可以处理8皮。灌装线每分钟可灌装5头鹰或4羽鸽子。鹰将在每分钟3.5鹰的喙锐化机中进行最后操作，该部门的工作时间为8小时。

制定解决方案的线性规划模型制定在（a）中求解的模型的对偶问题对模型进行管理解释，通过直接从最优表中读取来确定对偶问题的最优解发现问题c。

除非另有说明，否则以下问题彼此独立，并且以问题的初始陈述为基础。

皮革机，灌装线和磨刀机上可能会加班。在每个部门中每一次加班所获得的最大利润是什么？公司经理参观鹰和鸽子生产线并观察到某些过程中存在闲置产能。他决定下令以该过程的所有中心以其全部已安装容量使用。您会对他说什么？如果每羽鸽子的利润降为/，最佳解决方案将会发生什么。9.00？为了使玩具具有更好的光洁度，已安装了上漆线；上漆线每分钟可同时装满5羽鹰或4羽鸽子，每天工作8小时。它会影响最佳解决方案吗？如果是这样，找到新的解决方案。

理论上的注意：

在此问题中，观察当前解决方案是否满足了新限制，如果是，这将是多余的限制并且不会影响当前解决方案，但是如果当前解决方案未满足，则有必要再次考虑此问题新限制。

模型：

X1 =当天要生产的鸽子数

X2 =当天要生产的鹰的数量

最大12X1 + 20X2

受制于

0.125X1 + 0.25X2 <= 480皮草机

0.25X1 + 0.2X2 <= 480填充线

0.2857143X2 <= 480峰值锐化

结束

在步骤2找到LP最佳