决策理论(线性规划与目标规划-)课件

线性规划与目标规划

2023/6/291目录一.线性规划概述二.线性规划问题及其数学模型三.单纯形法四.对线性规划的评价2023/6/292一、线性规划概述线性规划是运筹学的一个重要分支。线性规划是由丹捷格（G.B.Dantzig）在1947年发表的成果。所解决的问题是美国制定空军军事规划时提出的，并提出求解线性规划问题的单纯形法。而早在1939年前苏联的学者康托洛维奇在解决工业生产组织和计划问题时，已提出了类似线性规划的模型，并给出了“解乘数法”的求解方法，遗憾的是当时，并没有得到领导重视。自1947年丹捷格提出了一般线性规划问题求解的方法——单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛和深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。2023/6/293一、线性规划概述从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已经成为现代科学管理的重要手段之一。查恩斯（A.Charnes）与库伯（W.W.Cooper）继丹捷格之后，于1961年提出了目标规划，艾吉利（Y.Ijiri）提出用优先因子来处理多目标问题，使目标规划得以发展。近十多年来，斯姆李（S.M.Lee）与杰斯凯莱尼（V.Jaaskelainen）应用计算机处理目标规划问题，使目标规划在实际应用方面比线性规划更为广泛，更为管理者所重视。2023/6/294二、线性规划问题及其数学模型2.1问题的提出及模型建立在生产管理和经营活动中经常提出一类问题，即如何合理利用有限的人力、物力、财力等资源，以便得到更好的经济效果。例：某工厂在计划内要安排生产甲，乙两种产品，已知成产单位产品所需的设备台时及A,B两种原材料的消耗，如下表：甲乙设备128台时原材料A4016kg原材料B0412kg2023/6/295二、线性规划问题及其数学模型该工厂每生产一件产品甲可获利2元，每生产一件产品乙可以获利3元，问如何安排计划使该工厂获利最多？设x1、x2

分别表示在计划期内产品甲、乙的产量

那么：目标函数：maxz=2x1+3x2

满足约束条件：x1+2x2≤8

4x1

≤16

x1,x2≥0

4x2≤12甲乙设备128台时原材料A4016kg原材料B0412kg2023/6/296二、线性规划问题及其数学模型从上例中我们可以看出如下特征：（1）每个问题都用一组决策变量（x1,x2,x3,···xn）表示某一方案，这组决策变量的值就表示一个具体方案。一般这些变量取值是非负且连续的。（2）存在相关数据，同决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。（3）都有一个要求达到的目标，它可以用决策变量及其有关的价值系数构成的线性函数（称为目标函数）来表示。按照问题的不同，要求的目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式如下：2023/6/297二、线性规划问题及其数学模型一般形式：目标函数：max(min)z=c1x1+c2x2+···+cnxn(2-1)满足约束条件：a11x1+a12x2+···+a1nxn≤(=,≥)b1a21x1+a22x2+···+a2nxn≤(=,≥)b2···(2-2)am1x1+am2x2+···+amnxn≤(=,≥)bmx1,x2,···,xn≥0(2-3)在线性规划的数学模型中，式(2-1)称为目标函数，cj为价值系数；式(2-2)、式(2-3)称为约束条件；aij称为技术系数，bij称为限额系数；式(2-3)也称为非负约束条件。“=”即为标准形式。2023/6/298二、线性规划问题及其数学模型2.2图解法图解法简单直观，有助于了解线性规划问题求解的基本原理01234123x1x2Q4Q1Q2Q3X1+2X2=84X1=164X2=12(4,2)Z=2x1+3x22023/6/299二、线性规划问题及其数学模型2.2图解法上例中求解得到的问题的最优解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况：1）无穷多最优解（多重最优解）2）无界解3）无可行解当求解结果出现2）、3）情况时，一般说明线性规划问题的数学模型由错误。前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意。2023/6/2910二、线性规划问题及其数学模型2.2图解法01234123x1x2Q4Q1Q2Q3X1+2X2=84X1=164X2=12(4,2)Z=2x1+3x2从图解法中直观地见到，当线性规划问题的可行性域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在有界可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。简单地说，这也算线性规划的几何意义。2023/6/2911三、单纯形法3.1单纯形概念单纯形是美国数学家G.B.丹捷格（乔治·丹捷格被认为是线性规划之父）于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形是指0维中的点，一维中的线段，二维中的三角形，三维中的四面体，n维空间中的有n+1个顶点的多面体。例如在三维空间中的四面体，其顶点分别为（0,0,0），（1,0,0），（0,1,0），（0,0,1）。具体单位截距的单纯形的方程是∑xi≤1，并且xi≥0，i=1，2，···，m。2023/6/2912三、单纯形法3.2单纯形法求解线性规划的思路：一般的线性规划问题具有线性方程组的变量数大于方程个数，这是有不定的解。但可以从线性方程组中找到一个个的单纯形，每个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或者最小值为止。这样问题就得到了最优解。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。2023/6/2913三、单纯形法3.3单纯形法求解步骤纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代2023/6/2914三、单纯形法3.4单纯形法求解程序框图2023/6/2915三、对线性规划的评价线性规划是最优化问题中的重要领域之一。很多运筹学中的实际问题都可以用线性规划来表述。线性规划的某些特殊情况，例如网络流、多商品流量等问题，都被认为非常重要，并有大量对其算法的专门研究。很多其他种类的最优化问题算法都可以分拆成线性规划子问题，然后求得解。在历史上，由线性规划引申出的很多概念，启发了最优化理论的核心概念，