Strona główna

Programowanie dyskretne


Pobieranie 32.47 Kb.
Data19.06.2016
Rozmiar32.47 Kb.

K.Pieńkosz Badania Operacyjne Programowanie dyskretne

Programowanie dyskretne

Dotyczy problemów decyzyjnych, w których pewne zmienne decyzyjne mogą przyjmować tylko dyskretne wartości np.:



  • całkowitoliczbowe

  • binarne (0 lub 1)

W zależności od rodzaju występujących zmiennych wyróżniamy zadania programowania

  • całkowitoliczbowego

  • binarnego

  • mieszanego – występują zmienne ciągłe i dyskretne


Przykład


Rozwiązanie: x1=4/3, x2=0, z=28/3.

Przy dodatkowym warunku



x1 oraz x2 całkowitoliczbowe

Rozwiązanie: x1=0, x2=1, z=8.

Sytuacje, w których stosuje się zmienne dyskretne

  • natura poszukiwanych rozwiązań jest dyskretna

  • wyznaczanie liczby niepodzielnych obiektów np. procesorów, zadań, pracowników itp.

  • określanie permutacji lub kombinacji pewnego zbioru obiektów – problemy kombinatoryczne

  • wybór decyzji spośród wielu wariantów

  • modelowanie funkcji kawałkami liniowych, np. uwzględnianie kosztów stałych

Metody rozwiązywania problemów dyskretnych

  • algorytmy specjalizowane

  • programowanie sieciowe

  • metody przeglądu

  • metoda podziału i oszacowań (branch & bound)

  • branch & cut, branch & price i inne odmiany

  • programowanie w logice ograniczeń

  • metody odcięć

  • programowanie dynamiczne



  • algorytmy genetyczne (ewolucyjne)

  • przeszukiwanie „tabu search”

  • symulowane wyżarzanie (wychładzanie)

  • algorytmy randomizowane, np. GRASP

Wykorzystywane „narzędzia”

  • solvery Zadań Programowania Mieszanego

  • wymagają zapisania problemu w postaci zadania programowania liniowego z ewentualnymi warunkami całkowitoliczbowości

  • pakiety Programowania w Logice Ograniczeń

  • wymagają zapisania problemu w stosownym języku, zwykle dość „elastycznym”

  • dla uzyskania efektywności potrzebują sformułowania dobrych reguł sterowania procesem przeglądu

  • programy specjalizowane dla danej klasy problemów

  • samodzielna implementacja algorytmów (zaczerpniętych z literatury, opracowanych bądź dostosowanych przez siebie)

Problem P

z(P) = max f(x)

xF(P)

Relaksacja


Problem A

z(A) = max g(x)

xF(A)

jest relaksacją problemu P jeżeli

(i) f(x)  g(x) dla każdego xF(P)

(ii) F(P)  F(A)




Restrykcja


Problem B

v(B) = max h(x)

xF(B)

jest restrykcją problemu P jeżeli

(i) f(x)  h(x) dla każdego xF(B)

(ii) F(P)  F(B)




Metoda podziału i oszacowań

(dla zadania maksymalizacji)




  1. Wybór podproblemu Pi do analizy (na początku P0 =P ).

  2. Oszacowanie optymalnej wartości funkcji celu dla podproblemu Pi

    1. od dołu zi – z rozwiązania dopuszczalnego (dobrego);

    2. od góry – z relaksacji (np. relaksacji liniowej);

  3. Sondaż podproblemu Pi

    1. gdy Pi niedopuszczalny zamykamy jego analizę;

    2. gdy zi = podproblem rozwiązany – zamykamy jego analizę. Jeżeli zi > z0, to znaleźliśmy lepsze rozwiązanie dopuszczalne problemu P, a więc z0:= zi ;

    3. gdy z0 – w podproblemie nie ma lepszych rozwiązań niż dotychczas znalezione (o wartości funkcji celu z0). Zamykamy analizę podproblemu;

    4. gdy > z0, zi < dokonujemy podziału podproblemu Pi na podproblemy Pj (nowe gałęzie drzewa), tak aby



  1. Jeżeli wszystkie podproblemy są zamknięte to STOP. W przeciwnym przypadku idziemy do 1.


Dla zadania minimalizacji analiza oszacowań jest oparta na odwrotnych relacjach.

Przykład











x2  3

x2  2




x1  5

x1  4

x1  3

x1  2

niedopu szczalne








x2  4

x2  3








Kwestie do rozstrzygnięcia

  • rodzaj relaksacji – kompromis między czasem obliczeń a dokładnością

  • strategia wyznaczania dobrych rozwiązań dopuszczalnych

  • sposób podziału na podproblemy – drzewo binarne, wielogałęziowe itd.

  • wybór zmiennej, względem której następuje podział

Przykład – problem plecakowy

Sformułowanie



Które spośród n przedmiotów o wartościach c1, c2,...,cn i ważących odpowiednio a1, a2,...,an należy zapakować do plecaka o ładowności b, aby łączna wartość zapakowanych przedmiotów była jak największa ?

Model Programowania Binarnego





Relaksacja liniowa problemu plecakowego

Właściwości relaksacji liniowej



  • Niech uporządkowanie przedmiotów będzie takie, że

c1/a1 c2/a2  ...  cn/an

Wtedy rozwiązanie



x1=1, x2=1, ..., xp-1=1, xp = ()/ap, xp+1=0, ..., xn=0 gdzie p = min{ j : }

jest optymalnym rozwiązaniem relaksacji liniowej problemu plecakowego



  • Zachłanny algorytm rozwiązywania

Powłoka wypukła

Najmniejszy zbiór wypukły zawierający zbiór rozwiązań dopuszczalny problemu dyskretnego

Właściwości

Relaksacja liniowa problemu ograniczonego do powłoki wypukłej daje rozwiązanie optymalne problemu dyskretnego.

Idea metod odcięć

(kolejne „przybliżanie” powłoki wypukłej)



  1.  rozwiązanie relaksacji liniowej;

  2.  jeżeli rozwiązanie dopuszczalne (całkowitoliczbowe), to STOP. W przeciwnym przypadku idź do 3;

  3.  generacja i dodawanie ograniczenia odcinającego uzyskane rozwiązanie, ale nie naruszające powłoki wypukłej. Idź do 1;


©snauka.pl 2016
wyślij wiadomość