# Clemson MTHSC 440 - Lecture (5 pages)

Previewing pages*1, 2*of 5 page document

**View the full content.**## Lecture

Previewing pages *1, 2*
of
actual document.

**View the full content.**View Full Document

## Lecture

0 0 124 views

Lecture Notes

- Pages:
- 5
- School:
- Clemson University
- Course:
- Mthsc 440 - Linear Programming

**Unformatted text preview: **

Playing with equations and inequalities MthSc 440 640 Linear Programming Lecture 8 Trivial if a b and c d then a c b d Similarly if a b and c d then a c b d Caution if a b and c d then a c b d Also if a b for any k 0 we have ka kb We can mix inequalities and equations Example Pietro Belotti Dept of Mathematical Sciences Clemson University September 16 2010 Reading for today pages 54 65 textbook Midterm exam Tuesday October 5 12 30pm 1 45pm a1 x1 a2 x2 an xn a0 b1 x1 b2 x2 bn xn b0 c1 x1 c2 x2 cn xn c0 and three numbers p q r 0 the following is true p a1 x1 a2 x2 an xn q b1 x1 b2 x2 bn xn r c1 x1 c2 x2 cn xn pa0 qb0 rc0 That is a convex combination of constraints is valid Non negative variables and linear functions Lower bounds of an LP problem Consider f x1 x2 5x1 3x2 and suppose x1 x2 0 Consider the following minimization problem What is f x1 x2 for any x1 x2 0 min 3x1 4x2 5x1 6x2 7 8x1 9x2 10 11x1 12x2 13 x1 x2 0 g1 x1 x2 0 g2 x1 x2 x1 g3 x1 x2 5x1 g4 x1 x2 5 00001x1 g5 x1 x2 4x1 2x2 We have a lower bound if we prove 3x1 4x2 c for some c g6 x1 x2 2x1 9x2 We can prove using for example the constraints that g7 x1 x2 3x1 5x2 For x1 x2 0 a function g x1 x2 ax1 bx2 f x1 x2 if and only if a 5 and b 3 ax1 bx2 c with a 3 and b 4 That would make c a lower bound Finding lower bounds using constraints A more general way Can we use convex combinations of constraints For example 0 3 first constraint 0 2 second constraint We have three constraint at our avail We need three numbers u1 u2 u3 0 With u1 u2 u3 we construct a new constraint ax1 bx2 c 0 25 5x1 6x2 0 2 8x1 9x2 0 25 7 0 2 10 1 25 1 6 x1 1 5 1 8 x2 1 75 2 0 2 85x1 3 3x2 3 75 u1 5x1 6x2 u2 8x1 9x2 u3 11x1 12x2 7u1 10u2 13u3 5u 8u2 11u3 x1 6u1 9u2 12u3 x2 7u1 10u2 13u3 z z z 1 2 85 3 and 3 3 4 The new constraint is valid for any u1 u2 u3 0 We want ax1 bx2 to be always below 3x1 4x2 so that c 7u1 10u2 13u3 is a valid lower bound We must have a 3 and b 4 Hence 2 85x1 3 3x2 is a lower bound of 3x1 4x2 for x1 x2 0 3 75 is a

View Full Document