Derive the dual of the new lp

Assignment Help Mathematics
Reference no: EM13967844

1. Give an example of a dictionary for which the current basic feasible solution is optimal and yet the coefficients of the non-basic variables in the z row are not all negative.

2. Take your final dictionary to your Quiz 2 after corrections if any are required (if you haven't picked it up remember to do so) and verify the revised simplex formulas. Namely identify B, AN, cB, cN, xB, xN and then compute B-1 and the z row using z = cBT B-1b + (cNT - cBTB-1AN )xN and then the remaining equations as xB = B-1b - B-1ANxN.

If you move the non basics to the left of the equations, the matrix B-1 can be read off as the coefficients of slack variables. Of course you don't have to change the dictionary and can do this directly but then the columns are either the negative of the coefficients of a slack variable if it is non-basic variable (recall xB = B-1b - B-1AnxN ) and an appropriate column of a single 1 if the slack variable is a basic variable.

3. Theorem 5.5 is taken from page 65-66 of V. Chvatal's book on Linear Programming. Consider the LP:

maximize ∑nj=1 cjxj

subject to ∑nj=1 aijxj ≤ bi (i = 1, 2, . . . m)

xj ≥ 0 (j = 1, 2, . . . , n)

Theorem 5.5. If (5.24) has at least one non-degenerate basic feasible optimal solution, then there is a positive s with the property: If |ti| ≤ s for all i = 1, 2, . . . , m, then the problem

maximize ∑nj=1 cjxj

subject to ∑nj=1 aijxj ≤ bi + ti (i = 1, 2, . . . m) (5.25)

xj ≥ 0 (j = 1, 2, . . . , n)

has an optimal solution and its optimal value equals

z∗ + ∑mi=1 yiti

with z∗ standing for the optimal value of (5.24) and with y1, y2, . . . , ym standing for the optimal solution of its dual.

Now consider the following LP

max 12x1 +20x2 +18x3
       4x1 +6x2 +8x3 ≤ 600
       x1 +(7=2)x2 +2x3 ≤ 300  x1, x2, x3 ≥ 0
       2x1 +4x2 +3x3 ≤ 550

The final dictionary is:

455_Final dictionary.png

Does Theorem 5.5 apply here?

For what value of s (choose the largest possible for this particular data!) is the theorem true? In this case I will offer you an hint about computing ∈. Hint: If you have been given an inequality 3t1 - 5t2 ≤ 5 which must hold for any choices t1, t2 satisfying -s ≤ t1 ≤ s and -s ≤ t2 ≤ s, then we deduce that s ≤ 5/8.

4. Consider our two phase method in the case that the LP is infeasible. We begin with the primal LP

max    z
      Ax ≤ b .
       x ≥ 0

We introduce an artificial variable x0 and obtain the new LP (in Phase 1)

max -x0
          x0

[-1| A] x ≤ b,

x0 ≥ 0, x ≥ 0,

where (-1) is the vector of -1's and we use [-1 | A] to denote the matrix obtained from A by adding one more column (of all -1's) on the left. We assume the maximum value of the objective function in the new LP is strictly negative. (In general this would depend on whether the original LP is infeasible; we assume the original LP is infeasible)

a) Derive the dual of the new LP. Verify that an optimal dual solution will verify (certify?) that the inequalities above do not have any feasible solution. Namely explain why

yT A ≥ 0T , y ≥ 0 , b.y < 0 will show that there is no feasible solution to the original LP.

b) Verify that for an optimal dual solution (the magic coefficients!) y = (y1, y2, . . . , ym)T we have y1 + y2 + ......+ ym = 1. (You may note that in assignment 1, the sum was 1/2 + 1/3 + 1/6 = 1).

a) Extend the standard theorem of the alternative as follows.

Let A be an m × n matrix and b be an m × 1 vector. Let u be an n × 1 vector (of upper bounds). Prove that either:

i) there exists an x with Ax ≤ b, x ≤ u

or

ii) there exists vectors y, z with ATy + z = 0, y, z ≥ 0, b.y + u.z < 0 but not both.

You may use the dual introduced in Assignment 1, question 5 to handle free variables.

b) Use a) to show that the following system of equalities with bounded variables given below has no solution. You can guess y, z for the given data:

-x1 -x2 ≤ -6

-x1 +x2 ≤ -8

x1 -2x2 ≤ 3

x1 ≤ 4

x2 ≤ 2

Reference no: EM13967844

Questions Cloud

How do the time-variations depend on the bandwidth : Consider the two-path example d = 2 km and the receiver at 1.5 km from the transmitter moving at velocity 60 km/h away from the transmitter. The carrier frequency is 900 MHz. Plot in MATLAB the magnitudes of the taps of the discrete-time baseb..
Demonstrate an understanding of professionalism. : What is the importance of becoming a nationally credentialed medical assistant?
Discuss all legal concepts : Worried about the wildly fluctuating price of oil, Airline wrote to Oil Company requesting a firm price on jet fuel for one year. On December 15, 2006, Oil Company wrote to Airline, stating: "I offer to supply you with any jet fuel ordered by you ..
Total ordering and holding costs : Suppose Ollah decides to order 200 bags at a time. What would the total ordering and holding costs for the year be? (For this problem, don't consider safety stock when calculating holding costs.)
Derive the dual of the new lp : Give an example of a dictionary for which the current basic feasible solution is optimal and yet the coefficients of the non-basic variables in the z row are not all negative - Derive the dual of the new LP. Verify that an optimal dual solution wil..
How do you determine that and how does your own daily : What strictly military lessons have you learned from the course so far that would help you accomplish your mission more effectively?
Which filter should one redesign : If one is aware of the channel filter h(t), one may want to redesign either the baseband filter at the transmitter or the baseband filter at the receiver so that there is no intersymbol interference between receiver samples and so that the noise ..
Identify the theories of victimization : The following are scenarios involving victims of crime. Identify the theories of victimization found in each scenario. Explain how these theories apply to each scenario
Today''s health and wellness professional : Why is understanding the ethnicity, customs, way of life, traditions, and mores of a specific society (multiculturalism) important to today's health and wellness professional?

Reviews

Write a Review

 

Mathematics Questions & Answers

  What was its net cash flow

Kendall Corners Inc. recently reported net income of $3.1 million and depreciation of $500,000. What was its net cash flow? Assume it had no amortization expense.

  Question says express each repeating decimal as a fraction

question says express each repeating decimal as a fraction

  Find the four zeros of the polynomial

Find the four zeros of the polynomial and find all roots in rectangular coordinates and exhibit them as vertices of certain regular polygons

  What balance does the bank statement show

Your checkbook shows a balance of $992.23. The bank statement does not show a deposit of $673.77, and checks for $122.52, $119.47, and $29.40 have not been cashed. What balance does the bank statement show?

  Determining euclidean algorithm

Modify the Euclidean algorithm to find the greatest common divisor of 2x^3 + x^2 - 2x - 1 and x^2 + 3x + 2. This requires long division with polynomials.

  Solve binary message probability

A binary message is sent over a noisy channel. The message is a sequence x1, x2, . . . , xn of n bits (xi 2 {0, 1}). Since the channel is noisy, there is a chance that any bit might be corrupted, resulting in an error (a 0 becomes a 1 or vice vers..

  What is the value of the sample correlation coefficient

A linear regression model has a slope of -2.5 and an intercept of 10. The sample coefficient of determination is 0.50. What is the value of the sample correlation coefficient?

  What values of h doom the crop to complete depletion

Draw and label the phase diagram(x. vs. x) for x. = 3x2 - 9x. Indicate the system progress (using arrows and EXPLAIN). Identify any critical points as stable, unstable, or semi-stable (EXPLAIN).

  Determining volume of ellipsoid

Find the volume of the ellipsoid generated by rotating around the x axis the region bounded by the ellipse with the equation (x/a)^2 + (y/b)^2 = 1

  Find out the sample size needed to estimate

Determine the sample size needed to estimate (lower case mu / mean of a random variable) for the given situation. E = 4, standard deviation = 35, level of confidence = .90

  What was the speed on each part of the trip

During the first part of a trip, a canoeist travels 76 miles at a certain speed. The canoeist travels 24 miles on the second part of the trip at a speed 5 mph slower. The total time for the trip is 4 hours. What was the speed on each part of the t..

  Estimate the time of death

Newton's Law of Cooling states that the rate of change of the temperature of an object is proportional to the difference between the temperature of the object and the temperature of the environment.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd