Simplex Algorithm

11 Key excerpts on "Simplex Algorithm"

• 

  eBook - ePub

  Deterministic Operations Research

  Models and Methods in Linear Optimization

  • David J. Rader(Author)
  • 2013(Publication Date)
  • Wiley

    (Publisher)

  CHAPTER 8

  SOLVING LINEAR PROGRAMS: SIMPLEX METHOD

  The previous two chapters introduced some basic concepts in optimization, such as improving search methods and the geometry and algebra of linear programs. We now combine these topics to produce an algorithm for solving linear programs called the Simplex Method. The simplex method is the most widely used optimization algorithm, solving daily thousands of real-world problems for business, industry, academe, and other scientific outlets. Various implementations routinely solve problems with millions of constraints and tens of millions of variables. In this chapter, we learn the fundamentals of the simplex method, how to implement it efficiently, and how it deals with various “problem areas.”

  8.1 SIMPLEX METHOD

  The simplex method is a specialized version of the general improving search algorithm (Algorithm 6.2) that is designed to take advantage of the properties of linear programs. Like many improving search algorithms, the simplex method moves from feasible solution to feasible solution, improving the objective function value at each step; however, the simplex method examines only certain types of solutions.

  Because linear programs can appear in many equivalent forms, we concentrate on solving only linear programs expressed in the canonical form

  (8.1)

  with m constraints and n variables. We assume the rank of , a is m and that m ≤ n . From the fundamental theorem of linear programming (Theorem 7.5), if a linear program has an optimal solution then at least one such solution exists at a basic feasible solution, which implies that we need to consider only basic feasible solutions. For a linear program in canonical form (8.1), a basic feasible solution is a solution for which the variables are partitioned into m basic variables and n − m nonbasic variables, the columns of , a associated with the basic variables (denoted by the matrix B ) are linearly independent, the values of the nonbasic variables xN are zero, and the values of the basic variables xB uniquely solve B xB = b

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Basic Mathematics for Economics, Business and Finance

  • EK Ummer(Author)
  • 2012(Publication Date)
  • Routledge

    (Publisher)

  Simplex Algorithm.

  5.3.2  Concepts and Definitions

  Let us first explain and define here some of the concepts that we will use throughout the rest of this chapter. Most of these concepts will be clearer as we proceed through the next few sections. We begin with the term algorithm. An algorithm is a fixed set of computational rules or procedures that are used repetitively to the problem under consideration for finding the solution to it. Each repetition of the algorithm is called an iteration. In each iteration we move the solution closer and closer to the optimum.

  The simplex method or Simplex Algorithm is a fixed set of computational rules or procedures for finding the BFSs in a LP problem. For any BFS, some variables are held at 0. Such variables are called nonbasic variables (NBVs) and all other variables are called basic variables (BVs). The set of BVs is called the basis.

  5.3.3  Iteration: The Basic Nature of the Simplex Method

  As an example to illustrate the iterative nature of the simplex method, consider the two-variable maximization LP problem (5.2.5) in Section 5.2.2, which we solved graphically using Figure 5.2.1 and found the optimal solution x∗ = 36 and y∗ = 6. We reproduce that problem here for convenience:

  The graphs of the objective function and of the functional forms of the constraints of this problem are illustrated in Figure 5.3.1(A), which is similar to Figure 5.2.1 . We converted the in equality constraints of this problem to equality constraints using slack variables and the converted problem is given in equations (5.2.21) and (5.2.22). This is called the augmented form of the original LP maximization problem (5.2.5). Let us now include the slack variables in our discussion and construct Table 5.3.1 that gives the coordinates of the corner points in Figure 5.3.1

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Linear Mathematics

  A Practical Approach

  • Patricia Clark Kenschaft(Author)
  • 2013(Publication Date)
  • Dover Publications

    (Publisher)

  Chapter 6 THE Simplex Algorithm

  6.1 Solving Standard Linear Programming Problems Using the Simplex Algorithm

  The linear programming problems in Chapter 5 included both nonnegativity constraints and other constraints. We shall refer to the constraints in any linear programming problem that are not nonnegativity constraints as significant constraints . These will be the constraints of primary interest, since whenever the simplex method is used, all the independent variables are assumed to be nonnegative . Thus the nonnegativity constraints are often not written, but simply understood.

  A linear programming problem is said to be standard if the objective function is to be maximized and if all the significant constraints are of the form a1 x1 + a2 x2 + … + an xn ≤ b where the ai and b are constants (b ≥ 0) and the x

  i

  are variables. Section 5.2 and 5.3 discussed only standard linear programming problems, as will this section and the next. In Section 7.1 we shall see that every standard linear programming problem can be expressed in the form “Maximize P = DX when AX ≤ B,” where D is a row vector, B is a column vector, A is a matrix, and all the elements in B are nonnegative.

  An algorithm is a method for solving a particular type of routine problem. The Simplex Algorithm (or method) is a mathematical technique that was developed in the middle of the twentieth century for the purpose of solving linear programming problems. This section shows how to use the Simplex Algorithm to solve standard linear programming problems. The next section explains more of the reasoning behind the algorithm, and Section 6.3 shows how it can be adapted to linear programming problems that are not in standard form.

  The Simplex Algorithm uses a basic idea from the tabular method-that of examining vertices of the feasible region. But only certain vertices are examined by the Simplex Algorithm. Each such vertex is described by a simplex tableau; a series of tableaux are written, each one describing a vertex adjacent to the one described by the previous tableau. In each tableau the value of the objective function is increased over the value in the previous tableau. When the objective function can increase no more, we have reached the maximum, and the location of the corresponding vertex can be read off the tableau. A standard linear programming problem always includes the origin as one of its feasible points; thus the first tableau can and will always describe the origin.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Elementary Linear Programming with Applications

  • Bernard Kolman, Robert E. Beck(Authors)
  • 1995(Publication Date)
  • Academic Press

    (Publisher)

  2

  The Simplex Method

  IN THIS CHAPTER we describe an elementary version of the method that can be used to solve a linear programming problem systematically. In Chapter 1 we developed the algebraic and geometric notions that allowed us to characterize the solutions to a linear programming problem. However, for problems of more than three variables, the characterization did not lead to a practical method for actually finding the solutions. We know that the solutions are extreme points of the set of feasible solutions. The method that we present determines the extreme points in the set of feasible solutions in a particular order that allows us to find an optimal solution in a small number of trials. We first consider problems in standard form because when applying the method to these problems it is easy to find a starting point. The second section discusses a potential pitfall with the method. However, the difficulty rarely arises and has almost never been found when solving practical problems. In the third section, we extend the method to arbitrary linear programming problems by developing a way of constructing a starting point.

  2.1 THE SIMPLEX METHOD FOR PROBLEMS IN STANDARD FORM

  We already know from Section 1.5 that a linear programming problem in canonical form can be solved by finding all the basic solutions, discarding those that are not feasible, and finding an optimal solution among the remaining. Since this procedure can still be a lengthy one, we seek a more efficient method for solving linear programming problems. The Simplex Algorithm is such a method; in this section we shall describe and carefully illustrate it. Even though the method is an algebraic one, it is helpful to examine it geometrically.

  Consider a linear programming problem in standard form

  (1)

  subject to

  (2)

  (3)

  where A = [a ij ] is an m × n matrix and

  In this section we shall make the additional assumption that b ≥ 0 . In Section 2.3 we will describe a procedure for handling problems in which b

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Applied Linear Algebra and Optimization Using MATLAB

  • Rizwan Butt(Author)
  • 2011(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  .

  5. Alternate Optimum. When a linear program has more than one optimal solution, it is said to have an alternate optimal solution. In this case, there exist more than one feasible solution having the same optimal value (Z0 ) for their objective functions.

  6. Unique Optimum. The optimal solution of a linear program is said to be unique when there exists no other optimal solution.

  7. Unbounded Solution. When a linear program does not pose a finite optimum (i.e., Zmax → 8), it is said to have an unbounded solution.

  6.6 The Simplex Method

  The graphical method of solving an LP problem introduced in the last section has its limitations. The method demonstrated for two variables can be extended to LP problems involving three variables, but for problems involving more than two variables, the graphical approach becomes impractical. Here, we introduce the other approach called the simplex method, which is an algebraic method that can be used for any number of variables. This method was developed by George B. Dantzig in 1947.

  It can be used to solve maximization or minimization problems with any standard constraints. Before proceeding further with our discussion with the Simplex Algorithm, we must define the concept of a basic solution to a linear system(6.13).

  6.6.1 Basic and Nonbasic Variables

  Consider a linear system Ax = b of M linear equations in N variables (assume N ≥ M).

  Definition 6.4 (Basic Solution)

  A basic solution to Ax = b is obtained by setting N - M variables equal to 0 and solving for the values of the remaining M variables. This assumes that setting the N - M variables equal to

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  A Course in Linear Algebra with Applications

  2nd Edition

  • Derek J S Robinson(Author)
  • 2006(Publication Date)
  • WSPC

    (Publisher)

  Chapter Ten LINEAR PROGRAMMING

  One of the great successes of linear algebra has been the construction of algorithms to solve certain optimization problems in which a linear function has to be maximized or minimized subject to a set of linear constraints. Typically the function is a profit or cost. Such problems are called linear programming problems.

  The need to solve such problems was recognized during the Second World War, when supplies and labor were limited by wartime conditions. The pioneering work of George Danzig led to the creation of the Simplex Algorithm, which for over half a century has been the standard tool for solving linear programming problems. Our purpose here is to describe the linear algebra which underlies the Simplex Algorithm and then to show how it can be applied to solve specific problems.

  10.1 Introduction to Linear Programming

  We begin by giving some examples of linear programming problems.

  Example 10.1.1 (A productionproblem)

  A food company markets two products F1 and F2 , which are made from two ingredients I1 and I2 . To produce one unit of product Fj one requires aij units of ingredient The maximum amounts of I1 and J2 available are m1 and m2 , respectively. The company makes a profit of pi on each unit of product Fi sold. How many units of F1 and F2 should the company produce in order to maximize its profit without running out of ingredients?

  10.1: Introduction to Linear Programming

  Suppose the company decides to produce Xj units of product Fj . Then the profit on marketing the products will be z = p1 x1 + p2 x2 . On the other hand, the production process will use a11 x1 +a12 x2 units of ingredient and I1 and a21 x2 + a22 x2 units of ingredient I2 . Therefore x1 and x2

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Optimization Using Linear Programming

  • A. J. Metei, Veena Jain(Authors)
  • 2019(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  and such a case needs to be handled differently. For the time being, we assume that we do not have this situation.

  3.4.Relationship between the Simplex and Graphical Methods

  Now that it can be seen that the simplex method is similar to solving a system of linear equations. In fact, this method does solve a system of linear equations (to be discussed in next chapter) and the solution is derived. Further, the method not only solves the equations but also optimizes the objective function of the problem. There are a number of methods for solving simultaneous linear equations. For example, the Gauss-Jordan method discussed in Chapter 1 is one such method which has a close relation to the simplex calculation.

  The simplex method as seen previously is an iterative method of solving a given linear programming problem. The method starts its calculation with an initial basic feasible solution and then repeats the solution process by removing one basic variable from the basis and allowing another from the non-basic variables to enter the basis, making successive improvements until the optimal solution is found. It is sometimes referred to as an adjacent extreme point solution procedure because it generally begins at a feasible extreme point and then successively evaluates the adjacent extreme point until one representing the optimal solution is found. It may be recalled that in the graphical method the optimum solution (if it exists) of a problem is found at one of the extreme points. To understand this more deeply, we consider Example 3.5 of the previous section:

  Maximize z = 4x1 + x2

  Subject to the constraints:

  Fig. 3.1

  Let the simplex method start its calculation at the origin (0, 0), which means at this point x1 and x2 are both non-basic variables. Now, since in the objective function equation x1 has a larger coefficient than x2 , we shall allow x1

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Integer and Combinatorial Optimization

  • Laurence A. Wolsey, George L. Nemhauser(Authors)
  • 2014(Publication Date)
  • Wiley-Interscience

    (Publisher)

  I.6

  Polynomial-Time Algorithms for Linear Programming

  1. INTRODUCTION

  Simplex methods (see Chapter I.2) are practical techniques for solving linear programs. But, according to the model of computational complexity presented in the previous chapter, they are unsatisfactory because their running time can grow exponentially with the size of the input. Here we give some polynomial-time algorithms for linear programming and discuss their consequences in combinatorial optimization.

  The ellipsoid algorithm, which will be presented in Section 2, was acclaimed on the front pages of newspapers throughout the world when it appeared in 1979. Although the algorithm turned out to be computationally impractical, it yielded important theoretical results. It was the first polynomial-time algorithm for linear programming. Also, as will be discussed in Section 3, it is a tool for proving that certain combinatorial optimization problems can be solved in polynomial time.

  In Section 4, we will present a version of a polynomial-time projective algorithm for linear programming. Remarkably good computational results have been claimed for projective algorithms, but only time will tell whether they are superior to, or a serious rival of, simplex methods.

  The running times of these polynomial-time algorithms typically depend on m, n, and log

  θA, b, c

  where

  In Section 5, it will be shown how the dependence on b and c can be eliminated. Thus, for example, when A is a (0, 1) matrix, there are linear programming algorithms that are polynomial in m and n.

  To present polynomial-time versions of the ellipsoid and projective algorithms, some basic questions about linear programming must be addressed.

  1. Unlike the simplex methods, the ellipsoid and projective algorithms are naturally described as algorithms to find a feasible point in a polyhedron. Hence, we must convert a feasibility algorithm into an optimization algorithm. The standard approach is to formulate a linear program as the feasibility problem: Find

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introductory Mathematical Economics

  • Adil H. Mouhammed(Author)
  • 2020(Publication Date)
  • Routledge

    (Publisher)

  Chapter Seven

  Linear Programming I: The Simplex Method

  Economics was defined by Lionel Robbins (1932) as the science of studying the allocation of scarce economic resources among competing ends, that is, economics is concerened with making choices and decisions. Similarly, linear programming is a mathematical theory by which the available economic resources can be allocated efficiently for achieving a certain goal.

  Linear programming was developed independently by Leonid Kantorovich and T.C. Koopmans; both shared the Nobel prize in economics in 1975 for developing this mathematical model (Kantorovich 1960,1965; Koopmans 1951). Kantorovich was able to find a mathematical model by which the available economic resources in the Soviet Union could be allocated efficiently. Kantorovich, however, was not able to develop an algorithm by which a linear mathematical program can be solved. This task was left to George Dantzig to develop in 1947 (Dantzig 1963). Since then economists such as Dorfman (1953), Dorfman et al. (1958), and Baumol (1977) have applied the model of linear programming to a variety of real world problems in transportation, accountancy, finance, diet, the military, agriculture, and human resources, to mention a few.

  A Problem’s Formulation and Assumptions

  The most difficult part of linear programming is the formulation of a particular segment of the real world in a linear mathematical programming context (Taha 1987; Thompson 1976; Lapin 1991). In fact, the formulation of a linear programming problem is an art that must be learned from experience rather than a textbook. Mathematically, a mathematical linear program is written as

  Maximize Z = c1 X1 + c2 X2 + c3 X3 + ... + cn Xn

  Subject to

  a 11

  X 1

  +

  a

  1 2

  X 2

  + ... +

  a ln

  X n

  ≤

  b 1

  a 21

  X 1

  +

  a 22

  X 2

  + ... +

  a

  2 n

  X n

  ≤

  b 3

  a

  3 1

  X 1

  +

  a

  3 2

  X 2

  + ... +

  a

  3 n

  X n

  ≤

  b 3

  ...................................

  a

  m 1

  X 1

  +

  a

  m 2

  X 2

  + ... +

  a

  m n

  X n

  ≤

  b m

  X 1

  ≥ 0 ,  

  X 2

  ≥ 0

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Quantitative Methods for Business and Economics

  • Adil H. Mouhammed(Author)
  • 2015(Publication Date)
  • Routledge

    (Publisher)

  CHAPTER SEVEN

  Linear Programming I: The Simplex Method

   

  Economics was defined by Lionel Robbins (1932) as the science of studying the allocation of scarce economic resources among competing ends, that is, economics is concerened with making choices and decisions. Similarly, linear programming is a mathematical theory by which the available economic resources can be allocated efficiently for achieving a certain goal.

  Linear programming was developed independently by Leonid Kantorovich and T.C. Koopmans; both shared the Nobel prize in economics in 1975 for developing this mathematical model (Kantorovich 1960,1965; Koopmans 1951). Kantorovich was able to find a mathematical model by which the available economic resources in the Soviet Union could be allocated efficiently. Kantorovich, however, was not able to develop an algorithm by which a linear mathematical program can be solved. This task was left to George Dantzig to develop in 1947 (Dantzig 1963). Since then economists such as Dorfman (1953), Dorfman et al. (1958), and Baumol (1977) have applied the model of linear programming to a variety of real world problems in transportation, accountancy, finance, diet, the military, agriculture, and human resources, to mention a few.

  A Problem’s Formulation and Assumptions

  The most difficult part of linear programming is the formulation of a particular segment of the real world in a linear mathematical programming context (Taha 1987; Thompson 1976; Lapin 1991). In fact, the formulation of a linear programming problem is an art that must be learned from experience rather than a textbook. Mathematically, a mathematical linear program is written as

  Maximize Z = c1 X1 + c2 X2 + c3 X3 + … + Cn Xn

  Subject to

  a11 X1 + a12 X2 + … + a1n Xn ≤ b1

  a21 X1 + a22 X2 + … + a2n Xn ≤ b2

  a31 X1 + a32 X2 + … + a3n Xn ≤ b3

            …………………

  am1 X1 + am2 X2 + … + amn Xn ≤ bm

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Operations Research

  A Practical Introduction

  • Michael W. Carter, Camille C. Price(Authors)
  • 2017(Publication Date)
  • CRC Press

    (Publisher)

  Thus, instead of a unique optimal solution, we have infinitely many optimal solutions from which to choose, thereby permitting management to select on the basis of secondary factors that do not appear in the model. This situation can be recognized in the Simplex tableau during Step 2 of the Simplex Algorithm. If a zero appears in the objective function row corresponding to a non-basic variable, then that non-basic variable can enter the basis without changing the value of the objective function. In other words, there are two distinct adjacent extreme points that yield the same value of z. When we apply the Simplex Algorithm to the problem illustrated in Figure 2.3, the initial solution is x 1 = x 2 = 0. In the first iteration, x 2 enters the basis and s 1 leaves, and this solution x 1 = 0, x 2 = 2 yields z = 4. Next, x 1 enters the basis and s 2 leaves, and we obtain the solution designated as point A in the figure where x 1 = 4/3, x 2 = 10/3, and z = 8. (Observe that s 3 is a basic variable and, therefore, constraint 3 is not binding at this point.) Now, the third Simplex tableau is as follows. z x 1 x 2 s 1 s 2 s 3 Solution z 1 0 0 0 1 0 8 x 2 0 0 1 1/3 1/3 0 10/3 x 1 0 1 0 −2/3 1/3 0 4/3 s 3 0 0 0 2/3 −1/3 1 14/3 This solution is optimal since all elements on the top row are non-negative. The zero in the top row corresponding to the non-basic variable s 1 signals that this problem has multiple optimal solutions. And, in fact, if we apply another pivot operation (by bringing s 1 into the basis and selecting s 3 to leave the basis), we obtain the fourth tableau z x 1 x 2 s 1 s 2 s 3 Solution z 1 0 0 0 1 0 8 x 2 0 0 1 0 1/2 −1/2 1 x 1 0 1 0 0 0 1 6 s 1 0 0 0 1 −1/2 3/2 7 This solution corresponds to point B in Figure 2.3 where x 1 = 6, x 2 = 1, and z = 8; and where s 1 is basic and consequently constraint 1 is not binding at this

  Sign up to read

  Learn more about book