Тема 5. Цілочислові та параметричні задачі лінійного програмування

Лекція 11.

Тема лекції: Узагальнення задачі лінійного програмування.

Мета: ознайомити студентів з методами розв’язання задач цілочислового та параметричного програмування.

План лекції

1. Задачі цілочислового програмування.

1. Метод Гоморі.

2. Параметричне лінійне програмування.

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

2. Іванюта І. Д. Практикум з математичного програмування: Навчальний посібник / І. Д. Іванюта, В. І. Рибалка, І. А. Рудоміно-Дусятська. – К.: «Слово», 2008. - 296 с.

3. Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

1. Задачі цілочислового програмування.

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

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

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

Z= (1)

за умов

,= b_i, i= , (2)

x_j≥0, (j= ), (3)

x_j - цілі, (j= ), (4)

умова цілочисельності (4), яка додається до звичайної задачі ЛП, суттєво ускладнює її розв’язання.

2. Метод Гоморі.

Сутність методу Гоморі (метод відтинання) полягає у тому, що спочатку розв’язується звичайна задача ЛП без урахування вимог цілочисельності змінних. Якщо отриманий оптимальний план задачі цілочисловий, то задача розв’язана. У протилежному випадку у модель вводиться спеціальне додаткове обмеження, що враховує цілочисельність змінних і володіє такими властивостями:

- вона повинна бути лінійною;

- вона повинна відтинати знайдений оптимальний нецілочисловий план задачі;

- не повинна відтинати ні одного цілочислового плану.

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

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

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

=а-[a].

[a] – ціла частина числа а, т.б. найбільше ціле число, яке не перевищує числа а.

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

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

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

Приклад 1.

за умов