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

магниевый скраб beletage

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

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

n

z = ^ CjXj ^ max(min);

j=1

Е a,jxj ^ bi , i = 1 m1;

j=1

E ajXj > b,,

J=1

i = m1 +1, m2 ;

2 ayXj = bi, i = m2 +1, m;

J=1                 

Xj > 0, j = 1, n;

Xj - цілі числа, j = 1, n1;

aij , bi

n1 < n,

де c,

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

Задача про «товарний портфель». Припустімо, що треба перевез-ти предмети різних найменувань, причому кількість предметів одногонайменування може повторюватися. Задано обмеження щодо кожноїхарактеристики предметів (вага, об'єм тощо) вектором B = (b,)m таелементи матриці A = (aу)mxn, де a, означають і-ту характеристикупредмета J-ro найменування. Задані також елементи вектора C = (c,) n,

задані дійсні числа.

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

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

n

z =2CjXj ^ max;j=1

2 aijx j ^ b i, i = 1, m;j=1         

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

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

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

Задача «комівояжера». Існує n міст, що пов'язані між собоютранспортною мережею. Відомі елементи матриці C = (c ^)nxn, де c^

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

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

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

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

nn

Z = TTCijXij,i=1 j=1

за умов одноразового виїзду та в'їзду для всіх міст

llXij =1 (j =1 n, i * j);

i=1

XXij = 1           (i = 1, n, i Ф j).

j=1

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

U - Uj + ПХу < n -1 (i = 1, n, j = 1, n, І Ф j),

де u, Uj — невід'ємні цілочислові змінні, які в процесі розв'язаннязадачі набуватимуть значень порядкових номерів міст за оптимальниммаршрутом прямування комівояжера.

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

n n

z = 2 ZCijXij ^ min, i ф j;i=1 j=1

ZXij = 1 (j = 1, n, І * j);

i=1

lLxij =1 (i =1, n, i * j);

- j=1

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

ut - Uj + nXj < n -1 (i = 1, n, j = 1, n, i ^ j).

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

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

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

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

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

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

Висновки

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

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

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

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

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

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

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

Питання для самоконтролю та обговорення

Що таке модель? Які причини використання моделей для при-йняття управлінських рішень? Для виконання яких управлінськихзавдань доцільно використовувати економіко-математичні моделі?

Які основні етапи економіко-математичного моделювання мож-на виділити? Дайте економічне обґрунтування економіко-матема-тичних моделей.

Який вигляд має загальна задача математичного програмуван-ня? Наведіть алгоритми графічного методу і симплекс-методурозв'язування задач лінійного програмування.

Як використання економіко-математичних моделей впливає навибір управлінських рішень? Чому?

Опишіть економічні постановки та математичні моделі задачі про«товарний портфель» і задачі «комівояжера». У чому їх особливості?

Задачі

1. Підприємство випускає продукцію трьох видів: P1, P2, P3 і викорис-товує сировину двох типів: S1 та S1. Норми витрат сировини характеризу-( 2 3 ї

де кожний елемент ait (i = 1, 2, 3; j = 1, 2)

ються матрицею A =

показує, скільки одиниць сировини j-ro типу витрачається на вироб-ництво одиниці продукції i-го виду. План випуску продукції заданоматрицею-рядком C = (100 80 130), вартість одиниці кожного типу

сировини (грн) — матрицею-стовпцем B = | 30 І. Визначити витрати

50

сировини для планового випуску продукції та загальну вартість цієїсировини.

2. Взуттєва фабрика спеціалізується на випуску виробів трьох ви-дів: туфель, кросівок та чобіт; при цьому використовується сировинатрьох типів: S1, S2, S3. Норма витрати кожної з них на одну пару взуттяй обсяг витрати сировини на 1 добу задано в таблиці.

Вид

Норма витрат сировини иа одну пару, грн

Витрати сировини

сировини

Туфлі

Кросівки

Чоботи

на 1 добу, грн

S1

5

3

4

2700

S2

2

1

1

900

S3

3

2

2

1600

Скласти економіко-математичну модель і знайти щоденний обсягвипуску кожного виду взуття.

3. Маємо трьох постачальників і чотири організації — споживачі.Потужність постачальників, попит споживачів, а також витрати на пере-везення одиниці вантажу для кожної пари «постачальник — споживач»наведено в таблиці. Треба так організувати перевезення вантажу, щобпід час нього отримати мінімальні загальні витрати й задовольнити всіхпостачальників та споживачів (скласти економіко-математичну модель).

 

 

Потреба споживачів

Постачальник

Запаспостачальників

1

2

3

4

 

 

20

110

40

110

1

60

1

2

5

3

2

120

1

6

5

2

3

100

6

3

7

4

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

Вид апарата

Продуктивність роботи ліній,шт. за добу

Витрати на роботу ліній,грн за добу

План, шт.

 

1

2

1

2

 

А

4

3

400

300

50

В

6

5

100

200

40

с

8

2

300

400

50

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

5. Суміш складається з трьох хімічних речовин A1, A2, A3. Відомаконцентрація кожної з цих речовин в одиниці продуктів P1 і P2, а та-кож вартість одиниці кожного продукту. Необхідно скласти суміш зпродуктів P1 та P2, щоб вартість суміші була мінімальною, якщо ві-домий мінімальний вміст хімічних речовин у суміші. Вихідні дані за-значено в таблиці. Побудувати математичну модель, розв'язати задачуграфічно та симплекс-методом.

Продукт

Вартість одиниці продукту

Концентрація речовини

А1

А2

А3

P1

130

8

5

3

Pi

80

2

6

10

Мінімальний вміст

16

30

30

6. Підприємство виробляє три види продукції: А, В і С, використо-вуючи для цього три види ресурсів 1, 2 і 3. Норми витрат ресурсів наодиницю кожної продукції (в грн) наведено в таблиці.

Ресурс

Норма витрат на одиницю продукції,за видами продукції

Запас ресурсу

А

В

с

1

4

5

8

200

2

5

4

4

250

3

3

3

7

220

Відома ціна одиниці продукції кожного виду: для продукції A —10 грн, для B — 8, для C — 9 грн. Сформувати математичну модельданої задачі, за допомогою симплекс-методу визначити оптимальнийплан виробництва продукції кожного виду в умовах обмеженості ре-сурсів, який дає підприємству найбільший дохід.

7. Для закупівлі верстатів, розміщених на виробничій площі 38 м2,компанія виділяє 20 млн грн. Маємо верстати двох типів: типу А —вартістю 5 млн грн, які потребують виробничої площі 8 м2 і маютьпродуктивність 7 тис. од. продукції за зміну, і типу Б — вартістю2 млн грн, котрі займають площу 4 м2 і дають за зміну 3 тис. од. про-дукції. Скласти математичну модель і розрахувати оптимальний варі-ант закупівлі верстатів, який дає максимальну продуктивність ділянки.