二线性规划与单纯形法.PPTVIP

第一章 线性规划与单纯形法 第一节 线性规划及其数学模型 第二节 线性规划的图解法 第三节 线性规划解的概念 第四节 单纯形法 第五节 单纯形法的进一步讨论 第六节 应用举例 一、问题的提出 一、问题的提出 例题1.2——配方问题 　　　养兔饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：需要采购各种饲料各多少克，既能满足养兔的营养要求又使费用最省。 例1.2的数学模型 设采购饲料I x1kg;饲料II x2kg;饲料III x3kg…… 目标函数：最省钱 　　　　　　　　　　minZ=0.2x1+0.7x2+0.4x3+0.3x4+0.8x5 约束条件： 3x1+2x2+x3+6x4+18x5 ≥700 营养要求： x1+0.5x2+0.2x3+2x4+0.5x5 ≥30 0.5x1+x2+0.2x3+2x4+0.8x5 =200 非负性要求：x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0 　 一、问题的提出 二、 线性规划的标准形 第二节 线性规划的图解法 第三节 线性规划解的概念与性质 第三节 线性规划解的概念与性质 　 基本最优解：使目标函数达到最优的基本可行解，称为基本最优解。 最优基：基本最优解对应的基，称为最优基。 退化基本可行解：基本可行解中存在取零值的基变量，则称该基本可行解为退化的基本可行解。 退化基：退化的基本可行解对应的基，称为退化基。 例1.8 求线性规划问题的所有基矩阵,指出其中的基可行解，并确定最优解。 　二、线性规划问题解的基本性质 定理1　线性规划问题的可行解集 　　　　是一个凸集 定理2　若一个线性规划有可行解，则它必有基可行解。 定理3　设线性规划的可行解集为D，则D的顶点（极点）就是线性　　　　　规划的基可行解。 定理4　若线性规划问题有最优解，则一定存在一个基可行解是最优解。即最优解一定可以在D的顶点上达到。 定理5　若线性规划存在两个相异的基可行解X（1），X（2）均为最　优解，则以X（1），X（2）为端点的线段上的一切点 　　　X＝α X（1）＋（1－α） X（2），0≤α≤1　也都是线性规划的最优解。　 第三节 线性规划解的概念与性质 注意：这并不是说，只有极点才能使目标函数值最大，其它点不能。而是说，如在其它点上使目标函数值达到最大，则一定可以找到一个极点X（m）使目标函数值达到此最大值。 有了定理4，求线性规划问题的最优解可不必在无穷多的可行解中有哪些信誉好的足球投注网站，只需在有限个基本可行解中有哪些信誉好的足球投注网站即可。虽然基本可行解至多有　　个，当n、m较大时， 仍是一个很大的数字。 第四节 单纯形法 一、单纯形法的基本思想 第四节 单纯形法 二、单纯形表 第三节 线性规划解的概念与性质　 找出一个初始基可行解 是否最优 转移到另一个基本可行解 （找出更优的目标函数值） 最优解 是 否 循 环 核心是：变量迭代 结束 例1.9 以1.1为例来讨论用单纯形法求解线性规化问题。 标准式为 (1.11) (1.12) 约束方程(1.12)的系数矩阵 x3，x4，x5的系数列向量线性独立 可以得到一个基 对应于B的变量 x3，x4，x5为基变量，从(1.12)中 可以得到 (1.13) 将(1.13)代人目标函数(1.11)得到 当令非基变量 ，便得到 z=0。这时得到一个基可行解X(0) 这个基可行解表示：工厂没有安排生产产品I、II；资源都没有被利用，所以工厂的利润指标z＝0． (1.14) (1.13) 从分析目标函数的表达式(1.14)可以看到： 非基变量x1，x2(即没有安排生产产品I，II)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品I或II，就可以使工厂的利润指标增加。 (1.14) 分析(1.13)，当将x2定为换入变量后，必须从x3，x4，x5中换出一个，并保证其余的都是非负，即x3，x4，x5≥0。 当x1=0，由(1.13)式得到 (1.15) 可以看出，当 式(1.15)成立。 因X2=3时， X5=0，所以决定用x2去替换x5。 (1.13) 将(1.13)中x2的位置与x5位置对换．得到 上式变换得到 (1.17) (1.16) (1.13) 将(1.17)代人目标函数(1.11)得到 令非基变量xl=x5=0，得到z=9，并得到另一个基可行解X(1) 将x1定为换入变量后， x2 ，x3，x4 中换出