Modelling production systems, the art of linear programming (MRPRODS)

TARGET AUDIENCE: Students, Academics, Industry Professionals, Employers, and Tech Enthusiasts

About the Thumbnail: This is the simple bar graph that I have made to illustrate multiple period production-inventory model as part of the activities we did!

Note: I’m sharing the digitized copies of my notes as well as copies I have of lecture notes as I’m decluttering :”). I will amend to any request upon reason. Thnaks!

OVERVIEW: One of the explorations that we did for our last term of our stay in DLSU was a course of operations research for production systems using linear programming . It was a shame that this was the last bit of our requirements to earn our degree since I could have applied this in my internship in Sanicare or atleast commented it to the plant engineer since there were clearly unoptimized tasks within their production line but I was not sure how to tackle it at that time.

You may check the course syllabus for this here!

Going back, Operations research is a field and practice dominated by industrial engineers which in my opinion is just a hyperfixation on making the production as perfect as possible using various mathematical concepts and techniques. This is poured into knowledge to ensure that there is a smooth production and process and in our case it is no wonder that sometimes, dealing with process improvements, these will be brought up into discussion.

The essence of linear programming (LP) in my own understanding is to optimize (fancy way to minimize or maximize a certain thing) for the allocation of resources given constraints. These constraints/conditions are often provided as word problems and it is up to the engineer how this is translated into systems of equations to solve under various methods that I will provide further below! Name of the game: achieve needed objective function

Before that, below is a copy of my personal notes and solutions to some of optimization problems and activities, I know its not much as the activities that we did as a class was done during our go-to software MATLAB under the Linear Programming toolbox! Of course, we can never have the solver in our reach that is why we were also taught how to solve this manually through Excel.

Methodology:

To clear out the basics for operations research (OR), I would like to think of it as the DMAIC methodolgy with just more legwork for following structured model-building process:

1. Define the problem and objectives
2. Observe the system and collect data
3. Formulate a mathematical model
4. Verify and validate the model
5. Determine the best solution using optimization
6. Present and interpret results
7. Implement and monitor system performance

The general Linear Programming (LP) model is expressed as:

\[\text{Maximize or Minimize: } Z = c_1x_1 + c_2x_2 + \dots + c_nx_n\]

subject to:

\[\begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \leq b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \leq b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n \leq b_m \\ x_j \geq 0 \text{ for all } j = 1, 2, \dots, n \end{cases}\]

Where:

• ( Z ): objective function
• ( x_j ): decision variables
• ( c_j ): cost or profit coefficients
• ( a_{ij} ): technical coefficients
• ( b_i ): resource limits

Of course the above model and equation is the general form but variables will be subjected to the descrition and nature of the problem!

Linear Programming and Formulation:

Now to further focus ourselves to how LP problems are solved, below are the techniques within our arsenal:

C. Simplex Method

The Simplex Method is an iterative algorithm that efficiently solves LP problems with multiple constraints.

Steps:

1. Convert inequalities into equalities by adding slack or surplus variables.
2. Set up the initial simplex tableau.
3. Identify:
   • Pivot column (entering variable): most negative coefficient in the objective row.
   • Pivot row (leaving variable): smallest positive ratio of RHS to pivot column entry.
4. Perform row operations to update the tableau.
5. Repeat until no negative entries remain in the objective row (optimality condition).

Example Simplex Tableau:

Basic Var	x1	x2	s1	s2	RHS
s1	1	2	1	0	6
s2	3	2	0	1	12
Z	-3	-5	0	0	0

When no negative coefficients remain in the (Z)-row, the current solution is optimal.

B. Graphical Method

Used for problems with two decision variables ((x_1), (x_2)):

• Feasible region is plotted based on constraint inequalities.
• Objective function lines are drawn to find the vertex of optimality.
• Intersection points of constraints are solved algebraically.

Example:

\[\text{Maximize } Z = 3x_1 + 5x_2\]

subject to:

\[\begin{cases} x_1 + 2x_2 \leq 6 \\ 3x_1 + 2x_2 \leq 12 \\ x_1, x_2 \geq 0 \end{cases}\]

C. Gauss–Jordan Method

The Gauss–Jordan elimination method is an algebraic approach for solving simultaneous linear equations by reducing the augmented matrix to reduced row echelon form.

For a system:

\[\begin{cases} a_1x + b_1y = c_1 \\ a_2x + b_2y = c_2 \end{cases}\]

We form the augmented matrix:

\[\begin{bmatrix} a_1 & b_1 & | & c_1 \\ a_2 & b_2 & | & c_2 \end{bmatrix}\]

We apply elementary row operations to obtain:

\[\begin{bmatrix} 1 & 0 & | & x \\ 0 & 1 & | & y \end{bmatrix}\]

This provides direct solutions for (x) and (y).

D. Big M-Method

When artificial variables are introduced (e.g., for ≥ or = constraints), the M-method penalizes these variables by assigning a large constant (M) to discourage their inclusion in the optimal solution.

Objective function:

\[Z = 3x_1 + 2x_2 - M(A_1 + A_2)\]

The artificial variables (A_1, A_2) are given a large negative (for maximization) or positive (for minimization) coefficient to drive them to zero during iterations.

E. Two-Phase Method

An alternative to the M-method, the Two-Phase Method divides the process into two stages:

Phase I:
Minimize the sum of all artificial variables:
\(W = A_1 + A_2 + ... + A_n\)
If (W = 0), proceed to Phase II.

Phase II:
Remove artificial variables and use the remaining ones to optimize the original objective function.

This method avoids the use of large constants, providing a more numerically stable approach.

As demonstration for the methods above, below is a consolidated document of the activities that I have made utilizing MATLAB LP solver and Excel for implementation:

---

Sensitivity and Post-Optimal Analysis

Aside from these methods, one of the things that I remember to apply for a culminating project for this subject (do check my project in different tab!) was to apply sensitivity analysis to validate the robustness of the solution to model the given scenario. Once an optimal solution is obtained, Sensitivity Analysis evaluates how changes in parameters affect the solution’s optimality. Here are the steps needed to perfrom such analysis.

1. Changes in Objective Function Coefficients

Determine how much each (c_j) can change without altering the current optimal basis.

1. Changes in Right-Hand Side (RHS) Values Adjust available resources ((b_i)) to see how it affects production or cost levels.

2. Shadow Prices The shadow price (dual value) represents how much the objective function will improve per unit increase in a constraint’s RHS.

\[\Delta Z = \sum_i \lambda_i \Delta b_i\]

where (\lambda_i) are the shadow prices.

1. Allowable Ranges Determine the allowable increase or decrease for each parameter such that the optimal basis remains unchanged.

I have provided my solution sheets for some LP use cases but MATLAB or any dedicated optimization software helps the engineers make their lives easier in solving these. To summarize and appreciate the effort of the solutions given, I have below the consolidated lecture notes that I have with me!

REFLECTIONS:

What I like about this course, as condensed as it is, (legit IE counterparts dedicate 12 units for the study of this), is that this is tailored for the manufacturing scene. There are many instances that you are often dealt with limited resources and this tool helps us how we can justify to stakeholders towards to the right course of action.

But whats its benefit is also its weakness. You can never really apply this in the field unless you are into the field! As ironic as it seems, but what was provided as an example to this was mainly research heavy but I have heard of talks that utilized LP to solve some optimization problems. It reality, this, imho, not really applied that often especially that as prospects for process engineers, we obliged to output improvements that will often deal with lowering standard times. What is often expected is to provide a work/project proposal to be done over a course of weeks. That is what I have also conferred with coursemates that took process engineering internships. What is important is not the tools utilized but on the output.

Like in my stay in Sanicare, what is being asked of me is for process improvements more than anything that is why I was shocked that they want me to make a project too for them when my window to implement it was long gone. The reality is that output-based work is stil standard and unless LP and operations research is applied in a fast and iterative process (like those sprint seshs that im sure MNC are doing with an extensive eng team), what is required for us is to deliver impact in as short time as possible in a SMART timeline.

U think this is a good take? Share down in the comments :>