(数学建模)第1章线性规划(编辑修改稿)

(数学建模)第1章线性规划(编辑修改稿)内容摘要：

1 17/3 28/9 1/3 － 1/9 1 2/3 25 35/3 λ j 0 0 － 98/9 － 1/9 －7/3 【例 】 用单纯形法求解 1 2 41 2 31 2 41 2 5m in 2 2566 2 210 , 1, , 5jZ x x xx x xx x xx x xxj            【 解】 这是一个极小化的线性规划问题 ,可以将其化为极大化问题求解 ,也可以直接求解 ,这时判断标准是： λj≥0(j=1， … ， n)时得到最优解。 容易观察到 ,系数矩阵中有一个 3 阶单位矩阵 ,x x x5为基变量。 目标函数中含有基变量 x4,由第二个约束得到 x4=6+x1－ x2，并代入目标函数消去 x4 得 212121 6)6(22 xxxxxxZ ＝ 单纯形法计算如表 1－ 6 所示。 表中 λj≥0,j=1,2,…,5 ，所以最优解为 X=(0， 5， 0， 1， 11,)T 最优值 Z=2x1－ 2x2－ x4=－ 25－ 1=－ 11。 求极小值问题时 ,注意判断标准 ,选进基变量时应选 λj0的变量进基。 表 1－ 6 XB x1 x2 x3 x4 x5 b θ x3 x4 x5 1 － 1 6 [1] 1 2 1 0 0 0 1 0 0 0 1 5→ 6 21 5 6 21/2 λ j 1 － 1↑ 0 0 0 x2 x4 x5 1 － 2 4 1 0 0 1 － 1 － 2 0 1 0 0 0 1 5 1 11 λ j 2 0 1 0 0 一章 第五节 【例 】求解线性规划 21max xxZ  042123212121xxxxxx、 【解】化为标准型 121 2 31 2 4m ax3 2 1240, 1, , 4jZ x xx x xx x xxj          初始单纯形表为见表 1－ 7。 表 1－ 7 XB x1 x2 x3 x4 b x3 x4 3 2 － 2 － 1 1 0 0 1 1 4 λ j － 1 1 0 0 λ2=10,x2进基，而 a120， a220，没有比值，从而线性规划的最优解无界。 由模型可以看出，当固定 x1 使 x2→+∞时 Z→+∞且满足约束条件，还可以用图解法看出具 有无界解。 【例 】求解线性规划 1212121212m ax 2 4242 1020Z x xxxxxxxxx      、 【解】化为标准型后用单纯形法计算如表 1－ 8 所示。 表 1－ 8 XB x1 x2 x3 x4 x5 b θ (1) x3 x4 － 1 1 [2] 2 1 0 0 1 0 0 4→ 10 2 5 x5 1 － 1 0 0 1 2 — λ j 2 4↑ 0 0 0 (2) x2 x4 x5 － 1/2 [2] 1/2 1 0 0 1/2 － 1 1/2 0 1 0 0 0 1 2 6→ 4 — 3 8 λ j 4↑ 0 － 2 0 0 (3) x2 x1 x5 0 1 0 1 0 0 1/4 － 1/2 [3/4] 1/4 1/2 － 1/4 0 0 1 7/2 3 5/2→ 14 — 10/3 λ j 0 0 0↑ － 2 0 (4) x2 x1 x3 0 1 0 1 0 0 0 0 1 1/3 1/3 － 1/3 － 1/3 2/3 4/3 8/3 14/3 10/3 λ j 0 0 0 － 2 0 表 1－ 8(3)中 λj全部非正 ,则最优解为 20,)25,0,0,27,3()1(  ZX T 表 1－ 8(3)表明 ,非基变量 x3 的检验数 λ3=0， x3若增加 ,目标数值不变 ,即当 x3 进基时 Z 仍等于 20。 使 x3 进基 x5出基继续迭代 ,得到表 1－ 8(4)的另一基本最优解 20,),0,0,310,38,314)1(  ZX T（ X(1)、 X(2)是线性规划的两个最优解，它的凸组合 )10()1( )2()1(   XXX 唯一最优解的判断 最优表中所有非基变量的检验数非零 ,则线规划具有唯一最优解。 多重最优解的判断 最优表中存在非基变量的检验数为零 ,则线性规划具有多重最优解； 无界解的判断 某个 λk0 且 aik≤０ (i=1， 2,…, m)则线性规划具有无界解。 例 】求解线性规划 21max xxZ  042123212121xxxxxx、 【解】化为标准型 121 2 31 2 4m ax3 2 1240, 1, , 4jZ x xx x xx x xxj          初始单纯形表为见表 1－ 7。 表 1－ 7 XB x1 x2 x3 x4 b x3 x4 3 2 － 2 － 1 1 0 0 1 1 4 λ j － 1 1 0 0 λ2=10,x2进基，而 a120， a220，没有比值，从而线性规划的最优解无界。 由模型可以看出，当固定 x1 使 x2→+∞时 Z→+∞且满足约束条件，还可以用图解法看出具有无界解。 【例 】求解线性规划 1212121212m ax 2 4242 1020Z x xxxxxxxxx      、 【解】化为标准型后用单纯形法计算如表 1－ 8 所示。 表 1－ 8 XB x1 x2 x3 x4 x5 b θ (1) x3 x4 － 1 1 [2] 2 1 0 0 1 0 0 4→ 10 2 5 x5 1 － 1 0 0 1 2 — λ j 2 4↑ 0 0 0 (2) x2 x4 x5 － 1/2 [2] 1/2 1 0 0 1/2 － 1 1/2 0 1 0 0 0 1 2 6→ 4 — 3 8 λ j 4↑ 0 － 2 0 0 (3) x2 x1 x5 0 1 0 1 0 0 1/4 － 1/2 [3/4] 1/4 1/2 － 1/4 0 0 1 7/2 3 5/2→ 14 — 10/3 λ j 0 0 0↑ － 2 0 (4) x2 x1 x3 0 1 0 1 0 0 0 0 1 1/3 1/3 － 1/3 － 1/3 2/3 4/3 8/3 14/3 10/3 λ j 0 0 0 － 2 0 表 1－ 8(3)中 λj全部非正 ,则最优解为 20,)25,0,0,27,3()1(  ZX T 表 1－ 8(3)表明 ,非基变量 x3 的检验数 λ3=0， x3若增加 ,目标数值不变 ,即当 x3 进基时 Z 仍等于 20。 使 x3 进基 x5出基继续迭代 ,得到表 1－ 8(4)的另一基本最优解 20,),0,0,310,38,314)1(  ZX T（ X(1)、 X(2)是线性规划的两个最优解，它的凸组合 )10()1( )2()1(   XXX 唯一最优解的判断 最优表中所有非基变量的检验数非零 ,则线规划具有唯一最优解。 多重最优解的判断 最优表中存在非基变量的检验数为零 ,则线性规划具有多重最优解； 无界解的判断 某个 λk0 且 aik≤０ (i=1， 2,…, m)则线性规划具有无界解。 大 M 和两阶段单纯形法 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。 在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。 这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M 法或两阶段法求解，是一种用人工变量作桥梁 的求解方法，也称为人工变量法。 一 、 大 M 单纯形法 大 M 单纯形法的基本思想是：约束条件加入人工变量后，求极大值时，将目标函数变为   nj mi ijj RMxcZ 1 1m a x ＝ ＝ 式中 M 为很大的正数，因而－ MRi 为很小的负数，在迭代过程中， Z 要达到极大化， Ri 就会很快出基。 求极小值时，将目标函数变为    nj mi ijj RMxcZ 1 1mi n 同理，在迭代过程中， Z 要达到极小化， Ri就会迅速出基。 【例 】 用大 M 单纯形法求解下列线性规划 012210243423m ax321321321321321xxxxxxxxxxxxxxxZ、 【 解】 首先将数学模型化为标准形式 5,2,1,012210243423m ax32153214321321jxxxxxxxxxxxxxxxZj 式中 x x5为松弛变量， x5可作为一个基变量，第一、三约束中分别加入人 工变量 x x7，目标函数中加入 ―M x6―M x7 一项，得到大 M 单纯形法数学模型 7,2,1,012210243423m ax732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj－ 再用前面介绍的单纯形法求解，见表 1－ 9 所示。 表 1－ 9 Cj 3 2 － 1 0 0 － M －M b CB XB x1 x2 x3 x4 x5 x6 x7 －M 0 －M x6 x5 x7 － 4 1 2 3 － 1 － 2 1 2 [1] － 1 0 0 0 1 0 1 0 0 0 0 1 4 10 1→ λ j 3－2M 2+M － 1+2M↑ － M 0 0 0 －M 0 － 1 x6 x5 x3 － 6 － 3 2 [5] 3 － 2 0 0 1 － 1 0 0 0 1 0 1 0 0 3→ 8 1 λ j 5－6M 5M↑ 0 － M 0 0 2 0 － 1 x2 x5 x3 － 6/5 [3/5] － 2/5 1 0 0 0 0 1 － 1/5 3/5 － 2/5 0 1 0 3/5 31/5→ 11/5 λ j 5↑ 0 0 0 0 2 3 － 1 x2 x1 x3 0 1 0 1 0 0 0 0 1 1 1 0 2 5/3 2/3 13 31/3 19/3 λ j 0 0 0 － 5 － 25/3 因为 λj≤0， j=1,2,…,5, 并且 x6， x7为非基变量，所以最优解 3152),0,0,31913,331(  ZX T ，最优值， 【例 】。