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.
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...
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...
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?
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...
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?
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...
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...
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...
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
-...
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...
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...
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...
<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...
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...
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...
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...
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}...
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...
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...
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...
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?
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...
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...
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\\...
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)$$...
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}...
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...
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...
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...
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...
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...
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...
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
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!
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...
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...
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...
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...
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...
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...
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...
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.
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...
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...
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...
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...
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...
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...