Повна версія

Головна arrow Економіка arrow Дослідження операцій в економіці

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

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

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

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

Завдання лінійного цілочисельного програмування формулюється так: знайти таке рішення (план) i, при якому лінійна функція

(8.1)

приймає максимальне або мінімальне значення при обмеженнях

(8.2)

(8.3)

- цілі числа. (8.4)

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

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

Методи целочисленной оптимізації можна розділити на три основні групи: а) методи відсікання; б) комбінаторні методи; в) наближені методи. Зупинимося докладніше на методах відсікання.

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

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

  • воно повинно бути лінійним;
  • має відсікати знайдений оптимальний нецілочисельне план;
  • не повинно відсікати жодного цілочисельного плану.

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

Далі завдання вирішується з урахуванням нового обмеження. Після цього в разі потреби додається ще одне обмеження і т.д.

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

Мал. 8.1

в первісному многограннике рішень, і відповідно отримане при цьому многограннике оптимальне рішення буде цілочисельним (рис. 8.1).

Один з алгоритмів розв'язання задачі лінійного цілочисельного програмування (8.1) - (8.4), запропонований Р. Гомори, заснований на симплексному методі і використовує досить простий спосіб побудови правильного відсікання.

Нехай задача лінійного програмування (8.1) - (8.3) має кінцевий оптимум, і на останньому етапі її рішення симплексним методом отримані наступні рівняння, що виражають основні змінні через неосновні змінні оптимального рішення:

(8.5)

так що оптимальним рішенням задачі (8.1) - (8.3) є i, в якому, наприклад, β; - неціла компонента. В цьому випадку можна довести, що нерівність, сформоване за i- му рівняння системи (8.5), має всі властивості правильного відсікання.

Для вирішення задачі цілочислового лінійного програмування (8.1) - (8.4) методом Гоморі використовується наступний алгоритм.

  • 1. симплексним методом вирішити задачу (8.1) - (8.3) без урахування умови целочисленности. Якщо всі компоненти оптимального плану цілі, то він є оптимальним і для задачі цілочислового програмування (8.1) - (8.4). Якщо перше завдання (8.1) - (8.3) нерозв'язна (тобто нс має кінцевого оптимуму або умови її суперечливі), то і друге завдання (8.1) - (8.4) також нерозв'язна.
  • 2. Якщо серед компонент оптимального рішення є нецілі, то вибрати компоненту з найбільшою цілою частиною і за відповідним рівнянням системи (8.5) сформувати правильне відсікання (8.6).
  • 3. Нерівність (8.6) введенням додаткової неотрицательной цілочисельний змінної перетворити в рівносильне рівняння і включити його в систему обмежень (8.2).
  • 4. Отриману розширену задачу вирішити симплексним методом. Якщо знайдений оптимальний план буде цілочисельним, то задача цілочисельного програмування (8.1) - (8.4) вирішена. В іншому випадку повернутися до п. 2 алгоритму.

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

!!! 1 У нерівності (8.6) присутній символ {}, що означає дробову частину числа. Цілою частиною числа а називається найбільше ціле число [в], що не перевершує а, дробової частиною числа - число {а}, рівне різниці між цим числом і його цілою частиною, тобто {а} = а- [в].

Наприклад, для (зверніть увагу, саме -3, а не -2) і

(8.6)

(8.7)

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

!!! 8.1. Для придбання обладнання з сортування зерна фермер виділяє 34 ден. од. Обладнання повинно бути розміщено на площі, що не перевищує 60 кв. м. Фермер може замовити обладнання двох видів: менш потужні машини типу А вартістю 3 ден. од., що вимагають виробничу площу 3 кв. м (з урахуванням проходів), і продуктивністю за зміну 2 т зерна, і більш потужні машини типу В вартістю 4 ден. од., що займають площу 5 кв. м, і продуктивністю за зміну 3 т сортового зерна.

Потрібно скласти оптимальний план придбання обладнання, що забезпечує максимальну загальну продуктивність за умови, що фермер може придбати не більше 8 машин типу В.

Рішення. Позначимо через кількість машин відповідно типу А і В, через Z - загальну продуктивність. Тоді математична модель задачі набуде вигляду

(!!! 8.8)

при обмеженнях:

(8.2)

(8.3)

- цілі числа. (8.4)

Наведемо завдання до канонічного виду, ввівши додаткові невід'ємні змінні . Отримаємо систему обмежень:

(8.5)

Вирішуємо задачу симплексним методом. Для наочності рішення ілюструємо графічно (рис. 8.2).

Мал. 8.2

На рис. 8.2 OKLM - область допустимих рішень задачі (8.Г) - (8.3 '), обмежена прямими (1), (2), (3) і осями координат; L (2/3; 8) - точка оптимального, але нецілочисельне рішення задачі (8.1 ') - (8.3'); (4) - пряма, що відсікає це нецелочисленное рішення; OKNM - область допустимих рішень розширеної задачі (8.1 ') - (8.3'), (8.6 '); N ( 2; 7) - точка оптимального цілочисельного рішення.

I крок. Основні змінні неосновні змінні

Перше базисне рішення - допусти

моє. Відповідне значення лінійної функції

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

прийняти система обмежень, з умови мінімуму відповідних відносин:

тобто що дозволяє (виділеним) є третє рівняння. При х. 2 = 8 в цьому рівнянні х- = 0, і в неосновні переходить змінна х 5 .

II етап. Основні змінні х 2 , х 3 , х 4 .

Неосновні змінні .р ,, ху

Після перетворень отримаємо

Переводимо в основні змінну а в неосновні х4.

III крок. Основні змінні х ,, х 2 , х 3 .

Неосновні змінні х4, х5.

Після перетворень отримаємо

Базисне рішення X., оптимально для задачі (8.1 ') - (8.3') ( ), так як в вираженні лінійної функції

відсутні неосновні змінні з позитивними коефіцієнтами.

Однак рішення Х 3 не задовольняє умові целочисленности (8.4 ') • За першого рівняння зі змінною х ,, що отримала нецелочисленное значення в оптимальному рішенні (2/3), складаємо додаткове обмеження (8.6):

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

Так як дробові частини ,

, Го остання нерівність запишемо

у вигляді

(8.6 ')

Ввівши додаткову целочисленную змінну х6 0, одержимо рівносильне нерівності (8.6 ') рівняння

(8.7 ')

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

IV крок. Основні змінні x v х 2, х3, χβ.

Неосновні змінні х4, х5.

Базисне рішення - неприпустимий

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

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

V крок. Основні змінні х ,, х2, х3, х5.

Неосновні змінні х4, х6.

Отримаємо після перетворень

Так як в вираженні лінійної функції немає основних змінних з позитивними коефіцієнтами, то Х 5 - оптимальне рішення.

Отже, Zmax = 25 при оптимальному целочисленном вирішенні X * = Х 5 = (2; 7; 19; 0; 1; 0), тобто максимальну продуктивність 25 т сортового зерна за зміну можна отримати придбанням 2 машин типу Л та 7 машин типу В при цьому незайнята площа приміщення складе 19 кв. м, залишки грошових коштів з виділених дорівнюють нулю, в резерві для покупки - 1 машина типу В (шоста компонента змістовного сенсу не має).

Зауваження. Для геометричної інтерпретації на площині Ох, х2 (див. Рис. 8.2) відсікання (8.6 ') необхідно входять до нього змінні х 4 і х- висловити через змінні х, і х2. Отримаємо (див. 2-е і 3-е рівняння системи обмежень (8.5 '))

  • (Див. Відсікання прямий (4) на рис. 8.2). ►
  • 8.2. Є досить велика кількість колод довжиною 3 м. Колоди слід розпиляти на заготовки двох видів: довжиною 1,2 і 0,9 м, причому заготовок кожного виду повинно бути отримано не менше 50 і 81 шт. відповідно. Кожна колода можна розпиляти на зазначені заготовки декількома способами: 1) на 2 заготовки але 1,2 м; 2) па 1 заготовку 1,2 м і 2 заготовки по 0,9 м; 3) на 3 заготовки по 0,9 м. Знайти число колод, що розпилюються кожним способом, з тим щоб заготовок будь-якого виду було отримано з найменшого числа колод.

Рішення. Позначимо через х {} х2, х3 число колод, що розпилюються відповідно 1, 2 і 3-м способами. З них можна отримати 2xj + х2 заготовок по 1,2 м і 2-х х + 3х2 заготовок по 0,9 м. Загальна кількість колод позначимо Z. Тоді математична модель задачі набуде вигляду

(8.1 ")

при обмеженнях:

  • (8.2 ")
  • (8.3 ")
  • - цілі числа. (8.4 ")

Ввівши додаткові змінні при

ведемо систему нерівностей до равносильной системі рівнянь:

(8.5 ")

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

III крок. Основні змінні x v х 2.

Неосновні змінні х у х А , х 5.

тобто при оптимальному рішенні

Вийшло, що дві компоненти оптимального рішення не задовольняють умові целочисленности (8.4 "), причому більшу цілу частину має компонента х 2. Відповідно до Π. 2 алгоритму розв'язання задачі цілочисельного програмування (див. С. 166) за другим рівнянням, що містить цю змінну х 2, складаємо додаткове обмеження (8.6):

Знайдемо дробові частини

і запишемо остання нерівність у вигляді

(8.6 ")

Ввівши додаткову змінну отримаємо

рівносильне нерівності (8.6 ") рівняння:

(8.7 ")

Висловимо з (8.7 ") додаткову змінну х6 і отримане рівняння введемо в систему обмежень, яку ми мали на останньому, III, крок рішення завдання (8.1") - (8.3 ") (без умови целочисленности).

IV крок. Основні змінні х { , х у х 6.

Неосновні змінні х 3, х4, х 5.

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

V крок. Основні змінні х); х 2, х3.

Неосновні змінні х4, х5, хб.

тобто при оптимальному рішенні

Отримане оптимальне рішення розширеної задачі (8.1 ") - (8.3"), (8.6 ") знову не задовольняє умові целочисленности (8.4"). По першому рівнянню зі змінною Xj, що отримала нецелочисленное значення в оптимальному

рішенні ( ), еоставляем другу додаткову ограни

чення (8.6):

яке наводимо до виду

За допомогою додаткової змінної приво

дим це нерівність до рівносильному рівняння, яке включаємо в систему обмежень, отриману на останньому, V, крок рішення розширеної задачі (8. Г ') - (8.3 "), (8.6") симплексним методом.

VI крок. Основні змінні x v х 2 , х у х т

Неосновні змінні х 4 , X-, х 6.

Опускаючи подальше рішення задачі симплексним методом (пропонуємо зробити це самим студентам), на заключному, VII, крок отримаємо.

VII крок. Основні змінні x v х т х3, х г

Неосновні змінні x v х 6 , х т

тобто при

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

Слід звернути увагу на те, що в отриманому виразі лінійної функції Z відсутні неосновні змінні х Г) і х 6. Це означає, що, взагалі кажучи, існує безліч оптимальних рішень (будь-яких, не обов'язково цілочисельних), при яких Z '= Zmjn = 46. Ці рішення виходять при значенні неосновної змінної х 7 (входить у вираз для Z), що дорівнює нулю (тобто при х 7 = 0), і при будь-яких значеннях неосновних змінних Ж5 і х 6 (не входять у вираз для Z), які "дозволяє" прийняти система обмежень: 0 <лг5 <min | 6; 39/2; 1; ∞} = 1 і 0 <х6 <min {° o; 13; ∞; l} = l, тобто при 0 < х 5 1 і 0 < x (i ≤ 1. Але в силу умови целочисленности змінні х- і х (> можуть прийняти тільки значення 0 або 1. Тому завдання матиме чотири цілочисельних оптимальних рішення, коли х. і * 6 в будь-якій комбінації приймають значення 0 або 1, а х 7 = 0. Підставляючи ці значення в систему обмежень на VII етапі, знайдемо ці оптимальні рішення:

Наявність альтернативних оптимальних цілочисельних рішень дозволяє здійснити вибір одного з них, керуючись додатковими критеріями, що не враховуються в математичної моделі задачі. Наприклад, з умови даної задачі випливає, що розпилювання колод не дає відходів лише за 3-му способу, тому природно при виборі одного з чотирьох оптимальних рішень віддати перевагу вирішенню Х ^ 3при якому максимальне число колод ( х 2 = 41) розпилюється без відходів.

Отже, Zmin = 46 при оптимальних цілочисельних рішеннях (5; 41; 0), (6; 39; 1), (7; 36; 3), (6; 38; 2). При записи оптимальних рішень ми залишили лише перші три компоненти, що виражають число колод, що розпилюються відповідно 1, 2 і 3-м способами, і виключили останні чотири компоненти, які не мають смислового значення. ►

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

  • [1] Можна переконатися, що при цьому рішення задачі коротше.
 
<<   ЗМІСТ   >>