Chapitre 1

Question 1

What is the point of an optimization problem ?

Answer 1

Finding the best solution from
among the set of all feasible solutions

Question 2

What does an optimization problem involves ?

Answer 2

It involves maximizing or minimizing a function f (x) over a set of constraints that can be equalities or inequalities

Question 3

What types of numbers can I an optimization problem contain ?

Answer 3

R : real numbers
Z : integers
N : non-negative integers

Question 4

What are some transformation rules to pass from :
- Max to min
- < to >
- equality to inequalities

Answer 4

max f (x) ⇐⇒ -min -f (x)

g(x) ≤ 0 ⇐⇒ -g(x) ≥ 0

g(x) = 0 ⇐⇒ g(x) ≤ 0 and g(x) ≥ 0

Question 4

What is the definition of : discrete optimization and two examples

Answer 4

Some or all of the variables used in a discrete mathematical program are restricted to be discrete variables - that is, to assume only a discrete set of values, such as the integers.

Combinatorial optimization, which refers to problems on graphs, matroids and other discrete structures.
Traveling Salesman Problem (TSP)

Integer Programming: Optimization where some or all variables are required to be integers.
Investment decisions in a company and scheduling drivers to meet daily demands

Question 5

What is the definition of : Unconstrained optimization versus constrained optimization

Question 6

What is a continuous optimization

Answer 6

Variables can take any real value within a given range.

Question 7

What is the definition of linear programming ?

Answer 7

A linear program is an optimization problem consisting in :
- Maximizing (or minimizing) a linear objective function
- Of n REAL variables subject to a set of constraints - Expressed as linear equations or linear inequalities
- lj = −∞ and uj = +∞ are possible values
- It is implicitly assumed that xj ∈ R for j = 1, . . . , n

Integer linear programming is different from linear programming !

Question 8

Give an example of linear programming.

Answer 8

A company operates two canning plants A and B. The growers G1, G2,G3
are willing to supply cereals in the following amounts:
G1: 200 tonnes at $11 per tonne
G2: 310 tonnes at $10 per tonne
G3: 420 tonnes at $9 per tonne
Shipping costs in $ per tonne are:

Question 9

What are the decision variables, the objective function and the types of constraints of linear programming ?

Answer 9

Variables x1, . . . , xn are called the decision variables of the problem.

The linear function to optimize is called the objective function.

Constraints can be linear equations or linear inequalities.

Constraints of type
lj ≤ xj ≤ uj lj , uj ∈ R ∪ {±∞}
are called constraint bounds.
They are generally treated in a special way by the algorithms.
In many cases, constraint bounds are just expressed as non-negativity constraints xj ≥ 0

Question 10

What are the fundamental assumptions of Linear programming ?

Answer 10

(1) Linearity: the impact of decision variables is linear in constraints and in objective function.

(2) Divisibility: non-integer values of decision variables are acceptable.

(3) Certainty: values of parameters are known and constant.

Question 11

What is the definition of feasibility and of the feasible region ?

Answer 11

A solution is feasible if it satisfies all the constraints of the problem
(including bound constraints)

The feasible region corresponds to the set of all the feasible solutions
of the problem.

Question 12

What is an half-space ?

Answer 12

The set of solutions of a linear inequality corresponds to a half-space
in R^n (a half-plane in R^2)

Question 13

What is an hyperplan ?

Answer 13

The set of solution of a linear equation corresponds to an hyperplan
in Rn (a straight line in R2)

Question 14

What is the geometry of a set of solution of inequalities and a linear equation

Answer 14

it is the set of solutions of the system, it correspond to the intersection of half-spaces and hyperplans defined by each element of the system.
This intersection is the feasible region. It is a convex set and de fines a polyhedron in R^n

Question 15

what is a convex set ?

Answer 15

A set C ⊆ Rn is convex if for all x1, x2 ∈ C

xλ = λx1 + (1 − λ)x2 ∈ C ∀λ ∈ [0, 1]

If λ = 0, then xλ = x2. When λ = 1, then xλ = x1

A set is convex if and only if every convex combination of its elements belongs to the set itself

Question 16

Feasible Region in the Plane can be :

Answer 16

1. Empty: it means that the problem has no feasible solution and consequently no optimal solution.
2. Bounded. A bounded feasible region may be enclosed in a circle. The LP has both a maximum value and a minimum value for the objective function.

3.Unbounded. An unbounded feasible region cannot be enclosed in a circle, no matter how big the circle is. If the coefficients on the
objective function are all positive, then an unbounded feasible region has a minimum but no maximum. In the last case, we say that the LP has no (finite) optimal solution and is unbounded

Question 17

How to find the contour line ?

Answer 17

Find first the origin then shift the origin line to the direction of the gradient Let z = f (x1, x2) = a1x1 + a2x2, then its gradient is the vector given
by (a1 a2)

Question 18

how to find a local max or min ?

Answer 18

first derivative must be equal to 0 and then second must be > or < depending on max or min

Question 19

what is the formula for the inverse of a 2x2 matrix ?

Answer 19

Det(B)=ad−bc

B ^−1= 1/Det(B) *( d−c)
​ (−b a)

Question 20

Canonical Form of a Linear Program

Answer 20

Maximization problem
All constraints are of type ≤
All variables are non-negative

Question 21

Standard Form of a Linear Program

Answer 21

Maximization problem
All constraints are equalities
All variables are non-negative

Question 22

From Canonical to Standard Form

Answer 22

Addition of slack variables xn+i