• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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

п

2 аух7 < Ьі , і = 1 т1:

7=1

п -

2 ауху > Ьі, і = т1 +1,т2 :

7=1

п -

ауху = Ьі , і = т2 +1, т:

7=1 _

ху > 0, у = 1, п:

ху - цілі числа, у = 1, п1: п1 < п,

де с7, а7, Ьі - задані дійсні числа.

Класичним прикладом управлінської задачі, яка описується цілочисловою моделлю, є задача про "товарний портфель".

Задача про "товарний портфель"

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

елементи матриці А = (ау)тхп, де означають /-ту характеристику

предмета у-го найменування. Задані також елементи вектора С = (су) п,

де Cj - корисність від перевезення предмета j-ro найменування. Треба так організувати перевезення товару, щоб максимізувати загальну корисність рейсу. Нехай Xj - кількість предметів j-ro найменування,

j = 1, n . Тоді математична модель задачі має такий вигляд:

n

z =2CjXj -" max; j=1

2 ajXj < bi, i = 1, m;

j=i _

< Xj > 0, j = 1, n ; Xj - цілі числа, j = 1, n.

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

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

Задача "комівояжера"

Існує n міст, що пов'язані між собою транспортною мережею. Відомі елементи матриці C = (Cj)nyn, де Cj

- відстані від z'-ro до j-ro міста. Виїхавши з одного міста, "комівояжер" повинен побувати в кожному місті тільки один раз і повернутися в те місто, з якого почав рухатися. Потрібно відшукати такий замкнений маршрут, що проходить через кожне місто лише один раз і довжина якого мінімальна.

Вводяться змінні Xj = {0;1}, де Xj набувають значення 1, якщо

комівояжер переїжджає від 7-го до j-ro міста, і 0 - у протилежному випадку.

Потрібно мінімізувати загальну відстань

n n

z = 2 2CjXj, за умов одноразового виїзду та в'їзду для всіх міст 2 Xij =1 (j =1 ^ i * j);

2 Xij =1 (i =1 ^ i * j).

j=1

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

Ui - Uj + nXj < n -1 (i = 1, n, j = 1, n, І Ф j),

де ui, Uj - невід'ємні цілочислові змінні, які в процесі розв'язання

задачі набуватимуть значень порядкових номерів міст за оптимальним маршрутом прямування комівояжера.

У результаті математична модель має такий вигляд

n n

z = Т.Т.СуХу -> min, i ф j;

Z xij =1 (j =1, n, i * j);

i=1

£ Xj = 1 (i = 1, n, i Ф j);

Xj = {0; 1} (i = 1, n, j = 1, n);

Ui - Uj + nXjj < n -1 (i = 1, n, j = 1, n, i Ф j).

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

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

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

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

- Комбінаторні методи. Ці методи базуються на ідеї цілеспрямованого перебирання всіх допустимих цілочислових розв'язків з відсіюванням множин неперспективних допустимих розв'язків.

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

Читайте також:

1. А) Задачі, що розкривають зміст дій
2. Алгебраїчне та інсерційне програмування
3. Алгоритм розв’язання задачі
4. Алгоритм розв’язання задачі
5. Алгоритм розв’язання розподільної задачі
6. Алгоритм розв’язування задачі
7. Алгоритм розв’язування задачі
8. Алгоритм розв’язування задачі
9. Алгоритм розв’язування задачі
10. Алгоритм розв’язування задачі
11. Алгоритм розв’язування задачі
12. Алгоритм розв’язування задачі оптимізації в Excel

Переглядів: 788