Mathematics Assignment Help
Each problem is worth 8
test points (purely for assigning a score out of 100% on the test), and some
problems may have several unrelated parts worth the points indicated.
Please write your
answers on these sheets or your own paper and send me either one PDF file for
your entire test or a separate file for each problem.
You may use any of our
course materials: the written chapter documents, the videos, and your Exercise
work. Other than accessing those allowed materials, you may not run any
programs, including any Web browser or communication software, to help you on
any questions, or communicate with anyone other than me about the test
questions or course material. Except, you may use a calculator or spreadsheet
program strictly to perform arithmetic, and, of course, several problems
explicitly ask you to use
Manual Simplex or Auto Heuristic TSP, so of course
on those problems you may use your computer to run those programs, and a text
editor to generate the necessary input files.
For each tableau, state one of the answers in the
chart below, and then write the additional information requested, depending on
the answer.
Instructions for Problems 1 and 2
On the next two pages you will find several simplex
method tableaux (four for each of Problems 1 and 2). These tableaux are not in
any particular order, and they are not necessarily for the same linear
programming instances.
Be sure to both write the “answer” and whatever
additional work is required—you will receive no credit on a part if you just
write the “answer” without the additional information, even if the answer is
correct.
Categorize each of the following Phase 1 tableaux
according to the directions (assume that the artificial variables are named aj
):
Categorize each of the following Phase 2 tableaux
according to the directions:
Consider this instance of an optimization problem:
a. [4
points] 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:
[4
points] 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)?
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.
USA 
India