I am trying to solve an optimization problem (variation of assignment problem). I'm stuck with how to represent this problem (as an LP or graph based). If it's formulated as a LP, I'm unsure of how to formulate it. (I have limited Math knowledge, and it's been quite long so I really could use some help).
Assume there are some students, and some teachers. There are different types of students, say based on their subject preference. Similarly, there are different types of teachers, say based on their expertise (Science, Math etc.). Students and teachers can have multiple types. Also, each student and teacher type has certain minimum and maximum assignments possible. The total assignments required for each student and teacher is fixed. There is a cost associated with assigning any student and teacher (the fees). We need to minimize the total fees paid by all students combined
For example:
Student1_subject denotes the number of credits Student1 takes of subject.
Similarly, Teacher1_subject denotes the number of credits (number of classes) the teacher teaches (with constraints) for subject.
The fees matrix shows the fees paid by student_i to teacher_j. If Student_x is paired with Teacher_y, fees charged is as per the table. If student_x and teacher_y are not paired, then fees charged is 0.
$1 \leq student1_{science} \leq 3 ;\\$ $3 \leq student1_{math} \leq 5 ;\\$ $\sum_{subj = science, math} student1_{subj} = 5 ;\\$
$2 \leq student2_{science} \leq 4 ;\\$ $6 \leq student2_{math} \leq 10 ;\\$ $\sum_{subj = science, math} student2_{subj} = 11 ;\\$
$ \\\\$ $2 \leq teacher1_{science} \leq 2 ;\\$ $\sum_{subj = science} teacher1_{subj} = 2 ;\\$
$3 \leq teacher2_{science} \leq 5 ;\\$ $0 \leq teacher2_{math} \leq 2 ;\\$ $\sum_{subj = science, math} teacher2_{subj} = 4 ;\\$
$0 \leq teacher3_{science} \leq 5 ;\\$ $3 \leq teacher3_{math} \leq 5 ;\\$ $\sum_{subj = science, math} teacher3_{subj} = 5 ;\\$
Now the fee matrix is as follows:
| Teacher1 | Teacher2 | Teacher3
Student1 | 10 | 15 | 30
Student2 | 4 | 23 | 19
Student3 | 12 | 32 | 56
$$ min: \sum_{teacher=1}^3 \sum_{student=1}^2 fees_{student, teacher} $$ where $fees_{student, teacher}$ is equal to the corresponding value in table if $student$ and $teacher$ are paired, else 0.
We need to match these students and teachers together, ensuring that the total fees paid by all students combined is minimized. (Note: One pairing of teacher and student costs just once, not based on their capacities).
This is just an example of what I'm trying to do, but if I'm unclear, I could take another more detailed example.