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

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