Example:

Maximization Problem

Suppose a company manufactures different electronic components for computers

Components

A

C

B

2 hours FABRICATION

1 hour ASSEMBLY

3 hours FABRICATION

1 hour ASSEMBLY

2 hours FABRICATION

2 hours ASSEMBLY

1000 labor-hours

800 labor-hours

FABRICATION

ASSEMBLY

If the profit for each component (A, B, C) is $7, $8, and $10 respectively, how many of each should be produced to maximize profit?

x1 = no. of components of type A

x2 = no. of components of type B

x3 = no. of components of type C

Maximize

Profit

P = 7(x1) + 8(x2) + 10(x3)

A

C

B

2 hours FABRICATION

1 hour ASSEMBLY

3 hours FABRICATION

1 hour ASSEMBLY

2 hours FABRICATION

2 hours ASSEMBLY

Fabrication

2(x1) + 3(x2) + 2(x3) <= 1000

Assembly

1(x1) + 1(x2) + 2(x3) <= 800

A = $ 7

B = $8

C = $10

(1000 hours)

(800 hours)

P = 7(x1) + 8(x2) + 10(x3)

2(x1) + 3(x2) + 2(x3) <= 1000

1(x1) + 1(x2) + 2(x3) <= 800

Maximize:

Fabrication:

Assembly:

-7(x1) - 8(x2) - 10(x3) + P = 0

2(x1) + 3(x2) + 2(x3) + s1 = 1000

1(x1) + 1(x2) + 2(x3) + s2 = 800

-7(x1) - 8(x2) - 10(x3) + P = 0

2(x1) + 3(x2) + 2(x3) + s1 = 1000

1(x1) + 1(x2) + 2(x3) + s2 = 800

x1

x2

x3

s1

s2

P

2

3

2

1

0

0

1

1

2

0

1

0

1000

800

s1

s2

-7

-8

-10

0

0

1

0

Goal: Setup Initial Tableau

x1

x2

x3

s1

s2

P

2

3

2

1

0

0

1

1

2

0

1

0

1000

800

s1

s2

-7

-8

-10

0

0

1

0

1. Set pivot column

2. Set pivot element

"Most negative" in bottom row

1000 / 2 = 500

800 / 2 = 400

[ ]

x3

Iteration 1

Next Goal: Make pivot element = 1

Iteration 1

Next Goal: Make all other elements in pivot column = 0

x1

x2

x3

s1

s2

P

2

3

2

1

0

0

1

1

2

0

1

0

1000

800

s1

x3

-7

-8

-10

0

0

1

0

1/2(R2) = R2

1/2(1) = 1/2

1/2(1) = 1/2

1/2(2) = 1

1/2(0) = 0

1/2(1) = 1/2

1/2(0) = 0

1/2(800) = 400

[ ]

x1

x2

x3

s1

s2

P

2

3

2

1

0

0

1/2

1/2

1

0

1/2

0

1000

400

s1

x3

-7

-8

-10

0

0

1

0

[ ]

Iteration 1

x1

x2

x3

s1

s2

P

2

3

2

1

0

0

1/2

1/2

1

0

1/2

0

1000

400

s1

x3

-7

-8

-10

0

0

1

0

-2(R2) + R1 = R1

10(R2) + R3 = R3

-2 (1/2) + 2 = 1

-2 (1/2) + 3 = 2

-2 (1) + 2 = 0

-2 (0) + 1 = 1

-2 (1/2) + 0 = -1

-2 (0) + 0 = 0

-2 (400) + 1000 = 200

10 (1/2) + -7 = -2

10 (1/2) + -8 = -3

10 (1) + -10 = 0

10 (0) + 0 = 0

10 (1/2) + 0 = 5

10 (0) + 1 = 1

10 (400) + 0 = 4000

[ ]

x1

x2

x3

s1

s2

P

1/2

1/2

1

0

1/2

0

400

s1

x3

1

2

0

1

-1

0

200

-2

-3

0

0

5

1

4000

Are there negative values in the last row?

Yes.

Iterate.

x1

x2

x3

s1

s2

P

1

2

0

1

-1

0

1/2

1

0

1/2

0

200

400

s1

x3

-2

-3

0

0

5

1

4000

1. Set pivot column

2. Set pivot element

"Most negative" in bottom row

200 / 2 = 100

400 / (1/2) = 800

x2

Iteration 2

Next Goal: Make pivot element = 1

1/2

[ ]

[ ]

Iteration 2

Next Goal: Make all other elements in pivot column = 0

x1

x2

x3

s1

s2

P

1

2

0

1

-1

0

1/2

1/2

1

0

1/2

0

200

400

x2

x3

-2

-3

0

0

5

1

4000

1/2(R1) = R1

1/2(1) = 1/2

1/2(2) = 1

1/2(0) = 0

1/2(1) = 1/2

1/2(-1) = -1/2

1/2(0) = 0

1/2(200) = 100

[ ]

x1

x2

x3

s1

s2

P

1/2

x2

x3

-2

-3

0

0

5

1

4000

1/2

1

0

1/2

0

400

1/2

1

0

1/2

-1/2

0

100

[ ]

Iteration 2

x1

x2

x3

s1

s2

P

1/2

1

0

1/2

-1/2

0

1/2

1/2

1

0

1/2

0

100

400

x2

x3

-2

-3

0

0

5

1

4000

-1/2(R1) + R2 = R2

3(R1) + R3 = R3

-1/2 (1/2) + 1/2 = 1/4

-1/2 (1) + 1/2 = 0

-1/2 (0) + 1 = 1

-1/2 (1/2) + 0 = -1/4

-1/2 (-1/2) + 1/2 = 3/4

-1/2 (0) + 0 = 0

-1/2 (100)

+ 400 = 350

3 (1/2) + -2 = -1/2

3 (1) + -3 = 0

3 (0) + 0 = 0

3 (1/2) + 0 = 3/2

3 (-1/2) + 5 = 7/2

3 (0) + 1 = 1

3 (100)

+ 4000 = 4300

[ ]

x1

x2

x3

s1

s2

P

1/4

0

1

-1/4

3/4

0

350

x2

x3

1/2

1

0

1/2

-1/2

0

100

-1/2

0

0

3/2

7/2

1

4300

Are there negative values in the last row?

Yes.

Iterate.

x1

x2

x3

s1

s2

P

1/2

1

0

1/2

-1/2

0

1/4

1

-1/4

3/4

0

100

350

x2

x3

-1/2

0

0

3/2

7/2

1

4300

1. Set pivot column

2. Set pivot element

"Most negative" in bottom row

100 / (1/2) = 200

350 / (1/4) = 1400

x1

Iteration 3

Next Goal: Make pivot element = 1

0

[ ]

[ ]

Iteration 3

Next Goal: Make all other elements in pivot column = 0

x1

x2

x3

s1

s2

P

1/2

1

0

1/2

-1/2

0

1/4

0

1

-1/4

3/4

0

100

350

x1

x3

-1/2

0

0

3/2

7/2

1

4300

2(R1) = R1

2(1/2) = 1

2(1) = 2

2(0) = 0

2(1/2) = 1

2(-1/2) = -1

2(0) = 0

2(100) = 200

[ ]

x1

x2

x3

s1

s2

P

1/4

x1

x3

-1/2

0

0

3/2

7/2

1

4300

0

1

-1/4

3/4

0

350

1

2

0

1

-1

0

200

[ ]

Iteration 3

x1

x2

x3

s1

s2

P

1

2

0

1

-1

0

1/4

0

1

-1/4

3/4

0

200

350

x1

x3

-1/2

0

0

3/2

7/2

1

4300

-1/4(R1) + R2 = R2

1/2(R1) + R3 = R3

-1/4 (1) + 1/4 = 0

-1/4 (2) + 0 = -1/2

-1/4 (0) + 1 = 1

-1/4 (1) + -1/4 = -1/2

-1/4 (-1) + 3/4 = 1

-1/4 (0) + 0 = 0

-1/4 (200)

+ 350 = 300

1/2 (1) + -1/2 = 0

1/2 (2) + 0 = 1

1/2 (0) + 0 = 0

1/2 (1) + 3/2 = 2

1/2 (-1) + 7/2 = 3

1/2 (0) + 1 = 1

1/2 (200)

+ 4300 = 4400

[ ]

x1

x2

x3

s1

s2

P

0

-1/2

1

-1/2

1

0

300

x1

x3

1

2

0

1

-1

0

200

0

1

0

2

3

1

4400

Are there negative values in the last row?

No.

Terminate.

Final Tableau.

x1

x2

x3

s1

s2

P

0

-1/2

1

-1/2

1

0

300

1

2

0

1

-1

0

200

0

1

0

2

3

1

4400

x1

x3

x1 = 200

x3 = 300

Max profit when:

x2 = 0

Profit = 4400

s1 = 0

s2 = 0

Also:

**Linear Programming:**

**The Simplex Method**

**Ateneo de Manila University, Philippines**

Linear

Programming

an optimization technique that deals with meeting a desired objective

Maximizing Profit

Minimizing Cost

Limited resources

(time, money, etc.)

Mathematical functions:

represent objectives and constraints

scheduling or setting a goal / agenda

History

First developed by Leonid Kantorovich

Source: http://upload.wikimedia.org/wikipedia/commons/f/f4/Leonid_Kantorovich_1975.jpg

1939: developed the linear programming technique

World War II: reduce costs to the army, increase losses to the enemy

**Developed by George Dantzig (1946)**

**Algorithm**

**1. Convert the LP problem to a system of linear equations (use "slack" variables).**

**2. Setup the initial tableau. Derive the basic feasible solution.**

**3. Select the pivot column.**

**4. Select the pivot element.**

**5. Use the pivot to clear the pivot column. (Here, the next basic feasible solution is derived.)**

**6. Iterate (3-5) until all negative values in the last row are eliminated.**

**7. The solution to the problem is the basic feasible solution from the final tableau.**