Проблем ранца

Проблем ранца је проблем који је највише истраживан у комбинаторној оптимизацији, са много примена у стварном животу. Због овога је испитано много специјалних случајева и направљено је много генерализација.

Заједничко за све верзије је н предмета, а сваки предмет $1\leq j\leq n$ има придружену вредност п_ј и тежину w_ј. Циљ је сакупити одређени број предмета, тако да вредност ранца буде максимална, али да тежина ранца не пређе задату вредност W. Углавном, ови коефицијенти се скалирају да би били цели бројеви и готово увек се претпоставља да су позитивни.

Проблем ранца у основној форми:

максимално $\sum _{j=1}^{n}p_{j}x_{j}$
предмет	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\}$	$\forall j\in \{1,\ldots ,n\}$

Директне генерализације

Једна од чешћих варијанти је да се сваки предмет може бирати више пута. Конкретно, код проблема ограниченог ранца за сваки предмет ј, и горњу границу у_ј (која може бити позитиван цео број или бесконачно) за број предмета ј може бити изабрано:

максимално $\sum _{j=1}^{n}p_{j}x_{j}$
предмет	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$u_{j}\geq x_{j}\geq 0,x_{j}$ цео број за све ј

Неограничени проблем ранца (који се некада назива и целобројни проблем ранца) не поставља горњу границу за број предмета који могу да се одаберу:

максимално $\sum _{j=1}^{n}p_{j}x_{j}$
предмет	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\geq 0,x_{j}$ цео број за све ј

Луекер је показао 1975. године^[1] да је варијата без границе НП-комплетан проблем. Обе варијатне, и са ограничењем и без ограничења, имају апроскимативну шему полиномијалног времена - ФПТАС (у суштини, као и код 0-1 проблемна ранца).

Ако се предмети поделе на к класа означене са $N_{i}$ , и ако из сваке класе мора да се узме тачно један предмет, добија се проблем ранца са вишетруким избором:

максимално $\sum _{i=1}^{k}\sum _{j\in N_{i}}p_{ij}x_{ij}$
предмет	$\sum _{i=1}^{k}\sum _{j\in N_{i}}w_{ij}x_{ij}\leq W,$
	$\sum _{j\in N_{i}}x_{ij}=1,$	за све $1\leq i\leq k$
	$x_{ij}\in \{0,1\}$	за све $1\leq i\leq k$ и све $j\in N_{i}$

Ако су за све предмете вредност и тежина идентични, добијамо проблем збира подскупа (често је дат одговарајући проблем, проблем одлучивања ):

максимално $\sum _{j=1}^{n}p_{j}x_{j}$
предмет	$\sum _{j=1}^{n}p_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\}$

Ако имамо н предмета и м ранчева са капацитетима $W_{i}$ , добијамо вишеструки проблем ранца:

максимално $\sum _{i=1}^{m}\sum _{j=1}^{n}p_{j}x_{ij}$
предмет	$\sum _{j=1}^{n}w_{j}x_{ij}\leq W_{i},$	за све $1\leq i\leq m$
	$\sum _{i=1}^{m}x_{ij}\leq 1,$	за све $1\leq j\leq n$
	$x_{ij}\in \{0,1\}$	за све $1\leq j\leq n$ и све $1\leq i\leq m$

Као специјалан случај вишетруког проблема ранца, када су вредности једнаке тежинама и сви бинови имају исти капацитет, можемо имати и проблем збира вишетруког подскупа:

Квадратни проблем ранца:

максимално $\sum _{j=1}^{n}p_{j}x_{j}+\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}p_{ij}x_{i}x_{j}$
предмет	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\}$	за све $1\leq j\leq n$

Проблем ранца - Унија скупа:

СУКП (Сет-Унион Кнапсацк Проблем) је дефинисао Келлерер и др.^[2]:

Дат је скуп од $n$ предмета $N=\{1,\ldots ,n\}$ и скуп од $m$ , тако рећи, елемената $P=\{1,\ldots ,m\}$ , где сваки предмет $j$ одговара подскупу $P_{j}$ скупа елемената $P$ . Предмети $j$ имају ненегативне вредности $p_{j}$ , $j=1,\ldots ,n$ , а елементи $i$ ненегативне тежине $w_{i}$ , $i=1,\ldots ,m$ . Коначна тежина скупа предемета је дата коначном тежином елемената уније одговарајућих скупа елемената. Циљ је наћи подскуп предмета са коначном тежином која не прелази капацитет ранца и максималну вредност.

Вишеструко ограничење

Ако постоји више од једног ограничења (на пример, и граница за обим и граница за тежину, где обим и тежина сваког предмета нису повезани), добијамо проблем ранца са вишеструким ограничењем, вишедимензионални проблем ранца, или м-димензионални проблем ранца. (Напомена, "димензија" се овде не односи на облик предмета.) Ово има 0-1, ограничену, и неограничену варијанту; неограничена је приказана испод.

максимално $\sum _{j=1}^{n}p_{j}x_{j}$
предмет	$\sum _{j=1}^{n}w_{ij}x_{j}\leq W_{i},$	за све $1\leq i\leq m$
	$x_{j}\geq 0$ , $x_{j}$ интегер	за све $1\leq j\leq n$

Показано је да је варијанта 0-1 (за све фиксне $m\geq 2$ ) НП-комплентна око 1980. године и да нема ФПТАС осим ако је П=НП.^[3]^[4]

Ограничена и неограничена варијанта (за све фиксне $m\geq 2$ ) имају исту сложеност.^[5]

За било које фиксно $m\geq 2$ , ови проблеми имају псеудо-полиномијални алгоритам (сличан оном за класичн проблем ранца) и ПТАС.^[2]

Ранац-слични проблеми

Ако су све вредности једнаке 1, можемо да покушамо да минимизујемо број предмета који тачно попуњују ранац:

минимално $\sum _{j=1}^{n}x_{j}$
предмет	$\sum _{j=1}^{n}w_{j}x_{j}=W,$
	$x_{j}\in \{0,1\},$	$\forall j\in \{1,\ldots ,n\}$

Ако имамо број складишта (исте величине), и желимо да спакујемо свих н предмета у што је мање могуће складишта, добијамо бин-проблем ранца, који је урађен тако да има индикатор за варијабле $y_{i}=1\Leftrightarrow$ складиште и се тренутно користи:

милимално $\sum _{i=1}^{n}y_{i}$
предмет	$\sum _{j=1}^{n}w_{j}x_{ij}\leq Wy_{i},$	$\forall i\in \{1,\ldots ,n\}$
	$\sum _{i=1}^{n}x_{ij}=1$	$\forall j\in \{1,\ldots ,n\}$
	$y_{i}\in \{0,1\}$	$\forall i\in \{1,\ldots ,n\}$
	$x_{ij}\in \{0,1\}$	$\forall i\in \{1,\ldots ,n\}\wedge \forall j\in \{1,\ldots ,n\}$

Проблем сецкања залиха је идентичан бин-проблему ранца, али пошто парцијалне истанце обично имају много мање типова предмета, често се користи друга формулација. Предмет ј је потребан Б_ј пута, сваки пример премдета који може да стане у само један ранац има променљиву, x_и (постоји м примера), и пример и користи предмет ј б_иј пута:

минимално $\sum _{i=1}^{m}x_{i}$
предмет	$\sum _{i=1}^{m}b_{ij}x_{i}\leq B_{j},$	за све $1\leq j\leq n$
	$x_{i}\in \{0,1,\ldots ,n\}$	за све $1\leq i\leq m$

Ако на вишеструки проблем ранца, додамо ограничење да је сваки подскуп величине н и уклонимо ограничење за коначну тежину, добијамо проблем задатка, који је такође проблем проналажења максималног бипартитивног поклапања:

максимално $\sum _{i=1}^{k}\sum _{j=1}^{n}p_{ij}x_{ij}$
предмет	$\sum _{i=1}^{n}x_{ij}=1,$	за све $1\leq j\leq n$
	$\sum _{j=1}^{n}x_{ij}=1,$	за све $1\leq i\leq n$
	$x_{ij}\in \{0,1\}$	за све $1\leq i\leq k$ и све $j\in N_{i}$

У варијанти ранац максималне густине постоји иницијална тежина $w_{0}$ , и ми увећавамо густину изабраног предемта кои не угрожава капацитет ограничења: ^[6]

максимално ${\frac {\sum _{j=1}^{n}x_{j}p_{j}}{w_{0}+\sum _{j=1}^{n}x_{j}w_{j}}}$
предмет	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\},$	$\forall j\in \{1,\ldots ,n\}$

Иако су мање познади од проблема поменутих изнад, постоји још неколико ранац-сличних проблема, укључујући:

Угнеждени проблем ранца
Колапсирајући проблем ранца
Нелинеаран проблем ранца
Обрнуто-параметарски проблем ранца

Од ових, последња три су обрађена у референцном раду Келлерер-а и других, Кнапсацк Проблемс.^[2]

Референце

^ Луекер, Г.С. (1975). „Репорт Но. 178, Цомпутер Сциенце Лабораторy, Принцетон; Тwо НП-цомплете проблемс ин ноннегативе интегер программинг”.
^ ^а ^б ^в Келлерер, Ханс; Пферсцхy, Улрицх; Писингер, Давид (2004). Кнапсацк Проблемс. Спрингер Верлаг. стр. 423. ИСБН 3-540-40286-1.
^ Генс, Г. V.; Левнер, Е. V. (1979). „Цомплеxитy анд Аппроxиматион Алгоритхмс фор Цомбинаториал Проблемс: А Сурвеy”. Централ Ецономиц анд Матхематицал Институте, Ацадемy оф Сциенцес оф тхе УССР, Мосцоw.
^ Корте, Б.; Сцхрадер, Р. (1980). „Он тхе Еxистенце оф Фаст Аппроxиматион Сцхемес”. Нонлинеар Программинг. Ацадемиц Пресс. 4: 415—437.
^ Магазине, M. Ј.; Цхерн, M.-С.; Магазине, Мицхаел Ј.; Цхерн, Маw-Схенг (1984). „А Ноте он Аппроxиматион Сцхемес фор Мултидименсионал Кнапсацк Проблемс”. Матхематицс оф Оператионс Ресеарцх. 9 (2): 244—247. дои:10.1287/моор.9.2.244.
^ Цохен, Реувен; Катзир, Лиран (2008). „Тхе Генерализед Маxимум Цовераге Проблем”. Информатион Процессинг Леттерс. 108: 15—22. дои:10.1016/ј.ипл.2008.03.017.

Литература

"Алгоритхмс фор Кнапсацк Проблемс", D. Писингер. Пх.D. тхесис, ДИКУ, Университy оф Цопенхаген, Репорт 95/1 (1995).

[1] Луекер, Г.С. (1975). „Репорт Но. 178, Цомпутер Сциенце Лабораторy, Принцетон; Тwо НП-цомплете проблемс ин ноннегативе интегер программинг”.

[KP-KPP-2] а ^б ^в Келлерер, Ханс; Пферсцхy, Улрицх; Писингер, Давид (2004). Кнапсацк Проблемс. Спрингер Верлаг. стр. 423. ИСБН 3-540-40286-1.

[3] Генс, Г. V.; Левнер, Е. V. (1979). „Цомплеxитy анд Аппроxиматион Алгоритхмс фор Цомбинаториал Проблемс: А Сурвеy”. Централ Ецономиц анд Матхематицал Институте, Ацадемy оф Сциенцес оф тхе УССР, Мосцоw.

[4] Корте, Б.; Сцхрадер, Р. (1980). „Он тхе Еxистенце оф Фаст Аппроxиматион Сцхемес”. Нонлинеар Программинг. Ацадемиц Пресс. 4: 415—437.

[5] Магазине, M. Ј.; Цхерн, M.-С.; Магазине, Мицхаел Ј.; Цхерн, Маw-Схенг (1984). „А Ноте он Аппроxиматион Сцхемес фор Мултидименсионал Кнапсацк Проблемс”. Матхематицс оф Оператионс Ресеарцх. 9 (2): 244—247. дои:10.1287/моор.9.2.244.

[6] Цохен, Реувен; Катзир, Лиран (2008). „Тхе Генерализед Маxимум Цовераге Проблем”. Информатион Процессинг Леттерс. 108: 15—22. дои:10.1016/ј.ипл.2008.03.017.

[1]

[2]

[3]

[4]

[5]

[6]