Relations Between Primal And Dual

2y ago
23 Views
3 Downloads
261.76 KB
11 Pages
Last View : 7d ago
Last Download : 4m ago
Upload by : Harley Spears
Transcription

Relations between Primal and DualIf the primal problem isMaximize ct x subject to Ax b, x 0then the dual isMinimize bt y subject to At y c (and y unrestricted)Easy fact:If x is feasible for the primal, and y is feasible for the dual, thenct x bt ySo (primal optimal) (dual optimal) (Weak Duality Theorem)Much less easy fact: (Strong Duality Theorem)If one of the primal and the dual have finite optima, they both have and(primal optimal) (dual optimal)1

The “Inverse Matrix”In the initial simplex tableau, there’s an identity matrix. At a later simplextableau, the “inverse matrix” is the matrix occupying the same space asthat original identity matrix.The inverse matrix conveys all information about the current state of thealgorithm, as we will see.2

3

Computing dual values from Inverse MatrixIf we have reached the optimal primal tableau, these methods give theoptimal dual values; at earlier iterations, they give a certain “dual” of thecurrent basic feasible solutionMethod 1:Row vector of dual values Row vector of original objective values ofcurrent basic variables (listed in order they appear along basic column ofcurrent tableau) X current inverseMethod 2: (see textbook for this)Write wi for initial basic variable in row i.Value of dual variable yi current z-row coefficient of wi originalobjective coefficient of wi4

Example — Primal problemMinimize 4x1 2x2 x3subject tox1 x2 2x3 32x1 2x2 4x3 5x1 , x2 , x3 0.In standard form:Minimize 4x1 2x2 x3 0s1 M R 0s2subject tox1 x2 2x3 s1 R 32x1 2x2 4x3 s2 5x1 , x2 , x3 , s1 , R, s2 0.5

Example — The dualMaximize 3y1 5y2subject toy1 2y2 4y1 2y2 22y1 4y2 1 y1 0, i.e. y1 0y1 My2 0Note that the addition of the artificial variable to the primal adds a newconstraint to the dual: y1 M . But since we imagine M to be very large,this effectively puts no new constraint on y1 . For convenience, we’ll takeM 100.6

Example — initial tableaux1x2x3s1Rs2solnz-row9698201 10000300R112 1103s22 240015Inverse matrix is boldedCurrent solution: R 3, s2 5, z 300. Feasible, but not optimalCurrent “dual solution”: (y1 y2 ) (100 0) 1001 (100 0)i.e. y1 100, y2 0, zdual 300We will see later that this is “optimal but not feasible”.7

Example — first iterationx1z-row 4.5x2x3s1Rs2soln198.50 1000 50.2548.75R020 11 .5.5x3.5 .5100.251.25Inverse matrix is boldedCurrent solution: R .5, x3 .25, z 48.75. Feasible, but not optimalCurrent “dual solution”: (y1 y2 ) (100 1) 1 .50.25i.e. y1 100, y2 50.25, zdual 48.75Again, “optimal but not feasible”.8 (100 50.25)

Example — optimal tableaux1z-row 4.5x2x3s1R00 .75s2 99.25 .625soln .875x2010 .5.5 .25.25x3.501 .25.25.1251.375Inverse matrix is boldedOptimal solution: x2 .25, x3 1.375, z .875.Optimal dual solution: (y1 y2 ) (2 1) .5 .25.25.125 (.75 .625)i.e. y1 .75, y2 .625, zdual .875This is readily checked to be feasible and optimal for dual9

Getting whole tableau from Inverse (and initial data)Constraint columns:New constraint column current inverse X original constraint columnObjective coefficients:Objective coefficient (z-row entry) of variable xj Left hand side of jthdual constraint (evaluated at current “dual solution”) - right hand side ofjth dual constraint10

Example — first iteration of previous problemx1z-row 4.5x2x3s1Rs2soln198.50 1000 50.2548.75R020 11 .5.5x3.5 .5100.251.25We look at (bolded) x2 constraint column and objective entry 1 .512 0 .25 2 .5(Inverse X original x2 column new x2 column)Coefficient of x2 in z-row is computed by(y1 2y2 ) 2 ([100] 2[ 50.25]) 2 198.5using values of y1 , y2 computed earlier.11

Relations between Primal and Dual If the primal problem is Maximize ctx subject to Ax b, x ‚ 0 then the dual is Minimize bty subject to Aty ‚ c (and y unrestricted) Easy fact: If x is feasible for the primal, and y is feasible for the dual, then ctx bty So (primal optimal) (dual optimal) (Weak Duali

Related Documents:

Primal-Dual: Hitting Sets Primal-Dual: Steiner Trees Primal Dual: MCF Jochen Könemann, September 25, 2004 Group Strategyproof Mechanisms for Steiner Forests - p. 9/44 Primal-dual technique: Main Ideas Construct integral primal and dual feasible solution at the same time: x and y Show that X j xj X i yi For some . Prove a worst-case upper-bound .

BEEF Primal Cut Weight Range Guide PRIMAL CARCASE - PRIMAL CUT WEIGHT RANGES CUT * H.A.M. NO. 160-180kg 180-220kg 220-260kg 260-300kg This information is to be used as a GUIDE ONLY. * H.A.M. - Handbook of Australian Meat Reference Cut Item and Code Number. GUIDE TO CARCASE BODY YIELD PRIMAL CUTS ACCOUNT FOR : 60% TRIMMINGS :

THE PRImAL FAT bURNER mEAL PLAN AND RECIPES 205 LUNCH: Thai Salad with Spicy Dressing DINNER: Cumin Pork Stir-Fry, Primal Cauliflower Fried Rice DAY 10 BREAKFAST: Primal Breakfast "Fondue" with coconut oil or Primal Gaucho Chimichurri LUNCH: Amazing Coconut Thai Soup DINNER: Carnitas Salad DAY 11 BREAKFAST: Breakfast Sausage Patty with Sautéed Greens, 2 to 3

Then λT b cT x Proof: λ T b λ Ax cT x Since x 0, we have λT A cT Maximum of dual minimum of primal (or) cost in the dual is never above the cost in the primal Fortunately for LP, gap 0 max. dual min. primal Suppose x and λare feasible. If λT b cT x, then x and λare optimal Proof:

PRIMAL It has one main coin and two tokens native to the Primal chain. It is the most unique cryptocurrency and the first non -fiat backed stable cryptocurrency with little to zero volatility. Prime: The code is PRM. It is the main coin and availabl e to the public powered by the Primal Chain.

with a basic Primal Fuel smoothie to create a wide variety of shake flavors. For a basic Primal Fuel smoothie, shake or blend 2 scoops (44 g) of Primal Fuel with 1 - 1 ¼ cups of cold water, or ½ cup ice (about 5 ice cubes) and ½ cup of cold water. For all recipes with a stir icon, simply shake or stir the ingredients together.

The Primal Blueprint 21-Day Total Body Transformation: Unabridged recording of the entire book, 5.5 hours in dura-tion. The Primal Connection: Unabridged re-cording of the entire book, 6 hours in duration. Digital Books Digital copies in PDF format of five popu-lar Primal Blueprint

American Gear Manufacturers Association franklin@agma.org June 15, 2012. at Happened in the 2011 US Gear Market? mand for gears was up sharply in the US because of the mendous investment in “traditional” capital equipment. en though gear demand was up 28%, domestic shipments rose only %. The gap was filled by record gear imports (in terms of levels rowth), a 33% rise. ports were due to a .