Optimisation

Optimisation linéaire Exercices
L. Pirau
Assistant ULB
Ex.1. Résoudre graphiquement et par dénombrement des bases : [pic] ([pic][pic] [pic]
| |Sommet |X1 |X2 |t1 |t2 |t3 |Z |Solution |
| |- S0 - |0 |0 |2 |6 |3 |0 |s.b.r. |
| | |0 |-2 |0 |10 |3 |- |s.b. |
| |- S4 - |0 |3 |5 |0 |3 |-6 |s.b.r. |
| | |0 | | | |0 |- |- |
| |- S1 - |2 |0 |0 |4 |1 |2 |s.b.r. = |
| | | | | | | | |s.o. |
| | |6 |0 |-4 |0 |-3 |- |s.b. |
| | |3 |0 |-1 |3 |0 |- |s.b. |
| |- S5 - |10/3 |4/3 |0 |0 |-1/3 |- |s.b. |
| |- S2 - |3 |1 |0 |1 |0 |1 |s.b.r. |
| |- S3 - |3 |3/2 |1/2 |0 |0 |0 |s.b.r. | On remarque une correspondance entre s.b.r. et sommets du domaine
réalisable.
Ex.2. Résoudre graphiquement et par dénombrement des bases : [pic] ([pic][pic] [pic]
| |Sommet |X1 |X2 |t1 |t2 |t3 |Z |Solution |
| |- S0 - |0 |0 |14 |12 |12 |0 |s.b.r. |
| | |0 |14 |0 |-30 |26 |- |s.b. |
| |- S4 - |0 |4 |10 |0 |16 |12 |s.b.r. |
| | |0 |-12 |26 |48 |0 |- |s.b. |
| | |14 |0 |0 |40 |-16 |- |s.b. |
| | |-6 |0 |20 |0 |24 |- |s.b. |
| |- S1 - |6 |0 |8 |24 |0 |6 |s.b.r. |
| |- S3 - |6 |8 |0 |0 |8 |30 |s.b.r. = |
| | | | | | | | |s.o. |
| |- S2 - |26/3 |16/3 |0 |40/3 |0 |24+2/3|s.b.r. |
| |- S5 - |12 |12 |-10 |0 |0 |- |s.b. | On remarque une correspondance entre s.b.r. et sommets du domaine
réalisable.
Ex.2. Résoudre par le simplexe : [pic] ([pic][pic] [pic]
| | |max | |1 |3 |0 |0 |0 |( cj |
| |B |CB |P0 |x1 |x2 |t1 |t2 |t3 |( xj |
| |t1 |0 |14 |1 |1 |1 |0 |0 | ( 1ère s.b.r. |
| | | | | | | | | |explicitée |
|xr ( |t2 |0 |12 |-2 |3 |0 |1 |0 |( aij |
| | | |z0 =|-1 |-3 |0 |0 |0 |( (zj - cj) où : zj|
| | | |0 | | | | | |= (cB ( aij |
| | | |(bi | |(xk | | | | |
| | |max | |1 |3 |0 |0 |0 | |
| |B |CB |P0 |x1 |x2 |t1 |t2 |t3 | |
|xr ( |t1 |0 |10 |5/3 |0 |1 |-1/3|0 | |
| |t3 |0 |16 |4/3 |0 |0 |1/3 |1 | |
| | | |z = |-3 |0 |0 |1 |0 | |
| | | |12 | | | | | | |
| | | | |(xk | | | | | |
| | |max | |1 |3 |0 |0 |0 | |
| |B |CB |P0 |x1 |x2 |t1 |t2 |t3 | |
| |x1 |1 |6 |1 |0 |3/5 |-1/5|0 | |
| |x2 |3 |8 |0 |1 |2/5 |1/5 |0 | |
| |t3 |0 |8 |0 |0 |-4/5|3/5 |1 | |
| | | |z = |0 |0 |9/5 |2/5 |0 |( solution optimale|
| | | |30 | | | | | | |
| | | | | | | | | | |
Ex.1. Résoudre : [pic] ([pic][pic]
| | |max | |18 |6 |0 |0 |0 | |
| |B |CB |P0 |x1 |x2 |t1 |t2 |t3 | |
| |t1 |0 |6 |-4 |3 |1 |0 |0 | |
| |t2 |0 |15 |-1 |3 |0 |1 |0 | |
|xr ( |t3 |0 |4 |1 |-4 |0 |0 |1 | |
| | | | |(xk | | | | | |
| | |max | |18 |6 |0 |0 |0 | |
| |B |CB |P0 |x1 |x2 |t1 |t2 |t3 | |
| |t1 |0 |22 |0 |-13 |1 |0 |4 | |
| |t2 |0 |19 |0 |-1 |0 |1 |1 | |
| |x1 |18 |4 |1 |-4 |0 |0 |1 | |
| | | |z = |0 |-78 |0 |0 |18 |( solution optimale|
| | | |72 | | | | | |infinie |
| | | | | | | | | | | Ex. Résoudre : [pic] ( [pic] ( [pic]
s.b. explicitée mais non réalisable. [pic]
| | |max | |5 |9 |0 |0 |0 |0 | |
| |B |CB |P0 |x1 |x2 |t1 |t2 |t3 |t4 | |
| |t1 |0 |-6 |-2 |-1 |1 |0 |0 |0 | |
| |t2 |0 |70 |7 |10 |0 |1 |0 |0 | |
| |t3 |0 |28 |7 |-4 |0 |0 |1 |0 | |
| |t4 |0 |4 |0 |1 |0 |0 |0 |1 | |
| | | |z0 =|-5 |-9 |0 |0 |0 |0 | |
| | | |0 | | | | | | | |
| | | | | | | | | | | |
( méthode de la base artificielle.
Le P.L. (1) devient : P.L. (2) [pic]
| |max | |5 |9 |0 |0 |0 |0 |-M | | | |B |CB |P0 |x1 |x2 |t1 |t2 |t3 |t4
|v1 | | | |v1 |-M |6 |2 |1 |-1 |0 |0 |0 |1 | | | |t2 |0 |70 |7 |10 |0 |1 |0
|0 |0 | | | |t3 |0 |28 |7 |-4 |0 |0 |1 |0 |0 | | | |t4 |0 |4 |0 |1 |0 |0 |0
|1 |0 | | | | | |z0 = 0 |-2M-5 |-M-9 |M |0 |0 |0 |0 | | | | | | | | | | | |
| | | |
| |max | |5 |9 |0 |0 |0 |0 |-M | | | |B |CB |P0 |x1 |x2 |t1 |t2 |t3 |t4
|v1 | | | |x1 |5 |3 |1 |1/2 |-1/2 |0 |0 |0 |1/2 | | | |t2 |0 |49 |0 |13/2
|7/2 |1 |0 |0 |-7/2 | | | |t3 |0 |7 |0 |-15/2 |7/2 |0 |1 |0 |-7/2 | | | |t4
|0 |4 |0 |1 |0 |0 |0 |1 |0 | | | | | |15 |0 |-13/2 |-5/2 |0 |0 |0 |5/2+M |
| | | | | | | | | | | | | | |
| |max | |5 |9 |0 |0 |0 |0 |-M | | | |B |CB |P0 |x1 |x2 |t1 |t2 |t3 |t4
|v1 | | | |x1 |5 |1 |1 |0 |-1/2 |0 |0 |-1/2 |1/2 | | | |t2 |0 |23 |0 |0
|7/2 |1 |0 |-13/2 |-7/2 | | | |t3 |0 |37 |0 |0 |7/2 |0 |1 |15/2 |-7/2 | | |
|x2 |9 |4 |0 |1 |0 |0 |0 |1 |0 | | | | | |41 |0 |0 |-5/2 |0 |0 |13/2 |5/2+M
| | | | | | | | | | | | | | | |
| |max | |5 |9 |0 |0 |0 |0 |-M | | | |B |CB |P0 |x1 |x2 |t1 |t2 |t3 |t4
|v1 | | | |x1 |5 |30/7 |1 |0 |0 |1/7 |0 |-10/7 |0 | | | |t1 |0 |46/7 |0 |0
|1 |2/7 |0 |-13/7 |-1 | | | |t3 |0 |14 |0 |0 |0 |-1 |1 |14 |0 | | | |x2 |9
|4 |0 |1 |0 |0 |0 |1 |0 | | | | | |402/7 |0 |0 |0 |5/7 |0 |13/7 |+M | | | |
| | | | | | | | | | | |