Homework Help: Linear Programming Problem

1. Nov 23, 2008

cyeokpeng

The admissions office at State University wants to develop a planning model for next year's entering freshman class. The university has 4500 available openings for freshmen. Tuition is $8600 for a local student, and$19200 for an overseas student. The university wants to maximize the tuition fees it receives new year. By state mandate, it can admit no more than 47% overseas students. Also, each college in the university must have at least 30% local students in its freshmen class.

In order to be ranked in several national magazines, it wants the freshmen class to have an average SAT score of 1150. Following are the average SAT scores for last year's freshmen class for local and overseas students in each college in the university plus the maximum size of the freshmen class for each college:

College Local (SAT) Overseas (SAT) Total Capacity
1. Architecture 1350 1460 470
2. Arts and Social Sciences 1010 1050 1300
3. Agriculture 1020 1110 240
5. Engineering 1360 1420 1060
6. Human Resources 1000 1400 610

Ans: (Textbook question, but no answers)

I show some of the workings, not all because too tedious:
Let the decision variables be xj = no. of students as shown in the table below
College Local Overseas
1. Architecture x1 x2
2. Arts and Social Science x3 x4
3. Agriculture x5 x6
5. Engineering x9 x10
6. Human Resources x11 x12

Objective Function
Maximize tuition fees,
Z = \$ 8600x1 + 19200x2 + 8600x3 + 19200x4 + 8600x5 + 19200x6
+ 8600x7 + 19200x8 +8600x9 + 19200x10 + 8600x11 + 19200x12

Subject to:
Class size constraints for each college is straightforward, there are 6 of them, with total no. of students in that college <= stated class size.

The two state policies are also straightforward, so I don't waste time showing.

I only have problems in the last type of constraints i.e. the constraints relating to the average SAT scores.
The constraints talk about each of the class must have an average SAT score of 1150. We are only given past year average SAT scores for each local and overseas student in each type of college. Question is: with only these limited info, how are we going to model these constraints?

I tried this way of modeling the average SAT score constraints, but it gives me with some problems too.
Using past year SAT scores to model this year scores (assume),
(Estimated total scores for local students in certain college*no. of local students +
Estimated total scores for overseas students in same college*no. of overseas students) / total no. of students in that college ≥ 1150
Hence, there will be 6 constraints for 6 different colleges!

But after some algebraic manipulations, some constraints seem to be nonsensical.
Eg. −200x1−310x2 ≤ 0 (always true, so can delete)
140x3 + 100x4 ≤ 0 (always false)
130x5 + 40x6 ≤ 0 (always false)
60x7 − 30x8 ≤ 0 (this constraint is ok)
−210x9−270x10 ≤ 0 (always true, so can delete)
150x11 − 250x12 ≤ 0 (this constraint is ok)

Can I make some reasonable assumptions to solve this problem?
Like, since in the Arts & Social Sciences college and Agriculture college, it is impossible to make the average SAT score to meet minimum standards, so we leave it out of the constraints.

i.e. the constraints (using those with physical meaning) for these become:
60x7 − 30x8 ≤ 0
150x11 − 250x12 ≤ 0

Is there any logical error behind this reasoning and assumptions?

2. Nov 23, 2008

lurflurf

I think you need to assume that this years class will have the sat average as last year. The constaint is for the whole school not each college
ie
−200x1−310x2 +140x3 + 100x4 +130x5 + 40x6 +60x7 − 30x8 −210x9−270x10+150x11 − 250x12 ≤ 0

It is obvious that some of the colleges (arts and ag) do not meet the standard individually.

3. Nov 23, 2008

cyeokpeng

Oh, I didn't think of that. So the min. standard for average SAT score 1150 is for the whole university! So that makes sense, and the constraint formed is much reasonable!

Thank you!