Through a compilation of representative linear programming problems, the aim is to develop the inventive capacity to formulate resource optimization problems.
Linear Programming - General Problem
Definition:
Given a set of m linear inequalities or linear equations, with n variables, it is required to find non-negative values of these variables that satisfy the restrictions and maximize or minimize some linear function of the variables called Objective Function.
Mathematically:
Find X J, J = 1, 2,….. n for:
Maximize
or Z = C 1 X 1 + C 2 X 2 +…… + C n X n
Minimize
With the following restrictions:
at 11 X 1 +…… + a 1j X j +…… + a 1n X n ≤ or ≥ b1
a i1 X 1 +…… + a ij X j +….. + a in X n ≤ or ≥ bi
a m1 X 1 +…… + a mj X j +…… + a mn X n ≤ or ≥ bm
X j = 0; j = 1, 2,…… n
Features of Linear Programming
- Linearity assumes that there cannot be terms like this: X 1 X 2, X 3 2 to 14 Log X 4 Assumes additive and multiplicative properties.
- If a type E unit needs 2 hours in Machine A and a type F unit needs 2½ hours, then they both need 4½ hours. If a type E unit needs 1 hour in Machine B, then 10 units need 10 hours.
- The function to optimize (maximize or minimize) is called the objective function, it does not contain any constant term. In the m restrictions, the conditions Xj = 0 (non-negativity condition) are not included. Solutions:
- Any set of Xj that satisfies the m constraints is called a solution to the problem.If the solution satisfies the non-negativity condition Xj = 0, it is called a feasible solution A feasible solution that optimizes the objective function is called an optimal feasible solution
There are usually an infinite number of feasible solutions to the problem, of all these, an optimal one has to be found
Guidelines and comments for modeling
In converting verbal models to formal models, it will be very useful to first describe in words a model that corresponds to the given problem.
You can proceed as follows:
- Express each restriction in words; When doing this, pay careful attention to whether the restriction is a requirement of the form:
≥ (greater than or equal to, at least, at least, at least), ≤ (less than or equal to, not greater than, at most), or
= (equal to, exactly equal to).
- Express the objective in words Verbally identify the decision variables. A useful guide is to ask yourself the question:
What decision must be made to optimize the objective function?. The answer to this question will help to correctly identify the decision variables. Express the objective function in terms of the decision variables. Check the consistency of units. For example, if the coefficients of an objective function Cj are given in S. / per kilo, the decision variables Xj must be in kilos, not tons or ounces. Express the constraints in terms of the decision variables. Check that for each constraint the units on the right side are the same as those on the left side.
Constraints cannot have a strict inequality, with the signs <or>. The reason for this is mathematical in nature.
Formulation of Models
Translate real world problems into mathematical models.
Do not read into a problem more than what is given. For example, do not introduce additional constraints or logical nuances or imaginary data that in your opinion could make the model more realistic.
Download the original file
