Цілочислове програмування
Постановка задачі

Існує доволі широкий клас задач математичного програмування, в економіко – математичних моделях яких одна або кілька змінних мають набувати цілих значень, наприклад, коли йдеться про кількість верстатів у цеху, тобто коли така вимога випливає з особливостей технології виробництва. До цілочислового програмування належать також задачі оптимізації, в яких змінні набувають лише двох значень – 0 або 1 (бульові, або бінарні, змінні).

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

Задача цілочислового програмування записується так :

, (1)

Для знаходження оптимального розв'язку цілочислових задач застосовують спеціальні методи. Найпростішим методом розв'язування цілочислової задачі є знаходження її оптимального роз в'язку як задачі, що має лише неперервні змінні, з подальші округленням останніх. Такий підхід часто є виправданим.

Для знаходження оптимальних планів задач цілочислової програмування застосовують дві основні групи методів:

— методи відтинання;

— комбінаторні методи.

Основою методів відтинання є ідея поступового «звуження» області допустимих розв'язків розглядуваної задачі. Пошук ціло­числового оптимуму починається з розв'язування задачі з так званими послабленими обмеженнями, тобто без урахування ви­мог цілочисловості змінних. Далі введенням у модель спеціаль­них додаткових обмежень, що враховують цілочисловість змінних, многокутник допустимих розв'язків послабленої задачі поступово зменшуємо доти, доки змінні оптимального розв'язку не набу­дуть цілочислових значень. До цієї групи належать:

Ø методи розв'язування повністю цілочислових задач (дробовий
алгоритм Гоморі);

Ø методи розв'язування частково цілочислових задач (другий
алгоритм Гоморі, або змішаний алгоритм цілочислового програ­
мування).

Комбінаторні методи цілочислової оптимізації базуються на пов­ному переборі всіх допустимих цілочислових розв'язків, тобто вони реалізують процедуру цілеспрямованого перебору, під час якої розглядається лише частина розв'язків (досить невелика), а решта враховується одним зі спеціальних методів.

Найпоширенішим у цій групі методів є метод віток і меж.

Починаючи з розв'язування послабленої задачі, він передба­чає розбиття початкової задачі на дві підзадачі виключенням об­ластей, що не мають цілочислових розв'язків, і дослідженням кожної окремої частини многокутника допустимих розв'язків.

Для розв'язування задач із бульовими змінними застосовують комбіновані методи, причому оскільки змінні є бульовими, то методи пошуку оптимуму значно спрощуються.

Метод Гоморі

Нехай маємо задачу цілочислового програмування (1) – (4). Для її розв'язування можна скористатися ітеративним методом Гоморі. Суть його полягає ось у чому:

1.Знаходять розв'язок послабленої, тобто задачі без вимог ці-
лочисловості змінних — (1) - (3).

Якщо серед елементів умовно-оптимального плану немає дробових чисел, то цей план є оптимальним планом задачі цілочислового програмування (1) - (4).

2.Коли в умовно-оптимальному плані є дробові значення, то
вибирається змінна, яка має найбільшу дробову частину. На базі
цієї змінної (елементів відповідного рядка останньої симплексної

таблиці, в якому вона міститься) будується додаткове обмеження Гоморі:

де символ {} позначає дробову частину числа.

Для визначення дробової частини будь-якого числа від цього числа віднімають цілу його частину — найбільше ціле число, що неперевищує даного Цілу частину числа позначають символом [] .

Наприклад :

[1,3] = 1; [-1,3] =-2;

{1,3} = 1,3 - 1 = 03; {-1,3} = -1,3 - (-2) =2 - 1,3 = 0,7.

3. Додаткове обмеження після зведення його до канонічного вигляду і введення базисного елемента приєднується до остан­ньої симплексної таблиці, яка містить умовно-оптимальний план. Здобуту розширену задачу розв'язують, а далі перевіряють її розв'язок на цілочисювість. Якщо він не цілочисловий, то про­цедуру повторюють повертаючись до пункту 2.

Так діють доти, доки не буде знайдено цілочислового розв'язку або доведено, що зада­ча не має допустимих розв'язків у множині цілих чисел.

Досвід показує, що процес розв'язування задач великої розмір­ності методом Гоморі повільно збіжний. Істотними є також по­хибки округлення, які можуть призвести до того, що отриманий цілочисловий план не буде оптимальним .
Случайные рефераты:
Реферати - Життєвий шлях Т.Г. Шевченка
Реферати - Життя та творчість Івана Нечуя-Левицького
Реферати - Життя і творчість Тодося Осьмачки
Реферати - Епічність прози Сави Божка
Реферати - Життя і творчий шлях Миколи Івановича Костомарова
Реферати - Новаторство в поезії Павла Тичини
Реферати
  • Всі реферати
  • Архітектура
  • Астрономія, авіація
  • Аудит
  • Банківська справа
  • Безпека життєдіяльності
  • Біографія, автобіографія
  • Біологія
  • Бухгалтерський облік
  • Військова кафедра
  • Географія
  • Геологія
  • Гроші і кредит
  • Державне регулювання
  • Діловодство
  • Екологія
  • Економіка підприємства
  • Економічна теорія
  • Журналістика
  • Іноземні мови
  • Інформатика, програмування
  • Історія всесвітня
  • Історія України
  • Історія економічних вчень
  • Краєзнавство
  • Кулінарія
  • Культура
  • Література
  • Макроекономіка
  • Маркетинг
  • Математика
  • Медицина та здоров'я
  • Менеджмент
  • Міжнародні відносини
  • Мікроекономіка
  • Мовознавство
  • Педагогіка
  • Підприємництво
  • Політологія
  • Право
  • Релігієзнавство
  • Промисловість
  • Сільське господарство
  • Сочинения на русском
  • Соціологія
  • Литература на русском
  • Страхування
  • Твори
  • Фізика
  • Фізична культура
  • Філософія
  • Фінанси
  • Хімія
  • Цінні папери
  • Логіка
  • Туризм
  • Психологія