Formulating Linear Programming Problems

12 Key excerpts on "Formulating Linear Programming Problems"

• 

  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
• 

  No longer available |Learn more

  Applied Linear Algebra and Optimization Using MATLAB

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

    (Publisher)

  Chapter 6 Linear Programming 6.1 Introduction In this chapter, we give an introduction to linear programming. Linear Programming (LP) is a mathematical method for finding optimal solutions to problems. It deals with the problem of optimizing (maximizing or min- imizing) a linear function, subject to the constraints imposed by a system of linear inequalities. It is widely used in industry and in government. His- torically, linear programming was first developed and applied in 1947 by George Dantzig, Marshall Wood, and their associates in the U.S. Air Force; the early applications of LP were thus in the military field. However, the emphasis in applications has now moved to the general industrial area. LP today is concerned with the efficient use or allocation of limited resources to meet desired objectives. Before formally defining a LP problem, we define the concepts linear function and linear inequality. 653 654 Applied Linear Algebra and Optimization using MATLAB Definition 6.1 (Linear Function) A function Z (x 1 , x 2 , . . . , x N ) of x 1 , x 2 , . . . , x N is a linear function, if and only if for some set of constants c 1 , c 2 , . . . , c N , Z (x 1 , x 2 , . . . , x N ) = c 1 x 1 + c 2 x 2 + · · · + c N x N . For example, Z (x 1 , x 2 ) = 30x 1 + 50x 2 is a linear function of x 1 and x 2 , but Z (x 1 , x 2 ) = 2x 2 1 x 2 is not a linear function of x 1 and x 2 . • Definition 6.2 (Linear Inequality) For any function Z (x 1 , x 2 , . . . , x N ) and any real number b, the inequalities Z (x 1 , x 2 , . . . , x N ) ≤ b and Z (x 1 , x 2 , . . . , x N ) ≥ b are linear inequalities. For example, 3x 1 + 2x 2 ≤ 11 and 10x 1 + 15x 2 ≥ 17 are linear inequalities, but 2x 2 1 x 2 ≥ 3 is not a linear inequality. • Definition 6.3 (Linear Programming Problem) An LP problem is an optimization problem for which we do the following: 1. We attempt to maximize or to minimize a linear function of the de- cision variables.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Optimization for Chemical and Biochemical Engineering

  Theory, Algorithms, Modeling and Applications

  • Vassilios S. Vassiliadis, Walter Kähm, Ehecatl Antonio del Rio Chanona, Ye Yuan(Authors)
  • 2021(Publication Date)
  • Cambridge University Press

    (Publisher)

  PART III Formulation and Solution of Linear Programming (LP) Problems 10 Introduction to LP Models The third part of this book is dedicated to the formulation and automated compu- tation of LP problems. The focus on LP formulations is explained by the following practical observations: 1. Formulating LP problems is a very good point at which to start learning how to transform problem descriptions into mathematical programming (equation- based) form. 2. LP problems find wide applications in many enterprise sectors, e.g. industry, commerce, finance. 3. Most real-world models, even of very large scale, are not entirely nonlinear. In fact, large-scale problems contain large linear constraint sections. 4. The applications chosen in this Part of the book are of vital importance in many situations and will almost invariably, in one form or another, be part of applied optimization problems, even nonlinear ones. 10.1 GENERAL LP PROBLEM MODEL Linear programming solves, under certain assumptions and conditions, the problem of allocating finite resources (e.g. workers, materials, machines, land) between alter- native and competitive with each other activities (e.g. product manufacture, service provision) in an optimal way. The level of each activity is to be chosen such as to optimize the result: e.g. profit maximization or cost minimization of all the activities simultaneously. Finiteness of resources also implies that there are constraints on their levels, as well as constraints on the qualities of the products produced, and there may also be other organizational or managerial constraints, depending on the model. A general LP formulation is as follows: min x or max x z = n  j =1 c j x j subject to: n  j =1 a ij x j (≤, =, ≥) b i i = 1, 2, . . . , m (10.1) x L j ≤ x j ≤ x U j j = 1, 2, . . . , n 115 10 Introduction to LP Models Alternatively, we may write the problem in vector format: min x or max x z = c T x subject to: a i  row i · x (≤, =, ≥) b i i = 1, 2, .

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Operations Research

  Operations Research: Theory and Practice

  • N.V.S Raju(Author)
  • 2019(Publication Date)
  • CRC Press

    (Publisher)

  2 Chapter

  Formulation of Linear Programming Problems

  Chapter Outline

      2.0  Introduction

      2.1  Formulation

      2.2  Major Assumption of LLP

  Practice Problems Review Questions Objective Type Questions Fill in the Blanks Answers

      2.0  Introduction

  In the previous chapter we have learnt that after collection of relevant data, it is to be translated into appropriate mathematical or Operations Research model. One of such models applied to production and allocations is linear programming in which the variables are linearly related. This process of translation is called formulation. In this chapter we learn how to formulate the Linear Programming Problem (LPP).

      2.1  Formulation

  The formulation of relevant data in Linear Programming Problem (LPP) is carried out in the following four steps :

  Step 1:  

  Selection of decision variables.

  Step 2:  

  Setting the objective function.

  Step 3:  

  Identification of constraint set.

  Step 4:  

  Writing the conditions of variables.

  These are explained as follows:

  Step 1:  

  Selection of Variables:

  In the given data, firstly the variables are to be identified. These are also called decision variables or design variables.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  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)

  2. There must be alternative courses of action, one of which will achieve the objec-tive. For example, the firm may allocate its production resources, like raw materi-als and manufacturing capabilities, to chairs and tables in the ratio of 1:1, 1:2, 2:1 or some other ratio. 171 Linear Programming and Problem Formulation 3. The decision variables must be continuous in nature. That is, the number of chairs and tables to be manufactured is flexible enough to take any non-negative values within a range. 4. Resources must be limited in supply, and achievement of the objective function is restricted by these constraints. That is, the furniture plant has limited manpower and machine-hours available. Hence, the more it allocates for chairs, the fewer tables it can make. The objective and constraints must be linear functions. That is, the manager should be able to express the firm’s objectives and limitations (constraints) in the form of linear mathematical equations or inequalities. For example, suppose a manager has been given resources for use (i.e. available man-hours, quantity of raw material, machine time, etc.). a. The quantity of available resources is known to the manager. b. The objective is to determine the resources required or utilisation to optimise the goal of the firm, which can be profit maximisation, sales maximisation, cost optimisation and so forth. c. This situation requires a search for the variables that affect the objective and are subject to certain constraints. With the help of decision variables, their con-straints, equalities or inequalities can be formed. d. They provide the optimal solution to achieve the objective. 7.2.7 Formulation of LPP Formulation is important because it gives the meaning of the business decision problem. It is used to mean the process of converting the oral description into mathematical expres-sions, which represent the relevant relationships among decision factors, objectives and restrictions on the use of resources.

  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)

  With the help of decision variables, their constraints, equalities or inequalities can be formed. They provide the optimal solution to achieve the objective. 7.2.7 Formulation of LPP Formulation is important because it gives the meaning of the business decision problem. It is used to mean the process of converting the oral description into mathematical expressions, which represent the relevant relationships among decision factors, objectives and restrictions on the use of resources. The general LPP with n decision variables and m constraints can be stated in the following form: Let z be a linear function defined by z = c 1 x 1 + c 2 x 2 +... + c n x n (7.1) x 1, x 2, x 3, …, x n are decision variables. where c j (j = 1, 2, 3, …, n) are constants. Let a ij be an m × n real matrix and let (b 1, b 2, …, b m) be a set of constants such. that a 11 x 1 + a 12 x 2 +... + a 1 n x n ≥ b 1 a 21 x 1 + a 22 x 2 +... + a 2n x n ≥ b 2 a m 1 x 1 + a m 2 x 2 + a mn x n ≥ b m (7.2) and x j ≥ 0, j = 1, 2,..., n (7.3) The problem of determining. (x 1, x 2, …, x n), which makes z minimum or maximum, which satisfies Equations 7.2 and 7.3, is called the general LPP. The linear function z = c 1 x 1 + c 2 x 2 + …+ c n x n is called the objective function of the general linear problem. Equation 7.2 is called the constraints of the general LPP. Equation 7.3 is usually known as the set of non-negative restrictions of the general LPP. Solution: (x 1, x 2, …, x n) real numbers which satisfy the constraints of the general LPP are called a solution. Feasible solution: Any solution to a general LPP which satisfies the non-negative restrictions of the problem is called a feasible solution to the general LPP. Optimum solution: Any feasible solution which optimises (minimises or maximises) the objective function of the general LPP is called the optimum solution. The goal of the linear programming model is to maximise or minimise the objective function

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Operations and Supply Chain Management

  • Roberta S. Russell, Bernard W. Taylor(Authors)
  • 2023(Publication Date)
  • Wiley

    (Publisher)

  683 LEARNING OBJECTIVES After reading this supplement, you will be able to: S14.1 Understand the basic concepts of linear programming. S14.2 Use the linear programming technique to formulate models for different types of operational problems where an objective is maximized or minimized subject to resource constraints. S14.3 Solve linear programming problems graphically. S14.4 Solve linear programming problems using the simplex method. S14.5 Solve linear programming problems with Excel. S14.6 Use sensitivity analysis to see the effect of model changes. S14.1 Basics of Linear Programming LEARNING OBJECTIVE S14.1 Understand the basic concepts of linear programming. One of the quantitative techniques used in Chapter 14 for operations planning and in Chapter 17 for scheduling is linear programming. Linear programming is one of the most widely used and powerful quantitative tools in operations management. It can be applied to a wide variety of different operational problems. Some of the more popular model types and their specific OM applications are described in Table S14.1. Linear programming is a mathematical modeling technique used to determine a level of operational activity in order to achieve an objective, subject to restrictions called con- straints. Many decisions faced by an operations manager are centered around the best way to achieve the objectives of the firm subject to the constraints of the operating environment. These constraints can be limited resources, such as time, labor, energy, materials, or money, or they can be restrictive guidelines, such as a recipe for making cereal, engineering specifica- tions, or a blend for gasoline. The most frequent objective of business firms is to maximize profit—whereas the objective of individual operational units within a firm (such as a produc- tion or packaging department) is often to minimize cost.

  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 - PDF

  Farm Managerial Economics

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

    (Publisher)

  For example, the optimization problem could aim at: Minimizing the costs in the production programme in purchasing three inputs from different sources so that, how much of each input to This ebook is exclusively for this university only. Cannot be resold/distributed. buy subject to constraints on minimum and maximum levels of inputs. Maximizing the profits in the production programme subject to resource (labour and raw materials) constraints. Table 9.2: Formulation of LP Model Involving the Allocation of Resources to Activities (Objective function is to minimize costs with reference to Table 9.4) Formulation of a minimum cost transportation plan determining the amount of goods to transport across each available route subject to constraints on supply availability and demand. Scheduling school buses to minimize the total distance travelled when carrying students. Selecting the product mix in a food processing firm to make best use of machine and labour-hours available, while maximizing the firm’s profit. Selecting the blends of raw materials in feed mills to produce finished feed combinations at minimum cost. Designing the distribution system that will minimize total shipping cost from several warehouses to various market locations. Note that, in solving a constrained optimization problem by LP technique, the most difficult aspect is formulation of the problem in a LP format or framework. After formulating the problem, the actual solution to the problem is then straightforward. Simple LP problems with only a few variables can be easily solved graphically or algebraically. However, for the complex problems involving more number of variables, the use computer software programmes is inevitable. Now, let us proceed to solve LP problems This ebook is exclusively for this university only. Cannot be resold/distributed.

  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)

  Our goal is to determine the values for X 1 and X 2 that maximize the objective in equation 2.5 while simultaneously satisfying all the constraints in equations 2.6 through 2.10. 2.8 The General Form of an LP Model The technique of linear programming is so-named because the MP problems to which it applies are linear in nature. That is, it must be possible to express all the functions in an LP model as some weighted sum (or linear combination) of the decision variables. So, an LP model takes on the general form: MAX (or MIN): c 1 X 1 1 c 2 X 2 1 ? ? ? 1 c n X n 2.11 Subject to: a 11 X 1 1 a 12 X 2 1 ? ? ? 1 a 1n X n # b 1 2.12 ( a k1 X 1 1 a k2 X 2 1 ? ? ? 1 a kn X n $ b k 2.13 ( a m1 X 1 1 a m2 X 2 1 ? ? ? 1 a mn X n 5 b m 2.14 Up to this point, we have suggested that the constraints in an LP model represent some type of limited resource. Although this is frequently the case, in later chapters Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 24 Chapter 2 Introduction to Optimization and Linear Programming you will see examples of LP models in which the constraints represent things other than limited resources. The important point here is that any problem that can be formulated in the preceding fashion is an LP problem. The symbols c 1 , c 2 , . . . , c n in equation 2.11 are called objective function coefficients and might represent the marginal profits (or costs) associated with the decision vari-ables X 1 , X 2 , .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Mathematics NQF3 SB

  TVET FIRST

  • M Van Rensburg, I Mapaling, M Trollope A Thorne(Authors)
  • 2017(Publication Date)
  • Macmillan

    (Publisher)

  154 Module 6 Using mathematical models to investigate linear programming problems Module 6 Learning Outcomes This module will show you how to do the following: • Unit 6.1: Solve linear programming problems by optimising a function in two variables, subject to one or more linear constraints, by numerical search along the boundary of the feasible region – the method for doing this is as follows: • Sketch the given functions within their constraints. • Determine and shade the feasible region. • Complete a boundary search to find the vertices of the feasible region. • Optimise the maximum or minimum from the given objective function. Note: Explicit constraints will be given in all cases. Figure 6.1: Optimising a linear function in two variables are often used in financial forecasting; here we see the feasible region for profit and loss. units R LOSS PROFIT Break-even point Revenue Total cost Break-even analysis Unit 6.1: Optimising a linear function in two variables 6.1.1 Pre-knowledge What do inequalities mean? We know that a linear equation in the form y = ax + q represents only the line cutting the x- and y-axes and doesn’t include the area around it. However, when we are dealing with inequalities, we are referring to the area surrounding a straight line and sometimes also the line itself. We can represent a linear inequality graphically by shading the area surrounding the straight line where the range of values for the inequality is true. We will focus on all possible inequalities ( > , < , ≥ and ≤ ). Greater than ( > ) Everything to the positive side of the line is included but the line itself is excluded (not included) in the region. A dashed line is used to represent a line that is not included. 155 Module 6 Example 6.1 Draw the following inequalities on separate axes: y > x + 4; y > 3; x > 1.

  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)

  a n Table 9.2 : Formulation of LP Model Involving the Allocation of Resources to Activities (Objective function is to minimize costs with reference to Table 9.4 ) Ingredients Contribution by Each Unit of Activity (Product) Max Limit of Ingredients (units) Product 1 Product 2 ... . Product N 1 b 11 b 12 ....... b 1n c1 2 b 21 b 22 ....... b 2n c2 3 b 31 b 32 ....... b 3n c3 . . . . . . . . . . . . J b m1 b m2 ....... b mn c m Contribution to Min Z per unit of activity (product) a 1 a 2 ....... a n This ebook is exclusively for this university only. Cannot be resold/distributed. Many variants can be posed in the formulation of LP problem and this makes the LP technique to apply to a wide variety of settings. For example, the optimization problem could aim at: Minimizing the costs in the production programme in purchasing three inputs from different sources so that, how much of each input to buy subject to constraints on minimum and maximum levels of inputs. Maximizing the profits in the production programme subject to resource (labor and raw materials) constraints. Formulation of a minimum cost transportation plan determining the amount of goods to transport across each available route subject to constraints on supply availability and demand. Scheduling school buses to minimize the total distance travelled when carrying students. Selecting the product mix in a food processing firm to make best use of machine and labor-hours available, while maximizing the firm’s profit. Selecting the blends of raw materials in feed mills to produce finished feed combinations at minimum cost. Designing the distribution system that will minimize total shipping cost from several warehouses to various market locations. Note that, in solving a constrained optimization problem by LP technique, the most difficult aspect is formulation of the problem in a LP format or framework. After formulating the problem, the actual solution to the problem is then straightforward.

  Sign up to read

  Learn more about book