National university of uzbekistan named after mirzo ulugbek uzbek-israel joint faculty

Example 1 A Maximization Problem with Mixed Constraints
Find the maximum value of
Objective function
subject to the constraints
Constraints
where , and .
Solution
To begin, add a slack variable to each of the first two inequalities and subtract a surplus variable from the third inequality to produce the system of linear equations below.

Next form the initial simplex tableau.

							Basic Variable
3	2	5	1	0	0	18
4	2	3	0	1	0	16
2	1	1	0	0	-1	4		←Departing
-3	-2	-4	0	0	0	0

This tableau does not represent a feasible solution because the value of is negative. So, should be the departing variable. There are no real guidelines as to which variable should enter the solution, and in fact, any choice will work. However, some entering variables will require more tedious computations than others. For example, choosing x₁ as the entering variable produces the tableau below.

							Basic Variable
0	1/2	7/2	1	0	3/2	12
0	0	1	0	1	2	8
1	1/2	1/2	0	0	-1/2	2
0	-1/2	-5/2	0	0	-3/2	6

Choosing as the entering variable on the initial tableau instead produces the tableau shown below, which contains “nicer” numbers.

							Basic Variable
-1	0	3	1	0	2	10
0	0	1	0	1	2	8
2	1	1	0	0	-1	4
1	0	-2	0	0	-2	8

Choosing as the entering variable on the initial tableau will also produce a tableau that does not contain fractions.
Notice that both of the tableaus shown represent feasible solutions. Any choice of entering variables will lead to a feasible solution, so use trial and error to find an entering variable that yields “nice” numbers. Once you have reached a feasible solution, follow the standard pivoting procedure to choose entering variables and eventually reach an optimal solution.
The rest of this solution uses the tableau produced by choosing x₂ as the entering variable. This tableau does represent a feasible solution, so proceed as usual, choosing the most negative entry in the bottom row to be the entering variable. (In this case, there is a tie, so arbitrarily choose to be the entering variable.)

							Basic Variable
-1	0	3	1	0	2	10		←Departing
0	0	1	0	1	2	8
2	1	1	0	0	-1	4
1	0	-2	0	0	-2	8
		↑
		Entering

							Basic Variable
-1/3	0	1	1/3	0	2/3	10/3
1/3	0	0	-1/3	1	4/3	14/3		←Departing
7/3	1	0	-1/3	0	-5/3	2/3
1/3	0	0	2/3	0	-2/3	44/3
					↑
					Entering

							Basic Variable
-1/2	0	1	1/2	-1/2	0	1
1/4	0	0	-1/4	3/4	1	7/2
11/4	1	0	-3/4	5/4	0	13/2
1/2	0	0	1/2	1/2	0	17

So, the maximum value of the objective function is , and this occurs when

, and .

Conclusion

In this work we have studied applications of linear programming in different fields. We concluded that linear programming is an important branch of applied mathematics that solves a wide variety of optimization problems. Optimization problems have always attracted a lot of attention due to applications in various sectors of economy and other sciences. However, after the WWII interest in these problems enormously increased as the first computers became to appear. They made available to perform large-scale numerical calculations, which allowed to consider the problems with many variables and gave higher accuracy.
In these days, linear programming is widely used in production planning and scheduling problems. Many recent advances in the field have come from the airline industry where aircraft and crew scheduling have been great improved by the use of linear programming. It is also used to increase profit of any business with a limited budget. Although the modern management issues are ever-changing, most companies would like to maximize profits and minimize costs with limited resources. For example, Google uses linear programming to stabilize YouTube videos. Therefore, many issues can be characterized as linear programming problems.
We have seen that optimization problems, particularly maximization ones, are described as a mathematical model, where a problem is described by some constraints (linear inequalities) and an object function to be maximized. There are several methods which are used in optimization problems. In our work, we learned the graphical and simplex methods of linear programming. Although the simplex method is not theoretically satisfactory from a computational point of view, it is by far the most widely used method to solve linear programming problems and only rarely are its limitations encountered in practical applications. Graphical methods are mostly comfortable for problems with two variables, where constraints, which are linear functions, can be sketched and the necessary regions and its boundaries can be found. However, this method is not much effective if number of variables are greated than 2, where sketching the contrraints become more challenging or not possible at all.
The biggest advantage of linear programming as an optimization method is that it always achieves the optimal solution if one exists.
In our work, we briefly reviewed the history, development and applications of linear programming. As an example, we learned the graphical and simplex methods and solved number of problems related to those. Particularly, for specific economic problems, we created a mathematical model, and showed their optimal solutions.
To sum up, linear programming is an important tool in maximization problems. It shows optimal solutions, which are obtained by rigid mathematical conclusions. We hope that we can apply this method in real sectors of economy and help to increase productivity and profit of various businesses.

References

1. 
   Ron Larson, David C. Falvo. Elementary Linear Algebra The sixth edition/ Available online at college.hmco.com/pic/larsonELA6e
   
2. 
   Baily M.J. “A Generalized Comparative Statics in Linear Programming”, Review of Economic Studies 23, 236-240., (1955-6).
   
3. 
   Beale, E.M.L, “Cycling in the Dual Simplex Algorithm”, Naval Research Logistics Quarterly 2, 269-276, (1955).
   
4. 
   Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Solutions, Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)
   
5. 
   G.B Dantzig: Maximization of a linear function of variables subject to linear inequalities, 1947.
   
6. 
   Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. (1998).
   
7. 
   Kantorovich, L. V. "Об одном эффективном методе решения некоторых классов экстремальных проблем" [A new method of solving some classes of extremal problems]. 211–214. (1940).
   
8. 
   https://math.libretexts.org/Sandboxes/Jaison_Novick/1250_Draft_4/08%3A_Linear_Programming_-_A_Geometric_Approach
   
9. 
   https://en.wikipedia.org/wiki/Linear_programming.
   
10. 
    F. L. Hitchcock: The distribution of a product from several sources to numerous localities, Journal of Mathematics and Physics, 20, 224–230, 1941.
    
11. 
    J. E. Beasley, editor. Advances in Linear and Integer Programming. Oxford Science, 1996. (Collection of surveys)
    
12. 
    Bland, Robert G. "New Finite Pivoting Rules for the Simplex Method". Mathematics of Operations Research. 2 103–107, (1977).
    
13. 
    Karl-Heinz Borgwardt. The Simplex Algorithm: A Probabilistic Analysis, Algorithms and Combinatorics, Volume 1, Springer-Verlag, 1987. (Average behavior on random problems)
    
14. 
    Richard W. Cottle, ed. The Basic George B. Dantzig. Stanford Business Books, Stanford University Press, Stanford, California, (Selected papers by George B. Dantzig). 2003.
    
15. 
    George B. Dantzig and Mukund N. Thapa. Linear programming 1: Introduction. Springer-Verlag. (1997).
    
16. 
    George B. Dantzig and Mukund N. Thapa. Linear Programming 2: Theory and Extensions. Springer-Verlag. (Comprehensive, covering e.g. pivoting and interior-point algorithms, large-scale problems, decomposition following Dantzig–Wolfe and Benders, and introducing stochastic programming.). (2003.)
    
17. 
    Edmonds, Jack, Giles, Rick. "A Min-Max Relation for Submodular Functions on Graphs". Studies in Integer Programming. Annals of Discrete Mathematics. Vol. 1. pp. 185–204.
    
18. 
    Fukuda, Komei; Terlaky, Tamás. Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. (1997) (1–3): 369–395.
    
19. 
    Gondzio, Jacek; Terlaky, Tamás. "3 A computational view of interior point methods". In J. E. Beasley (ed.). Advances in linear and integer programming. Oxford Lecture Series in Mathematics and its Applications. Vol. 4. New York: Oxford University Press. (1996) pp. 103–144.
    
20. 
    Murty, Katta G. Linear programming. New York: John Wiley & Sons, Inc. pp. xix+482. (comprehensive reference to classical approaches). (1983)
    
21. 
    Evar D. Nering and Albert W. Tucker, Linear Programs and Related Problems, Academic Press. (elementary), 1993
    
22. 
    M. Padberg, Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999. (carefully written account of primal and dual simplex algorithms and projective algorithms, with an introduction to integer linear programming – featuring the traveling salesman problem for Odysseus.)
    
23. 
    Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Corrected republication with a new preface, Dover. (computer science)
    
24. 
    Michael J. Todd "The many facets of linear programming". Mathematical Programming. (3): 417–436. (Invited survey, from the International Symposium on Mathematical Programming.) (February 2002).
    
25. 
    Vanderbei, Robert J. Linear Programming: Foundations and Extensions. Springer Verlag. (2001). 
    
26. 
    Vazirani, Vijay V. Approximation Algorithms. Springer-Verlag. (Computer science). (2001).