运筹学课程设计（论文）-用MATLAB和LINGO求解生产问题.docx

用matlab和lingo求解生产问题1 问题的提出生产问题是一类常见的线性规划问题.在生产一种或多种产品的时候，面对多种可选择的资源有多种不同的生产方案，与此同时不同的生产方案可以带来不同的产品效益，而选择不同的生产方案时所消耗的资源也不同，即导致成本费用的差异.因此制定生产方案则是要解决在限定的资源下选择一套生产方案，使其满足各项约束条件的情况下同时达到最小成本，增加产品利润.例如：某厂决意生产两种糖果:硬糖和软糖,糖果仅由糖,坚果,和巧克力制成，三种材料的总量分别为100盎司，20盎司以及30盎司.软糖须含有至少20%的坚果，糖须含有至少10%的坚果和10%的巧克力.并且已知1盎司软糖和硬糖的售价分别为25、20美分，根据要求安排生产计划使得工厂的收入最大化.2 问题的分析线性规划问题的数学模型包括三个组成要素：(1)决策变量：又称为控制变量，是模型所代表的系统中受到控制或能够控制的变量，表现为未知参数（变量），最后通过选定决策变量来实现最优解；(2)约束条件：决策变量客观上必须满足的限制条件，反映出实际问题中不受控制的系统变量对受控制的决策变量的限制关系，包括等式约束和不等式约束 ；(3)目标函数：模型所代表的性能指标，在模型中表现为决策变量的函数，反映了实际问题所要达到的理想目标，分为求最大值和最小值两种形式.如果规划问题的数学模型中，决策变量的取值是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型成为线性规划的数学模型.实际问题中线性的含义:一是严格的比例性，如生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例；二是可叠加行，如生产多种产品时，可获取的总利润是各项产品的利润之和，对某项资源的消耗量应等于各产品对该项资源的消耗量的和.很多实际问题往往不符合上述条件，为处理问题方便，可看做近似满足线性条件.如安排生产计划问题则是以收入为目标函数，各种材料所占比例以及材料总数为约束条件，构成线性规划问题.线性规划问题部分内容框架如下：实际问题lp模型 基本概念线性规划的数学模型线性规划的各种解的概念可行解基本解基本可行解最优解基本最优解基本方法图解法单纯形法对偶单纯形法进一步讨论修正单纯形法对偶理论灵敏度分析算法复杂度分析 线性规划问题的数学模型的一般形式:（1）列出目标函数及约束条件：max（或min）z=st（2）画出约束条件所表示的可行域；（3）在可行域内求目标函数的最优解.3 问题假设（1）制造糖果的三种原材料总量不会因为任何因素发生改变；（2）每种糖果对原料的需求可以严格控制；（3）糖果的生产过程是稳定的，并且没有技术问题；（4）生产过程中互不干扰；（5）在生产时不会存在材料浪费的情况，即生产机器上不会沾到原材料导致实际使用的原材料与加入材料量不符.4 符号说明设以i表示糖果的种类，以j表示制造糖果所需要的原材料，xij表示每种糖果所需要的每种材料的含量，具体对应关系如表： 单位：盎司 ji糖坚果巧克力硬糖x11x12x13软糖x21x22x23z:生产硬糖和软糖的总收入.5 模型的建立5.1 模型的准备工作目标函数：max（或min）约束条件：st 上述模型简化形式为：目标函数：max（或min）z=约束条件：st5.2 建立模型5.2.1 运用matlab软件求解模型目标函数系数矩阵：c=20,20,20,25,25,25即目标函数为：max z=20*（x11+x12+x13）+25(x21+x22+x23)各决策变量在其相关的影响因素下所需满足的约束条件： x11 +x21100x12+x2220x13+x2330x11-9x12+x130x11+x12-9x130x21-4x22+x230xij0,i,j=1,2,35.2 .2 运用lingo软件求解模型其具体过程如下流程图：输入lingo软件按题要求求解最优可行解写出目标函数、决策变量所满足的约束条件依照题目要求，将各因素数字量化，决定目标函数变量，决策变量 6 模型求解由问题分析可得：(1)生产的总收入与两类糖果的生产总量有关;(2)每类糖果的生产总量等于糖、坚果和巧克力三者的含量之和;(3)糖、坚果和巧克力三者的总含量有限，生产两类糖果时所耗用的总材料数不能超过给定材料的总含量.6.1 matlab软件求解结果z=3.2500e+003x= 80.0000 10.0000 10.0000 20.0000 10.0000 20.0000对结果进行分析得： 单位：盎司 ji糖坚果巧克力硬糖801010软糖201020合计1002030最大收入（美分）32506.2 lingo软件求解结果根据以上的目标函数和约束条件，借助lingo软件中的求解线性规划程序，最终得到：global optimal solution found. objective value: 3250.000 infeasibilities: 0.000000 total solver iterations: 5 variable value reduced cost x11 80.00000 0.000000 x12 10.00000 0.000000 x13 10.00000 0.000000 x21 20.00000 0.000000 x22 10.00000 0.000000 x23 20.00000 0.000000对结果进行分析得： 单位：盎司 ji糖坚果巧克力硬糖801010软糖201020合计1002030最大收入（美分）32507 模型验证及结果分析7.1 模型验证7.1.1 matlab软件求解结果验证采用matlab软件中的线性规划模型得：x11=80x12=10x13=10x21=20x22=10x23=20max z=3250由以上结果可知：（1）硬糖的生产计划为：80盎司糖、10盎司坚果和10盎司巧克力；（2）软糖的生产计划为：20盎司糖、10盎司坚果和20盎司巧克力；（3）生产硬糖和软糖产生的最大收入为3250美分.7.1.2 lingo软件求解结果验证采用lingo软件中的线性规划模型得：x11=80x12=10x13=10x21=20x22=10x23=20max z=3250由以上结果可知：（1）硬糖的生产计划为：80盎司糖、10盎司坚果和10盎司巧克力；（2）软糖的生产计划为：20盎司糖、10盎司坚果和20盎司巧克力；（3）生产硬糖和软糖产生的最大收入为3250美分.7.2 结果分析通过我们建立的lingo模型，求解出了一个合理的生产计划，下面我们将对lingo求解的结果进行详细的分析如下：查看lingo报告窗口（reports window）,可以看到如下结果global optimal solution found. objective value: 3250.000 infeasibilities: 0.000000 total solver iterations: 5variable value reduced costx11 80.00000 0.000000x12 10.00000 0.000000x13 10.00000 0.000000x21 20.00000 0.000000x22 10.00000 0.000000x23 20.00000 0.000000row slack or surplus dual price1 3250.000 1.0000002 0.000000 15.000003 0.000000 65.000004 0.000000 15.000005 0.000000 5.0000006 0.000000 0.0000007 0.000000 10.00000 “objective value:3250.000”表示最优目标值为3250.“value”给出最优解中各变量的值：最优生产计划是：生产硬糖需要80盎司的糖，10盎司的坚果和 10盎司的巧克力；生产软糖需要20盎司的糖，10盎司的坚果和10盎司的巧克力.“slack or surplus”为给出的松驰变量的值：第1行松驰变量 =3250（模型第一行表示目标函数，所以第二行对应第一个约束）第2行松驰变量 =0第3行松驰变量 =0第4行松驰变量 =0第5行松驰变量 =0第6行松驰变量 =0第7行松驰变量 =0 “dual price”（对偶价格）表示当对应约束有微小变动时, 目标函数的变化率.输出结果中对应于每一个约束有一个对偶价格.若其数值为p， 表示对应约束中不等式右端项若增加1 个单位，目标函数将减少p个单位（min型问题）.显然，如果在最优解处约束正好取等号（也就是“紧约束”，也称为有效约束或起作用约束），对偶价格值才可能不是0.本例中：除了第6行都是紧约束，对应的对偶价格值分别为1、15、65、15、5、10.对于非紧约束（如本例中第6行是非紧约束），dual price 的值为0, 表示对应约束中不等式右端项的微小扰动不影响目标函数.有时, 通过分析dual price, 也可对产生不可行问题的原因有所了解.用matlab软件求解可知：c=-20,-20,-20,-25,-25,-25;a=1,0,0,1,0,0;0,1,0,0,1,0;0,0,1,0,0,1;1,-9,1,0,0,0;1,1,-9,0,0,0;0,0,0,1,-4,1;b=100,20,30,0,0,0;其中c表示目标函数的系数，a表示约束条件的系数矩阵，b表示约束条件满足的值.我们发现通过matlab软件编程得到的结果与lingo软件编程得到的结果相同,即生产计划为：生产硬糖需要80盎司的糖，10盎司的坚果和 10盎司的巧克力；生产软糖需要20盎司的糖，10盎司的坚果和10盎司的巧克力.并且两种方法求解得到的最大收入都是3250美分，因此该计划是最优的生产计划.参 考 文 献1 何坚勇编著最优化方法 m北京：清华大学出版社，2007：1-27.2 朱德通编著. 最优化模型与实验 m上海：同济大学出版社，2003：1-39.3 徐渝、贾涛编著. 运筹学（上册）m北京：清华大学出版社，2005：1-8.4 hamdy a. taha著.运筹学导论（英文版第8版）m北京：人民邮电出版社，2007：1-80.5 刘卫国编.matlab程序设计教程m北京：中国水利水电出版社，2001：1-180.6 谢金星，薛毅编注优化建模与lingo软件m北京：清华大学出版社，2005：1-280.附 录1、matlab软件的源程序clear;c=-20,-20,-20,-25,-25,-25;a=1,0,0,1,0,0;0,1,0,0,1,0;0,0,1,0,0,1;1,-9,1,0,0,0;1,1,-9,0,0,0;0,0,0,1,