2023学年度 线性规划问题举例

线性规划问题举例作为上述线性规划问题的数学模型的应用，下面将对三个问题建立线性规划模型．这些问题以及其他线性规划问题的更详细的讨论，在本书的第三部分给出．运输问题一个制造厂希望把若干单位的产品从几个仓库发送到若干个零售点．每个零售点都需要一定数量的产品，而每个仓库也能供应一定数量的产品．这里作如下规定：m=仓库的数目．n=零售点的数目．ai=第i个仓库能供应产品的总量．bj=第j个零售点所需产品的总量．xij=从仓库i运到零售点j的产品数量．这里xij是待定的未知量．如作出表格(当m=2，n=3)则可以看出从仓库1运出产品的总量能用线性方程表示为x11＋x12＋x13=a1．(2．1)对于仓库2有x21＋x22＋x23=a2．(2．2)也要考虑三个零售点所需产品的总量，用下列方程表示：制造厂知道从仓库i运到零售点j一个单位产品的费用为cij．我们还假定费用关系是线性的，即运送xij单位的费用为cijxij．制造厂希望确定，从每个仓库到每个零售点，要运送多少数量的产品，才能使全部运输费用为极小．使费用为极小的目标，可通过极小化线性费用函数c11x11＋c12x12＋c13x13＋c13x13＋c21x21＋c22x22＋c23x23(2．4)来实现．因为一个非负的xij表示从仓库i到零售点j的运输量，所以我们要求全部变量xij≥0．把等式(2．1)至(2．3)，目标函数(2．4)和变量非负的条件联合起来，则m=2，n=3的运输问题就可以表示成下列线性规划问题：作为运输问题的一个数值例子，让我们考虑两个仓库三个零售点的问题，其中可把这个问题写成线性规划问题如下：我们注意上述方程可代表一组会计上的帐目，它们记录了仓库与零售点之间货物流通量．类似地，许多线性规划问题的方程只不过是会计步骤的数学表达．下表给出一个平凡解即x11=0，x12=5，x13=0，x21=8，x22=0，x28=2．相应的目标函数值是2x12＋3x21＋x23=2·5＋3·8＋1·2=36．第二组解(许多组解中的一组)是其目标函数值为26．由第十章的方法可以证明，这个解是极小解．(对于此例，读者应能验证，任何其他解所得到的运输费用都大于26．)活动性分析问题某公司掌握了几种数量固定的资源(如原材料，劳动力和设备)，合起来能生产若干不同产品中的一种或这些产品的某种组合．已知公司每生产一个单位的j种产品所需要的i种资源的数量，同时也已知每生产一个单位的j种产品所能获得利润的数量．公司希望生产的产品组合能使其获得的总利润为最大．对此问题可以作如下定义：m=资源的种类数．n=产品的种类数．aij=生产一个单位的j种产品所需i种资源的数量．bi=i种资源的最大可用量．cj=生产单位j种产品的利润数．xj=j种产品的活动水平(或产量)．有时称aij为投入－产出系数或技术系数．使用i种资源的总量可表示为线性函数ai1x1＋ai2x2＋…＋ainxn．因为上述使用i种资源的总量必须小于或等于i种资源的最大可用量，所以对i种资源有下列线性不等式：ai1x1＋ai2x2＋…＋ainxn≤bi．由于负的xj没有实际意义，所以我们要求所有xj≥0．生产xj单位的j种产品所获得的利润为cjxj．上述极大化利润函数问题的数学表达如下：如第二章将讨论的那样，一个不等式可等价于非负变量的一个等式，所以上述问题是一般线性规划问题的另一种提法．为了说明上述模型，我们考虑在Gass[172]中所给出的例子．一个生产家具的公司计划生产两种产品——椅子和桌子，其可用资源包括400板英尺①的红木板和450个工时．已知生产每把椅子需用红木板5板英尺，10个工时，其利润为45美元，而生产每张桌子需用红木板20板英尺和15个工时，其利润为80美元．问题是要确定，在资源约束范围内，公司生产多少把椅子和多少张桌子，其总利润最大．生产一把椅子需消耗5板英尺的木板和10个工时，而生产一张桌子需消耗20板英尺木板和15个工时．令x1为椅子的生产量，x2为桌子的生产量．上述活动性分析问题，用线性规划的形式可写成下述极大化利润函数的问题：当然，对于上述约束条件，具有很多组可能的解．例如，仅生产椅子的解为x1=45，x2=0，其利润为45×45=2025美元；仅生产桌子的解为x1=0，x2=20，其利润为80×20=1600美元．求出的最优解为：生产椅子x1=24，生产桌子x2=14，其利润为2200美元．食物配料问题这里给出若干不同食物的营养成分含量．例如，我们所考虑的不同食物中，已知每英两食物含有多少毫克的铁或磷，我们也已知每种营养成分的最低日需要量．因为每英两食物的费用是已知的，所以问题是，在满足营养成分的最低日需要量的条件下，确定费用最低的食物配方．定义m=营养成分的种类数．n=食物的种类数．aij=在每一英两的第j种食物中含有第i种营养成分的毫克数．bi=第i种营养成分最低日需要量的毫克数．cj=每英两第j种食物的费用．xj=购买第j种食物的英两数(xj≥0)．购买的所有食物中含有第i种营养成分的总量可表示为ai1x1＋ai22＋…＋ainxn．因为这一总量必须大于或等于第i种营养成分的最低日需要量，这个线性规划问题可表示如下：下面给出关于食物配料问题的一个简单数值例题．考虑两种食物x1和x2以及含有维生素B1、磷、铁三种营养成分的食物配料问题．每种食物中含有各种营养成分的数量(毫克/英两，简写为mg/oz)列于下表对于这两种食物的饮食，至少要求获得维生素毫克，磷毫克，铁毫克．x1的费用为2美分/英两，x2的费用为5/3美分/英两．根据前述一般食物配料问题的格式，本例相应的线性规划问题如下：这个问题的最优解为x1=20/7英两，x2=40/7英两的混合饮食，其费用为美元．把这一结果与单纯用食物x1或单纯用食物x2的解进行费用比较，读者将会受到启发．对于上面的一些例子，以及所有归结为线性规划问题一般形式的问题，我们都假定某些基本的线性关系式成立．线性规划的比例性要求，可通过活动性分析和食物配料问题来说明，在这些问题中，我们假定活动(指产量或配料)水平的改变会引起所需资源或营养成分按比例地改变．当我们对全部生产所用的资源求和或对全部食物中的营养成分求和时，也用到了可加性的要求．虽然我们有权怀疑这些假定的普遍性，但它们的合理性或近似性已使它们在现实世界中得到大量重要的应用．附注最早的线性规划方法的应用，分为三种主要类型：军事应用——来源于空军SCOOP方案，各种经济间的Leontief投入－产出模型以及有关零和二人对策与线性规划之间关系的问题．这些应用领域已得到扩大和发展，但线性规划应用的重点已经转移到工业领域．此外，线性规划问题的应用已经发展到社会和城市的各种问题，例如教育、法律实施、卫生事业、环境保护等应用方面的书目包括在下述分类的文献目录中：农业、合同裁决、工业、经济分析、军事、人员分配、生产计划与存货控制、结构设计、交通研究、运输与网络理论、货郎担问题及其他应用．有关补充