# Transformation Algorithms - Linear Programming Models

Problem:

This question involves formulating a linear programming model a transportation problem where demand exceeds supply. The question has four parts: (a) to (d).

Please see the attachment for full details of the question.

a) Write down a linear programming model of the transportation problem in the case when demand exceed supply.

b) Describe an algorithm to find the closed path of stepping-stones required by the transportation algorithm.

c) Apply Vogel's rule to the following transportation problem and then perform ONE iteration of the transportation algorithm. State the resulting basic feasible solution and whether or not it is optimal.

See attachment for table

d) Write down three advantages the transportation algorithm has over the Simplex method for solving Transportation problems.

© BrainMass Inc. brainmass.com October 25, 2018, 8:25 am ad1c9bdddfhttps://brainmass.com/math/linear-programming/transformation-algorithms-linear-programming-models-539386

#### Solution Preview

(a). MODEL

Lest us assume sources are S1, S2, S3, ..., Sm which supply s1, s2, s3, ..., sm units to Destinations D1, D2, D3, ..., Dn of which demands are d1, d2, d3, ..., dn.

if S1 supplies x11, x12, x13, ..., x1n units, S2 supplies x21, x22, x23, ..., x2n units, ..., Sm supplies xm1, xm2, xm3, ..., xmn units to D1, D2, D3, ..., Dn destinations respectively such that:

For supply less than demand,

s1 + s2 + s3 + ... + sm < d1 + d2 + d3 + ... dn

To balance, the unsatisfied demand , add a dummy source Sz. Let us assume Sz supplies xz1, xz2, xz3, ..., xzn units to D1, D2, D3, ..., Dn destinations, with zero costs.

Hence,

s1 + s2 + s3 + ... + sm + sz = d1 + d2 + d3 + ... dn

x11 + x12 + x13 + ... + x1n = s1

x21 + x22 + x23 + ... + x2n = s2

...

xm1 + xm2 + xm3 + ... + xmn = sm

xz1 + xz2 + xz3 + ... + xzn = sz

And,

x11 + x21 + x31 + ... + xm1 + xz1 = d1

x12 + x22 + x32 + ... + xm2 + xz2 = d2

...

x1n + x2n + x3n + ... + xmn + xzn = dn

If costs of supply from ith source to jth destination is cij/unit, then function

S = sum(i=1,m; j = 1,n) (cij * xij) [Note: czj = 0]

Objective is to find non-negative values of xij such that function S is minimized.

(b). ALGORITHM

1. Determine an initial basic feasible solution using a method like Vogel Approximation Method.

2. Make sure number of occupied cells is exactly = m+n-1, where m = number of rows and n = number of columns.

3. Select an unoccupied cell. Beginning at this cell, trace a closed path, starting from the selected unoccupied cell until finally returning to that same unoccupied cell.

4. Assign plus (+) and minus (-) signs alternatively on each corner cell of the closed path just ...

#### Solution Summary

Vogel's rule linear programming method applied to solve a transportation problem.Also, linear programming model for demand exceeding supply, algorithm of closed path o stepping-stones, comparison of simplex and transportation algorithms are described.

Quantitative Analysis

1. Which of the following is not a reason for the failure of a particular quantitative analysis technique in solving a problem?

a. underestimating the total cost of using quantitative techniques

b. failure to define the real problem

c. under-emphasis on theory and over-emphasis on application

d. underestimating the total time required to develop and implement the most appropriate technique

e. resistance to change and reluctance of decision-makers to trust and act upon the results obtained by using unfamiliar techniques

2. Evaluating all possible values of a variable in a model is called

a. trial and error.

b. complete enumeration.

c. an algorithm.

d. variablization.

e. none of the above

3. The classical method of determining probability is

a. subjective probability.

b. marginal probability.

c. objective probability.

d. joint probability.

e. conditional probability.

4. The expected value of a probability distribution is

a. the measure of the spread of the distribution.

b. the variance of the distribution.

c. the average value of the distribution.

d. the probability density function.

e. the range of continuous values from point A to point B, inclusive.

5. At a university with 1,000 business majors, there are 200 business students who are enrolled in an introductory statistics course. Of these 200, 50 are also enrolled in an introductory accounting course. There are an additional 250 business students who are enrolled in accounting but are not enrolled in statistics. If a business student is selected at random, what is the probability that the student is not enrolled in accounting?

a. 0.20

b. 0.25

c. 0.30

d. 0.50

e. none of the above

6. Expected monetary value (EMV) is

a. the average or expected monetary outcome of a decision if it can be repeated a large number of times.

b. the average or expected value of the decision if you know what would happen ahead of time.

c. the average or expected value of information if it were completely accurate.

d. the amount you would lose by not picking the best alternative.

e. a decision criterion that places an equal weight on all states of nature.

7. The maximax decision criterion

a. minimizes the maximum opportunity loss.

b. maximizes the minimum outcome.

c. yields the best of the worst possible outcomes when the probability is favorable.

d. produces the alternative with the highest possible return.

e. none of the above

8. If product demand follows a normal distribution and we want to apply marginal analysis, which of the following do we not need to know?

a. the mean sales estimate

b. the standard deviation of the sales estimate

c. the marginal profit

d. the marginal loss

e. the standard deviation of the profit estimate

9. In constructing a utility curve,

a. a comparison is made with the different amounts of money at different times.

b. the certainty of a certain amount is compared with the

willingness to gamble that amount on a larger amount.

c. one takes the risk out of gambling.

d. inflation plays a critical part in the evaluation.

e. none of the above

10. Payoff tables are more difficult to use than decision trees when

a. perfect information is available.

b. formulating a conditional values table.

c. the opportunity loss table is available.

d. a sequence of decisions must be made.

e. all possible outcomes and alternatives are not known.

11. When using Bayesian analysis

a. the actual probabilities of the states of nature are never known.

b. it makes no difference whether one is employing EMV or utility as a measure of outcome.

c. the joint probabilities must total less than 1.

d. the more accurate a survey, the more likely the survey is to make a positive prediction.

e. none of the above

12. Which method is NOT a step used to develop a forecast using the Decomposition Method?

a. Compute seasonal indices using CMAs.

b. Deseasonalize the data by dividing each number by its seasonal index.

c. Proctoring the data by seasonal indexes and statistical methods.

d. Multiply the trendline forecast by the appropriate seasonal index .

e. Forecast for future periods using the trend line.

13. A tracking signal was calculated for a particular set of demand forecasts. This tracking signal was positive. This would indicate that

a. demand is greater than the forecast.

b. demand is less than the forecast.

c. demand is equal to the forecast.

d. the MAD is negative.

e. none of the above

14. The EOQ model assumes,

a. a simple regression model would always be adequate.

b. a moving average model is uncertain.

c. all input values are fixed and known with certainty.

d. an exponential smoothing model would always be best.

e. none of the above

15. Which of the following factors is (are) not included in carrying cost?

a. spoilage

b. obsolescence

c. cost of capital

d. inspecting incoming inventory

e. warehousing overhead costs

16. The annual demand for a product is 1,000 units. The company orders 200 units each time an order is placed. The lead time is 6 days, and the company has determined that 20 units should be held as a safety stock. There are 250 working days per year. What is the

reorder point?

a. 20

b. 24

c. 44

d. 120

e. none of the above

17. To evaluate quantity discounts, one uses the EOQ model, and modifies the model so that

a. holding cost is considered as a percentage of unit cost rather

than a separable dollar cost.

b. the EOQ is calculated to lie within one of the cost corridors.

c. holding cost is calculated on an "average basis" across the

discounts.

d. any one of the above approaches could be used.

e. none of the above

18. An optimal solution to a linear program

a. will always lie at an extreme point of the feasible region.

b. could be any point in the feasible region of the problem.

c. will always be unique (only one optimal solution possible for any one problem).

d. will always include at least some of each product or variable.

e. must always be in whole numbers (integers).

19. Two models of a product - Regular (X) and Deluxe (Y) - are produced by a company. A linear programming model is used to determine the production schedule. The formulation is as follows:

Maximize profit = 50X + 60 Y

Subject to: 8X + 10Y ≤ 800 (labor hours)

X + Y ≤ 120 (total units demanded)

4X + 5Y ≤ 500 (raw materials)

all variables ≥ 0

The optimal solution is X = 100 Y = 0.

How many units of the raw materials would be used to produce this number of units?

a. 400

b. 200

c. 500

d. 120

e. none of the above

20. In order for a linear programming problem to have a unique solution, the solution must exist

a. at the intersection of the non-negativity constraints.

b. at the intersection of a non-negativity constraint and a

resource constraint.

c. at the intersection of the objective function and a constraint.

d. at the intersection of two or more constraints.

e. none of the above

21. The following does not represent a factor a manager might consider when employing linear programming for a production scheduling:

a. labor capacity

b. space limitations

c. product demand

d. risk assessment

e. inventory costs

22. Production scheduling is amenable to solution by linear programming because

a. the optimal product combination will minimize production risk.

b. effective resource use will lead to optimal profits.

c. linear programming will allow investment losses to be minimized.

d. scheduling requires specific, narrowly defined constraints.

e. objective functions and constraints can be readily developed and are relatively stable over time.

23. A type of linear programming problem that is used in marketing is called the

a. media selection problem.

b. Madison Avenue problem.

c. marketing allocation problem.

d. All of the above are examples of marketing linear programming problems.

e. None of the above are examples of marketing linear programming problems.

24. In applying the simplex solution procedure to a maximization problem to determine which variable enters the solution mix

a. pick the one with the smallest Cj − Zj.

b. pick the one with the largest Cj − Zj.

c. pick the one with the largest Cj.

d. pick the one with the smallest Zj.

e. pick the smallest nonnegative number formed by dividing each amount in the quantity column by the appropriate column at the exiting variable.

25. Sensitivity analysis in linear programming

a. centers around applications of computer routines to solve LP problems.

b. concerns studies of the extra information associated with the dual LP.

c. concerns changes in the data used to build the LP model and the effects on the optimal solution.

d. all of the above

26. The presence of one or more constraints that do not affect the feasible solution region is:

a. redundancy.

b. inequality.

c. unboundedness.

d. a constraint.

e. none of the above

27. In applying Vogel's approximation method to a cost minimization problem, row and column penalties are determined by

a. finding the largest unit cost in each row or column.

b. finding the smallest unit cost in each row or column.

c. finding the sum of the unit costs in each row or column.

d. finding the difference between the two lowest unit costs in each row and column.

e. finding the difference between the two highest unit costs in each row and column.

28. In solving maximization assignment problems,

a. just reverse all the decision rules used in the minimizing algorithm (if it says subtract, now add, etc.).

b. use the Australian transformation process and convert the data.

c. convert the problem to an equivalent minimization problem.

d. all of the above

29. The only restriction we place on the initial solution of a transportation problem is that

a. we must have nonzero quantities in a majority of the boxes.

b. all constraints must be satisfied.

c. demand must be less than supply.

d. we must have a number (equal to the number of rows plus the number of columns minus one) of boxes which contain nonzero quantities.

e. none of the above

30. Which of the following is not a technique used in solving nonlinear program problems?

a. classical optimization

b. gradient method

c. diorama algorithm

d. steepest ascent method

e. separable programming

31. In a goal programming problem with two goals at the same priority level, all the deviational variables are equal to zero in the optimal solution. This means

a. there is no feasible solution to the problem.

b. all goals are fully achieved.

c. nonlinear programming must be used to solve this.

d. this problem was an integer programming problem.

e. none of the above

32. If we wish to select a location for a new manufacturing plant, the best approach would be to use

a. zero-one integer programming.

b. mixed-integer programming.

c. any linear programming model.

d. an assignment model.

e. a goal programming model.

33. The minimal-spanning technique would best be used

a. by an architect to lay out corridors between offices in a new office building.

b. by a telephone company attempting to lay out wires in a new housing development.

c. by an airline laying out flight routes.

d. none of the above

e. all of the above

34. When using the shortest-route technique, the second step is to

a. find the next-nearest node to the origin and put the distance in a box by the node.

b. trace the path from the warehouse to the plant.

c. determine the average distance traveled from source to end.

d. find the nearest node to the origin and put a distance box by the node.

e. none of the above

35. Find the shortest route from Node 1 to Node 5 using the shortestroute technique.

From To Node Node Distance

1 2 200

1 3 150

2 3 50

2 4 300

3 4 250

3 5 200

4 5 150

a. 350

b. 400

c. 450

d. 600

e. none of the above

36. In a PERT network, the earliest (activity) start time is the

a. earliest time that an activity can be finished without delaying the entire project.

b. latest time that an activity can be started without delaying the entire project.

c. earliest time that an activity can start without violation of precedence requirements.

d. latest time that an activity can be finished without delaying the entire project.

e. none of the above

37. Consider a project that has an expected completion time of 60 weeks and a standard deviation of five weeks. What is the probability that the project is finished in 70 weeks or less (round to two decimals)?

a. 0.98

b. 0.48

c. 0.50

d. 0.02

e. none of the above

38. In CPM,

a. an activity may start before its immediate predecessors have finished.

b. no more than two activities may be performed simultaneously.

c. the total cost of completing an activity in the crash time is higher than the normal cost.

d. when we crash an activity, we complete the activity in the minimum possible time.

e. none of the above

39. Which of the following is not an assumption in common queuing mathematical models?

a. Arrivals come from an infinite, or very large, population.

b. Arrivals are Poisson distributed.

c. Arrivals are treated on a first-in, first-out basis and do not balk or renege.

d. Service times follow the negative exponential distribution.

e. The average arrival rate is faster than the average service rate.

40. Customers enter the waiting line at a cafeteria on a first come, first served basis. The arrival rate follows a Poisson distribution, while service times follow an exponential distribution. If the average number of arrivals is six per minute and the average service rate of a single server is eight per minute, what is the average number of customers in the system?

a. 0.50

b. 0.75

c. 2.25

d. 3.00

e. none of the above

41. In queuing problems, the size of the calling population is important because

a. we have models only for problems with infinite calling populations.

b. we have models only for problems with finite calling populations.

c. the size of the calling population determines whether or not the arrival of one customer influences the probability of arrival of the next customer.

d. we will have to consider the amount of space available for the queue.

e. none of the above

42. Which of the following is not always a step in Monte Carlo simulation:

a. establishing probability distributions

b. building a cumulative probability distribution for each variable

c. setting random number intervals

d. starting an exponential generator

e. simulating the experiment

43. Using simulation for a queuing problem

a. would be rare in a realistic situation.

b. is an unreasonable alternative if the arrival rate is not

Poisson distributed but can be plotted on a curve.

c. could be appropriate if the service time was not exponential or constant.

d. all of the above

44. Special purpose simulation languages include

a. FORTRAN.

b. BASIC.

c. GPSS.

d. PL/1.

e. all of the above

45. Of the following, this is NOT a step in modeling

a. developing a solution.

b. defining the problem.

c. training and development.

d. implementing the results.

e. testing the solution.

46. A technique that allows a decision maker to plan, schedule, monitor, and control project costs is:

a. PERT/Cost.

b. PERT/Monitoring.

c. PERT/Planning.

d. PERT/Scheduling.

47. The length of a waiting line can be

a. finite

b. limited or unlimited

c. studied indefinitely

d. infinite

e. none of the above

48. A probability distribution has been developed, and the probability of 2 arrivals in the next hour is 0.20. A random number interval is to be assigned to this. Which of the following would NOT be an appropriate interval?

a. 01-20

b. 21-40

c. 00-19

d. 00-20

49. Which of the following should cause a process control system to sound the alarm?

a. natural variations

b. a mean is greater than a standard deviation

c. control variations

d. assignable variations

e. none of the above

50. The Poisson distribution forms the basis for which of the following charts?

a. c-chart

b. x -chart

c. p-chart

d. all of the above

e. none of the above