Mathematics
Formulating Linear Programming Problems
Formulating Linear Programming Problems involves defining an objective function and constraints to optimize a linear objective subject to linear equality and inequality constraints. This process requires identifying decision variables, determining the objective to be maximized or minimized, and specifying the constraints that must be satisfied. The goal is to find the optimal solution that maximizes or minimizes the objective function while meeting all constraints.
Written by Perlego with AI-assistance
8 Key excerpts on "Formulating Linear Programming Problems"
Learn about this page
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
eBook - ePubLinear Optimization and Duality
A Modern Exposition
- Craig A. Tovey(Author)
- 2020(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 3Formulating and Solving Linear Programs
Preview: This chapter teaches LP formulation, how to build an LP model that accurately describes the critical elements of a problem. The main steps in model building are: understand and visualize the problem; define index sets and data; define the decision variables; write the objective function as a linear combination of the decision variables; and write the constraints as linear inequalities in the decision variables. This chapter also explains how to interpret the results from LP solver software, and points out features of problems that resist LP formulation.Remember word problems? For example, A and B together can dig a ditch in 20 days. A, working alone, can dig a ditch in 30 fewer days than can B working alone. How long does it take for B to dig a ditch? Linear programming formulation is like word problems. It is a skill different from algebraic manipulation, and it comes naturally to some people. But many others, who are usually good at math, are stumped by formulation problems. If you feel stumped, do not let yourself be fearful or paralyzed. Remember, formulation is a different skill. You can learn it, and I will help you learn it.Questions to ask when formulating are as follows:- What choices do I have? What can I control? This tells you what your decision variables are.
- What is my goal? This tells you your objective function.
- What limits my choices? What is impossible? This tells you your constraints.
- Define index sets first. Use different index variables for different index sets.
- Define the data in full detail, including units.
- Define decision variables in full detail, including units. Choose notation that looks different from the notation for the data. Sometimes I use upper case for data and lower case for variables.
- Separate the data from the model. Some LP modeling languages will force you to make this separation. It may be annoying on small cases, but it is good practice.
- Anindya Ghosh, Prithwiraj Mal, Abhijit Majumdar(Authors)
- 2019(Publication Date)
- CRC Press(Publisher)
linear optimization problem . If either the objective function or the constraints have nonlinearity, then such optimization problems belong to nonlinear optimization. Various algorithms exist to solve these optimization problems. Linear programming (LP) is one of the most popular, versatile, commonly used, and simplest classical optimization techniques to provide an optimal solution for a linear function of decisive variables satisfying linear constraints (Murthy 1983; Sharma 2010; Srinivasan 2014; Taha 1989). This chapter presents a detailed application of methods of LP to deal with linear single-objective optimization problems in textile engineering.6.2 Linear Programming Problem FormulationIn order to solve an LP problem, it is initially essential to formulate the mathematical model of LP. Consequently, the LP can be solved using various methods. To formulate an LP problem, the unknown decisive variables are identified first. Then the objective of the problem, along with the constraint(s) are identified. The objective is put as a linear function of the decisive variables. The constraints are expressed as linear equations or inequations (i.e., inequality equations or equations with the sign ≥ or ≤ ) with the decisive variables. Some simple examples of the formulation of LP problems are as follows.Example 6.1: Example of formulation of a maximization LP problem with inequality constraintsA textile unit produces two types of fabrics of equal width—poplin and canvas. Poplin requires 100 g of cotton yarn per meter, whereas canvas requires 160 g of the same cotton yarn per meter. The minimum demand of poplin in the market is 80 meters per day, whereas the demand for canvas is unlimited. The mill has 12,000 g of cotton yarn available per day in its stock. The profit of poplin is Rs. 10 and that for canvas is Rs. 20. The textile mill would like to plan the production to maximize the profit.
- Kevin J. Hastings(Author)
- 2018(Publication Date)
- Chapman and Hall/CRC(Publisher)
2Linear Programming
Introduction
Mathematical programming is the area of mathematics that is concerned with optimizing an objective function of several variables subject to constraints on those variables. We have already encountered such a problem in Chapter 1 . Consider again the minimal cost spanning tree problem as illustrated by Figure 1.1 . A subgraph of the original communications network can be represented by a matrix A = xi j )i,j= 1, …, n in which xi j = 1 if edge {vi , vj } is in the subgraph and xi j = 0 otherwise. In finding a tree of minimal cost, we are really solving the problem: minimize the total cost of all edges in the subgraph subject to the condition that there is exactly one path in the subgraph from each vertex to each other vertex. Since Ak (i, j) is the number of paths of length k from vi to vj , we see that we can write the problem as:minimize: g (x 11,x 12, … ,x,n , n − 1x) =n n∑i < j∑c ( i , j )xi jsubject to:∑k = 1n − 1A k( i , j ) = 1 for i ≠ j ,x= 0 or 1i jwhere n is the number of vertices and c(i, j) is the cost of edge {νi , νj }.The objective function g is linear in the variables xi j , but the first constraint is highly non-linear, and the second constraint forbids the variables from taking on arbitrary real values in some interval. Both of these conditions make the problem difficult. Fortunately, we developed other techniques for the spanning tree problem.The problems that we will study in this chapter are more tractable, though they are still non-trivial and have wide applications. The underlying idea of the problem is to optimally allocate limited resources. The objective function will be linear, the constraints will be linear, and the variables will usually take values in subsets of the non-negative half of the real line. Such problems belong to the area of mathematical programming called linear programming.The following example is a good illustration. A winery makes three kinds of wine: red, white, and rosé. A gallon of red wine yields a profit of $1.25 and requires 2 bushels of type I grapes, 0 bushels of type II grapes, 2 lbs. of sugar, and 2 labor hours to produce. The corresponding numbers for white wine are $1.50, 0 bushels, 2 bushels, 1 lb., and 1 labor hour, and those for rosé wine are $2, 1 bushel, 1 bushel, 1.5 lbs., and 2 labor hours. If in a week, the winery has available 200 bushels of type I grapes, 150 bushels of type II grapes, 90 lbs. of sugar, and 250 labor hours, then how much of each wine should be made to maximize total profit?
eBook - ePubOperations Research
Operations Research: Theory and Practice
- N.V.S Raju(Author)
- 2019(Publication Date)
- CRC Press(Publisher)
2 ChapterChapter OutlineFormulation of Linear Programming Problems
2.0 Introduction2.1 Formulation2.2 Major Assumption of LLPPractice Problems Review Questions Objective Type Questions Fill in the Blanks Answers2.0 IntroductionIn 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 FormulationThe 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.These are explained as follows:Step 4:Writing the conditions of variables.In the given data, firstly the variables are to be identified. These are also called decision variables or design variables.Step 1:Selection of Variables:
eBook - ePubOperations Research Using Excel
A Case Study Approach
- Vikas Singla(Author)
- 2021(Publication Date)
- CRC Press(Publisher)
2 Linear Programming DOI: 10.1201/9781003212966-2 2.1 Introduction Chapter 1 discussed the importance of OR discipline as a scientific way of solving well-formulated problems, which help to make accurate decisions. The decision-making process by using OR was detailed as involving two steps. The first step deals with formulation of a well-defined problem. It included the identification of problem and alternative solutions. The second step was termed as problem analysis, and it involved model development and solution. Model simulates real problem as accurately as possible so that solution represents the solution accurately. Linear programming (LP) has been considered as an important and effective OR technique, which has the ability to simulate a complex problem through a mathematical model and provide solutions by applying algorithms. It is regarded as one of the major and most significant discoveries in the field of mathematics and problem solving of the last century. The significance of technique increases manifold as it can be used for model development and solution for simple or complex problems, for small or large industry and for any sector whether government or private. The importance gained acceptance with increase in computing power. Complex problems involving number of decision variables and constraint equations would be impossibly hard to solve manually. For instance, profit by selling a product could be a function of price only. However, most likely, there could be other variables such as price of competitor product, distribution costs, and other products in product line, which could estimate profit very difficult. Computers made such solutions easy and more precise
eBook - ePub- Adil H. Mouhammed(Author)
- 2020(Publication Date)
- Routledge(Publisher)
Mathematically, a mathematical linear program is written as Maximize Z = c 1 X 1 + c 2 X 2 + c 3 X 3 +... + c n X n 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[--=PLGO-SEP. ARATOR=--]X n ≤ b m X 1 ≥ 0, X 2 ≥ 0,..., X n ≥ 0 This mathematical model suggests that there are (n) different activities (X 1, X 2,..., X n). These activities (doing something) may take the form of the production of output such as TV sets (X 1), automobile (X 2), corn (X 3), and so forth. Conversely, the model contains the quantities of several economic resources designated by (b 1, b 2,..., b m). For example, (b 1) may be the number of hours available, (b 2) may be the amount of loan that can be obtained to produce a unit of output, and (bm) may be the amount of fertilizer available. The linear programming model is primarily designed for allocating these economic resources to each economic activity in order to achieve a specified goal such as profit maximization, given the knowledge of the coefficients (c j), j = 1,2,..., n; the technological coefficients (a ij); and b i, i = 1, 2,...m. The coefficients of (c j) indicate the contribution of each activity to the objective function. For example, if the objective function is to maximize profit, then (c 1) may be the contribution of one unit of (X 1) to total profit; (c 2) may be the contribution of one unit of (X 2) to total profit; and (c n) may be the contribution of one unit of (X n) to the profit. In other words, each unit of output (X 1), (X 2), and (X n) generates a profit of (c 1), (c 2), and (c n). As can be seen from the model, the objective function is restricted by several linear constraints, each of which describes the resource requirements per unit of output
eBook - ePub- Adil H. Mouhammed(Author)
- 2015(Publication Date)
- Routledge(Publisher)
CHAPTER SEVENLinear 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 asMaximize Z = c1 X1 + c2 X2 + c3 X3 + … + Cn XnSubject toa11 X1 + a12 X2 + … + a1n Xn ≤ b1a21 X1 + a22 X2 + … + a2n Xn ≤ b2a31 X1 + a32 X2 + … + a3n Xn ≤ b3…………………am1 X1 + am2 X2 + … + amn Xn ≤ bm
eBook - ePub- Alan J. Baker(Author)
- 2018(Publication Date)
- Routledge(Publisher)
Chapter 5 the possibilities for experimentation with different settings of chance constraints were discussed), but the point that should be established is that programming techniques are quite neutral on questions of decision criteria and approach. Linear programming in particular adapts readily, not only to the expression of many different problem types, but also to the representation of widely differing decision criteria and procedures.6.2 Operational Applications of Linear Programming
6.2 (i) Introduction
This section describes a number of operational applications of linear programming with the intention of demonstrating both the versatility of LP techniques and the ways in which additional information can usually be extracted from a problem’s optimal solution. No account of LP’s value in decision making would be complete without at least an introduction to the transportation method and its many possible applications, and 6.2 (iii) and 6.2 (iv) attempt to satisfy these minimum requirements.6.2 (ii) Production Mix Problem with Order Size Constraint
The production of shirts involves four processes: cutting, assembly, button-holing/buttoning and inspection/packaging. One company produces three different shirt brands: ‘Westminster’, ‘City’ and ‘Knightsbridge’. The number of minutes of labour time required for one dozen shirts of each brand in each process is as follows:In preparing a production plan for one week, management expects the numbers of man-hours available in the four processes to be 26, 50, 30 and 20 respectively. Labour is not transferable to other uses or dismissible in the planning period, so its cost is treated as fixed. The profit margins (selling price minus variable costs) per dozen shirts are £8, £10 and £7 for brands W, C and K, respectively. Firm orders for a total of 60 dozen shirts of brand C and/or K have been received, and these must be satisfied. Whatever else is produced can be sold or stockpiled for later sale at zero cost. How many shirts of each brand should the company produce in order to maximise its profit?
