Jump to content
Sign in to follow this  

Linear Programming Problem

Recommended Posts

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

4. Business 1090 1180 820

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

4. Business x7 x8

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?

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.