土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

（用实例引入人工变量法）

例1-7 用单纯形法求解下列线性规划问题：

maxZ?2x1?3x2?5x3x1?x2?x3?72x1?5x2?x3?10x1,x2,x3?0

解：将第二个约束条件化为等式（左边减去一个松弛变量）后，约束条件的系数矩阵不存在单位矩阵，这时可在约束条件第一、二等式的左边分别加上一个人工变量作为初始基变量，使之出现单位矩阵。为了使目标函数中的人工变量为0，令它们的系数为任意大的负值“-M”，然后采用一般单纯形表法求解。

minZ?2x1?3x2?5x3?Mx4?0x5?Mx6x1?x2?x3?x4?72x1?5x2?x3?x5?x6?10x1,x2,x3,x4,x5,x6?0Cj

目标函数 决策变量 基变量 初 x4 2 3 -5 -M 0 -M x1↓ x2↓ x3 x4 x5 x6 常数 7 xj -M -M 1 1 1 1 0 0 始表 ←x6 计 算 Zj [2] -5 1 0 -1 1 10 -3M 4M -2M -M M -M ?j 3M+2 3-4M 2M-5 0 -M 0 ??min(7/1,10/2)?5 第21页 ------------------------------------------------------------------------------------------------------------------------------------------------------

土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

一次 ←x4 迭代 x1 Zj -M 2 0 [7/2] 1/2 1 1/2 -1/2 1 -5/2 1/2 0 -1/2 1/2 2 ?M?5 ?72 2 5 ?j x2 x1 MMM?1 -M ??1 ?1 2227MM3M0 M?8 ?6 0 ?1 ??1 22223 2 0 1 1/7 2/7 1/7 -1/7 1 0 6/7 5/7 -1/7 1/7 2 3 15/7 16/7 1/7 -1/7 4/7 45/7 Zj ?j 0 0 -50/7 -M-16/7 -1/7 -M+1/7 所以最优解为：X=（45/7，4/7，0，0，0，0） 例1-8 对LP模型：

minw?15y1?24y2?5y3 s.t. 6y2?y3?2y1?3?05y1?2y2?y3?1

用两阶段法求解。 解：先分为标准型：

max(?w)??15y1?24y2?5y3?0y4?0x5 s.t. 6y2?y3?y4?y6?2y1?7?05y1?2y2?y3?y5?y7?1

对

minZ?y6?y76y2?y3?y4?y6?25y1?2y2?y3?y5?y7?1y1?7?0第22页

------------------------------------------------------------------------------------------------------------------------------------------------------

s.t.

土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

使用单纯形法求解，化为标准型后，列出单纯形表并迭代如下 目标函数 决策变量 基变量 初 y6 Cj 0 0 0 0 0 -1 -1 y1↓ y2↓ y3 y4 y5 y6 y7 常数 2 1 1/3 1/3 yj -1 -1 0 0 [6] 1 -1 0 1 0 5 2 1 0 -1 0 1 5 8 2 -1 -1 0 0 0 1 1/6 -1/6 0 1/6 0 始表 ←y7 一次 ?j y2 迭代 ←y7 ?j y2 -1 [5] 0 2/3 1/3 -1 -1/3 1 5 0 2/3 1/3 -1 -4/3 0 0 0 1 1/6 -1/6 0 1/6 0 0 1 0 2/15 1/15 -1/5 -1/15 1/5 0 0 0 0 0 -1 -1 1/3 1/15 y1 ?j 在上表中的最终表中除去人工变量y6,y7后，回归到原来的标准型：

max(?w)??15y1?24y2?5y3?0y4?0x5 s.t. 6y2?y3?y4?y6?2y1?7?05y1?2y2?y3?y5?y7?1

然后对该最终表继续使用单纯形法计算： 目标函数 决策变量 基变量 Cj -15 -24 -5 0 0 常数 y1 y2 y3↓ y4 y5 yj 第23页

------------------------------------------------------------------------------------------------------------------------------------------------------

土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

初 y2 -24 -15 -24 -5 0 1 1/6 -1/6 0 1/3 1 0 [2/15] 1/15 -1/5 1/15 0 -9 6 -3 -3 始表 ←y1 一次 迭代 ?j y2 y3 -5/4 1 0 -1/4 1/4 1/4 15/2 0 1 1/2 -3/2 1/2 ?j -15/2 0 0 -7/2 -3/2 故Y?(0,1/4,1/2,0,0)T 1.15题分析：

xij?0令i=1,2,3代表A，B，C三种商品，j=1,2,3代表前，中，后舱，

代表装载于第j舱位的第i中商品的数量（件）。

1、目标函数为运费总收入：

maxZ?1000(x11?x12?x13)?700(x21?x22?x23)?600(x31?x32?x33)

2、约束条件： 前中后舱载重限制：

8x11?6x21?5x31?20008x12?6x22?5x32?3000 8x13?6x23?5x33?1500前中后舱体积限制：

10x11?5x21?7x31?400010x12?5x22?7x32?5400 10x13?5x23?7x33?1500

三商品的数量限制：

第24页

------------------------------------------------------------------------------------------------------------------------------------------------------