intro to discrete mathematics

Question

Using the Simplex Method...

 

1.) maximize x + 2y subject to the constraints

     -x + y ≤ 100

     6x + 6y ≤ 1200

     x ≥ 0; y ≥ 0

 

2.) maximize 3x + 2y + 5z subject to the constraints

     x + 2z ≤ 10

     3y + 2z ≤ 24

     x ≥ 0; y ≥ 0

 

3.) suppose that a furniture manufacturer makes chairs, sofas and tables. the amounts of labour of various types as well as the relative availability of each type are summarized by the following chart:

                   chair      sofa      table     daily labour available (hrs.)

carpentry     6             3            8                         768

finishing      1             1            2                         144

upholstery   2             5                                        216

 

The profit per chair is $80, per sofa is $70 and per tableis $120. How many pieces of each type of furniture should be manufactured each day to maximize profit?

 

4.) minimize 3x + 5y + z , subject to the constraints

     x + y + z ≥ 20

     y + 2z ≥ 20

     x ≥ 0; y ≥ 0; z ≥ 0

 

5.) a dietician is designing a daily diet that is to contain at least 60 units of protein, 40 units of carbohydrates and 120 units of fat. The diet is to cnsit of two types of foods. One serving of food-A contains 30 units of protein, 10 units of carbohydrates, and 20 units of fat and costs $3. One serving of food-B contains 10 units of protein, 10 units of carbohydrates and 60 units of fat and costs $1.50. Design the diet that provides the daily requirements at the least cost.

Answer 1

The tableaux shown below are transitional, showing changes which may be the result of simultaneously applying several steps in the Simplex process. This is to conserve space and allow all questions to be answered. PR stands for Pivot Row, PC for pivot column and PE for pivot element (highlighted in red).

(1)

(2)

(3)

(4) To use the Simplex method we need to convert this minimisation problem into a maximisation problem. To do this we start with a matrix:
1 1 1 20 from x+y+z≥20 (constraint 1)

1 0 2 20 from x+2z≥20 (constraint 2)

3 5 1   1 from 3x+5y+z=c (objective function)

Now we transpose the matrix (swap rows and columns):

  1   1 3

  1   0 5

  1   2 1

20 20 1

The rows and columns are now interchanged.

More to follow...