Seminar 1:
Linear programming, building the model
Problem 1: Build the mathematical problem of the problem:
a) Marketing campaign problem
The advertising agency has to design marketing campaign using 5 media channels
(television, internet, radio, newspaper, banners) in order to maximize the
overall marketing effect expressed by the number of people reached by the campaign.
Advertising is primarily focused on certain categories of persons by age,
income and education. The sponsor’s requirements are as follows:
• At most 50 % of the amount would be allocated to the TV and internet
campaign.
• We have to allocate at least 10% but no more than 30 % of total budget in
each media
• We need to reach at least 2,5 mil. people 30-50 years old, at least 0,8 mil.
people with monthly income 40,000 CZK or more and at least 1,5 mil.
people with higher education.
The total amount of funds for the campaign is CZK 10 million. Based on regular
surveys conducted by the advertising agency, it has been estimated that when
spending CZK 1,000 in the media, the following numbers of people from the
respective categories will be reached by the media channel:
media channel TV internet radio newspaper banners
total 750 420 300 360 180
age 30 - 50 320 280 140 240 120
income > 40,000 CZK 120 90 60 60 50
higher education 350 200 120 140 60
Design a marketing campaign maximizing number of reached respondents and
meeting the requirements of the sponsor and the budget constraints.
b) Portfolio diversification problem
Management of a financial institution plans to invest 50 million Czech crowns in
securities. There are five options: three types of shares A1, A2, A3 and two types
of bonds O1, O2. Each of these five variants is characterized by the expected
yield in per cent per year and an index expressing the investment risk, see the
table:
A1 A2 A3 O1 O2
yield [%] 25 18 20 14 12
risk index 9 5 7 3 1
The company ’s investment strategy assumes:
• to invest at least 50% of the total amount in bonds
• the overall risk index (the weighted average risk of each option) does not
exceed 5
• none of the options will be purchased in less than 5 million Czech crowns
The aim of the model is to design a portfolio structure that will maximize the
expected return on investment, while respecting the investment strategy.
c) Hillier and Lieberman, 3.4-7.
Ralph Edmund loves steaks and potatoes. Therefore, he has decided to go on a
steady diet of only these two foods (plus some liquids and vitamin supplements)
for all his meals. Ralph realizes that this isn’t the healthiest diet, so he wants
to make sure that he eats the right quantities of the two foods to satisfy some
key nutritional requirements. He has obtained the following nutritional and cost
information:
Ingredient Grams of Ingredient Daily Requirement
per Serving
Steak Potatoes (Grams)
Carbohydrates 5 15 ≥ 50
Protein 20 5 ≥ 40
Fat 15 2 ≤ 60
Cost per serving 4 2
Ralph wishes to determine the number of daily servings (may be fractional)
of steak and potatoes that will meet these requirements at a minimum cost.
Formulate a linear programming model for this problem. and use the graphical
method to solve this model.
Problem 2: Use the graphical method to solve the LP problem:
z = 2x1 − x2 → min.
subject to
x1 − x2 ≥ −2
x1 + x2 ≤ 6
x1 − x2 ≤ 0
x1 ≥ 1
x2 ≥ 0
And answer following questions:
• Would the solution be the same if the inequalities are strict?
• Find the solution of the same problem with opposite inequality in the
second constraint: x1 + x2 ≥ 6?
• Does the corresponding maximization problem have solution?