Linear and Nonlinear Programming solutions

difference between linear and nonlinear programming models and methods of mathematical economics linear, what is the difference between linear and nonlinear programming problems
Dr.FlynnHanks Profile Pic
Dr.FlynnHanks,United States,Teacher
Published Date:26-07-2017
Your Website URL(Optional)
LinearandNonlinearProgramming 1Chapter1 INTRODUCTION 1.1 OPTIMIZATION The concept of optimization is now well rooted as a principle underlying the anal- ysis of many complex decision or allocation problems. It offers a certain degree of philosophicalelegancethatishardtodispute,anditoftenoffersanindispensablede- gree of operational simplicity. Using this optimization philosophy, one approaches a complex decision problem, involving the selection of values for a number of in- terrelatedvariables,byfocusingattentiononasingleobjectivedesignedtoquantify performance and measure the quality of the decision. This one objective is maxi- mized (or minimized, depending on the formulation) subject to the constraints that may limit the selection of decision variable values. If a suitable single aspect of a problem can be isolated and characterized by an objective, be it profit or loss in a business setting, speed or distance in a physical problem, expected return in the environment of risky investments, or social welfare in the context of government planning,optimizationmayprovideasuitableframeworkforanalysis. It is, of course, a rare situation in which it is possible to fully represent all the complexities of variable interactions, constraints, and appropriate objectives when faced with a complex decision problem. Thus, as with all quantitative techniques of analysis, a particular optimization formulation should be regarded only as an approximation. Skill in modeling, to capture the essential elements of a problem, andgoodjudgmentintheinterpretationofresultsarerequiredtoobtainmeaningful conclusions. Optimization, then, should be regarded as a tool of conceptualization andanalysisratherthanasaprincipleyieldingthephilosophicallycorrectsolution. Skillandgoodjudgment,withrespecttoproblemformulationandinterpretation of results, is enhanced through concrete practical experience and a thorough under- standing of relevant theory. Problem formulation itself always involves a tradeoff between the conflicting objectives of building a mathematical model sufficiently complex to accurately capture the problem description and building a model that is tractable. The expert model builder is facile with both aspects of this tradeoff. One aspiring to become such an expert must learn to identify and capture the im- 1920 Contents portantissuesofaproblemmainlythroughexampleandexperience;onemustlearn to distinguish tractable models from nontractable ones through a study of available technique and theory and by nurturing the capability to extend existing theory to newsituations. This book is centered around a certain optimization structure–that characteristic of linear and nonlinear programming. Examples of situations leading to this struc- ture are sprinkled throughout the book, and these examples should help to indicate how practical problems can be often fruitfully structured in this form. The book mainly, however, is concerned with the development, analysis, and comparison of algorithmsforsolvinggeneralsubclassesofoptimizationproblems.Thisisvaluable not only for the algorithms themselves, which enable one to solve given problems, but also because identification of the collection of structures they most effectively solvecanenhanceone’sabilitytoformulateproblems. 1.2 TYPESOFPROBLEMS The content of this book is divided into three major parts: Linear Programming, Unconstrained Problems, and Constrained Problems. The last two parts together comprisethesubjectofnonlinearprogramming. LinearProgramming Linear programming is without doubt the most natural mechanism for formulating avastarrayofproblemswithmodesteffort.Alinearprogrammingproblemischar- acterized,asthenameimplies,bylinearfunctionsoftheunknowns;theobjectiveis linearintheunknowns,andtheconstraintsarelinearequalitiesorlinearinequalities intheunknowns.Onefamiliarwithotherbranchesoflinearmathematicsmightsus- pect,initially,thatlinearprogrammingformulationsarepopularbecausethemathe- maticsisnicer,thetheoryisricher,andthecomputationsimplerforlinearproblems than for nonlinear ones. But, in fact, these are not the primary reasons. In terms of mathematicalandcomputationalproperties,therearemuchbroaderclassesofopti- mization problems than linear programming problems that have elegant and potent theories and for which effective algorithms are available. It seems that the popu- larity of linear programming lies primarily with the formulation phase of analysis rather than the solution phase–and for good cause. For one thing, a great number of constraints and objectives that arise in practice are indisputably linear. Thus, for example, if one formulates a problem with a budget constraint restricting the total amountofmoneytobeallocatedamongtwodifferentcommodities,thebudgetcon- straint takes the form x + x ≤ B, where x , i = 1,2, is the amount allocated to 1 2 j activity i, and B is the budget. Similarly, if the objective is, for example, maximum weight, then it can be expressed as w x + w x , where w , i = 1,2, is the unit 1 1 2 2 jContents 21 weightofthecommodityi.Theoverallproblemwouldbeexpressedas maximize w x +w x 1 1 2 2 subjectto x + x ≤ B, 1 2 x ≥ 0, x ≥ 0, 1 2 which is an elementary linear program. The linearity of the budget constraint is extremely natural in this case and does not represent simply an approximation to a moregeneralfunctionalform. Another reason that linear forms for constraints and objectives are so popular in problem formulation is that they are often the least difficult to define. Thus, even if an objective function is not purely linear by virtue of its inherent definition (as in theaboveexample),itisoftenfareasiertodefineitasbeinglinearthantodecideon some other functional form and convince others that the more complex form is the bestpossiblechoice.Linearity,therefore,byvirtueofitssimplicity,oftenisselected astheeasywayoutor,whenseekinggenerality,astheonlyfunctionalformthatwill beequallyapplicable(ornonapplicable)inaclassofsimilarproblems. Ofcourse,thetheoreticalandcomputationalaspectsdotakeonasomewhatspe- cial character for linear programming problems–the most significant development being the simplex method. This algorithm is developed in Chapters2 and 3. More recent interior point methods are nonlinear in character and these are developed in Chapter5. UnconstrainedProblems It may seem that unconstrained optimization problems are so devoid of structural properties as to preclude their applicability as useful models of meaningful prob- lems. Quite the contrary is true for two reasons. First, it can be argued, quite con- vincingly, that if the scope of a problem is broadened to the consideration of all relevant decision variables, there may then be no constraints—or put another way, constraints represent artificial delimitations of scope, and when the scope is broad- ened the constraints vanish. Thus, for example, it may be argued that a budget con- straintisnotcharacteristicofameaningfulproblemformulation;sincebyborrowing atsomeinterestrateitisalwayspossibletoobtainadditionalfunds,andhencerather than introducing a budget constraint, a term reflecting the cost of funds should be incorporated into the objective. A similar argument applies to constraints describ- ing the availability of other resources which at some cost (however great) could be supplemented. The second reason that many important problems can be regarded as having no constraints is that constrained problems are sometimes easily converted to uncon- strained problems. For instance, the sole effect of equality constraints is simply to limit the degrees of freedom, by essentially making some variables functions of others. These dependencies can sometimes be explicitly characterized, and a new22 Contents problem having its number of variables equal to the true degree of freedom can be determined. As a simple specific example, a constraint of the form x + x = Bcan 1 2 be eliminated by substituting x = B− x everywhere else that x appears in the 2 1 2 problem. Aside from representing a significant class of practical problems, the study of unconstrained problems, of course, provides a stepping stone toward the more gen- eral case of constrained problems. Many aspects of both theory and algorithms are mostnaturallymotivatedandverifiedfortheunconstrainedcasebeforeprogressing totheconstrainedcase. ConstrainedProblems Inspiteoftheargumentsgivenabove,manyproblemsmetinpracticeareformulated asconstrainedproblems.Thisisbecauseinmostinstancesacomplexproblemsuch as, for example, the detailed production policy of a giant corporation, the planning of a large government agency, or even the design of a complex device cannot be directlytreatedinitsentiretyaccountingforallpossiblechoices,butinsteadmustbe decomposed into separate subproblems—each subproblem having constraints that areimposedtorestrictitsscope.Thus,inaplanningproblem,budgetconstraintsare commonly imposed in order to decouple that one problem from a more global one. Therefore, one frequently encounters general nonlinear constrained mathematical programmingproblems. Thegeneralmathematicalprogrammingproblemcanbestatedas minimize f(x) subjectto h (x)= 0, i= 1,2, ..., m j g (x)≤ 0, j= 1,2, p j x∈ S. Inthisformulation,xisann-dimensionalvectorofunknowns,x= (x , x , ..., x ), 1 2 n and f, h, i= 1,2, ..., m,andg , j= 1,2, ..., p,arereal-valuedfunctionsofthe i j variables x , x , ..., x .ThesetS isasubsetofn-dimensionalspace.Thefunction 1 2 n f is the objective function of the problem and the equations, inequalities, and set restrictionsareconstraints. Generally, in this book, additional assumptions are introduced in order to make theproblem smoothinsomesuitable sense.Forexample,thefunctionsinthe prob- lemareusuallyrequiredtobecontinuous,orperhapstohavecontinuousderivatives. This ensures that small changes in x lead to small changes in other values associ- ated with the problem. Also, the set S is not allowed to be arbitrary but usually is required to be a connected region of n-dimensional space, rather than, for example, a set of distinct isolated points. This ensures that small changes in x can be made. Indeed, in a majority of problems treated, the set S is taken to be the entire space; thereisnosetrestriction.Contents 23 In view of these smoothness assumptions, one might characterize the problems treatedinthisbookascontinuousvariableprogramming,sincewegenerallydiscuss problemswhereallvariablesandfunctionvaluescanbevariedcontinuously.Infact, thisassumptionformsthebasisofmanyofthealgorithmsdiscussed,whichoperate essentiallybymakingaseriesofsmallmovementsintheunknownxvector. 1.3 SIZEOFPROBLEMS Oneobviousmeasureofthecomplexityofaprogrammingproblemisitssize,mea- suredintermsofthenumberofunknownvariablesorthenumberofconstraints.As might be expected, the size of problems that can be effectively solved has been in- creasing with advancing computing technology and with advancing theory. Today, with present computing capabilities, however, it is reasonable to distinguish three classes of problems: small-scale problems having about five or fewer unknowns and constraints; intermediate-scale problems having from about five to a hundred orathousandvariables;andlarge-scaleproblemshavingperhapsthousandsoreven millions of variables and constraints. This classification is not entirely rigid, but it reflects at least roughly not only size but the basic differences in approach that accompany different size problems. As a rough rule, small-scale problems can be solved by hand or by a small computer. Intermediate-scale problems can be solved on a personal computer with general purpose mathematical programming codes. Large-scale problems require sophisticated codes that exploit special structure and usuallyrequirelargecomputers. Much of the basic theory associated with optimization, particularly in nonlinear programming, is directed at obtaining necessary and sufficient conditions satisfied by a solution point, rather than at questions of computation. This theory involves mainly the study of Lagrange multipliers, including the Karush-Kuhn-Tucker The- orem and its extensions. It tremendously enhances insight into the philosophy of constrained optimization and provides satisfactory basic foundations for other im- portant disciplines, such as the theory of the firm, consumer economics, and opti- malcontroltheory.TheinterpretationofLagrangemultipliersthataccompaniesthis theory is valuable in virtually every optimization setting. As a basis for computing numericalsolutionstooptimization,however,thistheoryisfarfromadequate,since it does not consider the difficulties associated with solving the equations resulting fromthenecessaryconditions. If it is acknowledged from the outset that a given problem is too large and too complextobe efficientlysolvedbyhand (and henceit is acknowledgedthat a com- puter solution is desirable), then one’s theory should be directed toward develop- ment of procedures that exploit the efficiencies of computers. In most cases this leads to the abandonment of the idea of solving the set of necessary conditions in favor of the more direct procedure of searching through the space (in an intelligent manner)forever-improvingpoints.24 Contents Today, search techniques can be effectively applied to more or less general non- linear programming problems. Problems of great size, large-scale programming problems, can be solved if they possess special structural characteristics, especially sparsity,thatcanbeexploitedbyasolutionmethod.Todaylinearprogrammingsoft- ware packages are capable of automatically identifying sparse structure within the inputdataandtakingadvantageofthissparsityinnumericalcomputation.Itisnow notuncommontosolvelinearprogramsofuptoamillionvariablesandconstraints, as long as the structure is sparse. Problem-dependent methods, where the structure is not automatically identified, are largely directed to transportation and network flowproblemsasdiscussedinthebook. Thisbookfocusesontheaspectsofgeneraltheorythataremostfruitfulforcom- putation in the widest class of problems. While necessary and sufficient conditions are examined and their application to small-scale problems is illustrated, our pri- mary interest in such conditions is in their role as the core of a broader theory ap- plicable to the solution of larger problems. At the other extreme, although some instances of structure exploitation are discussed, we focus primarily on the gen- eral continuous variable programming problem rather than on special techniques forspecialstructures. 1.4 ITERATIVEALGORITHMSANDCONVERGENCE The most important characteristic of a high-speed computer is its ability to per- form repetitive operations efficiently, and in order to exploit this basic character- istic, most algorithms designed to solve large optimization problems are iterative in nature. Typically, in seeking a vector that solves the programming problem, an initial vectorx is selected and the algorithm generates an improved vectorx . The 0 1 processisrepeatedandastillbettersolutionx isfound.Continuinginthisfashion, 2 a sequence of ever-improving pointsx , x , ..., x ,..., is found that approaches a 0 1 k ∗ solution pointx . For linear programming problems solved by the simplex method, thegeneratedsequenceisoffinitelength,reachingthesolutionpointexactlyaftera finite (although initially unspecified) number of steps. For nonlinear programming problems or interior-point methods, the sequence generally does not ever exactly reach the solution point, but converges toward it. In operation, the process is termi- nated when a point sufficiently close to the solution point, for practical purposes, is obtained. The theory of iterative algorithms can be divided into three (somewhat overlap- ping)aspects.Thefirstisconcernedwiththecreationofthealgorithmsthemselves. Algorithms are not conceived arbitrarily, but are based on a creative examination of the programming problem, its inherent structure, and the efficiencies of digital computers. The second aspect is the verification that a given algorithm will in fact generate a sequence that converges to a solution point. This aspect is referred to as global convergence analysis, since it addresses the important question of whether the algorithm, when initiated far from the solution point, will eventually convergeContents 25 to it. The third aspect is referred to as local convergence analysis or complexity analysis and is concerned with the rate at which the generated sequence of points convergestothesolution.Onecannotregardaproblemassolvedsimplybecausean algorithm is known which will converge to the solution, since it may require an ex- orbitantamountoftimetoreducetheerrortoanacceptabletolerance.Itisessential whenprescribingalgorithmsthatsomeestimateofthetimerequiredbeavailable.It istheconvergence-rateaspectofthetheorythatallowssomequantitativeevaluation and comparison of different algorithms, and at least crudely, assigns a measure of tractabilitytoaproblem,asdiscussedinSection1.1. A modern-day technical version of Confucius’ most famous saying, and one which represents an underlying philosophy of this book, might be, “One good the- ory is worth a thousand computer runs.” Thus, the convergence properties of an it- erative algorithm can be estimated with confidence either by performing numerous computer experiments on different problems or by a simple well-directed theoreti- cal analysis. A simple theory, of course, provides invaluable insight as well as the desiredestimate. For linear programming using the simplex method, solid theoretical statements on the speed of convergence were elusive, because the method actually converges to an exact solution in a finite number of steps. The question is how many steps might be required. This question was finally resolved when it was shown that it was possible for the number of steps to be exponential in the size of the program. The situation is different for interior point algorithms, which essentially treat the problembyintroducingnonlinearterms,andwhichthereforedonotgenerallyobtain asolutioninafinitenumberofstepsbutinsteadconvergetowardasolution. For nonlinear programs, including interior point methods applied to linear pro- grams, it is meaningful to consider the speed of convergence. There are many dif- ferentclassesofnonlinearprogrammingalgorithms,eachwithitsownconvergence characteristics. However, in many cases the convergence properties can be deduced analytically by fairly simple means, and this analysis is substantiated by compu- tational experience. Presentation of convergence analysis, which seems to be the natural focal point of a theory directed at obtaining specific answers, is a unique featureofthisbook. There are in fact two aspects of convergence-rate theory. The first is generally knownascomplexityanalysisandfocusesonhowfastthemethodconvergesoverall, distinguishingbetweenpolynomial-timealgorithmsandnon-polynomial-timealgo- rithms. The second aspect provides more detailed analysis of how fast the method converges in the final stages, and can provide comparisons between different algo- rithms.Bothofthesearetreatedinthisbook. The convergence-rate theory presented has two somewhat surprising but defi- nitely pleasing aspects. First, the theory is, for the most part, extremely simple in nature.Althoughinitiallyonemightfearthatatheoryaimedatpredictingthespeed of convergence of a complex algorithm might itself be doubly complex, in fact the associated convergence analysis often turns out to be exceedingly elementary, re- quiringonlyalineortwoofcalculation.Second,alargeclassofseeminglydistinct algorithms turns out to have a common convergence rate. Indeed, as emphasizedChapter2 BASICPROPERTIESOFLINEAR PROGRAMS 2.1 INTRODUCTION A linear program (LP) is an optimization problem in which the objective function is linear in the unknowns and the constraints consist of linear equalities and linear inequalities.Theexactformoftheseconstraintsmaydifferfromoneproblemtoan- other,butasshownbelow,anylinearprogramcanbetransformedintothefollowing standardform: minimize c x +c x +...+c x 1 1 2 2 n n subjectto a x +a x +...+a x = b 11 1 12 2 1n n 1 a x +a x +...+a x = b 21 1 22 2 2n n 2 (1) . . . . . . a x +a x +···+a x = b m1 1 m2 2 mn n m and x 0, x 0, ..., x 0, 1 2 n wheretheb’s,c’sanda ’sarefixedrealconstants,andthe x’sarerealnumbersto i i ij i be determined. Wealways assume that each equation has been multiplied by minus unity,ifnecessary,sothateachb 0. i † Inmorecompactvectornotation, thisstandardproblembecomes T minimize c x subjectto Ax=b and x0. (2) T Herex is an n-dimensional column vector,c is an n-dimensional row vector,A is an m× n matrix, and b is an m-dimensional column vector. The vector inequality x0meansthateachcomponentofxisnonnegative. Before giving some examples of areas in which linear programming problems arise naturally, we indicate how various other forms of linear programs can be con- vertedtothestandardform. † SeeAppendixAforadescriptionofthevectornotationusedthroughoutthisbook. 2930 Example1. (Slackvariables).Considertheproblem minimize c x +c x +···+c x 1 1 2 2 n n subjectto a x +a x +···+a x 6 b 11 1 12 2 1n n 1 a x +a x +···+a x 6 b 21 1 22 2 2n n 2 . . . . . . a x +a x +···+a x 6 b m1 1 m2 2 mn n m and x 0, x 0, ..., x 0, 1 2 n In this case the constraint set is determined entirely by linear inequalities. The problemmaybealternativelyexpressedas minimize c x +c x +···+c x 1 1 2 2 n n subjectto a x +a x +···+a x +y = b 11 1 12 2 1n n 1 1 a x +a x +···+a x +y = b 21 1 22 2 2n n 2 2 . . . . . . a x +a x +···+a x +y = b m1 1 m2 2 mn n m m and x 0, x 0, ..., x 0, 1 2 n and y 0, y 0, ..., y 0. 1 2 m The new positive variables y introduced to convert the inequalities to equalities i are called slack variables (or more loosely, slacks). By considering the problem as one having n+ m unknowns x , x , ..., x , y , y , ..., y , the problem takes 1 2 n 1 2 m the standard form. The m× (n+ m) matrix that now describes the linear equality constraints is of the special form A, I (that is, its columns can be partitioned into two sets; the first n columns make up the original A matrix and the last m columns makeupanm×midentitymatrix). Example2. (Surplus variables). If the linear inequalities of Example1 are reversed sothatatypicalinequalityis a x +a x +···+a x b, i1 1 i2 2 in n i itisclearthatthisisequivalentto a x +a x +···+a x −y = b i1 1 i2 2 in n i i with y 0. Variables, such as y, adjoined in this fashion to convert a “greater than i i orequalto”inequalitytoequalityarecalledsurplusvariables. Itshouldbeclearthatbysuitablymultiplyingbyminusunity,andadjoiningslack andsurplusvariables,anysetoflinearinequalitiescanbeconvertedtostandardform iftheunknownvariablesarerestrictedtobenonnegative. Example3. (Free variables—first method). If a linear program is given in standard form except that one or more of the unknown variables is not required to be non-31 negative, the problem can be transformed to standard form by either of two simple techniques. To describe the first technique, suppose in (1), for example, that the restriction x 0 is not present and hence x is free to take on either positive or negative 1 1 values.Wethenwrite x = u −v , (3) 1 1 1 where we require u 0 and v 0. If we substitute u −v for x everywhere in 1 1 1 1 1 (1), the linearity of the constraints is preserved and all variables are now required to be nonnegative. The problem is then expressed in terms of the n+ 1 variables u , v , x , x , ..., x . 1 1 2 3 n There is obviously a certain degree of redundancy introduced by this technique, however, since a constant added to u and v does not change x (that is, the repre- 1 1 1 sentation of a given value x is not unique). Nevertheless, this does not hinder the 1 simplexmethodofsolution. Example4. (Free variables—second method). A second approach for converting to standard form when x is unconstrained in sign is to eliminate x together with one 1 1 of the constraint equations. Take any one of the m equations in (1) which has a nonzerocoefficientfor x .Say,forexample, 1 a x +a x +···+a x = b, (4) i1 1 i2 2 in n i where a , 0. Then x can be expressed as a linear combination of the other vari- i1 1 ables plus a constant. If this expression is substituted for x everywhere in (1), we 1 areledtoanewproblemofexactlythesameformbutexpressedintermsofthevari- ables x , x , ..., x only. Furthermore, the ith equation, used to determine x , is 2 3 n 1 now identically zero and it too can be eliminated. This substitution scheme is valid since any combination of nonnegative variables x , x , ..., x leads to a feasible 2 3 n x from (4), since the sign of x is unrestricted. As a result of this simplification, 1 1 we obtain a standard linear program having n− 1 variables and m− 1 constraint equations.Thevalueofthevariable x canbedeterminedaftersolutionthrough(4). 1 Example5. (Specific case). As a specific instance of the above technique consider theproblem minimize x +3x +4x 1 2 3 subjectto x +2x + x = 5 1 2 3 2x +3x + x = 6 1 2 3 x 0, x 0. 2 3 Since x isfree,wesolveforitfromthefirstconstraint,obtaining 1 x = 5−2x − x . (5) 1 2 3 Substituting this into the objective and the second constraint, we obtain the equiva- lentproblem(subtractingfivefromtheobjective)32 minimize x +3x 2 3 subjectto x + x = 4 2 3 x 0, x 0, 2 3 whichisaprobleminstandardform.Afterthesmallerproblemissolved(theanswer is x = 4, x = 0)thevaluefor x (x =−3)canbefoundfrom(5). 2 3 1 1 2.2 EXAMPLESOFLINEARPROGRAMMINGPROBLEMS Linear programming has long proved its merit as a significant model of numerous allocation problems and economic phenomena. The continuously expanding litera- ture of applications repeatedly demonstrates the importance of linear programming as a general framework for problem formulation. In this section we present some classicexamplesofsituationsthathavenaturalformulations. Example1. (The diet problem). How can we determine the most economical diet that satisfies the basic minimum nutritional requirements for good health? Such a problem might, for example, be faced by the dietitian of a large army. We assume thatthereareavailableatthemarketndifferentfoodsandthatthe jthfoodsellsata pricec perunit.Inadditiontherearembasicnutritionalingredientsand,toachieve j a balanced diet, each individual must receive at least b units of the ith nutrient per i day.Finally,weassumethateachunitoffood jcontainsa unitsoftheithnutrient. ij If we denote by x the number of units of food j in the diet, the problem then is j toselectthe x ’stominimizethetotalcost j c x +c x +···+c x 1 1 2 2 n n subjecttothenutritionalconstraints a x +a x +···+a x b, i= 1,...,m, i1 1 i2 2 in n i andthenonnegativityconstraints x 0, x 0, ..., x 0 1 2 n onthefoodquantities. This problem can be converted to standard form by subtracting a nonnegative surplus variable from the left side of each of the m linear inequalities. The diet problemisdiscussedfurtherinChapter4. Example2. (Manufacturing problem). Suppose we own a facility that is capable of manufacturing n different products, each of which may require various amounts of m different resources. Each product can be produced at any level x 0, j = j 1,2,...,n,andeachunitofthe jthproductcansellfor p dollarsandneedsa units j ij33 of the ith resource, i = 1,2,...,m. Assuming linearity of the production facility, if we are given a set of m numbers b , b , ..., b describing the available quantities 1 2 m ofthemresources,andwewishtomanufactureproductsatmaximumrevenue,ours decisionproblemisalinearprogramtomaximize p x + p x +···+ p x 1 1 2 2 n n subjecttotheresourceconstraints a x +a x +···+a x 6 b, i= 1,...,m i1 1 i2 2 in n i andthenonnegativityconstraintsonallproductionvariables. Example3. (The transportation problem). Quantities a , a , ..., a , respectively, 1 2 m of a certain product are to be shipped from each of m locations and received in amountsb , b , ..., b ,respectively,ateachofndestinations.Associatedwiththe 1 2 n shippingofaunitofproductfromoriginitodestination jisashippingcostc .Itis ij desiredtodeterminetheamounts x tobeshippedbetweeneachorigin–destination ij pairi= 1,2, ..., m; j= 1,2, ..., n;soastosatisfytheshippingrequirementsand minimizethetotalcostoftransportation. Toformulatethisproblemasalinearprogrammingproblem,wesetupthearray shownbelow: Theithrowinthisarraydefinesthevariablesassociatedwiththeithorigin,while the jth column in this array defines the variables associated with the jth destina- tion. The problem is to place nonnegative variables x in this array so that the sum ij across the ith row is a , the sum down the jth column is b , and the weighted sum j j ∑ ∑ n m c x ,representingthetransportationcost,isminimized. ij ij j=1 i=1 Thus,wehavethelinearprogrammingproblem: ∑ minimize c x ij ij ij n ∑ subjectto x = a for i= 1,2, ..., m (6) ij j j=1 m ∑ x = b for j= 1,2, ..., n (7) ij j i=1 x 0for i= 1,2, ..., m; j= 1,2, ..., n. ij34 Inorderthattheconstraints(6),(7)beconsistent,wemust,ofcourse,assumethat ∑ ∑ m n a = b which corresponds to assuming that the total amount shipped is i j i=1 j=1 equaltothetotalamountreceived. Thetransportationproblemisnowclearlyseentobealinearprogrammingprob- leminmnvariables.Theequations(6),(7)canbecombinedandexpressedinmatrix formintheusualmannerandthisresultsinan(m+n)×(mn)coefficientmatrixcon- sistingofzerosandonesonly. Example4. (The maximal flow problem). Consider a capacitated network (see Fig. 2.1, and Appendix D) in which two special nodes, called the source and the sink, are distinguished. Say they are nodes 1 and m, respectively. All other nodes must satisfy the strict conservation requirement; that is, the net flow into these nodes mustbezero.However,thesourcemayhaveanetoutflowandthesinkanetinflow. The outflow f of the source will equal the inflow of the sink as a consequence of the conservation at all other nodes. A set of arc flows satisfying these conditions is said to be a flow in the network of value f. The maximal flow problem is that of determining the maximal flow that can be established in such a network. When writtenout,ittakestheform minimize f n n ∑ ∑ subjectto x − x − f = 0 1j j1 j=1 j=1 n n ∑ ∑ x − x = 0, i, 1, m (8) ij ji j=1 j=1 n n ∑ ∑ x − x + f = 0 mj jm j=1 j=1 0≤ x ≤ k , foralli, j, ij ij wherek = 0forthoseno-arcpairs(i, j). ij Fig.2.1 Anetworkwithcapacities Example5. (A warehousing problem). Consider the problem of operating a ware- house,bybuyingandsellingthestockofacertaincommodity,inordertomaximize profitoveracertainlengthoftime.ThewarehousehasafixedcapacityC,andthere35 is a cost r per unit for holding stock for one period. The price, p, of the commod- i ity is known to fluctuate over a number of time periods— say months, indexed by i. In any period the same price holds for both purchase or sale. The warehouse is originallyemptyandisrequiredtobeemptyattheendofthelastperiod. To formulate this problem, variables are introduced for each time period. In par- ticular,let x denotethelevelofstockinthewarehouseatthebeginningofperiodi. i Let u denote the amount bought during period i, and let s denote the amount sold i i duringperiodi.Iftherearenperiods,theproblemis n ∑ maximize (p(s −u)−rx) i i i i i=1 subjectto x = x +u − s i= 1,2, ..., n−1 i+1 i i i 0 = x +u − s n n n x +z = C i= 2, ..., n i i x = 0, x 0, u 0, s 0, z 0, 1 i i i i where z is a slack variable. If the constraints are written out explicitly for the case i n= 3,theytaketheform −u + s +x =0 1 1 2 −x −u + s +x =0 2 2 2 3 x +z =C 2 2 −x −u + s =0 3 3 3 x +z =C 3 3 Note that the coefficient matrix can be partitioned into blocks corresponding to thevariablesofthedifferenttimeperiods.Theonlyblocksthathavenonzeroentries are the diagonal ones and the ones immediately above the diagonal. This structure istypicalofproblemsinvolvingtime. Example6. (Linear Classifier and Support Vector Machine). Suppose several d- dimensional data points are classified into two distinct classes. For example, two- dimensionaldatapointsmaybegradeaveragesinscienceandhumanitiesfordiffer- entstudents.Wealsoknowtheacademicmajorofeachstudent,asbeinginscience d orhumanities,whichservesastheclassification.Ingeneralwehavevectorsa ∈ E i d for i = 1,2, ..., n and vectors b ∈ E for j = 1,2, ..., n . We wish to find 1 j 2 a hyperplane that separates the a’s from the b ’s. Mathematically we wish to find i j d y∈ E andanumberβsuchthat T a y+β 1 foralli i T b y+β 6−1forall j, j T wherex : x y+β= 0 is the desired hyperplane, and the separation is defined by the+1and–l.Thisisalinearprogram.SeeFig.2.2.36 Fig.2.2 Supportvectorfordataclassification Example7. (Combinatorial Auction). Suppose there are m mutually exclusive po- tential states and only one of them will be true at maturity. For example, the states may correspond to the winning horse in a race of m horses, or the value of a stock index,fallingwithinmintervals.Anauctionorganizerwhoestablishesaparimutuel auction is prepared to issue contracts specifying subsets of the m possibilities that pay 1 if the final state is one of those designated by the contract, and zero oth- erwise. There are n participants who may place orders with the organizer for the purchase of such contracts. An order by the jth participant consists of an m-vector T a = (a , a , ..., a ) whereeachcomponentiseither0or1,aoneindicatinga j 1j 2j mj desiretobepaidifthecorrespondingstateoccurs. Accompanying the order is a numberπ which is the price limit the participant j is willing to pay for one unit of the order. Finally, the participant also declares the maximumnumberq ofunitsheorsheiswillingtoacceptundertheseterms. j The auction organizer, after receiving these various orders, must decide how many contracts to fill. Let x be the (real) number of units awarded to the jth or- j der.Thenthe jthparticipantwillpayπ x .Thetotalamountpaidbyallparticipants j j T isπ x,wherexisthevectorof x ’sandπisthevectorofprices. j If the outcome is the ith state, the auction organizer must pay out a total of ∑ n a x = (Ax) . The organizer would like to maximize profit in the worst possi- ij j j j=1 blecase,anddoesthisbysolvingtheproblem T maximize π x−max(Ax) i i subjectto 06x6q. Thisproblemcanbeexpressedalternativelyasselectingxandscalar sto37 T maximize π x− s subjectto Ax−1s60 06x6q where 1 is the vector of all 1’s. Notice that the profit will always be nonnegative, sincex=0isfeasible. 2.3 BASICSOLUTIONS Considerthesystemofequalities Ax=b, (9) wherex is an n-vector,b an m-vector, andA is an m×n matrix. Suppose that from the n columns of A we select a set of m linearly independent columns (such a set existsiftherankofAism).Fornotationalsimplicityassumethatweselectthefirst m columns of A and denote the m× m matrix determined by these columns by B. ThematrixBisthennonsingularandwemayuniquelysolvetheequation. Bx =b (10) B for the m-vector x . By putting x = (x ,0) (that is, setting the first m components B B ofx equal to those ofx and the remaining components equal to zero), we obtain a B solutiontoAx=b.Thisleadstothefollowingdefinition. Definition. Given the set of m simultaneous linear equations in n unknowns (9), let B be anynonsingularm×msubmatrixmadeupofcolumnsofA.Then,ifalln−mcomponents ofx not associated with columns ofB are set equal to zero, the solution to the resulting set ofequationsissaidtobeabasicsolutionto(9)withrespecttothebasisB.Thecomponents ofxassociatedwithcolumnsofBarecalledbasicvariables. In the above definition we refer to B as a basis, since B consists of m linearly m independent columns that can be regarded as a basis for the space E . The basic solution corresponds to an expression for the vector b as a linear combination of thesebasisvectors.Thisinterpretationisdiscussedfurtherinthenextsection. In general, of course, Eq. (9) may have no basic solutions. However, we may avoidtrivialitiesanddifficultiesofanonessentialnaturebymakingcertainelemen- tary assumptions regarding the structure of the matrix A. First, we usually assume that n m, that is, the number of variables x exceeds the number of equality con- j straints.Second,weusuallyassumethattherowsofAarelinearlyindependent,cor- responding to linear independence of the m equations.A linear dependency among the rows ofA would lead either to contradictory constraints and hence no solutions to(9),ortoaredundancythatcouldbeeliminated.Formally,weexplicitlymakethe followingassumptioninourdevelopment,unlessnotedotherwise.38 Full rank assumption. The m× n matrix A has m n, and the m rows of A are linearly independent. Undertheaboveassumption,thesystem(9)willalwayshaveasolutionand,infact, itwillalwayshaveatleastonebasicsolution. The basic variables in a basic solution are not necessarily all nonzero. This is notedbythefollowingdefinition. Definition. If one or more of the basic variables in a basic solution has value zero, that solutionissaidtobeadegeneratebasicsolution. We note that in a nondegenerate basic solution the basic variables, and hence the basisB,canbeimmediatelyidentifiedfromthepositivecomponentsofthesolution. There is ambiguity associated with a degenerate basic solution, however, since the zero-valuedbasicandsomeofnonbasicvariablescanbeinterchanged. Sofarin the discussion of basic solutions we havetreated only the equality con- straint (9) and have made no reference to positivity constraints on the variables. Similardefinitionsapplywhentheseconstraintsarealsoconsidered.Thus,consider nowthesystemofconstraints Ax=b, x0, (11) whichrepresenttheconstraintsofalinearprograminstandardform. Definition. Avectorxsatisfying(11)issaidtobefeasiblefortheseconstraints.Afeasible solutiontotheconstraints(11)thatisalsobasicissaidtobeabasicfeasiblesolution;ifthis solutionisalsoadegeneratebasicsolution,itiscalledadegeneratebasicfeasiblesolution. 2.4 THEFUNDAMENTALTHEOREMOFLINEAR PROGRAMMING In this section, through the fundamental theorem of linear programming, we estab- lish the primary importance of basic feasible solutions in solving linear programs. The method of proof of the theorem is in many respects as important as the result itself, since it represents the beginning of the development of the simplex method. The theorem (due to Caratheodory) ´ itself shows that it is necessary only to con- sider basic feasible solutions when seeking an optimal solution to a linear program becausetheoptimalvalueisalwaysachievedatsuchasolution. Correspondingtoalinearprograminstandardform T minimize c x subjectto Ax=b, x0 (12) a feasible solution to the constraints that achieves the minimum value of the objec- tive function subject to those constraints is said to be an optimal feasible solution. Ifthissolutionisbasic,itisanoptimalbasicfeasiblesolution.39 Fundamental theorem of linear programming. Given a linear program in standard form (12)whereAisanm×nmatrixofrankm, i) ifthereisafeasiblesolution,thereisabasicfeasiblesolution; ii) ifthereisanoptimalfeasiblesolution,thereisanoptimalbasicfeasiblesolution. Proofof(i).DenotethecolumnsofAbya , a , ..., a .Supposex= (x , x , ..., x ) 1 2 n 1 2 n isafeasiblesolution.Then,intermsofthecolumnsofA,thissolutionsatisfies: x a + x a +···+ x a =b. 1 1 2 2 n n Assumethatexactly pofthevariables x aregreaterthanzero,andforconvenience, i thattheyarethefirst pvariables.Thus x a + x a +···+ x a =b. (13) 1 1 2 2 p p There are now two cases, corresponding as to whether the set a , a , ..., a is 1 2 p linearlyindependentorlinearlydependent. case 1: Assumea , a , ..., a are linearly independent. Then clearly, p6 m. If 1 2 p p = m, the solution is basic and the proof is complete. If p m, then, since A has rank m, m− p vectors can be found from the remaining n− p vectors so that the resulting set of m vectors is linearly independent. (See Exercise 12.) Assigning the valuezerotothe correspondingm− p variablesyieldsa (degenerate)basicfeasible solution. case 2: Assume a , a , ..., a are linearly dependent. Then there is a non- 1 2 p trivial linear combination of these vectors that is zero. Thus there are constants y , y , ..., y ,atleastoneofwhichcanbeassumedtobepositive,suchthat 1 2 p y a +y a +···+y a =0. (14) 1 1 2 2 p p Multiplyingthisequationbyascalarεandsubtractingitfrom(13),weobtain (x −εy )a +(x −εy )a +···+(x −εy )a =b. (15) 1 1 1 2 2 2 p p p Thisequationholdsforeveryε,andforeachεthecomponentsx −εy correspondto j j asolutionofthelinearequalities—althoughtheymayviolate x −εy 0.Denoting i i y= (y , y , ..., y , 0,0, ..., 0),weseethatforanyε 1 2 p x−εy (16) isasolutiontotheequalities.Forε= 0,thisreducestotheoriginalfeasiblesolution. Asε is increased from zero, the various components increase, decrease, or remain constant,dependinguponwhetherthecorrespondingy isnegative,positive,orzero. i Sinceweassumeatleastoney ispositive,atleastonecomponentwilldecreaseasε i isincreased.Weincreaseεtothefirstpointwhereoneormorecomponentsbecome zero.Specifically,weset ε= minx/y : y 0. i i i40 For this value ofε the solution given by (16) is feasible and has at most p−1 pos- itive variables. Repeating this process if necessary, we can eliminate positive vari- ablesuntilwehaveafeasiblesolutionwithcorrespondingcolumnsthatarelinearly independent.AtthatpointCase1applies. v Proof of (ii). Letx= (x , x , ..., x ) be an optimal feasible solution and, as in 1 2 n theproofof(i)above,supposethereareexactly ppositivevariables x , x , ..., x . 1 2 p Again there are two cases; and Case 1, corresponding to linear independence, is exactlythesameasbefore. Case 2 also goes exactly the same as before, but it must be shown that for anyε the solution (16) is optimal. To show this, note that the value of the solutionx−εy is T T c x−εc y. (17) For ε sufficiently small in magnitude, x−εy is a feasible solution for positive or T T negative values ofε. Thus we conclude thatc y= 0. For, ifc y , 0, anε of small magnitude and proper sign could be determined so as to render (17) smaller than T c x while maintaining feasibility. This would violate the assumption of optimality T ofxandhencewemusthavec y= 0. Havingestablishedthatthenewfeasiblesolutionwithfewerpositivecomponents is also optimal, the remainder of the proof may be completed exactly as in part (i). v This theorem reduces the task of solving a linear program to that of searching over basic feasible solutions. Since for a problem having n variables and m con- straintsthereareatmost ( ) n n = m m(n−m) basicsolutions(correspondingtothenumberofwaysofselectingmofncolumns), thereareonlyafinitenumberofpossibilities.Thusthefundamentaltheoremyields an obvious, but terribly inefficient, finite search technique. By expanding upon the techniqueofproofaswellasthestatementofthefundamentaltheorem,theefficient simplexprocedureisderived. It should be noted that the proof of the fundamental theorem given above is of a simple algebraic character. In the next section the geometric interpretation of this theorem is explored in terms of the general theory of convex sets. Although the geometric interpretation is aesthetically pleasing and theoretically important, the reader should bear in mind, lest one be diverted by the somewhat more advanced argumentsemployed,theunderlyingelementarylevelofthefundamentaltheorem. 2.5 RELATIONSTOCONVEXITY Our development to this point, including the above proof of the fundamental theo- rem, has been based only on elementary properties of systems of linear equations. These results, however, have interesting interpretations in terms of the theory of

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.