Оптимальное решение целочисленной модели информационной системы методом ветвей и границ | Статья в журнале «Молодой ученый»

Автор:

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

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

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

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

Семахин А. М. Оптимальное решение целочисленной модели информационной системы методом ветвей и границ // Молодой ученый. — 2013. — №2. — С. 82-85. — URL https://moluch.ru/archive/49/6153/ (дата обращения: 20.10.2018).

Метод ветвей и границ применяется для решения полностью или частично целочисленных задач линейного программирования. Предложен в 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 с.





Основные термины (генерируются автоматически): задача, этап, линейное программирование, оптимальное решение, доля финансирования проекта, информационная система, непрерывная задача, целочисленная математическая модель, метод ветвей, список.


Похожие статьи

Метод Гомори в решении целочисленной задачи оптимизации...

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

Целочисленное решение задач линейного программирования...

При решении задач частично-целочисленного линейного программирования методом ветвей и границ на определенных этапах решаются вспомогательные задачи линейного программирования (ЛП), для которых применяется симплекс-метод.

Приложения линейного программирования к решению...

Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel. К решению краевых задач пространственных стержней при переменных упруго-пластических нагружениях.

Применение метода линейного программирования для...

Цель настоящей статьи — показать использование метода линейного программирования при решении текстовых задач по математике, предполагающих максимизацию (минимизацию) некоторой величины, например...

Решение интервальной задачи дробно-линейного...

В настоящее время широко разработаны вопросы традиционной оптимизации систем с детерминированными параметрами [1,2]. С математической точки зрения такая оптимизация есть отыскание экстремумов функции, параметры которых детерминированные...

Решение многокритериальных задач линейного...

Рис. 1. Оптимальное решение задачи.

многокритериальная оптимизация, задача линейного программирования, метод последовательных уступок.

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

Предельная эффективность и параметрический анализ в задачах...

Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel. Приложения линейного программирования к решению архитектурно-строительных задач.

Организация решения задач динамического программирования

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

Линейное программирование | Статья в журнале «Молодой...»

В данной статье рассматривается задача линейного программирования и возможный способ её решения — симплекс метод. Приведены примеры, поясняющие, что такое линейное программирование и симплекс метод.

Обсуждение

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

Похожие статьи

Метод Гомори в решении целочисленной задачи оптимизации...

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

Целочисленное решение задач линейного программирования...

При решении задач частично-целочисленного линейного программирования методом ветвей и границ на определенных этапах решаются вспомогательные задачи линейного программирования (ЛП), для которых применяется симплекс-метод.

Приложения линейного программирования к решению...

Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel. К решению краевых задач пространственных стержней при переменных упруго-пластических нагружениях.

Применение метода линейного программирования для...

Цель настоящей статьи — показать использование метода линейного программирования при решении текстовых задач по математике, предполагающих максимизацию (минимизацию) некоторой величины, например...

Решение интервальной задачи дробно-линейного...

В настоящее время широко разработаны вопросы традиционной оптимизации систем с детерминированными параметрами [1,2]. С математической точки зрения такая оптимизация есть отыскание экстремумов функции, параметры которых детерминированные...

Решение многокритериальных задач линейного...

Рис. 1. Оптимальное решение задачи.

многокритериальная оптимизация, задача линейного программирования, метод последовательных уступок.

Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.

Предельная эффективность и параметрический анализ в задачах...

Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel. Приложения линейного программирования к решению архитектурно-строительных задач.

Организация решения задач динамического программирования

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

Линейное программирование | Статья в журнале «Молодой...»

В данной статье рассматривается задача линейного программирования и возможный способ её решения — симплекс метод. Приведены примеры, поясняющие, что такое линейное программирование и симплекс метод.

Задать вопрос