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

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

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

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

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

Семахин А. М. Метод Гомори в решении целочисленной задачи оптимизации информационной системы // Молодой ученый. — 2013. — №1. — С. 38-43.

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





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

Обсуждение

Социальные комментарии Cackle
Задать вопрос