Целочислено програмиране

Целочислено програмиране (ЦП; англ. integer programming, IP) — това е раздел на математическата оптимизация, в който се изследват задачи, при които някои или всички променливи трябва да приемат само целочислени стойности.

Най-добре изученият частен случай е целочисленото линейно програмиране (ЦЛП; англ. integer linear programming, ILP), при което целевата функция и ограниченията са линейни. За разлика от линейното програмиране, където променливите могат да приемат произволни реални стойности, изискването за целочисленост прави задачите на ЦП значително по-сложни за решаване.

Целочисленото програмиране намира широко приложение в икономиката, логистиката, производственото планиране и други области, където променливите по своята природа са дискретни (например брой произведени единици продукция или брой работници).

Определение и терминология

Общата задача на целочисленото линейно програмиране може да бъде записана по следния начин:

Намери вектор $x$, който:

максимизира (или минимизира) $c^{T}x$

при условия:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (всички компоненти на вектора $x$ са цели числа)

където $x$ — вектор от променливи, $c$ и $b$ — вектори, а $A$ — матрица от коефициенти.

В зависимост от изискванията към променливите се разграничават следните типове задачи:

• Изцяло целочислено програмиране: всички променливи трябва да бъдат цели.
• Смесено целочислено програмиране (англ. mixed-integer programming, MIP): само част от променливите трябва да бъдат целочислени.
• Булево (0-1) програмиране: променливите приемат само стойности 0 или 1, което позволява моделиране на логически решения от типа „да/не".

Ключови свойства и сложност

Изчислителна сложност

Задачата на целочисленото линейно програмиране в общия случай е NP-трудна. Това означава, че не съществува известен алгоритъм, способен да намери точно оптимално решение за произволна задача на ЦП за полиномиално време. Сложността се дължи на комбинаторния характер на задачата, тъй като броят на възможните целочислени решения може да нараства експоненциално с увеличаването на броя на променливите.

Връзка с линейното програмиране (ЛП-релаксация)

За всяка задача на ЦП може да се формулира нейната линейна релаксация — задача за линейно програмиране (ЛП), в която изискването за целочисленост на променливите е отпаднало. Решението на ЛП-релаксацията има две важни свойства:

1. То може да бъде намерено значително по-бързо (за полиномиално време).
2. Оптималната стойност на целевата функция на ЛП-релаксацията дава оценка (горна граница за задача за максимизация и долна за минимизация) за оптималната стойност на изходната целочислена задача.

Впрочем простото закръгляване на дробното решение на ЛП-релаксацията до най-близките цели числа, като правило, не води до оптимално или дори допустимо решение на целочислената задача.

Свойство на пълна унимодулярност

Съществува важен клас задачи на ЦЛП, които се решават толкова лесно, колкото и техните ЛП-релаксации. Това са задачи, при които матрицата на ограниченията $A$ е напълно унимодулярна (т.е. определителят на всяка нейна квадратна подматрица е равен на 0, +1 или −1). Ако матрицата $A$ е напълно унимодулярна, а векторът $b$ е целочислен, то всички върхове на многостена от допустими решения на ЛП-релаксацията автоматично ще бъдат целочислени. Следователно решението, намерено чрез симплекс-метода, ще бъде целочислено. Примери за такива задачи са транспортната задача и задачата за назначенията.

Методи за решаване

За решаване на общи задачи на ЦП, които не притежават свойството на пълна унимодулярност, са разработени точни методи, основани на идеите за неявно изброяване.

• Метод на разклоненията и границите (англ. Branch and Bound) — основен точен метод, основан на систематичното разбиване на множеството от допустими решения на подмножества (разклоняване) и отрязване на онези подмножества, които очевидно не съдържат оптимално решение. За оценка на перспективността на подмножествата се използва ЛП-релаксация.

• Метод на отсичащите равнини (метод на Гомори; англ. Cutting Plane Method) — итеративен подход, който последователно добавя към задачата нови линейни ограничения („отсичания"). Тези отсичания „отрязват" дробните решения на ЛП-релаксацията, без да засягат нито едно допустимо целочислено решение, като постепенно приближават областта на допустимите решения на ЛП-релаксацията към изпъкналата обвивка на целочислените решения.

Съвременните решатели, като правило, използват хибридни алгоритми, като например методът на разклоненията и отсичанията (англ. Branch and Cut), който съчетава предимствата на двата подхода.

Примери и области на приложение

Целочисленото програмиране позволява моделирането на множество класически задачи на комбинаторната оптимизация.

• Задачата за раницата: класическа задача за 0-1 програмиране, при която трябва да се избере набор от предмети с максимална обща стойност, без да се надвишава ограничението за общо тегло.
• Задачата на търговския пътник: задача за намиране на най-краткия маршрут, минаващ през зададен набор от градове. Може да бъде формулирана като задача за целочислено програмиране, при която променливите отговарят за включването на ребрата на графа в крайния маршрут.

Благодарение на своята гъвкавост, ЦП е един от най-търсените инструменти в изследването на операциите и намира приложение в такива области като:

• Логистика и управление на веригите за доставки: оптимизация на транспортните маршрути, разполагане на складове, управление на запасите.
• Производствено планиране: съставяне на производствени графици, разпределение на ресурси, натоварване на оборудването.
• Финанси и икономика: формиране на инвестиционен портфейл, бюджетиране на капиталовложения.
• Телекомуникации и енергетика: проектиране на комуникационни мрежи, планиране на работата на енергийни блокове.

Вижте също

• Линейно програмиране
• Метод на разклоненията и границите