Навігація
Головна
Цілочисельне програмуванняОСНОВИ ЛІНІЙНОГО ПРОГРАМУВАННЯОснови лінійного програмуванняДержавне програмуванняМОЖЛИВОСТІ ВИКОРИСТАННЯ ПРОКУРОРОМ І АДВОКАТОМ НЕЙРОЛІНГВІСТИЧНОГО...Метод лінійного програмування, симплекс-метод і лінійні оцінкиМатематичне програмуванняСтратегічне програмуванняСОЦІАЛЬНЕ ПРОГРАМУВАННЯМетоди опуклого математичного програмування і умовні нелінійні оцінки
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

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

Цілочисловим (іноді його називають також дискретним) програмуванням називається розділ математичного програмування, що вивчає екстремальні завдання, в яких на шукані змінні накладається умова целочисленности, а область допустимих рішень кінцева. Вивчення цього розділу в курсі "Економіко-математичні методи і прикладні моделі" викликається тим, що величезна кількість економічних завдань носить дискретний, найчастіше цілочисельний характер, що пов'язано, як правило, з фізичною неделимостью багатьох елементів розрахунку: наприклад, не можна побудувати два з половиною заводу, купити півтора автомобіля і т.д. У ряді випадків такі завдання вирішуються звичайними методами, наприклад симплексним методом, з подальшим округленням до цілих чисел. Однак такий підхід виправданий, коли окрема одиниця становить дуже малу частину всього обсягу (наприклад, товарних запасів); в іншому випадку він може внести значні спотворення в дійсно оптимальне рішення. Тому розроблені спеціальні методи вирішення цілочислових задач, серед яких можна виділити два напрямки: методи відсікання (відсікаючих площин) і комбінаторні методи.

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

Розглянемо більш детально один з методів відсікаючих площин, відомий як метод Гоморі. Метод Гомо ри для лінійних задач цілочисельного програмування заснований на понятті конгруентності дійсних чисел. Будь-яке дійсне число можна представити у вигляді суми його цілої і дробової частин: х = [х] + {х}, де квадратні дужки означають цілу частину, а фігурні - дробову. Наприклад, 7,5 = [7,5] + {7,5} = 7 + 0,5. Невід'ємні числа (для простоти ми будемо розглядати тільки їх) називаються конгруентними, якщо рівні їх дробові частини. Якщо позначати конгруентність чисел символом "=", то, наприклад,;; зокрема, всі цілі числа конгруентний нулю, тому умова целочисленности змінної х можна записати:

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

data-override-format="true" data-page-url = "http://stud.com.ua">

Приклад 3.6. Нехай для придбання обладнання, що розміщується на виробничої площі 38 м2, фірма виділяє 20 млн руб. Є одиниці обладнання двох типів: типу А вартістю 5 млн руб., Що вимагає виробничу площу 8 м2 і має продуктивність 7 тис. Од. продукції за зміну, і типу Б - вартістю 2 млн руб., що займає площу 4 м2 і дає за зміну 3 тис. од. продукції. Потрібно розрахувати оптимальний варіант придбання устаткування, що забезпечує максимум продуктивності ділянки

Рішення. Сформулюємо економіко-математичну модель задачі. Нехай х {, х 2 - кількість придбаних машин типу

А і типу Б відповідно. Тоді цільова функція задачі матиме вигляд

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

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

Введемо додаткові змінні х 3, Ж4, за допомогою яких вихідні нерівності перетворяться в рівності:

з яких випливає, що змінні х 3, х 4 можуть приймати тільки невід'ємні цілочисельні значення. Частковий симплексної таблиці на останній ітерації (без урахування целочисленности) наведено в табл. 3.15.

Таблиця 3.15

Базисні змінні

План

data-override-format="true" data-page-url = "http://stud.com.ua">

1

1

0

1

-0,5

7,5

0

1

-2

1,26

29,5

0

0

1

0,25

Звідси видно, що в оптимальному плані х 1 = 1; х 2 = 7,5 і максимум цільової функції дорівнює

Для нецілочисельне змінної х 2 складаємо з наведеної симплексной табл. 3.15 рівняння:

звідки

Так як - ціле число, то цілої повинна бути і права частина останнього рівняння ("" - символ конгруентності):

звідси можна отримати, що

тобто вираз може бути одно 0,5, або 1,5, або 2,5 і т.д. Отже, з'являється додаткове обмеження:, яке шляхом введення додаткової неотрицательной цілочисельний змінної х 5 перетвориться в рівність, так що система обмежень вихідної задачі в канонічному вигляді містить три рівняння:

Повторивши процес вирішення симплексним методом для даної розширеної системи обмежень, отримаємо новий оптимальний план, в якому змінні, що входять в базис, приймають цілі значення:. Таким чином, придбання двох машин типу А і п'яти машин типу Б забезпечує максимум продуктивності ділянки, рівний 29 тис. Од. продукції в зміну. Зауважимо, що якщо б у якості плану був обраний варіант, що отримується в результаті округлення початкового рішення задачі симплексним методом (), то сумарна продуктивність була б дорівнює лише 28 тис. Од. продукції.

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

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

Задача про призначення в загальному вигляді може бути сформульована таким чином. Мається п працівників, які можуть виконувати п робіт, причому використання i -го працівника на j -й роботі, наприклад, приносить дохід з ij.

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

Введемо змінні:

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

(3.22)

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

(3.23)

(3.24)

причому одно або 0, або 1 (так звані булеві змінні) для всіх

Обмеження (3.23) відображають умова того, що за кожним працівником може бути закріплена тільки одна робота, а обмеження (3.24) означають, що для виконання кожної роботи може бути виділений тільки один працівник.

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

Іншим завданням подібного роду є завдання про комівояжера, яка може бути сформульована таким чином. Мається п міст, пронумерованих числами від 1 до п. Комівояжер, виїжджаючи з міста 1, повинен побувати в кожному місті рівно один раз і повернутися у вихідний пункт. Нехай відомі відстані між містами (). Потрібно знайти найкоротший маршрут.

Введемо змінні:

Вимога однократного в'їзду в міста і виїзду з них запишеться у вигляді наступних обмежень:

(3.25)

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

(3.26)

Загальне число таких обмежень одно (n - 1) • (n - 2), і вони, не виключаючи допустимий маршрут, виключають можливість існування подмаршрутов.

Таким чином, завдання про комівояжера полягає в мінімізації цільової функції:

(3.27)

при умовах (3.25), (3.26), де змінні, приймають тільки невід'ємні цілі значення.

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

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >

Cхожі теми

Цілочисельне програмування
ОСНОВИ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Основи лінійного програмування
Державне програмування
МОЖЛИВОСТІ ВИКОРИСТАННЯ ПРОКУРОРОМ І АДВОКАТОМ НЕЙРОЛІНГВІСТИЧНОГО ПРОГРАМУВАННЯ (НЛП)
Метод лінійного програмування, симплекс-метод і лінійні оцінки
Математичне програмування
Стратегічне програмування
СОЦІАЛЬНЕ ПРОГРАМУВАННЯ
Методи опуклого математичного програмування і умовні нелінійні оцінки
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук