您所在位置：网站首页 > 中学教育 > 高中教育线性代数线性代数 A第五章线性规划or1

线性代数线性代数 A第五章线性规划or1

126页

卖家[上传人]：woxinch****an2018

文档编号：56924693

上传时间：2018-10-17

文档格式：PPT

文档大小：1.04MB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

12 金贝

/ 126 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、第五章线性规划,1 运筹学的发展历史（Operations Research）第二次世界大战高射炮阵地火力的配置，武器库设置问题等英国雷达、新式武器演示及评价（1938）“作业研究” Erlang 1917的排队论；美国数学家G.B.Dantzig的线性规划求解问题（1947）；T.C.Koopmans的运输问题;很多诺贝尔奖金得主的工作与运筹约有关。 60年代华罗庚“优选法、统筹方法”，国防科技的计划评审技术。计算机运筹学的发展实际问题的最优与满意解。,2 OR的内容和分支,规划论:线性规划、非线性规划、整数规划、动态规划图论与网络分析（哥尼斯堡七桥）排队论（打饭问题）库存理论图与网络计划对策论齐王赛马，矩阵对策决策论 “管理就是决策”，决策的原则、决策的方法等多目标规划等,3 OR特点,理论和实践，合理利用(人、财物、时、空等信息)寻求满意效果；实践性强，寻最优化的方案；系统的观点，全局性规划，多方法的总和（单个系统而非大系统）。是以定量的模型化方法来描述和解决问题（本质）；应用的普遍性。,运筹学的研究给管理工作带来巨大效益；用数学语言揭示管理过

2、程和规律；用定量的方法来研究管理问题；管理科学包括定性和定量两部分。,5 运筹学与管理科学,4 基本过程,分析和表达问题；建立模型数学模型,网络模型,图论模型,仿真模型等；求解模型，即寻找方案；检验(对解的最优性进行检验)；方案的分析、评价、实施；,军事运筹学；农业运筹学；交通运输系统运筹学；公共卫生运筹学运筹学与计算机科学运筹学与优化技术之间的关系,6 运筹学与控制论（Cybernatics）,优化与控制观点的区别控制论的主要分之控制论与运筹学、管理科学的关系,7 运筹学与其它学科的关系,第一节线性规划问题（Linear Programming ）,教学目的：重点引入线性规划问题的模型、几何性质、单纯形解法和线性规划的对偶定理。应理解和掌握线性规划的几何性质和求解原理，能针对实际问题，建立相应的线性规划模型。,重点：线性规划问题的求解方法、解的基本性质以及对偶原理。,难点：线性规划的单纯形法求解思想、矩阵表述、对偶理论以及灵敏度分析,问题1：某工厂计划生产甲、乙两种产品。所需的设备台时及A、B两种原材料消耗，详见下表,该工厂每生产一件甲产品可获利2元，每生产

3、一件乙产品可获利3元，问如何安排生产计划，可使利润最大？,1.1 线性规划问题及其数学模型,解：设x1，x2分别为甲、乙产品的数量，则有约束条件 x1 + 2x28 4x1 16 4x212x10，x20，称x1，x2为决策变量,目标函数 max z=2x1+3x2,问题2：运输问题的运价、产量、销量如下表，如何安排调运，运费最小？,解：设 xij为从产地运往销地的物资数量(i=1,2；j=1,2,3), 则有目标函数：min z=2 x11+x12+3 x13+2x21+ 2x22+4x23约束条件: x11+x12+ x13 = 50x21+ x22+x23 = 30x11+ x21 =40x12+ x22 =15x13+ x23 =25xij0 i=1,2；j=1,2,3,总结：线性规划三要素：决策变量、目标函数、约束条件线性规划的特点:目标线性、约束条件为线性不等式或等式,一般情况下，其值均是正的,其中：C价值向量A系数矩阵b资源向量,其它表示形式：形式：max(min)Z= cixjs.t aijxj,=,bi，i=1,2,mxj 0，j=1,2,n向量形式: max(mi

4、n)Z=cixjs.t Pjxj,=,bi, i=1,2,mxj 0，j=1,2,n矩阵形式: max(min)Z=CXs.t AX ,=,bX 0,线性规划问题模型的标准型,任意线性规划模型转化为标准型的方法,1、目标最小化： min Z=max(Z)=max Z 2、约束条件为不等式：“” 引进非负松弛变量xk0,(减去)松弛变量,对应于xk的目标系数取为零。“” 引进松弛变量xl0, (加入)松弛变量,对应于xl 的目标系数取为零。 3、决策变量xk是自由变量(无非负限制)，或xj有上下界限制是可以引进新的变量，转化为变量0形式。例如xk是自由变量，引进xl0, xm0,新变量，令xk =xl-xm，对应的目标系数仍为ck 。 4、当bi小于零的时候，在等式两边同时乘以-1即可。“小加、大减、一变二”,2.1、图解法: 图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。（用图解法求解,线性规划不需要化成标准型）图解法的步骤：1、约束区域的确定 2、目标函数等值线3、平移目标函数等值线求最优值,2 线性规划图解法,线性规划解的几种可能情况1、

5、唯一最优解2、无穷多最优解3、无可行解4、无有限最优解(无界解),例1： max z=2x1+ 3x2 x1+ 2x284x1 16x1，x20,有唯一解,画图步骤： 1、约束区域的确定 2、目标函数等值线 3、平移目标函数等值线求最优值,有无穷多解,两个顶点处达到最优解,例2：,约束条件围不成区域 (又称矛盾方程),无可行解,例3：,Max z=4x1+3x2 -3x1+2x2 6 s.t -x1+3x2 18 x1, x2 0,无有限最优解(无界解),例4：,线性规划的几何特性：,线性规划问题若有最优解,一定在其可行域的顶点达到;有最优解(唯一最优解必在一个顶点达到或无穷多最优解至少在两个顶点达到);无解(可行域为空集或目标函数无有限极值),图解法得出线性规划问题解的几种情况,问题 : 围成无界区域就不能有唯一解吗?,列向量 x=(x1，x2，xm）T为m维列向量。xRn 线性相关一组向量v1,vn,如果有一组不全为零的系数1, ,n,使得: 1 v1+nvn=0 则称v1,vn 是线性相关的. 线性无关一组向量v1,vn,如果对于任何数1,n,若要满足: 1 v1+nvn=0 ,则必有系数1=n=0,(全为零)则称v1,vn线性无关. 矩阵A的秩设A为一个mn阶矩阵(m0的数乘（2）式在分别与（1）相加和相减，这样得到 (x1-1)P1+(x2-2)P2+(xm-m)Pm=b (x1+1)P1+(x2+2)P2+(xm+m)Pm=b,

《线性代数线性代数 A第五章线性规划or1》由会员woxinch****an2018分享，可在线阅读，更多相关《线性代数线性代数 A第五章线性规划or1》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源