Electronics Manufacturing – B324
Linear programming
Linear programming is concerned with the maximization or minimization of a linear objective function in many variables subject to linear equality and inequality constraints.
Source: Dantzig, G., Thapa, M. (1997). Linear programming 1: introduction. New York, NY, USA: Springer-Verlag New York, LLC.
In the context of electronics manufacturing, linear programming has more specific applications:
- Programming is a synonym for planning, or more specifically, planning of manufacturing activities, resources and products
- The linear objective function describes the potential amount of profit, loss, revenue or cost
- Variables are the resources (input) and/or products (output) related to the manufacturing activities
- Linear equality and inequality constraints describe requirements or restrictions caused by manufacturing activities
- Maximization is concerned with profit, revenue or output quantities
- Minimization is concerned with loss, costs or input quantities
Optimization refers to a large number of techniques to identify maximum and minimum solutions for problems. Linear programming is one such technique. It is a common and widespread technique because a surprising number of real world problems can be described or estimated using linear equations!
A
standard form of a linear programming problem is to find values of
x1, x2, ... , xn so as to
(note 1)
maximize z = c1x1 + c2x2 + ... + cnxn
Subject to
(note 2)
a11x1 + a12x2 + ... + a1nxn ≤ b1
a21x1 + a22x2 + ... + a2nxn ≤ b2
...
am1x1 + am2x2 + ... + amnxn ≤ bm
and
(note 3)
x1 ≥ 0, x2 ≥ 0, ... , xn ≥ 0
Notes:
(1) Objective function could also be expressed as minimizing z
(2) Functional constraints could also be expressed with ≥ or =
(3) This requirement is also known as the nonnegativity constraint
Linear programming has very specific terms:
- A solution is any specification of values for x1, x2, ... , xn
- A feasible solution is one such that all constraints are satisfied
- The feasible region is the collection of all feasible solutions
- It is possible for a problem to have an empty feasible region, e.g. no feasible solution
- An optimal solution is a feasible solution that has the most favorable value of the objective function
- When maximizing the objective function, the most favorable value is the largest value
- When minimizing the objective function, the most favorable value is the smallest value
Linear programming problems may also be described in
matrix notation as:
(note 1)
maximize Z = ctx
Subject to
(note 2)
ax ≤ b
and
(note 3)
x ≥ 0
where
c, x, b, 0 are column vectors, and
a is a matrix of m rows by n columns
Notes:
(1) Objective function could also be expressed as minimizing z
(2) Functional constraints could also be expressed with ≥ or =
(3) This requirement is also known as the nonnegativity constraint
Linear programming is commonly used to find optimal solutions for product mix problems.
ECE Electronics Ltd manufactures 19" LCD monitors and Blu-ray disc players. Each monitor sold yields an incremental profit of £20 and each disc player sold yields £40.
A monitor requires 4 hours of processing at Anglesea building and 2 hours at Buckingham building. A disc player requires 6 hours of processing at Anglesea building, 6 hours at Buckingham building and 1 hour at Portland building. Anglesea building has a maximum of 120 hours of available processing capacity per day, Buckingham building has 72 hours available and Portland has 10 hours available.
How many monitors and disc players should be manufactured per day to maximize profits for ECE Electronics?
The
objective function is expressed as:
Maximize z = 20x1 + 40x2
where
z represents daily profit,
x1 represents monitors, and
x2 represents disc players
The
functional constraints are expressed as:
4x1 + 6x2 ≤ 120
2x1 + 6x2 ≤ 72
x2 ≤ 10
x1, x2 ≥ 0
where
Constraint 1 represents Anglesea building,
Constraint 2 represents Buckingham building, and
Constraint 3 represents Portland building
Constraint 4 is the nonnegativity requirement
The problem could be described using
matrix notation in order to find the optimal solution using linear programming software.
The
objective function expressed as a vector:
c = [20, 40]
The
functional constraints expressed as a matrix of coefficients and a vector for the RHS constants:
a = [4, 6; 2, 6; 0, 1]
b = [120, 72, 10]
The R Project software provides a variety of statistical and numerical computing features, including linear programming.
Similar to Matlab, R scripts evaluate each expression and displays the result. Usually, an expression is typed on its own line. Multiple expressions can be combined on the same line by using a ; (semicolon) to separate each expression. Anything that appears after the # symbol is considered to be comments and not evaluated. Run the sample script to solve the example problem above.
Reference documents
According to the optimal solution, ECE Electronics will earn the maximum daily profit of £640 by manufacturing 24 monitors and 4 disc players per day.
Write an R script to solve this problem:
Maximize z = 3x1 + x2
Such that,
12x1 + 14x2 ≤ 85
3x1 + 2x2 ≤ 18
x2 ≤ 4
x1, x2 ≥ 0
Write an R script to solve this problem:
Minimize z = 40x1 + 50x2
Such that,
140x1 + 100x2 ≥ 1540
60x1 + 180x2 ≥ 1440
x1, x2 ≥ 0
