线性规划案例(2)

案例分析1 降低自助食堂的成本——线性规划All-State 大学的自助食堂每个星期四的中午准时提供一道特殊的菜。

这种想来十分美味的菜是一种炖菜，包含有炒过的洋葱、煮熟的土豆片、绿豆和蘑菇汤。

不幸的是学生们没有能够看到这道菜的特殊质量。

他们为这道菜起了一个令人讨厌的名字，杀手炖菜。

学生们很不情愿吃这道菜，但是自助食堂对星期四的午餐只提供了有限的选择（也就是炖菜）。

自助食堂的经理Maria Gonzalez 希望明年可以降低成本。

她相信降低成本的一种当然的方法是购买较为便宜而质量可能比较低的配料。

由于这种炖菜是每星期自助食堂菜单中的重要组成部分，因此她认为如果她能够降低为制作这种炖菜所购买的配料的成本，整个自助食堂的营运成本将大大降低。

因此她决定花一些时间看看在保持营养和口味要求的情况下如何将成本降到最低。

Maria 集中研究降低这种炖菜的两种主要配料的成本，土豆和绿豆。

这两种配料占据了大多数的成本和营养成分，是影响口味的主要因素。

Maria 每星期从一个批发商那里购买土豆和绿豆。

土豆的成本是每磅0.4 美元，绿豆的成本是每磅1 美元。

All-Sate 大学规定了每一个自助食堂的主菜都必须达到的营养要求。

这道菜必须包含180克的蛋白质、80 毫克的铁、1050 毫克的维生素C ( 1 磅相当于454 克，1 克等于1000毫克）。

为了简化计划，Maria 假设这道炖菜中只有土豆和绿豆提供了营养。

它们的营养成分信息如下表所示：( 1 盎司相当于31.1 克）Edson Branner 是自助食堂的厨师，非常注重于口味。

她告诉Maria 为了使得炖菜可口，土豆和绿豆的总量比至少应当是6 : 5 。

在得到了在自助食堂就餐的学生数之后，Maria 得知她必须购买足够数量的土豆和绿豆，为每星期至少10 公斤的炖菜做好准备。

（1 公斤等于1000克。

）为了简化计划，她假设只有土豆和绿豆决定了能够准备的炖菜的数量。

线性规划应用案例分析线性规划是一种在数学和运营管理中常见的优化技术。

它涉及到在一组线性不等式约束下，最大化或最小化一个线性目标函数。

这种技术可以应用于许多不同的领域，包括供应链管理、资源分配、投资组合优化等。

本文将探讨几个线性规划应用案例，以展示其在实际问题中的应用和价值。

某制造公司需要计划生产三种产品，每种产品都需要不同的原材料和生产时间。

公司的目标是最大化利润，但同时也受到原材料限制、生产能力限制以及每种产品市场需求限制的约束。

通过使用线性规划，该公司能够找到最优的生产计划，即在满足所有约束条件下，最大化利润。

某物流公司需要计划将货物从多个产地运输到多个目的地。

公司的目标是最小化运输成本，但同时也受到运输能力、货物量和目的地需求的约束。

通过使用线性规划，该公司能够找到最优的运输方案，即在满足所有约束条件下，最小化运输成本。

某投资公司需要将其资金分配给多个不同的投资项目。

每个项目都有不同的预期回报率和风险水平。

公司的目标是最大化回报率，同时也要保证投资风险在可接受的范围内。

通过使用线性规划，该公司能够找到最优的投资组合，即在满足所有约束条件下，最大化回报率。

这些案例展示了线性规划在实践中的应用。

然而，线性规划的应用远不止这些，它还可以用于诸如资源分配、时间表制定、路线规划等问题。

线性规划是一种强大的工具，可以帮助决策者解决复杂的问题并找到最优解决方案。

线性规划是一种广泛应用的数学优化技术，适用于在多种资源限制下寻求最优解。

这种技术涉及到各种领域，包括工业、商业、运输、农业、金融等，目的是在给定条件下最大化或最小化线性目标函数。

下面我们将详细讨论线性规划的应用。

线性规划是一种求解最优化问题的数学方法。

它的基本思想是在一定的约束条件下，通过线性方程组的求解，求得目标函数的最优解。

这里的约束条件通常表现为一组线性不等式或等式，而目标函数则通常表示为变量的线性函数。

工业生产：在工业生产中，线性规划可以用于生产计划、物料调配、人力资源分配等方面。

线性规划的应用一、引言线性规划是一种数学优化方法，广泛应用于各个领域，如经济学、管理学、工程学等。

本文将介绍线性规划的基本概念、模型建立以及应用案例。

二、线性规划的基本概念1. 目标函数：线性规划的目标是最大化或最小化一个线性函数，称为目标函数。

目标函数通常表示为z = c₁x₁ + c₂x₂ + ... + cₙxₙ，其中c₁、c₂、...、cₙ为系数，x₁、x₂、...、xₙ为决策变量。

2. 约束条件：线性规划的约束条件是一组线性不等式或等式，用于限制决策变量的取值范围。

约束条件通常表示为a₁x₁ + a₂x₂ + ... + aₙxₙ ≤ b，其中a₁、a₂、...、aₙ为系数，b为常数。

3. 决策变量：线性规划中的决策变量是需要确定的变量，其取值决定了目标函数的取值。

决策变量通常表示为非负数，即x₁, x₂, ..., xₙ ≥ 0。

三、线性规划模型建立线性规划的模型建立包括确定目标函数、约束条件以及决策变量的取值范围。

下面以一个生产计划问题为例，详细说明线性规划模型的建立过程。

假设某工厂生产两种产品A和B，每天可用的生产时间为8小时。

产品A每单位利润为100元，产品B每单位利润为150元。

产品A每小时需要2人工时，产品B每小时需要3人工时。

工厂每天可用的人工时为20小时。

现在需要确定每天生产的产品数量，以最大化利润。

1. 确定目标函数：由于目标是最大化利润，因此目标函数为z = 100A + 150B，其中A为产品A的数量，B为产品B的数量。

2. 确定约束条件：根据生产时间和人工时的限制，可以得到以下约束条件：- 2A + 3B ≤ 20（人工时限制）- A, B ≥ 0（非负数限制）3. 确定决策变量的取值范围：由于产品数量不能为负数，因此决策变量的取值范围为A, B ≥ 0。

四、线性规划的应用案例线性规划在实际应用中有广泛的应用，下面以物流配送问题为例，介绍线性规划的应用案例。

某物流公司需要将货物从仓库分配到不同的配送中心，以满足客户的需求。

线性规划与圆线性规划是一种数学优化方法，广泛应用于工程、经济、管理等领域。

它的目标是在给定的约束条件下，寻觅一个线性模型的最优解。

而圆是一个具有无限多个点的几何形状，由一个固定的中心点和与中心点距离相等的所有点组成。

线性规划与圆之间的联系并不直接，但在某些情况下可以通过线性规划来解决与圆相关的问题。

下面将介绍两个与线性规划与圆相关的实际应用案例。

案例一：最小圆覆盖问题在一个平面上给定一组点，求一个圆，使得这个圆能够覆盖所有的点，并且圆的半径尽可能小。

这个问题可以转化为一个线性规划问题。

首先，我们可以定义一个变量x表示圆心的横坐标，变量y表示圆心的纵坐标，变量r表示圆的半径。

然后，我们可以设置一组约束条件，确保圆能够覆盖所有的点。

例如，对于每一个点(xi, yi)，我们可以设置一个约束条件(x-xi)^2 + (y-yi)^2 ≤ r^2，表示该点在圆的内部。

此外，我们还可以设置一个约束条件，确保圆的半径尽可能小，例如r ≥ 0。

最后，我们可以设置一个目标函数，使得圆的半径最小化，例如minimize r。

通过求解这个线性规划问题，我们可以得到最小圆覆盖问题的最优解。

案例二：圆的最大包含问题在一个平面上给定一个圆和一组点，求一个半径最大的圆，使得这个圆能够彻底包含所有的点。

同样，这个问题也可以转化为一个线性规划问题。

首先，我们可以定义一个变量x表示圆心的横坐标，变量y表示圆心的纵坐标，变量r表示圆的半径。

然后，我们可以设置一组约束条件，确保圆能够彻底包含所有的点。

例如，对于每一个点(xi, yi)，我们可以设置一个约束条件(x-xi)^2 + (y-yi)^2 ≤ r^2，表示该点在圆的内部。

此外，我们还可以设置一个约束条件，确保圆的半径尽可能大，例如r ≥ 0。

最后，我们可以设置一个目标函数，使得圆的半径最大化，例如maximize r。

通过求解这个线性规划问题，我们可以得到圆的最大包含问题的最优解。

线性规划应用案例线性规划是一种在约束条件下寻找最优解的数学优化方法。

它在实际应用中广泛使用，涉及许多领域和行业。

本文将介绍两个典型的线性规划应用案例：运输问题和产能规划问题。

一、运输问题运输问题是线性规划最早发展起来的一个领域，它是指如何在各个供应地和需求地之间运输商品，以使得总运输成本最小。

一个典型的运输问题可以描述为：有m个供应地和n个需求地，每个供应地和需求地之间有一个固定的运输成本和一个固定的供应和需求量。

问题是如何确定每对供需地之间的运输量，以使得总运输成本最小。

举例来说，假设有三个供应地A、B、C，三个需求地X、Y、Z。

运输成本如下表所示：\begin{array}{ c c c c c c }&X&Y&Z&供应量\\A&10&12&8&100\\B&6&8&7&200\\C&9&10&11&300\\需求量&150&175&125&\\\end{array}求解此问题的线性规划模型如下：目标函数：minimize \quad Z = 10x_{11} + 12x_{12} + 8x_{13} + 6x_{21} + 8x_{22} + 7x_{23} + 9x_{31} + 10x_{32} + 11x_{33}约束条件：x_{11} + x_{12} + x_{13} \leq 100x_{21} + x_{22} + x_{23} \leq 200x_{31} + x_{32} + x_{33} \leq 300x_{11} + x_{21} + x_{31} \geq 150x_{12} + x_{22} + x_{32} \geq 175x_{13} + x_{23} + x_{33} \geq 125x_{ij} \geq 0, i = 1,2,3 \quad j = 1,2,3其中x_{ij}表示从供应地i到需求地j的运输量。

4.1二元线性规划问题[案例1]投资生产A产品时,每生产一百吨需要资金200万元.需场地200㎡,可获利润300万元;投资生产B产品时,每生产一百米需要资金300万元,需场地l00㎡,可获利润200万元.现某单位可使用资金1 400万元,场地900㎡,问应作怎样的组合技资，可使获利润最多?(上海市第七届中学生数学知识应用竞赛初赛试题四).分析 (1) 先将题中的数据整理成下表.若设生产A产品x百吨,生产B产品y百米则根据右表列出约束条件：2x＋3y ≤142x＋y≤9x,y≥0目标函数为S=3x+2y.(2)在坐标系内确定满足约束条件的区域即图4-1中画斜线的区域,这一区域称为可行解域.(3) 作目标函数变化直线,即作直线3x+2y= S.由图可知,目标函数只能在可行区域的交点上达到最大.(4) 求出交点P的坐标(13/4, 5/2)这就是满足约束条件且使目标函数达到最大的决策变量的值,我们称之为最优可行解这时目标函数值S=59/4=14.75(百万).以上就是用图解法求解两个变量线性规划问题的全过程.说明:我们通常把满足约束条件的一组决策变量的值称为可行解,也就是说,可行解域中的任意一点都是可行解.可行域的角点(如图4-1中的O,P,A,B)所对应的解称为基本可行解.使目标函数达到最大值或最小值的基本可行解称为最优基本可行解.[案例2](广告问题)某公司准备推出一个新产品,打算拨出款项3万6千元在本地的电视台做广告,希望第一个月的销售额最大.当地电视台广告部安排该公司的广告在晚上八点前和九点后做广告.晚八点前的广告每秒400元,九点后的广告每秒600元,每次播出的时间在10到60秒之间.根据市场调查研究表明,受广告影响的人数依赖于广告播出的时间以及年龄层次,受广告影响的人数总是和广告播出的时间成正比例.广告时每秒影响各年龄组的人数(千人)估计如表所示.现在的要求是广告宣传至少要影响1 500 000个年轻人,2 000 000个中年人和2 000 000个老年人.该公司也估计了在第一个月内受广告影响的人中,每10个年轻人中有1人、20个中年人中1人、50个老年人中1人将购买一件新产品〈并且假设没有一个人第二次再买〉请你帮助该公司的经理在分配早晚电视广告方面提出有益的建议.分析本题涉及的变量较多,因此弄清问题的意义,确定变量并寻找变量间的关系就显得特别重要.(1) 变量情况.主要变量:限制在10秒和60秒之间的两次广告时间.制约变量:总的费用≤36 000元,需影响年轻人数≥1500千人,需影响中年人数≥2 000千人,需影响老年人数≥2000千人.(2) 变量间的关系:总的费用=(购买的时间×每秒价格)之和;.影响的人数=(购买的时间×相应年龄组每秒影响的人数)之和;.销售额=(占影响人数的份额×对应组影响的人数)之和.(3)建模与求解:记x、y分别表示早、晚购买的时间(秒);S=第一个月的销售额(用千人表示),C=总的费用(元);Y、M、O分别表示年轻、中年、老年组受到广告影响的人数(千人).于是有.C=400x＋600y ≤3 600,Y=30x＋50y≥1500,M=100x＋80y≥2 000, (*)O=50x＋40y≥2 000,10≤x≤60, 10≤y≤60要求S=0.1Y＋0.05M＋0.02O=9x＋9.8y的最大值.符合约束条件(*)的点(x,y)在如图4-2所示的六边形区域内，求S=9x+9.8y的最大值转化为求直线y=9x/9.8＋S/9.8的截距S/9.8的最大值.由图4-2知,当此直线过图中直线400x+600y=3600和x =60的交点A(60,20)时,截距最大,此时Smax=9×60+9.8×20=736(千人).(4) 结论：如上讨论可知,满意的结果是第一个月的销售额是736 000（份）只要购买晚八叫点前60秒和九点后20秒的广告即可.此时,花掉了所有的预算并超过所有年龄组所要求影响的人数评价 (1) 本题中建构模型时的线性假设是否现实是可以进一步考虑的.实际上,受广告影响的人数不一定呈线性关系,或许是“S”型的曲线.(2) 购买广告的时间如何使用也是一个问题,如10秒钟的广告重复播出，情况较简单，如果广告时间再长一点或短一点，那么广告播出的时间和受影响的人数之间的关系就更复杂(3) 当然,广告影响的人数显然和广告制作的风格、质量等因素有关.[案例3]一艘货船可装货物30盹,装载体积是14立方米,现有五件货物待运，它们的重量和获利如表：试问装运哪几件才能获利最多?(上海市第四届中学生数学知识应用竞赛初赛试题十五)分析观察所给数据,发现2号货物的体积已超过装载体积的最大值14立方米,可不予考虑.于是最优方案只有两种可能:（1,0,0,1,1）,(0,0,1,1,1),相应的目标函数值为z(1,0,0,1,1)= 9,z(0,0,1,l ,1)=7.因此,装运第1、4、5号货物,能获最大利润9千元说明：本问题用0-1规划的思想0-1规划是一类特殊的整数线性规划,它要求自变量只取0或1.投资计划、人员指派、固定成本运输、机械加工排序等便属于这类问题.案例4一艘货船可装货物500吨,装载体积不能超过200立方,现有六件货物待运,它们的需求量、利润列表如下:问如何确定运输方案能获利最高?(上海市第五届中学生数学知识应用竞赛初赛试题十)分析本题的目标函数为z=40x1+70x2+80x3+50x4+60x5+30x6,其中变量应满足约束条件:50x1+60x2+40x3+30x4+70x5+20x6≤200,150x1+130x2+200x3+180x4+140x5+110x6≤500xi∈{0,1},i=1,2,…,6仔细观察约束条件可知, x1, x2, x3, x4, x5, x6中至少应有三个为零.又注意到目标函数中系数最小的三项为40x1,50x4,30x6,令x1=x4=x6=0,x2= x3= x5=1,此时目标函数值为210,且满足约束条件,故装载2、3、5号货物可获利最大,其值为210万元因为0-1规划问题中的变量只取0或1,所以容易想到用穷举法来求最优解.但是,n个变量可产生2n个可能的组合,故当n较大时,采用完全归纳法进行搜索求解并不可取.下面的部分枚举法可有效地减少运算次数,使最优解较快地被发现.[案例5]求目标函数z=8x1+2x2+5x3+7x4+4x5在约束条件－3 x1－3x2＋3x3＋2x4＋x5≤－2，x1－3x2＋x3－x4－2x5≤－4，－2 x1＋x2－x3＋x4＋2x5≥3,xi∈｛0,1｝,i=1,2,…,5下的最小值分析注意到目标函数中的系数均为正数,令x1=x2=x3=x4=x5=0,得目标函数无条件最小值0,但它不满足约束条件,故非最优解;使目标函数系数最小的xi取1,其余取0,即x2=1, x1=x3=x4=x5=0得除0以外目标函数的最小值2,但它不满足约束条件,故非最优解；使目标函数系数次小的xi取1,其余取0,即x5=1, x1=x2=x3=x4=0,得到除0、2以外的最小值4,但它不满足约束条件,非最优解;比较最小两系数之和与第三小的系数,前者为6,后者等于5,故令x3=1, x1=x2=x4=x5=0,得到除0、2、4以外的最小值5,但仍非最优解;比较最小两系数之和与第四小的系数,前者为6,后者为7,故令x2=x5=1，x2=x3=x4=0,它给出了除0、2、4、5以外的最小值6，且满足约束条件,故为最优解,其值为6.说明 (1) 实际操作时,可以用下表来表示上述过程,层次清楚又直观简明.（2）如求最大值,可令x1=x2=x3=x4=x5=0得目标函数无条件最大值26,再令系数最小的变量x2=0,其余不变……,其思想方法与求最小值是相同的(3) 本题也可通过分析约束条件求解.从第3个约束条件可知x5=1, x1=0,从第1个约束条件可知x2=1,由此可得x3=x4=0,故目标函数最小值为6.案例6有一批1米长的合金钢材现要截成长为23厘米和13厘米二种规格,用怎样的方案截取使材料利用率为最高?并求出材;料最高利用率.(上海市首届中学生数学知识应用竞赛初赛试题五)分析设23厘米和13厘米这两种规格各截x、y根,则23x＋13y≤100,(1)x,y∈N. (2)要求材料利用率z=(23x＋13y)/100尽可能接近或等于1方法1(穷举法)由(l)可知,x的可能取值为0,l ,2,3,4,其对应y的最大值为7,5,4,2,0,于是可算得相应的材料利用率如表所示.故在l米长的合金钢材上,裁和2段23cm,4段13cm,能获得材料的最高利用率98%.方法2(图解法).满足约束条件(1)、(2)的点(x,y),就是直线23x+13y=100与两坐标轴在第一象限所围三角形AOB区域上(包括边界)的格点,如图4-4.显然,格点越靠近直线AB,那么残料就越少,若格点恰好在直线AB上,则此格点所对应的下料方案一定是最优的(无残料).通过观察、比较知,与直线最近的格点为。

1。

人力资源分配问题例1.某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如表1所示。

设司机和乘务人员分别在各时间段开始时上班,并连续工作8小时，问该公交线路应怎样安排司机和乘务人员,既能满足工作需要,又使配备司机和乘务人员的人数最少？解：设x i表示第i班次时开始上班的司机和乘务人员数，这样我们建立如下的数学模型。

目标函数：Min x1+x2+x3+x4+x5+x6约束条件:s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3，x4，x5,x6≥0运用lingo求解：Objectivevalue:150。

0000ariableValueReducedCostX160。

000000。

000000X210.000000.000000X350。

000000。

000000X40.0000000.000000X530.000000.000000X60.0000000.000000例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。

为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。

问应该如何安排售货人员的作息,既满足工作需要，又使配备的售货人员的人数最少?解：设x i(i=1,2，…,7)表示星期一至日开始休息的人数，这样我们建立如下的数学模型。

目标函数：Min x1+x2+x3+x4+x5+x6+x7约束条件：s.t.x1+x2+x3+x4+x5≥28x2+x3+x4+x5+x6≥15x3+x4+x5+x6+x7≥24x4+x5+x6+x7+x1≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31x7+x1+x2+x3+x4≥28x1,x2，x3，x4,x5,x6，x7≥0lingo求解Objectivevalue:36。

00000VariableValueReducedCostX112.000000。

附录2 线性规划案例Appendix 2 Projects of Linear Programming案例1 食油生产问题(1)食油厂精炼两种类型的原料油——硬质油和软质油，并将精制油混合得到一种食油产品。

硬质原料油来自两个产地:产地1和产地2，而软质原料油来自另外三个产地：产地3，产地4和产地5。

据预测，这5种原料油的价格从一至六月分别为：产品油售价为200元/吨。

硬质油和软质油需要由不同的生产线来精炼。

硬质油生产线的每月最大处理能力为200吨，软质油生产线最大处理能力为250吨/月。

五种原料油都备有贮罐，每个贮罐的容量均为1000吨，每吨原料油每月的存贮费用为5元。

而各种精制油以及产品无油罐可存贮。

精炼的加工费用可略去不计。

产品的销售没有任何问题。

产品食油的硬度有一定的技术要求，它取决于各种原料油的硬度以及混合比例。

产品食油的硬度与各种成份的硬度以及所占比例成线性关系。

根据技术要求，产品食油的硬度必须不小于3.0而不大于6.0。

各种原料油的硬度如下表（精制过程不会影响硬度）：假设在一月初，每种原料油都有500吨存贮而要求在六月底仍保持这样的贮备。

问题1：根据表1预测的原料油价格，编制逐月各种原料油采购量、耗用量及库存量计划，使本年内的利润最大。

问题2：考虑原料油价格上涨对利润的影响。

据市场预测分析，如果二月份硬质原料油价格比表1中的数字上涨Ｘ％，则软质油在二月份的价格将比表1中的数字上涨2Ｘ％，相应地，三月份，硬质原料油将上涨2Ｘ％，软质原料油将上涨4Ｘ％，依此类推至六月份。

试分析Ｘ从1到20的各情况下，利润将如何变化？案例2 食油生产问题（2）在案例1中，附加以下条件，求解新的问题：1.每一个月所用的原料油不多于三种。

2.如果在某一个月用一种原料油，那么这种油不能少于20吨。

3.如果在一个月中用了硬质油1或硬质油2，则在这个月中就必须用软质油5。

案例3 机械产品生产计划问题机械加工厂生产7种产品（产品1到产品7）。