Linear programming Definition and 114 Threads

Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization).
More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polytope where this function has the smallest (or largest) value if such a point exists.
Linear programs are problems that can be expressed in canonical form as










Find a vector





x







that maximizes






c


T



x







subject to




A

x



b







and





x



0

.






{\displaystyle {\begin{aligned}&{\text{Find a vector}}&&\mathbf {x} \\&{\text{that maximizes}}&&\mathbf {c} ^{T}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}}
Here the components of x are the variables to be determined, c and b are given vectors (with





c


T




{\displaystyle \mathbf {c} ^{T}}
indicating that the coefficients of c are used as a single-row matrix for the purpose of forming the matrix product), and A is a given matrix. The function whose value is to be maximized or minimized (




x




c


T



x



{\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x} }
in this case) is called the objective function. The inequalities Ax ≤ b and x ≥ 0 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 they have the same dimensions. If every entry in the first is less-than or equal-to the corresponding entry in the second, then it can be said that the first vector is less-than or equal-to the second vector.
Linear programming can be applied to various fields of study. It is widely used in mathematics, and to a lesser extent in business, economics, and for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proven useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.

View More On Wikipedia.org
  1. T

    A Finding dual optimum of a linear problem

    A simple linear problem goes min c'x such that f_i(x)<= 0 and Ax=b x Suppose we make all constraints affine. Then Dx-e<=0 and Ax-b =0 We get the Langrangian function as c'x + λ'(Dx-e) +ν'(Ax-b) and since Ax-b is 0, we reduce L to c'x + λ'(Dx-e) The dual function g is inf L(x,λ) x Then I...
  2. alpha

    Python Solving Linear Programming problems in python PulP

    Okay so far I have come up with the following: The objective function is: 30LADA + 40LAHO + 50SADA + 40SAHO + 110DANY + 125DACH + 105HONY + 115HOCH (to read this please see the table above as I have just used the first two letters of each except NY which I have represented by NY). In these I...
  3. alpha

    Optimizing Constraints for Linear Programming Problem

    So far I have figured out the following: maximize 0.02x1 + 0.01x2 +0.06x3 + 0.07x4 subject to: xi <= 200,000 xi >= 24,000 x3 <= x2 +x4 x1 >= x3 But when I try to solve this in solver, I get an error which means my contraints must be wrong. Any suggestions on what constaints to put?
  4. chwala

    Solve the problem involving linear programming

    Find question and solution here; The initial steps were a bit confusing to me...i decided to use hours instead of minutes ...only then did it become more clear to me. See my graph, Ok i follow that the function would be optimised at ##x=45## and ##y=6.25## ...now to my question...we...
  5. Z

    Linearizing an equation for Mixed-integer linear programming (MILP)

    Summary:: Linearizing an equation for MILP Hi All I have Linear programming problem where I need to linearise the following function: Y = A * log2(1 + (Bx/Cx^2)). where A, B and C are constants. Can you please help or advise?
  6. Z

    Who is Zero and What is Operations Research?

    Hi all My name is Zero and I am a MSc student in Operations Research at The University of Leeds
  7. B

    Is My Linear Programming Model Formulated Correctly?

    I've tried formulating the LP model for the question above and would like to check if I'm doing anything incorrectly. Below is my LP model. Let X1 be the number of one-child family interviewed on weekdays morning Let X2 be the number of one-child family interviewed on weekdays evening Let X3...
  8. V

    Optimizing Resources with Linear Programming: A Step-by-Step Approach

    I am comfortable solving these types of problems, however I am having trouble setting up this problem and am unsure if I am doing this correctly so would someone be able to assist me? I first wrote an equation for the people: 10x +8y +11z. Then I made an equation for the flour: 4x + 12y + 8z...
  9. mertcan

    Linear programming and resolution theorem

    Hi everyone hope you are well, I would like to express what I have done for this question: Proving and employing caratheodory theorem we can say that any point in polyhedron can be expressed as a convex combination of at most n+1 points (where n is the space dimension) in same polyhedron that...
  10. bagasme

    B Solving a Linear Programming Problem which Requires Integer Solutions

    Hello, In grade 11 of high school, I encountered this linear programming problem on my textbook: The "alternative solution" described in the textbook as follows: Let: - ##x## : amount of plant A - ##y## : amount of plant S - ##L## : garden area - ##L_x## : area of garden for one plant A -...
  11. E

    MHB Linear programming - Simplex Method - Stuck with picking the right 'generator'

    Dear All, Thank you for reading my post. I'm stuck with picking the correct 'generator' element in the attached example (Simplex method). As you can see, the solution keeps picking the yellow elements as 'generators', but I don’t understand why we can't choose the purple ones. Can somebody...
  12. A

    I Open source software for integer programming

    I don't usually need help in locating software, but I'm having a heck of a time tracking down a good open-source bit of software which solves integer programming problems using arbitrary precision! If I don't find one soon, I'll need to write it myself. Which I don't mind, but it's silly to...
  13. C

    I Linear Programming: how to identify conflicting equations

    I'm reading about the Simplex method to solve a Linear Program. If a program is rejected as being infeasible, is there a method to identify which equations are causing it to be infeasible and a technique for reducing the program in an optimal way? (I'm not sure what 'optimal' is exactly, but my...
  14. mertcan

    Bland rule proof linear programming

    <Moderator's note: Continued from a technical forum and thus no template. Re-opening has been approved by moderator.> Hi, my question is related to simplex algorithm anticycling rule called Bland's rule. While I was working with the proof in the link...
  15. mertcan

    I Linear programming -- Bland rule degeneracy

    hi, my question is related to a proof involves bland rule for avoiding the degeneracy. Initially I emphasized some sentences which have importance in attachment/file with yellow color. At the beginning, it says xs is entering variable and when it enters objective value does not change( because...
  16. Erenjaeger

    I How Do You Formulate Decision Variables in a Linear Programming Problem?

    I was given the problem attached in the photo below and the first question is to define the decision variables and formulate the problem as a linear program. There are no solutions online, so it would be helpful if someone on the mighty PF could check them to see if they are correct, thanks...
  17. S

    I Linear Program:Multiple Optima for multivariable Obj. Func.?

    I know there can be an infinite number of solutions when the objective function with 2 variables has an equal slope as a constraint's slope (assuming the constraint is affecting the feasible region and not a redundant constraint). How can you know there are multiple optimal solutions for...
  18. S

    A Can this optimization problem be solved?

    Hello, I am working on an optimization problem but I am not sure if the problem can be formulated and solved with conventional solvers. Assume the minimization problem for a set of elements ##\mathcal{N} =\{ 1,\dots, h, \dots, i,\dots, N \}## $$ \mathrm{minimize}\quad C = \sum_{i=1}^{N}...
  19. L

    I Can Linear Programming Handle Combined Item and Shipping Costs Optimization?

    Hi everyone. I am tackling a problem related to the purchase of items that are available from different vendors, and from what I've seen so far it seems to me that it may be solvable by linear programming methods (I'm using R). However I'm not sure how to set up the problem to achieve the exact...
  20. G

    MHB Linear Programming word problems

    a small business makes laptops and notepads. In any given month labour costs must not exceed £1350 and material costs must be a maximum of £1150. Relevant information: Laptops cost £50 in materials to make and labour costs £50, they make £110 profit on each laptop. notepads cost £25 in...
  21. mpoli

    Linear Programming Case Study - Case Problem

    Homework Statement Linear Programming Case Study - Case Problem ( Page # 109 Decision making methods) “The Possibility” Restaurant? In the case problem, Angela and Zooey wanted to develop a linear programming model to help determine the number of beef and fish meals they should prepare each...
  22. evinda

    MHB Is This Solution to the Linear Programming Problem Correct?

    Hello! (Wave) I want to solve the linear programming problem: $\max (5x_1-4x_2) \\ -x_1+x_2 \geq -6 \\ 3x_1-2x_2 \leq 24 \\ -2x_1+3x_2 \leq 9 \\ x_1, x_2 \geq 0$ I have found that the solution is $\left(0, \frac{6}{5}, \frac{36}{5},0, \frac{99}{5} \right)$.. Am I right?
  23. evinda

    MHB Solving Linear Programming Problems Graphically

    The following linear programming problem is given and I want to solve it graphically. $$\max (x-y) \\ x+y \leq 4 \\ 2x-y \geq 2 \\ x,y \geq 0$$ I have drawed the lines : $$(\ell_1) x+y=4 \\ (\ell_2) 2x-y=2 \\ (\ell_3) x=0 \\ (\ell_4) y=0$$ as follows: I have drawed the line $2x-y=0$ taking...
  24. M

    LP objective function with unknown parameters

    Hi All, I am struggling with minimization(maximization) problems which needs to be solved graphically but they have unknown parameter in objective function: For example: f = 2x_1 + \lambda x_2(min) for conditions: -x_1 + x_2 \leq 3 x_1 + 2x_2 \leq 12 3x_1 -x_2 \leq 15 x_i \geq 0 More than...
  25. evinda

    MHB Exploring Canonical Form of Linear Programming

    Hello! (Wave) A linear programming problem is in canonical form if it's of the following form: $$\pm \max (c_1 x_1+ \dots + c_n x_n) , c_1, \dots, c_n \in \mathbb{R} \\ Ax=b, A \in F^{m \times n}, x=\begin{bmatrix} x_1\\ \dots\\ \dots \\ x_n \end{bmatrix}, b=\begin{bmatrix} b_1\\ \dots\\...
  26. evinda

    MHB What is the maximum of the given function in the closed square $D$?

    Hello! (Wave) We consider the function $f(x_1,x_2)=x_1+x_2$ and the (closed) square $D$ with edges $(0,0), (1,0), (1,1), (0,1)$. Check if $f$ has a maximum in $D$ and if so, find the points of $D$ at which this maximum is achieved.$$\max_{(x_1,x_2) \in D} (x_1+x_2)$$...
  27. S

    Piecewise Linear Programming with Multiple Functions

    Dear Friends I have a question about linear programming. It would be great to have your comments or suggestions. Consider the followings \begin{equation} \\ Y = [y_{1}, y_{2}, \cdots, y_{n}] \\ G = [g_{1}, g_{2}, \cdots, g_{n}] \\ \textbf{X} = \begin{pmatrix} 0 & x_{1,2} & \cdots & x_{1,n}...
  28. S

    MHB Linear programming problem (simplex algorithm)

    Can anyone help me to solve that problem ? I would really appreciate For the linear programming problem P1 : Max z = 2 + x1 - 2x4 x2 = 1 - x4 x3 = 0 - x1 - x4 xi \ge 0 1 \le i \le 4 Question 1 : Explain why the writing of that linear programming in the form proposed above...
  29. Y

    MHB Solve Linear Programming: Find Max Value & Calculate Bounds

    Hello all, I hope I am in the right forum, I have a question regarding linear programming (optimization). I have this target function: \[Z=0.045X+0.06Y-2\] subject to the following constraints: 1. \[X+Y\leqslant 500\] 2. \[X\geqslant 0.2(X+Y)\] 3. \[Y\geqslant 0.5(X+Y)\] 4. \[X\leqslant...
  30. H

    MHB Linear Programming Formulation problem faced - Maximization problem

    Hi All. I am new here and I faced some issues in formulating the objective functions and constraints for the following scenario. Could any kind souls assist in giving me some advices on how I can proceed to do so? Company Y is producing two different cookies; S cookies and E cookies. The...
  31. W

    Linear Programming - satisfaction only at least one constraint

    Linear Programming - satisfaction of only at least one constraint Hi Is there a form of relaxation/modification of an LP of the form \text{min }\;\;f^\mathsf{T}x\\\mathbf{A}x\leq b such that if only anyone of the constraints is satisfied, then the solution ##x## is regarded as feasible...
  32. J

    How Does Car Type and Investment Limit Affect Dealership Profit Maximization?

    Homework Statement A manager of an automobile dealership must decide how many cars to order for the new model year in order to maximize his profit. There are two types of cars: midsize cars and compact cars. The selling price and costs are listed in the following table: Car type -- Selling...
  33. T

    How can I use linear programming to distribute S into two bins?

    I have a problem at work I'm trying to solve and I can't figure out a good way to do it, hoping someone might be able to help. I have put the relevant info in the below pastebin. Basically I want to distribute some amount of S into two bins, one of which is split into smaller bins, in such a way...
  34. A

    MHB How to Set Up a Linear Programming Problem in Excel?

    Hello everyone, I am stuck on the problem given below. I am know how to set this problem algebraically but I am having a hard time setting up this problem in excel. This is the problem: I would really appreciate if you guys help me. Thank you! :D
  35. T

    MHB Linear programming duality

    I have an hour to solve this problem. I have calculated the duality of linear problem. My question is,whats the range i can change some values,so the optimal solution stay as it is? Is there an easy way to calculate it? Thanks to all!
  36. E

    MHB Linear Programming formulation problem

    Hello evryone :) Is there someone who can help mi in formulating two LP models (Thinking) ? Example 1 The Finnish company Suomi Oy produces three products A, B and C. For this, 2 types of raw materials are used (I and II ). There are 5000 units of I and 7500 units of II available. See the...
  37. D

    Linear programming - convex analysis

    Homework Statement Given 2 problems: (P1) min min(##x_1,x_2##) s.t ##x_1, x_2 \geq 0## (P2) min t s.t ##t \leq x_1## ##t \leq x_2## ##x_1, x_2 \geq 0## (i) Is the mapping f(##x_1,x_2##)=min(##x_1,x_2##) convex? (ii) What are the objectives of (P1) and (P2)? Homework Equations The...
  38. S

    Mathematical formulation of Linear Programming Problem

    A ship has three cargo loads -forward, centre and after. The capacity limits are given: Commodity Weight (in tonne) Volume (in cu. feet) Forward 2000 100000 Centre 3000 135000 After 1500 30000 The following cargoes are offered. The ship owner may accept all or any part of each commodity...
  39. M

    MHB Solutions of the given linear programming problem

    Hello! :o Given the following linear programming problem $$\min(2x + 3y + 6z + 4w)$$ $$x+2y+3z+w \geq 5$$ $$x+y+2z+3w \geq 3$$ $$x,y,z,w \geq 0$$ I am asked to find all the solutions using the simplex method. To solve this problem we use the Two-Phase method, don't we? Then I found that there...
  40. S

    MHB Linear Programming using Graphing Calculator

    My daughter needs serious help with Linear Programming using Graphing Calculator. She has a problem she has been trying to solve for over a month, I have tried to help her and searched endlessly for help. Hopefully, the link below works. Everything comes up fine except for the very last part...
  41. S

    Concavity of f(c) in Linear Programming

    Homework Statement Let c in R^n be a parameter and consider the following function of c: f(c)= minimize cx subject to Ax=b x>/= 0 where x is an n-dimensional decision vector, A is an mxn matrix, and b is an m-dimensional constant. The function f(c) is determined by...
  42. E

    Linear Programming Exam Question

    Homework Statement Here is the stated problem: MSA computer corporation manufactures two computer system. Alpha 4 and Beta 5. The firm employs five technicians working 160 hours per month. Management insists on no overtime next month (less than or equal to 160 hours).20 hours labour is...
  43. T

    Linear Programming Mixture Problem

    Homework Statement Hi, I am having a problem with this particular type of problem. I am just so confused that I don't even know how to attempt these types of problems. Can someone please explain to me how to work with mixture problems.
  44. P

    MHB Linear Programming Problem using the Simplex Method

    Here is my story problem: An electronics store stocks VCRs, stereo systems, and television sets. They have limited storage space and can stock a total of at most 210 of these three machines. They know from past experience that they should stock twice as many VCRs as stereo systems and at least...
  45. U

    How Can Linear Programming Optimize Seating Capacity Within a Budget?

    Ok, so ill start this off with this, I don't know a whole lot about math. I do however have a question that I am pretty sure someone on these forums can help me out with. What I am looking for is an equation that I can later plug different numbers into. Lets say you have $1,000,000...
  46. A

    Linear programming: How to find extreme points and extreme directions?

    Hi guys I'm reading a book about linear programming and network flows. In chapter 2 when it talks about convex sets and their analysis it talks about extreme points and extreme directions of a convex set. I understand the definitions of extreme points and extreme directions, but I don't know...
  47. A

    MHB Linear Programming using the simplex method

    Southwestern Oil supplies two distributors in the Northwest from two outlets. S1 and S2. Distributor S1 needs at least 3000 barrels of oil, and D2 needs at least 5000 barrels. The two outlets can each furnish exactly 5000 barrels of oil. The cost per barrel to ship the oil are:S1: D1=$30...
  48. A

    MHB Linear Programming using the simplex method

    The Chemistry department at a local college decides to stock at least 900 small test tubes and 600 large test tubes. It wants to buy at least 2700 test tubes to take advantage of a special price. Since the small test tubes are broken twice as often as the large, the department will order at...
  49. A

    How to solve this Linear Programming problem graphically

    Homework Statement Solve the following LP problem GRAPHICALLY Minimise -x1+x2 subject to constraints x1+x2 >=1, x1+2x2<=8, x1-x2<=5, x1>=0, x2>=0. a)by sketching the feasible set b)finding...
Back
Top