Cours 9

Volume de Polytopes

La programmation linéaire résoud des problèmes

Max c^t.x

A . x < b

en trouvant des solutions rationnelles. Peut-on trouver des solutions entières?

Peut-on calculer le volume du polytope?

Pour étudier ces problèmes, il faut étudier des grilles régulières et leur intersection avec les polytopes définis par

 A . x < b.

Observations :

Trouver une solution entière au problème de Maximisation (ou une solution sur la grille) peut être beaucoup plus difficile que de de trouver une solution rationnelle. Le problème est NP-dur.
Trouver le volume du polytope est encore plus difficile, bien qu'il existe des cas où le volume soit donné par une formule (cube, pyramide). Le problème est #P-dur.

Hyperplans et grilles :

Il est recommandé de réduire la taille des cellules Excel pour représenter des hyperplans en dimension 2 (droites). Le système de coordonnées est x horizontal x>0 et y>0 vers le bas vertical. L'origine est le coin en haut à gauche.

Représenter graphiquement l'équation d'une droite: y= -x+30

 ' draw line y=  -x+30  I=abscisse et J=ordonnée

 For I = 1 To 30
 J = 30 - I

 Cells(J + 1, I).Select
    With Selection.Interior
        .ColorIndex = 7
        .Pattern = xlSolid
    End With
 Next I

Représenter graphiquement l'équation du polytope défini par:

 y > -x+30
 y < x/2 +30
 y > 2x -30

 Sub Main()
 Worksheets(1).Activate

 ' draw line y=  -x+30

 For I = 1 To 30
 J = 30 - I

 Cells(J + 1, I).Select
    With Selection.Interior
        .ColorIndex = 7
        .Pattern = xlSolid
    End With
 Next I


 ' draw line y=  x/2+30

 For I1 = 1 To 60
 J = 30 + (I1 / 2)

 Cells(J + 1, I1).Select
    With Selection.Interior
        .ColorIndex = 11
        .Pattern = xlSolid
    End With
 Next I1


 ' draw line y=  2x-30

 For I1 = 16 To 45
 J = 2 * (I1) - 30

 Cells(J, I1).Select
    With Selection.Interior
        .ColorIndex = 8
        .Pattern = xlSolid
    End With
 Next I1
 '  UserForm1.Show

End Sub

Le Userform1 est similaire à celui défini lors des marches aléatoires: Argument 1= nombre d'itérations Argument 2 non utilisé CommandeButton1 = Start CommandeButton2 = Stop

Marche aléatoire à l'intérieur du polytope
- Tirage similaire aux précédents: il faut vérifier qu'on reste à l'intérieur

 Private Sub CommandButton1_Click()
 Dim I1 As Integer, J1 As Integer
 Dim v As String
 Worksheets(1).Activate
 ' Bouton d'itération   i: entre 0 et m
 ' Bouton d'itération   j: entre 0 et m
 ' On affiche le point i+1, j+1 dans le carré 1,m-1

I = 30 J = 30 k = 1

  Do While k <= Cells(1, 1) + 1
  Randomize
  L = CInt((Rnd * 4) + 0.5)
  If L = 1 Then I1 = Abs(I - 1)
  If L = 2 Then I1 = I + 1
  If L = 3 Then J1 = Abs(J - 1)
  If L = 4 Then J1 = J + 1
 ' Verify that I1,J1 is inside: Check=0 if outside!

 If (Check(I1, J1) = 0) Then
 I1 = I
 J1 = J
 End If
 ' construct I1;J1 and insert in a sorted list

 v = CStr(I1) + ";" + CStr(J1)
 insertion (v)
 Worksheets(1).Activate
 'Cells(1, 4) = v

 Cells(J1 + 1, I1).Select
    With Selection.Interior
        .ColorIndex = 11
        .Pattern = xlSolid
    End With
 ' update k, I and J
 k = k + 1
 I = I1
 J = J1
 Loop

 End Sub

Fonction Check vérifie si on reste l'intérieur du polytope.

Check=0 si on sort et Check=1 si on est à l'intérieur.

 Function Check(x As Integer, y As Integer) As Integer
 Check = 0
 If (x + y > 30 And y - (x / 2) < 30 And (2 * x) - y < 30) Then Check = 1

 End Function

Fonction insertion qui insère les valeurs I;J dans une liste triée

 Public Sub insertion(valeurcherchee As String)
 Worksheets(2).Activate

 Dim premligne, derligne, lireligne As Double
 ' Dim valeurcherchee As String
 premligne = 2
 derligne = Cells(1, 2) + 1

 'valeurcherchee = InputBox("valeur cherchée")

 While premligne <> derligne - 1
    lireligne = Int((premligne + derligne) / 2)
    Range("A" & lireligne).Select
    If Selection = valeurcherchee Then
 '       MsgBox ("trouvee en " + CStr(lireligne))
        IJ = 1
        Exit Sub
        Else
        If Selection > valeurcherchee Then
            derligne = lireligne
            Else
            premligne = lireligne
        End If
    End If
 Wend

 If Range("A" & premligne).Value = valeurcherchee Then
 ' MsgBox ("trouvé en " + premligne)
 IJ = 1
    Else
    If Range("A" & derligne).Value = valeurcherchee Then
 '     MsgBox ("trouvé en " + derligne)
      IJ = 1
        Else
    'check  < than first
        If Range("A2").Value > valeurcherchee Then
        premligne = 1
        End If
    ' check > last
     If Range("A" & derligne).Value < valeurcherchee Then
     premligne = derligne
     End If
     'general case :insertion just after premligne

 Cells(premligne + 1, 1).Select
    Selection.EntireRow.Insert
     Cells(premligne + 1, 1) = valeurcherchee
     Cells(1, 2) = Cells(1, 2) + 1

        ' MsgBox ("Non trouvé")
    End If
 End If
 End Sub

Volume approché du polytope

La liste triée du Worksheet 2 donne l'ensemble des positions atteintes. Pour voir le volume, il suffit d'insérer le polytope dans un cube dont on connait le volume. Le volume approché est le nombre de positions, c'est-à-dire la taille de la liste divisée par le nombre de points du cube, multiplié par le volume du cube.

Fichier Excel avec toutes les subroutines et fonctions

UP2