Яка задача математичного програмування називається цілочисловою?

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

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

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

за умов: ;                                         ; — цілі числа .                                                                                                                                                                                                                                                                     

10. Опишіть алгоритм методу Гоморі.

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

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

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

Якщо задача не має розв’язку (цільова функція необмежена, або система обмежень несумісна), то задача також не має розв’язку.

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

.

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

 

 

11.Як звести задачу лінійного програмування до канонічної форми?

Задачу ЛП можна легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень всі b_i (i = 1, 2, …, m) невід’ємні, а всі обмеження є рівностями.

Якщо якесь b_i від’ємне, то, помноживши i -те обмеження на
(– 1), дістанемо у правій частині відповідної рівності додатне значення. Коли i -те обмеження має вигляд нерівності а _{i 1} х ₁ + а _{i 2} х ₂ + … + а _in x_n ≤ b_i, то останню завжди можна звести до рівності, увівши додатковузмінну x_{n + 1}: a_{i 1} x ₁ + a_{i 2} x ₂ + … +
+ a_in x_n + x_{n + 1} = b_i.

Аналогічно обмеження виду а _{k 1} x ₁ + a_{k 2} x ₂ + … + a_knx_n ≥ b_k зводять до рівності, віднімаючи від лівої частини додаткову змінну х_{n + 2}, тобто: a_{k 1} x ₁ + a_{k 2} x ₂ + … + a_knx_n – x_{n + 2} = b_k (х_{n +1} ≥ 0, х_{n +2} ≥ 0).