线性规划及其单纯形求解方法.pptVIP

如果记以及则第29页，共43页，星期日，2025年，2月5日(二)单纯形法的计算步骤第1步，找出初始可行基，建立初始单纯形表。第2步，判别检验所有的检验系数（1）如果所有的检验系数,则由最优性判定定理知，已获最优解，即此时的基本可行解就是最优解。（2）若检验系数中，有些为正数，但其中某一正的检验系数所对应的列向量的各分量均非正，则线性规划问题无解。（3）若检验系数中，有些为正数，且它们所对应的列向量中有正的分量，则需要换基、进行迭代运算。第30页，共43页，星期日，2025年，2月5日第3步，选主元。在所有大于零的检验数中选取最大的一个b0s，对应的非基变量为xs，对应的列向量为若则确定brs为主元项。第4步，在基B中调进Ps，换出Pjr，得到一个新的基第5步，在单纯形表上进行初等行变换，使第s列向量变为单位向量，又得一张新的单纯形表。第6步，转入上述第2步。第31页，共43页，星期日，2025年，2月5日第1页，共43页，星期日，2025年，2月5日线性规划是运筹学中发展较快、应用较广和比较成熟的一个分支。它在实际应用中日益广泛与深入,已经被广泛地应用到工业、农业、商业与交通运输规划，工程技术的优化设计，以及企业管理等各个领域。在地理学领域，线性规划，作为传统的计量地理学方法之一，是解决有关规划、决策和系统优化问题的重要手段。第2页，共43页，星期日，2025年，2月5日线性规划的数学模型线性规划的标准形式及方法线性规划的解及其性质线性规划问题的求解方法——单纯形法应用实例:农场种植计划模型第1节线性规划及其单纯形求解方法第3页，共43页，星期日，2025年，2月5日（一）线性规划模型之实例线性规划研究的两类问题：某项任务确定后，如何统筹安排，以最少的人力、物力和财力去完成该项任务；面对一定数量的人力、物力和财力资源，如何安排使用，使得完成的任务最多。它们都属于最优规划的范畴。以下为一些实例。一、线性规划的数学模型第4页，共43页，星期日，2025年，2月5日运输问题假设某种物资（譬如煤炭、钢铁、石油等）有m个产地，n个销地。第i产地的产量为ai（i=1，2，…，m），第j销地的需求量为bj(j=1,2，…，n)，它们满足产销平衡条件。如果产地i到销地j的单位物资的运费为Cij，要使总运费达到最小，可这样安排物资的调运计划：第5页，共43页，星期日，2025年，2月5日设xij表示由产地i供给销地j的物资数量，则上述问题可以表述为：

求一组实值变量xij(i=1，2，…，m；j=1，2，…，n)，使其满足而且使第6页，共43页，星期日，2025年，2月5日资源利用问题假设某地区拥有m种资源，其中，第i种资源在规划期内的限额为bi(i=1，2，…，m)。这m种资源可用来生产n种产品，其中，生产单位数量的第j种产品需要消耗的第i种资源的数量为aij(i=1，2，…，m；j=1,2,…,n)，第j种产品的单价为cj(j=1，2，…，n)。试问如何安排这几种产品的生产计划，才能使规划期内资源利用的总产值达到最大?第7页，共43页，星期日，2025年，2月5日设第j种产品的生产数量为xj(j=1，2，…，n)，则上述资源问题就是：求一组实数变量xj(j=1，2，…，n)，使其满足

第8页，共43页，星期日，2025年，2月5日合理下料问题用某种原材料切割零件A1，A2,…,Am的毛坯，现已设计出在一块原材料上有B1，B2，…，Bn种不同的下料方式，如用Bj下料方式可得Ai种零件aij个，设Ai种零件的需要量为bi个。试问应该怎样组织下料活动，才能使得既满足需要，又节约原材料？第9页，共43页，星期日，2025年，2月5日设采用Bj方式下料的原材料数为xj，则上述问题可表示为：求一组整数变量xj(j=1，2，…，n)，使得第10页，共43页，星期日，2025年，2月5日（二）线性规划的数学模型以上例子表明，线性规划问题具有以下特征：①每一个问题都用一组未知变量（x1，x2，…，xn）表示某一规划方案，其一组定值代表一个具体的方案，而且通常要求