Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
48 Cards in this Set
- Front
- Back
|
Linear programming techniques |
It consist of a sequence of steps that will lead to an optimal solution to linear-constrained problems, if an optimum exists |
|
|
Linear programming models |
are mathematical representations of constrained optimization problems. |
|
|
Linear programming algorithms |
It require that a single goal or objective be specified (i.e.: maximization of profit, or minimization of cost). |
|
|
Objective function, Decision Variables, Constraints, Parameters |
Four components provide the structure of a linear programming model |
|
|
Objective function |
mathematical statement of profit (or cost, etc.) for a given solution. |
|
|
Decision variables |
represents choices available to the decision maker in terms of amounts of either inputs or outputs. |
|
|
Constraints |
limitations that restrict the available alternatives to decision makers. |
|
|
Parameters |
numerical constants; fixed values given to solve the model. |
|
|
Feasible solution space |
the set of all feasible combinations of decision variables as defined by the constraints |
|
|
An LP model |
It consists of a mathematical statement of the objective and a mathematical statement of each constraint. |
|
|
Nonnegativity constraints |
are listed on a signle linel they reflect the condition that no decision variable is allowed to have a negative value. |
|
|
Linearity, Divisibility, Certainty, Nonnegativity |
In order for LP models to be used effectively, certain assumptions must be satisfied |
|
|
Linearity |
The impact of decision variables is linear in constraints and the objective function |
|
|
Divisibility |
Non-integer values of decision variables are acceptable |
|
|
Certainty |
Values of parameters are known and constant |
|
|
Nonnegativity |
Negative values of decision variables are unacceptable |
|
|
• In formulating a model, begin by identifying the decision variables. Very often, decision variables are “the quantity” of something., such as x1 – the quantity of product 1. • Generally, decision variables have profits, costs, times, or a similar measure of value associated with them. • Constraints are restrictions or requirements on one or more decision variables, and they refer to available amounts of resources such as labor, material, or machine time, or to minimal requirements such as “Make at least 10 units of product 1.” |
Model Formulation |
|
|
Graphical linear programming |
It is a method for finding optimal solutions to two-variable problems. |
|
|
The graphical method of linear programming |
It plots the constraints on a graph and identifies an area that satisfies all the constraints, referred to as the feasible solution space. |
|
|
feasible solution space. |
an area that satisfies all the constraints, referred to as the ____. |
|
|
(1) set up the objective function and the constraints in mathematical format, (2) plot the constraints, (3) identify the feasible solution space, (4) plot the objective function, and (5) determine the optimum solution. |
• The general procedure followed in the graphical approach is as follows. Enumerate. |
|
|
• The first step is to transform the constraint into an equation of a straight line by replacing the inequality symbol with an equal sign. • The next step is to determine where the line intersects each axis. o To find these, get the x and y intercepts of the equation. • Plot the points and connect them with a straight line. If a constraint has only one variable, it will be a straight line. • Indicate by shading whether the inequality is greater than or less than. • Repeat steps for each constraint. |
PLOTTING CONSTRAINTS |
|
|
The feasible solution space |
is the set of all points that satisfies all constraints. |
|
|
Plotting an objective function line |
involves the same logic as plotting a constraint line: determine where the line intersects each axis. |
|
|
redundant constraint. |
a constraint that does not form a unique boundary of the feasible solution space. Such a constraint is called a _____. |
|
|
Its removal would not alter the feasible solution space. |
A constraint is redundant if it meets the following test, what is it? |
|
|
at least one of the other constraints in the problem is more restrictive than the redundant constraint. |
• When a problem has a redundant constraint....? |
|
|
polygon. Moreover, the solution to any problem will be at one of the corner points (intersection of constraints) of the polygon. |
The feasible solution space in graphical linear programming is typically a ____. |
|
|
•For problems that have more than two decision variables, the graphical method isn’t appropriate. The “enumeration” approach is used to find the optimal solution. |
For problems that have more than two decision variables, the graphical method isn’t appropriate. What approach is use to find the optimal solution? |
|
|
the enumeration approach |
With this approach, coordinates of each corner points are determined, and then each set of coordinates is substituted into the objective function to determine its value at that corner point. |
|
|
every combination of x1 and x2 on the segment that touches the constraint the feasible solution space represents an optimal solution. Hence, there are multiple optimal solutions. |
In some instances, the objective function will be parallel to one of the constraint lines that forms a boundary of feasible solution space. When this happens....? |
|
|
Sensitivity analysis |
It is a means of assessing the impact of potential changes to the parameters of an LP model. |
|
|
(1) Objective function coefficients, (2) Right-hand values of constraints, (3) Constraint coefficients |
sensitivity analysis: There are three potential changes [to the parameters of an LP model] |
|
|
A change in the value of an objective function coefficient can cause a change in the optimal solution of a problem. When a change does occur in the value of an objective function coefficient, it can be helpful for a manager to know if that change will affect the optimal values of the decision variables. The manager can quickly determine this by referring to that coefficient’s range of optimality. The range of optimality is the range of values over which the solution quantities of all the decision variables remain the same. |
Objective function coefficients |
|
|
The range of optimality |
This is the range of values over which the solution quantities of all the decision variables remain the same. |
|
|
• It is important to know if a constraint is binding on a solution. A constraint is binding if substituting the values of the decision variables of that solution into the left-hand side of the constraint results in a value that is equal to the RHS. In other words, it stops the objective function from achieving better value. • Each constraint has a corresponding shadow price. It is the amount by which the value of the objective function would change with a one-unit change in the RHS value of a constraint. If a constraint is nonbinding, its shadow price is zero. • In general, multiplying the amount of change in the RHS value of a constraint by the shadow price will indicate the change’s impact on the optimal value of the objective function. However, this is only true over a limited range called the range of feasibility. In this range, the value of the shadow price remains constant. Hence, as long as a change in the RHS value of a constrain is within this range of feasibility, the shadow price will remain the same. |
Right-hand values of constraints |
|
|
• substituting the values of the decision variables of that solution into the left-hand side of the constraint results in a value that is equal to the RHS. In other words, it stops the objective function from achieving better value. |
A constraint is binding if ? |
|
|
shadow price. |
It is the amount by which the value of the objective function would change with a one-unit change in the RHS value of a constraint. If a constraint is nonbinding, this is zero. |
|
|
range of feasibility. |
In this range, the value of the shadow price remains constant. |
|
|
o At least one of the constraints must be of the = or ≥ variety. This causes the feasible solution space to be away from the origin. o The optimal point is the one closest to the origin. |
Graphical minimization problems are quite similar to maximization problems. There are two important differences. What are these? |
|
|
binding constraint |
If a constraint forms the optimal corner point of the feasible solution space, it is called a what? |
|
|
binding constraint |
It limits the value of the objective function; if the constraint could be relaxed, an improved solution would be possible. |
|
|
not binding |
For constraints that are _____, making them less restrictive will have no impact on the solution. |
|
|
surplus. |
If the left-hand side is greater than the right-hand side of the equation, we say there is a ____. |
|
|
Surplus |
It occurs when the values of decision variables are substituted into a ≥ constraint the amount by which the resulting value exceeds the right-hand-side value |
|
|
slack |
If the left-hand side is less than the right-hand side of the equation, we say there is ______. |
|
|
Slack |
It is when the values of decision variables are substituted into a ≤ constraint the amount by which the resulting value is less than the right-hand-side value. |
|
|
The simplex method |
It is a general-purpose linear programming algorithm widely used to solve large-scale problems. |
