linear programming

Question

An undergraduate is determining her course schedule for the fall semester. She is considering five courses, which are shown in the following table. Also included are the number of hours she expects to have to devote to each course each week and her expected grade in each course:

Course                         Hours per Week            Expected Grade
Management I                     5                                   3
Principles of Accounting       10                                  4
Marketing                            8                                  2.7
Management                       7                                    3
Information System            10                                  2.7

She does not want to work more than 32 hours each week. Principles of Accounting, Marketing, and Information System all require a lot of computing and mathematics, and she would like to take no more than two of these courses. To remain on schedule and meet prerequisites, she needs to take at least two of the following courses: Management I, Principles of Accounting and Information System. The student wants to develop a course schedule that will maximize the total expected grade.

Formulate a capital budgeting problem for the above situation by determining

(a) The decision variables.
(b) The objective function.
(c) All the constraints.

Answer 1

This falls into the category of a very poorly written question which is probably one reason why no tutor has answered it for months. The question assumes a different type of universe where a student can predict their expected grade and number of hours per week they need to devote to a course in advance before deciding whether to take a course. It's also an extreme version of a yes-or-no universe where the options are:

 

Yes: A student takes a course, spends the given number of hours, and receives an expected grade

No: A student does not take the course

 

That's probably another reason no tutor has answered the question. In a universe like that one, who would ever need a tutor?

 

And finally, there are two different courses with the names "Management" and "Management I." It's as if the person who wrote the question were intentionally trying to make it as unrealistic and unacademic as possible. Finally, there's a course called "Information System" without the "s." This question may be more about a new educator learning to write questions by trial-and-error than it is about students learning linear algebra.

 

So much for the rant. Now let's temporarily enter the question-writer's universe and try to answer the question.

 

a) Decision Variables:  The decision variables are five binary variables. The student can take Management I (yes or no), Principles of Accounting (yes or no), Marketing (yes or no), Management (yes or no), Information System (yes or no). Because each variable has only two possible states, there are only 2^5 = 32 possible answers to the question. Let's call those five variables A, B, C, D, and E in the order that you listed them. Each can have a value of zero for no and one for yes. This subtype of linear programming is sometimes called zero-one linear programming.

 

b) Objective Function: Total expected grade should be maximized. I'm pretty sure that the question writer meant the total of the grade points from the rightmost column for the courses that the student selects. Let's call that x.

 

c) Constraints: Let's call hours per week h. One constraint is h≤32. The others are combinations of binary variables that are required or forbidden. She cannot take more than two of Principles of Accounting (B), Marketing (C), and Information System (E), so she's forbidden from taking all three of these courses. With binary variables, this means that B+C+E<3. (This constraint could also be expressed as B×C×E≠1 or B×C×E=0.) She needs to take at least two of Management I (A), Principles of Accounting (B), and Information System (E), so A+B+E≥2.

 

So the total problem is:

 

Given five binary variables, A through E, maximize:

 

3A+4B+2.7C+3D+2.7E (I called this value x)

 

given the constraints:

 

5A+10B+8C+7D+10E≤32 (I called this value h)

B+C+E<3

A+B+E≥2

 

Ready to try to answer the question? With a little bit of tweaking of the variable names and constraints, something called the Balas Additive Algorithm could be used. Another method would be to use the final two constraints to narrow down the 32 possible answers to a smaller number, determine h and x for each possible answer, and then find the maximum x among those choices that meet the criterion for h. This wouldn't be that difficult using Excel, and it's the method I'd use to answer the question.