Exercise: Optimization and Simulation
Exercise Sheet 1
Jörg Ebner - Information Systems Research
November 14, 2024
Jörg Ebner - Information Systems Research Exercise: Optimization and Simulation November 14, 2024 1 / 10
Semester overview
Exercise sessions:
1 14.11.24 - Linear Optimization
2 21.11.24 - Simplex and Big-M
3 05.12.24 - Revised Simplex
4 09.01.25 - Duality
5 23.01.25 - Simplex with R
6 30.01.25 - Transportation Problem
7 06.02.25 - Q&A Session
Changes to be announced on Ilias
Deadline for bonus points: February 16, 2025 at the end of the day
Exam: February 26, 2025
Jörg Ebner - Information Systems Research Exercise: Optimization and Simulation November 14, 2024 2 / 10
Introduction to Linear Optimization
Definition: Mathematical method for finding the best outcome in a
model with linear relationships.
Objective: To maximize or minimize a linear objective function while
adhering to a set of linear equality and inequality constraints.
Solving Methods: Simplex method and the Interior-Point method
(among others).
Decision Variables: Represent the choices to be made, subject to
constraints.
Matrix Representation: Can be represented using matrices,
enhancing computational efficiency (Revised Simplex).
Applications: Widely applied in operations research, economics,
finance, engineering, and management.
Jörg Ebner - Information Systems Research Exercise: Optimization and Simulation November 14, 2024 3 / 10
Question 1
A furniture company requires at least the following:
200 sheets of plastic with size 150 cm x 150 cm (Format A)
300 sheets of plastic with size 200 cm x 110 cm (Format B)
100 sheets of plastic with size 250 cm x 150 cm (Format C)
However, their supplier can only deliver sheets with size 200 cm x 520 cm.
Therefore, the furniture company needs to cut the sheets upon their
receipt. It can cut the sheets in any of the following ways:
The company needs to perform the cutting in a way that minimizes the
waste of material, or in other words to minimize the number of sheets they
need to order. Formulate this task as a linear optimization problem.
Jörg Ebner - Information Systems Research Exercise: Optimization and Simulation November 14, 2024 4 / 10
Question 1 - Solution
Decision variables:
x1 ... Number of sheets with cut 1
x2 ... Number of sheets with cut 2
...
x6 ... Number of sheets with cut 6
6
P
Objective function: min z = x1 + x2 + ... + x6 = xi
i=1
Constraints:
Format A: 3x1 + 0x2 + 0x3 + 0x4 + x5 + 2x6 ≥ 200
Format B: 0x1 + 4x2 + 0x3 + 2x4 + x5 + 2x6 ≥ 300
Format C: 0x1 + 0x2 + 2x3 + x4 + x5 + 0x6 ≥ 100
Non-negativity conditions: x1 , ..., x6 ≥ 0.
Jörg Ebner - Information Systems Research Exercise: Optimization and Simulation November 14, 2024 5 / 10
Question 2
In an agricultural business, farmers take care of cows and sheep. There is
enough space for 50 cows and 200 sheep, and the total pasture land spans
over 72 acres. A cow needs 1 acre, while a sheep needs 0.2 acres for
grazing. There are several workers who take care of the animals for a total
of 10,000 hours per year. For each cow 150 hours and for each sheep 25
hours per year are needed. The yearly profit per cow amounts to 250
euros, and per sheep to 45 euros. In order to determine the maximum
profit that can be obtained by the farm:
a Formulate the question as a linear optimization problem.
b Solve the linear optimization problem graphically.
c Check the solution with R. Determine the binding constraints in both
the graphical solution from (b) and from the output of the
solveLP() function.
Jörg Ebner - Information Systems Research Exercise: Optimization and Simulation November 14, 2024 6 / 10
Question 2a - Linear Optimization Problem
Let x1 denote the number of cows, and x2 the number of sheep. The linear
optimization problem can be expressed in the following way:
max z = 250x1 + 45x2
s.t. x1 + 0.2x2 ≤ 72 (pasture)
150x1 + 25x2 ≤ 10, 000 (working hours)
x1 ≤ 50 (stables)
x2 ≤ 200 (stables)
x1 , x2 ≥ 0
Jörg Ebner - Information Systems Research Exercise: Optimization and Simulation November 14, 2024 7 / 10
Question 2b - Graphical Solution
Transformation of the constraints:
x2 ≤ −5x1 + 360
x2 ≤ −6x1 + 400
x1 ≤ 50
x2 ≤ 200
Transformation of the objective function:
z 50
x2 = − x1
45 9
Jörg Ebner - Information Systems Research Exercise: Optimization and Simulation November 14, 2024 8 / 10
Question 2b - Graphical Solution
From the graph, we can see that the optimal solution occurs at: x1∗ = 40,
x2∗ =160. This yields z ∗ = 17,200.
Jörg Ebner - Information Systems Research Exercise: Optimization and Simulation November 14, 2024 9 / 10
