# Manual Systems of Linear Inequalities (Little Mathematics Library)

Conic sections would be studied and used for thousands of years by Greek, and later Islamic and European, mathematicians.

Solving linear inequalities

In particular Apollonius of Perga 's famous Conics deals with conic sections, among other topics. Chapter eight deals with solving determinate and indeterminate simultaneous linear equations using positive and negative numbers, with one problem dealing with solving four equations in five unknowns. He used fan fa , or Horner's method, to solve equations of degree as high as six, although he did not describe his method of solving equations. Shu-shu chiu-chang , or Mathematical Treatise in Nine Sections , was written by the wealthy governor and minister Ch'in Chiu-shao c.

The earliest known magic squares appeared in China. The four elements , called heaven, earth, man and matter, represented the four unknown quantities in his algebraic equations. The author uses the method of fan fa , today called Horner's method , to solve these equations. The Precious Mirror opens with a diagram of the arithmetic triangle Pascal's triangle using a round zero symbol, but Chu Shih-chieh denies credit for it. A similar triangle appears in Yang Hui's work, but without the zero symbol. There are many summation series equations given without proof in the Precious mirror.

A few of the summation series are: . Diophantus was a Hellenistic mathematician who lived c. He is known for having written Arithmetica , a treatise that was originally thirteen books but of which only the first six have survived. It is usually rather difficult to tell whether a given Diophantine equation is solvable. There is no evidence that suggests Diophantus even realized that there could be two solutions to a quadratic equation. He also considered simultaneous quadratic equations. In Arithmetica , Diophantus is the first to use symbols for unknown numbers as well as abbreviations for powers of numbers, relationships, and operations;  thus he used what is now known as syncopated algebra.

The main difference between Diophantine syncopated algebra and modern algebraic notation is that the former lacked special symbols for operations, relations, and exponentials. Note that the coefficients come after the variables and that addition is represented by the juxtaposition of terms. A literal symbol-for-symbol translation of Diophantus's syncopated equation into a modern symbolic equation would be the following: . Arithmetica is a collection of some solved problems with specific numbers and there is no postulational development nor is a general method explicitly explained, although generality of method may have been intended and there is no attempt to find all of the solutions to the equations.

The Indian mathematicians were active in studying about number systems. The earliest known Indian mathematical documents are dated to around the middle of the first millennium BC around the 6th century BC. The recurring themes in Indian mathematics are, among others, determinate and indeterminate linear and quadratic equations, simple mensuration, and Pythagorean triples. Aryabhata — was an Indian mathematician who authored Aryabhatiya. In it he gave the rules, . Brahmagupta fl. In his work Brahmagupta solves the general quadratic equation for both positive and negative roots.

Unlike Diophantus who only gave one solution to an indeterminate equation, Brahmagupta gave all integer solutions; but that Brahmagupta used some of the same examples as Diophantus has led some historians to consider the possibility of a Greek influence on Brahmagupta's work, or at least a common Babylonian source. Like the algebra of Diophantus, the algebra of Brahmagupta was syncopated. Addition was indicated by placing the numbers side by side, subtraction by placing a dot over the subtrahend, and division by placing the divisor below the dividend, similar to our notation but without the bar.

Multiplication, evolution, and unknown quantities were represented by abbreviations of appropriate terms. In Algebra, he gave the general solution of Pell's equation. Bhaskara uses the initial symbols of the names for colors as the symbols of unknown variables. So, for example, what we would write today as. The dots over the numbers indicate subtraction. The first century of the Islamic Arab Empire saw almost no scientific or mathematical achievements since the Arabs, with their newly conquered empire, had not yet gained any intellectual drive and research in other parts of the world had faded.

In the second half of the 8th century, Islam had a cultural awakening, and research in mathematics and the sciences increased. Greek works would be given to the Muslims by the Byzantine Empire in exchange for treaties, as the two empires held an uneasy peace. Arabic mathematicians established algebra as an independent discipline, and gave it the name "algebra" al-jabr.

They were the first to teach algebra in an elementary form and for its own sake. The first emphasizes Hindu influence, the second emphasizes Mesopotamian or Persian-Syriac influence and the third emphasizes Greek influence. Many scholars believe that it is the result of a combination of all three sources. Throughout their time in power, the Arabs used a fully rhetorical algebra, where often even the numbers were spelled out in words. The Arabs would eventually replace spelled out numbers e. Al-Khwarizmi, who died around CE, wrote more than half a dozen mathematical and astronomical works, some of which were based on the Indian Sindhind.

This is the operation which Al-Khwarizmi originally described as al-jabr. It no longer concerns a series of problems to be resolved, but an exposition which starts with primitive terms in which the combinations must give all possible prototypes for equations, which henceforward explicitly constitute the true object of study. On the other hand, the idea of an equation for its own sake appears from the beginning and, one could say, in a generic manner, insofar as it does not simply emerge in the course of solving a problem, but is specifically called on to define an infinite class of problems.

Al-Jabr is divided into six chapters, each of which deals with a different type of formula. Al-Khwarizmi most likely did not know of Diophantus's Arithmetica ,  which became known to the Arabs sometime before the 10th century. Diophantus would have written as . And al-Khwarizmi would have written as . Arabic mathematicians treated irrational numbers as algebraic objects.

His work on algebra and polynomials , gave the rules for arithmetic operations to manipulate polynomials. The historian of mathematics F. Stemming from this, Al-Karaji investigated binomial coefficients and Pascal's triangle. He used what would later be known as the " Ruffini - Horner method" to numerically approximate the root of a cubic equation.

He also developed the concepts of the maxima and minima of curves in order to solve cubic equations which may not have positive solutions. Some scholars, such as Roshdi Rashed, argue that Sharaf al-Din discovered the derivative of cubic polynomials and realized its significance, while other scholars connect his solution to the ideas of Euclid and Archimedes. Sharaf al-Din also developed the concept of a function.

To determine this, he finds a maximum value for the function. However, J. Lennart Berggrenn notes that he was mistaken, as decimal fractions were first used five centuries before him by the Baghdadi mathematician Abu'l-Hasan al-Uqlidisi as early as the 10th century. This same fractional notation appeared soon after in the work of Fibonacci in the 13th century. Just as the death of Hypatia signals the close of the Library of Alexandria as a mathematical center, so does the death of Boethius signal the end of mathematics in the Western Roman Empire.

Although there was some work being done at Athens , it came to a close when in the Byzantine emperor Justinian closed the pagan philosophical schools. The year is now taken to be the beginning of the medieval period. Scholars fled the West towards the more hospitable East, particularly towards Persia , where they found haven under King Chosroes and established what might be termed an "Athenian Academy in Exile".

During the Dark Ages, European mathematics was at its nadir with mathematical research consisting mainly of commentaries on ancient treatises; and most of this research was centered in the Byzantine Empire. The end of the medieval period is set as the fall of Constantinople to the Turks in The 12th century saw a flood of translations from Arabic into Latin and by the 13th century, European mathematics was beginning to rival the mathematics of other lands. In the 13th century, the solution of a cubic equation by Fibonacci is representative of the beginning of a revival in European algebra.

As the Islamic world was declining after the 15th century, the European world was ascending. And it is here that Algebra was further developed. Modern notation for arithmetic operations was introduced between the end of the 15th century and the beginning of the 16th century by Johannes Widmann and Michael Stifel. This created a new algebra consisting of computing with symbolic expressions as if they were numbers.

Another key event in the further development of algebra was the general algebraic solution of the cubic and quartic equations, developed in the midth century. The idea of a determinant was developed by Japanese mathematician Kowa Seki in the 17th century, followed by Gottfried Leibniz ten years later, for the purpose of solving systems of simultaneous linear equations using matrices.

Gabriel Cramer also did some work on matrices and determinants in the 18th century. Algebraic x is conventionally printed in italic type to distinguish it from the sign of multiplication. But the Swiss-American historian of mathematics Florian Cajori examined these and found all three lacking in concrete evidence; Cajori credited Descartes as the originator, and described his x , y , and z as "free from tradition[,] and their choice purely arbitrary. Nevertheless, the Hispano-Arabic hypothesis continues to have a presence in popular culture today.

The "sh" sound in Old Spanish was routinely spelled x. Evidently Lagarde was aware that Arab mathematicians, in the "rhetorical" stage of algebra's development, often used that word to represent the unknown quantity. Although the mathematical notion of function was implicit in trigonometric and logarithmic tables, which existed in his day, Gottfried Leibniz was the first, in and , to employ it explicitly, to denote any of several geometric concepts derived from a curve, such as abscissa , ordinate , tangent , chord , and the perpendicular.

Leibniz realized that the coefficients of a system of linear equations could be arranged into an array, now called a matrix , which can be manipulated to find the solution of the system, if any. This method was later called Gaussian elimination. Leibniz also discovered Boolean algebra and symbolic logic , also relevant to algebra.

The ability to do algebra is a skill cultivated in mathematics education. As explained by Andrew Warwick, Cambridge University students in the early 19th century practiced "mixed mathematics",  doing exercises based on physical variables such as space, time, and weight. Over time the association of variables with physical quantities faded away as mathematical technique grew.

A linear programming problem is a mathematical programming problem in which the function f is linear and the set S is described using linear inequalities or equations. A farmer has 10 acres to plant in wheat and rye. The area forms a triangle like the next picture. Check to see if it is optimal. However, for problems involving more than two variables or problems involving a large number of constraints, it is better to use solution methods that are adaptable to computers. Figure 1. Matrices and Linear Programming Expression30 4.

Degeneracy is caused by redundant constraint s and could cost simplex method extra iterations, as demonstrated in the following example. Some form of memoization can be used to avoid re-computation. Write the word or phrase that best completes each statement or answers the question. Almonds are packaged 20 bags per case. In many settings the term refers to integer linear programming ILP , in which An integer linear program in canonical form is expressed as:.

In a feasible problem, an equal-to constraint cannot be nonbinding. Answer Selected Answer: True Correct Answer: e Question 4 0 out of 2 points The standard form for the computer solution of a linear programming problem requires all variables to be to the right and all numerical values to be to the left of the The Linear Programming Calculator an online tool which shows Linear Programming for the given input.

Answer Selected Answer: True Correct Answer: e Question 4 0 out of 2 points The standard form for the computer solution of a linear programming problem requires all variables to be to the right and all numerical values to be to the left of the A calculator company produces a scientific calculator and a graphing calculator.

Competitive priorities, Chapter 2 2. Linear Programming and Polyhedral Combinatorics Summary of what was seen in the introductory lectures on linear programming and polyhedral combinatorics. Linear programming 40 9. The attendant can handle only 60 vehicles. Quadratic programming 26 6. Graphical method. Any setting of the variable x and y that satisfies all the constraints 2 - 4 a feasible solutions dashed in the figure forms a convex region in the two-dimensional space.

The constraints may be in the form of inequalities, variables may not have Start studying Algebra 2: 3. Determine the objective and write a linear objective function. From the developers of the Excel Solver: Solve larger Linear Programming problems, faster than ever, and create models more easily. It is most often used in computer modeling or simulation in order to find the best solution in allocating finite resources Chapter 7: Linear Programming in Practice Because linear programming is so remarkably useful in practice, it has been the subject of ongoing research since its invention over 50 years ago.

In this chapter, we will be concerned only with the graphical method. Define variables. Loading Unsubscribe from Amy Langelli? Introduction The theory of linear programming provides a good introduction to the study of constrained maximization and minimization problems where some or all of the constraints are in the form of inequalities rather than equalities. The essential topics will be reviewed in the first lectures. Linear Programming: More Word Problems page 4 of 5 Sections: Optimizing linear systems , Setting up word problems In order to ensure optimal health and thus accurate test results , a lab technician needs to feed the rabbits a daily diet containing a minimum of 24 grams g of fat, 36 g of carbohydrates, and 4 g of protien.

Linear Programming in Two Dimensions: A g g. The company has pounds of oats and pounds of flour available. It takes 2 minutes to answer the short answer problems and 4 minutes to answer the essay problems. The objective and constraints in linear programming problems must be expressed in terms of linear equations or inequalities. Name the coordinates of the vertices of the feasible region. Consider a. Learn vocabulary, terms, and more with flashcards, games, and other study tools. The objective function is the one that the solver of a linear programming problem wishes to maximize or minimize.

Decision variables A. The area of a parking lot is square meters. What is the velocity expressed as a function of a with which wave-fronts propagate? The solution of the system is the intersection of the individual solutions. The following form of the linear programming problem is referred to as the Then, for the Tableau-G, we have the following key rules for the dual simplex method:.

R, and X Applied Mathematics for. A company makes two products X and Y using two machines A and B. Linear programming, or LP, is a method of allocating resources in an optimal way. Linear program can be converted from any form into standard. Rank 43 Share a link to this widget: More.

Convexity 72 The graph of an inequality is the collection of all solutions of the inequality. One batch of B uses 2 pounds of oats and 3 pounds of flour. How to write vertex form, Add or Subtract Polynomials calculator, TAKS prep workbook for 8th Grade answer key, four linear equations four unknowns, dividing rational expressions solver. Linear programming solution examples Linear programming example UG exam. Write each linear equation in standard form. Consider the In Section 4.

Graph the system of inequalities. Lagrange relaxations and duality 23 5. The essence of management is to make choices that make optimal use of scarce resources. The MATLAB linear programming solver is called linprog and is Simplex Method for Standard Minimization Problem Previously, we learned the simplex method to solve linear programming problems that were labeled as standard maximization problems.

Several conditions might cause linprog to exit with an infeasibility message. When we asked how many chairs and tables Determine and graph linear functions given graphs, values or equations. The time in minutes to process one unit of each product on each machine is shown below: A calculator company produces a scientific calculator and a graphing calculator.

Solving Systems with More Variables than Equations45 Aggregate planning, Chapter 13 4. Given an. We use A typical Linear Program consists of three components:. Determine the slope and y-intercept of the line. Lec11 Page 1 Example 3: LP relaxation for the largest independent set problem. Classwork 5. Fractional vs integer solutions. The number of hours per week it takes to assemble and finish each type of stapler, and the profit for each type of stapler is given in the table below: Regular Heavy Duty In linear programming LP , all of the mathematical expressions for the objective function and the constraints are linear.

Linear equations in one variable Inthisunitwegiveexamplesofsimplelinearequationsandshowyouhowthesecanbesolved. Sufficient unbounded, or have finite optima, or have no feasible solutions. A company manufactures four products 1,2,3,4 on two machines X and Y. The time in minutes to process one unit of each product on each machine is shown below: This file derived from G8-M4-TE Linear Inequalities and Linear Programming 5. Dantzig in Such prob- Linear programming LP, also called linear optimization is a method to achieve the best outcome such as maximum profit or lowest cost in a mathematical model whose requirements are represented by linear relationships.

The third constraint is the total area present for plantation. Practice setting up linear programming models for business applications Select an even-numbered LP problem from the text, excluding 14, 20, 22, 36 which are part of your homework assignment. Capacity management concepts, Chapter 9 3. Practice continued Form K Linear Programming.

Linear Combinations, Span, Linear Independence39 8. Thischapterintroducesnotations,terminologiesand formulations of linear programming. Inanyequationthereisanunknownquantity,x say Exercise Set 2. Remember, we're trying to do this without having to use the graph at all. Excel has an add-in called the Solver which can be used to solve systems of equations or inequalities. In this lesson you will study one type of optimization process called linear programming. We will now discuss how to find solutions to a linear programming problem.

It is clear that no set of values of the unknowns satisfies such an inequality, therefore in the case under discussion the system 1 is incompatible ii has no solutions. It is quite remarkable that the converse proposition is also valid: namely. Let us agree to say that the inequality 65 is inconsistent if it is not satisfied by any set of values of the unknowns. Obviously, any inconsistent inequality is of the form 3 where d in our system. So let us suppose that none of the numbers a1, a2 It is easy to see that these numbers are sure to contain both positive and negative numbers.

Indeed, if all of the indicated numbers had the o x same sign, were they positive, for example, then the system 4 would be reduced to the form - a' would hence be compatible. Assume for definiteness that the first k numbers of a1, 02 ak are positive and the remaining in — k are negative. Then the first k inequalities of the system 5 can be replaced by a single first inequality. For systems in one unknown the theorem is thus valid. We now assume that the statement of the theorem is valid for systems in ii — 1 unknowns and under this assumption establish its validity for the case of n unknowns.

So suppose an incompatible system of linear inequalities in 11 unis given; keeping to the notation of the previous knowns x1, section we call it "system S ". We construct the concomitant system S' for it; the latter will be incompatible after S. Since the number of unknowns in the system S' is ii — 1, the hypothesis of induction applies to it.

This means that a certain combination of inequalities ; of the system S' is an inconsistent inequality.

• Account Options.
• God and the World of Signs: Trinity, Evolution, and the Metaphysical Semiotics of C. S. Peirce.
• Inequalities (Little Mathematics Library).
• Music (Fergusons Careers in Focus)!
• GMAT Quant: Arithmetic with Inequalities.
• Intersection Calculus on Surfaces With Applications to 3-Manifolds (Memoirs of the American Mathematical Society)?
• Fungi, Algae, and Protists;

But it is easily seen that each inequality of the system S' is a combination of inequalities of S ; indeed, if we simply add up the inequalities v, and or of the system S , we get i. Hence it follows in turn that a certain combination of inequali- x,, ties of the original system S is an inconsistent inequality.

The theorem on incompatible systems of linear inequalities is just one of the manifestations of the deep analogy existing between the properties of systems of linear inequalities and those of systenm at linear equations. Let us try to substitute the word "equation" for "inequality" in the formulation of the theorem. We shall have the following proposition: If a system of linear equations is incompatible, then a certain combination of these equcLtions is an inconsistent equation.

It turns out that this proposition is also valid. It is called the Kronecker-Capelli theorem in a somewhat different formulation and is proved in linear algebra this is the name of the part of mathematics which studies linear operations, i. For the above to be better understood, however, it is necessary to introduce clarity into the concept of combination. A combination of equations is constructed in the same way as a combination of inequalities, the only difference being that one is allowed to multiply the given equations by any, not only nonnegative, numbers.

As in the case of inequalities the word "inconsistent" refers to an equation having no solutions. Hence 0, Corollary of the theorem on incompatible systems. If a system of nonlieqwire solutions, then a certain combination inequalities 11 where all the of these inequalit it's is an inc'quahtv of the 0 and the absolute term a The Fundamental Set of Solutions In Section 8 we have discussed a method for finding solutions of systems of linear inequalities.

In spite of its having many obvious merits the method fails to give answers to some questions; for example. It is to this end that this and the next section of our book are devoted. The main difficulties, it will he seen, arise in considering homogeneous systems which arc dealt with in the present section: the general case i. For the reader's convenience our account is broken down into a number of points.

A linear function of n arguments. The role of the arguments is played by n variables x1, v2 x,,. One can assume, however, that function 1 depends on one rather than n arguments; this argument is the point X x1, x2, We establish the following two properties of a linear function. Some properties of the solutions of a homogeneous system of linear inequalities. If the point X i.

1. The Truth Will Out: Unmasking the Real Shakespeare!
2. Quality of Life: Assessment, Analysis, and Interpretation.
3. Selected writings.
4. Both propositions follow readily from the pioperties of a linear Indeed, suppose i is any of the numbers function proved in sect. X are solutions of mite system 2. Indeed, by virtue of Proposition I each of the points k1X1, k17X,, is a solution of the system 2 but then by virtue k2X2 of Proposition 2 so is the sum of the points.

Let us agree to call any are nonnegative numbers, a point of the form 3 , where k1, k2, Then the above consequence will allow the following statement. A nonnegative combination of any number of solutions qf the homo- geneous system 2 is again a solution of this system. We introduce the following definition. A set of a finite number of solutions xi, x2, It follows that in this case formula 4 in which k1. Hence it is clear that the problem of finding the fundamental set of solutions is one of primary importance in the investigation of the system 2.

The development of an algorithm which would allow the fundamental set of solutions for any system 2 to be found using quite simple operations is what we set ourselves as the final object. I readily yield the following two propositions: i. If X is some solution of equation 6 and k is any number, then kX is again a solution of equation 6. If X and Y are two solutions of equation 6. The proof of the propositions is left to the reader.

According to the premises there are some nonzero numbers among Set a,7 0, for example. It follows from to the points X1, X2. Now it is easy to prove the fact that any solution X of equation 6 is a nonnegative combination of the solutions X i' Indeed, let numbers X,.

For brevity of further writing denote the left-hand side of equation 6 by L X. Indeed, each of the points satisfies inequality 5. Consider a specific example. The points X1, X2, X3, X4 form the fundamental set of solutions for inequality In order to learn how to construct fundamental sets of solutions, first consider a problem like this. Suppose we are given the homogeneous system L1 X 12 L,, X 0 of linear inequalities. Suppose tiorher thot we know the fundamental 75 set of solutions x1, x2, It is required to construct the fundamental set of solutions for the system resulting from the addition of another inequality 13 to The solutions of the system 12 are precisely all nonnegative combinations of the points X1, X2, We must pick among these combinations those which would satisfy inequality 13 and, what is more, constitute the fundamental set of solutions for the system 12 , All points X1, X2,..

I none afld SO do of them is a solution of inequality The J? To prove the theorem, we first establish the following lemma. Ant' nonnegative combination of the points X can he represented as a nonnegcmtire combination of the and points X, or else a. Notice first of all that each of the points 17 satisfies the system To prove the theorem, all that remains therefore is to check the following: if some point K is a solution of the system 12 , 13 , then it can he represented in the form of a nonnegative combination of the points Suppose therefore that there are strictly positive where all the coefficients a1 , If at the same time it is found that not all of the coefficients of Xj, We continue in this way till an expression is obtained for the point X in which all the coefficients of Xj X1 are zero.

But this is exactly the required representation for X. The existence am! Let us consider an arbitrary system of homo- geneous linear inequalities. For the first inequality of the system we can using the method described in sect. On adjoining to the first the second inequality we can, on the basis of the theorem of sect. We then adjoin the third inequality and so on until we have the fundamental set of solutions for the whole of the original system of inequalities. This proves the existence, and at the same time points out the method for the construction, of the fundamental set of solutions.

For computational convenience make the following table: L1 X - X1 1 X2 0 1 0 0 X3 X4 —— 0 0 0 —3 0 0 —4 0 1 0 5 0 0 1 —6 79 Indicated in each row of the table is one of the fundamental points of the system 20 and the value of the function L1 X for that point, it is seen from the table that the only point of type X3.

The points Y3, Y1, Y2, V4 form the fundamental set of solutions for the system consisting of 20 and the first inequality of Adjoin the second inequality of 19 to that system and make the following table: L2 Y 0 0 1 0 5 0 3 0 1 Y2 0 5 4 0 3 Y4 0 0 6 5 —13 - —3 seen horn the table that the role of the points and that of the points ,. To conclude this point, we note that having proved the existence of the fundamental set of solutions for any homogeneous system of linear inequalities we have thereby proved Theorem 2' of Section 7 on the structure of any convex polyhedral cone.

The Solution of a Nonhomogeneous System of Inequalities Now that we have learnt how to construct the general solution of a homogeneous system of inequalities it won't be difficult to solve a similar problem for an arbitrary, i. There is a relation of certain kind between solutions of the systems 1 I and 2 in that if x1. Indeed, consider, for example, the first inequality of 2. It holds i, i.

A similar argument goes through for any inequality of 2 , whence our statement. It is easily seen that any solution of the system 1 can be is some obtained by the above method. Having established that solving the system 1 by the above method reduces to solving the homogeneous system 2 we have proved Theorem 3 of Section 7 on the structure of any convex polyhedral region. This may be illustrated by the example of the system 4. Thereby the statement of Theorem 3 of Section 7 is proved for Bearing as on the system 4.

A Linear Programming Problem Linear programming is a relatively new field of applied mathemain connection with the tackling of varied economic problems. Until recently the only method of solving such problems has been by ordinary rough calculation, estimating "by sight", or else by looking all the possible variants over to find the best. The situation is changing now. Over the past few decades the complexity of production has increased to such an extent that it has become impossible just to look the variants over.

The factors influencing decisions have turned out to be so numerous that in some cases the number of variants is running into milliards. This has drastically increased the interest in mathematical methods in economics. Besides, the process of"mathematization of economics" has been promoted by the devel- opment of computing technique, in particular by the advent of electronic computers. Let us consider some examples of linear programming problems. A factory turning out items of two types has an assembly shop with a production capacity of items of the first type or items of the second per diem at the same lime the quality control department is capable of checking at most items of either type per diem.

It is further known that items of the first type cost twice as much as items of the second type. Under these condi- tions it is required to find such a production plan so many items of the first type and so many items of the second per diem which would ensure the largest profit for the factory. Denote the line by As the number c increases, the line shifts "upwards" at the same time remaining parallel to its initial position.

The largest value of c at which the line still has points in common with the shaded polygon is that value of c at which the line passes through the point P. The example discussed is certainly very primitive, still it gives an idea of the nature of linear programming problems.

In some problems such as in the example above an additional requirement is imposed on the variables, that they should be integers. Example 2 diet problem. There are several kinds of food at one's disposal. It is necessary to compose a diet which would, on the one hand, satisfy the minimal human body requirements for nutrients proteins, fats, carbohydrates, vitamins, etc. Consider a simple mathematical model of this problem. Suppose there are two kinds of food, F1 and F2, which contain the nutrients A, B. It is known how much nutrient of one or another kind is contained in 1 lb of F1 or F2; this information is presented in the following table.

A of In addition te body El. It is necessary to compute the amount x1 of the food F1 and the amount x2 of the food F2 so that the required amounts of the nutrients should be ensured with minimal expenditures on the food. Thus we arrive at the following problem. Various problems can be reduced to such schemes, viz, alloy problems and problems in fuel-oil blending, feed mix problems and problems in fertilizer mixing, etc.

Example 3 transportation problem. Coal mined in several deposits is shipped to a number of consumers, to factories, power stations, etc. It is known how much coal is mined at each of the deposits, say, per month and how much is required by any of the consumers for the same term. One knows the distances between the deposits and the consumers as well as the traffic conditions between them; considering these data one can calculate the cost of transporting each ton of coal from any deposit to any consumer.

It is required that the transportation of coal should be planned in such a way under these conditions that the expenditures on it shall be minimal. Assume for simplicity that there are only two deposits D1, D2 and three consumers C3. The amounts of coal at D1 and C2. C3 D2 are and 02 respectively: let the requirements of be b1, b2, h3 respectively.

The problem can certainly be formulated in a more general form, i. It was given the name of "transportation problem" and was one of the first to be successfully solved using linear programming methods. We have considered in a simplified form three linear programming problems. Despite the diversity of their subjects the problems have much in common in their formulations.

In each problem one seeks the values of several unknowns, it being required: i that these values should be nonnegative: ii that these values should satisfy a certain system of linear equations or linear inequalities: iii that at these values a certain linear function should attain a minimum or maximum. We remark that condition ii seems to be a disjoining rather than a uniting condition, for in one case the unknowns must satisfy equations and in the other they must satisfy inequalities.

But we shall see later that one case is easily reduced to the other. It is problems of this kind that linear programming is concerned with. More strictly, linear programming is a branch of mathematics which studie. The number of variables and that of conditions equations or inequalities may of course be arbitrary. In actual problems these numbers may be very large some ten or several tens or even more. Let us put the above verbal statement down in strict terms of formulas. The general mathematical statement of a linear programming problem looks as follows. The equations of I are called the constraints of a given problem.

Strictly speaking, conditions III are also constraints: it is not customary, however, to call them so since they are not characteristic of a gizen problem alone, but are common to all linear programming problems. Of the three examples considered above only the last the transportation problem corresponds, one would think, to the statement just given.

The remaining two look slightly different since all the constraints they contain have the form of inequalities and not of equations. It is possible, however, using a simple method, to make inequality constraints go over into the equivalent constraints given in the form of equations. We demon- strate this method using the diet problem as an example. The 90 system of constraints consists of three inequalities in this problem, so we introduce three additional unknowns x3, x4, x5.

It is frequent for a linear programming problem to require that the maximum, and not the minimum, of a linear function f should be found out. It is highly interesting that the converse should also be possible, i. We shall not dwell on this, however. In conclusion we shall make a few remarks concerning the adopted terminology. Any nonnegative solution of a system of constraints is called feasible. A feasible solution yielding the minimum of a function f is called optimal. It is the finding of an optimal solution that is our goal. The optimal solution, if any, is not necessarily unique: cases are possible where there may be an infinite number of optimal solutions.

The Simplex Method Actual linear programming problems tend to contain a large nupber of constraints and unknowns. It is natural that solving such problems involves a large number of calculations. This difficulty is overcome with the help of high-speed computers. The algorithm a computer programme is based on may be connected with a specific class of problems.

There exist. Given a certain system of linear equaand a certain linear function f, it tions in a unknowns v , is required to find among the solutions of the given system such a solution which minimizes the function f. To begin working by the simplex method it is necessary that the given system of equations should be reduced to a form such that some r unknowns are expressed in terms of the rest, the absolute in the expressions being nonnegative.

This question will be considered later on see v2, x3 in the left members of the sect. A change in the basis involves a corresponding change in the structure of the system I , of course. We illustrate the simplex method by some examples. The corresponding Here the unknowns basic solution is 1, 2, 3, 0, 0 the value of f is 0 for this solution.

Since negative coefficient, we may try to decrease the value of I by increasing x5 while retaining a zero value for x4. Care should be taken in doing so, however, since changing x5 will lead to changes 93 in the values of x1, x2, x3 and it is necessary to see to it that none of them become negative. There is no such danger for 'c1, since increasing x5 results in the increase of x1. As a result we have a new feasible solution 5, 0, 1, 0, 2 in which the number of positive unknowns is equal to three as before.

The value of I for this solution is equal to — 2. The new basis now consists of x1, x5, x3. To make appropriate modifications in the system of constraints, it is necessary to express these unknowns in terms of x2, x4. This completes the first step of the process. Let us see if it is possible to decrease the value of f still further. The new basis now consists of x1. This completes the second step of the process. In the example analysed the process has terminated in finding 1 an optimal solution. Yet another termination of the process is possible.

To illustrate it, we solve the following example. The basic solution is of the form 0, 0, 1, 2 the corresponding value of the function I being equal to 0. In the expression for f the coefficient of x1 is negative, therefore we try to increase x1 without changing. The first equation 95 does not prevent us from doing so. The new feasible solution is 2.

## History of algebra

In the last expression for I the coefficient of v2 is negative. We want to see how much we can decrease the value of f by increasing while keeping 0. For this purpose we look over the x2 terms in both equations of the system and notice that both coefficients of x2 are positive. If it turns out some nonbasic unknown that there are several negative coefficients, one may choose any of them.

This introduces a certain amount of arbitrariness into the computations. The arbitrariness does not necessarily end here, it may happen that increasing to the extreme makes several basic unknowns vanish together.

Then it is possible to make any of them x1 exchange roles with i. It would of course be possible to eliminate the arbitrariness by introducing some additional agreement. There is no particular need to do it, however. In fact some arbitrariness is even helpful. In the previous subsection we described the procedure for solving a linear programming problem by the 96 simplex method.

In many linear programming problems the basis can be directly perceived, and in others it has to be found. We shall consider one of the methods of finding the basis generally known as "the method of an artificial basis". We shall analyse an example to illustrate the method. To do this we should multiply both members of the first equation by — 1. It remains to decide how to transform the unknowns v1, Y2 of the system 5 into nonbasic unknowns. Here the premises under which the simplex method begins to work are satisfied since the system 5 is of the required form it has the original basis Yi.

In some steps we arrive at the desired minimum. Since F 0 and hence mm F 0, two cases are possible: 1. Therefore the original system 4 will have no nonnegative solutions in this case. Hence it will follow that any linear programming problem with such a system of constraints is insoluble. Suppose that in this case x? Since y?

Further, if on accomplishing the process i. Vi, Y2 still belong to the basis, then some further transformations are required. Comparing the coefficients of x4 and the absolute terms in the equations of 5 we find that x4 can be increased only to 4. Yi then vanishing. The 98 We solve the first equation for x4 and substitute the resulting expression into the second equation and into F. As a result we have succeeded in making the unknown Yi nonbasic. In the new expression for F the coefficient ofx1 is negative.

Looking at equations 6 we see that x1 can be increased only to 1, then vanishing. The new basis consists of x4, x1. On transforming equations 6 and the expression for F transforming the latter is now optimal. Thus the problem is solved. As already noted, when applying the simplex method to finding the minimum of the function F equal to the sum of the artificial unknowns, it may happen that by the time the process is over i.

These unknowns can also be transformed into nonbasic ones by simple methods which we shall demonstrate using an example. The unknowns Y2 and y3 are still part of the basis. We now make use of this circumstance to make leave the basis. To do this we observe that there is a Y2 and negative number among the coefficients of the unknowns x1, We make the replacement x3 y2 we make the unknown x3 basic and make nonbasic. To do this we solve the second of the equations for x3 and substitute the resulting expression for into the other equations. Since the absolute term in the second equation is zero, as a 32 become result of such an operation the absolute terms in the equations will remain unchanged and hence nonnegative.

## Pauls Online Math Notes

But we should not be much annoyed at this. For if some numbers x1, satisfy the original system of constraints, then Vi, must be zero. There are so-called duality theorems in various branches of mathe- matics. Each of them allows the constructing for any statement in a given theory, according to a certain standard rule, of another statement in such a way that the validity of the first statement automatically leads to the validity of the second.

A remarkable example of a duality theorem is met in linear programming too. Suppose a certain linear programming problem is given; we shall call it the original problem. The constraints are given in the form of inequalities. We connect with problem A another problem which we call a dual problem relative to problem A or problem A'. Comparing problems A and A' we notice: 1. That the coefficient of the jth unknown in the ith equation of the system 1' is the same as that of the ith unknowns in the jth equation of the system 1 ; 2.

That the absolute terms of the inequalities in each of the problems coincide with the coefficients of the unknowns in the linear function of the other problem; 3. That in the system of inequalities of problem A the inequalities are all of the 0 type, it being required in the problem that the maximum of f should be attained. On the contrary, in the system of inequalities of problem A' the inequalities are all of the 0 type, but in return it is required in it that the minimum of p should be attained.

One of the main theorems in linear programming, the so-called duality theorem, states the following. Duality theorem. If an original problem is solvable, so is its dual, the maximum of the function f being equal to the minimum of the function p: max We shall prove this theorem by reducing it to the question of compatibility of a certain system of inequalities. To make the proof more convenient to follow, we break it down into several stages.

Stage 1. In the same way, we multiply the first inequality of the system 1' by x? Hence the two expressions in brackets coincide. But then b1 y? Stage 2. Reducing problems A and A' to the solution of a certain system of inequalities. The unknowns of the system S are x1,.. We first of all establish the following fact. If the system S has nonnegative solution 4 then It is seen that it the numbers x? What is remarkable about it is that a linear programming problem, i. In fact, the solution of the system S in the range of nonnegative values of unknowns is of course not a bit easier than the solution of the original linear programming problem problem however, the very possibility of such a reduction is very curious.

Now we prove the above statement. First of all, it is clear that are nonnegative and satisfy the system 1 ; simithe numbers x? Morelarly the numbers over, these numbers satisfy the inequality following from the last inequality of the system S. This proves the above proposition. Stage 3. Completing the proof Now it remains for us to show the following: if problem A has a solution, then the system S has a nonnegative solution.

We shall argue following the rule of contraries, i. For this case we have the corollary of the theorem on incompatible systems Section 9. True, this corollary refers to a system consisting of 0 type and our system S has inequalities inequalities of the of the 0 type. Lccording to the corollary of the theorem on incompatible systems, ii, Cnln this is not the case, solution x? Consider some nonnegative i. For this solution the value of the function f is c 1x?

So on supposing that the system S has no nonnegative solutions, we come to a contradiction. Such solutions are therefore certain to exist, which proves the duality theorem. Let us call the set problem problem A. This is done in Fig. This value is equal to 3. By the duality theorem the maximum of the function f must also be equal to 3. Transportation Problem In Section 12 we have considered a number of specific linear programming problems.

Of special interest among them is the transpor- tation problem, above all due to its practical significance.

## Systems of Linear Inequalities a. S. Solodovnikov (Little Mathematics Library)

There is voluminous literature devoted to this and similar problems. One must say that the methods of solving the transportation problem are rather instructive. They demonstrate the indubitable fact that when solving any special class of problems general methods say the simplex method should be employed with caution, i.

Stating the problem. We remind the reader how the transportation problem is stated in the general form. There are some, say m, source points suppliers A1, A2, We assume the condition implying that the total stock of goods is equal to the summed we are also given demand for it. In addition to the numbers a1, denoting the cost of transporting a ton of quantities goods from point A, to point It is required to develop an optimal shipping schedule, i.

B3, Indeed, the ith equation of the system 1 implies that the sum of the unknowns in the ith row of the transportation table is equal to a,: we shall call equations 1 horizontal for this reason. Similarly, the jth equation of the system 2 records the fact that the sum of the unknowns in the fth column of the transportation table is equal to h1; because of this we shall call the equations of the system 2 vertical.

We ship x,1 tons of goods from point A, to point B, the cost of transporting one ton being c1. We thus come to the following linear programming problem. Given the. Find among the nonnegative ,r minimizes the fiAnction 3. The transportation problem can be solved by the simplex method like any other linear programming problem. Because of the special structure of the system of constraints 1 , 2 the general procedure of the simplex method is, of course, greatly simplified when applied to the transportation problem. Here we present a method for solving the transportation problem called the method of potentials.

It is a variant of the simplex method specially adapted for solving the transportation problem. Finding the first basis. As we know, the work by the simplex method is preceded by a preparatory stage, that of finding the first basis.