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

Автор:

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

Опубликовано в Молодой учёный №1 (48) январь 2013 г.

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

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

Семахин А. М. Метод Гомори в решении целочисленной задачи оптимизации информационной системы // Молодой ученый. — 2013. — №1. — С. 38-43. — URL https://moluch.ru/archive/48/5986/ (дата обращения: 17.12.2018).

Целочисленное линейное программирование ориентировано на решение задач линейного программирования, в которых все или некоторые переменные принимают целочисленные значения [1, c. 136].

Для решения целочисленной задачи линейного программирования Р. Гомори предложил метод отсечения плоскостей в 1958 г. [1, c. 143].

Алгоритм Гомори содержит этапы:

Этап 1. Решение непрерывной задачи. Если решение дробное переход на 2 этап.

Этап 2. Решение расширенной задачи [2, c. 410].

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

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

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

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

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

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

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

(2)

Таблица 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 приведена первая итерация.

Таблица 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 приведено оптимальное решение непрерывной задачи.

Переход ко второму этапу алгоритма Гомори.

Выбирается базисная переменная с наибольшей дробной частью: , , . Для переменной составляется уравнение.

В табл. 4 и табл. 5 представлены расширенная задача и 3 итерация.

Таблица 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


Таблица 4

Расширенная задача с первым дополнительным ограничением

БП

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

=

-0,305961

0,194383

-0,1627

-0,52315

-0,34786

-0,527221

Z=

2,00526

0,176807

0,252551

0,28534

1,822477

1,425931


Таблица 5

Третья итерация

БП

1

-

-

-

-

-

=

0,569642

0,588017

0,25542

-1,084156

0,443182

1,529584

=

0

0

0

0

0

1

=

2,071475

0,58991

2,006242

-1,587645

-1,055679

1,034781

=

0,811731

0,437271

0,515833

-1,176842

-0,782522

2,249531

=

0580328

-0,368694

0,308599

0,992278

0,659799

-1,896738

Z=

1,177753

0,702539

-0,18749

-1,129581

0,881649

2,704617


В табл.6 приведено оптимальное нецелочисленное решение.

В табл.7 представлена расширенная задача со вторым дополнительным ограничением.

Таблица 6

Оптимальное нецелочисленное решение

БП

1

-

-

-

-

-

=

1,203704

0,185185

0,592593

1,09259

1,164074

-0,542779

=

0

0

0

0

0

1

=

3

0

2,5

1,6

0

-2

=

1,5

0

0,881832

1,186

0

0

=

0,584844

-0,371563

0,311001

1,007782

0,664934

-1,911499

Z=

1,838386

0,282829

0,16381

1,13837

1,632745

0,545424


Таблица 7

Расширенная задача со вторым дополнительным ограничением

БП

1

-

-

-

-

-

=

1,203704

0,185185

0,592593

1,09259

1,164074

-0,542779

=

0

0

0

0

0

1

=

3

0

2,5

1,6

0

-2

=

1,5

0

0,881832

1,186

0

0

=

0,584844

-0,371563

0,311001

1,007782

0,664934

-1,911499

=

-0,203704

-0,185185

-0,592593

-0,09259

-0,164074

0,542779

Z=

1,838386

0,282829

0,16381

1,13837

1,632745

0,545424


В табл.8 приведена четвертая итерация. В табл.9 и табл.10 представлены расширенная задача и оптимальное целочисленное решение. Оптимальный целочисленный план = (табл. 10). Значение целевой функции Z=1.52728.

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

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

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

Таблица 8

Четвертая итерация. Отсечение дробной части переменной

БП

1

-

-

-

-

-

=

1

0

1

1

1

0

=

0

0

0

0

0

1

=

2,14062

-0,781249

4,21875

1,20939

-0,692187

0,289847

=

1,19687

-0,275572

1,48809

1,04822

-0,244157

0,807704

=

0,477937

-0,468751

0,524814

0,959189

0,578826

-1,62664

=

0,34375

0,312499

-1,6875

0,156246

0,276875

-0,915939

Z=

1,78208

0,231638

0,276429

1,11278

1,58739

0,695464


Таблица 9

Расширенная задача с третьим дополнительным ограничением

БП

1

-

-

-

-

-

=

1

0

1

1

1

0

=

0

0

0

0

0

1

=

2,14062

-0,781249

4,21875

1,20939

-0,692187

0,289847

=

1,19687

-0,275572

1,48809

1,04822

-0,244157

0,807704

=

0,477937

-0,468751

0,524814

0,959189

0,578826

-1,62664

=

0,34375

0,312499

-1,6875

0,156246

0,276875

-0,915939

=

-0,34375

-0,312499

0,68785

-0,156246

-0,276875

0,915939

Z=

1,78208

0,231638

0,276429

1,11278

1,58739

0,695464


Таблица 10

Оптимальное целочисленное решение

БП

1

-

-

-

-

-

=

1

0

1

1

1

0

=

0

0

0

0

0

1

=

3

-2,5

2,5

1,60001

0

-2

=

1,5

-0,881833

0,88183

1,186

0

0

=

0,993565

-1,50001

-0,506442

1,19356

0,994141

-3,00056

=

0

1

-1

0

0

0

=

1,1

-3,20001

-2,20001

0,499989

0,886003

-2,93101

Z=

1,52727

0,741244

0,786034

0,996964

1,38216

1,3744


Литература:

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

  2. Конюховский П. В. Математические методы исследования операций в экономике. — СПб.: Издательство «Питер», 2000. — 208 с.

  3. Семахин А. М. Анализ математической модели информационной системы. В сб. материалов X Всероссийской научно-практической конференции с международным участием (25–26 ноября 2011 г.). — Томск: Изд-во Том.ун-та, 2011. — Ч.2–206 с.





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


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

Оптимальное решение целочисленной модели...

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

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

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

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

Целочисленные модели в строительстве | Статья в журнале...

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

Поэтому используются приближенные методы; методы отсечения (вводятся дополнительные ограничения, «отсекающие» нецелочисленный план); метод...

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

Метод решения рассматриваемых ниже задач связан с именем российского Лауреата Нобелевской премии по экономике Л. В. Канторовича (за вклад в теорию оптимального распределения ресурсов; 1975 г.; взгляд на математику как на единую дисциплину...

Декомпозиционный метод решения транспортной задачи...

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

Некоторые прикладные задачи целочисленного программирования

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

Формирование оптимальной сети структурных подразделений...

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

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

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

Обсуждение

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

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

Оптимальное решение целочисленной модели...

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

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

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

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

Целочисленные модели в строительстве | Статья в журнале...

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

Поэтому используются приближенные методы; методы отсечения (вводятся дополнительные ограничения, «отсекающие» нецелочисленный план); метод...

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

Метод решения рассматриваемых ниже задач связан с именем российского Лауреата Нобелевской премии по экономике Л. В. Канторовича (за вклад в теорию оптимального распределения ресурсов; 1975 г.; взгляд на математику как на единую дисциплину...

Декомпозиционный метод решения транспортной задачи...

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

Некоторые прикладные задачи целочисленного программирования

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

Формирование оптимальной сети структурных подразделений...

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

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

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

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