线性规划第一.ppt

*第30页，共42页，星期日，2025年，2月5日*由于直线I是等直线，而且斜率相等，它们又是一系列平行线，因此只要画出其中任意的一条线，将它们平移到某个与凸集相交的极限位置，所得的交点就是既满足约束条件(在凸集范围内)，又使f值为最大的最优解。如下图中的点，X1=350，X2=100，f=21500。第31页，共42页，星期日，2025年，2月5日*第1页，共42页，星期日，2025年，2月5日*1.线性规划的概念例6.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：?产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500?第2页，共42页，星期日，2025年，2月5日*问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3x1+2x2≤65；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1+x2≤40；1.线性规划的概念第3页，共42页，星期日，2025年，2月5日*对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2≤75；另外，产品数不可能为负，即x1,x2≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：1.线性规划的概念第4页，共42页，星期日，2025年，2月5日*目标函数Maxz=1500x1+2500x2?约束条件s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0?1.线性规划的概念第5页，共42页，星期日，2025年，2月5日*这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2的取值。1.线性规划的概念第6页，共42页，星期日，2025年，2月5日*一般形式目标函数：Max(Min)z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2...am1x1+am2x2+…+amnxn≤(=,≥)bmx1，x2，…，xn≥01.线性规划的概念第7页，共42页，星期日，2025年，2月5日*标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥01.线性规划的概念第8页，共42页，星期日，2025年，2月5日*可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:1.线性规划的概念第9页，共42页，星期日，2025年，2月5日*1.极小化目标函数的问题：设目标函数为Minf=c1x1+c2x2+…+cnxn