Chapitre 2 Flashcards
What are xD and xE ?
decision variables in canonical form are noted xD , The standard form will always be obtained by adding some slack variables xE to the canonical problem
what are c and x in terms of vector ?
Matrix Notation : c is a row-vector and x is a column-vector, in general, the scalar product between two vectors x and y is denoted by xT y
Matrix Form of a Canonical PL and Matrix Form of a Standard PL
Go check in course
Transformation Rules :
Minimization ↔ maximization:
Inequation ≥ ↔ inequation ≤ :
Equation → inequation ≤ :
Inequation → equation:
Real variable → non-negative variable:
Variable with a lower bound:
min f (x) = −max (−f (x))
ax ≥ b ⇐⇒ (−a)x ≤ −b
ax ≤ b and (−a)x ≤ −b
ax ≤ b ⇐⇒ ax + s = b, s ≥ 0 and ax ≥ b ⇐⇒ −ax + s = −b, s ≥ 0
x = x+ − x− and x+, x− ≥ 0
x′ = x − b and x′ ≥ 0
Min-max or max-min problem
Min z = max{c1x, . . . , ckx}
Min z = max{c1x, . . . , ckx}
⇐⇒
Min z = t
s.t. t ≥ c1x
. . .
t ≥ ckx
t ∈ R
Particular Transformations : Absolute value
|x| ≤ b
⇐⇒
x ≤ b
x ≥ −b
Chebychev Approximation : Determine a linear approximation y = ax +b minimizing the largest
estimation error
Min z = max |yi − axi − b|
Min z = t
s.t. t ≥ yi − axi − b i = 1, . . . ,m
t ≥ −yi + axi + b i = 1, . . . ,m
How to solve a Linear System:
Ax = b
first we create B which is constituted of m linearly independent columns of A.
then we find B-1 =1/(ad − bc) (d −b)
(−c a )
then we calculate B-1 * (AIB)
we set the column of base B as free variables (for example x2 and x4) we replace the others with s,t
what is an ordered basis ?
Every matrix B formed by m linearly independent column of A is an ordered basis of the system.
Columns forming B are called basic, the other non-basic.
Variables corresponding to the columns of B are called basic, the other non-basic.
By extension, we call a basis the ordered list of basic variables or their indices.
It is denoted by beta example (2,4)
what is a basic solution corresponding to base B.
The particular solution obtained by fixing non-basic variables xN to 0 is called a basic solution corresponding to base B.
It is given by: xB = B−1b and xN = 0
Basic Solution of a Standard LP
AxD + IxE = b
xD , xE ≥ 0
If we choose the initial base B0 = I formed by the slack variables, then the basic solution is given by
xB = xE = b and xN = xD = 0 (xn = non basic decision variable)
Basic Solution of a Standard LP : why the basic solution lies at the intersection of the n
hyperplans corresponding to the non-basic variables ?
Consequence: for a problem with two decision variables, the basic solutions correspond to the intersections of the straight lines defined
by the constraints, including non-negativity constraints.
For any basis B, its basic solution is obtained by fixing the n non-basic variables to 0
If the ith slack variable (xn+i ) is fixed to 0, then the solutions lie in the following hyperlan:
ai1x1 + . . . + ainxn = bi
If the jth decision variable is fixed to 0, the solutions lie in the following hyperplan:
xj = 0
Consequently, the basic solution lies at the intersection of the n hyperplans corresponding to the non-basic variables.
what is a pivoting matrix ?
Pivoting corresponds to premultiplying the matrix (A | b) by a pivoting matrix. It differs from the identity matrix by only 1 column.
What is a Chebychev Approximation
Determine a linear approximation y = ax +b minimizing the largest estimation error
What Can We Do With a Constraint of Type |x| ≥ b
attention : This is not a linear constraint !
We have to decompose the orginal problem into two sub-problems :
▶ Replace |x| ≥ b with x ≤ -b in the first one
▶ Replace |x| ≥ b with x ≥ b in the second one
The final solution is given by the best solution of these two sub-problems
