线性规划与单纯形法

线性规划问题的单纯形法求解步骤

线性规划是一种优化问题，它的解决方法有很多种，在这里我们来介绍其中一种常用的方法——单纯形法。我们将介绍单纯形法的求解步骤，以帮助读者更好地理解和掌握这种求解方法。

1. 建立数学模型

任何一个线性规划问题的解决都需要先进行建模。我们将问题转换成数学模型，然后使用数学方法进行求解。线性规划问题的一般形式为：

max cx

s.t.

Ax ≤ b

x ≥ 0

其中，c、x、b、A都是向量或矩阵，x≥0表示各变量都是非负数。其中c表示目标函数，A和b表示约束条件。

2. 计算初始基可行解 我们需要从初始点开始，逐步优化目标函数。但是，在开始优化前我们需要先找到一个基可行解。基可行解的定义是：如果所有非基变量的取值都是0，并且所有基变量的取值都是非负的，则该解被称为基可行解。当基可行解找到后，我们就可以开始进行优化。

3. 确定进入变量

在单纯形法中，每次迭代中我们都需要找到进入变量。进入变量是指，通过操作非基变量可以使得目标函数增加的变量。我们需要找到一个使得目标函数增加最多的非基变量，将其称为进入变量。

4. 确定离开变量

在确定进入变量后，我们需要确定一个离开变量。离开变量是指，通过操作基变量可以使得目标函数增加的变量。我们需要找到一个离开变量，使得当进入变量增加到某个值时，该离开变量的值为0。这样，我们就找到了一个最小的正根比率，使得通过基本变量出基到进入变量变为零而得到的新解是可行的。

5. 交换变量 接下来，我们需要将已选定的进入变量和离开变量进行交换。此时，我们将进入变量转变为基变量，离开变量转变为非基变量。通过这种交换，我们还需要调整我们的基向量。由于这个交换，我们将得到一个新的基可行解，并且它可以比之前的解更好。

6. 重复迭代

我们需要重复上述步骤，直到我们找到最优解。重复迭代意味着我们将不断查找新的进入变量和离开变量，并进行变量交换。这种找到最优解的过程可能非常复杂，但是单纯形法的效率很高，通常可以在很短的时间内找到最优解。

运筹学考试重点

题型概述：单选、判断、填空、建模、计算分析

第一章 线性规划与单纯形法

例1． 某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原料的消耗，如下图所示。

产品 I II

设备

原料A

原料B 1

4

0 2

0

4 8台时

16kg

12kg

该工厂每生产一件产品I可获利2元，生产一件产品II可获利3元，若用Z表示利润，X1、X2表示产量，该计划问题的数学模型可以表示为：目标函数

maxZ=2X1+3X2

满足约束条件 ｛X1+2X2<=8

{4X1 <=16 X1,X2>=0

{ 4X2<=12

最优解是唯一的，但对于一般线性规划问题，求解结果还可能出现以下几种情况：

1. 无穷多最优解（多重最优解）

2. 无界解

3. 无可行解

线性规划问题的标准形式为：(M1) maxZ=c1x1+c2x2+…….+cnxn

下面讨论如何变换为标准型的问题。

（1） 若要求目标函数实现最小化，即minZ=CX。这时只需将目标函数最小化变换求目标函数最大化，即令Z’=-Z,于是得到maxZ’=-CX.

（2） 约束方程为不等式。这里有两种情况：一种是约束方程为“<=”不等式，则可在“<=”不等式的左端加上非负松弛变量，把原“<=”不等式变为等式；另一种是约束方程为“>=”不等式，则可在“>=”不等式的左端减去一个非负剩余变量（也可称松弛变量），把不等式变为等式。

例 将例1的数学模型化为标准型。

解. maxZ=2x1+3x2

｛X1+2X2<=8

{4X1 <=16 X1,X2>=0

第一章 线性规划及单纯形法习题

1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。

（1）0,42266432min21212121xxxxxxxxz (2)

0,12432223max21212121xxxxxxxx

(3)

83105120106max212121xxxxxxz (4)

0,2322265max12212121xxxxxxxxz

2.将下列线性规划问题化成原则形式。

(1)无约束43214321432143214321,0,,2321422245243minxxxxxxxxxxxxxxxxxxxxz (2)

无约束3214321321321321,0,0232624322minxxxxxxxxxxxxxxxxz

3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并拟定最优解。

(1)

)6,,1(0231024893631223min6143214321321jxxxxxxxxxxxxxxzj (2)

)4,,1(01022274322325min432143214321jxxxxxxxxxxxxxzj

4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中旳各基本可行解相应图解法中可行域旳哪一顶点。

(1)

0,825943510max12212121xxxxxxxxz (2)

0,242615532max12212121xxxxxxxxz

,.

一、选择填空

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

二、判断正误

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

三、将下列问题化为标准型

1.123412341231324237..2358,0,0,MaxZxxxxxxxxstxxxxxxx符号不限

[解] 令'22xx，'445xxx，在约束1中引入非负的松弛变量6x，约束2两边同乘以-1。整理得：

''12345''123456'123''12345623()()7..23()58,,,,,0MaxZxxxxxxxxxxxstxxxxxxxxx

即：

12345123456123123456237..2358,,,,,0MaxZxxxxxxxxxxxstxxxxxxxxx

2. Min Z=-x1+5x2-2x3

x1 +x2 - x3 ≤ 6

2x1 - x2 +3x3 ≥ 5

x1 + x2 = 10 s.t. ,.

x1 ≥ 0, x2 ≤ 0, x3符号不限

[解] 首先，令对变量x3进行处理，令x3 = x’3- x4;再令x’2 = - x2。然后对目标函数和约束条件进行标准化。

Max Z=x1+5x2+2x3-2x4

x1 - x2 - x3+x4+x5 = 6

2x1 + x2 +3x3 - 3x4 -x6 = 5

x1 - x2 = 10

x1, x2, x3, x4, x5, x6≥ 0

四、用图解法求解下列线性规

1. min Z= - x1+2x2