Разработка управленческого решения средствами пакета Excel. Степанов А.Г. - 57 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

57
Задача банковского взаимозачета
Задача банковского взаимозачета возникает в том случае, когда из
имеющегося набора n платежных поручений стоимостью c
j
,
(
1
)
jn≤≤
следует отобрать тот набор платежных поручений, который максималь-
но приблизил бы их к сумме взаимозачета V при наличии ограничения
1
.
n
jj
j
сx V
=
≤
∑
Переменные в этом случае принимают только дискретные значения
x
j
∈{0,1}, а целевая функция имеет вид
1
ma
x.
n
jj
j
сx
=
→
∑
Задача представляет особый интерес, когда n достаточно велико.
Так, например, при n = 25 и значениях c
j
={12,07; 15,98; 10,19; 80,79;
46,19; 57,84; 31,08; 41,45; 6,13; 16,46; 47,13; 95,83; 0,46; 65,96; 86,51; 58,11;
40,55; 60,41; 72,52; 51,59; 26,88; 37,24; 26,11; 63,63; 96,62} результат реше-
ния
X
=
{0; 0; 0; 1; 1; 1; 0; 1; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 0; 0; 0; 1; 1}
обеспечивает значение суммы взаимозачета 965,59 при заданной вели-
чине V = 1000.
Задача банковского взаимозачета может рассматриваться как уп-
рощенный вариант открытой задачи о назначениях.
Задача коммивояжера
Имеется n пунктов, связанных между собой дорогами так, что из-
вестны затраты на проезд из одного пункта в другой c
ij
. Требуется най-
ти такой маршрут, чтобы стоимость поездки была бы минимальной.
Задача имеет много аналогий с транспортной задачей и отличается от
нее в первую очередь тем, что искомые переменные принимают только
два возможных значения – 1, если перевозка производится и 0, если нет.
Отметим, что каждый пункт маршрута, кроме исходного, должен быть
посещен только один раз. Введем n
2
переменных
{}
0,
1
ij
x ∈
, удовлетво-
ряющих ограничениям
11
1, 1 , 1, 1
.
nn
ij ij
ij
xjnxi
n
==
=≤≤ =≤≤
∑∑

Страницы