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;
30 Cards in this Set
- Front
- Back
In this chapter we will explore two special linear programming models
|
The transportation model
The assignment model |
|
Because of their structure, they can be solved more ________ than the simplex method.
|
efficiently
-For real world large scale problems, efficient solution method is important. |
|
hese problems are members of a category of LP techniques called ...
|
network flow problems
|
|
A network problem can be represented by…
|
|
|
The importance of network models
|
Many business problems lend themselves to a network formulation.
Optimal solutions of network problems are guaranteed integer solutions, because of special mathematical structures. No special restrictions are needed to ensure integrality. Network problems can be efficiently solved by compact algorithms due to their special mathematical structure, even for large scale models. |
|
Transportation model
|
The transportation problem deals with the distribution or allocation of goods from several points of supply (sources) to a number of points of demand (destinations)
Usually we are given the capacity of goods at each source and the requirements at each destination Typically the objective is to minimize the total transportation, distribution, allocation, and/or production costs |
|
When equal demand and supply occur, a __________ is said to exist
|
balanced problem
-This is uncommon in the real world and we have techniques to deal with unbalanced problems. |
|
One systematic approach is known as the ...
|
northwest corner rule
- requires that we start in the upper-left-hand cell (or northwest corner) of the table and allocate units to ship- ping routes as follows: 1. Exhaust the supply (factory capacity) at each row before moving down to the next row. 2. Exhaust the (warehouse) requirements of each column before moving to the right to the next column. 3. Check that all supply and demands are met. |
|
Heuristic
|
of, pertaining to, or based on experimentation, evaluation, or trial-and-error methods.
|
|
The transportation problem deals with the ..
|
distribution of goods from several points of supply
(origins or sources) to a number of points of demand (destinations). Usually we are given a ca- pacity (supply) of goods at each source, a requirement (demand) for goods at each destination, and the shipping cost per unit from each source to each destination. |
|
The _______ method is an iterative technique for moving from an initial feasible solution to an optimal feasible solution.
|
stepping-stone
|
|
The stepping-stone process has two distinct parts:
|
The first involves testing the current solution to determine if improvement is possible, and
the second part involves making changes to the current solution in order to obtain an improved solution. This process continues until the optimal solution is reached. |
|
Each unused shipping route (or square) in the transportation table is tested by asking the following question:
|
“What would happen to total shipping
costs if one unit of our product were tentatively shipped on an un-used route?” |
|
Five Steps to Test Unused Squares with the Stepping-Stone Method
|
1. Select an unused square to be evaluated.
2. Beginning at this square, trace a closed path back to the original square via squares that are currently being used and moving with only horizontal and vertical moves. 3. Beginning with a plus sign at the unused square, place alternate minus signs and plus signs on each corner square of the closed path just traced. 4. Calculate an improvement index by adding together the unit cost figures found in each square containing a plus sign and then subtracting the unit costs in each square containing a minus sign. 5. Repeat steps 1 to 4 until an improvement index has been calculated for all unused squares. If all indices computed are greater than or equal to zero, an optimal solution has been reached. If not, it is possible to improve the current solution and decrease total shipping costs. |
|
Note that every row and every
column will have ________ in the stepping stone method. |
either two changes or no changes
|
|
Improvement index
|
|
|
In the stepping stone method a path can go through any box but can only ...
|
turn at a box or cell that is occupied.
|
|
To reduce our overall costs, we
want to select the route with the ______ indicating the largest improvement. |
negative index
|
|
Improvement indices for each of
the unused shipping routes must now be ____ to see if any are negative. |
tested
|
|
The transportation algorithm
has four basic steps. |
|
|
Dummy sources or destinations
are used to ... |
balance problems in
which demand is not equal to supply. |
|
Degeneracy occurs when...
|
the number of occupied squares or routes in a transportation table solution is less than the num-
ber of rows plus the number of columns minus |
|
Locating a ______within
one overall distribution system is aided by the transportation method. |
new facility
|
|
The Hungarian method of assignment provides us with an efficient means of finding ...
|
the opti-
mal solution without having to make a direct comparison of every option. -It operates on a prin- ciple of matrix reduction, which means that by subtracting and adding appropriate numbers in the cost table or matrix, we can reduce the problem to a matrix of opportunity costs. |
|
Here are the three steps of the
assignment method. |
|
|
Steps in the Assignment Method
|
|
|
Row and column opportunity
costs reflect the ... |
cost we are
sacrificing by not making the least-cost selection. |
|
Total opportunity costs reflect
|
the row and column opportunity
cost analyses. |
|
When a zero opportunity cost is
found for all of the assignments, an _______ can be made. |
optimal assignment
-This line test is used to see if a solution is optimal. |
|
Maximization problems can
easily be converted to minimization problems. This is done by... |
subtracting each rating
from the largest rating in the table. |