Актуальність задачі цілочисельного ЛП. Математична постановка цілочисельних задач ЛП. Алгоритм Гоморі - Економіко-математичне моделювання

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

Задачу цілочислового програмування записують так : [xі є z, і=1,2,...п]

Для знах. оптим планів застосовують дві основні групи методів:метиди відтинання і комбінаторні методи. Якщо отримане оптимальне рішення цілочисельності, то завдання виконане.

Алгоритм Гоморі - алгоритм, який використовується для рішення повністю цілочисельних завдань лінійного програмування. Алгоритм включає в себе:

    1. Рішення завдання одним з методів групи симплекс-методів або групи методів внутрішньої точки без урахування вимоги целочисленности. Якщо отримане оптимальне рішення цілочисельності, то завдання виконане. 2. Складається додаткове обмеження для перемінної B [i], яка в оптимальному плані має максимальне дробове значення, хоча повинна бути цілою. Тоді величини коефіцієнтів елементів A [i, j] , B [i] обчислюються так:

Де - ціла частина числа A [i, j] . Тоді додаткове обмеження формується таким чином:

Воно буде цілим невід'ємним при цілих невід'ємних в [i, j] і о [j] Після складання обмеження воно вводиться в систему лінійних обмежень і завдання вирішується заново при вихідних обмеженнях і додаткове обмеження. Якщо отримано цілочисельне рішення, задача вирішена. В іншому випадку необхідно повторити другий етап.

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




Актуальність задачі цілочисельного ЛП. Математична постановка цілочисельних задач ЛП. Алгоритм Гоморі - Економіко-математичне моделювання

Предыдущая | Следующая