Materials for Electronic Products
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
x_{1}, x_{2}, ... , x_{n} so as to
(note 1)
maximize z = c_{1}x_{1} + c_{2}x_{2} + ... + c_{n}x_{n}
Subject to
(note 2)
a_{11}x_{1} + a_{12}x_{2} + ... + a_{1n}x_{n} ≤ b_{1}
a_{21}x_{1} + a_{22}x_{2} + ... + a_{2n}x_{n} ≤ b_{2}
...
a_{m1}x_{1} + a_{m2}x_{2} + ... + a_{mn}x_{n} ≤ b_{m}
and
(note 3)
x_{1} ≥ 0, x_{2} ≥ 0, ... , x_{n} ≥ 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 x_{1}, x_{2}, ... , x_{n}
- 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 = cx
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 = 20x_{1} + 40x_{2}
where
z represents daily profit,
x_{1} represents monitors, and
x_{2} represents disc players
The
functional constraints are expressed as:
4x_{1} + 6x_{2} ≤ 120
2x_{1} + 6x_{2} ≤ 72
x_{2} ≤ 10
x_{1}, x_{2} ≥ 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.
# loads the library that includes linear programming solver
library(lpSolve)
# specify the coefficients of the objective function as a vector
f.obj <- c(20, 40)
# specify the coefficients of the constraints as a matrix
f.con <- matrix (c(4, 6, 2, 6, 0, 1), nrow=3, byrow=TRUE)
# specify the direction of the constraints as a vector corresponding to the rows
f.dir <- c("<=", "<=", "<=")
# specify the RHS of the constraints as a vector corresponding to the rows
f.rhs <- c(120, 72, 10)
# solve the linear programming problem
# max = maximize the objective function, or,
# min = minimize the objective function
results <- lp ("max", f.obj, f.con, f.dir, f.rhs)
# display the status of the linear programming solver
# 0 = success, or, 2 = no feasible solution
results$status
# display the optimal value if available
results$objval
# display the solutions matching the optimal value if available
results$solution
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 = 3x_{1} + x_{2}
Such that,
12x_{1} + 14x_{2} ≤ 85
3x_{1} + 2x_{2} ≤ 18
x_{2} ≤ 4
x_{1}, x_{2} ≥ 0
Write an R script to solve this problem:
Minimize z = 40x_{1} + 50x_{2}
Such that,
140x_{1} + 100x_{2} ≥ 1540
60x_{1} + 180x_{2} ≥ 1440
x_{1}, x_{2} ≥ 0
Write an R script to solve this problem:
You have £10,000 available for investments. Two friends have offered you an opportunity to become a partner in two different entrepreneurial ventures, one operated by each friend. In both cases, the investment would involve some of your time as well as investing cash. Becoming a full partner in the Bob's business would require an investment of £5,000 and 400 hours, and your estimated earnings would be £4,500. The corresponding figures for Alice's business are £4,000 and 500 hours, with an estimated earnings of £4,500. However, both friends are flexible and would allow you to come in at any fraction of a full partnership you would like. If you choose a fraction of a full partnership, all the above figures given for a full partnership (money investment, time investment, and your earnings) would be multiplied by this same fraction. Due to other commitments, you only have 600 hours available to spend on these investments. Solve the problem to find the combination of investments which would maximize your total estimated earnings.
Write an R script to solve this problem:
An electronics company produces precision medical diagnostic computers at two assembly factories, one in Portsmouth and one in Cornwall. Three hospitals have placed orders for this month's production output. The Portsmouth factory can produce 400 units this month and the Cornwall factory can produce 500 units this month. Hospital 1 has ordered 300 units, Hospital 2 has ordered 200 units and Hospital 3 has ordered 400 units. The table below shows the cost for shipping each computer unit from each factory to each of these hospitals. Solve the problem to determine the best shipping plan for how many units to ship from each factory to each hospital.
| Hospital 1 | Hospital 2 | Hospital 3 |
Portsmouth factory | £600 | £800 | £700 |
Cornwall factory | £400 | £900 | £600 |