Do3

Модели на дискретната и целочислената оптимизация.

страницата се нуждае от дописване/преглеждане**

---

Въведение

Дискретната оптимизация най-общо казано е поддял на приложната математика и компютърните науки, който се занимава
с изследването и решаването на оптимизационни проблеми , при които множеството от допустими решения е "дискретно" или може да бъде сведено до такова . Оптимизационните задачи се характеризират с 3 основни компонента - целева функция , на която се търси минимум/максимум , множество от променливи ( някои от които (или всичките) имат ограничение за целочисленост ) и множество от ограничения.

Модели на дискретна оптимизация.

Линейна оптимизация

Отсега нататък винаги когато казваме "програма на линейната оптимизация" ще имаме предвид план за решаването на даден проблем -
терминът "Linear programming" се отнася точно до това - планиране на решения за даден клас оптимизационни задачи ( вж. по-долу определението за ЛП ).
При линейната оптимизация същественото е , че целевата функция е линейна , както и самите ограничения представляват линейни неравенства. По-формално казано - нека ни е даден n- мерен многостен и функция :

$f(x_1 , x_2 , . . . , x_n) = c_1x_1 + c_2x_2 + . . . + c_nx_n + d$

определена върху този многостен. Програма на линейното оптимиране намира точка в този многостен , където функцията приема минимална (максимална стойност) - ако такава съществува. Гарантирано е , че при наличието на такава стойност , то при претърсване измежду върховете на многостена ще намерим поне 1 допустимо решение. В каноничен вид проблема на линейното оптимиране се определя като :

да се намери максимума / минимума на $c^T\chi$
при допълнителното условие $A\chi <= b$

където $\chi$ представлява вектора на променливите ( който трябва да се определи ) , c и b са вектори от дадени коефициенти , А е матрица от дадени коефиценти ( в целевата функция пишем $c^T$ , за да разграничим само , че c е представен като вектор - ред , а $\chi$ - вектор стълб , b - са ни коефициентите от дясната страна на неравенствата , който представляват условията , а А - съответно коефициентите от лявата - вж. стандартната форма по-долу ).

В стандартен вид проблема на линейната оптимизация има вида:

да се намери максимума / минимума на $f(x_1 , x_2 , . . . , x_n) = c_1x_1 + c_2x_2 + . . . + c_nx_n$
при допълнителните условия:

(1)

\begin{cases} a_{11}x_1 + a_{12}x_2 + . . . + a_{1n}x_n <= b_1 \\ a_{21}x_1 + a_{22}x_2 + . . . + a_{2n}x_n <= b_2 \\ . . . . .\\ a_{m1}x_1 + a_{m2}x_2 + . . . + a_{mn}x_n <= b_m \end{cases}

Прехода между предходните две представяния е непосредствен. Може да присъстват допълнителни ограничения като целочисленост на променливите , неотрицателност и т.н. Съществуват две ситуации при , които нямаме решение - ако две или повече от ограниченията си противоречат ( тогава областта от допустими решения е празна ) - например x ≥ 2 и x ≤ 1 или когато многостена е неограничен по посока на целевата функция( например при целева функция $x_1 + 3 x_2$ , на която търсим максимума и ограничения $x_1 \ge 0, x_2 \ge 0, x_1 + x_2 \ge 10$ ). Забележете , че в зависимост от това как е дефиниран проблема във втория случаи , множеството от допустими решения може да е неограничено и пак да имаме оптимално решение.

Целочислена линейна оптимизация.

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