Загальна задача лінійного програмування

Кафедра економічної кібернетики

Та інформаційних систем

Лабораторна робота №1

З дисципліни «Інформатика»

на тему:

«Текстовий редактор MS Word

Введення та редагування тексту»

Виконала:

студентка 11-з групи

факультету економіки

та підприємництва

Шевчук М. В.

Перевірив:

Гринчак М. В.

 

Умань 2015

Симплексний метод розв’язування задач лінійного програмування

 

Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості змінних необхідно застосовувати інший метод. З властивостей розв’язків задачі лінійного програмування відомо: оптимальний розв’язок задачі має знаходитися в одній з кутових точок багатогранника допустимих розв’язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (допустимих планів задачі, які ще називають опорними). Порівняння вершин багатогранника можна здійснити тільки після відшукання якоїсь однієї з них, тобто знайшовши початковий опорний план. Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачіз n векторів A1, A2, … An.

Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ[1]. Тому необхідне використання методу, який уможливлював би скорочення кількості обчислень. В 1949 році такий метод був запропонований американським вченим Дж. Данцигом – так званим симплексний метод.

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

Процес розв’язання задачі симплексним методом має ітераційний характер: ітерації[2] повторюються в певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує.

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

Загальна задача лінійного програмування

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

Z_ext=c₁x₁+c₂x₂+… + c_nx_n

за умов:

a₁₁x₁+a₁₂x₂+…+a_1nx_n {≤,=,≥}b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n {≤,=,≥}b₂

a_m1x₁+a_m2x₂+…+a_mnx_n {≤,=,≥}b_m

x₁≥0, x₂≥0,…x_n≥0.

Отже, потрібно знайти значення змінних x₁, x₂, …, x_n, які задовольняють умови, і цільова функція (Z_ext) набуває екстремального (максимального чи мінімального) значення.

Для загальної задачі лінійного програмування використовуються такі поняття.

Вектор Х = (x₁, x₂,…, x_n), координати якого задовольняють систему обмежень та умови невід’ємності змінних, називається допустимим розв’язанням задачі лінійного програмування.

Допустимий план Х = (x₁, x₂,…,x_n), називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи у вигляді рівностей, а також обмеження щодо невід’ємності змінних.

Опорний план Х = (x₁,x₂,…,x_n), називається невиродженим, якщо він містить точно m додатних змінних, інакше він вироджений.

Опорний план X^*= (x₁^*,x₂^*,…,x_n^*), за якого цільова функція досягає максимального (чи мінімального) значення, називається оптимальним розв’язком задачі лінійного програмування.

Уперше постановка задачі лінійного програмування та один із методів її розв’язання були запропоновані Л.В. Канторовичем у роботі «Математические методы огранизации планирования производства» у 1939 році Дж. Данціг розробив симплекс-метод – один із основних методів розв’язування задач лінійного програмування. З тих пір теорія лінійного програмування бурхливо розвивалася і нині носить цілісний, в основному, закінчений характер.

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

[1] з широким використанням ЕОМ – Електроноо-обчислювальної машини.

[2] ітерації – однотипні обчислювальні процедури.