Цілочислове програмування

Размещено на http://www.allbest.ru/

ЛЕКЦІЯ 8

ЦІЛОЧИСЛОВЕ ПРОГРАМУВАННЯ

Анотація

Економічна і математична постановка цілочислової задачі лінійного програмування. Геометрична інтерпретація розв'язків цілочислових задач лінійного програмування на площині. Загальна характеристика методів розв'язування цілочислових задач лінійного програмування. Методи відтинання. Метод Гоморі. Комбінаторні методи. Метод гілок та меж.

1. Економічна і математична постановка цілочислової задачі лінійного програмування

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

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

- вибір послідовності виробничих процесів;

- календарне планування роботи підприємства;

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

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

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

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

 (1)

За умов:

(2)

(3)

- цілі числа (4)

2. Геометрична інтерпретація розв'язків цілочислових задач лінійного програмування на площині

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

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

Нехай, наприклад, у результаті розв'язування задачі про поєднання галузей у сільськогосподарському підприємстві отримали оптимальне поголів'я корів - 1235,6. Округливши це значення до 1236, не припустимося значної похибки. Проте за деяких умов такі спрощення призводять до істотних неточностей.

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

Рис. 1:

Максимальне значення функціонала для даної задачі знаходиться в точці В. Округлення дасть таке значення оптимального плану (точка D на рис. 1). Очевидно, що точка D не може бути розв'язком задачі, оскільки вона навіть не належить множині допустимих розв'язків (чотирикутник ОАВС), тобто відповідні значення змінних не задовольнятимуть систему обмежень задачі.

Зауважимо, що геометрично множина допустимих планів будь-якої лінійної цілочислової задачі являє собою систему точок з цілочисловими координатами, що знаходяться всередині опуклого багатокутника допустимих розв'язків відповідної не цілочислової задачі. Отже, для розглянутого на рис. 1 випадку множина допустимих планів складається з дев'яти точок (рис. 2), які утворені перетинами сім'ї прямих, що паралельні осям Ох₁ та Oх₂ і проходять через точки з цілими координатами 0, 1, 2.

Рис. 2:

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

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

3. Загальна характеристика методів розв'язування цілочислових задач лінійного програмування

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

1) точні методи:

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

- комбінаторні методи;

2) наближені методи.

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

До цієї групи належать:

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

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

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

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

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

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

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

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

До наближених методів належать:

- метод локальної оптимізації (метод вектора спаду);

- модифікації точних методів;

- методи випадкового пошуку та ін.

Головними показниками для зіставлення ефективності застосування конкретних наближених алгоритмів на практиці є такі: абсолютна та відносна похибки отриманих наближених розв'язків.

Де:

F - цільова функція (в даному разі для визначеності допускаємо вимогу відшукання максимального її значення);

Х₁ - наближений розв'язок, знайдений деяким наближеним методом;

Х^* - оптимальний план задачі.

4. Методи відтинання. Метод Гоморі

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

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

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

Отриманий новий багатогранник розв'язків містить всі цілі точки, які були в початковому, і розв'язок, що буде отримано на ньому, буде цілочисловим (рис. 3).

Рис. 3:

Слід відмітити, що визначення правила для реалізації ідеї Данціга стосовно формування додаткового обмеження виявилось досить складним завданням і першим, кому вдалось успішно реалізувати цю ідею, був Гоморі.

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

(5)

За умов:

(6)

(7)

- цілі числа (8)

Допустимо, що параметри - цілі числа.

Не враховуючи умови цілочисловості, знаходимо розв'язок задачі (5)-(7) симплексним методом. Нехай розв'язок існує і міститься в такій симплексній таблиці:

Таблиця 1:

Змінні - базисні, а - вільні. Оптимальний план задачі: . Якщо - цілі числа, то отриманий розв'язок є цілочисловим оптимальним планом задачі (5)-(8). Інакше існує хоча б одне з чисел, наприклад, - дробове. Отже, необхідно побудувати правильне обмеження, що відтинає нецілу частину значення .

Розглянемо довільний оптимальний план задачі (5)-(7). Виразимо в цьому плані базисну змінну через вільні змінні:

(9)

Виразимо коефіцієнти при змінних даного рівняння у вигляді суми їх цілої та дробової частин. Введемо позначення:

- - ціла частина числа ;

- - дробова частина числа .

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

Наприклад, для:

Отримаємо:

(10)

(11)

Отже, рівняння (11) виконується для будь-якого допустимого плану задачі (5)-(7). Допустимо тепер, що розглянутий план є цілочисловим оптимальним планом задачі. Тоді ліва частина рівняння (11) складається лише з цілих чисел і є цілочисловим виразом. Отже, права його частина також є цілим числом і справджується рівність:

(12)

Де:

N - деяке ціле число.

Величина N не може бути від'ємною. Якщо б , то з рівняння (12) приходимо до нерівності:

Звідки:

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

Якщо від лівої частини рівняння (12) відняти деяке невід'ємне число, то приходимо до нерівності:

(13)

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

Отже, для розв'язування цілочислових задач лінійного програмування (1)-(4) методом Гоморі застосовують такий алгоритм:

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

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

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

Доведено, що за певних умов алгоритм Гоморі є скінченним, але процес розв'язування задач великої розмірності методом Гоморі повільно збіжний. Слід також мати на увазі, що і кількість ітерацій суттєво залежить від сформованого правильного відтинання. Наведене правило (13) щодо формування правильного відтинання не єдине. Існують ефективніші відтинання, які використовуються у другому та третьому алгоритмах Гоморі, однак наявний практичний досвід ще не дає змоги виділити з них найкращий.

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

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

Розглянемо приклад розв'язування цілочислової задачі лінійного програмування методом Гоморі.

Приклад 1. Сільськогосподарське підприємство планує відкрити сушильний цех на виробничій площі 190 м², маючи для цього 100 тис. грн., і можливість придбати устаткування двох типів: А і В. Техніко-економічну інформацію стосовно одиниці кожного виду устаткування подано в табл. 2:

Таблиця 2:

Розв'язання. Нехай х₁ і х₂ - кількість комплектів устаткування відповідно типу А і В.

Запишемо економіко-математичну модель задачі:

Розв'язуємо задачу, нехтуючи умовою цілочисловості. Остання симплексна таблиця набуде вигляду:

Таблиця 3:

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

- тоді додаткове обмеження набуває вигляду:

.

Таблиця 4:

Приєднавши отримане обмеження до симплексної таблиці (табл. 3) з умовно-оптимальним планом, дістанемо знаходимо цілочисловий оптимальний план

5. Комбінаторні методи. Метод гілок та меж

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

Розглянемо один із комбінаторних методів. Для розв'язування задач цілочислового програмування ефективнішим за метод Гоморі є метод гілок і меж. Спочатку, як і в разі методу Гоморі, симплексним методом розв'язується послаблена (без умов цілочисловості) задача. Потім вводиться правило перебору.

Нехай потрібно знайти х_j - цілочислову змінну, значення якої х_j = в оптимальному плані послабленої задачі є дробовим. Очевидно, що в деякому околі даної точки також не існує цілочислових значень, тому відповідний проміжок можна виключити з множини допустимих планів задачі в подальшому розгляді. Таким проміжком є інтервал між найближчими до цілочисловими значеннями. Можна стверджувати, що на інтервалі цілих значень немає. Наприклад, якщо = 2,7 дістаємо інтервал , де, очевидно, немає х_j, яке набуває цілого значення і оптимальний розв'язок буде знаходитися або в інтервалі , або . Виключення проміжку з множини допустимих планів здійснюється введенням до системи обмежень початкової задачі додаткових нерівностей. Тобто допустиме ціле значення x_j має задовольняти одну з нерівностей виду:

Дописавши кожну з цих умов до задачі з послабленими обмеженнями, дістанемо дві, не пов'язані між собою, задачі. Тобто, початкову задачу цілочислового програмування (1)-(4) поділимо на дві задачі з урахуванням умов цілочисловості змінних, значення яких в оптимальному плані послабленої задачі є дробовими. Це означає, що симплекс-методом розв'язуватимемо дві такі задачі:

Перша задача:

(14)

За умов:

(15)

(16)

- цілі числа, (17)

(18)

Друга задача:

(19)

За умов:

(20)

(21)

- цілі числа (22)

(23)

Де:

- дробова компонента розв'язку задачі (1)-(4).

Наведені задачі (14)-(18) і (19)-(23) спочатку послаблюємо, тобто розв'язуємо з відкиданням обмежень (17) і (22). Якщо знайдені оптимальні плани задовольняють умови цілочисловості, то ці плани є розв'язками задачі (1)-(4). Інакше пошук розв'язку задачі триває. Для дальшого розгалуження вибираємо розв'язок задачі з більшим значенням цільової функції, якщо йдеться про максимізацію, і навпаки - з меншим значенням цільової функції в разі її мінімізації. Подальше розгалуження виконується доти, доки не буде встановлено неможливість поліпшення розв'язку. Здобутий останній план - оптимальний.

Розв'язування цілочислових задач методом гілок і меж можна значно прискорити. Очевидно, що кожна наступна задача, яку отримують в процесі розв'язування відрізняється від попередньої лише одним обмеженням. Тому за послідовного розв'язування задач немає сенсу розв'язувати їх симплексним методом спочатку. Досить буде почергово приєднати нові обмеження виду (18) і (23) до останньої симплекс-таблиці попередньої задачі та вилучити (в разі необхідності) непотрібні «старі» обмеження.

Геометрично введення додаткових лінійних обмежень виду (18) та (23) в систему обмежень початкової задачі означає проведення гіперплощин (прямих), що розтинають багатогранник (багатокутник) допустимих планів відповідної задачі лінійного програмування у такий спосіб, що уможливлюється включення в план найближчої цілої точки цього багатокутника (рис. 4). Допустимо, що А - точка максимуму, тоді за методом гілок та меж багатокутник допустимих планів задачі ABCOD поділяється на дві частини прямими та +1, що виключає з розгляду точку А, координата якої є не цілим числом.

Рис. 4:

Опишемо алгоритм методу гілок та меж:

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

Коли в умовно-оптимальному плані є дробові значення, то вибирають одну зі змінних і визначають її цілу частину ;

Записують два обмеження, що відтинають не цілочислові розв'язки:

Кожну з одержаних нерівностей приєднують до обмежень початкової задачі. В результаті отримують дві нові цілочислові задачі лінійного програмування;

У будь-якій послідовності розв'язують обидві задачі.

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

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

Якщо ж в обох задачах одержано не цілочислові розв'язки, то для дальшого гілкування вибирають ту задачу, для якої здобуто краще значення цільової функції і здійснюють перехід до кроку 2.

Приклад 2. Розв'яжемо методом гілок і меж задачу з прикладу 1.

Розв'язання. Відкинувши умову цілочисловості, дістанемо розв'язок:

Отже, допустиме ціле значення х₂ має задовольняти одну з нерівності:

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

Для задачі І (з обмеженням ) оптимальним буде розв'язок:

А для задачі IІ (з обмеженням ) - розв'язок:

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

Розв'язуємо задачу І, окремо приєднуючи до неї обмеження:

;

.

Отримуємо такі дві задачі:



Розв'язком задачі ІІІ є план , а задачі IV - план, . Обидва розв'язки є цілочисловими, проте краще значення цільової функції забезпечує розв'язок задачі IV. Тому оптимальним планом початкової цілочислової задачі буде , що збігається з розв'язком, отриманим за методом Гоморі. математичний геометричний площина

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

Рис. 5:

Кожен елемент такого «дерева» - це певна задача, що має відповідний оптимальний план. Після одержання не цілочислового розв'язку послабленої (тобто без умови цілочисловості) початкової задачі ми перетворили її на дві інші з додатковими умовами. З них кращим виявився розв'язок задачі І, однак оскільки він був не цілочисловим, то ми продовжили процес гілкування. Задачу І введенням додаткових обмежень перетворили в задачу ІІІ та задачу IV. Оптимальні плани обох цих задач цілочислові, але план задачі IV дає більше значення функціонала, тому цілочисловим оптимальним планом початкової задачі є розв'язок задачі IV.

Размещено на Allbest.ru