Ask Question, Ask an Expert


Ask Homework Help/Study Tips Expert

problem 1: Duality

Recall the max flow problem:


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

Select a law that has an impact on the health care industry

Select a law that has an impact on the health care industry. Examples of such laws may include access to care, discrimination, health care privacy and security, employment, etc. Write a 1,750- to 2,100-word paper in whic ...

Discussion anaphylactic shockthe treatment of anaphylactic

Discussion : Anaphylactic Shock The treatment of anaphylactic shock varies depending on a patient's physiological response to the alteration. Immediate medical intervention and emergency room visits are vital for some pa ...

Health care information systems are important in dispensing

Health Care Information Systems are important in dispensing of information throughout the organization. You will develop a research paper on a health care technology that has become essential to the sharing of informatio ...

Assignment applicationusing the Assignment: Application: Using the

Assignment: Application: Using the Data/Information/Knowledge/Wisdom Continuum Have you ever gone online to search for a journal article on a specific topic? It is amazing to see the large number of journals that are ava ...

Assessment task seven pt session one review-at the

Assessment Task Seven PT Session One review- At the completion of the session you are required to gain feedback from the client you have just trained. You are required to: Obtain feedback from clients on their own person ...

Frist paper one page 15 spacing1 identify a societal

Frist paper (one page 1.5 spacing) 1. Identify a societal problem that is developing due to trends in society 2. Discuss the impact of this social trend. 3. What type of innovation and organization can be created to help ...

Artart criticism is the process of gathering facts and

Art Art criticism is the process of gathering facts and information about a work of art and the artist to describe, analyze, interpret, and evaluate art. For this assignment, you will choose one work of art from the foll ...

Think piecethis assignment is a think piece which is an

Think Piece This assignment is a "think piece," which is an essay that requires you to interact with a subject and develop your own interpretation based on that experience. After your initial analysis of a specific topic ...

Assignmentthis week we explored the challenges of cost and

Assignment This week we explored the challenges of cost and access as it relates to health care. (1) What factors have led to increasing health care costs? (2) What are some ways to control these costs? As you discuss so ...

Cultural activity reportas a way of experiencing the

Cultural Activity Report As a way of experiencing the Humanities beyond your classroom, computer, and textbook, you are asked to do a certain type of "cultural activity" that fits well with our course and then report on ...

  • 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

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate