有：4+Δb≥0；即 Δb≥‐4。故当约束 2 的常数项在[‐4，∞]变化时，其对偶价格不变。
从上表中看到，要使最优基保持不变，则有-1.5-Δc2/2≤0，且-1/8+Δc2/8≤0。由此可得‐3≤Δc2≤1 时，原最优解不变。 （2）设资源量 b 的变化量为 Δb，若 ∆ 0，则原解（基）仍为最优解（基） 。即： 0 4 4 + 2 2 1/2 1/4 0 0 1/2 1 0 1/8 0 ∆ 0
0 x3 1 -4 0 -2
0 x4 0 1 0 0
0 x5 - 1/2 2 1/4 1/4
b 2 8 3 13
进基 出基
x5 x4 min{8/2,3/1/4}
2 XB x1 x5 x2 x1 1 0 0 0
3 x2 0 0 1 0
0 x3 0 -2 1/2 -1.5
0 x4 1/4 1/2 - 1/8 - 1/8
设司机和乘务人员分别在各时间段一开始时上班，并连续工作 8h，问该公交线路怎样
安排司机和乘务人，既能满足工作需要，又配备最少司机和乘务人员。 （1）写出上述问题的数学模型。 （2）将所建的数学模型化为标准型。 （3）求解上述模型（可以采用软件） 。 解： 设 xi 表示第 i 班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0 标准型：Max Z=-x1 - x2 - x3 - x4 - x5 - x6 + x7 + x8 + x9 + x10 + x11 + x12 约束条件：s.t. x1 + x6 - x7= 60 x1 + x2- x8 = 70 x2 + x3 – x9 = 60 x3 + x4 – x10 = 50 x4 + x5 – x11 = 20 x5 + x6 – x12 = 30 x1,x2,x3,x4,x5,x6 , x7,x8,x9,x10,x11,x12≥ 0 解得：x1=40; x2=20; x3=30; x4=20; x5=0; x6=30;目标函数值为：140。 4、用单纯形法求解下面的线性规划问题
可行域无界，目标函数有无穷多个解。 （3）max z=x1+x2 2 , 4 2 0
可行解无界，目标函数无界 （4）max z=2x1+3x2 2 3 4 3
,
0
可行域为空集。 3、某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 班次 1 2 3 4 5 6 时间 6：00 —— 10：00 10：00 —— 14：00 14：00 —— 18：00 18：00 —— 22：00 22： —— 2：00 2：00 —— 6：00 所需人数 60 70 60 50 20 30
（1 ） ）请建立该问 问题的数学模 模型。 （2 ） ）请用图解法 法进行求解。 （3 ） ）若项目Ⅰ的 的利润改为 3 元，解发生 生什么变化？
max z 2x 1 x 2 5x 2 15 解： （1）数学模 模型 6x 1 2x 2 24 s. t. x 1 x 2 5 x ,x 0 1 2
（2 ）
（3 ） ）若项目Ⅰ的 的利润改为 3 元，有无穷 穷多个解。 2、用 用图解法求解 解下列问题。 （1）max z=-3x1+2x2 2 , 0 4 5
可行域无界，目标函数有唯一解。 （2）max z=-2x1+x2 2 , 0 4 5
进基 出基
x2 x5 min{8/2,12/4}
0 3 σj
x4 x2
4 0 2
0 1 0
0 0 0
1 0 0
0 1/4 - 3/4
16 3 Z=9
第二次迭代 Cj CB 2 0 3 σj 第三次迭代 Cj CB 2 0 3 σj
T
2 XB x1 x4 x2 x1 1 0 0 0
3 x2 0 0 1 0
请根据表中数据回答下列问题： （1）变量 x2 的系数在什么范围内变化，此问题最优解不变？ （2）约束条件 3 的常数项在什么范围内变化时，其对偶价格不改变？ 解： （1）考虑基变量系数 c2 发生变化，即由 3 变为 3+Δc2。将其放入单纯形表中有： Ci CB 2 0 3+Δc2 XB x1 x5 x2 σj b 4 4 2 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 0 -2 1/2 -1.5-Δc2/2 0 x4 1/4 1/2 -1/8 -1/8+Δc2/8 0 x5 0 1 0 0
第 一章 线性规 规划 1、美 美佳公司计划 划制造Ⅰ、Ⅱ Ⅱ两种家电产 产品。已知各 各制造一件时 时分别占用的 的设备 A，B 的台 时、 调 调试工序时间 间及每天可用 用于这两种家 家电的能力、 各售出一件时 各 时的获利情况 况， 如下表所 所示。 问该 该公司应制造 造两种家电各 各多少件，使 获取的利润为 为最大。 项目 目 设备 A（h） 设备 B（h） 序（h） 测试工序 利润（元） Ⅰ 0 6 1 2 Ⅱ 5 2 1 1 每天 天可用能力 15 24 5
max Z 2x 1 3x 2 0x 3 0x 4 0x 5 x 1 2x 2 x 3 8 4x 1 x 4 16 4x 2 x 5 12 x ,x ,x ,x ,x 0 1 2 3 4 5
Cj CB 0 0 0 σj 第一次迭代 Cj CB 0 XB x3 2 x1 1 3 x2 0 0 x3 1 0 x4 0 0 x5 - 1/2 b 2 进基 出基 x1 x3 min{2/1,16/4} XB x3 x4 x5 2 x1 1 4 0 2 3 x2 2 0 4 3 0 x3 1 0 0 0 0 x4 0 1 0 0 0 x5 0 0 1 0 b 8 16 12 0
0 x5 0 1 0 0
b 4 4 2 14
所以，x =（4,2,0,0,4） ；Z=14 5、求解线性规划问题
min w 2x 1 3x 2 5x 3 2x 4 3x 5 x 1 x 2 2x 3 x 4 3x 5 4 2x 1 2x 2 3x 3 x 4 x 5 3 x ,x ,x ,x ,x 0 1 2 3 4 5
已知对偶问题的最优解为 y1=4/5，y2=3/5；试用互补松弛定理求出原问题的最优解。 解：对偶问题为 max 4 3 2 2 2 3 3 5 2 2 3 3 将 y1*=4/5, y2*=3/5 代入约束条件，得到第二、三、四个约束条件为严格不等式，亦即这些 约束中加入的松弛变量 yi 大于零。根据互补松弛性质 x*yi=0 可得： x2*=0; x3*=0; x4*=0 由于 y1*>0; y2*>0，根据互补松弛性 yi*xi=0 可得： x6=0;x7=0
故有：∗3ຫໍສະໝຸດ ∗∗ ∗2
4 3
求解后得到：x1*=1，x5*=1。故原问题的最优解为：X*=（1,0,0,0,1）T，w*=5 6、已知线性规划问题 max 2 3 2 4 4 , 其最终单纯形表为： Ci CB 2 0 3 XB x1 x5 x2 σj b 4 4 2 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 0 -2 1/2 -1.5 0 x4 1/4 1/2 -1/8 -1/8 0 x5 0 1 0 0 , , , 8 16 12 0