Question

Publish your answer to the questions below in the BLOG titled: Minimization LP Using Simplex. This activity is worth 0 points. Your Test # 1 will not be graded if you do not accomplish this activity. For due date refer to the course Calendar in the Tools area of Blackboard.

Provide a descriptive explanation in 1 to 2 paragraphs.We covered Simplex Method for Maximization problem. Discuss with other student how we can solve Minimization problem using Simplex Method.

Answer 1

LP Problem solved using Two Phases Simplex Method

Minimization Problem,

Let me consider an Advertising company uses Television and Radio Costs of advertising one advertising unit using Television, Radio are $20 and $30 respectively, number of potential customer to be reached per unit using advertising channel like Television is 450 and number of potential customer to be reached per unit using advertising channel Radio is 500, Number of women customers reached per unit for Advertising channel Television is 230 and Number of women customers reached per unit for Advertising channel Radio is 150, this advertising campaign require minimum 5000 women Exposures and 12000 exposure of potential customers,

Here, let me consider, Number of advertising units for Television = X1,

Number of advertising units for Radio = X2,

Objective function that cost is to be minimized, so, Minimize Cost or Z = 20*X1+30*X2

Constraints are:

450*X1+500*X2>=12,000

230*X1+150*X2>=5000,

X1,X2>=0,

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

As the constraint 1 is of type '≥' we should add the surplus variable X3 and the artificial variable X5.
As the constraint 2 is of type '≥' we should add the surplus variable X4 and the artificial variable X6.

We'll build the first tableau of Phase I from Two Phase Simplex method.

The leaving variable is P6 and entering variable is P1.

Intermediate operations

Pivot row (Row 2):
5000 / 230 = 500 / 23
230 / 230 = 1
150 / 230 = 15 / 23
0 / 230 = 0
-1 / 230 = -1 / 230
0 / 230 = 0
1 / 230 = 1 / 230

Row 1:
12000 - (450 * 500 / 23) = 51000 / 23
450 - (450 * 1) = 0
500 - (450 * 15 / 23) = 4750 / 23
-1 - (450 * 0) = -1
0 - (450 * -1 / 230) = 45 / 23
1 - (450 * 0) = 1
0 - (450 * 1 / 230) = -45 / 23

Row Z:
-17000 - (-680 * 500 / 23) = -51000 / 23
-680 - (-680 * 1) = 0
-650 - (-680 * 15 / 23) = -4750 / 23
1 - (-680 * 0) = 1
1 - (-680 * -1 / 230) = -45 / 23
0 - (-680 * 0) = 0
0 - (-680 * 1 / 230) = 68 / 23

The leaving variable is P5 and entering variable is P2.

Intermediate operations

Pivot row (Row 1):
51000 / 23 / 4750 / 23 = 204 / 19
0 / 4750 / 23 = 0
4750 / 23 / 4750 / 23 = 1
-1 / 4750 / 23 = -23 / 4750
45 / 23 / 4750 / 23 = 9 / 950
1 / 4750 / 23 = 23 / 4750
-45 / 23 / 4750 / 23 = -9 / 950

Row 2:
500 / 23 - (15 / 23 * 204 / 19) = 280 / 19
1 - (15 / 23 * 0) = 1
15 / 23 - (15 / 23 * 1) = 0
0 - (15 / 23 * -23 / 4750) = 3 / 950
-1 / 230 - (15 / 23 * 9 / 950) = -1 / 95
0 - (15 / 23 * 23 / 4750) = -3 / 950
1 / 230 - (15 / 23 * -9 / 950) = 1 / 95

Row Z:
-51000 / 23 - (-4750 / 23 * 204 / 19) = 0
0 - (-4750 / 23 * 0) = 0
-4750 / 23 - (-4750 / 23 * 1) = 0
1 - (-4750 / 23 * -23 / 4750) = 0
-45 / 23 - (-4750 / 23 * 9 / 950) = 0
0 - (-4750 / 23 * 23 / 4750) = 1
68 / 23 - (-4750 / 23 * -9 / 950) = 1

There is any possible solution for the problem, so we can continue to Phase II to calculate it.

Intermediate operations

Remove the columns corresponding to artificial variables.

Modify the row of the objective function for the original problem.

Calculate the Z line:
-(0) + (-30 * 204 / 19) + (-20 * 280 / 19) = -11720 / 19
-(-20) + (-30 * 0) + (-20 * 1) = 0
-(-30) + (-30 * 1) + (-20 * 0) = 0
-(0) + (-30 * -23 / 4750) + (-20 * 3 / 950) = 39 / 475
-(0) + (-30 * 9 / 950) + (-20 * -1 / 95) = -7 / 95

The leaving variable is P2 and entering variable is P4.

Intermediate operations

Pivot row (Row 1):
204 / 19 / 9 / 950 = 3400 / 3
0 / 9 / 950 = 0
1 / 9 / 950 = 950 / 9
-23 / 4750 / 9 / 950 = -23 / 45
9 / 950 / 9 / 950 = 1

Row 2:
280 / 19 - (-1 / 95 * 3400 / 3) = 80 / 3
1 - (-1 / 95 * 0) = 1
0 - (-1 / 95 * 950 / 9) = 10 / 9
3 / 950 - (-1 / 95 * -23 / 45) = -1 / 450
-1 / 95 - (-1 / 95 * 1) = 0

Row Z:
-11720 / 19 - (-7 / 95 * 3400 / 3) = -1600 / 3
0 - (-7 / 95 * 0) = 0
0 - (-7 / 95 * 950 / 9) = 70 / 9
39 / 475 - (-7 / 95 * -23 / 45) = 2 / 45
-7 / 95 - (-7 / 95 * 1) = 0

The optimal solution value is Z = 1600 / 3
X1 = 80 / 3
X2 = 0

Same way maximization problem can be considered, for this same advertising company, profit required to be maximized, (Only Profit data has changed, other data are kept same)

Advertising company uses return of advertising one advertising unit using Television, Radio are $2 and $3 respectively, number of potential customer to be reached per unit using advertising channel like Television is 450 and number of potential customer to be reached per unit using advertising channel Radio is 500, Number of women customers reached per unit for Advertising channel Television is 230 and Number of women customers reached per unit for Advertising channel Radio is 150, this advertising campaign require minimum 5000 women Exposures and 12000 exposure of potential customers,

Here, let me consider, Number of advertising units for Television = X1,

Number of advertising units for Radio = X2,

Objective function that Profit to be Maximized, or Z = 2*X1+3*X2

Constraints are:

450*X1+500*X2>=12,000

230*X1+150*X2>=5000,

X1,X2>=0,

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

As the constraint 1 is of type '≥' we should add the surplus variable X3 and the artificial variable X5.
As the constraint 2 is of type '≥' we should add the surplus variable X4 and the artificial variable X6.

We'll build the first tableau of Phase I from Two Phase Simplex method.

The leaving variable is P6 and entering variable is P1.

Intermediate operations

Pivot row (Row 2):
5000 / 230 = 500 / 23
230 / 230 = 1
150 / 230 = 15 / 23
0 / 230 = 0
-1 / 230 = -1 / 230
0 / 230 = 0
1 / 230 = 1 / 230

Row 1:
12000 - (450 * 500 / 23) = 51000 / 23
450 - (450 * 1) = 0
500 - (450 * 15 / 23) = 4750 / 23
-1 - (450 * 0) = -1
0 - (450 * -1 / 230) = 45 / 23
1 - (450 * 0) = 1
0 - (450 * 1 / 230) = -45 / 23

Row Z:
-17000 - (-680 * 500 / 23) = -51000 / 23
-680 - (-680 * 1) = 0
-650 - (-680 * 15 / 23) = -4750 / 23
1 - (-680 * 0) = 1
1 - (-680 * -1 / 230) = -45 / 23
0 - (-680 * 0) = 0
0 - (-680 * 1 / 230) = 68 / 23

The leaving variable is P5 and entering variable is P2.

Intermediate operations

Pivot row (Row 1):
51000 / 23 / 4750 / 23 = 204 / 19
0 / 4750 / 23 = 0
4750 / 23 / 4750 / 23 = 1
-1 / 4750 / 23 = -23 / 4750
45 / 23 / 4750 / 23 = 9 / 950
1 / 4750 / 23 = 23 / 4750
-45 / 23 / 4750 / 23 = -9 / 950

Row 2:
500 / 23 - (15 / 23 * 204 / 19) = 280 / 19
1 - (15 / 23 * 0) = 1
15 / 23 - (15 / 23 * 1) = 0
0 - (15 / 23 * -23 / 4750) = 3 / 950
-1 / 230 - (15 / 23 * 9 / 950) = -1 / 95
0 - (15 / 23 * 23 / 4750) = -3 / 950
1 / 230 - (15 / 23 * -9 / 950) = 1 / 95

Row Z:
-51000 / 23 - (-4750 / 23 * 204 / 19) = 0
0 - (-4750 / 23 * 0) = 0
-4750 / 23 - (-4750 / 23 * 1) = 0
1 - (-4750 / 23 * -23 / 4750) = 0
-45 / 23 - (-4750 / 23 * 9 / 950) = 0
0 - (-4750 / 23 * 23 / 4750) = 1
68 / 23 - (-4750 / 23 * -9 / 950) = 1There is any possible solution for the problem, so we can continue to Phase II to calculate it.

Intermediate operations

Remove the columns corresponding to artificial variables.

Modify the row of the objective function for the original problem.

Calculate the Z line:
-(0) + (3 * 204 / 19) + (2 * 280 / 19) = 1172 / 19
-(2) + (3 * 0) + (2 * 1) = 0
-(3) + (3 * 1) + (2 * 0) = 0
-(0) + (3 * -23 / 4750) + (2 * 3 / 950) = -39 / 4750
-(0) + (3 * 9 / 950) + (2 * -1 / 95) = 7 / 950

The leaving variable is P1 and entering variable is P3.

Intermediate operations

Pivot row (Row 2):
280 / 19 / 3 / 950 = 14000 / 3
1 / 3 / 950 = 950 / 3
0 / 3 / 950 = 0
3 / 950 / 3 / 950 = 1
-1 / 95 / 3 / 950 = -10 / 3

Row 1:
204 / 19 - (-23 / 4750 * 14000 / 3) = 100 / 3
0 - (-23 / 4750 * 950 / 3) = 23 / 15
1 - (-23 / 4750 * 0) = 1
-23 / 4750 - (-23 / 4750 * 1) = 0
9 / 950 - (-23 / 4750 * -10 / 3) = -1 / 150

Row Z:
1172 / 19 - (-39 / 4750 * 14000 / 3) = 100
0 - (-39 / 4750 * 950 / 3) = 13 / 5
0 - (-39 / 4750 * 0) = 0
-39 / 4750 - (-39 / 4750 * 1) = 0
7 / 950 - (-39 / 4750 * -10 / 3) = -1 / 50

Solution is unbounded.(Answer)