Chapitre 1 Flashcards
What is the point of an optimization problem ?
Finding the best solution from
among the set of all feasible solutions
What does an optimization problem involves ?
It involves maximizing or minimizing a function f (x) over a set of constraints that can be equalities or inequalities
What types of numbers can I an optimization problem contain ?
R : real numbers
Z : integers
N : non-negative integers
What are some transformation rules to pass from :
- Max to min
- < to >
- equality to inequalities
max f (x) ⇐⇒ -min -f (x)
g(x) ≤ 0 ⇐⇒ -g(x) ≥ 0
g(x) = 0 ⇐⇒ g(x) ≤ 0 and g(x) ≥ 0
What is the definition of : discrete optimization and two examples
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
What is the definition of : Unconstrained optimization versus constrained optimization
What is a continuous optimization
Variables can take any real value within a given range.
What is the definition of linear programming ?
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 !
Give an example of linear programming.
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:
What are the decision variables, the objective function and the types of constraints of linear programming ?
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
What are the fundamental assumptions of Linear programming ?
(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.
What is the definition of feasibility and of the feasible region ?
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.
What is an half-space ?
The set of solutions of a linear inequality corresponds to a half-space
in R^n (a half-plane in R^2)
What is an hyperplan ?
The set of solution of a linear equation corresponds to an hyperplan
in Rn (a straight line in R2)
What is the geometry of a set of solution of inequalities and a linear equation
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
what is a convex set ?
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
Feasible Region in the Plane can be :
- Empty: it means that the problem has no feasible solution and consequently no optimal solution.
- 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
How to find the contour line ?
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)
how to find a local max or min ?
first derivative must be equal to 0 and then second must be > or < depending on max or min
what is the formula for the inverse of a 2x2 matrix ?
Det(B)=ad−bc
B ^−1= 1/Det(B) *( d−c)
(−b a)
Canonical Form of a Linear Program
Maximization problem
All constraints are of type ≤
All variables are non-negative
Standard Form of a Linear Program
Maximization problem
All constraints are equalities
All variables are non-negative
From Canonical to Standard Form
Addition of slack variables xn+i
