The document describes how to formulate a linear programming problem to maximize the profit of a toy factory. It involves 5 steps: 1) Pick important information like production quantities, machine times, and profits. 2) Form constraints from the machine time limits. 3) Write the objective function to maximize total profit. 4) Introduce slack variables and write the initial tableau. 5) Iterate the simplex method by finding pivots to solve the problem.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PPT, PDF, TXT or read online from Scribd
The document describes how to formulate a linear programming problem to maximize the profit of a toy factory. It involves 5 steps: 1) Pick important information like production quantities, machine times, and profits. 2) Form constraints from the machine time limits. 3) Write the objective function to maximize total profit. 4) Introduce slack variables and write the initial tableau. 5) Iterate the simplex method by finding pivots to solve the problem.
The document describes how to formulate a linear programming problem to maximize the profit of a toy factory. It involves 5 steps: 1) Pick important information like production quantities, machine times, and profits. 2) Form constraints from the machine time limits. 3) Write the objective function to maximize total profit. 4) Introduce slack variables and write the initial tableau. 5) Iterate the simplex method by finding pivots to solve the problem.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PPT, PDF, TXT or read online from Scribd
The document describes how to formulate a linear programming problem to maximize the profit of a toy factory. It involves 5 steps: 1) Pick important information like production quantities, machine times, and profits. 2) Form constraints from the machine time limits. 3) Write the objective function to maximize total profit. 4) Introduce slack variables and write the initial tableau. 5) Iterate the simplex method by finding pivots to solve the problem.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt
You are on page 1/ 46
STEP BY STEP GUIDE
1. Formulate the problem (i) Pick out important information (ii) Formulate constraints (iii) Formulate objective function Introduce slack variables Form initial tableau Obtain new tableaux (i) Identify pivotal column (ii) Find -values (iii) Identify pivotal row (iv) Identify pivot (v) Pivot Get the solution
2. 3. 4.
5.
THE PROBLEM A small factory produces two types of toys: cars and diggers. In the manufacturing process two machines are used: the moulder and the colouriser. A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs 1 hour on the moulder and 1 hour on the colouriser. The moulder can be operated for 16 hours a day and the colouriser for 9 hours a day. Each digger gives a profit of 16 and each car gives a profit of 14. The profit needs to be maximised.
How do we formulate this problem?
STEP BY STEP GUIDE
1. Formulate the problem (i) pick out important information (ii) formulate constraints (iii) formulate objective function Introduce slack variables Form initial tableau Obtain new tableaux Get the solution
2. 3. 4. 5.
PICKING OUT IMPORTANT INFORMATION
A small factory produces two types of toys: cars and diggers. In the manufacturing process two machines are used: the moulder and the colouriser. A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs 1 hour on the moulder and 1 hour on the colouriser. The moulder can be operated for 16 hours a day and the colouriser for 9 hours a day. Each digger gives a profit of 16 and each car gives a profit of 14.
PICKING OUT IMPORTANT INFORMATION
A small factory produces two types of toys: cars and diggers. In the manufacturing process two machines are used: the moulder and the colouriser. A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs 1 hour on the moulder and 1 hour on the colouriser. The moulder can be operated for 16 hours a day and the colouriser for 9 hours a day. Each digger gives a profit of 16 and each car gives a profit of 14.
A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs 1 hour on the moulder and 1 hour on the colouriser.
PICKING OUT IMPORTANT INFORMATION
A small factory produces two types of toys: cars and diggers. In the manufacturing process two machines are used: the moulder and the colouriser.
The moulder can be operated for 16 hours a day and the colouriser for 9 hours a day.
Each digger gives a profit of 16 and each car gives a profit of 14.
A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs 1 hour on the moulder and 1 hour on the colouriser. The moulder can be operated for 16 hours a day and the colouriser for 9 hours a day.
STEP BY STEP GUIDE
1. Formulate the problem (i) pick out important information (ii) formulate constraints (iii) formulate objective function Introduce slack variables Form initial tableau Obtain new tableaux Get the solution
2. 3. 4. 5.
A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs 1 hour on the moulder and 1 hour on the colouriser. The moulder can be operated for 16 hours a day and the colouriser for 9 hours a day.
Using the decision variables
d = number of diggers c = number of cars make two constraints from this information.
FORMING CONSTRAINT 1 THE MOULDER A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs 1 hour on the moulder and 1 hour on the colouriser. The moulder can be operated for 16 hours a day and the colouriser for 9 hours a day.
2d + c 16
FORMING CONSTRAINT 2 THE COLOURISER A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs 1 hour on the moulder and 1 hour on the colouriser. The moulder can be operated for 16 hours a day and the colouriser for 9 hours a day.
d+c9
STEP BY STEP GUIDE
1. Formulate the problem (i) pick out important information (ii) formulate constraints (iii) formulate objective function Introduce slack variables Form initial tableau Obtain new tableaux Get the solution
2. 3. 4. 5.
PICKING OUT IMPORTANT INFORMATION
A small factory produces two types of toys: cars and diggers. In the manufacturing process two machines are used: the moulder and the colouriser.
Each digger gives a profit of 16 and each car gives a profit of 14.
FORMING THE OBJECTIVE FUNCTION
Each digger gives a profit of 16 and each car gives a profit of 14.
Let Z be the total profit; formulate the objective function
FORMING THE OBJECTIVE FUNCTION
Each digger gives a profit of 16 and each car gives a profit of 14.
Z = 16d + 14c
THE LINEAR PROGRAMMING PROBLEM
MAXIMISE Z = 16d + 14c subject to the constraints: (i) 2d + c 16 (ii) d+c 9 (iii) c0,d0 VERY IMPORTANT DONT FORGET YOUR NON NEGATIVITY CONSTRAINTS !
STEP BY STEP GUIDE
1. Formulate the problem 2. Introduce slack variables 3. Form initial tableau 4. Obtain new tableaux
5. Get the solution
INTRODUCING SLACK VARIABLES
To change inequalities (i) and (ii) into equations we add slack variables s and t This gives: (i) (ii) 2d + c + s = 16 d+c+t = 9
THE NEW LINEAR PROGRAMMING PROBLEM
MAXIMISE Z = 16d + 14c + 0s + 0t subject to the constraints:
2d + c + s + 0t = 16 d + c + 0s + t = 9 c0,d0,s0,t0
STEP BY STEP GUIDE
1. Formulate the problem 2. Introduce slack variables 3. Form initial tableau 4. Obtain new tableaux
5. Get the solution
We want to put all the information in the form of a table. This is called the initial tableau. To form the initial tableau we need to change the objective function from Z = 16d + 14c + 0s + 0t
to Z 16d 14c 0s 0t = 0
FORMING THE INITIAL TABLEAU
Label the table with your basic variables, s and t and with your non basic variables, d and c.
1. 2. 3. 4. Formulate the problem Introduce slack variables Form initial tableau Obtain new tableaux (i) Identify pivotal column (ii) Find -values (iii) Identify pivotal row (iv) Identify pivot (v) Pivot Get the solution
3.
PIVOTAL COLUMN We now need to find where to pivot and we start by entering the basis by choosing the column with the most negative entry in the objective row. BASIC VARIABLES
d 2 1 -16
c 1 1 -14
s 1 0 0
t 0 1 0
VALUE
s t Z
16 9 0
This is the most negative coefficient with corresponding variable d and its column is called the pivotal column. d is now called the entering variable.
STEP BY STEP GUIDE
1. 2. 3. 4. Formulate the problem Introduce slack variables Form initial tableau Obtain new tableaux (i) Identify pivotal column (ii) Find -values (iii) Identify pivotal row (iv) Identify pivot (v) Pivot Get the solution
3.
FINDING -VALUES You are now going to find the pivotal row and the leaving variable. You need to find -values. 1. Identify positive entries in the pivotal column. 2. Divide each entry in value column by the corresponding positive entry in the pivotal column. BASIC VARIABLES
VALUE
s t Z
2 1 -16
1 1 -14
1 0 0
0 1 0
16 9 0
STEP BY STEP GUIDE
1. 2. 3. 4. Formulate the problem Introduce slack variables Form initial tableau Obtain new tableaux (i) Identify pivotal column (ii) Find -values (iii) Identify pivotal row (iv) Identify pivot (v) Pivot Get the solution
5.
PIVOTAL ROW For row (i) For row (ii)
16 2 9 1
8 9
The row with the smallest -value is called the pivotal row. Here the pivotal row is row (i)
STEP BY STEP GUIDE
1. 2. 3. 4. Formulate the problem Introduce slack variables Form initial tableau Obtain new tableaux (i) Identify pivotal column (ii) Find -values (iii) Identify pivotal row (iv) Identify pivot (v) Pivot Get the solution
5.
THE PIVOT The pivot! BASIC VARIABLES
d 2 1 -16
c 1 1
s 1 0 0
t 0 1 0
VALUE
s The pivotal row
16 9 0
t Z
-14
The pivotal column
STEP BY STEP GUIDE
1. 2. 3. 4. Formulate the problem Introduce slack variables Form initial tableau Obtain new tableaux (i) Identify pivotal column (ii) Find -values (iii) Identify pivotal row (iv) Identify pivot (v) Pivot Get a solution
5.
PIVOTING 1. Replace the leaving variable with the entering variable. 2. Divide all entries in the pivotal row by the pivot. The pivot becomes 1. 3. Add suitable multiples of the pivotal row to all other rows until all entries, apart from the pivot, in the pivotal column are zero.
Step 1
- Replace the leaving variable with the entering variable. d 2 1 -16 c 1 1 -14 s 1 0 0 t 0 1 0 VALUE
BASIC VARIABLES
16 9 0
t Z
Step 2 - Divide all entries in the pivotal row by the pivot. The pivot becomes 1. BASIC VARIABLES
d 1
c 1/2
s 1/2
t 0
VALUE
s d
t Z
PIVOTING BASIC VARIABLES
d 2 1 -16
c 1 1 -14
s 1 0 0
t 0 1 0
VALUE
s t Z
16 9 0
Step 3 - Add suitable multiples of the pivotal row to all other rows until all entries, apart from the pivot, in the pivotal column are zero. row (ii) row (i) gives
1/2
-1/2
PIVOTING
BASIC VARIABLES
VALUE
d t Z
1 0
1/2 1/2
1/2 -1/2
0 1
8 1
PIVOTING BASIC VARIABLES
d 2 1 -16
c 1 1 -14
s 1 0 0
t 0 1 0
VALUE
s t Z
16 9 0
Step 3 - Add suitable multiples of the pivotal row to all other rows until all entries, apart from the pivot, in the pivotal column are zero. row (iii) + 8 row (i) gives
-6
128
BASIC VARIABLES
VALUE
d t Z
1 0 0
1/2 1/2 -6
1/2 -1/2 8
0 1 0
8 1 128
This is our second tableau
PIVOTING Follow the rules for finding a pivot on your second tableau. Pivot as before. Continue this process until there are no negative entries in the objective row. This will be your final tableau. This is called the optimal tableau.
OPTIMAL TABLEAU BASIC VARIABLES
d 1 0 0
c 0 1 0
s 1 -1 2
t -1 2 12
VALUE
d c Z
7 2 140
Note there are no negative entries in the objective row. Can you see the solution?
STEP BY STEP GUIDE
1. Formulate the problem 2. Introduce slack variables 3. Form initial tableau 4. Obtain new tableaux
5. Get the solution
OBTAINING THE SOLUTION
BASIC VARIABLES
d 1 0 0
c 0 1 0
s 1 -1 2
t -1 2 12
VALUE
d c
7 2 140
Remember that since s and t are now nonbasic variables they are set to zero. This corresponds to the solution: s = 0, t = 0, d=7 c=2 Z = 140
THE SOLUTION Dont forget to put your solution back into the context of the problem. Z = 140 d=7 c=2 The maximum profit is 140 To make this profit the factory should produce 7 diggers and 2 cars.
