生产中的线性规划问题

1、实际生产中的线性规划问题【摘要】线性规划是运筹学中的一个基本分支，它广泛应用现有的科学技术和数学方法，解决实际中的问题，帮助决策人员选择最优方针和决策。本文主要 研究如何把线性规划的知识运用到企业、生活生产中，是企业提高生产效率，生 活生产更加合理。通过建立模型并利用相关软件，对生活中有限的资源进行合理 分配，从而获得最佳经济效益。关键词线性规划数学方法合理分配最佳效益【引言】随着经济全球化的不断发展，企业面临更加激烈的市场竞争。企业必须不断提高盈利水平，增强其获利的能力，在成本、生产、运输、销售等环节 中提高效率，形成企业的核心竞争力，才能在激烈的市场竞争中立于不败之地。 在各类经济活动中，

2、经常遇到这样的问题：在生产条件不变的情况下，如何通过 统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使 总的经济效益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划”（Linear Programming，简记为LP）问题。线性规划是应用分析、量化的方法，对 经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的 最优方案，以实现有效管理。利用线性规划我们可以解决很多问题。如：在不违 反一定资源限制下，组织安排生产，获得最好的经济效益（产量最多、利润最大、 效用最高）。也可以在满足一定需求条件下，进行合理配置，使成本最小。同时 还可以在任务或目标确

3、定后，统筹兼顾，合理安排，用最少的资源（如资金、设 备、原材料、人工、时间等）去完成任务。下面我们用线性规划方法对企业在生 产中的具体问题进行探讨。二、线性规划的模型线性规划是运筹学的一个重要分支，自1947年丹捷格提出了一般线性规划 问题求解的方法-单纯形法之后，线性规划在理论上趋向成熟，在实际中日益广 泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策的线性规划问 题之后，线性规划的适用领域更为广泛了。以前人们在用这个模型求解时计算非常麻烦，而近几十多年来，由于电子计 算机应用的飞速发展，应用计算机处理线性规划问题使人们求解变得越来越容易 了。LINDO软件是解决线性规划问题的有力

4、工具，它可用于解决50000个约束 条件，20000个变量的线性规划问题，所以线性规划的具体运用也越来越受管理 者的重视了。一、线性规划在企业中的应用下面我们从企业在进行制定生产计划、设备使用、材料的使用、配料分配、 运输、广告促销、企业决策等几方面看看如何运用线性规划使企业得到最优方案。 例1（生产计划问题）假设某厂计划生产甲、乙两种产品，其主要原材料有钢材 3600kg，铜材 2000kg及专用设备能力3000台时，己原材料和设备的单间消耗定额以及单位产 品所获利润如下表所示（表1-1）。问如何安排生产方使该厂所获利润最大？表1-1消耗定颔、产品甲（件）乙 （件）现有材料及设备能力钢材94

5、3600 (kg)铜材4520CO (kg)设备能力31030C0 (台时)单位产品利润（元）70120为了求解这一问题，设甲、乙两种产品的计划产量分别为X ,X件。生产这两种 产品所消耗的钢材总数量为9气+ 4，但现在只有钢材3600kg，因此，应有19x +4x 3600类似地，可以得到124号 + 5x2 20003x1 + 10j:2 3000显然，由于各种产品的数量不能为负数，我们还有并且，总利润为z 二 70沔 +1202综合起来，可以把这个问题的数学形式表达成maz 古=7。西 +120+4叱 3600;4al + 5a2 2000,I 3况十54勺 40;斗八乏口-二、线性规划

6、在企业中的决策应用、确定型决策确定型决策是指面对的问题的相关因素是确定的，从而建立的决策模型的各种参 数是确定的。解决确定型决策问题的方法有线性规划、非线性规划、动态规划等 等，而我要介绍的是线性规划。线性规划是最基本也是最常用的一种数学模型。 为了把一个实际问题用线性规划的方法求解，需要建立数学模型。线性规划问题 的标准为：目标函数maxZ= U cjx.=1 jj一 一 aijx=bl约束条件 s.t. j=1（i=1,2,，m;j=1,2,，n）宇。b z 0建立标准型的好处在于：我们可以只针对这种标准形式来研究它的求解方法。至 于其它各种形式的线性规划问题，可以先将非标准型变成标准型，

7、然后在用标准 型的求解方法求解。线性规划问题的求解方法有图解法，单纯形法，表解式的单 纯形法。其中单纯形法的计算步骤为：(1)找出初始可行基(或用增加新变量 的方法创造初始可行基)建立初始单纯形表。检查所有的zj-cj。如果全部的zj-cjNO,则改解为最优解。反之，说明改 解不是最优解。选择具有最小检验数的非基变量为换入变量。它所对应的那一列称为主列。用主列元素中的每一个大于0的系数去除同行的限定系数(或称右项)， 取比值最小的那一行所对应的基变量为换出变量。把换出变量的那一行，除以该行主列元素的系数。进行行变换，使换出变量那一行之外的全部主列元素变成0.重复第二步，直到没有新的非基变量可以

8、改善目标函数为止。案例：在企业投资决策中，经常需要用到线性规划。例如：随着人们经济 水平的不断提高，某投资商决定投资建汽车厂生产大轿车和载重汽车两种型号的 的汽车，已知生产每辆汽车所用的钢材都是2吨/辆，该工厂每年的供应的钢材 为1600吨，工厂的生产能力是载重汽车2.5小时/辆，大轿车5小时/辆，工 厂全年的有效工时为2500小时；已知供应给该厂的大轿车用的座椅400辆/年。 据市场调查，出售一辆大轿车可获利4千元，出售一辆载重汽车可获利3千元. 问在这些条件下，该投资商如何安排生产才能使工厂获利最大？1、分析与建模：该问题是在有限资源约束下求利润最大化的问题，设x1为生产大汽车的数量，x2

9、为生产载重汽车的数量.模型：maxZ=4x1+3x2ST: 2x1+2x2W16005x1+2.5x2W2500 x1W400 x1N0, x2N01、模型求解(表解式单纯形法)增加三个变量x3,x4,x5,先将该问题化成标准型：maxZ=4x1+3x2ST: 2x1+2x2+x3=16005x1+2.5x2+x4=2500 x1+x5=400 x1,x2, x3,x4,x5N0表解形式如表:c1X302X403X50 x1600250040080050040012345X X X X X12210052.5010 0001300014z.5z.-c.X3X4X1400-4-3002102.5

10、01000-21-501800500400400200zj z.-c.400041600000041X0001-0.824002002330100.4-2200324100014004004z.z.-c.4301.2-2220050001.2-21X0000.5-0.41200253011-0.406003乂2410-0.50.402004zj z-c.4310.402600最优50010.40解从表中可得，该工厂生产200辆大汽车，600辆载重汽车所得到的利润最大为maxZ=4x1+3x2=2600 （千元） 、不确定型决策如果决策问题涉及的条件中有些是未知的，对一些随机变量，连它们的概率分

11、布 也不知道，这类问题被称为不确定型决策。不确定型决策的基本准则有：1.乐观法（又称最大最大准则）：采用这种方法的基本出发点是对未来的客观情 况总是抱乐观态度。其基本步骤是:找出个方案在不同自然状态下的最大益损值; 取各方案最大益损值的最大者为决策方案。例如：某企业打算生产某产品。据市场预测分析，产品销路有三种可能性：销路 好、一般和差。生产该产品有三种方案：改进生产线、新建生产线、外包生产。 各种方案的收益值如表：项目销路好销路一般销路差改进生产线180120-40新建生产线240100-80外包生产1007016在本例中，三种方案的最大收益依次为180、240、100，其中第二种方案对应的

12、 值最大，所以选择新建生产线的方案。悲观法（又称最大最小准则）：采用这种方法的基本出发点是对未来的客观 情况总是抱悲观态度，然后在最坏的情况下有争取最好的可能。其基本步骤是： 找出各行动的方案在不同自然状态下的最小益损值；找各方案最小益损值的最大 者。仍以上个案例为例：三种方案的最低收益依次为40，-80，16,其中第三种 方案对应的值最大，所以选外包生产的方案。3、后悔值法（又称最小最大原则）：决策者在选择了某方案后，若事后发现客 观情况并未按自己预想的发生，会为自己事前的决策而后悔。由此，产生了最小 最大后悔值决策方法，其步骤是：（1）计算每个方案在每种情况下的后悔值，定 义为：后悔值二该

13、情况下的各方案的最大收益-该方案在该情况下的是收益（2）找出各方案的最大后悔值；（3）选择最大后悔值中最小的方案。仍以上例为例，得到关于后悔值的表格为：项目销路好销路一般销路差最大后悔值改进生产线180120-4060新建生产线240100-8096外包生产1007016140从表格中可以看出，其中第一方案对应的最大后悔值最小，所以选择改进生产线 的方案。、风险型决策方法如果决策问题涉及的条件中有些是随机因素，它虽然是不确定型的，但是知道它 的概率分布，这类决策被称为风险型决策。解决风险型决策问题常用的决策原则 有最大可能原则、渴望水平原则和期望值最大原则。1、最大可能原则：按最大概率的自然状

14、态进行决策。这种原则适用于在一组自 然状态中某种状态出现的概率特别大，而其它状态下各行动方案的益损值差别不 大的情况。2、渴望水平原则：预先给出收益的一个渴望水平A,对每一个行动，都求出其收 益达到渴望水平A的概率。使这个概率最大的行动就是渴望水平原则下的最优行 动.3、期望值最大原则：用期望值法进行决策是把每个行动方案的期望值求出来， 加以比较，然后选择期望值最大（当目标是利润时）或期望值最小（当目标是损 失时）的行动方案。在很多情况下，利用决策树来表示决策过程是很方便的。决策树中，口表示决 策点，从它引出的分支叫方案分支，分支数反映可能的行动方案数；。一表示机 会节，从它引出的分支叫事件分

15、支或概率分支，每条分支上写明自然状态及其出 现的概率，分支数反映可能的自然状态数。一表示结果节点，它旁边的数值是 每个方案在相应的自然状态下的效益值。在机会节点上方的数字是各机会或方案 的期望值，在决策点，经过比较将期望值最大的一支保留，其它各支去掉，称为 剪枝。最后决策点上方的数字就是最优方案的期望值。下面举例说明利用决策树 来进行决策的方法。例如：为生产某种产品，设计了两个基建方案：一是建大厂， 二是建小厂。大厂需要投资300万元，小厂需要投资160万元，两者的使用期都 是10年。估计在此期间，产品销路好的可能性是0.7，两个方案的年度损益值 如表：自然状态概率建大厂建小厂销路好0.710040销路差0.3-2010解决该问题的步骤:（1）画决策树（2）计算各点的益损期望值：点2： 0.7X100X10年+0.3X （-20） X10