Linear Programming

12 Key excerpts on "Linear Programming"

• 

  No longer available |Learn more

  Operations Research

  • (Author)
  • 2014(Publication Date)
  • Orange Apple

    (Publisher)

  ____________________ WORLD TECHNOLOGIES ____________________ Chapter- 8 Linear Programming Linear Programming ( LP ) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships. More formally, Linear Programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Given a polytope and a real-valued affine function defined on this polytope, a Linear Programming method will find a point on the polytope where this function has the smallest (or largest) value if such point exists, by searching through the polytope vertices. Linear programs are problems that can be expressed in canonical form: where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients and A is a (known) matrix of coefficients. The expression to be maximized or minimized is called the objective function ( c T x in this case). The equations A x ≤ b are the constraints which specify a convex polytope over which the objective function is to be optimized. (In this context, two vectors are comparable when every entry in one is less-than or equal-to the corresponding entry in the other. Otherwise, they are incomparable.) Linear Programming can be applied to various fields of study. It is used most extensively in business and economics, but can also be utilized for some engineering problems. Industries that use Linear Programming models include transportation, energy, telecommunications, and manufacturing. It has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design. History The problem of solving a system of linear inequalities dates back at least as far as Fourier, after whom the method of Fourier-Motzkin elimination is named.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Operations Research

  A Practical Introduction

  • Michael Carter, Camille C. Price, Ghaith Rabadi(Authors)
  • 2018(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  2 Linear Programming 2.1      The Linear Programming Model

  Linear Programming is a special class of mathematical programming models in which the objective function and the constraints can be expressed as linear functions of the decision variables. As with the more general mathematical programming models, the decision variables represent quantities that are, in some sense, controllable inputs to the system being modeled. An objective function represents some principal objective criterion or goal that measures the effectiveness of the system (such as maximizing profits or productivity, or minimizing cost or consumption). There is always some practical limitation on the availability of resources (time, materials, machines, energy, or manpower) for the system, and such constraints are expressed as linear inequalities or equations involving the decision variables. Solving a Linear Programming problem means determining actual values of the decision variables that optimize the objective function, subject to the limitations imposed by the constraints.

  The use of Linear Programming models for system optimization arises quite naturally in a wide variety of applications. Some models may not be strictly linear, but can be made linear by applying appropriate mathematical transformations. Still other applications are admittedly not at all linear, but can be effectively approximated by linear models. The ease with which Linear Programming problems can usually be solved makes this an attractive means of dealing with otherwise intractable nonlinear problems.

  In the following section, we will see examples of the wide variety of applications that can be modeled with Linear Programming. In each case, the first task will be to identify the controllable decision variables xi

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Optimization

  Algorithms and Applications

  • Rajesh Kumar Arora(Author)
  • 2015(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  93 4 Linear Programming 4.1 Introduction Linear Programming refers to an optimization problem that has the objec-tive and the constraints as a linear function of the design variables. The con-straints could be of an equality or inequality type or both. Mathematically, a linear function satisfies the following properties: f ( x + y ) = f ( x ) + f ( y ) (4.1) f ( kx ) = kf ( x ) (4.2) where x and y are the variables and k is a scalar. A practical linear program-ming problem (LPP) might contain hundreds of design variables and con-straints and thus require special solution techniques that are different from the methods that were described in the previous chapters. A number of applications of LPP can be found in the literature, some of which include • An airline company would like to assign crews to different flights in an optimal way so that total cost is minimized while covering its entire network. • In a portfolio optimization problem, an investor would like to know the investment allocation to different assets that would maximize the return. • An oil company blends different qualities of oil to produce differ-ent grades of gasoline, which need to be shipped to users who are located in different places. The quantity of gasoline that can be pro-duced is fixed at a certain maximum and so is the input oil quantity. The company would like to maximize its profit. • A company produces a number of products and this requires a num-ber of processes on different machines. The profit from each prod-uct is known and the maximum time available for each machine 94 Optimization: Algorithms and Applications is fixed. The company would like to determine the manufacturing policy that would maximize its profit. • A government-run bus company has to cover different places in a metro city. As a government company, it has an obligation to cover all parts of the city, irrespective of whether a particular route is prof-itable or not.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Mathematics Old and New

  • Saul Stahl, Paul E. Johnson(Authors)
  • 2017(Publication Date)
  • Dover Publications

    (Publisher)

  Chapter 5

  Linear Programming

  Outside of the physical sciences and the discipline of statistics, the most popular of mathematical applications is the topic of Linear Programming. This tool can be used wherever decisions are to be made that need to take into account the limited nature of all resources and the inevitability of competing requirements. It was developed by George B. Dantzig (1914–2005) during World War II in order to resolve the huge distribution problems faced by the armed forces in trying to keep the several fronts supplied with men, weapons, and supplies. The various examples and exercises of this chapter should convince the student of the wide range of applications of this tool.

  5.1 Graphing Inequalities

  We begin with the discussion of a problem that will motivate some definitions.

  Example 5.1.1. A small company produces chairs and full length sofas. The production of a chair requires 6 man-hours and the materials cost $30. The production of a sofa requires 10 man-hours and the materials cost $80. The company has 120 man-hours and a budget of $870 available each week. If the profit per chair is $45 and the profit per sofa is $80, how many of each should be produced so as to maximize the weekly profit?

  Let x denote the number of chairs and y the number of sofas to be produced. In terms of these variables the profit is

  The problem calls for finding those x and y that result in the largest possible profit, subject to the constraints of limited labor and limited budget. Specifically, x and y are constrained by the following inequalities:

  Labor: 6x + 10y ≤ 120

  Budget: 30x + 80y ≤ 870.

  These elements are common to all Linear Programming problems. There is always a function that needs to be maximized (or minimized, as is the case when, say, the focus is on costs). This is called the objective function. There are also inequalities that delimit the variables on which the objective function depends. These are the constraints. Mathematical problems with such objective functions and constraints are called optimization problems and are in general very difficult. Linear programs are those optimization problems whose objective functions and constraints happen to be linear

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Basic Business Analysis and Operations Research

  • R H Mole(Author)
  • 2013(Publication Date)
  • Butterworth-Heinemann

    (Publisher)

  C h a p t e r 6 Linear Programming Essential theory The term linear programme' is given to a particular type of constrained optimization problem. It is assumed explicitly that there is a linear form of objective; say minimize the raw material costs of production, or maximize the contribution of some activity to overheads and profit. It is also explicitly assumed that the optimization of the objective function is subject to linear constraints. Constraints result from a multitude of factors. A constraint may be due to scarce resources such as a restriction upon working capital, or a contractual obUgation to supply a certain quantity of product. The simplest linear programme has the form. Maximize ζ = hxx + ¿?2-^2 + . . · + Subject to a i j J C i + «1,2^2 + . · . + < = Ci forxi> = 0 X2>= 0 . . . Xn>= 0 There are η main variables, sometimes called decision variables. There are m linear inequality constraints which are written such that the left-hand sides are less than or equal to the non-negative right-hand side values (ci in the ith inequality). The main variables Xj for y = 1,2, . . . ,Λ are subject to explicit non-negativity restrictions, but it is important to appreciate the convention that these are excluded from the count of m linear constraints per se. On occasion the constraints are mixed, i.e. include hnear equality constraints, and hnear inequality constraints where the left-hand side exceeds the non-negative right. These features are discussed later. Consider the following numerical example, which is deliberately chosen for simpUcity rather than reaUsm. A division of a company manufactures two main products, type 1 and 2. The number of 81 82 Linear Programming 500 Figure 6.1 Constraints of PI items produced per period is Χχ and X2 respectively.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Quantitative Techniques in Business, Management and Finance

  A Case-Study Approach

  • Umeshkumar Dubey, D P Kothari, G K Awari(Authors)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Programming is a process or procedure to be carried out in a systematic and predetermined way to achieve an objective. It is an activity that passes through a series of logical sequences under a set of condition to reach a particular goal.

  7.2.2 Definition of LPP

  Linear Programming, one of the techniques of operations research, has been applied to a wide range of business and economic problems. It is a technique for determining an optimum schedule of interdependent activities in view of available resources. LPP is also useful in solving problems in finance, budgeting and investment.

  Mathematician Kohlar has defined Linear Programming as a method of planning and operation, involved in the construction of a model, of a real situation, containing the following elements:

  1. Variables representing the available choices
  2. Mathematical expressions
  3. Relation of the variables to the controlling conditions
  4. Reflection of the criteria to be used in measuring the benefits derivable from each of several possible plans
  5. Establishment of the objective

  7.2.3 Features of LPP

  1. The relationship between variables is linear.
  2. The objective function should be linear in its variable.
  3. The equation or inequation which represents the limitation of resources is also linear.
  4. Mathematic techniques are designed, developed and operated on mathematical principle.
  5. The programme is optimised.
  6. Concern is optimised by minimising some quantity and maximising some quantity.
     1. Minimising quantities = cost, expenses, losses and so forth
     2. Maximising quantities = profit, sale
  7. It deals with interdependent activity and can influence the behaviour of other elements.
  8. Restrictions or constraints exist in the problem to some extent.
  9. It deals only with quantitative elements.

  7.2.4 Importance of LPP

  Linear Programming technique is extensively used in management, administration, trade and industry. Its uses are so extensive that wherever there is a need for planning under uncertainty, choosing the best course of action from various alternatives, Linear Programming is applied. With the development of scientific management, managers started exploring new techniques to maximise returns and minimise costs. This policy of modern management made Linear Programming an important technique in business. Its importance as a technique can be studied in the following areas.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Spreadsheet Modeling &amp; Decision Analysis

  A Practical Introduction to Business Analytics

  • Cliff Ragsdale(Author)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Constraints impose restrictions on the values that can be assumed by the decision variables and define the set of feasible options (or the feasible region) for the problem. Linear Programming (LP) problems represent a special category of MP problems in which the objective function and all the constraints can be expressed as linear com-binations of the decision variables. Simple, two-variable LP problems can be solved graphically by identifying the feasible region and plotting level curves for the objective function. An optimal solution to an LP problem always occurs at a corner point of its feasible region (unless the objective function is unbounded). Some anomalies can occur in optimization problems including alternate optimal solutions, redundant constraints, unbounded solutions, and infeasibility. 2.13 References Bazaraa, M. and J. Jarvis. Linear Programming and Network Flows . New York: Wiley, 1990. Dantzig, G. Linear Programming and Extensions . Princeton, NJ: Princeton University Press, 1963. Eppen, G., F. Gould, and C. Schmidt. Introduction to Management Science . Englewood Cliffs, NJ: Prentice Hall, 1993. Shogan, A. Management Science . Englewood Cliffs, NJ: Prentice Hall, 1988. Winston, W. Operations Research: Applications and Algorithms . Belmont, CA: Duxbury Press, 1997. Questions and Problems 1. An LP model can have more than one optimal solution. Is it possible for an LP model to have exactly two optimal solutions? Why or why not? 2. In the solution to the Blue Ridge Hot Tubs problem, the optimal values for X 1 and X 2 turned out to be integers (whole numbers). Is this a general property of the solu-tions to LP problems? In other words, will the solution to an LP problem always consist of integers? Why or why not? 3. To determine the feasible region associated with less than or equal to constraints or greater than or equal to constraints, we graphed these constraints as if they were equal to constraints.

  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)

  assignment problem.

  5.2  LP: Introduction 5.2.1  LP: Definition, Concepts, and Assumptions

  One can define LP as a technique that, given a linear objective function in n variables and m linear inequality constraints with the same variables, helps find nonnegative values of these variables which will satisfy the constraints and optimize the objective function. This definition suggests that the LP technique employs a mathematical model to represent the optimization problem. It also suggests that the objective function and the constraints are expressed as linear functions. It should be noted that the word “programming” in LP does not connote computer programming. Instead, it stands for “planning”in other words, for “planning of activities.”

  The above definition of the LP technique implies that a LP problem possesses three important ingredients. The first ingredient is that, as in the classical approach, any LP problem has an objective function to be optimized. One difference between the classical optimization approach and the LP optimization approach is that in the former the objective function may or may not be linear, while in the latter it is strictly linear. The second important ingredient of a LP problem is that, again like a classical constrained optimization problem, it involves one or more constraints. But, the constraints in the former are, like the objective function, also linear. Moreover, these constraints are in the form of inequalities, while they are equalities in classical constrained optimization problems. The third important ingredient of the LP technique is that it, in most cases, gives the optimal solution(s) for the choice variables (also called decision variables). But, a condition imposed is that the optimal values of the choice variables be nonnegative. Although classical optimization may also give an optimal solution to a constrained optimization problem, it does not impose the just mentioned nonnegativity constraint or nonnegativity condition

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Farm Managerial Economics

  • Kumar, K Nirmal Ravi(Authors)
  • 2021(Publication Date)
  • Daya Publishing House

    (Publisher)

  However, this technique is based on the certain assumptions. We know, an assumption is a simplifying condition taken to hold true in the system being analyzed in order to render the model mathematically tractable (solvable). The following are the important assumptions of LP technique: Linearity: As mentioned earlier, the objective function that the farmer seeks to optimize ( i.e. , maximize or minimize) is linear and can be represented graphically by straight lines. This linearity applies to constraint inequalities as well, since the addition of slack and surplus variables convert all inequalities into linear equations. So, linearity implies, the objective function ( i.e. , maximization or minimization) can be described by a linear function of the decision variables. That is, the mathematical function involves only the first powers of the variables (3X 1 , 5X 1 ) and with no cross products (say, 3X 1 *5X 1 ). ? Constraints set or Functional constraints: The constraints set can be expressed as a set of linear equations. In addition to the linear requirements, non-negativity condition state that, the variables cannot assume negative values, as negative quantity of resources and output does not have a meaning. Proportionality: The contribution of any decision variable to the objective function is proportional to its value. That is, the contribution to the objective function from each decision variable is proportional to the value of the decision variable. This contribution is assumed constant and independent of the variable level. Similarly, the use of each resource per unit of each decision variable is assumed constant and independent of variable level. Thus, there are no economies of scale. For example, in the profit maximization problem, the contribution from one unit of paddy area towards profit This ebook is exclusively for this university only. Cannot be resold/distributed. maximization is Rs. 60, from two units of paddy area towards profit maximization is Rs.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Finite Mathematics

  • Stefan Waner, Steven Costenoble(Authors)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  In that example it would also be natural to ask which of the various possibilities gives the company the largest profit. This is a kind of problem known as a Linear Programming problem (commonly referred to as an LP problem). Linear Programming Problems in Two Unknowns A Linear Programming (LP) problem in two unknowns x and y is one in which we are to find the maximum or minimum value of a linear expression ax 1 by , called the objective function , subject to a number of linear constraints of the form cx 1 dy # e or cx 1 dy $ e . The solution set of points 1 x , y 2 satisfying all constraints is called the feasible region for the problem, the largest or smallest value of the objective function is called the optimal value , and a pair of values of x and y that gives the opti-mal value constitutes an optimal solution . Quick Example 1. Maximize p 5 x 1 y Objective function subject to x 1 2 y # 12 2 x 1 y # 12 s Constraints x $ 0, y $ 0. See Example 1 for a method of solving this LP problem (that is, finding an optimal solution and value). To solve LP problems, we use the following result. Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-300 350 Chapter 5 Linear Programming Let’s use this to solve an LP problem, and then we’ll discuss why it’s true. Solving a Linear Programming Problem Maximize p 5 x 1 y subject to x 1 2 y # 12 2 x 1 y # 12 x $ 0, y $ 0. Solution We begin by drawing the feasible region for the problem. We do this using the techniques of Section 5.1, and we get Figure 17. The feasible region is bounded and nonempty, so the first part of the Fundamental Theorem of Linear Programming tells us that the problem has an optimal solution. Each feasible point (point in the feasible region) gives an x and a y satisfying the constraints.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Optimal Decisions

  Principles of Programming

  • Oskar Lange(Author)
  • 2014(Publication Date)
  • Pergamon

    (Publisher)

  This follows from the assumption of the linearity of the objective func-tion; only linear transformations of the objective function maintain its linearity. In other words, the only permissible transformations of the objective function consist in changing the unit of measurement and in changing the zero point. 9 The use, in this case, of an arbitrary mono-tonic transformation which retains the extreme points will cause the programme to transcend the scope of Linear Programming. In this way, the application of Linear Programming is limited to situa-tions in which the degree of realization of the objective is measurable, in contrast to marginal programming, in which it is sufficient that the various degrees of realization of the objective can be arranged in order of sequence. This can be expressed in yet another way. In linear pro-gramming problems it is necessary for the degree of realization of the objective to be a quantity and in marginal programming it is suffi-cient for it to be a magnitude. 10 4. The simplex method It follows from the basic theorem of the theory of linear program-ming, demonstrated in the preceding section, that the optimal solution of the Linear Programming problem, defined by conditions (4.1), (4.2) and (4.3), can be written as (4 0 ) ,4°U.,4, 0 ) ,0,0,...,0), (4.10) where x ( ° χψ ..., x ( n 0) are positive. Geometrically this means that the optimal solution is given by the co-ordinates of one of the vertexes of the polyhedron of feasible solu-tions. 9 The object is then to transform function f(x i9 x 2 , .-.,*n) into function g = F[f(x x ,x 29 ..., x„)] according to formula g(xi , x 2 ,..., x n ) = A+Bf(x l , x 2 , ..., x n ). Multiplying function/by B we change its scale, i.e. the unit of measure-ment in which the values of function /are expressed. Adding constant A, we change the point of reference, i.e.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Agricultural Production Economics in 2 Vols.

  • Kumar, K Nirmal Ravi(Authors)
  • 2021(Publication Date)
  • Daya Publishing House

    (Publisher)

  Cannot be resold/distributed. The constraint for the manpower is, 3X 1 +2X 2 ≤ 40 Since the resources are to be used within or below the daily availability level, inequality sign of less than or equal sign (≤) is used. Further, we cannot produce negative number of units of biscuits which is a non-negative constraint expressed as, X 1 ≥ 0, X 2 ≥0 Thus, the LP model for the given problem is, Maximize Z = 3X 1 + 2X 2 Subject to constraints, 100X 1 + 115X 2 ≤150 10X 1 +12X 2 ≤15 3X 1 +2X 2 ≤ 40 where X 1 ≥0, X 2 ≥ 0 III. Assumptions in LP Technique Since, the objective function (maximization of profits or minimization of costs) that the farmers seek to optimize as well as the constraints that they face are often linear over the relevant range of operation, LP technique is very useful. However, this technique is based on the certain assumptions. We know, an assumption is a simplifying condition taken to hold true in the system being analyzed in order to render the model mathematically tractable (solvable). The following are the important assumptions of LP technique: Linearity : As mentioned earlier, the objective function that the farmer seeks to optimize (i.e., maximize or minimize) is linear and can be represented graphically by straight lines. This linearity applies to constraint inequalities as well, since the addition of slack and surplus variables convert all inequalities into linear equations. So, linearity implies, the objective function (i.e., maximization or minimization) can be described by a linear function of the decision variables. That is, the mathematical function involves only the first powers of the variables (3X 1 , 5X 1 ) and with no cross products (say, 3X 1 *5X 1 ). Constraints set or Functional constraints : The constraints set can be expressed as a set of linear equations. In addition to the linear requirements, non-negativity condition state that, the variables This ebook is exclusively for this university only. Cannot be resold/distributed.

  Sign up to read

  Learn more about book