Reference no: EM132737975

Question 1. Categorize each of the following Phase 1 tableaux according to the directions (assume that the artificial variables are named aj):

Question 2. Categorize each of the following Phase 2 tableaux according to the directions:

Question3. Consider this instance of an optimization problem:
min - 5x1 - 4x2 + 2x3 subject to 2x1 + 3x2 - x3 ≤ 12
-3x1 + x2 + 2x3 = 15
x1 + x2 + 3x3 ≥ 6

a. Add slack, surplus, or artificial variables as needed to convert the given constraints to the required form for an instance of LP-carefully write the converted constraints here, in mathematical notation:

b. Create a data file for Phase 1 on this instance (you are allowed to use a text editor), and use ManualSimplex to do Phase 1, and Phase 2 (unless Phase 1 tells you to stop) to solve this instance, concluding that the constraints are infeasible, or the problem is unbounded, or that it has an optimal point, and answer all the questions below.
Is this instance infeasible (if you say "yes," you will obviously not need to answer any further questions)?

Is this instance unbounded (if you say "yes," you will obviously not need to answer any further questions)?
If you think that this instance has an optimal point,

list the original variables (of the form "xj") that are basic at the optimal point, with their optimal values:

and what is the optimal objective function value (be sure to get the sign correct for the original problem)?

4. Here is the data for an instance of the transportation problem, where the rows represent factories, the columns represent stores, the far right column of numbers is the total units shipped from each factor, the bottom row of numbers is the total units to be received at each store, and the number in row j, column k is the cost to send one unit from factory j to store k.

Your job on this problem is to create the data file for this instance and use ManualSimplex to do Phase 1 and then Phase 2, finding the optimal number of units to ship from each factory to each store in order to minimize the total shipping cost.

Write the values of the optimal basic variables in the chart above, and state clearly the optimal shipping cost.

Directions for Problem 5

Demonstrate (by writing out the complete tree on the next page) the branch and bound heuristic algorithm for the 0-1 knapsack instance with this data:

with the knapsack capacity being 15.

You must demonstrate the "best first" version of the algorithm that always explores the node with the best bound, where the bound is obtained by computing the profit that could be achieved, given the current choices at the node, if we were allowed to use fractional parts of the following item(s), and prunes nodes whenever their bound is less than a known achievable profit or their weight is too high.

For each node that is drawn, use the format shown in the part that is already done on the next page, including numbering the nodes in the order they are added to the priority queue.

Write you answer on the next page. The first few nodes have already been done, to save you time and to show the desired format. This is a snapshot of the algorithm at the point where nodes 2, 4, and 5 are in the priority queue.

Whenever a node is pruned, write immediately below out why it has been pruned.

You will be penalized if you explore nodes that should have been pruned. Be sure to generate all nodes, though, that the algorithm produces, even if you as a clever human can see that there is no point.

In general, show all your work and explain all your reasoning.

Directions for Problem 6

Consider the ETSP instance with these 30 points (given for your convenience in the attached file problem6):

Your job on this problem is to use AutoHeuristicTSP to solve this instance, and to do what is asked below to show your full understanding of the algorithm.

Write your branch and bound tree and other answers on the next page.

Draw the branch and bound tree showing the node number and score for each node (you can just draw the first, say, up to 10 nodes, to show that you understand how it works, and then you can stop drawing). You don't have to write down the cuts you make (write the score in each node after all cuts have been done), but you should clearly show on the edges what branching choices you are making.

Clearly state which node gives the optimal tour and state the total length of that tour.

6. (write your answer for Problem 6 here)

Directions for Problem 7:

Suppose we have some factories, some warehouses, and some stores, and we want to send a certain number of units of some product from the factories, to the warehouses, and then to the stores, with minimal shipping cost, where we have a known, fixed cost of shipping one unit of product along each possible path from a particular factory to a particular warehouse, and from a particular warehouse to a particular store.
For example, we might have three factories (represented by triangles), each with some number of products to ship, and four stores (represented by circles) each with some number of products to receive, and we have two warehouses (represented by squares), each with a limit of the number of units that can be received and later shipped out, like this (where its number of products is written discreetly next to each factory, warehouse, and store):

Instead of labeling the edges with the per unit cost of shipping, these charts give that information:

Cost of shipping one unit from factory j
(the row) to warehouse k (the column):
1 2
1
2
3

Cost of shipping one unit from warehouse
k (the row) to store m (the column):
1 2 3 4
1
2

We can solve this problem by modeling it as an instance of LP.

Your job is to write, on the next page, using the data provided in the diagram and charts above, the objective function in its entirety (which would be minimized) and a few of the constraints as requested, using the variables fjk = number of units to ship from factory j to warehouse k and wkm = number of units to ship from warehouse k to store m.

7. (write your answer to Problem 7 here) Write the objective function here:

Write here the constraint that says the total number of units shipped out of factory 2 will be equal to the number of units it produces:

Write here the constraint that says that warehouse 1 must receive and send out the same number of units:

Write here the constraint that says that warehouse 2 must not receive more than its specified limit on its number of units:

Write here the constraint that says that store 4 must receive its specified number of units:

Attachment:- Test 3.rar