Chapter 21 Flashcards
Goal Seek
Goal Seek works by changing one variable to achieve target value
Optimization
For multiple variables, each with its own constraint, Goal Seek does not work. Here we use Optimization
Objective function, constraints on the variable, non negative constraints.
The objective function, the constraints on the variables, and the non-negativity constraints together constitute an optimization problem. As the relationships between the variables are linear, we refer to this class of problems as linear programming problems. In a linear programming problem, the objective function and the constraints are linear equations. Linear means the equations do not have exponents (e.g., 3X2+ 4Y2) or cross products (e.g., 3XY + 4YZ). The graph of a linear equation would be a line of the form y=mx+c, that is, a straight line. Here, c is a constant (the intercept on the graph), x is the variable of interest, and m is the coefficient of x and determines the slope of the straight line.
Graphical Solution
In a linear programming problem with only two variables, the optimal values of the two variables can be found by representing the two variables on the x (horizontal) and y (vertical) axes of a graph. Each constraint can be represented as a straight line forming a boundary within which a solution must be found.
Feasible region
The bounded area in a graph is referred to as the feasible region. The feasible region is a set of all points that satisfy the constraints.
Graphical solutions provide a good appreciation of the geometry of optimization problems and give us a number of insights. For instance:
- We can have an empty feasible region, that is, a linear programming problem without a set of feasible solutions.
- We could also have an unbounded feasible region, one that is not limited by some constraint.
- We could have more than one optimal solution
Empty feasible region
A problem in linear programming is said to be infeasible if it has no feasible solutions, i.e. the feasible region is empty. In this case, a graph of the equations shows that feasible regions given by the different constraints do not overlap. The constraints result in mutually exclusive solution regions, that is, the solution regions do not overlap, and our linear programming problem is
infeasible. Shaded areas in the graph do not overlap and hence provide neither a feasible solution nor an optimal solution.
Unbounded feasible region
If the constraints do not allow a bounded region, our problem is described as unbounded and will not have a feasible solution. The shaded area in the graph is feasible area but is not bounded and does not provide an optimal solution.
Multiple Optimal points
In some situations, it is possible to have multiple optimal points. For instance, if the slope of the objective function is identical to that of a constraint, we could have more than one optimal solution.
Despite the usefulness of graphical solutions in understanding optimization problems, their application is limited as graphical solutions
can be used where only two variables are involved. In reality, optimization problems are likely to involve many different variables and a large number of constraints.
Simplex method in Linear Programming
The Simplex Method is based on the insight that the solution to an optimization problem must lie at the intersection of two or more constraints, in other words, a corner point. The Simplex Method starts
with a corner point and checks to see if there is another neighboring corner point that improves the value of the objective function. If such a
point exists, the algorithm repeats this process starting from the neighboring corner. The Simplex Method is iterative, that is, it repeats this process until such time that no further improvement in the objective function can be found. When the algorithm reaches this point, it has found the optimal solution.
The Solver Add-in
In Excel, we solve optimization problems using an add-in known as Solver.
These days software applications come with very many features. Not all features are required by every user of a program. In such cases, a set of features can be packaged as an ‘add-in’. An add-in extends the functionality of the main program for the user who requires these special features.
Note that Add-Ins may be of different types – Excel Add-Ins or COM Add-Ins – depending on how they have been developed.
What is Solver
One type of add-in that comes packaged with Excel is Solver. To understand what Solver does, consider other tools that we have studied. Data Tables show the effects of changes in one variable (one-way data
table) or two variables (two-way data table) on one or more variables (depending on the type of data table). Goal Seek changes one variable until we achieve a target value. However, both Data Tables and Goal
Seek are not constrained. Solver, on the other hand, can change more than one variable – while respecting constraints – until we achieve an optimal value. For this reason, solvers are sometimes known as optimizers.
How to install the Solver add-in
To install Solver Add-in
- Keyboard: ALT + FTAA
- Mouse: File -> Options -> Add-Ins
- Then from the list of ‘Add-ins available’, check Solver Add-in and click OK
- The Solver button should be now visible on the Data ribbon.
In a linear programming problem it may not be possible to find
a set of points that satisfy all of the constraints in the problem. This type
of problem is said to be:
a. A. Infeasible
b. B. Inconsistent
c. C. Unbounded
d. D. Redundant
a. A. Infeasible
A linear programming problem with only _______ decision
variable(s) can be solved by a graphical solution method.
a. A. 1
b. B. 2
c. C. 3
d. D. 4
b. B. 2
The following linear programming problem has been written to plan the production of two products. The company wants to maximize its profits
X1 = number of product 1 produced
X2 = number of product 2 produced
MAX: 150 X1 + 250 X2, Subject to:
2 X1 + 5 X2 less than equal to 200 (for Resource 1)
3 X1 + 7 X2 less than equal to 175 (for Resource 2)
X1, X2 greater than equal to 0
How much profit is earned for each unit of product X2 produced?
a. 150
b. 175
c. 200
d. 250
d. 250
