A search engine needs to decide which advertisement to show on the search results page each time a user searches for a keyword. Assume there are m keywords that users can search for, and the number of queries for keyword j is estimated to be vj . There are n advertisers. The i-th advertiser has budget bi and is willing to pay a price pij for an advertisement shown on the search results page for keyword j. Assume that only one advertisement can be shown on each search results page. The search engine needs to decide, for each (i, j), the fraction (or if you prefer, the number) of search results pages for keyword j that will show an advertisement from advertiser i. The search engine's goal is to maximize its revenue. Formulate this as a linear program.