Главная | Обратная связь | Поможем написать вашу работу!

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

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

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

2.40. У цеху підприємства вирішено встановити додаткове обладнання, для розміщення якого виділено 19/3 м²площі. На придбання обладнання підприємство може витратити 10 тис. грн., при цьому воно може купити обладнання двох видів. Комплект обладнання I виду стоїть 1000 грн., а II виду – 3000 грн. Придбання одного комплекту обладнання I виду дозволяє збільшити випуск продукції в зміну на 2 од., а одного комплекту обладнання II виду — на 4 од. Знаючи, що для установки одного комплекту обладнання I виду потрібно 2 м² площі, а обладнання II виду — 1 м² площі, визначити такий набір додаткового обладнання, що дає можливість максимально збільшити випуск продукції.

Розв’язок. Складемо математичну модель задачі. Припустимо, що підприємство придбає x₁ комплектів обладнання I виду і x₂ комплектів обладнання II виду. Тоді змінні x₁ і х₂ повинні задовольняти наступним нерівностям:

(24)

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

F=2х₁+4х₂ (25)

По своєму економічному змісту змінні x₁ і х₂ можуть приймати лише цілі невід’ємні значення, тобто

х₁, х₂ ≥ 0 (26)

х₁, х₂ – цілі (27)

Таким чином, приходимо до наступної математичної задачі: знайти максимальне значення лінійної функції (25) при виконанні умов (24), (26) і (27). Так як невідомі можуть приймати тільки цілі значення, то задача (24) — (27) є задачею цілочисельного програмування. Оскільки число невідомих задачі дорівнює двом, Розв’язок даної задачі можна знайти, використовуючи її геометричну інтерпретацію. Для цього насамперед побудуємо багатокутник рішень задачі, що полягає у визначенні максимального значення лінійної функції (25) при виконанні умов (24) і (26) (рис. 2.2). Координати всіх точок побудованого багатокутника рішень ОАЕВС задовольняють системі лінійних нерівностей (24) і умові невід’ємності змінних (26). Разом з тим умові (27), тобто умові цілочисельності змінних, задовольняють координати лише 12 точок, відзначених на рис. 2.2. Щоб знайти точку, координати якої визначають Розв’язок вихідної задачі, замінимо багатокутник ОАВС багатокутником ОКЕМЫР, що містить всі припустимі точки із цілочисельними координатами і таким, що координати кожної з вершин є цілими числами. Виходить, якщо найти точку максимуму функції (25) на багатокутнику ОКЕМNF, то координати цієї точки і визначать оптимальний план задачі.

Для цього побудуємо вектор =(2; 4) і пряму 2 x₁ +4 x₂ =12, що проходить через багатокутник рішень ОКЕМNF (число 12 узято довільно). Побудовану пряму пересуваємо в напрямку вектора доти, поки вона не пройде через останню спільну точку її з даним багатокутником. Координати цієї точки і визначають оптимальний план, а значення цільової функції в ній є максимальним.

У цьому випадку шуканою є точка Е (1;3),у якій цільова функція приймає максимальне значення F_max =14. Отже, координати точки Е визначають оптимальний план задачі (24)-(27). Відповідно до цього плану підприємству варто придбати один комплект обладнання I виду і три комплекти обладнання II виду. Це забезпечить підприємству при наявних у нього обмеженнях на виробничі площі і кошти максимальне збільшення випуску продукції, рівне 14 од. за зміну.

Рис. 2.2

2.41. Для виконання робіт можуть бути використані п механізмів. Продуктивність i -го механізму (i = ) при виконанні j -ї роботи (j = ) дорівнює c_ij. Припускаючи, що кожний механізм може бути використаний тільки на одній роботі і кожна робота може виконуватися тільки одним механізмом, визначити закріплення механізмів за роботами, що забезпечує, максимальну продуктивність. Побудувати математичну модель задачі.

Розв’язок. Введемо змінну x_ij,значення якої дорівнює 1, якщо при виконанні i -ї роботи використовується j -й механізм, і дорівнює 0 у противному випадку. Тоді умови використання кожного механізму тільки на одній роботі виражаються рівностями

а умови виконання роботи тільки одним механізмом – рівностями

)

Таким чином, завдання полягає у визначенні таких значень невідомих x_ij (i = ; j = ), що задовольняють системам рівнянь (28) і (29) і умові (30), при яких досягається максимальне значення функції

Сформульована задача є задачею цілочисельного програмування.

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

при умовах

x_j ≥ 0 (j = ) (34)

x_j – цілі(j = ) (35)

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

Метод Гомори. Знаходження Розв’язок задачі цілочисельного програмування методом Гомори починають із визначення симплексним методом оптимального плану задачі (32)-(34) без врахування цілочисельності змінних. Після того як цей план знайдений, проглядають його компоненти. Якщо серед компонент немає дробових чисел, то знайдений план є оптимальним планом задачі цілочисельного програмування (32)-(35). Якщо ж в оптимальному плані задачі (32)-(34) змінна х_j приймає дробове значення, то до системи рівнянь (33) додають нерівність

і знаходять Розв’язок задачі (32)-(34), (36).

У нерівності (36) а_ij^* і b_i^* – перетворені вихідні величини а_ij і b_i,значення яких узяті з останньої симплекс-таблиці, а f (а_ij^*)і f (b_i) – дробові частини чисел (під дробовою частиною деякого числа а розуміється найменше невід’ємне число b таке, що різниця між a і b є цілою). Якщо в оптимальному плані задачі (32)-(34) дробові значення приймають декілька змінних, то додаткова нерівність (36) визначається найбільшою дробовою частиною.

Якщо в знайденому плані задачі (32)-(34), (36) змінні приймають дробові значення, то знову додають одне додаткове обмеження і процес обчислень повторюють. Проводячи кінцеве число ітерацій, або одержують оптимальний план задачі цілочисельного програмування (32)-(35), або встановлюють її нерозв’язність.

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

де γ_ij визначаються з наступних співвідношень:

1) для x_j, які можуть приймати не цілочисельні значення,

2) для x_j,які можуть приймати тільки цілочисельні значення,

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

1. Використовуючи симплексний метод, знаходять Розв’язок задачі (32)-(34) без врахування вимоги цілочисельності змінних.

2. Складають додаткове обмеження для змінної, котра в оптимальному плані задачі (32)-(34) має максимальне дробове значення, а в оптимальному плані задачі (32)-(35) повинна бути цілочисельною.

3. Використовуючи двоїстий симплекс-метод, знаходять Розв’язок задачі, що виходить із задачі (32)-(34) у результаті приєднання додаткового обмеження.

4. У випадку необхідності складають ще одне додаткове обмеження і продовжують ітераційний процес до одержання оптимального плану задачі (32)-(35) або встановлення її нерозв’язності.

2.49. Методом Гомори знайти максимальне значення функції

F= 3 х₁+ 2 х₂ (40)

при умовах

x_j ≥ 0 (j = ) (42)

x_j – цілі(j = ) (43)

Дати геометричну інтерпретацію Розв’язок задачі.

Розв’язок. Для визначення оптимального плану задачі (40)-(43) спочатку знаходимо оптимальний план задачі (40)-(42) (табл. 2.28).

Таблиця 2.28

і	Базис	С_б	Р₀
Р₁	P₂	Р₃	Р₄	Р₅
	Р₃ Р₄ Р₅			–3 –3	–1 –2
	Р₃ Р₁ Р₅				–1 –2 –5		–1
	Р₂ Р₁ Р₅		7/2 19/2 71/2			1/2 1/2 5/2	–1/2 1/2 1/2

Як видно з табл. 2.28, знайдений оптимальний план X =(19/2; 7/2; 0; 0; 10) задачі (40)-(42) не є оптимальним планом задачі (40)-(43), оскільки два компоненти x₁ і x₂ мають не цілочисельні значення. При цьому дробові частини цих чисел рівні між собою. Тому для однієї із цих змінних складається додаткове обмеження. Складемо, наприклад, таке обмеження для змінної х₂. З останньої симплекс-таблиці (табл. 2.28) маємо

х₂+ (1/2) х₃ –(1/2) х₄ =7/2.

Таким чином, до системи обмежень задачі (40)-(42) додаємо нерівність

f (1) х₂+f (1/2) х₃+f (–1/2) х₄ ≥ f (7/2), або (1/2) х₃ +(1/2) х₄ ≥ 1/2, тобто

х₃+х₄ ≥ 1 (44)

Таблиця 2.29

i	Базис	С_б	Р₀
Р₁	Р₂	Р₃	Р₄	Р₅	Р₆
	P₂ Р₁ Р₅ Р₆		7/2 19/2 –1 71/2			1/2 1/2 –1 5/2	–1/2 1/2 –1 1/2
	P₂ Р₁ Р₅ Р₄					–1		–1/2 1/2 –1 1/2

Знаходимо тепер максимальне значення функції (40) при виконанні умов (41), (42) і (44) (табл. 2.29).

З табл. 2.29 видно, що вихідна задача цілочисельного програмування має оптимальний план X* =(9; 4; 0; 1; 32). При цьому плані значення цільової функції дорівнює F_тах =35. Дамо геометричну інтерпретацію Розв’язок задачі. Областю припустимих рішень задачі (40)-(42) є багатокутник ОАВСD (рис. 2.3). З рис. 2.3 видно, що максимальне значення цільова функція приймає в точці C (19/2; 7/2), тобто що X =(19/2; 7/2; 0; 0; 34) є оптимальним планом. Це безпосередньо видно і з табл. 2.28. Так як X =(19/2; 7/2; 0; 0; 34) не є оптимальним планом задачі (40)-(43) (числа 19/2 і 7/2 – дробові), то вводиться додаткове обмеження x₃+х₄≥ 1. Виключаючи із нього х₃ і х₄ підстановкою замість них відповідних значень із рівнянь системи обмежень (41), одержимо x₁ ≤ 19. Цій нерівності відповідає півплощина, обмежена прямою x₁ =9, що відтинає від багатокутника ОАВСD трикутник ЕFС.

Рис. 2.3.

Як видно з рис. 2.3, областю припустимих рішень отриманої задачі є багатокутник ОАВЕFD. У точці Е (9; 4) цього багатокутника цільова функція даної задачі приймає максимальне значення. Так як координати точки Е – цілі числа і невідомі х₃, х₄ і x₅ приймають цілочисельні значення при підстановці в рівняння (41) значень x₁ =9 і х₂ =4, то X* =(9; 4; 0; 0; 32) є оптимальним планом задачі (40)-(43). Це випливає і з табл. 2.29.

⇐ Предыдущая 5 6 7 8 91011 12 13 14 Следующая ⇒