Mgt Science Chp 9

Front 1

In this chapter we will explore two special linear programming models

Back 1

The transportation model
The assignment model

Front 2

Because of their structure, they can be solved more ________ than the simplex method.

Back 2

efficiently
-For real world large scale problems, efficient solution method is important.

Front 3

hese problems are members of a category of LP techniques called ...

Back 3

network flow problems

Front 4

A network problem can be represented by…

Back 4

Front 5

The importance of network models

Back 5

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.

Front 6

Transportation model

Back 6

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

Front 7

When equal demand and supply occur, a __________ is said to exist

Back 7

balanced problem
-This is uncommon in the real world and we have techniques to deal with unbalanced problems.

Front 8

One systematic approach is known as the ...

Back 8

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.

Front 9

Heuristic

Back 9

of, pertaining to, or based on experimentation, evaluation, or trial-and-error methods.

Front 10

The transportation problem deals with the ..

Back 10

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.

Front 11

The _______ method is an iterative technique for moving from an initial feasible solution to an optimal feasible solution.

Back 11

stepping-stone

Front 12

The stepping-stone process has two distinct parts:

Back 12

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.

Front 13

Each unused shipping route (or square) in the transportation table is tested by asking the following question:

Back 13

“What would happen to total shipping
costs if one unit of our product were tentatively shipped on an un-used route?”

Front 14

Five Steps to Test Unused Squares with the Stepping-Stone Method

Back 14

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.

Front 15

Note that every row and every
column will have ________ in the stepping stone method.

Back 15

either two changes or no changes

Front 16

Improvement index

Back 16

Front 17

In the stepping stone method a path can go through any box but can only ...

Back 17

turn at a box or cell that is occupied.

Front 18

To reduce our overall costs, we
want to select the route with the
______ indicating the
largest improvement.

Back 18

negative index

Front 19

Improvement indices for each of
the unused shipping routes
must now be ____ to see if any
are negative.

Back 19

tested

Front 20

The transportation algorithm
has four basic steps.

Back 20

Front 21

Dummy sources or destinations
are used to ...

Back 21

balance problems in
which demand is not equal to
supply.

Front 22

Degeneracy occurs when...

Back 22

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

Front 23

Locating a ______within
one overall distribution system is
aided by the transportation
method.

Back 23

new facility

Front 24

The Hungarian method of assignment provides us with an efficient means of finding ...

Back 24

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.

Front 25

Here are the three steps of the
assignment method.

Back 25

Front 26

Steps in the Assignment Method

Back 26

Front 27

Row and column opportunity
costs reflect the ...

Back 27

cost we are
sacrificing by not making the
least-cost selection.

Front 28

Total opportunity costs reflect

Back 28

the row and column opportunity
cost analyses.

Front 29

When a zero opportunity cost is
found for all of the assignments,
an _______ can be
made.

Back 29

optimal assignment
-This line test is used to see if a
solution is optimal.

Front 30

Maximization problems can
easily be converted to
minimization problems. This is
done by...

Back 30

subtracting each rating
from the largest rating in the
table.