Reference no: EM131121868
Enforced Separation in 3-Dimensional Assignment) Consider the 3-dimensional assignment problem of Example 10.7 that involves a set of jobs J, a set of machines M, and a set of workers W. We assume that each of the sets J, M, and W contains n elements, and that the constraints are equality constraints. Suppose that the problem is -separable, in the sense that for some βjm and γmw, and some ≥ 0, we have
(a) Show that if the problem is solved with 3-dimensional assignment obtained achieves the optimal cost of the original problem within 2n.
(b) Suppose that we don't know 
and that we use the enforced separation approach of Example 10.7. Thus, we first solve the jobs-tomachines 2-dimensional assignment problem with values.
Example 10.7In the assignment problems we have considered so far, we group the nodes of the graph in pairs. Multidimensional assignment problems involve the grouping of the nodes in subsets with more than two elements, such as triplets or quadruplets of nodes. For an example of a 3-dimensional assignment problem, suppose that the performance of a job j requires a machine m and a worker w, and that there is a given value ajmw corresponding to the triplet (j, m,w). Given a set of jobs J, a set of machines M, and a set of workers W, we want to find a collection of job/machine/worker triplets that has maximum total value.
|
Under the current manufacturing process
: Under the current manufacturing process, the proportion of computer chips that are defective is 0.4 and a new process is claimed to reduce that proportion. It is desired to test this claim statistically. n = 20, and X defined there.
|
|
Constraint relaxation and lagrangian relaxation
: (Constraint Relaxation and Lagrangian Relaxation) The purpose of this exercise is to compare the lower bounds obtained by relaxing integer constraints and by dualizing the side constraints. Consider the nonlinear network optimization problem with ..
|
|
Determine the amount of accumulated depreciation
: Which depreciation method (MACRS or optional straight-line) would minimize net income for income tax reporting for the 3-year period ending December 31, 2011? Determine the amount of accumulated depreciation at December 31, 2011. Ignore present value..
|
|
Lagrangian relaxation in multidimensional assignment
: Lagrangian Relaxation in Multidimensional Assignment) Apply the Lagrangian relaxation method to the multidimensional assignment problem of Example 10.7, in a way that requires the solution of 2-dimensional assignment problems. Derive the form of ..
|
|
Obtained achieves the optimal cost of the original problem
: Enforced Separation in 3-Dimensional Assignment) Consider the 3-dimensional assignment problem of Example 10.7 that involves a set of jobs J, a set of machines M, and a set of workers W.
|
|
Compute the annual depreciation charges over the machine
: Compute the annual depreciation charges over the machine's life assuming a December 31 yearend for each of the following depreciation methods.
|
|
Determine the net effect of this plan on blawnox pretax
: The firm's variable cost ratio is 70 percent, and its required pretax rate of return on current assets investments is 18 percent. The company also expects its inventory investment to decrease by $1 million due to the anticipated decrease in sales. De..
|
|
Non differentiabilities of the dual function
: This exercise shows that non differentiabilities of the dual function given in Section 10.3, often tend to arise at the most interesting points and thus cannot be ignored. Show that if there is a duality gap, then the dual function q is nondiffe..
|
|
Trade secrets are protectable
: Each of the following is considered trade dress except: Trade secrets are protectable:
|