Тема 6. Нелінійні оптимізаційні моделі економічних процесів Постановка задачі дискретного лінійного програмування

До класу задач дискретного лінійного програмування належать ЗЛП, в яких умову невід’ємності змінних замінено вимогою дискретності, тобто для кожної змінної х_j (j = ) визначено набір значень змінних (не обов’язково цілих), яких вона може набувати. В загальному вигляді задачу дискретного лінійного програмування можна записати так:

; (2.95)

£

³

; (2.96)

, (2.97)

де n₁ £ n.

Якщо n₁ = n, задача (2.81)-(2.83) називається задачею дискретного лінійного програмування, та частково дискретною, якщо n₁ < n.

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

ЗЦЛП формулюється аналогічно задачі лінійного програмування. Відмінність полягає в тому, що всі (частково) змінні, які становлять оптимальний план, мають бути цілими числами:

; (2.98)

£

³

; (2.99)

, (2.100)

– цілі, . (2.101)

Якщо n₁ = п, то (2.98)-(2.101) – ЗЦЛП; якщо n₁ < п – задача частково цілочислового лінійного програмування.

Окремий випадок ЗЦЛП – задача з так званими булевими змінними, тобто зі змінними, що набувають значень "нуль" або "одиниця":

; (2.102)

³

³

£

; (2.103)

(2.104)

Слід зазначити, що й досі через обчислювальні труднощі розв’язування ці задачі застосовуються на практиці обмежено.

Здавалося б, очевидний наступний шлях розв’язування ЗЦЛП: розв'язати відповідну ЗЛП, тобто задачу (2.98)-(2.101), а потім округляти значення змінних оптимального плану до найближчих цілих чисел. Однак такий шлях у багатьох випадках не лише дає погане наближення до оптимуму, але й не завжди отриманий набір чисел задовольняє основну систему обмежень.

Розглянемо приклад.

Приклад 2.15

;

х₁ ³ 0, х₂ ³ 0; х₁, х₂ - цілі.

Побудуємо множину планів задачі, не враховуючи цілочисловості змінних. Множина планів відповідної задачі лінійного програмування б опуклий многокутник ОАBCD (рис. 2.11).

Рис. 2.11

Множина планів ЗЦЛП – сукупність дискретних точок цього многокутника, отже, загальна теорема лінійного програмування для таких задач несправедлива. Оптимальний план відповідної ЗЛП: х₁ = 90/23; х₂ = 40/23. Якщо заокруглити значення змінних до цілих чисел, тобто взяти х₁ =4, х₂ = 2, то ці значення не задовольняють основну систему обмежень, тобто не є планами обох задач.

Таким чином, щоб розв’язати ЗЦЛП, потрібні особливі методи розв'язування. Розрізняють методи відсікання та комбінаторні методи.

Методи відсікання

Вихідним для методів відсікання є оптимальний план відповідної задачі лінійного програмування, отриманої в результаті виключення умови цілочисловості. Якщо умову цілочисловості задовольняють усі значення змінних цього оптимального плану, то він – оптимальний план ЗЦЛП. Якщо умова цілочисловості не виконується хоча б одною змінною, то складають додаткове лінійне обмеження (в противному разі виходимо за рамки лінійного програмування), що виключає (відсікає) хоча б одну нецілочислову компоненту плану. Розв'язується нова задача лінійного програмування. Процес побудови додаткових обмежень і розв’язування отримуваних задач лінійного програмування триває доти, доки не вийде цілочисловий оптимальний план або стане очевидною нерозв’язність ЗЦЛП.

Додаткове обмеження кожного разу треба складати таким чином, щоб не відсікалась частина області, що містить який-небудь план ЗЦЛП, тобто відсікання має задовольняти так звану властивість правильності.

Означення 2.16. Нехай Х* – оптимальний план відповідної ЗЛП, що не є планом ЗЦЛП. Нерівність

(2.105)

називається правильним відсіканням, якщо виконуються такі умови:

1) Х* не задовольняє нерівність,

2) будь-який план ЗЦЛП задовольняє цю нерівність.

Відмінність методів відсікання полягає в методах побудови правильних відсікань. Уперше методи побудови правильних відсікань для розв’язування цілочислових і частково цілочислових задач лінійного програмування були розроблені Ф. Гоморі.

Перший алгоритм Гоморі

Цей алгоритм застосовується для розв’язування цілочислових задач лінійного програмування.

Нехай задано задачу

; (2.106)

; (2.107)

, (2.108)

– цілі, . (2.109)

Розв’яжемо симплексним методом задачу (2.106)-(2.109). Нехай Х* – її оптимальний план. Якщо всі компоненти Х* цілі, то він оптимальний план задачі (2.42)-(2.45). Якщо хоча б одна компонента неціла, процес розв’язування треба продовжити.

Нехай – неціла компонента плану Х*. Множину індексів небазисних змінних останньої симплексної таблиці розв'язування задачі (2.106)-(2.109) позначимо N. Нагадаємо, що найближче ціле число, що перевищує а, позначається [a], а дробова частина (тобто а) – [a] = {a}. Очевидно, що {a} = 0.

Покажемо, що по i-му рядку симплексної таблиці можна побудувати правильне відсікання.

Теорема 2.16 Нехай X* – план задачі (2.106)-(2.109) тоді співвідношення

,

u_і ³ 0, u_i – ціле, визначає правильне відсікання.

Приклад 2.16 Знайти розв’язок задачі

;

х_j ³ 0 – цілі .

Другий алгоритм Гоморі

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

Нехай задано таку задачу:

; (2.110)

; (2.111)

, (2.112)

– цілі, ; n₁ < n. (2.113)

Другий алгоритм Гоморі грунтується на такій теоремі.

Теорема 2.18 Нехай Х* – оптимальний план задачі (2.110)-(2.113). Якщо – неціле (1 £ і £ n), то

; (2.114)

u ³ 0, ціле,

де N – множина індексів небазисних змінних плану Х*;

визначає правильне відсікання.

Приклад 2.17 Знайти розв’язок задачі

;

х₁ ³ 0; х₂ ³ 0; х₂ – ціле.