Библиографическое описание:

Семахин А. М. Оптимальное решение целочисленной модели информационной системы методом ветвей и границ // Молодой ученый. — 2013. — №2. — С. 82-85.

Метод ветвей и границ применяется для решения полностью или частично целочисленных задач линейного программирования. Предложен в 1960 г. А Лэндом и Дж. Дойгом [1, c. 411].

В начале итерации метода ветвей и границ необходимо иметь:

  1. Список задач линейного программирования, каждая из которых должна быть решена в последующих итерациях.

  2. Нижнюю границу оптимального значения линейной формы задачи . На первой итерации в качестве берется значение целевой функции в любой целочисленной точке . Если точку указать невозможно, то принимают .

Пусть в результате итераций метода получили список из задач: и существует . Алгоритм метода ветвей и границ содержит этапы:

1 Этап. Выбирается из списка задач линейного программирования задача для решения, . Задача решается.

2 Этап. Если задача имеет решение, то переходим к этапу 3. Иначе, исключаем задачу из списка, =. Переход к этапу 1. При делаем вывод, что исходная задача не имеет решения и процесс заканчивается.

3 Этап. Если , то переходим к этапу 4. В противном случае задача исключается из списка. Переход к этапу 1.

4 Этап. Если все компоненты вектора удовлетворяют условию целочисленности, то переходим к этапу 5. В противном случае задача из списка исключается. План запоминается, . Переход к этапу 1. При вектор является решением исходной задачи и процесс решения заканчивается.

5 Этап Задача из списка исключается. В список включаются две новые задачи линейного программирования — задача и задача , =. Переход к этапу 1. Процесс разбиения задачи на две новые задачи линейного программирования осуществляется следующим образом. Пусть — дробная компонента в полученном оптимальном плане и целая часть. Тогда задача имеет вид:

при ограничениях

(1)

Тогда задача имеет вид:

при ограничениях

(2)

Процесс решения продолжается пока не будут решены все задачи линейного программирования из списка. Решение задачи будет на последней итерации [2, c. 36].

Разработаем целочисленную математическую модель информационной системы и определим оптимальное решение методом ветвей и границ.

Математическая модель формулируется следующим образом: из числа фирм, предоставляющих услуги спутникового Internet на территории Российской Федерации, требуется выбрать провайдера спутникового Internet с максимальной величиной чистого приведенного эффекта (NPV) и удовлетворяющих финансовым ограничениям.

Пусть — доля финансирования проекта “НТВ-Плюс”, — доля финансирования проекта Europe On Line, - доля финансирования проекта Astra Network, - доля финансирования проекта Satpro, - доля финансирования проекта Network Service. - бинарные переменные.

Целочисленная математическая модель имеет вид

при ограничениях (3)

Решим непрерывную задачу. Приведем к стандартной форме и составим исходную Жорданову таблицу (табл. 1).

при ограничениях (4)


Итерация 1. Предварительные условия: 1. Задача 1. 2. Нижняя граница .

Этап 1. Выбираем задачу 1 и решаем ее. Получаем оптимальный план (1,037635, 0, 0.305961, 0, 0), =2,00526.

Этап 2. Задача 1 имеет решение. Переход на 3 этап.

Этап 3. =2,00526>. Переход на 4 этап.

Этап 4. Переменные имеют дробные значения. Переход на 5 этап.

Этап 5. Задача 1 исключается из списка. В список включаются две новые задачи: 2 и 3.

В табл.2 приведено допустимое решение.

В табл.3 приведено оптимальное решение непрерывной задачи.


Таблица 1

Начальная Жорданова таблица

БП

1

-

-

-

-

=

6,5

5,4

3,2

2,931

6,286

5,9

=

3,0

2,006437

1,5

3,000547

3,000575

3,2

=

3,0

0,0

2,5

2,0

0,0

1,6

=

1,5

0,0

0,881832

0,0

0,0

1,186

Z=

0

-1,52727

-0,741239

-1,374394

-0,14511

-0,530312


Таблица 2

Допустимое решение

БП

1

-

-

-

-

-

=

=

0,58484

-0,371563

0,311

1,911498

0,664934

1,007782

=

3,0

0

2,5

2,0

0

1,6

=

1,5

0

0,881832

0

0

1,186

Z=

1,83838

0,282827

0,16381

-0,545426

1,632745

1,138371


Таблица 3

Оптимальное решение непрерывной задачи

БП

1

-

-

-

-

-

=

1,037635

0,290692

0,504283

-0,283954

0,975263

0,806429

=

0,305961

-0,194383

0,1627

0,52315

0,34786

0,527221

=

2,388078

0,388766

2,174601

-1,0463

-0,69572

0,545558

=

1,5

0

0,881832

0

0

1,186

Z=

2,00526

0,176807

0,252551

0,28534

1,822477

1,425931


Задача 2.

при ограничениях (5)

Задача 3.

при ограничениях (6)

Оптимальное решение (1, 0, 0, 0, 0), =1,527270.

Результаты проведенных исследований позволили сделать следующие выводы.

  1. Разработана целочисленная математическая модель оптимизации информационной системы, позволяющая сократить затраты и сроки проектирования информационных систем и повысить обоснованность принимаемых решений.

  2. Найдено оптимальное решение целочисленной задачи оптимизации информационной системы методом ветвей и границ


Литература:

  1. Таха Х. А. Введение в исследование операций. 7-е издание.: Пер. с англ. М.: Издательский дом “Вильямс”, 2005–912 c.

  2. Мастяева И. Н., Горбовцов Г. Я., Семенихина О. Н. Исследование операций ыв экономике: Учебное пособие / Московский государственный университет экономики, статистики и информатики. — М.: МЭСИ, 2003. — 119 с.





Обсуждение

Социальные комментарии Cackle