Decision variables analysis for structured modeling

Journal of Harbin Institute of Technology( New Series ) , Vol. 9 ,No. 1 ,2002Decision variables analysis for structured modelingPAN Qi-shu ,HE Dong-bo，ZHANG Jie，HU Yun-quan潘启树,赫东波，张洁，胡运权( Management School , Harbin Institute of Technology , Harbin 150001 , China )but it is not quite addaptive to sig-nificant changes in environmental conditions. Therefore , Decision Variables Analysi( DVA ) ,a new modellingmethod is proposed to deal with linear programming modeling and changing environments. In variant linear pro-gramming , the most complicated relationships are those among decision variables. DVA classifies the decisionvariables into different levels using different index sets , and divides a model into different elements so that anychange can only have its effect on part of the whole model. DVA takes into consideration the complicated rela-tionships among decision variables at different levels , and can therefore sucessfully solve any modeling problemin dramatically changing environments.Key words : decision variables analysis ; model management ; stuctured modelingCLC number : TP391Document code : AArticle ID : 1005-9113( 2002 )01 -0049-060 INTRODUCTIONComparison shows clearly the capacity of the method.Its use is illustrated with a conclusion drawn in the lastModeling is the basis for model management ancsection.Dolk' 1] thinks that structured modeling , logic model-ing , and graph grammars are the three most important1FURTHER ANALYSIS OF STRUCTUREDmodeling methods. Structured modeling231 shares aMODELINGcommon ancestry with data modeling and underlies da-tabase management , entity relationship model in parti-There are three levels of structure for structuredcular. However , structured modeling has gone well be-modeling , elemental structure , generic structure andyond entity-relationship , and has particular relevance tomodular structure , and five elements in the elementalapplications in operation research and management sci-structure :ence. Logic modeling 31 originates largely from artificial* Primitive entity element ;intelligence concepts and relies on first order logic , andCompound entity element ;it not only represents models but also manipulate them.* Attribute element ;Graph grammar + J provides a graph-based paradigm forFunction element ;model representation and is especially effective fo*Test element.node-arc problems , such as network analysis. So evenGeneric structure functions to capture natural fa-now , the most appropriate modeling for MS/OR is stillmilial groupings of elements. Modular structure func-structured modeling.tionsto organize generic structure hierarchically to theStructured modeling was initally proposed by A Mappropriate and useful extent. Figs. 1 and 2 illustrateGeffrion to provide a general modeling method to sup-the element graph and genus graph of a simple modelport the whole model life cycle. However ,it is not sowith two nutrients and two materials well blended.convenient for modeling under changing environments.The modular outline is :For example , when the model is broken down into more&FEEDMIXfurther details ，the method is not flexible in dealing&NUT_ DATAwith changing decision variables. So , it is not free toNUTRdeal with the more practical and more complicatedMINproblems. Decision Variable Analysis( DVA ) is put& MATFRIAISforward to complement structured modeling. Structured中国煤化工modeling is further analysed in second section ，DVAYHCNMHG.method is given in the following section as an example.Reeived 2000-12- 1049.Journal of Harbin Institute of Technology( New Series ) ,Vol. 9 ,No. 1 ,2002Nutrition testprogramming because they form the relationship amongthe components of an optimization problem that cannuitsition levelstotal-costgenerally be divided into goal and constraint condi-tions. Some definitions and theorems are as defined be-ow :( 1 ) Levels of decision variables. Decision varia-unit cosquantity,bles can be classified to different levels by different? R 9sansets , so that we can find different levels of decisionvariables.( 2 ) Primary deoision variables and primary setsof decision variables. The set to which decision varia-nutrientsmaterialsbles naturally belongs by semantic is called the primaryFig. 1 Element graph for a 2 x 2 feedmix modelset of decision variables , and at the same time , thevariables are called primary decision variables. For ex-TNlevelample , quantity is the primary decision variable whilethe product is the primary set for a product-mix prob-Totcostlem , and the primary set in transportation is the Carte-sian product of suppliers and customers.A MinAnalysis. ,Ucost( 3 ) Nuclear decision variables. When the deci-sion variables are divided into further details by allB.kinds of relevant sets till they can not be divided anyNutrMaterialfurther , and the decision variables at this level arecalled nuclear decision variables.Fig.2 Genus graph for feedmix model( 4 ) Molecular decision variables. Decision varia-bles other than decision variables at nuclear level areANALYSIScalled molecular decision variables.( 5 ) Final decision variables. The variables whichNLEVELcan used to represent other levels of variables while theT :NLEVELmodel is finally constructed are called final decisionTOTCOSTIn structured modeling ，decision variables andPrimary or final decision variables can be nuclearfixed parameters are taken as two varieties of the samedecision variables sometimes , and they can also be mo-construction. Geoffrion thinks that this is appropriatelecular ones in other conditions.from the perspective of the whole modeling life cycle.Theorem 1 In linear programming , any molecu-However , decision variables are essential for modeling.lar variables can be presented by linear combination ofFor example , after we divide thgeneric graph into twonuclear variables.parts A and B according to the goal and constraint con-Theorem 2 In linear programming , any linearditions , we can see the intersection of A and B is Qfunction can be presented by linear combination of mo-the decision variable. So it can be seen that decisionlecular variables and nuclear variables.variables are the most important components of theThese two theorems are obvious ，the proof ismodel , and all the others surround them. Moreover ,ittherefore omitted.is inconvenient for structured modeling to deal withA DVA model consists of three main parts : deci-complicated relations among the variables ，becausesion variables and their interlationship , goal , and con-there is no tool for structured modeling , such as genusstraints ,and it represents the model in different partsgraph and element graph to help with the analysis ofso that any change to the model or conditions can onlydecision variables. For example ， according to thehave effects on part of it. The following is the modelingproblems in Appendix( a ) ,it is inconvenient to do anprocess by DVA :analyses by using the above two kinds of graphs. This* Determine primary decision variables accordingis mainly because the problem relate to different levelsto tlof decision variables.中国煤化工decision variables andtheir.TYHC N M H Gonship between primary2 DECISION VARIABLES ANALYSIS METHODsets and other sets.* Determine non-primary decision variables till2.1 Decision V ariables Analysis Fundamentalsnuclear decision variables are identified.Decision variables are important for mathematical* Establish inter relationship between different50-.Journal of Harbin Institute of Technology( New Series ), Vol. 9 ,No. 1 ,2002levels of decision variables.Material cost =unit cost * Q;: Specify the goal function.* Specify the constraint conditions in groups.， Specify the constraint conditions for groups.Constraints groups are as shown in Fig. 5. It2.2 Modeling by DVAmeans Q;≤Max amount.We will use the DVA to solve the problem in theAppendix. For modeling by DVA ,a model is dividedinto three parts : decision variables ，goal , and con-straints. Decision variables are divided into differentlevels ,and the constraints and the goal can be repre-sented by linear combination of different levels of deci-sion variables. So the important part of this method isto identify the relationship among different levels of de-CandiesMaterialcision variables. For the problems proposed in the Ap-pendix , we concentrated on their generic structures ,Fig.3 Relationship among decision variablesand gave only a generic graph of the model. Because itis very easy to comprehend the main spirit of the meth-Total profitod in an intuitional manner.2.2. I Modeling of part oneTotal salesotal materialTotal manuf-* Determine the primary decision variables ac-▲★acturing fetcostcording to the goal set.The goal is to define how to establish the quantityprice .Qunit feeUnit cost2)of products to achieve profit target. So it is easy to i- .dentify the quantity of candies as the primary decisionvariable , and the candy set as the primary decisionCandyvariable set. that is {candy } So the primary decisionvariables areQ; ,i∈{candy }.Fig. 4 Goal function* Determine the non-primary decision variablesand their sets according to the relationship between theT:Material testprimary sets and other sets.It is easy to establish the relationship betweencandies and material needed. SoQ; is related to the setMax material{materials } , and this level of the decision variablesare determined by the two sets. We specified the deci-sion variables asQ; ,i∈{candy }j∈{material } andit means that the consumption level of the materialj incandy i.Fig.5 Material constraintill the nuclear decision variables are identified.According to the problem , the nuclear variablesAccording to this question , we specified the finalare Qjdecision variable as Q; , although the nuclear decision* Establish the relationship between levels of de-variables are Qqcision variables.2.2.2 Modeling of part twoIt is obvious that the formula can be specified Q:When there is a change , for instance a new recipe: C;*Q; and another formula sumit ( Qj) = Q;,has been adopted in a candy factory ,as shown in Ap-where Q; means the total consumption of materialsj ,Cjpendix( b ) , what will be the change in the DVA mod-means the percentage composition of materialsj in can-eling ?We also determine the modification of the modelas shown below.dyi. The relation is as shown in Fig. 3.* Specify the goal function.According to the question , there is no change inThe goal is to establish the quantity of candies to .the中国煤化工ecision variables are asfollomaximize the profits. It can be seen from Fig. 4 that .Total profit = total sales - total manufacturing feeYHC NMHG:Q; ,i∈{candy }- total materials costNon-primary decision variables :Q; ,j∈{Materi-Sales= price, * Q;als }Manufacturing fee=unit fee * Q;Q; ,i∈{candy},j ∈{Materials }and the nuclear variables are Q;;.Journal of Harbin Institute of Technology( New Series ), Vol. 9 ,No. 1 ,2002* Establish the relationship between different lev-The manufacturing relation is divided into prod-els of decision variables.uct-by relationship and product- -on relationship.At this step ,C; is not a constant ,and we do notProduct- -by means the candies are produced by mate-specify them as decision variables. So the relation a-rial while product- -on means the candies are producedmong the variables can only be as shown in Fig. 6.in the production- -on the lines. The two relations canform into the compound relation produce- on- -by.hxWhen we specify the material consumption on one 0the production lines the relation consumption- -on isfound. So Q; is also related to the set {materials } , andthe set {lines } So three sets and four relations deter-mine the decision variables. We specified the decisionCandiesMaterialvariables asQq ,Qj QiandQjk ,whilei ∈{candy }jFig. 6 Relationship among decision variables∈{material }andh∈{line }.* Determine the non-primary decision variablesIt means thatQ; = sumK Qj)and Q; = sum (till the nuclear decision variables are found.Q;).We specified the nuclear variables as Q;* Specify the goal function.* . Find the relationship between different levels ofThe goal function remains the same as that in Fig.decision variables.4.It is obvious that the formula can be specified as* Specify the constraint conditions in groups.follows :The material constraints remain the same. We canQ;=sun(Q雅),Qx=sun(Qi)，Qj=add a group of analysis constrains as shown in Fig. 7.sun( Qg );So there are two groups of constraints : they are materi-Q; = sun( Q;) ,sun( Qax); ,Q, = sum( Q;) ,al constraints in Fig. 5 and the analysis constrains insun( Q;)k ,Qk = sum( Qin), ,sun( Q; ).Fig. 7. This constraint is as fllows :The relations are as shown in Fig. 8.Qf(≤or≥)c;Q;orQ;/Q(≤or≥)C;Q、Some of the Cj have no value if there is no limitwhen we use materials j in candy i , and other recipeQlimits can be represented in the above fomula.T:Analysis testQ/Q、C,MaterialsFig. 8 Relationship among decision variableIt can be seen from Fig. 9 that there will be somesmall changes in the goal function.Fig.7 Analysis constraintsTotal profits2.2.3 Modeling of part threeIt is very easy to construct a new model with envi-Total salesTotal manuf-ronments changed. We go on analysing the changes asacturing feetotal material costdescribed in Appendix( c ) . The changes in conditionsunit feesare significant at this time ,for a new line has been a-price;Unit cost, Qdopted. We also analyses the situation step by step.* Determine the primary decision variables ac-cording to the goal.中国煤化工At this step , primary decision variables Q; ,i∈MHCNMHGrgy UUal lunction{candy } remain unchanged.* . . Determine the non-primary decision variablesTotal profit = total sales - total manufacturing feeand their sets according to the relations between the- total material costprimary sets and other sets.52.Journal of Harbin Institute of Technology( New Series ), Vol. 9 ,No. 1 ,2002Sales = price; *Q; = price; * sum,( Qi )Gik means recipe parameters on different lines.Manufacturing fee = unit feex *Q;Fig.11 shows the new constraints of production capaci-Material cost = unit cost * Q;ty ,and each line has a maximum production capacity.* Specify the constraint conditions in groups.Constraints groups are as shown in Fig. 10 andT:CapacityFig. 11. Making only a lttle modification with thestructure in Fig. 7 can get Fig. 10. It means the follow-ing :Max capacityQu(≤or≥)CaQx or Qjg/Qa(≤or≥)C;T:AnalysisQg/QaFig.11 Capacity constraints2.2. 4 Comparison of three modelsNow we compare the three models. First , the ma-terial constraints remain unchanged in the three situa-tions. Second , the object function and the analysisconstraints changed very little. The decision variablesCandiesLineMaterialchanged a lot. So the DVA method can be adoptive tochanging environments ,if we use the method mainly toFig. 10 Analysis constraintsdeal with the changes of decision variables. The chan-ges are as shown in Table 1.Table 1 Changes to the modelModeling part IModeling part IIMaterials testHaveSameGoalLittle changeAnalysis testDecision variablesGreat changeCapacity test-Have .3 CONCLUSIONAPPENDIX( a) A candy factory produces three kinds of can-DVA can solve complicated linear program model-dies I ,II ,I using three kinds of materials A B (ing problems , and analyze decision variables by the re-The percentage of material in candies , material CoSlationship among the models and establish the levels ofthe maximum use of material per month , the price anddecision variables , the goal , and the groups of con-processing cost per kilogram are as shown in Table 2.straints step by step. For structured modeling ,all rela-If the demand for the condies is large , then the goal istionship among models must be given in elemental orhow to plan the outputs of three kinds of products so asgeneric graphs. When there is any change to the mod-to gain the maximum profit.el , the graph must be modified. In the case of DVA ,if( b) The factory gets a new recipe stating that theany part of the model is changed , the relevant con-candy can maintain its flavor by following the propor-straints and decisions variables will be modified andtions in Table 3. Other parameters do not change.probably only one level of decision variables must be( c )The factory gets a new source of materialschanged while the other levels remain the same. So therapacity is also increasedmethod becomes more useful for modeling by case-throu中国煤化工duction line. The newbased reasoning , because it can make adaptation natu-line|YHCN MH Gy the fllowing recipe.ral and easy. Last but not least , it is easy for DVA toThe new line s parameters and the material availableanalyze the complicated relations among levels of deci-are as shown in Table 4 and Table 5，and Table 6sion variables and solve linear programming modelingshows the capacities of the two lines.problems.Journal of Harbin Institute of Technology( New Series ) ,Vol. 9 ,No. 1 ,2002Table 2 ParametersMaterial costMaximum outputMaterials A60%15%20%2.002000Materials B25%30%.1.502500Materials C50%1.001200Processing cost0.500.400.30Price3. 402. 852.25Table 3 ParametersII≥60%≥15%-1.50≤20%≤60%≤50%Process fee0. 403.402.852. 25Table 4 Parameters for new production lineIReferences :≥50%≥10%[1] DOLK D R , KOTTEMAN J E. Model integration and atheory of models[ J ] Decision Support System ，1993≤15%(9)51 ~ 63.[2] GEOFFRION A M. An introduction to structured model-0.200. 10ing[ J ] Management Science , 1987 , 33( 5 ): 547 ~588.[3 ] GEOFFRION A M. The formal aspects of structured mod-eling[ J ] Operations Research , 1989 ,37( 1 ) :112.Table 5 Material supplies[4] JONES C V. An introduction to graph-based modelingsystems ,Part I :Overvien[ J ]. ORSA Journal of Com-puting ,1990(2):136~ 151.4000[5] LEE R M , KRISHNAN R. Logic as an integrated model-ing framework[ J ] Computer Science in Economics and5000Management , 1989( 2) :14.3000Table 6 Production capacity of two linesProduction capacityOld line8000New line7000中国煤化工MYHCNMHG.54.