Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Homework Help/Study Tips Expert

problem 1: Duality

Recall the max flow problem:

1907_duality.jpg

max x2t + x3t
xs1 = x12 + x13
xs2 + x12 = x2t
x13 = x3t

0 ≤ xs1 ≤ 2
0 ≤ xs2 ≤ 3
0 ≤ x12 ≤ 3
0 ≤ x13 ≤ 4
0 ≤ x2t ≤ 2
0 ≤ x3t ≤ 1

A) prepare the dual of the above max-flow problem.

B) Solve both problems with AMPL, and for each print the values of the variables and the values of the dual variables (if a problem has a constraint c1, its dual value can be displayed with the command “display c1.dual;”). Verify that the numbers correspond between primal and dual, and that the optimal solution of the primal and the dual is in accordance with duality.

C) Show the minimum cut that results from solving the dual problems.

D) Consider replacing the objective function in the max cut problem with max xs1 + xs2 which gives an equivalent formulation of the max-flow problem. How does the dual formulation change? describe why it is equivalent to the first dual problem.

problem 2: Complementary slackness and duality

Consider the following LP problem:

min x1 + 3x2 + x3 − x4
s.t. x1 + x2 + x3 + x4 ≥ 0
x1 + x2 − x3 − x4 ≥ 1
x2, x3 ≥ 0 x1, x4 ≤ 0.

A) Unique primal-dual solutions.

• Find a feasible solution (by trying a few guesses) and compute its associated value of the objective function, zprimal.

• prepare the dual.

• Find a feasible solution to the dual (just pick one) and compute its associated value of the objective function, zdual, and check, according to weak duality, that it is not less than zprimal.

• Solve the dual through the graphical method.

• After finding the optimal value of the dual variables, use complementary slackness to find the optimal value of the primal variables.

• Solve both primal and dual problems in AMPL. Print out the solutions.

B) Multiple primal solutions.

• Change the right hand side of the second constraint to -1. How would the dual change?

• Solve the new dual problem graphically.

• Again use complementarity to derive the primal solution. Do you get a unique primal solution or do you get more than one? Can you find all primal optimal solutions? (Hint: all feasible solutions that satisfy complementarity are optimal).

• Solve both primal and dual problems in AMPL. Print out the solutions.

• For the primal problem which of the multiple solutions do you obtain? Can you modify the primal problem a little to obtain a different solution from the optimal set?

problem 3: Linear Programming

Consider the following optimization problem:

min x
s.t. x ≥ max{a1, a2, . . . , an}

Reprepare this problem as a Linear Programming Problem. What is the solution of this problem? prepare the dual of this problem. From duality theory and complementary slackness give a simple formula for the optimal solution of the dual.

Homework Help/Study Tips, Others

  • Category:- Homework Help/Study Tips
  • Reference No.:- M91167

Have any Question? 


Related Questions in Homework Help/Study Tips

Local government leaders have asked you to provide

Local government leaders have asked you to provide information and recommendations for increasing sustainability in the community.  Perform an initial search to learn about green initiatives for a city in your area.  Cre ...

1 gospel of thomas saying 96 jesus said the kingdom of the

1. Gospel of Thomas, Saying 96 Jesus said, "The kingdom of the Father is like a woman. She took a little bit of yeast. She hid it in dough and made it into huge loaves of bread." Question: A saying of Jesus similar to th ...

Divine roles across culturespart i - select one common

Divine Roles Across Cultures Part I - Select one common divine role that recurs in world mythology. Possible options of divine roles include the following: father or mother divinities, divinities of war, home or hearth d ...

Work for tutor ann harris only write a 1050- to 1400-word

Work for tutor Ann Harris only Write a 1,050- to 1,400-word paper in which you examine the role of industrial/organizational psychology in selecting and training employees. In your examination, address the following: Cho ...

A 15-gram sample of neon is placed in a sealed container

A 15-gram sample of neon is placed in a sealed container with a constant volume of 8.5 liters.  If the temperature of the container is 27ºC, which of the following expressions gives the correct pressure of gas?  The idea ...

Discussioncommunity efforts and managing public relations

DISCUSSION Community Efforts and Managing Public Relations (PR)" Please respond to the following: • You are a new PR intern at Apple. Apple is donating 200 iPads to a local inner-city school to promote technology in educ ...

You are a new physician setting up your own practice in a

You are a new physician setting up your own practice in a new town. You are researching the different MCOs offered in your area and are considering becoming a physician for one of these networks. You have also invited th ...

Please respond to the question below with a minimum of 200

Please respond to the question below with a minimum of 200 words. Discuss how a nurse's previous abusive relationships might negatively or positively affect his or her practice with victims of domestic violence. Support ...

Discussion question review the following research

Discussion Question Review the following research questions. 1. Is the use of soap and water or alcohol-based rubs more effective in preventing nosocomial infections? 2. How effective are anti-depressive medications on a ...

You studied the topic of eminent domain which is the power

You studied the topic of eminent domain, which is the power to take private property, without permission from the owner, for public use by a state, municipality or private person or authorized corporation, following the ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro