A Company wishes to assign six of its workers to six different jobs (one worker to each job and vice versa). The rating of each worker with respect to each job on a scale of 0 to 10 (10 being a high rating) is given by yhe following table:

Job 1 Job 2 Job 3 Job 4 Job 5 Job 6
Worker 1 8 9 6 3 7 5
Worker 2 4 3 9 7 5 6
Worker 3 7 3 2 1 9 7
Worker 4 4 6 5 4 8 5
Worker 5 7 6 1 2 8 7
Worker 6 4 4 5 4 5 7
If the company wishes to maximize the total rating of the assignment, find the optimal assignment plan and corresponding maximum total rating.

Formulate LP problem

To formulate the linear programming problem, we can define decision variables that represent the assignment of each worker to each job. Let's define binary decision variables x_ij for each worker i and each job j, where x_ij takes a value of 1 if worker i is assigned to job j, and 0 otherwise.

We can then define the objective function that we want to maximize, which is the total rating of the assignment. The rating of each worker for the assigned job can be multiplied by the corresponding decision variable, and the sum of these products across all workers and jobs will give us the total rating. So the objective function is:

Maximize: 8x_11 + 9x_12 + 6x_13 + 3x_14 + 7x_15 + 5x_16
+ 4x_21 + 3x_22 + 9x_23 + 7x_24 + 5x_25 + 6x_26
+ 7x_31 + 3x_32 + 2x_33 + 1x_34 + 9x_35 + 7x_36
+ 4x_41 + 6x_42 + 5x_43 + 4x_44 + 8x_45 + 5x_46
+ 7x_51 + 6x_52 + 1x_53 + 2x_54 + 8x_55 + 7x_56
+ 4x_61 + 4x_62 + 5x_63 + 4x_64 + 5x_65 + 7x_66

Subject to the following constraints:

1. Each worker should be assigned to exactly one job:
x_11 + x_12 + x_13 + x_14 + x_15 + x_16 = 1
x_21 + x_22 + x_23 + x_24 + x_25 + x_26 = 1
x_31 + x_32 + x_33 + x_34 + x_35 + x_36 = 1
x_41 + x_42 + x_43 + x_44 + x_45 + x_46 = 1
x_51 + x_52 + x_53 + x_54 + x_55 + x_56 = 1
x_61 + x_62 + x_63 + x_64 + x_65 + x_66 = 1

2. Each job should be assigned to exactly one worker:
x_11 + x_21 + x_31 + x_41 + x_51 + x_61 = 1
x_12 + x_22 + x_32 + x_42 + x_52 + x_62 = 1
x_13 + x_23 + x_33 + x_43 + x_53 + x_63 = 1
x_14 + x_24 + x_34 + x_44 + x_54 + x_64 = 1
x_15 + x_25 + x_35 + x_45 + x_55 + x_65 = 1
x_16 + x_26 + x_36 + x_46 + x_56 + x_66 = 1

3. The decision variables should be binary:
x_ij = 0 or 1 for all i, j

Now, solving this linear programming problem will provide the optimal assignment plan and the corresponding maximum total rating.