Similar problem 4



|Similar problem 4.1 # 11 of Practice Are you having trouble deciding on the pivot element? See PP on subject |

| | | | | | | | | | |

| |Write the solutions that can be read from the simplex tableau | | | |

| | | | | | | | | | |

| |x1 |x2 |x3 |s1 |s2 |s3 |z | | |

| |0 |2 |0 |5 |2 |2 |0 |15 | |

| |0 |3 |1 |0 |1 |2 |0 |2 | |

| |7 |4 |0 |0 |3 |5 |0 |35 | |

| |0 |-4 |0 |0 |4 |3 |2 |40 | |

| | | | | | | | | | |

| | | | | | | | | | |

| |Describe how you arrive at your solutions. | | | | |

| | | | | | | | | | |

| | | | | | | | | | |

| | | | | | | | | | |

In a simplex tableau, columns with all non-zero entries indicate that the variable is equal to zero. As a result, the above tableau shows that x2 = 0, s2 = 0, and s3 = 0.

The columns with one non-zero entry are interpreted to mean that the non-zer0 entry times the variable is equal to the value in the rightmost column, in the same row as the non-zero entry. From the above table then:

7x1 = 35 ( x1 = 5

x3 = 2

5s1 = 15 ( s1 = 3

2z = 40 ( z = 20

|Similar problem 4.1 # 15 of Practice Are you having trouble deciding on the pivot element? See PP on subject |

| | | | | | | | | | |

| |Pivot ONCE as indicated in the simplex tableau. Read the solution from the result. |Pivot element is highlighted. |

| | | | | | | | | | |

| |x1 |x2 |x3 |s1 |s2 |s3 |z | | |

| |4 |2 |3 |1 |0 |0 |0 |22 | |

| |2 |2 |5 |0 |1 |0 |0 |28 | |

| |-3 |-2 |-4 |0 |0 |0 |1 |0 | |

| | | | | | | | | | |

| |Describe how you arrive at your solutions. | | | | |

| | | | | | | | | | |

Pivoting once about the highlighted entry, the row operations to be performed are:

Row 2: Divide Row 2 by 5

Row 1: Subtract 3 times Row 2 from Row 1

Row 3: Subtract 2 times Row 2 from Row 3

Row 4: Add 4 times Row 2 to Row 4

The resulting tableau is:

|x1 |x2 |x3 |s1 |s2 |s3 |z | |

|14/5 |4/5 |0 |1 |-3/5 |0 |0 |194/5 |

|2/5 |2/5 |1 |0 |1/5 |0 |0 |28/5 |

|1/5 |11/5 |0 |0 |-2/5 |1 |0 |169/5 |

|-7/5 |-2/5 |0 |0 |4/5 |0 |1 |112/5 |

The solutions from this tableau, using the same procedure from the previous problem are:

x1 = 0 x2 = 0 s3 = 0

x3 = 28/5 s1 = 194/5 s3 = 169/5

z = 112/5

|Take the time to do and look at solutions to earlier practice exercises on this section. It will be a big | | | |

|help. Similar problem 4.2 # 11, #17 of Practice. #17 is done as a PP presentation. | | | |

| | | | | |

| | | | | | | | | |

| |

| |

| | | |

| | | | | | | | |

Let x1 represent the number of Basic sets produced and sold.

Let x2 represent the number of Regular sets produced and sold.

Let x3 represent the number of Deluxe sets produced and sold.

The profit equation to be maximized is z = 30x1 + 40x2 + 40x3

The constraints are: 2x1 + 2x2 + 2x3 ≤ 800

x1 + x2 + x3 ≤ 400

x2 + x3 ≤ 200

The first and second constraints are redundant, as the first one is a multiple of the second constraint and, therefore, add no additional useful information to the problem. For this reason, the first constraint is disregarded.

The constraints written with slack variables included are:

x1 + x2 + x3 + s1 ≤ 400

x2 + x3 + s2 ≤ 200

The initial tableau is then:

[pic]

The most negative entry is the bottom row is in both the 2nd and 3rd columns, as both a re -40. In either case, the lowest ratio occurs in the second row. As a result, the pivot is either the second or third column in row 2. The second column is chosen arbitrarily.

The row operations for this pivot are:

Subtract Row 2 from Row 1

Add 40 times Row 2 to Row 3

The result is:

[pic]

The most negative entry in the bottom row is now in the first column, and the smallest ratio corresponds with the entry in the first row. The pivot is then the first row of the first column.

The row operations for this pivot are:

Add 30 times Row 1 to Row 3

The result is:

[pic]

With no remaining negative entries in the bottom row, this is the optimal solution.

The solution is: x1 = 200, x2 = 200, and the profit is 14,000

|See practice exercises 4.3 for helpful hints | | | | |

| | | | | | | | | |

| |State the dual problem for the linear programming problem | | |

| | | | | | | | | |

| | |Given | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

Write the augmented matrix for the minimization problem:

[pic]

Write the transpose of the augmented matrix:

[pic]

Write the maximization problem corresponding to the new matrix, changing variables from yi to xi, and from w to z:

Maximize: z = 115x1 + 200x2 + 50x3

Subject to: x1 + 2x2 + x3 ≤ 1

2x1 + x2 ≤ 1

3x1 + 8x2 + x3 ≤ 4

With x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0

|Similar problem 4.3 # 11 of Practice. Notice where the answers come from on this problem |

| | | | | | | | | | |

| |Given | | | | | | | |Solve |

| | | | | | | | | | |

| | | | | | | | | | |

| | | | | | | | | |use the symplex method |

| | | | | | | | | |or "The solver" |

| | | | | | | | | | |

| | | | | | | | | | |

| | | | | | | | | | |

| | | | | | | | | | |

| | | | | | | | | | |

| | | | | | | | | | |

| | | | | | | | | | |

| | | | | | | | | | |

| | | | | | | | | | |

As with the previous problem, write the augmented matrix for the minimization problem.

[pic]

Write the transpose of the matrix:

[pic]

Write the maximization problem, changing variables from yi to xi, and from w to z:

Maximize z = 60x1 + 40x2

Subject to: 2x1 + x2 ≤ 3

3x1 + 4x2 ≤ 2

With x1 ≥ 0 and x2 ≥0

Write the constraints with slack variables added:

2x1 + x2 + s1 = 3

3x1 + 4x2 + s2 = 2

Write the initial simplex tableau:

[pic]

The largest negative value in the bottom row is in the first column, and the smallest ratio occurs in the second row of that column. As a result, pivot about the entry in the second row of the first column.

The row operations for that pivot are:

Divide Row 2 by 3

Subtract 2 times Row 2 from Row 1

Add 60 times Row 2 to Row 3

The resulting tableau is:

[pic]

As there are no negative entries in the bottom row, this is the optimal solution.

To get the solution to the original minimization problem, read the values in the bottom row of the columns corresponding to the slack variables from this final tableau, with y1 = s1 and y2 = s2. The minimum value of w will have the same value as the value of z from the maximization problem.

s1 = 0 ( y1 = 0

s2 = 20 ( y2 = 20

z = 40 ( w = 40

The solution to the minimization problem is w = 40, with y1 = 0 and y2 = 20

|Similar problem 4.3 # 19 of Practice. Notice where the answers come from on this problem |

| | | | | | | | | | |

| |Time vs return: You have a part-time job conducting public interviews. You find that a political interview takes 55 min. |

| |and a market interview takes 45 min. You need to minimize the time you spend doing interviews to allow more time for your |

| |full-time job. The rules to keep the part-time job are as follows: You must complete at least 8 interviews each week. Also, |

| |you must earn at least $60 a week of which you earn $10 from each political interview, and $8 from each market interview. You |

| |also have the restriction that you must earn at least 40 bonus points per week of which 5 come from political interviews and 6 |

| |come from market interviews. How many interviews of each should you do each week to minimize the time you spend. Be |

| |specific, explain your logic and show all your work. |

| | |

| | |

| | |

Let y1 represent the number of political (55 minute) interviews.

Let y2 represent the number of market (45 minute) interviews.

The total time spent on all interviews is w = 55y1 + 45y2..

The constraints involved are:

At least 8 interviews must be completed per week, therefore: y1 + y2 ≥ 8

Earn at least $60 per week, therefore: 10y1 + 8y2 ≥ 60

Earn at least 40 bonus points per week: 5y1 + 6y2 ≥ 40

The complete minimization problem is then:

Minimize w = 55y1 + 45y2

Subject to: y1 + y2 ≥ 8

10y1 + 8y2 ≥ 60

5y1 + 6y2 ≥ 40

With y1 ≥ 0, y2 ≥ 0.

(It could be pointed out at this time that the answer is obviously 8 market interviews and 0 political interviews. Completing 8 market interviews meets all of the constraints. Decreasing the number of market interviews and increasing the number of political interviews will only serve to increase the time, which is opposite of the goal here. The answer of 8 market interviews and 0 political interviews cannot be improved upon under the conditions of this scenario.)

Write the augmented matrix for the minimization problem:

[pic]

Write the transpose of the augmented matrix:

[pic]

Write the corresponding maximization problem, changing variables from yi to xi and w to z as in the previous problem.

Maximize z = 8x1 + 60x2 + 40x3

Subject to: x1 + 10x2 + 5x3 ≤ 55

x1 + 8x2 + 6x3 ≤ 45

With x1 ≥ 0, x2 ≥ 0, and x3 ≥ 0

Write the constraints for the maximization problem, adding slack variables:

x1 + 10x2 + 5x3 + s1 = 55

x1 + 8x2 + 6x3 + s2 = 45

The initial tableau for the maximization problem is then:

[pic]

The most negative value in the bottom row is -60 in the second column. The smallest ratio in that column is 55/10, corresponding to the entry in row 1. Therefore, pivot about the entry in the second column of row 1.

The row operations for that pivot are:

Divide Row 1 by 10

Subtract 8 times Row 1 from Row 2

Add 60 times Row 1 to Row 3

The result is:

[pic]

The most negative entry in the bottom row is now in the third column. The smallest ratio in that column is in the second row, ½. Pivot about the entry in the second row of the third column,

The row operations for this pivot are:

Divide Row 2 by 2

Subtract (Row 2)/2 from Row 1

Add 10 times Row 2 to Row 3

The result is:

[pic]

The is only one negative entry in the bottom row, in the first column. The smallest ratio is (½)/(1/10) in the second row. Pivot about the entry in the second row of the first column.

The row operations for this pivot are:

Multiply Row 2 by 10

Subtract (Row 2)/20 from Row 1

Add Row 2 to Row 3

The result is:

[pic]

The only negative entry in the bottom row is in the fourth column. Pivot about the entry in the first row, as the second row entry is negative.

The row operations for this pivot are:

Multiply Row 1 by 2

Add 4 times Row 1 to Row 2

Add 2 times Row 1 to Row 3

The result is:

[pic]

There are no negative numbers in the bottom row of the tableau, indicating that this is the optimal solution.

The solution read from the tableau is (remember, the solution for the variables of the minimization problem are found here in the slack variables):

y1 = 0 y2 = 8 w = 360

Solution:

Performing 8 market interviews and 0 political interviews will use the minimum

amount of time, while meeting or exceeding the other criteria.

| |

|Introduce slack variables as necessary, write the initial simplex tableau, and then select the first pivot element. Explain what you did and |

|why. |

| |

| |

|Find x1≥0 and x2≥0 such that |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

|1 |

|x1 |

|+ |

|1 |

|x2 |

|≤ |

|10 |

| |

| |

| |

|5 |

|x1 |

|+ |

|4 |

|x2 |

|≤ |

|75 |

| |

| |

| |

|And maximize |

| |

| |

| |

| |

| |

| |

| |

| |

| |

|z |

|= |

|4 |

|x1 |

|+ |

|2 |

|x2 |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

|Next find the solution for x1, x2, s1, s2 and z. |

| |

Write the constraints with slack variables included:

x1 + x2 + s1 = 10

5x1 + 4x2 + s2 = 75

Write the initial simplex tableau:

[pic]

The most negative entry in the bottom row is in the first column. Dividing the last entry of the first two rows by the first entry in the same row, the lowest non-negative quotient is 10/1. This indicates that the pivot should be about the entry in the first row of the first column.

The row operations corresponding to this pivot are:

Subtract 5 times Row 1 from Row 2

Add 4 times Row 1 to Row 3

The result is:

[pic]

Since there are no negative entries in the bottom row, this is the optimal solution.

The solutions read from the tableau are:

x2 and s1 are zero because the entries for those columns are all non-zero.

Ignoring the columns for x2 and s1, the other solutions are easily read:

xq = 10

s2 = 25

z = 40

The solution to the maximization problem is z = 40, with x1 = 10, s2 = 25, x2 = s1 = 0.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download