2. 3.2 Поняття симплексного методу (см)

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

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

Вчені розглядали більш раціональне використання ідеї про перебір кутових точок: якщо відомо будь-яку кутову точку (опорний план) і значення цільової функції в ній, то всі кутові точки, в яких цільова функція набуває гірших, тобто більших, значень (розглядає ЗЛП на мінімум цільової функції), свідомо не потрібні. Тому природно знайти спосіб переходу від одної кутової точки (опорного плану) до кращої, від неї – до ще кращої і т.д. У цьому й полягає суть симплексного методу (СМ). Таким чином, можна ввести таке його поняття; CM – це обчислювальна схема, що дає змогу за наявності опорного плану спрямовано перебирати опорні плани доти, доки не буде знайдено оптимальний план або встановлено, що ЗЛП не має розв’язку.

У зв’язку з цим поняттям, природно, виникають чотири етапи процедури CM:

побудова початкового опорного плану,

оцінка оптимальності плану;

оцінка розв’язності ЗЛП;

перехід від одного опорного плану до кращого.

Назву методу "симплексний" запропонував американський учений Д. Данціг у 1947 p. Ця назва виникла з геометричної інтерпретації перших окремих задач, до яких було застосовано метод, і не відповідає його суті. "Симплекс" – грецьке слово, що перекладається як "найпростіший", – назва певного опуклого многокутника у вищій математиці.

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

Першовідкривач лінійного програмування – радянський учений Я.В. Канторович. Розглядаючи питання планування роботи агрегатів фанерної фабрики в 1939 p., він математично розв’язав кілька задач: про найкраще завантаження машин; розкроювання матеріалу з найменшими відходами; розподіл вантажів по кількох видах транспорту тощо. При цьому він розробив універсальний метод розв'язування таких задач, а також різні алгоритми, що його реалізують.

Побудова початкового опорного плану.

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

Отже, розглядається ЗЛП, у якій серед відповідних векторів є ортонормований базис.

Опишемо побудову початкового опорного плану. Нехай ортонормований базис утворюють перші т векторів. Тоді ЗЛП має вигляд

; (2.42)

(2.43)

Випишемо відповідні вектори:

; ; ... ; ; ; ...; .

Означення 2.11. Змінні, що відповідають векторам, які утворюють ортонормований базис, називаються базисними.

Змінні, що відповідають векторам, які не входять до базису, називаються вільними.

Якщо вектори А₁,А₂, ... ,А_mутворюють базис, то змінні х₁, х₂, ..., х_m –базисні, а змінні х_m₊₁, ..., x_п – вільні. За означенням невиродженого опорного плану, базисні змінні мають бути додатними, а вільні – нульовими. Прирівняємо в основній системі обмежень змінні х_m₊₁, ..., x_п до нуля, тоді базисні змінні набудуть значень х₁= b₁, х₂= b₂, ..., х_m = b_m. Отже, отримано початковий опор ний план

Розглянемо окремий випадок ЗЛП, заданої не в канонічному вигляді, яка після зведення до канонічного вигляду задовольняє вказану умову. Це задача раціонального використання ресурсів:

; (2.45)