Consider the following problem.
Minimize Z = 3x1 + 2x2,
subject to
and
x1 >= 0, x2 >= 0.
(a) Solve this problem graphically.
(b) Using the Big M method, construct the complete first simplex tableau for the
simplex method and identify the corresponding initial (artificial) BF solution. Also
identify the initial entering basic variable and the leaving basic variable.
(c) Work through the simplex method step by step to solve the problem.
Consider the following problem.
Maximize Z = 2x1 – x2 + x3,
subject to
and
x1 >= 0, x2 >= 0, x3 >= 0.
(a) Work through the simplex method step by step in algebraic form to solve this
problem.
(b) Work through the simplex method step by step in tabular form to solve the problem.
Consider the following problem.
Maximize Z = 2x1 + 4x2 + 3x3,
subject to
and
x1 >= 0, x2 >= 0, x3 >= 0.
Let be the artificial variable for the first constraint. Let x5 and be the surplus
variable and artificial variable, respectively, for the second constraint.
You are now given the information that a portion of the final simplex tableau is as
follows:
(a) Extend the fundamental insight presented in Sec. 5.3 of the textbook to identify the
missing numbers in the final simplex tableau. Show your calculations.
(b) Identify the defining equations of the CPF solution corresponding to the optimal
solution in the final simplex tableau.
In the MBA program at a prestigious university in the Pacific Northwest, students bid
for electives in the second year of their program. Each student has 100 points to bid
(total) and must take two electives. There are four electives available: Management
Science, Finance, Operations Management, and Marketing. Each class is limited to 5
students. The bids submitted for each of the 10 students are shown in the table below.
(a) Formulate this problem as an assignment problem by constructing an appropriate
cost table.
(b) Reformulate this assignment problem as an equivalent transportation problem by
constructing the appropriate parameter table.
(c) Formulate and solve a spreadsheet model for this problem.
(d) Does the resulting solution in part (c) seem like a fair assignment?
(e) Which alternative objectives might lead to a fairer assignment?
Consider the following activity-on-arc project network, where the 12 arcs (arrows)
represent the 12 activities (tasks) that must be performed to complete the project and
the network displays the order in which the activities need to be performed. The number
next to each arc (arrow) is the time required for the corresponding activity. Consider the
problem of finding the longest path (the largest total time) through this network from
start (node 1) to finish (node 9), since the longest path is the critical path. Formulate a
BIP model for this problem.
The kitchen manager for Sing Sing Prison is trying to decide what to feed its prisoners.
She would like to offer some combination of milk, beans, and oranges. The goal is to
minimize cost, subject to meeting the minimum nutritional requirements imposed by
law. The cost and nutritional content of each food, along with the minimum nutritional
requirements, are shown below. What diet should be fed to each prisoner?
Formulate and solve a linear programming model for this problem in a spreadsheet.
Formulate this same model algebraically.
Customers arrive at a fast food restaurant with one server according to a Poisson
process at a mean rate of 30 per hour. The server has just resigned, and the two
candidates for the replacement are X (fast but expensive) and Y (slow but inexpensive).
Both candidates would have an exponential distribution for service times with X having
a mean of 1.2 minutes and Y having a mean of 1.5 minutes. Restaurant revenue per
month is given by $6,000/W where W is the expected waiting time (in minutes) of a
customer in the system.
Determine the upper bound on the difference in their monthly compensations that
would justify hiring X rather than Y.
Cindy Stewart and Misty Whitworth graduated from business school together. They
now are inventory managers for competing wholesale distributors, making use of the
scientific inventory management techniques they learned in school. Both of them are
purchasing 85-horsepower speedboat engines for their inventories from the same
manufacturer. Cindy has found that the setup cost for initiating each order is $200 and
the unit holding cost is $400.
Cindy has learned that Misty is ordering 10 engines each time. Cindy assumes that
Misty is using the basic EOQ model and has the same setup cost and unit holding cost
as Cindy. Show how Cindy can use this information to deduce what the annual demand
rate must be for Misty’s company for these engines.
Sarah and Jennifer have just graduated from college at the University of Washington in
Seattle and want to go on a road trip. They have always wanted to see the mile-high city
of Denver. Their road atlas shows the driving time (in hours) between various city pairs,
as shown below. Formulate and solve a network optimization model to find the quickest
route from Seattle to Denver?
