Linear programming is a general model that can be used to solve problems of allocating limited resources optimally, including planning activities to achieve an "optimal" result, namely a result that reflects the achievement of a certain target that is best (according to a mathematical model) among several possible alternatives, by using linear functions.
Getting to Know Linear Programming
Linear Programming Models
The mathematical model for formulating the general problem of allocating resources for various activities, in the LP model two types of functions are known:
1. Objective Function
Is a function that describes the goal/target in LP problems related to optimal arrangement of several resources, to obtain maximum profit or minimum cost. The optimized value is expressed as Z.
2. Constraint Function
It is a form of mathematical presentation of the limitations of available capacity that will be allocated optimally to various activities.
To facilitate the discussion of this LP model, the following symbols are used:
- m = various limitations of available sources or facilities.
- n = types of activities that use these resources or facilities.
- i = number of each type of source or facility available (i = 1, 2, 3, ...,m).
- j = number of each type of activity that uses available resources or facilities (j = 1, 2, 3, ..., n).
- xj = activity level j (j = 1, 2, 3, ..., n)
- aij = the number of resources i required to produce each unit of output of activity j (i = 1, 2, 3, ..., m; j = 1, 2, 3, ..., n)
- bi = the number of sources (facilities) i available to be allocated to each activity unit (i = 1, 2, 3, ..., m).
- Z = optimized value (maximum or minimum)
- Cj = increase in the value of Z if there is an increase in the activity level (xj) by one unit; or is the contribution of each unit of output of activity j to the value of Z.
All the symbols above are then arranged into a standard LP table as follows:
Table 1.1. Data for Linear Programming model
| Kegiatan | Pemakaian sumber per unit kegiatan (keluaran) | | | | | Kapasitas Sumber |
|------------------|-----------------------------------------------|-----|-----|---|-----|------------------|
| Sumber | 1 | 2 | 3 | … | n | |
| 1 | a11 | a12 | a13 | … | a1n | b1 |
| 2 | a21 | a23 | a23 | … | a2n | b2 |
| 3 | a31 | a33 | a33 | … | a3n | b3 |
| … | … | … | … | … | … | … |
| 4 | am1 | am2 | am3 | | amn | bm |
| Increment Z (∆Z) | C1 | C2 | C3 | … | Cn | |
| Tingkat kegiatan | X1 | X2 | X3 | … | Xn | |The basic reason for the table above is that a mathematical model can be constructed which is used to present an LP problem as follows:
Objective function:
Maximize Z = C1X1 + C2X2 + C3X3 + ... + CnXn
Limitations:
1. a11X1 + a12X2 + a13X3 + ... + a1nXn ⪯ b1
2. a21X1 + a22X2 + a23X3 + ... + a2nXn ⪯ b2
.. ..... + ..... + ..... + ... + ..... . ..
.. ..... + ..... + ..... + ... + ..... . ..
m. am1X1 + am2X2 + am3X3 + ... + amnXn ⪯ bm
dan
X1 ⪰ 0, X2 ⪰ 0, ... Xn ⪰ 0The LP model form above is a standard form for LP problems that will be used later. In other words, if each problem can be formulated mathematically following the model above, then the problem can be solved using the LP technique.
Limit functions can be grouped into two types:
- Functional constraint functions, namely m constraint functions.
- Non-negative boundary functions, namely boundary functions that are expressed by Xi ⪰ 0.
In practice, not all problems can exactly follow the model above, there are several problem variants such as the following:
1. Minimization problem
Where one is required to determine the combination (output) that can be minimized. In this case, the objective function is stated as follows:
Minimize Z = C1X1 + C2X2 + C3X3 + ... + CnXn
2. The limit function has a mathematical sign ⪰
When formulated it looks like this:
ai1X1 + ai2X2 + ai3X3 + ... + ainXn ⪰ bi
3. The limit function has a mathematical sign =
When formulated it looks like this:
ai1X1 + ai2X2 + ai3X3 + ... + ainXn = bi
4. The non-negative limit function does not exist or is unlimited.
Some Basic Assumptions of Linear Programming
1. Proportionality
This means that the rise and fall of the Z value and the use of available resources or facilities will change proportionally with changes in the level of activity. For example;
a. Z = C1X1 + C2X2 + C3X3 + ... + CnXn
- Each additional 1 unit of X1 will increase the use of resource/facility 1 by a11
- Each additional 1 unit of X2 will increase the use of resource/facility 1 by a12
- etc.
b. a11X1 + a12X2 + a13X3 + ... + ainXn ⪯ bi
- Each change of 1 unit of X1 will increase the use of resource/facility 1 by a11.
- Each change of 1 unit of X2 will increase the use of resource/facility 1 by a12
- etc.
2. Additivity
This means that the value of the objectives of each activity does not affect each other, or in LP it is assumed that the increase in the objective (Z) caused by the increase in an activity can be added without affecting the part of the Z value obtained from other activities. For example:
Where, Z = 3X1 + 5X2 and X1 = 10; X2 =2;
So, Z = 30 + 10= 40
If X1 increases by 1 unit, then according to the first assumption, the Z value becomes 40 + 3 = 43.
So, the value of 3 due to the increase in X1 can be directly added to the initial Z value without reducing the portion of Z obtained from activity 2(X2). In other words, there is no correlation between X1 and X2.
3. Divisibility
States that the output produced by each activity can be a fractional number, thus the resulting Z value.
Misal: X1 = 6.5; Z = 10.75
4. Deterministic (Certainty)
States that all parameters contained in the LP model (aji, bi, Cj) can be estimated with certainty, although rarely precisely.
Some Definitions in Linear Programming
Solution (Solving)
Is the final answer to a problem
Feasible Solution
Is a solution that does not violate existing boundaries.
No Feasible Solution
This means that there is no feasible area, meaning that the nature or location of the boundaries is such that it does not allow for feasible areas or alternatives to exist.
Optimal Solution
Is a feasible solution that has an optimal or best (maximum or minimum) objective value (Z value in the objective function)
Multiple Optimal Solutions
This means that there are several optimal alternatives to a problem.
Boundary Equation
Occurs when a constraint with an "equal to (=)" sign
Corner Point Feasible Solutions
It is a feasible solution that lies at the angle (intersection) between two lines.
Corner Point Infeasible Solutions
It is a point that lies at the intersection of 2 lines but outside the feasible region.
No Optional Solution
Occurs when a problem does not have an optimal answer or solution, this can be caused by the following factors:
- There is no feasible solution
- There is a limit that does not limit the size of the Z value.
Linear Programming Terms or Properties
Condition 1
- If there is only one optimal solution, it must be a corner point feasible solution.
- If there are multiple solutions then there are more than 2 optimal points located on the line connecting the 2 corner solutions.
Condition 2
Corner point feasible solutions are limited in number
Condition 3
If a corner point feasible solution is better than the 2 nearest corner point feasible solutions, then that point is the optimal or best point among all corner point feasible solutions.
Some Linear Programming Methods
- Graphical Method
- Simplex Method
- Transportation Method (Stepping Stone)
- MODI Method (Modified Distribution)
Reference:
Operations Research Module, Chapter 2 Linear Programming, compiled by Minawarti, ST.