Reference no: EM132734970

Exercise 25
Demonstrate the brute force method, using the ManualSimplex application, on this LP (you will need to use a text editor to make a suitable input file for this problem, which is already in the required format for LP):

max x1 + 2x2 + 3x3 + 3x4 + 2x5 + x6 subject to 4x1 + 8x2 + 3x3 + 6x4 + 10x5 - x6 = 120
8x1 - 4x2 - 6x3 - 8x4 + x5 + 3x6 = 24
12x1 + 5x2 - 9x3 + 6x4 - 9x5 + 8x6 = 360
x ≥ 0

List all different ways (order doesn't matter) to choose m basic variables, and for each, use the program to do the row operations, and mark as infeasible or feasible, and if it is feasible, write the objective function value. When all have been done, note the optimal choice, and state clearly the values of all the variables and the objection function value for this optimal choice.

Exercise 26
For each of the 3 problems below, produce a careful mathematical description of the LP, ready to be put into a data file for use with ManualSimplex. Then use the application, noting the values of the basic variables and the objective function at the optimal tableau for both Phase 1 and Phase 2, as appropriate, and describe the final solution to each problem as infeasible, unbounded, or having an optimal feasible point.
a. Formulate and solve this LP:

subject to the constraints

max x1 + 2x2 + 3x3
-3x1 + 15x2 - 3x3 ≥ 3 6x1 + 3x2 + 6x3 ≤ 60
-6x1 + 6x2 + 3x3 ≤ 21
9x1 + 5x2 - x3 ≥ 21
-3x1 + 5x2 + 2x3 ≥ 3 6x1 + 8x2 - 4x3 ≤ 30
8x2 - 4x3 ≤ 12
3x1 + 3x3 ≥ 12
x1, x2, x3 ≥ 0

b. Formulate and solve the above LP, but with this constraint added:
2x3 ≤ 1
c. Formulate and solve the LP for part a, but with the first four constraints removed.

Exercise 27
In this exercise you will explore using LP to solve a problem that comes up in game programming. Also, you'll get to practice performing the simplex method on a number of LP instances where you can verify the correctness of the results.
Suppose you have two polygonal objects in a 2D game, as follows. The first object has its center at the point c = cx , and has vectors a , a , and a from c to its three vertices
cy
(the technique works for any number of vertices). Then it turns out that every point in the first object can be expressed as
c + µ1a1 + µ2a2 + µ3a3,
where µ1 + µ2 + µ3 = 1 and all the µj values are nonnegative (this is a standard convex combination idea). In addition, let's say that this object is moving along a straight line with velocity vector v = vx , so that at any time λ (with λ 0, of course) the center is
vy
at c + λv.

Exercise 28
Formulate and solve the LP produced by the transportation problem with this data (attached):

Put your optimal point in this chart and check that the objective function value matches the direct calculation and that the rows and columns add up to the targets.

Exercise 29
Implement the small instance of the maximum network flow problem shown below as an LP instance and solve it using ManualSimplex. Turn in a graph showing the optimal amount of flow along each edge.
Assume, obviously, that vertex 1 is the source and vertex 6 is the sink, and that the numbers written along the edges are the capacities of the edges.

Exercise 30
Perform the branch and bound algorithm for the 0-1 knapsack problem similarly to the previous example, on the instance given below.
For convenience, you probably will want to actually draw the tree, noting that at any moment the nodes that have no children are the ones that would be in the priority queue, and the node with the best bound can be found by simply scanning those nodes.

Exercise 31
Your job on this Exercise is to write code in Java to implement the branch and bound algorithm for the 0-1 knapsack problem.
Create a Java application named Ex31 that will ask the user for the name of a data file, read the information from the data file, and then solve that instance of the 0-1 knapsack problem using the branch and bound method, following exactly the algorithm demonstrated in the previous example-without an explicit tree.
The data file must contain the capacity of the knapsack, followed by the number of items, followed by the profit and weight information (on one line) for each item. All these values are integers. You may assume that the items are sorted in order from most profitable per unit of weight to least profitable.
As a small but important requirement to avoid irritating me, you must label the items starting with 1, rather than 0.

Exercise 32
Your job on this Exercise is to solve some fairly large (n = 30) instances of ETSP using
AutoHeuristicTSP.

For an instance of ETSP with n = 30, the dynamic programming approach would take Θ(n22n-1) or so steps, which is some multiple of 900 billion steps, requiring a table with roughly a billion rows and 30 columns).
So, it should be fairly impressive that our new approach will be able to solve such problems quite easily!
To do this, just run AutoHeuristicTSP with the desired data file as input, and interactively do cuts and branches until the optimal tour is found.
First solve the instance bad1, drawing by hand some (until you are sure you understand how to draw the entire tree, and get tired) of the branch and bound tree following the style used on page 9.16 (AutoHeuristicTSP keeps track of everything for you, so you don't really need to draw the tree to solve the instance, but I'm requiring it to force you to practice what you'll need for Test 3).
Then, solve the instance bad2.

For both instances, report the optimal tour total length and the branching choices that led to the node for this optimal tour in the branch and bound tree.
I came up with bad1 and bad2 by using RandomTestingHeuristicTSP with n = 30 to generate random test instances with 30 points and picking ones that looked hard.

Exercise 33
Your job on this Exercise is to demonstrate Christofides' algorithm on the instance of ETSP with these 12 points:
1: (64, 65)
2: (7, 71)
3: (8, 55)
4: (51, 57)
5: (55, 56)
6: (80, 75)
7: (3, 84)
8: (17, 84)
9: (72, 72)
10: (65, 31)
11: (58, 10)
12: (8, 30)

Your demonstration will be mostly graphical, drawing on the diagram on the next page the edges of the minimum spanning tree T obtained by Prim's algorithm, the set O of vertices with an odd number of edges of T connected to them, the edges in the minimum weight matching M of the points in O, a list of vertices that form an Eulerian traversal of the vertices, and finally the list of vertices for the tour obtained by this algorithm.

You must also compute the total length of this tour, and compare it to the optimal tour (obtained by using one of our earlier algorithms). Verify that this tour has total length less than or equal to 1.5 times the optimal tour's total length.

Attachment:- exercies.zip