习题一
1.1 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。
（a）无穷多最优解 最优解为点（3/4,1/2）到点（3/2,0）之间线段上的所有点。
min z?2x1?3x2
（b）无可行解
?4x1?6x2?6?s.t.?4x1?2x2?4?x,x?0?12（c）唯一最优解 X=（10,6） 最优值Z=16
（d）无界解
1.2 对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。
maxz?3x1?x2?2x3?12x1?3x2?6x3?3x4?9??2x5?10（a）?8x1?x2?4x3
s.t.?3x?x6?0?1?xj?0(j?1,?,6)?P1?12?A?8???3P2310P36?40P4300020P5P60??0??1??
基 P1 P1 P1 P1 P1 P1 P1 P1 P1 P1 P2 P2 P2 P3 P3 P2 P2 P2 P2 P3 P3 P3 P4 P4 P5 P3 P4 P5 P4 P5 P3 P4 P5 P6 P4 P5 P6 P5 P6 P6 P6 P6 P6 P6 P6 基解 X1 0 0 0 7/4 0 0 1 0 5/4 3/4 0 0 0 0 0 X2 16/3 10 3 -4 0 0 0 0 0 0 16/3 10 3 0 0 X3 -7/6 0 0 0 -5/2 3/2 -1/2 0 0 0 -7/6 0 0 -5/2 3/2 X4 0 -7 0 0 8 0 0 3 -2 0 0 -7 0 8 0 X5 0 0 7/2 0 0 8 0 5 0 2 0 0 7/2 0 8 X6 0 0 0 21/4 0 0 3 0 15/4 9/4 0 0 0 0 0 可行否 否 否 是 否 否 是 否 是 否 是 否 否 是 否 是 目标值 3 10 3 5/4 -5 3 2 0 15/4 9/4 3 10 3 -5 3 P4 P5 P6 0 0 0 3 基解16个，基可行解7个，最优解4个，最优值是3。
minz?5x1?2x2?3x3?2x4?x1?2x2?3x3?4x4?7 ?s.t.?2x1?2x2?x3?2x4?3?x?0(j?1,?,4)?j5 0 是 0 （b）
P1?1A???2P222P331P44??2?
基 P1 P1 P1 P2 P2 P2 P3 P4 P3 P4 基解 X1 -4 2/5 -1/3 0 0 X2 11/2 0 0 1/2 -1/2 X3 0 11/5 0 2 0 1 X4 0 0 11/6 0 2 1 可行否 否 是 否 是 否 是 目标值 -31 43/5 2 5 5 5 P3 P4 0 0 基可行解3个，最优解2个，最优值5。
1.3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解分别对应图解法中可行域的哪一顶点。 （a）
maxz?10x1?5x2?0x3?0x4?3x1?4x2?x3?9?x4?8?5x1?2x2??x?0(j?1,2,3,4)?j
1.6 将下列线性规划问题化为标准形式，并列出初始单纯形表。 (a)
minz?3x1?5x2?x3?x1?2x2?x3?6?（b）?2x1?x2?3x3?16
s.t.??x1?x2?5x3?10?x,x?0,x无约束3?12解：添加剩余变量x4和松弛变量x5，划为： minz?3x1?5x2?x3?x1?2x2?x3?x4?6??2x1?x2?3x3?x5?16 s.t.??x1?x2?5x3?10?x,x,x,x?0,x无约束3?1245令w= -z，x3=x3’-x3’’ ，x3’≥0，x3’’≥0，标准形式为
maxw??3x1?5x2?x3'?x3''?x1?2x2?x3'?x3''?x4?6??2x1?x2?3x3'?3x3''?x5?16 s.t.??x1?x2?5x3'?5x3''?10?x,x,x',x'',x,x?045?1233再引入人工变量x6,x7,问题划为： maxw??3x1?5x2?x3'?x3''?Mx6?Mx7?x6?6?x1?2x2?x3'?x3''?x4? ?2x1?x2?3x3'?3x3''?x5?16s.t.??x7?10?x1?x2?5x3'?5x3''?x,x,x',x'',x,x,x,x?04567?1233初始单纯形表为： CJ CB XB -M X6 0 b 6 -3 X1 1 2 1 2M-3 -5 X2 2 1 1 3M-5 1 X3’ 1 3 5 6M+1 -1 X3’’ -1 -3 -5 -6M-1 0 X4 -1 0 0 -M 0 X5 0 1 0 0 -M X6 1 0 0 0 -M X7 0 0 1 0 X5 16 -M X7 10
1.7 用大M法求解下列线性规划问题，并指出属哪一类解。 (a)maxz?2x1?x2?2x3?x1?x2????2x1?s.t.?2x2??x,x,x?123x3?6x3?2?x3?0?0
解：化为标准形为：
maxz?2x1?x2?2x3?Mx7?Mx8?Mx9?x7?6?x1?x2?x3?x4??x5?x8?2 ??2x1?x3s.t.?2x2?x3?x6?x9?0??xj?0,(j?1,?,9)?CJ CB XB b -M X7 6 -M X8 2 -M X9 0 -M X7 6 2 X1 1 -2 0 2-M 1 -1 X2 1 0 2 -1+3M 0 2 X3 1 1 -1 2+M 3/2 0 X4 -1 0 0 -M -1 0 X5 0 -1 0 -M 0 0 X6 0 0 -1 -M 1/2 -M X7 1 0 0 0 1 -M X8 0 1 0 0 0 -M X9 0 0 1 0 -1/2 θ 6 ---- 0 4
习题一
