LIBRARY Michigan State W This is to certify that the thesis entitled APPLICATION OF OPTIMIZATION THEORY IN BIOMECHANICS presented by Diane Marie Pietryga has been accepted towards fulfillment of the requirements for _M._S_._ degree in Jenhanica. @aswm Major professor Date 2/20/87 0-7839 MSU it all M Action/Equal Opportunity Institution MSU LIBRARIES “ RETURNING MATERIALS: Place in book drop to remove this checkout from your record. FINES will be charged if book is returned after the date stamped below. APPLICATION OF OPTIMIZATION THEORY IN BIOMECHANICS By Diane Marie Pietryga A.THESIS Smeitted to Michigan State University in partial fulfillment of the requirements for the degree of ‘MASTER.OF SCIENCE Department of Metallurgy, Mechanics and Materials Science 1987 ABSTRACT APPLICATION OF OPTIMIZATION 'IHEDRY IN BIOVIEEHANICS By Diane Marie Pietryga The purpose of this research was to investigate optimization criteria for the redundant bicmechanical problem, in which the muscle forces act as the unknowns . Three optimization problens of the lumbar spine were formulated: the linear problens of minimizing the upper bound of muscle stress and of minimizing the spinal canpression and the nonlinear problem of minimizing the summation of muscle stress to the nith power. The nonlinear problen is based on naximum endurance of musculoskeletal function, where the parameter n i is based on the percentage of slow twitch fibers . The linear criterion of minimizing the upper bound of nuscle stress predicted a more even distribution of nuscle stress among the synergistic nuscles and a greater distribution of nuscle activity canpared to the other two objective functions. 'Ihe criterion of minimizing the spinal caupression was examined, and it was noted that the upper bounds of muscle stress seened to limit the solution more than spinal canpression . The author wishes to express her appreciation to the following people for Inaking the canpletion of her Master of Science degree possible: To Dr. Robert Wm. Soutas-Little, her najor professor, for his friendship, encouragenent and invaluable guidance in this project. To Dr. Alejandro Diaz, for his assistance in this project and for serving on her catmittee. To Dr. George E. wise, for serving on her carmittee and for his warm friendship. To Dr. James J. Rechtien, for serving on her carmittee. To Brooks Shoe, Incorporated, for their generous funding of this project. To Brenda K. Miller, for her warm friendship and patience in the seeningly endless chore of typing this manuscript. To Andrew Hull, for his assistance in carputer program developnent. 'Ib Daniel D. Lauderback, her best friend, for his endless support and encouragenent and, most of all , for his priceless friendship. To her family, especially her parents, for their understanding, encwragenent and support in her acadenic pursuits . ii TABIEOFWS Page I..IS'I’OFFIGURE‘S .......... v Section I. IN'I‘RODIIII‘ION ............................................... 1 II. SURVEYOFIJTERAIURE ...... ...... 4 III. AMLYTICALMEI‘HODSANDRESULTSHHNHHHHH ...... ....... 15 APPENDIXA-SIMPLEXME’IHOD...................................... 46 APPENDIXB-GENERAUZEDRHDUCEDGRADIENPDEIHGDWW . 53 BIBLICXERAPHY... ...... ........ ............ .... ........ ............ 58 iii LISTOFTABLES Body Segment Weights and Mass—Center locations .......... CfOSS-SGCtional maic mtaoooooooooooooo ...... o ooooo Transverse Section Through the Abdanen at L3 ........ . . . . Three-Dimensional Optimal Solutions .......... . . . . . . ..... Optimum load and Stress Data frcm the Criterion of Minimizing the Upper Bound of Muscle Stress ...... . ........ Stress Data fren the Criterion of Minimizing the Upper Bound of Muscle Stress. . ............................ Optiimmi load and Stress Data fran the Criterion of Minimizing the Ccmpression on the L3 Lumbar Vertebra. ..... SlowTwitch Fiber Parameters ...... . .............. (mtiimim load and Stress Data fran the Endurance Criterion. load Values of Nonlinear Criteria ......................... iv Page 20 22 24 28 31 32 33 35 3'7 41 LIST W FIGURES Figure l. EctemalSysten ........................................... 3. DcmainFormedbythe Inequality Constraints............... 4. Equality Constraint Planes ...... ................... 5. Solution Space DefinedbytheConstraJnts 6 . Erector Equivalent Space .................................. 7. Latissimus Dorsi Space .................................... Page l7 19 26 27 29 38 39 IN'IWDIIZ‘I'ION The methods of optimization theory are now being applied to the analysis of the redundant muscular system, in which the muscles are active elements . The skeletal system, connected through ligaments and muscles , provides vital structural support for the human body. load- sharing among the structures of the musculoskeletal systen has not been subjected to extensive study. The lumbar spine, due to the widespread problem of low-back pain, is one structure requiring investigation of the muscle interactions . Most adults will suffer from sane form of low—back pain during the course of their lives. According to sane estimates, as much as one quarter of the population will lose time from the job or will have to curtail recreational activities . Many people will become permanently disabled by low-back problems . Since low-back conditions are a leading cause of compensation costs to industry, it becomes not only a serious physical problem to the individual sufferer, but a major socioeconcmic disability as well . Far too little is known about what causes low-back pain and how it can be prevented or effectively treated. Although muscle may not be the primary participant in the cannon low—back pain syndrcme , it may have significant influence on its onset and outcome. For this reason, engineers and physicians are collaborating in the effort to understand the mechanical basis of musculature in low-back pain and to design programs for its prevention and treatment. 2 As stated earlier, optimization methods are now being used to determine muscular activity . The study of a practical optimization problem requires a realistic representation of the physical system by means of a suitable mathematical model and the formulation of an appropriate performance criterion . The mathematical model must describe correctly, at least , the qualitative features of the practical system in the range of operating conditions, and the performance criterion must represent an optimal characteristic of the system. The concept of optimization is well rooted as a principle underlying the analysis of many complex decision problems. It offers a certain degree of philosophical elegance that is hard to dispute, and it now offers an indispensible degree of operational simplicity. Over the last few decades there has been a steady shift in applied optimization from the status of an art to that of a scientific discipline. In the past, most of the theory of optimization concentrated on the subject of optimality conditions , and practical methods of computation were rarely investigated. Today, due to the interaction between mathematicians and engineers , theory and practice are better integrated. To a large degree, this trend has been fostered by the development of high—speed computers with which large-scale problem can be solved with an exactness that previously was unapproachable . Computer availability has given rise to new optimization techniques and has enhanced previously developed ones . Consequently, practitioners of many disciplines are building large scale optimization models and solving them routinely with linear and nonlinear programming . Linear programming is a mechanism for formulating a vast array of problem with modest effort. A linear programming problem is characterized, as the name implies, by linear functions of the urflmcvms; the objective function is linear in the unknowns and the constraints are linear equalities or linear inequalities in the unknowns. The linear structure insures that the extremmm will lie at the intersection of two or more constraints . This greatly reduces the number of possible locations for the extremum. Efficient algorithim that inspect this limited region of solution space have been developed with the most significant of these being the simplex method. This method can be referenced in Appendix A. Alternatively, nonlinear programming pertains to optimization problem in which the objective function and/or the constraints have nonlinear mathematical forms . The constraints , which are classified either as equalities or inequalities, define the solution space from which an optimal solution is to be obtained. Characteristic of nonlinear problem , there are no general techniques for solving a problem, but only special ones , each covering a particular class of practical problem . The geieralized reduced gradient method, which can be referenced in Appendix B, was used for solving the nonlinear optimization problem presented in this literature. SURVEYOFIJ'JERATURE ‘Ihe hurman musculoskeletal system can be considered as a system of rigid articulating segments on which known external forces (weight, ground reaction, external load) and unknown muscle, ligament and joint forces are acting. Relationships between known external forces and the unknown musculoskeletal or internal forces can be obtained from force and marent equilibrium equations . Since more muscles than are mechanically necessary normally cross a joint, the number of unknown forces will in general exceed the number of equilibrium equations . This mechanical redundancy yields the problem statically indeterminate . In statically determinate problem , internal and external forces can be determined by the use of free body diagrams and equilibrium equations . Hmever , in statically indeterminate problem the equilibrium equations must be caiplemented by relations involving deformations . These deformations are obtained by considering the gearetry of the problem and they must be carpatible with the external supports . By considering engineering structures as deformable and analyzing the deformations in their various members , it is possible to carpute forces which are statically indeterminate . Unfortunately, the aforementioned method cannot be applied to the indeterminate musculoskeletal problem. Since muscular load and deformation depend on the amount of muscle contraction the exact muscular load cannot readily be determined from load-deformation diagrams . For example , in isaretic contraction, no overall length change exists between muscle origin and insertim. A method for solving the problem of indeterminancy is reduction of the excess number of unknown variables. This is acccnplished by either grouping functionally similar muscles together, or by eliminating individual muscles based on electramyographic observation. However , these anatomical simplifications may induce considerable error and the mechanical action of individual muscles is obscured. Alternatively, optimization methods have also been used to obtain a unique solution. By using an optimization method, not only can a solution be obtained , but possible physiologically based rationales for the solution can be associated. This approach erploys a model of the inherent muscle selection process. The model is based upon the assumption that the selection process represents an optimal behavior of the bicmechanical system. The optimal response approach provides a consistent basis for a tractable mathetatical formulation of the problem and suggests an interesting qualitative picture of muscle response . Various optimization criteria rave been developed over the last twenty years . These criteria include minimization of : l. Summation of muscle force, 2 Fi 2 . Summation of ratios , 2 (Pi/Fimax)’ 2(Fi/Ai) 3 . Weighted summation of muscle force , ligament mments and joint reactions, * * Z Fi + C1 (ij + ij + sz) + C2 Rjoint 4. Spinal campression, C S. Squares of muscular forces, ratios and vertebral stresses, £(Fi)2, 2(Fi/Ai)2, 2(Fi/Fimx)2, 2(ri)2 6. Muscular fatigue (maximize activity eidurance), ( 2(Si)n)1/n, and maximize the minirmmm of Tiend where Tieid = ai*((Fi/Fimax)*loo)ni 7. The upper bound of muscle stress, Si 8. The free energy input to the muscles, E Each of these criteria will now be discussed in detail. In 1967, McConaill defined the "Principle of Minimal Total Mascular Force" , which postulates that no more total muscular force than is both necessary and sufficient to maintain a posture or perform a motion would be used. Accordingly, this would minimize the sum of the muscle forces, namely ZFi (15). This criterion was used by several investigators to analyze muscle force in static situations . In 1972, Barbenel calculated the muscular forces at the terporamandibular joint (2) . He concluded that the suggested minimum muscle force principle did not apply. In 1973, Seireg and Arvikar analyzed the forces in the lower extremities in standing, leaning and stooping postures (22) . Other investigators have studied muscles of the upper limbs. Penrod presented, in 1974, a biarechanical analysis of a simplified biaxial model of the wrist (18). In 1976, Yeo used a study of elbow flexion to examine the validity of the minimum force criterion. His theoretical results contradicted the experimental results; therefore, it was concluded that MacOonaill ' s hypothesis of minimal total muscular force was invalid (28). The minimum force criterion was also used for the analysis of forces in the leg during level walking by Hardt and Pedotti et al. in 1978, and Patriarco et al. in 1981 (12, 16, 17). Pedotti et a1. and Patriarco et a1. eiployed additional , physiologically based constraints to improve the muscle force predictions . Pedotti et al. also used a criterion consisting of the sum of ratios of muscular force to maximum possible muscle force, 2(Fi/me), and applied this to the analysis of forces in the leg during level walking (17) . This criterion was eiployed because it enhances the total muscular force criterion by utilizing the muscles more efficiently by deranding larger force production from the larger muscles; moreover , it takes into account the instantaneous state of each muscle , since F imax depends upon the instantaneous length of muscle as well as its velocity. Crowninshield and fellow investigators employed a total muscle tensile stress criterion, 2(Fi/Ai) (6) . The physiological cross-sectional area, Ai, was determined by muscle volume divided by its length. They studied forces in the arm muscles during isometric and isokinetic elbow flexion and forces at the hip duing level walking, climbing, domcending stairs and rising from a sitting position. Another type of linear objective function was exployed by Seireg and Arvikar in 1973 and 1975 (22, 23). They used a weighted sum of muscle forces and ligament moments for analysis of forces in the legs in standing, leaning and stooping postures and quasi-static walking. The weighting factors can be different for each problem and were chosen in order to get reasonable results . A weighting factor between four and infinity was found to be applicable to all the investigated postures. It is difficult to make a physiological interpretation of this kind of empirically adjustable objective function. However, William and Seireg also used this type of criterion in 1977 and 1979 for the prediction of muscle forces in the jaw and in the leg during bicycling and by Yettram and Jackman in 1980 for the analysis of forces in the vertebral column (26 , 27 , 29) . In 1978 , Hardt concluded that the minimum force criterion yielded a purely geometric optimization, whereby the set of muscle mment arm vectors which produce the lowest muscle forces will be choosen over all other possibilities . Consequently, the only representation of the muscles in the mathetatics is in the form of their moment arms, ignoring the physiology of the system. To incorporate sate physiological properties into the problem, Hardt proposed to define a cost function that would minimize the instantaneous energy requiremnts of the muscles. This formulation was used for the prediction of muscle forces during walking and it revealed an increased number of muscles participating in the moverent (12) . Patriarco et al . supported this formulation in 1981 (16). In 1981, Schultz and Andersson presented a model for internal force estimation of the lumbar trunk. They chose to minimize the compression on the lumbar vertebra (20). This criterion was applied to several physical activities including nonsymetric weight-holding, resisting a push to the left and resisting a lmgitudinal twist mment. Schultz, et al., in 1982, used linear programming to investigate the load on lumbar trunk structures during various mysical tasks including flexion-extension, lateral heading, and torsion (21). The different objective functions were applied, the first minimized the expressive load on the lumbar vertebra and the second minimized the largest muscle force crossing the lumbar vertebra . Myoelectric measureients did not reveal much difference between the cost functions. Unfortunately , the results of a linear criterion are not always physiologically consistent, and this has bee) noted by most investigators . When muscle force is the variable used to formulate the load sharing criterion, there is a preference for muscles with large matent arms. When muscle stresses, or ratios of muscle force to maximum muscle force are used as the variable in the criterion, there is preference for muscles with the largest product of matent arm and cross- sectional area . Investigators improved the predictions of muscle forces with linear criteria by formulating additional physiologically based constraints. This enforced synergism between the muscles. Nonlinear objective functions can predict synergism, even without the formulation of additional constraints. It is thought that linear optimization was used more for reasons of matheratical convenience than for reasons of physiological requirerent . Investigators are now erphasizing the importance of selecting muscle prediction criteria based on sound physiological bases rather than m an arbitrary or mathematically convenient basis . Unfortunately, nonlinear optimization convergence on a global minimum is not assured. In 1977, Gracovetsky et a1. defined an objective function of the sum of squared shear stresses in the vertebral column and predicted forces during weight lifting (ll) . This criterion was developed based on a study finding compression to have relatively minor effects on the spine compared to shear effects. This result can be explained by considering that the spine is built to take a corptression load but that any shear effect cannot readily be compensated. This criterion was 10 modified to a quadratic objective function, that minimized shear and penalized excessive muscle power, in 1981 by Gracovetsky et a1. (10). For the analysis of walking, Pedotti et al., in 1978, used the sum of squared muscle forces, which is a sort of power criterion. This criterion not only minimizes total muscular force, it also penalizes large individual muscle forces. They also used the sum of squared ratios of muscle force to maximum muscle force, namely 2 (Fi/me)z. This criterion was selected as the most feasible since it used the muscles most efficiently while keeping their level of activation as low as possible (17) . In 1981, Crowninshield and Brand presented an optimization method which uses a criterion of maximum endurance of musculoskeletal function (4). The method is based on the inversely nonlinear relationship of muscular force and contraction endurance . This relationship was proposed to be of the form: 1nT=-n*(ln f) +c where T is the maxinmmm time of contraction, f is the contractile force , arnd n and c are experimentally obtainable constants . They suggested that the muscle selection to maximize activity endurance is physiologically reasonable during many normal activities , particularly prolonged and repetitive activities , such as normal gait. This criterion is not applicable to all fonm of locamtion such as activities occurring to maximize speed or to minimize pain. Based on several reports, Crowninshield and Brand assumd that, in an approximate manner , the muscle force-endurance relationship is a basic property of muscle tissue (4). They suggested that the maximum endurance of a muscle contraction is thus related to the magnitude of 11 the average stress within the muscle tissue. The determination of muscle force during body function may then be formulated as a nonlinear optimization problem with an objective to minimize the summation of muscle stress to the nth power. The parameter, n, is dependent on the percentage of slow twitch fibers. Muscle forces predicted in this manner will tend to keep individual muscle stresses low. low individual muscle stresses are achieved by predicting force activity in numerous muscles and preferentially predicting force in muscles with large cross- sectional areas and long mment arms . Since individual muscle stresses are low their potential for prolonged contraction will be high. The actual value of n may vary between individual subjects and individual muscle due to fiber type and fiber orientation. Since accurate and detailed experimental data were not available n = 3 was selected as a reasonable value, as it is the average value reported in literature. To reduce the magnitude of the objective function, thereby avoiding numerical problem in large scale optimization, the function is rnormalized. The criterion has the form [£(Fi/Ai)3]1/3, where m is the number of muscles . This method was deionstrated at the elbow during iscmetric contraction and in the lower extremity during locorotion. During gait , the observed muscle activity pattern in the lower extremities , as detenmirned by HG, shows substantial agreemnt with that activity pattern predicted when endurance is used as the optimization criterion. In addition, since this problem has a continuous convex character of the objective function and the linear constraints it falls into the category of convex programming. This convexity assures that the only minimum is a global or absolute miniImmm. 12 Dul et al., in 1984, presented a similar criterion which is based on the hypothesis that muscular fatigue is minimized during learned endurance activities (7) . An endurance type of activity such as constrained sitting posture or walking, involves sustained or repetitive muscular contractions . These contractions are fatiguing, and after a specific period of time , the endurance time, the required mechanical output cannot be maintained anymore . It is assumed that the neuranuscular system anticipates this by selecting a load sharing between the muscles such that endurance time of the activity is maximized, hence muscular fatigue minimized. Again, this concept may be less useful for other types of activity where quick contractions are involved. Dul's criterion is to maximize the minimum of Ti where Ti=ai(Fi*lOO/Fimx)ni. Ti is the endurance time and F1 is the force for the ith muscle. The constants ai and ni are muscle parameters depending on the percentage of slow twitch fibers for the respective muscle. The criterion was used to determine forces in the lower extremities during static-isotetric knee flexicn. The predicted muscular load sharing was in good agreement with direct force measuremnt data. In comparison with Crowninshield and Brand, the general pattern of load sharing is similar, yet the predicted magnitude of the muscle force is not the same. The cubic criterion predicted linear synergism, whereas the minimum-fatigue criterion predicts non-linear synergism. Both criteria predict that there is relatively more force in muscles with large cross- sectional areas . For the cubic criterion more force is also allocated to muscles that have large moment arms . The load sharing predicted with the minimum fatigue criterion does not depend on marent arm, although 13 the absolute force levels do depend on this variable . Instead, relatively more force is allocated to muscles with a high percentage of slow-twitch fibers . This reveals the pertinence of incorporating muscle fiber types into the problem. A new optimization approach, based on minimizing the upper bound of muscle stress, was introduced in 1984 by An et a1. (1). The concept of this new optimization approach is quite different from those previously used in sumations of muscle force or stress, or their nonlinear combinations . Optimization procedures used to minimize the sum of unknown force variables have been more or less based on consideration of overall efforts of the system. However, from an energy storage and transport viewpoint, each muscle bundle has its own storage and blood supply . Therefore, in constructing the optimization criteria for this new technique, individual muscle effort was considered. Since this technique allows a solution which considers more even distribution of muscle stress among all synergistic muscles, it will favor the muscular response with the largest endurance for the task. The criterion of minimizing the upper bound of muscle stress was applied to a simplified model of the elbow joint. For conparison purposes , this problem was also solved using other previously mentioned objective criteria. These included minimizing the sumation of muscle forces and summation of muscle stress using the linear optimiztion method, as well as minimizing the summation of the square of muscle force and summation of the square of muscle stress using rnonlinear optimization. The solution of muscle force distribution based on the proposed approach predicted the same number of active muscles for the same given loading condition as that using either of the nonlinear 14 criterion. The accuracy of the results obtained by this new technique was further verified by its canpatibility with physiological considerations . From the mathetatical point of view, the formulation of this criterion has a major advantage as well. Since the entire system of constraints and objective functions consists of linear terms of unknown variables , the well-established linear programming algorithm, the simplex method, can be used to obtain the solution efficiently. In contrast, the algorithm obtained by rnonlinear optimization is usually more involved and less efficient than linear programming. In addition, convergence of the solution to a global minimum is not always guaranteed. The criteria of minimizing the upper bound of muscle stress and of maximizing the activity endurance time are the least disputed criteria in the bionechanical problem. In other words , these two criteria seem to represent an optimal characteristic of various activities performed by the human musculoskeletal system. For this reason, both of these criteria will be developed for a nonsymmetric weight holding task. ANALYTICAL METHODS AND RESULTS Qatimization can be used to determine the muscle and joint loads on any part of the body, but it will be applied here to determine the loads on the lumbar spine . loads on the lumbar spine should be kept as light as possible since it is suspected that heavy loads rave a role in both causing back pain and aggravating pre-existing lumbar spine conditions . Since heavy spinal loads are to be avoided, it is necessary to know under what circumtances they arise. By determining the muscle and joint forces that occur during various physical activities , these circumtances can be defined. Tb conpute the loads on the lumbar spine created by a quasi—static physical activity, the body is first divided into upper and lower parts by an imaginary transverse cutting plane . This cutting plane is passed through the level of the lumbar spine at which the loads are to be determined. In this case, it is at the L3 vertebra. The upper part is considered as a free body subject to the laws of Newtonian mechanics, and a two—stage calculation procedure is carried out (Figures 1 and 2). In the first stage, the external force is considered as an equivalent force and mment acting at the origin; in the second, the internal forces are estimated to place the system in equilibrium. The equivalent external system consists of six conponents: three force corponents and three monent corponents . To calculate the external equivalent system, a coordinate system must be established. The origin is placed at the center of the L3 15 16 vertebral body and it is assumed that the equivalent system acts at that point. Coordinate directions are selected as follows: the x axis is positive to the right, the y axis is positive anteriorly, and the z axis is positive superiorly. The x arnd y axes lie in the transverse cutting planeandthezaxisisperpendiculartothecuttingplane,as illustrated in Figures 1 and 2. The body segment weights and the mass-center locations were obtained from Clauser et a1. and Eycleshymer and Schoemaker respectively, as referenced by Schultz and Andersson (3,8,20). The coordinates of the mass center locations are specified as (xi, yi, 2i) , where i represents the specific body part. The action of a force on a body can be separated into two effects, exterrnal and internal. The weight of a body, an external effect, is the gravitational force distributed over its voluie which may be taken as a concentrated force acting through the mass center location. Referring to Figure 1, the following equations were written for the external force and monent corponents of the upper body segment: (1) Fx = 0 (2) Fy = O (3) Fz=-(Q+wh+wl+wr+wt) (4) Mx = -(qu + tht + yrwr + 371Wl + thh) (5) My = -(lel - err) (6) M2 = 0 where: Q = weight of object held in right hand weight of the head and upper neck 33 =3 II = weight of the left upper limb 17 r- -w--l-..---l-:--+.,./ ll :4...) N\\ G Wf/_0:/ \\ External System Figure 1. 18 W = weight of the right upper limb W = weight of the trunk above the cutting plane F = equivalent external force carponent in the x direction at the origin F = equivalent external force component in the y direction y at the origin F = equivalent external force canponent in the z direction at the origin M = equivalent external marent component in the x direction at the origin M = equivalent external motent carpooent in the y direction y at the origin M = equivalent external moment component in the z direction at the origin If the nurerical values of Table 1 are assured, then the three nonzero corponents of the net reaction are : Fz = -391 N (7) Mx = —3130 Non M = -l60 Ncm Y The external system must be balanced by the internal force between thelowerbodysegment andtheupperbodysegment, inordertokeepthe upper body in equilibrium. However, the external force system is not affected by the material properties of the body tissues . Anatomical variables affect the external gravitational forces only in so far as they influence mass distributions and mutant arms. ThetrunkmodelinFigureannbeusedtoidentifythe internal forces . Since this model incorpora es ten muscle equivalents , which represent most of the major muscle groups spanning the lumbar region , it can be used in a variety of physical activities. l9 Figure 2. Equivalent Internal System 20 The three spiral segment loads, C, Sa and Sr are assured to act atthe coordinate system origin. The muscle orientation angles are defined as: B , the angle between the internal obliques and the z axis; 6, theanglebetweentheexternalobliquesandthezaxis;and¥, the angle between the latissimus dorsi and the z axis. TABLE 1. Body Segment Weights and Mass-Center locations Weight (N) Coordinate locations (cm) Q = 40 xq = 0 yq = 45 Wh = 35 xh = O yh = 8 W1 = 32 x1 = 20 y1 = 1 Wr = 32 XI. = 15 yr = 24 wt=252 xt=0 yt=1 Solving the equilibrium equations written from Figure 2 for the equivalent external forces and monents generates the following equations: (8) -Fx = -Sr 4» sin Y * (Ll-LI.) (9) -Fy=-Sa-sin8*(Il+Ir)+sin5*(Xl+Xr) (10) —Fz=P+C-El-Er-cos 8*(Il+lr)-cosY*(I-1+Lr) -Rl-Rr-cos<5*(Xl+)%) (ll) -Mx=ye*(E1+Er)-cos B*yo*(Il+Ir)+cosY *yl* (Lima-yrwawn-oosé *y.*s>+ypp (12) -M =-x “(E1 -Er)-cosi3 *xo*(Il -Ir)-cosY 1"xl y e *(Ll-Lr)-xr*(R1Ms)-wsfl_5*x*(X-lgc) (l3) -Mz=-sin8 *xo* (Ir -Il)—sinY *y1*(Lr-Ll)- sind *xo *(Xl Xr-) 21 left erectcr equivalent force = right erectcr equivalent force a .‘i am at II I = left internal oblique force H Ir = right internal oblique force L1 = left latissimus dorsi equivalent force Lr = right latissimus dorsi equivalent force R1 = left rectus abdominis force Pr = right rectus abdominis force X1 = left external oblique force Xr = right external oblique force P = intra—abdominal pressure force C = corpressive spinal force Sr = right-lateral spinal shear Sa = anterior spinal shear The intra-abdominal pressure resultant can be determined from experimental measuremnts . The maximum calculated intra-abdcminal pressure in stance is 25 mmHg as referenced from Gracovetsky, et a1. (10). With the abdominal cavity area, 273.4 cmz, this resultant force from intra—abdoninal pressure can be calculated to be 92.8 N (9). The trunk cross-sectional geometrical data given in Table 2 , are representative of a person who has a trunk width of 30 cm and a trunk depth of 20 cm at the L3 vertebral level (20). Substituting the values in Table 2 and the values for the intra-abdominal pressure and the equivalent external system into equations (8) through (13) yields the following simplifications: (l4) 0 = —Sr + 0.707 * (Ll - Lr) (15) (16) (17) (18) (19) The 22 0 = —8a - 0.707 * (I1 + Ir) + 0.707 * (X1 + Xr) 298.2 = C - E1 - Er - 0.707 * (Il + Ir) - 0.707 * (Ll + Lr) — R1 - Rr — 0.707 * (x1 + xr) 2684.57 = 4.4 * (ii:1 + Er) — 2.69 * (11 + Ir) + 3.96 * (Ll + Lr) - 10.8 * (R1 + Rr) - 2.69 * (X1 + X1.) 160 = — 5.4 * (El - Er) - 9.54 * (I1 - Ir) - 4.45 * (L1 - Lr) - 3.6 * (Rl - Rr) - 9.54 * (Xl - XI.) 0 = 9.54 * (I1 - Ir) + 3.96 * (L1 - Lr) - 9.54 * (X1 - Xr). thirteen internal forces are unknown. Since only six equations are available to find them, it is obvious that the use of this model leads to a statically indeterminate problem. The examples following will illustrate two different optimization methods for solving this problem. TABLE 2 . Cross-Sectional Gearetric Data Coordinate locations (cm) Angles (degrees) xr = 3.6 yr = 10.8 B = 45 x = 0.0 = 4.8 <5 =45 p yp x0 = 13.5 yo = 3.8 y = 45 Xe = 5.4 ye - 4.4 x:L = 6.3 Yl = 5.6 The major question that arises when optimization is used for solution, diversity different is the choice of the objective function. Considering the of musculoskeletal function, it is likely that distinctly criteria for muscle selection may be utilized for different activities . For the physical activity previously discussed, the following optimization problem will be developed: first , minimization 23 of the upper bound of muscle stress and second, minimization of the summation of muscle stress to the nith power, which is based on maximum endurance of musculoskeletal function. Previously, most optimization procedures have been more or less based on consideration of overall efforts of the systenn. The criterion of minimizing the upper bounnd of muscle stress was developed to take individual muscle effort into consideration. This idea stem from the energy storage and transport viewpoint that each muscle bundle has its own storage and blood supply. This technique predicts a solution with a more even distribution of muscle stress among all synergistic muscles , thereby favoring the largest endurance for the task (1) . With this particular criterion, the core of the problem formulation lies within defining the constraints, as opposed to explicitly defining the objective function. The most important of these constraints being those that define the donain where muscle stress Si is greater than or equal to any other muscle stress Sj‘ Ornce this domain is defined, the upper bound of muscle stress Si is minimized. In order to define this space, nine inequality constraints were developed for each individual muscle , Mi . Mathematically these constraints are represented by: (20) Si 3 Sj The muscle cross-sectional areas, given in Table 3, were used to calculate the respective muscle stresses (9) . Additional constraints incorporated into this problem here the equilibrium equations (16) through (19). These equations were obviously formulated as the four equality constraints. Equations (14) and (15) 24 TABLE 3 . Transverse Section Through the Abdonen at L3 Area (omz) Muscle . Right Left Erector Equivalent 20.202 20.121 latissimus Dorsi 2.129 2.258 External Oblique 7.032 7.610 Internal Oblique 9.615 10.582 Rectus Abdominis 3.549 4.323 were used to find Sa and S r after the optimization solution was obtained. This changes the optimization problem to one of eleven unknowns . Also included in this problem were the ten inequality constraints that the muscle forces must be greater than or equal to zero. This arises from the fact that muscle contractions always produce tensile forces . In the simplex method, these constraints are automatically assured. Finally , the problem statemnt for minimizing the upper bound of muscles stress is: (21) minimize 0‘) (D P- M: ,... IV subject to |V S. 3 0 equations (16) through (19) Since n-dimensional space is impossible to envision, the solution space for this type of problem will be illustrated in three-dimensional muscle space . Each axis represents the force in one of the three 25 muscles, Mi where i = l, 2, 3. For simplicity, the respective areas, Ai' will all be unity. The donain formed by the inequalities: (22) S S > 3‘1 (23) S S > 3‘2 represents the area where 83 is greater than or equal to S1 annd 52. Both inequalities, (22) and (23), form a 45 degree plane between the respective variables , Mi . The problem is limited to the positive quadrant due to the constraints that the variables must be greater than or equal to zero. These constraints are represented by the expression: (24) M110, i=1, 2,3 The area above the 45 degree planes and bounded by the perpendicular planes is the donain where 83 is the greatest. This domain is illustrated in Figure 3. It is important to note that if the areas were notunityandequal, (A1=A2=A3=1), theplaneswouldnotbeat45 degree angles. In addition, two equality constraints , Figure 4 , were incorporated into this problem. These constraints are represented by the equations : (25)3.0*M1+M2+1.5*M3=9 (26) M1+0.8*M2+2.0*M3=8 The line of intersection formed by these two planes defines the coordinate values that satisfy both constraints . This limits the optimization solution to the values on this line. 26 3595:00 3:269: 93 3 ooEtou 5280 .m 959". .1!- di- l Cin- Illi- .- -u- i- 27 Semi 2.85.80 Ego-sow .e 2:9“. \I 28 Containing all of the constraints together defines the conplete solution space. The only possible solution space lies along the line of intersection formed by the equality constraints that is contained in the detain where $3 is the greatest. This space is illustrated in Figure 5. Note that the line of intersection formed by the equality constraints intersects the 45 degree plane between M2 and M3 . This point of intersection is the solution to minimizing the upper bound of M3 muscle stress . Furthermore , imagine the domains defining S1 and S2 as the greatest superimposed on Figure 5 . This involves a 45 degree planne between the M1 and M2 axes, parallel to the M3 axis. It is easy to visualize that minimizing the upper bound of M2 muscle stress yields the same optimum solution as that of M3. However, since the line of intersection formed by the equality constraints does not intersect the detain where S1 is the greatest, no solution exists when minimizing the upper bound of M1 muscle stress. Table 4 lists the nunerical results obtained when searching each domain. Table 4 . Three-Dimensional Optinmmm Solutions Donain Optimum Solution M1 ._ ..... .— M2 0.881 2. 542 2.542 M3 0.881 2.542 2.542 Referring back to the weight lifting task, all ten muscular donains were searched using the simplex method. Seven of the ten detains searched yielded a nuterical solution . However , the optimum 29 252650 9: >9 ooczoo 8me 523.8 .m Boot 30 solution was found in only two of these seven detains, the right equivalent erectcr and the right latissimus dorsi . Note that these two domains generated the identical solution. Table 5 lists the load and stress values that the muscles were predicted to carry in the optimal solution. The stress values of the remaining five domains are listed in Table 6. The three domains that did not have a numerical solution were El, Il annd L1' in which the solution did not satisfy the constraints. In corparison, Schultz and Anndersson also solved this nonsymetric weight holding problem of ten muscular unknowns using linear programming (20). They selected the cost function to minimize the conpression on the L3 lumbar vertebra. The constraints consisted of the equilibrium equations (16) through (19) , the ten requiremnts that the muscle tensions cannot be negative and the ten requiremnts that the muscle contraction intensities cannot exceed the reasonable level of 100 Iii/om2 . The equations for x and y force equilibrium, (14) and (15), were used to calculate Sa and Sr after the solution was obtained. This problem is formulated as: (27) minimize C subject to 0 .5. Mi 5. 100 N/cmm2 equations (16) through (19) The solution to this optimization problem is listed in Table 7. In constructing the optimization criterion for minimizing the summation of muscle stress to the nith power, the importance of selecting a criterion based on sound physiological bases was emphasized. It is assured, that in an approximate manner the muscle force-endurance relationship is a basic property of muscle tissue (4) . The maximum 31 TABLE 5. Optimum load and Stress Data from the Criterion of Minimizing the Upper Bounnd of Muscle Stress Elerent load (N) Stress (N/cmz) E1 282.013 14.016 Er 283.153 14.016 Il 0.000 0.000 Ir 8.859 0.921 L1 31.646 14.016 Li 29.840 14.016 R1 0.000 0.000 R.r 0.000 0.000 X.l 0.000 0.000 Xi 8.110 1.153 C 918.835 -- Sa 0.530 —-- S 1.277 -- 32 Table 6 . Stress Data from the Criterion of Minnimizing the Upper Bound of Muscle Stress Space Searched / Stress (N/cmz) Elenent Ir Rl RY X1 Xr El 18 . 746 18 . 999 17 . 262 16 . 000 17 . 119 Er 18 . 746 18 . 999 17 . 262 19 . 372 17 . 119 I1 16.182 0.000 0.245 0.960 0.000 Ir 18.746 2.551 0.000 0.000 0.929 L1 18 . 745 18 . 999 17. 262 19. 372 17. 119 Lr l8 . 746 18 . 999 17 . 262 19 . 371 17 . 119 R1 0.000 18.999 0.000 0.000 0.000 Rr 0.000 0.000 17.262 0.000 0.000 X1 0 . 000 0 . 000 0 . 461 19 . 372 14 . 762 XI. 1. 140 3 . 343 0. 000 19 . 372 17. 119 33 Table 7. Optinmmm load and Stress Data from the Criterion of Minimizing the Oonpression on the L3 Lumbar Vertebra Elenent load (N) Stress (Womz) E1 98.640 4.902 Er 128.270 6.349 Il 0.000 0.000 Ir 0.000 0.000 L1 212.900 94.293 Li 212.900 99.999 R1 0.000 0.000 R.r 0.000 0.000 X1 0.000 0.000 Xi 0.000 0.000 C 826.150 —- Sa 0.000 -- Sr 0.000 -- 34 endurance of a muscle contraction is thus inversely related to the magnitude of the average stress within the muscle tissue. The determination of muscle force during body function may then be formulated as a nonlinear optimization problem with an objective to minimize the sumation of muscle stress to the nith power. The constant ni is related to fiber type and fiber orientation or more specifically to the percentage of slow twitch fibers for the respective muscle, Mi. This criterion is valid only when applied to an endurance activity. An endurance type of activity involves sustained or repetitive muscular contractions . The activity of holding a relatively stall weight in front of the body can be considered an endurance activity since it involves sustained muscular contractions. The muscle force-endurance relationship was proposed to be of the form: (28) lnT. =-n. *1nM. +c. 1 1 1 1 where: Ti = maximum time of contraction for the ith muscle Mi = muscular contractile force for the ith muscle n. = constant relating endurance time with muscle force for 1 the ith muscle ci = endurance time for a muscle force level of 1% maximum muscle force for the ith muscle The parameters ni and ci are dependent on the percentage of slow- twitch fibers, 21' These parameters can be represented by the following equations: (29) nn‘,L = 0.25 + 0.036 * Zi (30) c. = 3.48 + 0.169 * z. 1 1 35 The percentage of slow twitch fibers for the relative muscles , referenced from Johnson et al., are listed in Table 8 (13). ME 8 . Slow Twitch Fiber Parameters Muscle Zi ni Ci Erector Equivalent 58.4 2.4 13.3 latissimus Dorsi 50.5 2.1 12.0 Internal Obliques 76.4 3.0 16.4' External Obliques 76.4 3.0 16.4 Rectus Abdominis 46.1 1.9 11.3 The values for both the internal and external obliques are the average values estimated from experimental studies since a more accurate value was not obtainable (4) . The constraints involved in this problem consist of four equality constraints and eleven inequality constraints . The equality constraints were the equilibrium equations (16) through (19). As before, the equations (14) and (15) were used to back solve for Sa and Sr after the optimization solution was obtained . The inequality constraints designate the reasonable range each muscle force can be found in. In other words, these constraints fornm both an upper and lower bound for muscle force. The timer bound is determined by assuming that the muscle contraction intensities do no exceed the reasonable level of 100 N/cnm2 . Hence, the determination of muscle force during body function is formulated as a nonlinear optimization problem with an objective to minimize the summation of muscle stress to the ni power. The problem statetent is sumarized as: 36 m (31) minimize Z (5.) 1'1i . l 1=l subject to o 5 si 3 100 N/cm2 equations (16) through (19) Predicting muscle forces to minimize this objective function coincides with maximizing endurance for the defined activity. The load and endurance data obtained from this optimization problem are listed in Table 9 . Figures (6) and (7) are referred to as two variable design spaces, where the design variables correspond to the coordinate axes . In general, a design space will be 11 - dimensional, where n is the number of design variables . The two variable design space is used to help visualize the concepts of optimization techniques . Figures 6 and 7 illustrate the objective function contours (dashed lines) as a function of the erectcr equivalents, El and E r’ and the latissimus dorsi, L1 and Lr , respectively. The solid lines on these figures represent the corresponding numbered constraints . In general , nonlinear optimization convergence on a global minimmm is not assured. However , the present problem due to the continuous convex character of the objective function and the linear constraints , falls into the category of convex programming. This convexity assures that the only minimum is a global minimum (25). In corparison, Crowinshield and Brand used a similar optimization criterion: 3 1/3 111 (32) 2 [(51) ] i=1 37 TABLE 9. Optimum.Load and Stress Data from.the Endurance Criterion Elemnt load (N) Stress (N/cmz) E1 282.700 14.050 Er 312.300 15.459 I1 0.000 0.000 Ir 0.000 0.000 L1 8.377 3.709 Li 8.377 3.934 R.l 0.000 0.000 R.r 0.000 0.000 X1 0.000 0.000 Xi 0.000 0.000 C 905.100 -- Sa 0.000 -—- Sr 0.000 -- 38 v®+m_m_.® vm+u@m_.® £122 .s $132 .9 . momow Em_m>_:om .90th .m mSoE x: ... m N: u m Nu n m E u v .58 u _ _m .smm .Em .8m .mmm .mmm I / i. / r . . .u m. II II III U r I mII /.I I/ I/ /I m I I I II II I L W // x/ z/ z/ 1“ M I/ III III III m .i/ / /u / / u m II II II I II [1 v / I I II in“ ..I I / / / 14 W II I/ II I/ u I I I 1 .II /II /I /In /I M no I/ I II II I11 n I / / / l1. . , ,1 , ,la 1 1 I/ I I, 5 1 X x, / K .1 l / I/ / I . mr n I/ I /I . III “ sods asses games. semis; 39 vmlmm__.® veimm__.® vmlmo__.® volwo__.® 8QO 6.00 m:E_mw:m._ .N. 329.... m x:. »: u v Hmou u _ _4 ®®.m ®®.m m®.m ®®.m mm m.’ 1 a z . 1 I , I z x/ U P z / I1. I z // x // 1 n / I // I cm I o’ w // // II III! m 7; x / I "I I 1/ 1/ I I... w l / II I/ u .n / I; . I In, L w I ’ ” l’n’" U .II II / /’ allu "I / I I, /’I' I... n /I I ll Illil m fill / ’0’ ”’ Ill" 1w. II / II IIII # mu. I I II III II!!! (I! # VII II II III IA h I I II I, v ¥hh h’b >>>>>> 4K L-th’.+erh-..~ho vs 15.8131; see .1 s: Emu __.® 40 The cube root of the objective function was taken for two practical reasons: first, so the objective function will have muscle stress units and second, to reduce the magnitude of the objective function thereby avoiding nurerical problem . The average experimental value of F3 is chosen for n. This method was denonstrated at the elbow during isoretric contraction and in the lower extremity during loconotion (4) . When this method was applied to the weight lifting task, only a nominal change in the solution occurred. Table 10 lists the load values withn=3, withandwithoutthe takingcubedrootandtakingthecubed root with n varied according to the percentage of slow twitch fibers . 41 Table 10. Load Values of Nonlinear Criteria Load (N) Normalized Not Normalized Normalized Element n=3 n=3 n=variab1e E1 281.200 281.200 282.700 Er 310.800 310.800 312.300 I1 0.000 0.000 0.000 Ir 0.000 0.000 0.000 L1 10.060 10.090 8.375 Lt 10.060 10.110 8.375 R.l 0.000 0.000 0.000 Rr 0.000 0.000 0.000 X1 0.000 0.000 0.000 xr 0.000 0.000 0.000 C 904.400 904.400 905.100 Sa 0.000 0.000 0.000 Sr 0.000 0.014 0.000 CONCLUSION The method of optimization is applied to corplex decision or redundant problem , in which a unique solution cannot readily be determined. When formulating an optimization problem, the performance criterion must represent an optimal characteristic of the system. Although electromyographic results were not available to confirm the validity of the criteria presented in this research, the optimization solutions are discussed mathematically. The linear optimization problem of minimizing the upper bound of muscle stress yielded seven numerical solutions . TWO of these seven muscular donains shared the same solution, which was also the optimal solution. The solution did not satisfy the constraints in the retaining three donains . The constraint violations occurred when searching the left internal oblique , the left erectcr equivalent and the left latissimns dorsi detains. The conflict that developed is that the equality constraints defined a solution space that was not cannon to the solution space or donain formed by the inequality constraints . This noncomronality did not allow the solution to satisfy the constraints . The five muscle domains that yielded a nunerical solution, but not the optimal solution, selected both different muscle force magnitudes and different active muscles. However, in each of the seven domains, all but two of the calculated stress values have the same stress as that of the muscular domain searched. The optimal solution, muscle spaces Er 42 43 annd Lr, has a maximum stress of 14.016 N/om2 conpared to the largest stress generated of 19.372 N/cnm2 in muscle space X1. For the nonlinear problem, only four active muscles were selected. Nonlinear cost functions are assured to select more synergistic muscles . Here, the linear method of minimizing the upper bound of muscle stress predicted ‘ a more even distribution of muscle stress among the synergistic muscles and a greater distribution of muscle activity. However, it is interesting to note that the stress values for both the minimm fatigue arnd minimum upper bournd of muscle stress criteria were in the same range. The active muscles selected for the minimum fatigue criterion were the same active muscles selected by the linear criterion of minimizing the conpression on the L3 vertebra . In conparing the dominant muscles , the erectcr equivalents were selected by the minimm fatigue criterion, while the latissimus dorsi were chosen by the criterion of minimizing the spinal corpression. The method of minimizing the spinal conpression drove the latissimus dorsi to its upper bound. When the upper bound was renoved, the latissimus dorsi. carried 96% of the muscular load with only a 128 N load decrease carried by the spine conpared to the other two cost functions . This response reveals that the solution had a greater dependency on the upper bound than on the cost function itself. Neither the criterion of minimizing the upper bound of muscle stress nor the endurance criterion yielded muscle stresses near the upper bound. The minimum fatigue criterion was modified four times. Only a negligible difference in force magnitude was noticed when the cubed root ofthecostfunctionswastakenforbothcasesofn=3andnivalues. Therefore, taking the cubed root was unnecessary in this problem. Only 44 a minor difference in force magnitude existed when the values of ni according to the percentage of slow twitch fibers were used conpared to the experimental average value of n=3 . For the activity of holding a 40 Nweight, this responsecanbeexpectedsince there isrotalarge difference between the ni parameters of the erectcr equivalents and the latissimus dorsi . The endurance criterion should be investigated further by increasing the load held in the right hannd. Increasing the load would involve more muscles , including the antagonistic rectus abdominis muscles , thereby involving a full range of ni parameters . Figure 6 illustrates that constraints 2 and 3, equations (16) and (17) respectively , are redundant in the vacinity of the erectcr space solution. Also, constraint 5, equation (19), does not even exist in the limited erectcr space shown. All four equality constraints are present in the latissimus dorsi solution space illustrated by Figure 7 . Constraints 2 and 3 are again found redundant in this space. In addition, constraints 4 and 5, equations (18) and (19) respectively, are also found redundant in the latissimus dorsi space shown. In both of the muscle spaces illustrated, the optimal solution is found at the intersection of the constraints . Knowledge of the magnitudes annd directions of muscle forces is necessary in the design of preventative and rehabilitative programs . In such applications , the solution to the indeterminate bionechanical problem can be obtained by formulating an objective function and utilizing an optimization technique. The criterion chosen to formnulate an optimization problem must represent an optimal characteristic if the problem is to yield an accurate solution. There is a great need to 45 experimentally validate the predictions presented and to continue formulating optimization problem based on physiological reasons . APPENDIX A APPENDIX A SIMPLEX m The original fornm of the simplex algorithm was developed by George B. Dantzig in 1947 annd was formally published in 1951. Many variations of the original technique have been developed since, but the original simplex algorithm is still the best procedure for the solution of the general linear programming problem when manual corputations are used. Certain other revised simplex algorithnm are conputationally advantageous when the solution is calculated with a digital conputer . The following derivation of the simplex method is referenced from David G. Luenberger . As previously stated, a linear programming problem is a matheratical program in which the objective function is linear in the unknowns and the constraints consist of linear inequalities and/or linear equalities. The exact form of these constraints may vary from one problem to another but any linear progranm can be transformed into the following standard form: . . . ++ mumnmze CX (A1) subjectto AI=S £30 mxnmatrix where : n — dimensional column vector U‘t ><+ 3’: ll m - dimensional column vector 46 47 E=n—dimensionalrowvector Various other forms of linear programs can be converted to the standard form by one or more of the following techniques: slack variables , surplus variables , free variables arnd by eliminating a variable unconstrained in sign. It is also important to note that all inequality constraints must be in the form of less than inequality constraints. The purpose of this is for the geomtric advantage of having the gradients of the cost function and the constraints point away from the optimal solution. A basic solution is obtained by setting all the independent variables equal to zero and solving for the dependent variables . This matrix is said to be in canonical form. Since optimal solutions are always basic solutions , it is important to understand the concept of basic solutions and the fundamental theorem of linear programming. Consider the system of equalities , (A2) SEES where: A=mxnmatrix x=n-dimensionalvector b=m—dimensionalvector From the n columns of A, select a set of m linearly independent columns. Such a set exists if the rannk of A is m. For notational simplicity, assume that the first m columns of A were selected and denote the m x m matrix determined by these columns by B. This matrix is illustrated in equations (A3) . 48 H o e o O 31am al,m+2 ° ' ' al,n a2,m+l a2,mn+2 ° ° ° 32,11 b20 0 0 . . . 0 . . . . . . . (A3) . . . . . . . . . . 0 0 1 b am,mn+1 am,mH-2 ’ ' ‘ fimm no The matrix B is referred to as a basis since it consists of m linearly independent columns that can be regarded as a basis for the space E“. The matrix B is then nonsingular and a unique solution may be obtained from the equation: ~4- (A4) BxB = where : mxmmatrix nm - dimensional vector U‘i‘ Uri (H? (Ti ii In - dimensional vector The vector {B is conposed of the first nm conponents of 3}, the basic variables, and the remaining components of n? are equal to zero. That is, 32 = (2:3, 0) . In general, equations (A2) may not have any basic solutions. By making certain elenentary assunptions regarding the structure of the matrix A, this trivial problem may be avoided. First, assure that n > m, that is, the number of variables xj exceeds the number of equality constraints. Seconnd, assume that the rows of A are linearly inndependent , corresponding to linear independence of the m equations . A linear dependency among the rows of A would lead either to contradictory constraints and hence no solutions to (A2), or to a redundancy that 49 could be eliminated. Now, with the assumption that 31. has rank :11, there exists at least one basic solution to (A2) . Another point worth cementing on is that of a degenerate solution. If one or more of the basic variables in a basic solution has value zero, that solution is said to be a degenerate basic solution. Note that in a nondegenerate basic solution , the basic variables , and hence the basis 1;, can be immediately identified frem the positive camponents of the solution. Since the zero—valued basic and nonbasic variables can be interchanged, ambiguity is associated with a degenerate basic solution . So far in the discussion of basic solutions, no reference has been made to the positivity constraints on the variables . Similar definitions apply when these constraints are also considered . Thus , consider the system of contraints: =3, 9:: (A5) 0 Xi‘ which represents the constraints of a linear program in standard form. If a vector 32 satisfies equations (16) it is said to be feasible for these constraints . A feasible solution to the constraints (A5) that is also basic is said to be a basic feasible solution; if this solution is also a degenerate basic solution , it is called a degenerate basic feasible solution. The primary importance of basic feasible solutions in solving linear programming problems is represented through the fundamental theorem of linear programming. The theorem itself shows that it is necessary only to consider basic feasible solutions when seeking an 50 optimal solution to a linear program because the optimal value is always achieved at such a solution. The gemetric interpretation of the simplex method is straight forward. The constraints form a polyhedron (multidimensional case) which is either convex from or to the origin, according to whether the "greater than" or the "less than" inequality condition is imposed. The polyhedron defines the feasible solution space . There is a special category of the infinite feasible solutions that is of a finite number. These solutions , called basic feasible solutions , are situated gearetrically at the vertices of the polyhedron. The number of basic solutions is determined by the number of variables , n, and the number of constraints , m, according to the cambinatorial formulas: (A6) 0}; = n1/m£(n - m)! The z—constant equations (evaluated cost functions for each basic solution) form a family of straight lines or hyperplanes . The extremmm solution is given by the remotest or the nearest intersecting points between the z—hyperplane and the polyhedron (24) . The first step of the simplex method, referred to as phase I, simply locates a vertex of the feasible set, or establishes that the set is erpty. Assuming that a vertex, or basic solution, has been found the procedure continues with phase II. This phase is the heart of the method, which searches from vertex to vertex along the edges (intersections of the planes) of the feasible set . At a typical vertex there are n edges to choose frem, sate leading away frum the optimal solution and others leading gradually toward it. Since linear programming forces the solution to stay in the feasible set , an edge 51 that is guaranteed to decrease (increase) the cost is chosen. Eventually the optimal solution is reached. Another important point is the convexity of the canonical system forms. During the various linear transformations occurring in linear programming, the convexity of the polyhedron does not change . The properties concerning the vertices therefore retain the same; they guarantee the necessity and sufficiency of the final extremal solution , if it exists . The simplex method proceeds from one basic feasible solution, that is one extrene point, of the constraint set of a problem in standard form to another, in such a way as to continually decrease the value of the objective function until a minimum is reached. This is accerplished by simple multiplications and additions referred to as pivoting. A pivot operation consists of m elerentary operations which replace a standard system by an equivalent canonical system. To initiate the use of the simplex method, the problem of finding an initial basic feasible solution arises . Except for the cases where the linear constraints are inequalities in which slack and/or surplus variables are used to transform the problem into one of standard form, it is not always possible to easily find an initial basic feasible solution. Therefore, it is necessary to develop a means for determining one so that the simplex method can be initiated. Interestingly, an auxiliary linear program and corresponding amlication of the simplex method can be used to determine the required initial solution . Another important point is that many linear programs arising from practical situations involve variables that are subject to both lover 52 and umer bounds. The simplex method is easily modified to accommdate the upper bound. One final cxnment pertains to the revised simplex. method. Extensive field experience has indicated that the simplex :method converges to an cptimum.solution in about m or 1.5hm pivot operations. Ifmismnuch smallerthann, that is, ifthematrixAhasfar fewerrcws than columns, pivots will occur in only a small fraction of the columns during the course of optimization . Since the other columns are not explicitly used, the work expended in calculating the elements in these columns after each pivot is wasted effort. The revised simplex method is a scheme for ordering the computations required of the simplex method so that unnecessary calculations are avoided. APPENDIX B APPENDIX B GENERALIZED REDUCED GRADIENI‘ MED-10D From a corputational viewpoint, the simplex method is related to the generalized reduced gradient method of nonlinear programming in that the problem variables are partitioned into basic and nonbasic groups . The following description of the generalized reduced gradient method was referenced from Garret N. Vanderplaats (25). However, before beginning this derivation, it is important to mention sore basic properties. Recalling from basic calculus that in order for a function of one variable to have a minimum, its second derivative must be positive. In the general n-dimensional case , this translates into the requirenent that the matrix of second partial derivatives of the objective with respect to the design variables must be positive definite. This matrix is called the Hessian matrix. Positive definiteness means that this matrix has all positive eigenvalues . If the Hessian matrix is positive definite at a given x, this insures that an extremmm of the design is at least a relative minimum. This vector, 32, is special in the sense that it satisfies the first order conditions. If the Hessian matrix is positive definite for all possible values of the design variables, 21', then a relative mfinimum of thedesignisguaranteedtobeaglobalminimmm. Inthis case, the objective function is said to be convex. When the objective function is convex and the constraints form a convex solution space the necessary 53 54 Kuhn-Tucker conditions are also sufficient to guarantee that if an optimal solution is obtained, it is the global optimum. The general nonlinear constrained optimization problem staterent can be written matheratically as : minimize FGE) (Bl) subject to gj(§) : 0 j = l,m hkfi) = 0, k = l, L where: FD?) objective function X‘l‘ ll vector of design variables g.(x) = inequality constraints equality constraints 7‘: 35. u lower bound on xi Pea put. = upper bound on xi Notice that the bounds on the variables are considered as side constraints . These side constraints could be included in the inequality constraint set , but are usually treated separately since they define the search region. Since the generalized reduced gradient method only solves equality-constrained problem , the problem statetent (Bl) must be modified by adding slack variables , x. , to the inequality constraints 3m to yield the general form: minimize FGE) (32) subject to ngE) + xjm = 0, j = l,m hkb?) = 0 k = l,L L u xi