现代设备管理方法 第四章线性规划.docVIP

第四章　线性规划 　　在企业的经营管理中，常常遇到如何在现有条件下，获得最大经济效益的诸多方面的具体问题，如如何磁品产量和质量的要求下，合理配置设备，合理储存备件，合理制定生产计划，以及合理运输、下料，正确决策……等等一系列优化生产组织与计划管理的问题。被广泛用来解决这类优化问题的重要工具之一就是线性规划。由于它具有广泛适应性，已成为当前应用极广的现代管理方法。 第一节 线性规划的基本概念 一、例4.1：设备配置问题　　某车间生产A、B、C三种产品，需要配置有关设备。各种数据列于表4.1中。　　　　　　　　　　　　　　　　　　　表4.1 产　　品 每强设备每天生产能力(件/天·台） 每天最低产量（件） 甲　设　备 乙　设　备 A 9 3 18 B 3 3 12 C 6 18 36 每天每台运转费(元) 800 640 ? 　　要求在保证完成每天生产任务的前提下，合理确定甲、乙设备的台数，使每天的运转费最低。　　显然，这是一个求满足一定条件（每天的最低产量）下的最小值（运转费最小）问题。解决这一问题的基本思路是：先假设所需配置的甲、乙设备的台数分别是X1台和X2台，然后寻找满足题意的X1、X2的范围，并逐步缩小，最后找出条例题意的X1、X2的具体数值。　　由于每台甲设备每天能生产9件A产品，每台乙设备每天能生产3件A产品，因此当甲乙设备分别配置X1和X2台时，则每天能生产A产品为9X1+3X2。题目要求这一产量每天至少18件，当然可以多一于这一产量。也就是说，由于A产品每天产量的要求，必须使配置的甲、乙设备的台数X1和X2满足下述不等式：　　　　　　　　　　9X1+3X2＞18　　　　　A产品产量的要求　　(4,1)同理可得:　　　　　　　　　　3X1+3X2＞12　　　　　B产品产量的要求　　(4,2)　　　　　　　　　　6X1+18X2＞36　　　　 C产品产量的要求　　(4,3)　　　同时满足上述三个不等式的非负的X1和X2(因为设备台数不能为负数)，一般来说有无穷多个组合，例如X1=2，X2=3；或X1=3，X2=2；……等等都同时满足上述三个不等式。这三个不等式组称为约束条件。于是题目要求：在保证完成每天生产任务的前提下，合理确定甲乙设备的台数X1，X2，使每天的运转费最低。在这时就转换成在同时满足约束条件（4，1）、（4，2）、（4，3）个不等式的无穷多个非负的X1和X2的组合中，选定一组确定的值，使每天运转费之和S为最低。即使S=800X1+640X2为最低。通常写成：使得　　minS(X1,X2)=800X1+640X2　　　　　　　　　　　　　　　　　　　　　　　　　　(4,4)(4,4)式是目标值的计算公式，称为目标函数。　　把上述分析归纳到一起，并将其写成简炼的数学表达式就是：　　设X1、X2分别为甲乙设备的配置台数，求X1，X2　　满足：{9X1+3X2≥18；3X1+3X2≥12；6X1+18X2≥36；}约束条件　　　　　X1≥0，X2≥0　　　　非负要求　　使得minS(X1,X2)=800X1+640X2　　上述数学表达式简炼地表达了题目的全部含义，称为此问题的线性规划模型。二、线性规划模型的特点　　1.求解问题有明确的目标，而且目标值能表示成求未知变量（决策变量）X1，X2……Xn的线性函数（目标函数）的极大值或极小值。如（4，4）式所示。并要求这些未知变量Xi的取值都是非负的。一般实际问题都能满足这一要求。本例的设备台数显然不能是负值。　　2.求解问题的目标同时受到多种限制条件的约束，且这些约束条件都能表示成线性等式或不等式，称为约束函数，如（4，1）、（4，2）、（4，3）式所示。所谓性线是指无论目标函数或约束函数都是Xi的一次函数，在平面直角坐标系中它们是一根直线，所以称为线性规划。　　3.通常同时满足所有约束条件的非负未知变量X1，X2，……Xn有无穷多组，每一组表示一个方案。即可从同时满足所有约束条件下的无穷多个方案中来选择达到目标极小值的方案。　　概括起来，线性规划就是求在线性约束下的线性目标函数的极值问题的数学模型。它由未知变量X1，X2，……Xn及线性约束函数和线性目标函数三部分组成。 　　第二节 实际问题线性规划模型举例 　　应用线性规划解决实际问题的通常步骤是：　　1.选择决策变量X1，X2，……Xn。选择原则是要便于写出约束和目标函数。　　2.确定目标函数。　　3.写出约束条件。　　4.求解。　　本节再通过实例，介绍如何按上述步骤，对实际问题进行分析后，建立其线性规划模型。　　例4.2：设备安装问题材　　某厂要安装A1，A2，……A3三台设备，可以安装在B1，B2……B3三个不同地方，各台设