1.5. Задача о ранце

Задача о ранце – задача о наилучшем использовании ограниченного объёма средств. Пусть имеется ряд проектов, характеризующихся эффектом и затратами на реализацию. Предприятие имеет ограниченный объём средств и потому не может реализовать все проекты сразу. Требуется отобрать проекты для реализации так, чтобы суммарный эффект был максимальным, а объем ресурсов не превосходил заданного уровня.

Экономико-математическая модель задачи состоит в определении максимального значения функции:

, (1)

при условиях:

(2)

При этом,

1, если i-й проект принимается к реализации;

х_i= 0, если i-й проект не принимается к реализации.

Д анная задача является задачей целочисленного программирования.

Точное решение задачи можно получить, решая ее методом ветвей и границ.

Сущность метода «ветвей и границ».

При решении методом ветвей и границ обозначаются четко две границы. Первая - максимально возможный эффект. Самый большой эффект достигается от реализации всех проектов. Выше этого значения получить нельзя. Отрицательным эффект не может быть, а следовательно ноль является нижней границей. Алгоритм проще всего представить в графическом виде, как сетевую структуру. Вершина этой сети будет характеризоваться двумя числами, которые записываются в виде дроби. В числителе – суммарный эффект от реализации всех проектов, в знаменателе – объем ограниченных ресурсов. Сеть строится при следующем предположении: если мы движемся вправо и вниз, то это означает, что соответствующий проект принимается к реализации, если влево и вниз, то проект не реализуется. Начальная вершина сети нумеруется: ноль. Если проект принимается к реализации, то из знаменателя дроби вычитают затраты на реализацию этого проекта, числитель остаётся без изменений. Если проект не реализуется, то из числителя вычитают эффект этого проекта. Если мы получаем в знаменателе отрицательное значение, то дальнейшему ветвлению сеть не подлежит. Сравнивая полученные в результате этих преобразований дроби, выбирают такую, которая обладает наибольшим эффектом. Данная ветка и будет содержать оптимальное решение.

Пример решения задачи о ранце методом ветвей и границ.

Предприятие может реализовать 6 проектов. Исходные данные по этим проектам представлены в таблице 1.

Таблица 1.

Проект	Затраты	Эффект	Эффективность	Место
I	6	30	5	3
II	26	65	2,5	6
III	17	79	4,65	4
IV	20	150	7,5	1
V	21	63	3	5
VI	15	100	6,7	2
Всего	105	487	29,35

Предприятие имеет только 60% средств на реализацию от суммарных затрат по всем проектам, то есть b=105×0,6=63.

Эффективность каждого проекта определяем как отношение эффекта к затратам:

d_i=c_i/a_i , i=1,…,n.

Целевая функция имеет вид:

F(x)= 30х₁+65х₂+79х₃+150х₄+63х₅+100х₆→max.

Ограничения задачи:

6х₁+26х₂+17х₃+20х₄+21х₅+15х₆≤63.

Обозначаем границы оптимального решения: верхняя – 487 (суммарный эффект от реализации всех проектов); нижняя – 0 (отрицательным эффект быть не может). Решение задачи о ранце методом ветвей и границ в графическом виде будет представлять собой сетевую структуру: график 1 и график 2. На первом графике представлена сеть при реализации первого проекта, на втором, если первый проект не реализуется.

Вершина нашей сети представлена в виде дроби, в числителе которой суммарный эффект от реализации всех проектов (487), а в - знаменателе объём имеющихся ресурсов (63). Так как объём ресурсов предприятия ограничен и его недостаточно на реализацию всех проектов, то наша задача состоит в том, чтобы отобрать проекты для реализации таким образом, чтобы суммарный эффект был максимальным, объём ресурсов не превосходил заданного значения.

Сравнивая полученные в результате всех преобразований дроби, выбирают такую, которая обладает наибольшим эффектом, то есть значение в числителе дроби максимальное, а знаменатель при этом - неотрицательное число. Исследовав графики, мы выбираем оптимальное решение:

Х={1;0;1;1;0;1},

при котором суммарный эффект будет равен: а затраты на реализацию выбранных проектов:

Задания для выполнения лабораторной работы

Предприятие может реализовать 6 проектов. Исходные данные по этим проектам представлены в таблице. Предприятие имеет только 70% средств на реализацию от суммарных затрат по всем проектам.

Вариант	Направление	Планируемая прибыль	Стоимость проекта
1	I	35	2000
	II	30	1600
	III	32	3200
	IV	27	1200
	V	45	1000
	VI	21	900
2	I	700	590
	II	680	640
	III	640	700
	IV	710	510
	V	810	250
	VI	650	120
3	I	200	300
	II	150	200
	III	400	145
	IV	160	120
	V	840	650
	VI	750	650
4	I	70	1700
	II	50	1800
	III	65	2000
	IV	80	2200
	V	650	450
	VI	350	270
5	I	190	1600
	II	200	1700
	III	170	1800
	IV	180	2000
	V	760	650
	VI	951	753
Вариант	Направление	Планируемая прибыль	Стоимость проекта
6	I	100	100
	II	200	150
	III	800	200
	IV	600	170
	V	700	210
	VI	300	140
7	I	100	250
	II	200	220
	III	500	230
	IV	150	170
	V	820	200
	VI	160	100
8	I	90	100
	II	50	300
	III	40	80
	IV	80	50
	V	100	170
	VI	60	140
9	I	500	220
	II	300	210
	III	200	160
	IV	400	130
	V	170	80
	VI	800	400
10	I	100	120
	II	140	170
	III	180	150
	IV	80	130
	V	210	110
	VI	250	100
11	I	200	200
	II	400	800
	III	700	600
	IV	100	900
	V	500	200
	VI	600	400
Вариант	Направление	Планируемая прибыль	Стоимость проекта
12	I	130	280
	II	210	150
	III	270	130
	IV	80	220
	V	260	200
	VI	240	210
13	I	400	260
	II	350	60
	III	140	170
	IV	360	150
	V	230	330
	VI	180	110
14	I	500	390
	II	210	200
	III	800	250
	IV	380	260
	V	200	270
	VI	400	190
15	I	420	410
	II	340	200
	III	300	420
	IV	120	380
	V	430	480
	VI	360	210
16	I	420	410
	II	340	200
	III	400	420
	IV	120	380
	V	430	480
	VI	140	300
17	I	420	420
	II	340	300
	III	300	320
	IV	120	280
	V	430	450
	VI	800	600
18	I	500	410
	II	400	300
	III	300	450
	IV	200	100
	V	430	380
	VI	380	150
19	I	100	400
	II	330	210
	III	310	410
	IV	130	370
	V	440	470
	VI	140	230
20	I	420	390
	II	340	190
	III	250	380
	IV	140	250
	V	430	450
	VI	500	380
21	I	160	480
	II	240	300
	III	370	510
	IV	290	380
	V	140	250
	VI	260	350
22	I	130	410
	II	150	380
	III	190	260
	IV	230	400
	V	300	800
	VI	260	720
23	I	390	480
	II	100	150
	III	230	340
	IV	300	600
	V	350	710
	VI	120	300
24	I	410	200
	II	240	340
	III	210	730
	IV	150	360
	V	110	200
	VI	120	470
25	I	230	500
	II	310	570
	III	190	300
	IV	400	760
	V	220	470
	VI	390	500