Home Page > > Details

Help With MA569 asp Programming

MA569 Summer I: Homework #2 
Instructions: Solution should be written neatly and legibly. Since we moved online, it will be hard 
to work with others, but you are encouraged to work with others on the assignment, but you should 
write up your own solutions independently. You should reference all of your sources, including your 
collaborators. 
1. Two people have decided to go into business together selling crabs that they catch along the 
Baltimore coast line After they catch the crabs, they bring them back to their processing plant 
where they are cleaned, clawed, andwrapped to go. Following this process, they ship the crabs 
to n different seafood restaurants located in a 10 mile × 10 mile square. Each restaurant i has 
two coordinates (ai1,ai2) and demands di crabs. 
Wewillmeasure the distance between the processing plant and the restaurant using the “Man- 
hattan metric” (which is sometimes called the “taxicab metric”). That is, all streets go either 
North-South or East-West, so the distance from location (xi , yi ) to (x j , yj ) is |xi − x j |+ |yi − yj |. 
The unit transportation cost of shipping a crab is $c per mile (so it costs $m c per mile to ship 
$m crabs). 
Their goal is to locate the processing plant at a point (x , y ) inside the 10×10 square tominimize 
the total transportation costs. 
(a) Formulate the problem of determining where the processing plant should be located as 
amathematical program tomeet all demands whileminimizing the transportation costs. 
(Your answer to this part does not need to be a linear program.) (Hint: use absolute value.) 
(b) Convert the mathematical program of part (a) to a linear programming problem. 
(c) It is claimed that there is always an optimal solution to the linear programming problem 
in which the processing plant is located at one of the restaurants. Show that this claim is 
false. 
(d) It is claimed that there is always an optimal solution to the linear programming problem 
in which the processing plant is located at the x -coordinate of one restaurant and the y - 
coordinate of one restaurant (they do not need to be the same restaurant). Show that this 
claim is true. 
2. Willy Wonka’s Candy Company produces three types of candy: 
• Wonka Bars 
• Bottle Caps 
• Giant Sweet Tarts 
In order to produce the different types of candy, Willy can run three different production pro- 
cesses as described below. Each process involves blending different types of sugars in theMag- 
ical Factories Mixer. 
Provess 1: Running Process 1 for one hour: 
Costs: $5 
Requires: Two barrels of Sugar type A and three barrels of sugar type B 
Output: TwoWonka Bars and One packet of Bottle Caps 
Provess 2: Running Process 2 for one hour: 
Costs: $4 
Requires: One barrel of Sugar type A and three barrels of sugar type B 
Output: Three packets of Bottle Caps 
Provess 3: Running Process 3 for one hour: 
Costs: $1 
Requires: Three barrels of Sugar type A and three packets of Bottle Caps 
Output: TwoWonka Bars and one packet of Giant Sweet Tarts 
Each week we can purchase: 
• 200 barrels of sugar type A and $2 Per Barrel 
• 300 barrels of sugar type B at $3 Per Barrel 
Assume that they can sell everything that they can produce. 
• Wonka Bars are sold at $9 per bar. 
• Bottle Caps are sold at $ 10 per packet. 
• Giant Sweet Tarts are sold at $24 per packet. 
Assume that 100 hours of mixing time are available. 
(a) Formulate a Linear Programming Problem whose solution will maximize Willy Wonka’s 
profits. 
(b) Assume that instead of having 200 barrels of sugar type A and 300 barrels of sugar type B 
available that you can order a total of 500 barrels. Show how to modify your Linear Pro- 
gramming formulation in part (a) to account for this revised problem. 
(c) Suppose that instead of selling three candies separately, they can only be sold as part of a 
box consisting of one Wonka Bar, two packets of Bottle Caps, and one pack of Giant Sweet 
Tarts. Each Wonka Box sells for $54. Modify your Linear Programming formulation in 
part (a) to model this new scenario. Assume that you again have 200 barrels of sugar type 
A and 300 barrels of sugar type B . (Hint: You may find it helpful to start by creating a 
mathematical program where the objective function is a minimum of linear functions, and 
then converting to a linear program.) 
3. Suppose that the following tableau occurs while solving a linear program in standard form us- 
ing the simplex algorithm, where A,B ,C ,D ,E ,F,G and H are all constants: 
z x1 x2 x3 x4 s1 s2 s3 
1 A 0 0 B C D 0 E 
0 F 0 1 1 1 3 0 4 
0 −2 1 0 2 G −1 0 2 
0 −1 0 0 0 H 1 1 3 
(a) What is the current CPF? 
(b) For each of the following situations, give values for A through H that would make the given 
condition true. 
i. The current CPF is a unique optimal solution. 
ii. The current CPF is not optimal, the only candidate for entering the basis is s1, and when 
the next iteration is performed, x3 will leave the basis. 
iii. The current CPF is not optimal, the only candidate for entering the basis is x1, and the 
the problem is unbounded from above. 
iv. The current CPF is optimal, and there exists exactly one other CPF that is also optimal. 
v. The current CPF is optimal, and there also exists an extreme ray of alternative optimal 
solutions. 
4. Consider the following Linear Programming Problem: 
Objective: Maximize 50x1 + 25x2 + 20x3 + 40x4 
Subject to: 2x1 + x2 ≤ 30 
x3 + 2x4 ≤ 20 
x1, x2, x3, x4 ≥ 0 
Work through the simplex algorithm step by step to find all of the optimal solutions. Show the 
steps of the simplex algorithm — you do not need to write out every row operation, but you should 
write the tableau for each iteration and indicate which variable is enter the basis and which 
variable is leaving the basis. 
5. A toy companyproduces three typesof toys—train, trucks, andcares. Theyhave threedifferent 
machines that are used to make the toys: Machine A, Machine B , and Machine C . 
• Creating a toy train requires 1 minute on Machine A, 3 minutes on Machine B , and 1 
minute onMachine C . 
• Creating a truck requires 2 minutes onMachine A and 4 minutes onMachine C . 
• Creating a toy car require 1 minute onMachine A and 2 minutes onMachine B . 
Machine A can be used for total of 430 minutes each day; machine B can be used for a total 
of 460 minutes each day; and machine C can be used for total of 420 minutes each day. The 
revenue for creating a train is $3; the revenue for a truck is $2; and the revenue for a car is $5. 
(a) Formulate a linear programming problem to maximize the revenue for the toy company. 
(b) Use the simplex algorithm to solve the linear programming problem. Show the steps of the 
simplex algorithm — you do not need to write out every row operation, but you should write 
the tableau for each iteration and indicate which variable is entering the basis and which 
variable is leaving the basis. 
6. Consider the following linear program: 
Objective: Minimize 2x1 − 3x2 
Subject to: x1 + 2x2 ≤ 12 
2x1 + x2 ≤ 8 
−x1 + x2 ≤ 12 
x1 ≥ −5 
(a) Graph the feasible region, and determine the coordinates of the vertices. 
(b) Work through the simplex algorithm step by step to find the optimal solutions. Show the 
step of the simplex algorithm. 
7. Consider the following linear program: 
Objective: Maximize 2x1 + 5x2 + 3x3 
Subject to: x1 − 2x2 + x3 ≥ 20 
2x1 + 4x2 + x3 = 50 
x1, x2, x3 ≥ 0 
Work through the simplex algorithm step by step to find the optimal solution. Show the steps of 
the simple algorithm. 
8. Consider the three-dimensional polytope shown below: 
The point J lies at the origin, and the points A, B and C lie on the x−, y− and z−axes, respec- 
tively. The coordinates of the vertices are given in the following table: 
A (1,0,0) F (0,1,1) 
B (0,1,0) G (1,1,0.5) 
C (0,0,1) H (0.5,1,1) 
D (1,1,0) I (1,0.5,1) 
E (1,0,1) J (0,0,0) 
Suppose that this polytope is the feasible region for some linear programming problem. 
(a) Suppose that the simplex algorithm for the linear programming problem starts at J and 
that the optimal solution occurs at H . For each of the following paths of vertices, state 
whether they could be legitimate paths for simplex algorithm. If it is not a possible path for 
the simplex algorithm, explain why not. 
i. J → B → F →H 
ii. J →D →G →H 
iii. J → A→ B → F →H 
iv. J → A→D → B → J →C → F →H 
(b) Find an objective function Z = Ax +B y +C z so that the points A,B ,D and J are all max- 
imal solutions, but the point (0,0,1) is not maximal. 
(c) Find an objective function Z = Ax +B y +C z so that the points G ,H and I are all maximal 
solutions, but the points (0,0,1) is not maximal. 
(d) Determine the inequalities that describe the feasible region. 
9. Consider the following linear program: 
Objective: Maximize 3x1 + 2x2 + 5x3 
Subject to: 3x1 − x2 − x3 ≤ −6 
2x1 − x2 − x3 ≥ 3 
2x1 − 3x2 + x3 ≥ 4 
x1, x2, x3 ≥ 0 
Work through the simplex algorithm step by step to show that there are no feasible solution to 
this linear program. 
10 
10. During the simplex algorithm a degenerate basic variable is a basic variable that is equal to 0. 
(a) Give an example of a tableau for which the following holds: 
• There is a degenerate basic variable. 
• There is a non-basic variable in the Z row that has a zero that has a zero coefficient. 
• The current CPF is the unique optimal solution (but there may more than one optimal 
tableau). 
(b) Give an example of a tableau for which the following holds: 
• There is a degenerate basic variable. 
• There is a non-basic variable in the Z row that has a zero coefficient. 
• The linear program has multiple optimal solutions, but only one CPF. 
11 
11. The Gemstone Tool company produces wrenches and pliers. They are both made from steel, and 
the process involves molding on a Molding Machine, and assembling on an Assembly Machine. 
The amount of steel used and the daily availability of steel are shown in the following table. The 
table also shows the amount of machine time needed for each product as well as the availability 
of machine time. 
Wrenches pliers Availability 
Steel (lbs.) 1.5 1.0 27000 lbs./day 
Molding Machine (hrs.) 1.0 1.0 21000 hours/day 
Assembly Machine (hrs.) 0.3 0.5 9000 hours/day 
There is demand for at most16000wrenches and for at most15000pliers. For every1000wrenches 
that are sold, the company makes $100; for every 1000 pliers which are sold, the company make 
$130. 
(a) Formulate a linear program to determine the optimal level of production for wrenches and 
pliers that maximized the earnings. 
(b) Solve the problem using Excel. What is the optimal solution to the linear program? What 
is the optimal objective value? 
(c) Use Excel to create the Sensitivity Report. Print out the Sensitivity Report, and include it 
with your homework. Use the sensitivity report to answer the following question: 
i. Suppose the amount of steel available increases to 28000 lbs./day. What is the new 
optimal objective value? 
ii. Suppose the Molding Machine changes to only being available for 20000 hours/day. 
What is the new optimal objective value? 
iii. Supoose that the demand for pliers increases to 18000 pliers. What is the new optimal 
objective value? 
iv. The company could purchase additional Assembly Machines to increase the amount 
of Assembly Machine hours available each day. How much should they be willing to 
spend to add an additional 100 hours of Assembly Machine time? 
v. Suppose that the price of wrenches increases, and that as a result, for every1000wrenches 
sold, the company make $110. Does this change the optimal solution? What is the new 
optimal objective value. 
vi. Suppose that demand for wrenches decreases to A wrenches. For what values of A is the 
current solution is optimal? 
12 
(d) Suppose that the company institutes a new policy — they must produce at least as many 
wrenches as pliers. Does the optimal solution changes? Why or why not? 
13 
12. Consider the following linear programming problem: 
Objective: Maximize 5x1 + 3x2 
Subject to: 2x1 + 3x2 ≤ 12 
2x1 + x2 ≤ 6 
x1, x2 ≥ 0 
(a) Sketch the graph of the feasible region for this linear programming problem, and determine 
the coordinates of the vertices. 
(b) Create the dual linear programming problem. 
(c) Sketch a graph of the feasible region for the dual problem, and determine the coordinates 
of the vertices. 
(d) Use the simplex algorithm to solve the primal problem (that is, the original problem, not 
the dual problem). 
(e) Identify the sequence of CPF solutions that the simplex algorithm uses to find the optimal 
solution. 
(f) Use the final tableau from part (d) to determine the optimal solution to the dual problem. 
(g) Each iteration of the simplex algorithm also corresponds to a point in the dual problem (al- 
though the point in the dual problem will not be a feasible solution until the final tableau). 
At each iteration, the coefficients of the slack variables in the top row of the tableau cor- 
respond to a point in the dual problem. Identify this sequence of points, and mark these 
points on your graph in part (c). 
14 
13. Consider the following linear program: 
Objective: Maximize 3x1 + 5x2 + 2x3 
Subject to: −2x1 + 2x2 + x3 ≤ 5 
3x1 + x2 − x3 ≤ 10 
x1, x2, x3 ≥ 0 
(a) Determine the optimal solution and optimal objective value to the linear program (using 
any method you want). 
(b) If we added the constraint 2x1+ x2+ x3 ≤ 70, would the optimal solution change? Explain 
your answer without re-solving the linear program. 
(c) What is the dual linear program? 
(d) Determine the optimal solution and optimal objective value to the dual linear program 
(Using any method you want). 
(e) Suppose we add an new variable x4 to the original linear program as follows: 
Objective: Maximize 3x1 + 5x2 + 2x3 + 20x3 
Subject to: −2x1 + 2x2 + x3 + x4 ≤ 5 
3x1 + x2 − x3 + 3x4 ≤ 10 
x1, x2, x3, x4 ≥ 0 
How does the new variable change the dual program? 
(f) Does the new variable changes the optimal solution to the dual program? Explain your 
answer without solving the new dual program. 
(g) Does the new variable changes the optimal solution to the original linear program? Explain 
you answer without solving the new primal program. 
15 
Contact Us - Email:99515681@qq.com    WeChat:codinghelp
Programming Assignment Help!