运簿 92g 线性规划(1) 熊中槽教授
运筹学 熊中楷教授 线性规划（1）
第一章:线性规劍( Chapterl: linear programming I. Examples and models of LP Graphic solution of lP There are three case in graphic solution of LP as follows: (1)a unique optimal feasible solution (2)an infinite number of optimal solution (3) unbounded feasible solution 狼中槽教授
运筹学 熊中楷教授 第一章：线性规划（1） Chapter1:linear programming 1． Examples and models of LP Graphic solution of LP There are three case in Graphic solution of LP as follows: （1）a unique optimal feasible solution （2）an infinite number of optimal solution （3）unbounded feasible solution
第一章:线性规劍( 第一章线性规划及单纯形法 .1一般线性规划问题的数学模型 典型引例:某工厂在计划期内安排甲,乙两种产品, 已知生产单位产品所消耗资源以及产生的利润如下表 狼中槽教授
运筹学 熊中楷教授 第一章 线性规划及单纯形法 1.1 一般线性规划问题的数学模型 典型引例： 某工厂在计划期内安排甲，乙两种产品， 已知生产单位产品所消耗资源以及产生的利润如下表： 第一章：线性规划（1）
第一章:线规划( 例:某工厂在计划期内安排甲,乙两种产品,已知生产单位产品 所消耗资源以及产生的利润如下表 甲产品 资源量 设备 8台时 原材料A4 16公斤 原材料B0 2043 12公斤 产生的利润2元 问题:如何计划使得工厂利润最大? 分析:决策中的关键变量是什么?变量中的相互因果关系是什么? 怎样用数学公式来建立有用的模型? 狼中槽教授
运筹学 熊中楷教授 例： 某工厂在计划期内安排甲，乙两种产品，已知生产单位产品 所消耗资源以及产生的利润如下表： 甲产品 乙产品 资源量 设备 1 2 8 台时 原材料A 4 0 16公斤 原材料B 0 4 12公斤 产生的利润 2元 3元 问题：如何计划使得工厂利润最大？ 分析：决策中的关键变量是什么？变量中的相互因果关系是什么？ 怎样用数学公式来建立有用的模型？ 第一章：线性规划（1）
第一章:线性规劍( 思路:利润最大 资源有约束 Max 2x1+3x2 一般形式 X1+2X2=0 X2>=0 狼中槽教授
运筹学 熊中楷教授 思路：利润最大 资源有约束 Max 2X1 +3X2 X1 + 2X2 =0 X2>=0 第一章：线性规划（1） 一般形式 Max CX AX=0
第一章:线性规劍( 1.线性规划定义 求一组变量x,x2,…x的值,使之满足关于这组变量的若干个线性等式或 不等式的约束条件,而且使这组变量的一个线性函数取到极大值(或极小值)。 这些变量称为决策变量,所要优化的函数称为目标函数,决策变量是取实数值 的连续变量。这样的问题称为线性规划 2.线性规划的一般形式与标准形式 线性规划的解的相关定义 可行解满足线性规划所有约束条件的各变量的一组值X=(x,x2,…,xn)T, 称为线性规划问题的可行解。全部可行解的集合称为可行域。 最优解使线性规划的目标函数达到以最优值(依照具体问题,或者是极大值, 或者是极小值)的可行解称为线性规划问题的最优解。 上述两个概念,对于一般形式、标准形式都适用,而下述五个概念,仅适用于 标准形式。 狼中槽教授
运筹学 熊中楷教授 1．线性规划定义 求一组变量x1，x2，…，xn的值，使之满足关于这组变量的若干个线性等式或 不等式的约束条件，而且使这组变量的一个线性函数取到极大值（或极小值）。 这些变量称为决策变量，所要优化的函数称为目标函数，决策变量是取实数值 的连续变量。这样的问题称为线性规划。 2．线性规划的一般形式与标准形式 3．线性规划的解的相关定义 可行解 满足线性规划所有约束条件的各变量的一组值X=（x1，x2，…，xn）T ， 称为线性规划问题的可行解。全部可行解的集合称为可行域。 最优解 使线性规划的目标函数达到以最优值（依照具体问题，或者是极大值， 或者是极小值）的可行解称为线性规划问题的最优解。 上述两个概念，对于一般形式、标准形式都适用，而下述五个概念，仅适用于 标准形式。 第一章：线性规划（1）
第一章:线性规劍( 基设标准形式线性规划的约束方程组为AX=b,,。若B是系数矩阵A的m阶满 秩子矩阵,则称B是线性规划问题的一个基。B中的每一个列向量称为基向量, 共m个,与基向量对应的变量称为基变量。B以外的列向量称为非基向量,对 应的变量称为非基变量,共(n-m)个。 基解在标准形式线性规划的约束方程组中,对应基B,令所有非基变量都等于 求解约束方程组AX=b,可惟一得出基变量的一组值,这些值和取零的非 基变量的值合起来,称为线性规划问题的基解或基本解。 基的个数不超过,一个基对应一个基解,故基解的个数也不超过。基解中非零 分量的个数不会大于约束方程的个数m。若一个基解的基变量中有取零值的, 则此基解称为退化的,否则称为非退化的。 基可行解对于标准形式的线性规划,如果一个基解X还满足变量取值非负性的 约束条件X≌0,则称此基解为基可行解或基本可行解 最优基如果一个基可先行解是最优解,则它所对应的可行基叫做最优基。 狼中槽教授
运筹学 熊中楷教授 基 设标准形式线性规划的约束方程组为AX=b，，。若B是系数矩阵A的m阶满 秩子矩阵，则称B是线性规划问题的一个基。B中的每一个列向量称为基向量， 共m个，与基向量对应的变量称为基变量。B以外的列向量称为非基向量，对 应的变量称为非基变量，共（n－m）个。 基解 在标准形式线性规划的约束方程组中，对应基B，令所有非基变量都等于 零，求解约束方程组AX=b，可惟一得出基变量的一组值，这些值和取零的非 基变量的值合起来，称为线性规划问题的基解或基本解。 基的个数不超过，一个基对应一个基解，故基解的个数也不超过。基解中非零 分量的个数不会大于约束方程的个数m。若一个基解的基变量中有取零值的， 则此基解称为退化的，否则称为非退化的。 基可行解 对于标准形式的线性规划，如果一个基解X还满足变量取值非负性的 约束条件X≥0，则称此基解为基可行解或基本可行解。 最优基 如果一个基可先行解是最优解，则它所对应的可行基叫做最优基。 第一章：线性规划（1）
第一章:线性规劍( 图解法 引例 目标函数:MAXZ=X1+3X26 满足的约束条件: 51+10X2=50 5X1+10X2=1 n"Z=X1+3X2 0123456789101121314 0 X1+3X2=常数:目标函数的等值线 由右图知,在D点得最优解。D点坐标(2,4),此时maxZ=14 画出各种情况对应的图形 狼中槽教授
运筹学 熊中楷教授 图解法 引例： 目标函数：MAX Z= X1+3X 2 满足的 约束条件： 5 X1+10 X2=1 X2=0 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5X1+10X2=50 X1+X2=1 X2=4 Z=X1+3X2 X1+3X 2 = 常数 ： 目标函数的等值线 由右图知，在D点得最优解。D点坐标（2，4），此时maxZ=14 画出各种情况对应的图形： 第一章：线性规划（1）
第一章:线性规劍( 图解法基本要求 能正确地按图解法的步骤画出图来解答题目,并会判定解的类型 知识要点 (1)图解法仅适用于两个变量的线性规划问题,求解时按原来题目对目标函数的 优化要求去求解即可,不必将求极小值化为求极大值。 三个变量的线性规划问题用图解法求解时,可行域是三维空间的多面体,很难用平 面上的图形画得清晰准确,目标函数对应的是三维空间中的平面,难以通过平面上 画出的立体图形求出最优解。所以,从理论上讲,三个变量的线性规划也有图解法, 但实际上不可行。多于三个变量的线性规划涉及到在高于三维的向量空间中求解优 化问题,而三维以上的空间已无直观的几何意义,故不存在相应的图解法。 (2)线性规划问题的解的情况共有四种 (3)线性规划问题如果有最优解,则可行域的某个顶点必定是最优解。为求最优 解,可以先计算可行域某个顶点处的目标函数值,再考察它周围相邻顶点的目标函 数值是否比这个值更优,如果为否,则该顶点就是最优解(或最优解之一),否则 转到比这个点的目标函数值更优的另一顶点,重复上述过程,直到找出对应最优解 的顶点。 狼中槽教授
运筹学 熊中楷教授 图解法基本要求 能正确地按图解法的步骤画出图来解答题目，并会判定解的类型。 知识要点 （1）图解法仅适用于两个变量的线性规划问题，求解时按原来题目对目标函数的 优化要求去求解即可，不必将求极小值化为求极大值。 三个变量的线性规划问题用图解法求解时，可行域是三维空间的多面体，很难用平 面上的图形画得清晰准确，目标函数对应的是三维空间中的平面，难以通过平面上 画出的立体图形求出最优解。所以，从理论上讲，三个变量的线性规划也有图解法， 但实际上不可行。多于三个变量的线性规划涉及到在高于三维的向量空间中求解优 化问题，而三维以上的空间已无直观的几何意义，故不存在相应的图解法。 （2）线性规划问题的解的情况共有四种： （3）线性规划问题如果有最优解，则可行域的某个顶点必定是最优解。为求最优 解，可以先计算可行域某个顶点处的目标函数值，再考察它周围相邻顶点的目标函 数值是否比这个值更优，如果为否，则该顶点就是最优解（或最优解之一），否则 转到比这个点的目标函数值更优的另一顶点，重复上述过程，直到找出对应最优解 的顶点。 第一章：线性规划（1）
运簿 92g 线性规划(2) 熊中槽教授
运筹学 熊中楷教授 线性规划（2）