《线性代数 线性代数 A第五章线性规划or1》由会员分享，可在线阅读，更多相关《线性代数 线性代数 A第五章线性规划or1（126页珍藏版）》请在金锄头文库上搜索。
1、第五章 线性规划,1 运筹学的发展历史（Operations Research） 第二次世界大战高射炮阵地火力的配置，武器库设置问题等 英国雷达、新式武器演示及评价（1938）“作业研究” Erlang 1917的排队论； 美国数学家G.B.Dantzig的线性规划求解问题（1947）；T.C.Koopmans的运输问题;很多诺贝尔奖金得主的工作与运筹约有关。 60年代华罗庚“优选法、统筹方法”，国防科技的计划评审技术。 计算机运筹学的发展实际问题的最优与满意解。,2 OR的内容和分支,规划论:线性规划、非线性规划、整数规划、动态规划 图论与网络分析（哥尼斯堡七桥） 排队论 （打饭问题） 库存
2、理论 图与网络计划 对策论齐王赛马，矩阵对策 决策论 “管理就是决策”，决策的原则、决策的方法等 多目标规划等,3 OR特点,理论和实践，合理利用(人、财物、时、空等信息)寻求满意效果； 实践性强，寻最优化的方案； 系统的观点，全局性规划，多方法的总和（单个系统而非大系统）。 是以定量的模型化方法来描述和解决问题（本质）； 应用的普遍性。,运筹学的研究给管理工作带来巨大效益； 用数学语言揭示管理过程和规律； 用定量的方法来研究管理问题； 管理科学包括定性和定量两部分。,5 运筹学与管理科学,4 基本过程,分析和表达问题； 建立模型数学模型,网络模型,图论模型,仿真模型等； 求解模型，即寻找方案
3、； 检验(对解的最优性进行检验)； 方案的分析、评价、实施；,军事运筹学；农业运筹学；交通运输系统运筹学；公共卫生运筹学 运筹学与计算机科学运筹学与优化技术之间的关系,6 运筹学与控制论（Cybernatics）,优化与控制观点的区别 控制论的主要分之 控制论与运筹学、管理科学的关系,7 运筹学与其它学科的关系,第一节 线性规划问题（Linear Programming ）,教学目的： 重点引入线性规划问题的模型、几何性质、单纯形解法和线性规划的对偶定理。应理解和掌握线性规划的几何性质和求解原理，能针对实际问题，建立相应的线性规划模型。,重 点：线性规划问题的求解方法、解的基本性质以及对偶原理
4、。,难 点：线性规划的单纯形法求解思想、矩阵表述、对偶理论以及灵敏度分析,问题1：某工厂计划生产甲、乙两种产品。所需的设备台时及A、B两种原材料消耗，详见下表,该工厂每生产一件甲产品可获利2元，每生产一件乙产品可获利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
5、,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
6、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
7、=xl-xm，对应的目标系数仍为ck 。 4、当bi小于零的时候，在等式两边同时乘以-1即可。“小加、大减、一变二”,2.1、图解法: 图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。（用图解法求解,线性规划不需要化成标准型） 图解法的步骤：1、约束区域的确定 2、目标函数等值线3、平移目标函数等值线求最优值,2 线性规划图解法,线性规划解的几种可能情况1、唯一最优解2、无穷多最优解3、无可行解4、无有限最优解(无界解),例1： max z=2x1+ 3x2 x1+ 2x284x1 16x1，x20,有唯一解,画图步骤： 1、约束区域的确定 2、目标函数
8、等值线 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,
