Лінійного програмування

Надана система з m лінійних рівнянь і n невідомим (х₁, х₂,…x_n):

A₁₁ × X₁ + A₁₂ × X₂ +.. + A_1n × X_n = B₁

A₂₁ × X₁ + A₂₂ × X₂ +.. + A_2n × X_n = B₂

- - - - - - - - - - - - - - - - - - - - - - - - - - - -(1)

A_m1 × X₁ + A_m2 × X₂ +... + A_mn × X_n = B_m

і деяка лінійна цільова функція відносно цих же n невідомих:

Zmin (max) = C₁ × X₁, + C₂ × X₂ +... C_n × X_n (2)

Потрібно знайти таке позитивне рішення системи (1), тобто Х₁ > 0,

Х₂ > 0,..., Х_n > 0, при якому лінійна форма (2) перетворювалася б в мінімум (максимум). Таку форму запису називають канонічною.

Скорочено, у математичному вигляді, основну задачу лінійного програмування (ЛП) записують так:

знайти:

Z = →extr

за наступних обмежень:

для i = 1,2,…m; j = 1,2,…n

та невід’ємності змінних:

X_j ≥ 0.

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

Від’ємне значення поголів’я худоби не мало б економічного змісту. Тому всі невідомі, що входять в задачу, повинні бути невід’ємними. Існує нескінченна множина рішень системи (1). Будь - яке невід’ємне рішення системи (1) називають допустимим, а допустиме рішення, що перетворює лінійну форму (2) в максимум (або мінімум), називають оптимальним рішенням. Частіше всього в задачах не обов’язково повинні бути використані всі ресурси. В цих випадках система обмежень (1) буде задана у вигляді нерівностей виду (3) або (4).

A₁₁ × X₁ + A₁₂ × X₂ +... + A_1n × X_n ≤ B₁

A₂₁ × X₁ + A₂₂ × X₂ +... + A_2n × X_n ≤ B₂

- - - - - - - - - - - - - - - - - - - - - - - - -(3)

A_m1 × X₁ + A_m2 × X₂ +... + A_mn × X_n ≤ B_m

A₁₁ × X₁ + A₁₂ × X₂ +.. + A_1n × X_n ≤ B₁

A₂₁ × X₁ + A₂₂ × X₂ +... + A_2n × X_n ≥ B₂

- - - - - - - - - - - - - - - - - - - - - - - - - - -(4)

A_m1 × X₁ + A_m2 × X₂ +.. + A_mn × X_n ≥ B_m

Подібні системи намагаються привести до канонічного вигляду, тобто до вигляду (1). Для цього до лівої частини нерівностей додаються в системі (3) деякі додатні невідомі, а в системі (4) - від’ємні. Обмеження можуть бути задані також у вигляді змішаної системи нерівностей, які містять нерівності і виду (1) і виду (3) і виду (4). Рішення задач лінійного програмування ведеться за певними правилами, що називаються алгоритмами рішень. Алгоритми діляться на дві групи. До першої групи відносяться універсальні алгоритми, за допомогою яких можуть бути вирішені всі лінійного програмування. Найбільш розповсюдженим із них є симплексний метод [1,2,3]. Симплекс - методів є два: прямий симплекс - метод застосовується щодо рішення моделей типу (3), симплекс - метод зі штучним базисом застосовується щодо рішення моделей типу (4).

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

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

Використання симплекс - методу (СМ) при знаходженні оптимальних рішень задач ЛП вручну, при загальній кількості змінних більше 10 долготривалі, трудомісткі з вірогідною часткою помилок. Тому виникає реальна необхідність при рішенні задач ЛП застосування сучасного програмного забезпечення та обчислювальної техники (ПЕОМ).

У даний час програмна реалізація СМ широко представлена в готових пакетах прикладних програм, які успішно використовуються для рішення задач ЛП з використанням ПЕОМ.