Podręcznik
Wersja podręcznika: 1.0
Data publikacji: 01.01.2022 r.
Wykłady
W1…WN, odpowiadające w sumie ok. 10-12 godz. standardowego wykładu
3. Techniki restrykcyjne i relaksacyjne
3.2. Restrykcja - dekompozycja Bendersa
W tym rozdziale pokażemy możliwości wykorzystania dekomponowalnej struktury zadania lokalizacji, stosując zamiast relaksacji techniki restrykcji. Restrykcja to technika polegająca na dodatkowym ograniczaniu zbioru dopuszczalnego problemu optymalizacji. W omawianej we wcześniejszych rozdziałach metodzie podziału i oszacowań restrykcja była wykorzystywana do wydzielania części obszaru dopuszczalnego poprzez narzucenie ograniczeń typu nierównościowego na zmienne. W metodzie opracowanej przez Bendersa w 1962r. restrykcja polega na narzuceniu konkretnych wartości wybranym zmiennym całkowitoliczbowym, podczas gdy pozostałe zmienne są optymalizowane. Metoda Bendersa ma zatem zastosowanie do rozwiązywania tylko pewnych klas problemów optymalizacji, dla których w możliwy jest rozdział zmiennych, w szczególności prowadzący do wyodrębnienia zadania programowania liniowego oraz zadania programowania dyskretnego, które jest łatwiejsze do rozwiązywania od pierwotnego problemu dyskretno-ciągłego.
Przypomnijmy, ze w zadaniu lokalizacji rozważanym w poprzednim podrozdziale poświęconym relaksacji Lagrange'a problem pierwotny polega na określeniu, w których miastach otworzyć magazyny (zmienna binarna ) oraz w jakich proporcjach zaspokoić zapotrzebowanie klientów w miastach
zaopatrywanych przez magazyny
(zmienna ciągła z zakresu
). Dla uproszczenia, analizujemy łatwieszą wersję problemu, w którym pomijamy ograniczone pojemności magazynów.
Sformułowanie matematyczne problemu pierwotnego P:
Zdefiniujmy teraz problem operujący tylko na zmiennych ciągłych , w którym
jest traktowane jako parametr - zostało poddane restrykcji. Przyjmując, że wartości wektora
są ustalone, restrykcja
zadania (P) jest podproblemem sparametryzowanym przez y. W takiej sytuacji
jest zadaniem liniowym względem zmiennej x o następującej postaci:
W powyższym sformułowaniu oznaczyliśmy też zmienne dualne do ograniczeń (4) i (5), które będą wykorzystane w dalszej analizie metody Bendersa. Przypomnijmy, że sformułowanie dualne można rozważać tylko dla problemów ze zmiennymi ciągłymi - a taki właśnie jest problem . Zauważmy przy okazji, że problem
może być zdekomponowany na
niezależnych podproblemów optymalizacji, podobnie niezależnie można określać odpowiednie zmienne dualne . Podproblem
:
W metodzie dekompozycji Bendersa kolejnym elementem schematu postępowania jest sformułowanie dualne zadania określane jako problem D1
. Skorzystamy z możliwości dekompozycji zadania
na podproblemy i dla ułatwienia rozważań sformułujemy podproblem
:
Zmienna dualna w zadaniu
jest nieograniczonego znaku, przy czym musi być zawsze niezerowa, tj. musi być zmienną bazową (każde miasto musi być zaopatrzone). Ze względu na maksymalizację, oraz ograniczenie (10)
będzie przybierać najniższą z wartości
, dla których
. Natomiast w pozostałych przypadkach, z tego względu że w bazie nie może być dodatkowych zmiennych
(lub zmiennych dopełniających) szczególna postać tego zadania pozwala wyznaczyć rozwiązania zmiennych dualnych jako:
Stąd:
Najważniejszą cechą zadania dualnego w metodzie Bendersa jest to, że jego zbiór rozwiązań dopuszczalnych nie zależy od wyboru . Dzieje się tak, ponieważ ustalony
jest pomijany w funkcji celu zadania pierwotnego, a jak pamiętamy, w ograniczeniach zadania dualnego wykorzystywane są jedynie współczynniki funkcji celu zadania prymalnego. Niezależność zbioru dopuszczalnego
od wektora
pozwala na rozważanie wyłącznie punktów wierzchołkowych tego zbioru, gdyż to w jednym z nich znajduje się optimum, którego wartość zależy od
. To pozwala przekształcić problem P do równoważnego zadania D2. W rozważanym tu problemie lokalizacji jest on następującej postaci. Problem
:
Bezpośrednie rozwiązywanie zadania D2 jest na ogół niepraktyczne, gdyż wymaga wyznaczenia wszystkich punktów wierzchołkowych zbioru dualnego, co może być szczególnie kłopotliwe w przypadku dużej liczby wierzchołków. Dlatego Benders opracował iteracyjną procedurę, która pozwala na wyznaczenie optymalnego wierzchołka zbioru dualnego zazwyczaj w niewielkiej liczbie iteracji.
Formalna konstrukcja algorytmu Bendersa:
- Krok 0. Wyznacz wartość wektora zmiennych dualnych
jako dowolne rozwiązanie dopuszczalne problemu dualnego
- uwaga, nie musi to być punkt wierzchołkowy zbioru dopuszczalnego. Jeżeli rozwiązanie dopuszczalne nie istnieje, to STOP. W p. p. przyjmij
i idź do kroku 1.
- Krok 1. Rozwiąż zadanie zrelaksowane
, tzn. zadanie D2, w którym występuje jedynie
ograniczeń. W wyniku rozwiązaniu zrelaksowanego zadania uzyskujemy optymalną wartość wektora
, i wartość funkcji celu będącą wartością oszacowania górnego
.
- Krok 2. Rozwiąż zadanie restrykcyjne
podstawiając
. W wyniku rozwiązania restrykcji zadania uzyskujemy optymalną wartość wektora zmiennych dualnych
. Na jego podstawie oraz wartości
można obliczyć oszacowanie dolne
w
-tej iteracji.
- Krok 3. Jeżeli
to
jest rozwiązaniem optymalnym problemu (P), idź do kroku 4 w celu wyznaczeniu optymalnej wartości x. W p.p. podstaw
i idź do kroku 1.
- Krok 4. Rozwiąż problem
przyjmując
. STOP.


Uwaga. Dekompozycja Bendersa może być szczególnie efektywna w przypadku, gdy struktura macierzy ograniczeń jest blokowo-diagonalna z wstęgą pionową, jak pokazano na poniższym rysunku.

Innym przykładem możliwości zastosowania metody dekompozycji Bendersa jest sytuacja, gdy funkcje powiązane ze zmienną
