Автор: Семахин Андрей Михайлович

Рубрика: Информатика

Опубликовано в Молодой учёный №2 (49) февраль 2013 г.

Статья просмотрена: 448 раз

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

Семахин А. М. Оптимальное решение целочисленной модели информационной системы методом ветвей и границ // Молодой ученый. — 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
Задать вопрос