下载文档原格式
§2.1 线性规划问题1、线性规划问题举例例2.1.1 某工厂用三种原料生产三种产品，已知的条件如表2.1.1所示，试制订总利润最大的生产计划解、每天生产三种产品的数量，分别设为321,,x x x ，则321453max x x x ++15003221≤+x xs .t . 8004232≤+x x2000523321≤++x x x 0,,321≥x x x例 2.1.2 运输问题一个制造厂要把若干单位的产品从两个仓库 2,1;=i A i ，发送到零售点 4,3,2,1;=j B j ，仓库 i A 能供应的产品数量为 2,1;=i a i ，零售点 j B 所需的产品的数量为 4,3,2,1;=j b j 。
假设供给总量和需求总量相等，且已知从仓库 i A 运一个单位产品往 j B 的运价为 ij c 。
问应如何组织运输才能使总运费最小？解、从仓库i A 运往j B 的产品数量 设为4,3,2,1,2,1;==j i x ij m i n ∑∑==2141i j ij ij x c2,1;4321==+++i a x x x x i i i i i s .t .4,3,2,1;21==+j b x x j j j 4,3,2,1,2,1;0==≥j i x ij2、线性规划模型（1）一般形式⎪⎪⎩⎪⎪⎨⎧==≥+=≥++==+++++=q j x qj x m p i b x a x a x a p i b x a x a x a t s x c x c x c z j j i n in i i i n in i i nn ,...,2,1;,...,2,1;0,...,1;,...,2,1;..min 221122112211无限制ΛΛΛn j x j ,...,2,1;=为待定的决策变量，),,,(21n c c c c Λ=为价值向量，n j c j ,...,2,1;=为价值系数，),...,,(21m b b b b =为右端向量，矩阵⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=mn m m n n a a a a a a a a a A ΛΛΛΛΛΛΛ212222111211 为系数矩阵。
线性规划题及答案一、问题描述某公司生产两种产品A和B，每一个产品的生产需要消耗不同的资源，并且每一个产品的销售利润也不同。
公司希翼通过线性规划来确定生产计划，以最大化利润。
已知产品A每一个单位的生产需要消耗2个资源1和3个资源2，每一个单位的销售利润为10元；产品B每一个单位的生产需要消耗4个资源1和1个资源2，每一个单位的销售利润为15元。
公司目前有10个资源1和12个资源2可供使用。
二、数学建模1. 假设生产产品A的数量为x，生产产品B的数量为y。
2. 根据资源的消耗情况，可以得到以下约束条件：2x + 4y ≤ 10 （资源1的消耗）3x + y ≤ 12 （资源2的消耗）x ≥ 0, y ≥ 0 （生产数量为非负数）3. 目标是最大化利润，即最大化销售收入减去生产成本：最大化 Z = 10x + 15y三、线性规划求解1. 将目标函数和约束条件转化为标准形式：目标函数：最大化 Z = 10x + 15y约束条件：2x + 4y ≤ 103x + y ≤ 12x ≥ 0, y ≥ 02. 通过图形法求解线性规划问题：a. 绘制约束条件的图形：画出2x + 4y = 10和3x + y = 12的直线，并标出可行域。
b. 确定可行域内的顶点：可行域的顶点为(0, 0)，(0, 2.5)，(4, 0)，(2, 3)。
c. 计算目标函数在每一个顶点处的值：分别计算Z = 10x + 15y在(0, 0)，(0, 2.5)，(4, 0)，(2, 3)四个顶点处的值。
Z(0, 0) = 0Z(0, 2.5) = 37.5Z(4, 0) = 40Z(2, 3) = 80d. 比较所有顶点处的目标函数值，确定最优解：最优解为Z = 80，即在生产2个单位的产品A和3个单位的产品B时，可以获得最大利润80元。
四、结论根据线性规划的结果，公司在资源充足的情况下，应该生产2个单位的产品A和3个单位的产品B，以最大化利润。
线性规划题及答案引言概述：线性规划是运筹学中的一种数学方法，用于寻觅最优解决方案。
在实际生活和工作中，线性规划问题时常浮现，通过对问题进行建模和求解，可以得到最优的决策方案。
本文将介绍一些常见的线性规划题目，并给出详细的答案解析。
一、生产规划问题1.1 生产规划问题描述：某工厂生产两种产品A和B，产品A每单位利润为100元，产品B每单位利润为150元。
每天工厂有8小时的生产时间，产品A每单位需要2小时，产品B每单位需要3小时。
问工厂每天应该生产多少单位的产品A 和产品B，才干使利润最大化？1.2 生产规划问题答案：设产品A的生产单位为x，产品B的生产单位为y，则目标函数为Max Z=100x+150y，约束条件为2x+3y≤8，x≥0，y≥0。
通过线性规划方法求解，得出最优解为x=2，y=2，最大利润为400元。
二、资源分配问题2.1 资源分配问题描述：某公司有两个项目需要投资，项目A每万元投资可获得利润2万元，项目B每万元投资可获得利润3万元。
公司总共有100万元的投资额度，问如何分配投资额度才干使利润最大化？2.2 资源分配问题答案：设投资项目A的金额为x万元，投资项目B的金额为y万元，则目标函数为Max Z=2x+3y，约束条件为x+y≤100，x≥0，y≥0。
通过线性规划方法求解，得出最优解为x=40，y=60，最大利润为240万元。
三、运输问题3.1 运输问题描述：某公司有两个仓库和三个销售点，每一个销售点的需求量分别为100、150、200，每一个仓库的库存量分别为80、120。
仓库到销售点的运输成本如下表所示，问如何安排运输方案使得总成本最小？3.2 运输问题答案：设从仓库i到销售点j的运输量为xij，则目标函数为Min Z=∑(i,j) cij*xij，约束条件为每一个销售点的需求量得到满足，每一个仓库的库存量不超出。
通过线性规划方法求解，得出最优的运输方案，使得总成本最小。
四、投资组合问题4.1 投资组合问题描述：某投资者有三种投资标的可选择，预期收益率和风险如下表所示。
线性规划经典例题引言概述：线性规划是一种运筹学方法，用于解决线性约束条件下的最优化问题。
它在各个领域都有广泛的应用，包括生产计划、资源分配、运输问题等。
本文将介绍几个经典的线性规划例题，以帮助读者更好地理解和应用线性规划方法。
一、生产计划问题1.1 最大利润问题在生产计划中，一个常见的线性规划问题是最大利润问题。
假设一个公司有多个产品，每个产品的生产和销售都有一定的成本和利润。
我们需要确定每个产品的生产数量，以最大化整体利润。
1.2 生产能力限制另一个常见的问题是生产能力限制。
公司的生产能力可能受到设备、人力资源或原材料等方面的限制。
我们需要在这些限制下，确定每个产品的生产数量，以实现最大化的利润。
1.3 市场需求满足除了考虑利润和生产能力，还需要考虑市场需求。
公司需要根据市场需求确定每个产品的生产数量，以满足市场需求，并在此基础上最大化利润。
二、资源分配问题2.1 资金分配问题在资源分配中，一个常见的线性规划问题是资金分配问题。
假设一个公司有多个项目，每个项目需要一定的资金投入，并有相应的回报。
我们需要确定每个项目的资金分配比例，以最大化整体回报。
2.2 人力资源分配另一个常见的问题是人力资源分配。
公司的人力资源可能有限，而各个项目对人力资源的需求也不同。
我们需要在人力资源有限的情况下，确定每个项目的人力资源分配比例，以实现最大化的效益。
2.3 时间分配除了资金和人力资源，时间也是一种有限资源。
在资源分配中，我们需要合理安排时间，以满足各个项目的需求，并在此基础上实现最大化的效益。
三、运输问题3.1 最小成本运输问题在运输领域，线性规划可以用于解决最小成本运输问题。
假设有多个供应地和多个需求地，每个供应地和需求地之间的运输成本不同。
我们需要确定每个供应地和需求地之间的货物运输量，以实现最小化的总运输成本。
3.2 运输能力限制另一个常见的问题是运输能力限制。
运输公司的运输能力可能受到车辆数量、运输距离或运输时间等方面的限制。
线性规划问题的解法与最优解分析线性规划是一种数学建模方法，用于解决最优化问题。
它在工程、经济学、管理学等领域有着广泛的应用。
本文将介绍线性规划问题的解法和最优解分析。
一、线性规划问题的定义线性规划问题是指在一定的约束条件下，求解一个线性目标函数的最大值或最小值的问题。
线性规划问题的数学模型可以表示为：max/min Z = c₁x₁ + c₂x₂ + ... + cₙxₙsubject toa₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ≥ 0其中，Z表示目标函数的值，c₁, c₂, ..., cₙ为目标函数中的系数，a₁₁,a₁₂, ..., aₙₙ为约束条件中的系数，b₁, b₂, ..., bₙ为约束条件中的常数，x₁,x₂, ..., xₙ为决策变量。
二、线性规划问题的解法线性规划问题的解法主要有两种：图形法和单纯形法。
1. 图形法图形法适用于二维或三维的线性规划问题。
它通过绘制约束条件的直线或平面以及目标函数的等高线或等高面，来确定最优解。
首先，将约束条件转化为不等式，并将其绘制在坐标系上。
然后，确定目标函数的等高线或等高面，并绘制在坐标系上。
最后，通过观察等高线或等高面与约束条件的交点，找到最优解。
图形法简单直观，但只适用于低维的线性规划问题。
2. 单纯形法单纯形法是一种迭代的求解方法，适用于高维的线性规划问题。
它通过在可行域内不断移动，直到找到最优解。
单纯形法的基本思想是从初始可行解开始，每次通过找到一个更优的可行解来逼近最优解。
它通过选择一个基本变量和非基本变量，来构造一个新的可行解。
然后，通过计算目标函数的值来判断是否找到了最优解。
如果没有找到最优解，则继续迭代，直到找到最优解为止。
单纯形法是一种高效的求解线性规划问题的方法，但对于大规模的问题，计算量会很大。
线性规划经典例题一、问题描述：某公司生产两种产品A和B，每天的生产时间为8小时。
产品A每件需要1小时的加工时间，产品B每件需要2小时的加工时间。
公司每天的总加工时间不能超过8小时。
产品A的利润为100元/件，产品B的利润为200元/件。
公司希望最大化每天的利润。
二、数学建模：设公司每天生产的产品A的件数为x，产品B的件数为y。
则目标函数为最大化利润，即：Maximize Z = 100x + 200y约束条件：1. 生产时间约束：x + 2y ≤ 82. 非负约束：x ≥ 0, y ≥ 0三、线性规划模型：Maximize Z = 100x + 200ySubject to:x + 2y ≤ 8x ≥ 0y ≥ 0四、求解方法：可以使用线性规划求解器进行求解，例如使用单纯形法或内点法等。
以下是使用单纯形法求解的步骤：1. 将目标函数和约束条件转化为标准形式：目标函数：Maximize Z = 100x + 200y约束条件：x + 2y ≤ 8x ≥ 0y ≥ 02. 引入松弛变量将不等式约束转化为等式约束：x + 2y + s1 = 8x ≥ 0y ≥ 0s1 ≥ 03. 构建初始单纯形表：基变量 | x | y | s1 | 常数项-----------------------------Z | 0 | 0 | 0 | 0-----------------------------s1 | 1 | 2 | 1 | 84. 进行单纯形法迭代计算：a. 选择进入变量：选择目标函数系数最大的非基变量，即选择y进入基变量。
b. 选择离开变量：计算各个约束条件的最小比值，选择比值最小的非基变量对应的约束条件的基变量离开基变量。
在本例中，计算得到最小比值为4，对应的约束条件为x ≥ 0，所以x对应的基变量离开基变量。
c. 更新单纯形表：基变量 | x | y | s1 | 常数项-----------------------------Z | 0 | 0 | -2 | -400-----------------------------s1 | 1 | 2 | 1 | 8d. 继续迭代计算，直到目标函数系数均为负数或零，达到最优解。
线性规划问题一、线性规划问题的基本概念先看几个典型实例 例1 生产计划问题某工厂拥有a 、b 两种原材料生产A 、B 两种产品，现有设备使用限量为8台时，已知每件产品的利润、所需设备台时及原材料的消耗如下表所示：试问：在计划期内应如何安排计划才能使工厂获得的利润最大？解 设x 1、x 2分别表示在计划期内产品A 、B 的产量，则所用设备的有效台时必须满足x 1＋2x 2≤8同样，由原材料的限量，可以得到4x 1≤16，4x 2≤12因此，生产计划就是满足如下约束条件的一组变量x 1、x 2的值：x1＋2x 2≤8， 4x 1≤16，4x 2≤12， x 1≥0，x 2≥0显然，可行的生产计划有限多个，现在问题就是要在很多个可行计划中找一个利润最大的，即求一组变量x 1、x 2的值，使它满足约束条件，并使目标函数L=2x 1＋3x 2的值最大（即利润最大）例2 资金分配问题某商店拥有100万元资金，准备经营A 、B 、C 三种商品，其中A 商品有A 1、A 2两种型号，B 商品有B 1、B 2两种型号，每种商品的利润率如下表所示：在经营中有以下限制：(1)经营A 或B 的资金各自都不能超过总资金的50%； (2)经营C 的资金不能少于经营B 的资金的25%； (3)经营A 2的资金不能超过经营A 的总资金的60%； 试问应怎样安排资金的使用才能使利润最大？解 设经营A 1、A 2、B 1、B 2、C 的资金分别为x 1，x 2,x 3,x 4，x 5（万元），这一问题的数学模型为求一组变量x 1、x 2，…，x 5的值，使它满足 x 1＋x 2＋…＋x 5=100， x 1＋x 2≤50， x 3＋x 4≤50，025x 3＋0.25x 4－x 5≤0 0.6x 1－0.4x 2≥0，x j ≥0 （j=1，2， (5)并使目标函数L=0.073x 1＋0.103x 2＋0.064x 4＋0.075x 4＋0.045x 5的值最大(利润最大)上面我们建立了几个实际问题的数学模型，虽然实际问题各不相同，但是它们的数学模型却有相同的数学形式，这就是：表示约束条件的数学式子都是线性等式或线性不等式，表示问题最优化指标的目标函数都是线性函数，因为约束条件和目标函数都是线性的，所以把具有这种模型的问题称为线性规划问题。
线性规划问题的数学模型的一般形式是 Max(Min)L=c 1x 1＋c 2x 2＋…＋c n x n .(1)a 11x 1＋a 12x 2＋…＋a 1n x n ≤b 1 (或≥b 1，或=b 1),a 21x 1＋a 22x 2＋…＋a 2n x n ≤b 2 (或≥b 2，或=b 2),………………………………(2)a m1x 1＋a m2x 2＋…＋a mn x n ≤b m (或≥b m ，或=b m )，x j ≥（j=1，2，…，n ）.(3)即求一组变量x j （j=1，2，…，n ）的值，满足约束条件，使目标函数L 的值最大（或最小），其中，x 1，x 2，…，x n 称为决策变量，简称变量，约束条件（3）称为变量的非负约束。
满足约束条件的一组变量的值称为线性规划问题的一个可行解，使目标函数L取得取大值（或最小值）的可行解称为最优解，此时，目标函数的值称为最优值，“s.t.”表示约束条件。
例如，在例1中，若变量x 1，x 2取值为x 1=1，x 2=2时，它们满足约束条件，因此x 1=1，x 2=2是该问题的一个可行解，此时目标函数的值为8。
求解线性规划问题有不少现成的数学软件，LINDO 软件就是其中之一，在LINDO6.1版本下打开，直接输入数学模型，例如，输入倒1的模型Max 2X1＋3X2s.t.X1＋2X 2＜=8 4X1＜=16 4X2＜=12 end注：LINDO 中已规定所有决策变量均为非负，因此不必输入约束条件中的非负约束条件，程序最后以“end ”结束将文件存储并命名后，选择菜单“Solve ”，得输出 OBJECTIVE FUNCTION VALUE 1)14.000000 VARIABLEVALUEREDUCEDCOSTX1 4.000000 X22.000000 即，生产A 产品4件、B 产品2件，利润为14万元。
例3 工作选择人员设有A 1、A 2、A 3、A 4四个人完成B 1、B 2、B 3、B 4四项工作，每人只做一件工作且每件工作仅由一人担任，A i 完成工作B j 所需时间为C ij （i ，j=1，2，3，4）（单位：天），如下表所示。
试问应指派哪个人去承担哪件工作，才能使总的花费时间最少？这个问题与上述各例有所不同，上述各例所设的变量都是问题中所要求的数量，而这个例题中我们要引入的变量必须具有指定某人做某件工作，而其他人不能做该工作。
数0、1就起到了这种作用，变量取1，说明该人做这件事，在总的花费时间中贡献时间，变量取0表示不做这件事，从而在总的花费时间中不作出贡献。
解引入16个变量1，当指派Ai 承担工作Bj时；xij=i，j=1，2，3，40，当指派Ai 不承担工作Bj时，由于每人只做一件工作，得x11＋x12＋x13＋x14=1x21＋x22＋x23＋x24=1x31＋x32＋x33＋x34=1x 41＋x42＋x43＋x44=1由于每件工作仅由一个担任，得x 11＋x21＋x31＋x41=1x 12＋x22＋x32＋x42=1x 13＋x23＋x33＋x43=1x 14＋x24＋x34＋x44=1得线性规划模型如下MinT=8x11＋13x12＋18x13＋23x14＋10x21＋14x22＋16x23＋27x24＋2x31＋10x32＋21x33＋26x34＋14x41＋22x42＋26x43＋28x44s.t xij=1xij=1 i，j=1，2，3，4xij=0或1这种线性规划称为0-1规划，这类问题也称为指派问题将模型输入LINDOMIn 8x11＋13x12＋18x13＋23x14＋10x21＋14x22＋16x23＋27x24＋2x31＋10x32＋21x33＋26x34＋14x41＋22x42＋26x43＋28x44 s.tx11＋x12＋x13＋x14=1x21＋x22＋x23＋x24=1 x31＋x32＋x33＋x34=1 x41＋x42＋x43＋x44=1 x11＋x21＋x31＋x41=1 x12＋x22＋x32＋x42=1 x13＋c23＋x33＋x43=1 x14＋x24＋x34＋x44=1 end int16注：int16表示16个变量全部为0-1变量求解得x 12=x 23=x 31=x 44=1,其余x ij =0，即A 1承担工作B 2，A 2承担工作B 3，A 3承担工作B 1，A 4承担工作B 4，花费的总时间最少为59天。
例4 汽车厂生产计划一汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求、利润以及每月工厂钢材、劳动时间的现有量如下表所示，试制订月解 设每月生产小、中、大型汽车的数量分别为x 1、x 2、x 3，工厂的月利润为L ，在题目所给参数均不随生产数量变化的假设下，立即可得线性规划模型： MaxL=2x 1＋3x 2＋4x 3s.t 1.5x 1＋3x 2＋5x 3≤600 280x 1＋250x 2＋400x 3≤60000x 1，x 2，x 3≥0求解得到输出ORJECTIVE FUNCTION VALUE 1） 632.2581 VARIABLEVALUE REDUCED COST X1 64.516129 0.000000 X2 167.7419280.000000 X3 0.0000000.946237 ROW SLACK OR SURPLUSDUAL PRICES 2)0.0000000.7311833) 0.000000 0.003226我们看到最优解x 1=64.516129,x 2=167.741928，x 3=0，出现小数，显然不合适 对于这个实际问题，变量x 1，x 2，x 3只能取整数，我们必须在上述所建立的线性规划模型中增加约束条件x 1，x 2，x 3为整数得来的线性规划模型如下：MaxL=4x 1＋3x 2＋2x 3s.t 1.5x 1＋3x 2＋5x 3≤600 280x 1＋25x 2＋400x 3≤60000 x 1≥0，x 2≥0，x 3≥0 x 1，x 2，x 3均为整数附加了整数约束条件的线性规划模型称为整数规划 用LINDO 直接求解，输入文件： max2x1＋3x2＋4x3 s.t1.5x1＋3x2＋5x3＜600 280x1＋250x2＋400x3＜60000 end gin3注：最后一行“gin3”是“3个变量均为整数”的说明语句。
求解得到输出（只列出需要的结果）： OBJECTIVE FUNCTION VALUE 1）632.0000 VARIABLEVALUEREDUCED COSTX1 64.000000 -2.000000X2 168.000000 -3.000000 X3 0.000000 -4.000000最优解为x 1=64，x 2=168，x 3=0，最优值为z=632，即问题要求的月生产计划为生产小型车64辆、中型车168辆，不生产大型车。
二、线性规划问题举例例1 自来水输送问题某市有甲、乙、丙、丁四个居民区，自来水由A ，B ，C 三个水库供应，四个区每天必须得到保证的基本生活用水量分别为30，70，10，10千吨，但由于水源紧张，三个水库每天最多只能分别供应50，60，50千吨自来水，由于地理位臵的差别，自来水公司从各水库向各区送水所需付出的引水管理费不同（见下表，其中C 水库与丁区之间没有输水管道），其他管理费用都是450元/千吨，根据公司规定，各区用户按照统一标准900元/千吨收费，此外，四个区都向公司申请了额外用水量，分别为每天50，70，20，40千吨，该公司应如何分配供水量，才能获问题分析 分配供水量就是安排从三个水库向四个区送水的方案，目标是获利最多，而从题目给出的数据看，A ，B ，C 三个水库的供水量160千吨，不超过四个区的基本生活用水量与额外用水量之和300千吨，因而总能全部卖出并获利，于是自来水公司每天的总收入是900×（50＋60＋50）=144000元，与送水方案无关，同样，公司每天的其它管理费用450×（50＋60＋50）=72000元也与送水方案无关，所以，要使利润最大，只需使引水管理费最小即可，另外，送水方案自然要受三个水库的供应量和四个区的需求量的限制。
模型建立很明显，决策变量为A ，B ，C 三个水库(i=1，2，3)分别向甲、乙、丙、丁四个区（j=1，2，3，4）的供水量，设水库i 向j 区的日供水量为x ij ，由于C 水库与丁区之间没有输水管道，即x 34=0,因此只有11个决策变量。
