数学建模与数学实验第一讲 建立规划模型.ppt

第一讲建立规划模型一、线性规划问题及其数学模型例23、线性规划解的概念4、线性规划解的情况例4例5，例65、图解法的启示6、线性规划单纯形法原理例7例86.5单纯形原理二、按照变量类型建立线性规划模型例9例10投资场所的选择问题例11厂址选择问题三、非线性规划模型例12（投资问题）例131、非线性规划的解例142、注意几点2.3四、目标规划问题及其数学模型可行域上的点虽然无穷多，但是其顶点是有限个，即线性规划问题的基可行解是有限个。那么从不可数的可行解中寻找最优解就过渡到了从有限个基可行解中寻找最优解。由图解法归纳得到单纯形法原理如下。（1）构造一个初始基可行解xB0；（2）从xB0出发，构造另外一个基，求其对应的基可行解xB1,其中两个基可行解对应的非零分量只有一个位置不同，故称为相邻基可行解（就是可行域相邻顶点）。对比它们所对应的目标函数值大小，如果从xB0出发，不能找到比xB0目标函数值大的相邻基可行解，xB0就是最优解。否则，用xB1替代xB0重复计算，直到终止计算。在建模过程的计算，这一计算过程用软件实现。在线性规划模型中，有时需要某些决策变量取整（甚至只取0和1），因此把线性规划模型分为一般（实数）线性规划模型，整数规划模型，0-1规划模型，混合规划模型。同时，在用某类软件计算规划模型时，一定要知道该软件能够处理的变量类型。例如，matlab的优化模块，能够处理实数型决策变量，也可以处理0-1变量的决策变量，但是目前还不能自由处理一般整数规划问题。但lingo优化软件，能够处理一般实数决策变量，也能够处理一般整数的决策变量（当然就能够处理0-1变量）。下面用例子来说明。例9某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运限制如下表1401365托运限制340273乙24195甲每件利润/百元每件重量/100kg每件体积/m3货物且甲种货物最多托运4件，问两种货物各托运多少件，可获利最大。变量设置：这里字母不分大小写。Xi：表示第i种货物的托运件数,i=1表示甲,i=2表示乙;Wi：表示第i种货物的单件重量；Vi：表示第i种货物的单件体积；Ci：表示第i种货物的单件利润；B1：表示货物的总体积限制；B2：表示货物的总重量限制；Z：表示总利润建立模型：总利润：z=c1x1+c2x2(百元)托运体积限制：托运的重量限制：货物甲的数量限制：货物属性限制：两种货物都按件数计数，不可分割，故x1,x2都取整数。数学模型归纳为这里，x1,x2均要求取整数，故此线性规划为整数线性规划。用lingo软件可以识别决策变量，很方便求解。某公司计划在市区的东、南、西、北四个区建立销售门面，拟议中有10个位置Ai(i=1,2,…,10)可供选择，考虑到各个地区居民消费水平以及居民的居住密度，规定在东区A1,A2,A3三个点中至少选择两个；在西区A4,A5两个点中至少选择一个；在南区A6,A7两个点中至少选择一个；在北区A8,A9,A10三个点中至少选择2个。Ai各个点的设备投资以及每年可获利润由于地点不同都不一样，预测情况如下表61584825302022504036利润18016014080907080150120100投资额A10A9A8A7A6A5A4A3A2A1另外，投资总额不能超过720万元，问应该选择哪几家销售点，可使得年利润为最大？[分析]对每个位置Ai来说，都只有两种选择，要么建销售网点，要么不建，二者必须其一。针对选择的彼此互斥性，可以用二元变量：在第i个点建立销售网点在第i个点不建销售网点i=1,2,…,10这样的决策变量，有如下性质：（1）xi+xj=1：xi和xj有且只有一个取1，另外一个取0；（2）xi+xj=1：xi和xj最多取1；（3）xi+xj=1：xi和xj至少一个取1；（4）kxj：要么取k，要么取0；（5）x1+x2+…+xm=p(p=m)：m个中恰好取p个。建立模型：在东区，三个点最多取2个，则在西区，两个点至少取1个，则在南区，两个点至少取1个，则在北区，三个点至少取2个，则由于总投资额不超过720万元，如果该点被选中，则该点的投资额加进总额，如果没有被选中，则该点投资额不用加，根据0-1变量的性质有，若设第i个点的投资额为ai,i=1,2,…,10;第i个点的利润为ci,i=1,2,…,10