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

Design a questionnaire that assesses peoples eating habits

Design a questionnaire that assesses people's eating habits. Your questions could address topics such as what they eat, when they eat, how much they eat, with whom they eat, where they eat, how heal they their eating hab ...

Psy1879 movie worksheet awakenings name

PSY1879 Movie worksheet: "Awakenings" Name _______________________ "Awakenings" is a 1990 film based on Dr. Oliver Sacks' 1973 book by the same title. The book is a true biographical story of a British neurologist (Olive ...

Assignmentlength 1500 -1750 wordsa mastermind behind 911

Assignment Length: 1,500 -1,750 words A mastermind behind 9/11, Khalid Sheik Mohammad (KSM), was captured in Pakistan in March of 2003. Immediately following his capture, KSM was subjected to a series of controversial in ...

Doubt uncertainty and the examined lifedoubt has always

Doubt, Uncertainty and the Examined Life Doubt has always been fundamental to philosophy. Plato says that the unexamined life is not worth living. The skeptics counseled doubt as a way of life. For Descartes doubt presen ...

Please respond to the following determine two ways to apply

Please respond to the following: Determine two ways to apply what you learned in this course in your current or a future position. Examine how your own theories of criminal justice have matured or changed since the begin ...

For your initial post this week imagine you are a candidate

For your initial post this week, imagine you are a candidate for the White House and present to the class at least one executive action you would take on your first day serving as president. (Please Note: it is not accep ...

Write a paper of 1000-1250 words regarding the statistical

Write a paper of 1,000-1,250 words regarding the statistical significance of outcomes as presented in the Messina et al. article, "The Relationship Between Patient Satisfaction and Inpatient Admissions Across Teaching an ...

Using an essay format please read and answer the questions

Using An Essay Format, Please Read And Answer The Questions Below In Complete Detail. Failure To Answer All Parts Of Each Question Selected Will Result In A Loss Of Possible Points Awarded. Thus, Skimpy Answers Reflectin ...

Find a plume find a venthow do researchers find

Find a Plume, Find a Vent How do researchers find deep-­-sea hydrothermal vents that are over 2000 meters (more than a mile and a half) below the ocean surface and are very tiny when compared with the vast ocean? In this ...

A random selection of files from a student counseling

A random selection of files from a student counseling center revealed the following reasons why college students seek services: Mental health issues 25 Learning/school issues 15 Relationship issues 5 Other 5 What does it ...

  • 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

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

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen