Seminar 9:
Multi-criteria programming
Problem 1: Use graphical method to find partial optimal solutions of the multicriteria
linear program:
z1 = 2x1 − x2 → max,
z2 = x2 → max,
on the feasible set X given by the constraints
2x1 + x2 ≤ 18,
x1 + 2x2 ≤ 12,
−x1 + x2 ≤ 3,
x1, x2 ≥ 0
Consider aggregated objective function z = v1 · z1 + v2 · z2 using weights
v1, v2 ≥ 0, v1 + v2 = 1.
Describe the solution of z → maxx∈X with respect to the values of parameters
v1, v2.
Problem 2:
Consider multi-criteria linear program:
z1 = 3x1 + 2x2 + 10 → max,
z2 = x1 − 4x2 + 10 → max
subject to
4x1 + 2x2 ≤ 20
x1 + 3x2 ≤ 12
xj ≥ 0; j = 1, 2
Show that there is no ideal solution. Find a compromise solution using minimal
component method. Do all the calculations by hand in the simplex table.
Problem 3:
Consider the nutritional problem of planning a daily diet for 100 people, with
9 kinds of basic foods available. Composition of foods in terms of important
nutritional components and their prices (all converted to 100g of food) is in the
table:
energy proteins Fe vit. A vit. C chol. price
[kJ] [g] [mg] [units] [mg] [mg] [CZK]
pork meat 1200 18.4 3.1 20 0 83 12
butter 3000 0.6 0.2 2500 0 120 11.2
bread 1160 7.2 0.8 0 0 1 1.5
potatoes 300 1.6 0.6 40 10 0 1.2
apples 240 0 0.5 60 2 0 1.5
eidam cheese 1260 31.2 0.6 1100 0 71 10.6
chicken 650 20.2 1.5 0 0 57 6
yoghurt 450 7 0.2 260 0 11 4.5
strawberries 150 0 0.8 60 60 0 12
Nutritional experts have determined that the daily portion of adult nutrition
should contain at least 80 g of protein, 15 mg of Fe, 6000 units of vitamin A
and 200 mg of vitamin C. To plan a daily catering for 100 people, we need
to determine an optimal composition of the diet while respecting the nutrition
experts’ recommendations. We try to obtain solution with the highest energy
value, the lowest cholesterol content and the lowest price. We have a maximum
of 40 kg of each food.
a) Find partial optima.
b) Convert criteria ”cholesterol and energy”to constraints sequentially allowing
for 10 % deviation from ideal solution.
c) Convert criteria ”cholesterol and energy”to constraints simultaneously allowing
for 10 % deviation from ideal solution