线性规划的图解法与单纯形解法

运筹学Operations Research王 慧东南大学经济管理学院电子商务系暨管理工程研究 wh_1线性规划的图解法与单纯形解法 p线性规划问题的图解法 p线性规划单纯形解法的原理p线性规划单纯形解法的计算步骤 p单纯形法计算的矩阵描述 p线性规划单纯形求解的大 M法p线性规划单纯形求解的两阶段法p线性规划单纯形求解可能的循环现象2线性规划问题的图解法p图解法，就是用作图的方法求解线性规划问题。p简单、直观的图解法一般只适用于具有 两个决策变量 的线性规划问题。p用图解法求解实际线性规划问题，一般按照如下基本步骤：Step1 画直坐标系；Step2 根据约束条件画出可行域；Step3 画过坐标原点的目标函数线；Step4 确定目标函数值的增大方向 (目标函数线法线方向 )Step5 目标函数线沿着增大方向平行移动，与可行域相交且有最大目标函数值的顶点，即为线性规划问题的最优解 。3x1x2O 10 2030 4010203040(15,10) 最优解 X=(15,10)最优值 Z=85例 2.142 4 6 x1x2246最优解 X=(3,1)最优值 Z=5(3,1)min Z=x1+2x2例 2.2524 6 x1x2246X（ 2） （ 3,1）X（ 1） （ 1,3）min Z=5x1+5x2例 2.3有无穷多个最优解即具有多重解 ,通解为01 当 =0.5时 =(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 62 4 6 x1x2246无界解 (无最优解 )max Z=x1+2x2例 2.47x1x2O 10 20 30 40102030405050无 可行解即无最优解max Z=10x1+4x2例 2.58由 以上例题可知，线性规划的解有 4种形式 ：1.有唯一最优解 (例 2.1例 2.2)2.有多重解 (例 2.3)3.有无界解 (例 2.4)4.无可行解 (例 2.5)1、 2情形为有最优解3、 4情形为无最优解9由图解法得到的启示 p线性规划问题求解的基本依据是：线性规划问题的最优解总可在可行域的顶点中寻找。寻找线性规划问题的最优解只需比较有限个顶点处的目标函数值。p线性规划问题求解时可能出现四种结局： 唯一最优解 、无穷多个最优解 、 无有界解 、 无解或无可行解 。p如果某一线性规划问题有最优解，我们可以按照这样的思路来求解：先找可行域中的一个顶点，计算顶点处的目标函数值，然后判别是否有其它顶点处的目标函数值比这个顶点处的目标函数值更大，如有，转到新的顶点，重复上述过程，直到找不到使目标函数值更大的新顶点为止。101.通过图解法了解线性规划有几种解的形式2.作图的关键有三点(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动11线性规划单纯形解法的原理 p单纯形方法的基本思想从可行域中的一个基可行解出发，判别它是否已经是最优解，如不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无解为止。p单纯形算法必须解决三个方面的问题：1. 如何确定初始的基可行解？2. 如何进行解的最优性判别？3. 如何寻找改进的基可行解？12确定初始的基可行解p标准型的线性规划问题系数矩阵中存在一个单位阵 以单位阵为一初始可行基。令非基变量取值为零，便得到一基可行解。 13【 例 2.6】 用单纯形法求下列线性规划的最优解 14【 解 】 化为标准型，加入松驰变量 x3、 x4则标准型为系数矩阵 A及可行基 B1r(B1)=2， B1是一个初始基 ,x3、 x4为基变量， x1、 x2为非基变量，令 x1=0、 x2=0由约束方程知 x3=40、x4=30得到初始基本可行解X(1)=(0,0,40,30)T 15以上得到的一组基可行解是不是最优解，可以从目标函数中的系数看出。目标函数 Z=3x1+4x2中 x1的系数大于零，如果 x1为一正数，则 Z的值就会增大，同样若 x2不为零为一正数，也能使 Z的值增大；因此只要目标函数中非基变量的系数大于零，那么目标函数就没有达到最大值，即没有找到最优解，判别线性规划问题是否达到最优解的数称为检验数，记作 j , j=1,2, n。 本例中 1=3, 2=4, 3=0, 4=0。最优解判断标准 当所有检验数 j0（ j=1， ， n） 时，基本可行解为最优解。 当目标函数中有基变量 xi时，利用约束条件将目标函数中的 xi消去即可求出检验数。 检验数 目标函数用非基变量表达时的变量系数16进基列 出基行bi /ai2， ai20i表 1-4(1)XB x1 x2 x3 x4 bx3 2 1 1 0 40x4 1 3 0 1 30 j 3 4 0 0 (2)x3x2 j (3)x1 x2 j 基变量110001/3 0 1/3 105/3 1 -1/3405/3 0 -4/3301 0 3/5 -1/5 180 1 -1/5 2/5 40 0 -1 -1将 3化为 1乘以1/3后得到30 1817最优解 X=(18， 4， 0， 0)T， 最优值 Z=70O 20 301040(3,4)X(3)=(18,4)最优解 X=(18,4)最优值 Z=70X(1)=(0,0)2010x2x130X(2)=(0,10)18单纯形表单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表。19单纯形算法的计算步骤 将线性规划问题化成标准型。 找出或构造一个 m阶单位矩阵作为初始可行基，建立初始单纯形表。 计算各非基变量 xj的检验数 j，若所有 j0， 则问题已得到最优解，停止计算，否则转入下步。 在大于 0的检验数中，若某个 k所对应的系数列向量 Pk0， 则此问题是无界解，停止计算，否则转入下步。 根据 maxj j 0=k原则，确定 xk为换入变量 (进基变量 )，再按 规则计算： =minbi/aik| aik 0=bl/ aik 确定 xl为换出变量。建立新的单纯形表，此时基变量中 xk取代了 xl的 位置。 以 aik为主元素进行迭代，把 xk所 对应的列向量变为单位列向量，即 aik变为 1，同列中其它元素为 0，转第 步。 20【 例 2.7】 利用单纯形列表算法求解例 2.6 21【 例 2.8】 用单纯形法求解22【 解 】 将数学模型化为标准形式：不难看出 x4、 x5可作为初始基变量，单纯法计算结果如表 1.所示 。 23Cj 1 2 1 0 0b CB XB x1 x2 x3 x4 x50 x4 2 3 2 1 0 150 x5 1/3 1 5 0 1 20j 1 2 1 0 0 0 x42 x2j 1 x1 2 x2 j 表 1 51/3 1 5 0 1 203 0 17 1 3 751/3 0 9 0 2M2025601 0 17/3 1/3 1 250 1 28/9 1/9 2/3 35/30 0 98/9 1/9 7/3最优解 X=(25， 35/3， 0， 0， 0)T， 最优值 Z=145/3 24【 例 2.9】 用单纯形法求解 25【 解 】 这是一个极小化的线性规划问题 ,可以将其化为极大化问题求解 ,也可以直接求解 ,这时判断标准是： j0(j=1， ， n)时得到最优解 。容易观察到 ,系数矩阵中有一个 3阶单位矩阵 ,x3、 x4、x5为基变量。目标函数中含有基变量 x4,由第二个约束得到 x4=6+x1 x2， 并代入目标函数消去 x4得26XB x1 x2 x3 x4 x5 b x3x4x51-1611210001000156215621/2j 1 -1 0 0 0 x2x4x51-241001-1-20100015111j 2 0 1 0 0 表中 j0,j=1,2, ,5所以最优解为 X=(0,5,0,1,11,)最优值Z=2x