Einführung

Dieser Artikel ist der 4. Artikel zur Lösung der Übung des Referenztextes "Problemlösungsserie von Python: Erstellen eines Optimierungsmodells mithilfe einer Datenanalysebibliothek" zur mathematischen Optimierung.

Der erste Artikel ist unten. Bitte sehen Sie zuerst hier.

Lösen Sie mathematische Optimierungsmodellübungen mit den OR-Tools von Google (1) Das einfachste Problem beim Füllen von Massen https://qiita.com/ttlabo/private/7e8c93f387814f99931f

Löse den Zahlenplatz (Nampure)

Dies ist die dritte Übung im Referenztext. Versuchen wir die folgenden Probleme sofort.

: language_balloon: Problem

`ruby:7.3.Problem`


Nummer Platz in der Abbildung unten(Nampre)Lösen. Die Bedingungen sind jedoch wie folgt.
① Achten Sie darauf, die Zahlen 1 bis 9 in alle 9x9-Felder einzugeben.
(2) Dieselbe Nummer kann nur einmal in einer Zeile, einer Spalte und einem 3x3 verwendet werden.
③ Wenn die Nummer gefüllt ist, verwenden Sie diese Nummer.

: Frage: ** Denken **

■ Stellen Sie sich ein mathematisches Modell vor Betrachten Sie 729 9x9x9-Felder, wie in Abbildung 2 dargestellt. Die Achsenrichtung ist Zeilen-, Spalten- und Zellennummer. Eine Zellennummer bedeutet eine Nummer, die in jeden Frame der Nummer passt.

Angenommen, ein Feld hat entweder ausgewählte oder nicht ausgewählte Zellennummern.

Angenommen, das erste Feld von unten in der 1. Zeile und 1. Spalte hat 1, wenn die Nummer 1 in der 1. Zeile und der 1. Spalte der Nummer ausgewählt ist, und 0, wenn sie nicht ausgewählt ist. Anschließend zeigt das zweite Feld am unteren Rand der ersten Zeile und der ersten Spalte an, ob die Nummer 2 ausgewählt ist oder nicht, und das obere Feld zeigt an, ob die Nummer 9 ausgewählt ist oder nicht. Diese setzen sich in gleicher Weise bis zur 9. Zeile und 9. Spalte fort. Wenn das Feld mit der Zellennummer z in der Spalte x y Spalte der Zellennummer z 1 ist, bedeutet dies im Allgemeinen, dass die Nummer in der Zelle der Zeile x Zeile y Spalte der Nummer z ist.

Unter der Annahme einer solchen Box werden wir sie formulieren.

: a: ** Antwort **

Jede dieser 729 Boxen ist 0 oder 1. Die Einschränkungen sind wie folgt:

(1) In einer Zelle von Nampre kann nur eine Nummer eingegeben werden. Das heißt, der Gesamtwert von 9 Feldern mit 1x1x9 (Zeile x Spalte x Zellennummer) beträgt 1. (2) In einer Zellenzeile kann nur dieselbe Nummer eingegeben werden. Der Gesamtwert von 9 9x1x1-Kartons beträgt 1 (3) In einer Zellenreihe kann nur dieselbe Nummer eingegeben werden. Der Gesamtwert von 9 Kartons mit 1x9x1 beträgt 1. (4) In das 3x3-Quadrat kann nur eine gleiche Zahl eingegeben werden. Der Gesamtwert von 9 3x3x1-Kartons beträgt 1.

3x3 Quadrate sind die 9 Quadrate, die durch die dicke Linie in der Abbildung angezeigt werden, die der Problemstellung beigefügt ist. (5) Wenn die Nummer von Anfang an angegeben wurde (die Abbildung, die der Problemstellung beigefügt ist), verwenden Sie diese Nummer. Der Gesamtwert einer Box mit 1x1x1 beträgt 1.

Betrachten Sie das Programm. Der Inhalt des Programms folgt im Wesentlichen dem OR-Tools-Handbuch von Google. (https://developers.google.com/optimization)

Schreiben Sie zu Beginn des Programms einen Zauber.

`ruby:7.4.renshu.py`


from __future__ import print_function
from ortools.linear_solver import pywraplp
import numpy as np

Da es durch den Mixed Integer Planning Solver gelöst wird, wird es unten deklariert.

`ruby:7.4.renshu.py`


# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

Definieren Sie die 9x9-Quadrate der fraglichen Zahl im folgenden zweidimensionalen Array vor.

`ruby:7.4.renshu.py`


pre = [[0,0,6,0,0,0,0,0,1],
       [0,7,0,0,6,0,0,5,0],
       [8,0,0,1,0,3,2,0,0],
       [0,0,5,0,4,0,8,0,0],
       [0,4,0,7,0,2,0,9,0],
       [0,0,8,0,1,0,7,0,0],
       [0,0,1,2,0,5,0,0,3],
       [0,6,0,0,7,0,0,8,0],
       [2,0,0,0,0,0,4,0,0]]

Deklarieren Sie 9x9x9-Felder als dreidimensionale Array-Variablenwürfel.

`ruby:7.4.renshu.py`


dice = {}

Definieren Sie für 9x9x9-Boxen (Würfelboxen) jede Box mit einer Variablen. Schleife die Linie von 1 bis 9 mit der Variablen x. Schleife die Spalte von 1 bis 9 mit der Variablen y. Schleife mit der Variablen z in Richtung der Zellennummer.

`ruby:7.4.renshu.py`


#Variable Definition der Würfelbox
for x in range(9):
    for y in range(9):
        for z in range(9):
            dice[x,y,z] = solver.BoolVar("dice%i%i%i" % (x,y,z))

Die Einschränkungen sind unten definiert.

** Einschränkungen (1) ** `In einer Zelle der Nummer kann nur eine Nummer eingegeben werden. Das heißt, der Gesamtwert von 9 Feldern mit 1x1x9 (Zeile x Spalte x Zellennummer) beträgt 1. `` Verwenden Sie solver.Sum (), um den Gesamtwert zu erhalten. Der zu summierende Wert beträgt 1 bis 9 Quadrate in z-Richtung der Würfel, und z wird in der Einschlussnotation von 1 bis 9 wiederholt (tatsächlich schleift der Indexwert von 0 bis 8).

`ruby:7.4.renshu.py`


for x in range(9):
    for y in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for z in range (9)]) == 1)

** Einschränkung (2) ** In die Zelle einer Zeile kann nur eine gleiche Nummer eingegeben werden. Der Gesamtwert von 9 Kartons mit 9x1x1 beträgt 1

`ruby:7.4.renshu.py`


for y in range(9):
    for z in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for x in range (9)]) == 1)

** Einschränkung (3) ** (3) In einer Spalte kann nur dieselbe Nummer eingegeben werden. Der Gesamtwert von 9 Kartons mit 1x9x1 beträgt 1

`ruby:7.4.renshu.py`


for x in range(9):
    for z in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for y in range (9)]) == 1)

** Einschränkung (4) ** (4) In das 3x3-Quadrat kann nur eine gleiche Zahl eingegeben werden. Der Gesamtwert von 9 Kartons mit 3x3x1 beträgt 1

`ruby:7.4.renshu.py`


#Schleife in Richtung der Z-Achse
for z in range(9):
    #Schleife die x-Koordinate, die von der mittleren Zelle des 3x3-Quadrats genommen wird
    for m1 in [1,4,7]:
        #Schleife die y-Koordinate, die von der mittleren Zelle des 3x3-Quadrats genommen wird
        for m2 in [1,4,7]:
            solver.Add(solver.Sum([dice[x,y,z] for x in [m1 - 1,m1,m1 + 1] for y in [m2 - 1,m2,m2 + 1]]) == 1)

** Einschränkung (5) ** (5) Wenn die Nummer von Anfang an angegeben wurde (Anhang zur Problemstellung), verwenden Sie diese Nummer. Der Gesamtwert einer Box mit 1x1x1 beträgt 1

`ruby:7.4.renshu.py`


for x in range(9):
    for y in range(9):
        if pre[x][y] != 0:
            z = pre[x][y]
            solver.Add(dice[x,y, z - 1] == 1)

Das ist alles für die Einschränkungen. Finde eine Lösung. Diesmal müssen Sie nicht maximieren oder minimieren.

`ruby:7.4.renshu.py`


#Lösungsausführung
status = solver.Solve()

Überprüfen Sie das Ergebnis.

`ruby:7.4.renshu.py`


if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())

    #Erstellen Sie ein Array p für die Anzeige
    p = []
    for x in range(9):
        for y in range(9):
            for z in range(9):
                if dice[x,y,z].solution_value() > 0.5:
                    p.append(z + 1)

    print(np.reshape(p, (9, 9)))                    
    print("Time = ", solver.WallTime(), " milliseconds")
else:
    print('The problem does not have an optimal solution.')

Bei dieser Ausführung wurde die folgende Lösung erhalten.

Solution: ok Objective value = 0.0 [[5 3 6 8 2 7 9 4 1] [1 7 2 9 6 4 3 5 8] [8 9 4 1 5 3 2 6 7] [7 1 5 3 4 9 8 2 6] [6 4 3 7 8 2 1 9 5] [9 2 8 5 1 6 7 3 4] [4 8 1 2 9 5 6 7 3] [3 6 9 4 7 1 5 8 2] [2 5 7 6 3 8 4 1 9]] Time = 477 milliseconds

Die Nummer wurde oben gelöst. Die folgende Abbildung zeigt dies in der Masse. Der rosa Teil ist die Zelle, deren Nummer im Voraus festgelegt wurde, als die Frage gestellt wurde.

Das gesamte Programm wird unten beschrieben.

`ruby:7.4.renshu.py`


from __future__ import print_function
from ortools.linear_solver import pywraplp
import numpy as np

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

pre = [[0,0,6,0,0,0,0,0,1],
       [0,7,0,0,6,0,0,5,0],
       [8,0,0,1,0,3,2,0,0],
       [0,0,5,0,4,0,8,0,0],
       [0,4,0,7,0,2,0,9,0],
       [0,0,8,0,1,0,7,0,0],
       [0,0,1,2,0,5,0,0,3],
       [0,6,0,0,7,0,0,8,0],
       [2,0,0,0,0,0,4,0,0]]


#Variable Definition der Würfelbox
dice = {}
for x in range(9):
    for y in range(9):
        for z in range(9):
            dice[x,y,z] = solver.BoolVar("dice%i%i%i" % (x,y,z))

#Einschränkung 1-Eine Zahl pro Quadrat(1 von 9 Feldern, die 1 enthalten, wenn in z-Richtung geschleift wird)
for x in range(9):
    for y in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for z in range (9)]) == 1)

#Einschränkung 2-Vertikal(y Richtung)Die gleiche Nummer ist eins(y Richtungにループした際に1が入る箱は9個のうち1個)
for x in range(9):
    for z in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for y in range (9)]) == 1)

#Einschränkung 3-Seite(x Richtung)Die gleiche Nummer ist eins(x Richtungにループした際に1が入る箱は9個のうち1個)
for y in range(9):
    for z in range(9):
        solver.Add(solver.Sum([dice[x,y,z] for x in range (9)]) == 1)

#Einschränkung 4-Eine gleiche Zahl im 3x3-Quadrat
#Schleife in Richtung der Z-Achse
for z in range(9):
    #Schleife die x-Koordinate, die von der mittleren Zelle des 3x3-Quadrats genommen wird
    for m1 in [1,4,7]:
        #Schleife die y-Koordinate, die von der mittleren Zelle des 3x3-Quadrats genommen wird
        for m2 in [1,4,7]:
            solver.Add(solver.Sum([dice[x,y,z] for x in [m1 - 1,m1,m1 + 1] for y in [m2 - 1,m2,m2 + 1]]) == 1)

#Einschränkung 5-Das Quadrat mit der Nummer ist diese Nummer
for x in range(9):
    for y in range(9):
        if pre[x][y] != 0:
            z = pre[x][y]
            #print('z=',z)
            solver.Add(dice[x,y, z - 1] == 1)

#Lösungsausführung
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())

    #Erstellen Sie ein Array p für die Anzeige
    p = []
    for x in range(9):
        for y in range(9):
            for z in range(9):
                if dice[x,y,z].solution_value() > 0.5:
                    p.append(z + 1)

    print(np.reshape(p, (9, 9)))                    
    print("Time = ", solver.WallTime(), " milliseconds")
else:
    print('The problem does not have an optimal solution.')

Ausstellungsstück

Dieser Artikel basiert auf den Übungen im Referenztext "Problemlösungsserie mit Python: Erstellen eines Optimierungsmodells mithilfe einer Datenanalysebibliothek" zur mathematischen Optimierung.

■ Referenztext "Problemlösungsserie von Python: So erstellen Sie ein Optimierungsmodell mithilfe einer Datenanalysebibliothek" Tsutomu Saito [Autor] Modern Science Company [Verlagswesen]

Meinungen etc.

Wenn Sie Meinungen oder Korrekturen haben, lassen Sie es uns bitte wissen.

[PYTHON] Lösen Sie mathematische Optimierungsmodellübungen mit den OR-Tools von Google (4) Lösen Sie Zahlenstellen

Einführung

Löse den Zahlenplatz (Nampure)

ruby:7.3.Problem

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

ruby:7.4.renshu.py

Ausstellungsstück

Meinungen etc.

`ruby:7.3.Problem`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`

`ruby:7.4.renshu.py`