2线性规划.ppt
《2线性规划.ppt》由会员分享,可在线阅读,更多相关《2线性规划.ppt(82页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、线线 性性 规规 划划(Linear Programming)线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题的求解方法线性规划问题的求解方法线性规划的图解法线性规划的图解法线性规划的单纯形法线性规划的单纯形法单纯形法的进一步讨论单纯形法的进一步讨论线性规划模型的应用线性规划模型的应用 为了完成一项任务或达到一定的目的,怎样用最少的为了完成一项任务或达到一定的目的,怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的,这个过程就是规划。达到一定的目的,这个过程就是规划。例一、有一正方形铁皮,如何截取例一、有一
2、正方形铁皮,如何截取 x x 使容积为最大?使容积为最大?xa此为无约束极值问题此为无约束极值问题一、线性规划问题及其数学模型线性规划问题及其数学模型(一)、问题的提出一)、问题的提出 设设 备备产产 品品 A B C D利润(元)利润(元)2 1 4 0 2 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12 例二、已知资例二、已知资料如下表所示,料如下表所示,问如何安排生产问如何安排生产才能使利润最大才能使利润最大?或如何考虑利?或如何考虑利润大,产品好销。润大,产品好销。模模 型型max Z=2x1+3x2 x1 0,x2 0s.t.2x1+2x2 12 x1+2x2 8
3、4x1 16 4x2 12此为带约束的极值问题此为带约束的极值问题问题中总有未知的变量,需要我们去解决。问题中总有未知的变量,需要我们去解决。要求:有目标函数及约束条件,一般有非负条件要求:有目标函数及约束条件,一般有非负条件存在,由此组成规划数学模型。存在,由此组成规划数学模型。如果在规划问题的数学模型中,变量是连续的如果在规划问题的数学模型中,变量是连续的(数值取实数)其目标函数是有关线性函数(一次方)(数值取实数)其目标函数是有关线性函数(一次方),约束条件是有关变量的线性等式或不等式,这样,约束条件是有关变量的线性等式或不等式,这样,规划问题的数学模型是线性的。反之,就是非线性的规划问
4、题的数学模型是线性的。反之,就是非线性的规划问题(其中一个条件符合即可)。规划问题(其中一个条件符合即可)。(二)、数学模型(二)、数学模型 1 1、目标函数:目标函数:约束条件:约束条件:2 2、线性规划数学模型的一般形式、线性规划数学模型的一般形式也可以记为如下形式也可以记为如下形式:目标函数:目标函数:约束条件:约束条件:如将上例用表格表示如下:如将上例用表格表示如下:设变量设变量 产产 品品 j 设设 备备 i 有效台时有效台时 利润利润 向向 量量 形形 式:式:矩阵形式:矩阵形式:规规划划确定型确定型随机型随机型静态规划静态规划动态规划动态规划线线 性规性规 划划非线性规划非线性规
5、划 整数规划整数规划 非整数规划非整数规划整数规划整数规划非整数规划非整数规划3、规划类型、规划类型一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但需将适用于任意变量、但需将一般形式变成标准形式一般形式变成标准形式二、线性规划问题的求解方法二、线性规划问题的求解方法(一)、求解方法(一)、求解方法1 1、解的概念、解的概念 可行解:满足约束条件可行解:满足约束条件、的解为可行解。的解为可行解。所有解的集合为可行解的集或可行域。所有解的集合为可行解的集或可行域。最优解:使目标函数达到最大值的
6、可行解。最优解:使目标函数达到最大值的可行解。基:基:B B是矩阵是矩阵A A中中mnmn阶非奇异子矩阵阶非奇异子矩阵(B0B0),),则则B B是一个基。是一个基。则称则称 Pj(j=1 2 m)为基向量。为基向量。Xj 为基变量,否则为非基变量。为基变量,否则为非基变量。(二)、线性规划问题的解(二)、线性规划问题的解 基本解:满足条件基本解:满足条件,但不满足条件,但不满足条件的的所有解,最多为所有解,最多为 个。个。基本可行解:满足非负约束条件的基本基本可行解:满足非负约束条件的基本解,简称基可行解。解,简称基可行解。可行基:对应于基可行解的基称为可行基。可行基:对应于基可行解的基称为
7、可行基。非可行解非可行解可可行行解解基解基解基可行解基可行解2 2、解的基本定理、解的基本定理 线性规划问题的可行域是凸集(凸多边形)。线性规划问题的可行域是凸集(凸多边形)。凸集凸集凸集凸集不是凸集不是凸集顶顶 点点 最优解一定是在凸集的某一顶点实现(顶点最优解一定是在凸集的某一顶点实现(顶点数目不超过数目不超过 个)个)先找一个基本可行解,与周围顶点比较,如先找一个基本可行解,与周围顶点比较,如不是最大,继续比较,直到找出最大为止。不是最大,继续比较,直到找出最大为止。3 3、解的情况、解的情况唯唯 一一 解解无无 穷穷 解解无无 界界 解解无可行解无可行解有最优解有最优解无最优解无最优解
8、 建立直角坐标建立直角坐标 ,图中阴影部分及边,图中阴影部分及边界上的点均为其解,是由约束条件来反映的。界上的点均为其解,是由约束条件来反映的。例一、例一、三、图三、图 解解 法法01 2 3 4 5 6 7 8 1 2 3 4 5 6 作作 图图 最最 优优 解:解:x1=4 x2=2有唯一最优解,有唯一最优解,Z=14Z=14x2 x1(4 2)例二、例二、例三、例三、无穷多最优解无穷多最优解无界解无界解x1x1x2 x2 x1x2 无可行解无可行解例四、例四、练习练习1 效效 产品产品机床机床 率率 A B机床台数机床台数 30 40 40 55 30 40 23 37 20 2 2、某
9、车间用三种不同型号某车间用三种不同型号的机床的机床、,加工,加工A A、B B两种零件,机床台数、生产两种零件,机床台数、生产效率如表所示。问如何合理效率如表所示。问如何合理安排机床的加工任务,才能安排机床的加工任务,才能使生产的零件总数最多?使生产的零件总数最多?1 1、某工厂生产、某工厂生产A A1 1、A A2 2 两种两种产品,产品,每件可获利润每件可获利润1515、2020元。每个产品都经过三道元。每个产品都经过三道工序,资料如表所示。工厂工序,资料如表所示。工厂应如何安排生产计划使获得应如何安排生产计划使获得的总利润最多?试写出此问的总利润最多?试写出此问题的数学模型。题的数学模型
10、。工工 产品产品工序工序 时时 A A1 1 A A2 2可用工时可用工时 3 2 800 2 3 800 1 1 350习习 题题 13 3、用图解法求解下面的线性规划问题:、用图解法求解下面的线性规划问题:x1x2 123(2)x1x2 123(1)(一)、基本思想(一)、基本思想 将模型的一般形式变成标准形式,再根据标准型模型,将模型的一般形式变成标准形式,再根据标准型模型,从可行域中找一个基本可行解,并判断是否是最优。如果从可行域中找一个基本可行解,并判断是否是最优。如果是,获得最优解;如果不是,转换到另一个基本可行解,是,获得最优解;如果不是,转换到另一个基本可行解,当目标函数达到最
11、大时,得到最优解。当目标函数达到最大时,得到最优解。(二)、线性规划模型的标准形式(二)、线性规划模型的标准形式1 1、标准形式、标准形式四、单纯形法四、单纯形法 2 2、特征:、特征:.目标函数为求极大值,也可以用求极小值;目标函数为求极大值,也可以用求极小值;.所有约束条件(非负条件除外)都是等式,所有约束条件(非负条件除外)都是等式,右端常数项为非负;右端常数项为非负;.变量为非负。变量为非负。3、转换方式:、转换方式:.目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ,则可将目标函,则可将目标函数乘以(数乘以(1 1),可化为求极大值问题。),可化为求极大值问题。也就是
12、:令也就是:令 ,可得到上式。,可得到上式。即即.约束方程的转换:由不等式转换为等式。约束方程的转换:由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量.变量的变换变量的变换 若存在取值无约束的变量若存在取值无约束的变量 ,可令,可令 其中:其中:例例 一、将下列线性规划问题化为标准形式一、将下列线性规划问题化为标准形式为无约束(无非负限制)为无约束(无非负限制)解解:用用 替换替换 ,且,且 ,将第将第3 3个约束方程两边乘以个约束方程两边乘以(1 1)将极小值问题反号,变为求极大值将极小值问题反号,变为求极大值标准形式如下:标准形式如下:引入变量引入变量例二、将线性规划问
13、题化为标准型例二、将线性规划问题化为标准型为无约束为无约束解:解:(三)、单纯形法(三)、单纯形法例一、例一、变成标准型变成标准型约束方程的系数矩阵约束方程的系数矩阵为基变量为基变量为非基变量为非基变量I I 为单位矩阵且线性独立为单位矩阵且线性独立令:令:则:则:基本可行解为基本可行解为(0 0 12 8 16 120 0 12 8 16 12)此时,此时,Z=0Z=0 然后,找另一个基本可行解。即将非基变量然后,找另一个基本可行解。即将非基变量换入基变量中,但保证其余的非负。如此循环换入基变量中,但保证其余的非负。如此循环下去,直到找到最优解为止。下去,直到找到最优解为止。注意:为尽快找到
14、最优解,在换入变量时有一定注意:为尽快找到最优解,在换入变量时有一定的要求。如将目标系数大的先换入等。的要求。如将目标系数大的先换入等。找出一个初始可行解找出一个初始可行解是否最优是否最优转移到另一个目标函数转移到另一个目标函数(找更大的基本可行解)(找更大的基本可行解)最优解最优解是是否否循循环环直到找出为止,核心是:变量迭代直到找出为止,核心是:变量迭代结束结束其步骤总结如下:其步骤总结如下:当当 时,时,为换入变量为换入变量确定换出变量确定换出变量为换出变量为换出变量接下来有下式:接下来有下式:用高斯法,将用高斯法,将 的系数列向量换为单位列向量,其的系数列向量换为单位列向量,其步骤是:
15、步骤是:结果是:结果是:代入目标函数:代入目标函数:有正系数表明:还有潜力可挖,没有达到最大值;有正系数表明:还有潜力可挖,没有达到最大值;此时:令此时:令 得到另一个基本可行解得到另一个基本可行解 (0,3,6,2,16,0)有负系数表明:若要剩余资源发挥作用,就必须有负系数表明:若要剩余资源发挥作用,就必须支付附加费用。当支付附加费用。当 时,即不再利用这些资源。时,即不再利用这些资源。如此循环进行,直到找到最优为止。如此循环进行,直到找到最优为止。本例最优解为:本例最优解为:(4,2,0,0,0,4)(四)、单纯形表(四)、单纯形表判定标准:判定标准:若求若求 或或例例 题:题:cj 2
16、 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1-Z0 2 3 0 0 0 012/28/212/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x6000 x3x4x516 4 0 0 0 1 0 -Z3x23010001/42620100-1/210010 0-1/2cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60003x3x4x5x262163 2 0 1 0 0 -1/2 1 0 0
17、 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/4-Z-9 2 0 0 0 0 -3/46/2216/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/44412-Z-13 0 0 0 -2 0 1/4cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x6 x1x5x2 4402 0 0 2 -4 0 1 1 0 1 -1 0 0 0 0 -4 4 1 0 0 1 -1/2
18、 1 0 0-Z-14 0 0 -1/2 -1 0 0 0 0 0 -2 0 1/4-13-Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cjcj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60203x3 x1x6 x2 0442 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0-Z-14 0 0 0 -3/2 -1/
19、8 0 0 0 0 -2 0 1/4-13-Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cj练习练习 0 0 -1/12 -7/24-33/4-Z x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cj15/43/4011/4-1/810-1/125/24(一)、模型情况一)、模型情况 变变 量:量:xj0 xj0 xj无约束无约束 结结1、组成、组成 约束条件:约束条件:=b 目标函数:目标函数:m
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划
限制150内