Programowanie całkowitoliczbowe - Matlab


Programowanie całkowitoliczbowe (PLC) jest szczególnym przypadkiem zadania programowanie liniowego. Zawiera dodatkowe założenia dotyczące zmiennych, które powinny przyjmować wartości całkowite. Bardzo istotne znaczenie mają również zadania programowania liniowego binarnego, w którym zmienne mogą przyjmować wartości 0 lub 1.
Zadania programowania całkowitoliczbowego są dużo częściej spotykane w praktyce. Jednak do ich rozwiązania stosuje się techniki programowania liniowego.

Metody rozwiązania PLC:

  1. Naiwne metody rozwiązywania zadania PLC - algorytm pełnego przeglądu:
    Pomijane są warunki całkowitoliczbowości, rozwiązywany jest problem algorytmem simpleks i następnie zaokrąglany wynik. Generowane są wszystkie rozwiązania dopuszczalne i wybierane najlepsze. Algorytmy pełnego przeglądu są więc bardzo nieefektywne.

  2. Algorytm podziału i ograniczeń

  3. Algorytm gałęzi i granic

Zadanie 1 - przykład algorytmu podziału i ograniczeń

Rozwiązać problem:

max z = 8x1 + 5x2
6x1+ 10x2 ≤ 45
9x1 + 5x2 ≤ 45
x1, x2 ≥ 0, x1, x2 całkowite

Etap 1 Relaksacja
Zaczynamy od rozwiązania relaksacji, gdzie relaksacją będziemy nazywać program liniowy, który powstaje po usunięciu warunku całkowitoliczbowości. Do rozwiązanie możemy użyć metody simpleks. Otrzymujemy następujące rozwiązanie:

x1 = 3.75, x2 = 2.25, z = 41.25.

Etap 2 Sprawdzenie rozwiązania - podział problemu
Otrzymane rozwiązanie jest niedopuszczalne ponieważ zmienne są niecałkowite. Wybieramy więc zmienną niecałkowitą która ma większy współczynnik funkcji celu. W naszym przypadku jest to x1. Następnie dokonujemy podziału zmiennej x1. Wartość będzie mniejsza od 3 lub większa od 4. Zadanie dzielimy więc na dwa podproblemy:

Zadanie 1


max z = 8x1 + 5x2
6x1+ 10x2 ≤ 45
9x1 + 5x2 ≤ 45
0 <= x1 <= 3
x1, x2 ≥ 0, x1, x2 całkowite

Zadanie 2


max z = 8x1 + 5x2
6x1+ 10x2 ≤ 45
9x1 + 5x2 ≤ 45
x1 >= 4
x1, x2 ≥ 0, x1, x2 całkowite


Etap 3 Sprawdzenie rozwiązania - podział problemu
Rozwiązania obu podproblemów są niecałkowite. Wybieramy podproblem, dla którego relaksacja daje większe górne oszacowanie. Jest to podproblem 2. Zmienna x2 jest niecałkowita. Dokonujemy więc podziału x2 i tworzymy kolejne dwa podproblemy.

Zadanie 3


max z = 8x1 + 5x2
6x1+ 10x2 ≤ 45
9x1 + 5x2 ≤ 45
0 <= x2 <= 1
x1, x2 ≥ 0, x1, x2 całkowite

Zadanie 4


max z = 8x1 + 5x2
6x1+ 10x2 ≤ 45
9x1 + 5x2 ≤ 45
x2 >= 2
x1, x2 ≥ 0, x1, x2 całkowite

Etap 4 Sprawdzenie rozwiązania - podział problemu
Podproblem 4 jest sprzeczny - odpowiadający mu wierzchołek zamykamy. Wybieramy otwarty podproblem z największym górnym oszacowaniem, czyli podproblem 3. Zmienna x1 jest niecałkowita dlatego dokonujemy jej podziału i tworzymy podproblemy 5 i 6.

Zadanie 5


max z = 8x1 + 5x2
6x1+ 10x2 ≤ 45
9x1 + 5x2 ≤ 45
0 <= x1 <= 4
x1, x2 ≥ 0, x1, x2 całkowite

Zadanie 6


max z = 8x1 + 5x2
6x1+ 10x2 ≤ 45
9x1 + 5x2 ≤ 45
x1 >= 5
x1, x2 ≥ 0, x1, x2 całkowite

Rozwiązując oba podproblemy otrzymujemy optymalne rozwiązania całkowite. W tym momencie wiemy, że dopuszczalne rozwiązanie to x1 = 5, x2 = 0 i wartości funkcji celu równej 40. Zamykamy oba wierzchołki. Musimy jeszcze zbadać otwarty podproblem 1. Ponieważ górne ograniczenie w tym podproblemie jest równe 37.5 to podproblem 1 nie może zawierać rozwiązania lepszego niż podproblem 6. Wierzchołek z podproblemem 1 zamykamy. Wszystkie wierzchołki są zamknięte i optymalne rozwiązanie znajduje się w podproblemie 6.

Zadanie 2 - przykład algorytmu podziału i ograniczeń

Rozwiązać problem:

max z = x1 + x2
x1+ 2x2 ≤ 32
18x1 + x2 ≤ 224
x1, x2 ≥ 0, x1, x2 całkowite

Odpowiedź:

Zadanie 3 - przykład algorytmu gałęzi i granic

Funkcja bintprog w Matlabie wykorzystuje metodę gałęzi i granic do rozwiązywania zadań programowania całkowitoliczbowego binarnego. W nowych wersjach Matlaba (>2014) funkcja została zastąpiona funkcją intlinprog.

Ogólna forma funkcji:

[x,fval,exiflag,output,lambda] = bintprog(f, A, b, Aeq, beq, x0, options)

Argumenty wejściowe:

f wektor kolumnowy stałych współczynników funkcji celu
A macierz ograniczeń liniowych nierównościowych
b kolumnowy wektor współczynników ograniczeń liniowych nierównościowych
Aeq macierz ograniczeń liniowych równościowych
beq kolumnowy wektor współczynników ograniczeń liniowych równościowych
x0 punkt startowy poszukiwań
options struktura opcji w algorytmie wyszukiwania

Argumenty wyjściowe:

x wektor zmiennych
fval wartość funkcji celu w punkcie minimum
exitflag informacja obliczeniowa
output informacja o rezultatach optymalizacji
lambda wartości współczynników Lagrange'a w punkcie optymalnym

Rozwiąż następujące zadanie:
Należy minimalizować funkcję:

f(x) = 8x1 + x2
przy obecności ograniczeń:
x1 + 2x2 >= -14
-4x1 - x2 <= -33
2x1 + x2 <= 20
gdzie x1, x2 >= 0,
x2 jest liczbą całkowitą

Odpowiedź: x1 = 6.5, x2 = 7

Zadanie 4 - przykład algorytmu gałęzi i granic

Rozwiąż następujące zagadnienie:

f(x) = -3x1 - 2x2 - x3
przy obecności ograniczeń:
x1 + x2 + x3 ≤ 7
4x1 + 2x2 + x3 = 12
gdzie x1, x2 >= 0,
x3 jest liczbą binarną

Odpowiedź: x1 = 0, x2 = 5.5, x3 = 1, z = 12

Wyświetlanie powierzchni Matlab - jedno z rozwiązań

% Wykres powierzchni (na podstawie zad.1)
x = 0:3; % zakres 
y1 = max((45 - 6*x)/10, 0); % równanie nr.1
y2 = max((45 - 9*x)/5, 0); % równanie nr.2
ytop = min([y1; y2]); % macierz wartości min.
area(x,ytop); 
hold on;