# What is Linear programming: Definition and 114 Discussions

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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### 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. ### Linear programming question: Solve this using the two phase method

Simplex method
13. 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...
14. ### 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...
15. ### 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...
16. ### 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...
17. ### 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...
18. ### 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...

27. ### 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)$$...
28. ### 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 \\ 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}...
29. ### 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...
30. ### 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...
31. ### 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...
32. ### 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...
33. ### 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...
34. ### 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...
35. ### 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
36. ### 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!
37. ### 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...
38. ### 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...
39. ### 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...
40. ### 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...
41. ### 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...
42. ### 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...
43. ### 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...
44. ### 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.
45. ### 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...

49. ### 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...
50. ### 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...