Дебела І. М. Економіко-математичне моделювання

Дебела І.М. Економіко-математичне моделювання 3.4. Симплексний метод розв’язування задач лінійного програмування Симплексний метод – це ітераційний процес, що починається з одного рішення – вершини багатогранника розв’язків і в пошуку найкращого варіанту здійснює перебір за усіма кутовими точками області можливих значень до тих пір, поки не буде знайдено оптимального рішення. Ідея цього методу полягає в здійсненні спрямованого перебору допустимих планів задачі,причому, на кожному кроці здійснюється перехід від одного опорного плану до наступного, який за критерієм оптимальності був би не гіршим за попередній. Значення цільової функції при цьому змінюється в заданому напрямку: збільшується (для задачі на максимум), зменшується (для задачі на мінімум). Ітераційність процесу розв’язання задачі симплексним методом проявляєтьсяв тому, що однотипні обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що такого не існує. Отже, симплекний метод — це ітераційна обчислювальна процедура, в основу якої покладено принцип послідовнї оптимізації значень змінних, з метою наближення цільової фукції до її екстремального значення, шляхом переходу від одного опорного плану задачі лінойного програмування до іншого. Застосуваня симплекс-метода можливе лише у випадку коли задача лінійного програмування записана в канонічному вигляді (пункт.3.1, (3.1. – 3.3.)). Алгоритм розв’язування задачі лінійного програмування симплексним методом: 1. Визначення початкового опорного плану задачі лінійного програмування. 2. Побудова симплексної таблиці. 3. Перевірка опорного плану на оптимальність за допомогою оцінок Δj = Zj - Cj. Якшо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок Δj = Zj - Cj не задовольняє умову оптимальності, то переходять до нового опрного плану або з’ясовують що оптимального плану не існує. 4. Перехід до нового опорного плану виконується визначенням розв’язувального елемента та розрахунком нової симплексної таблиці. 5. Повторення дій починоючи з п.3. Розглянемо кожний крок алгоритму докладніше. 1. Визначення початкового опорного плану Визначення першого опорного лану починають із запису задачі у канонічній формі, тобто коли усі обмеження задачі є рівняннями із невід’ємними правими частинами. Якщо в умові задачі присутні обмеження – нерівності, то перетворення їх на рівняння відбувається за допомогою додаткових змінних, які вводяться до лівої частини обмеження типу «≤» із знаком «+», а до обмеження типу «≥» із знаком «-». У цільовій фукції додаткові змінні маєть коефіцієнт «0». Розглянемо задачу лінійного програмування (3.6 – 3.8), . і запишемо її в канонічній формі: . Після зведення задачі до канонічного виду її доцільно записати у векторному вигляді. ^ Опорний план задачі утворюють m одиничних лінійно незалежних векторів, які утворюють базис m-вимірного простору (де m- кількість обмежень у задачі лінійного програмування) Наприклад, маємо задачу в канонічній формі (3.16). Допустимо, що система рівнянь містить перші m одиничних лінійно незалежних векторів. Запишемо систему обмежень у векторній формі. (3.16) Система обмежень (3.15) у векторній формі матиме вигляд: , (3.17) де , ,..., , , …, , , — лінійно незалежні одиничні вектори m-вимірного простору, що утворюють одиничну матрицю і становлять базис цього простору. ^ Кількість одиничних лінійно незалежних векторів повинна дорівнювати кількості рівнянь системи обмежень задачі лінійного програмування. Якщо ця умова не виконується, тобто у системі обмежень немає необхідної кількості одиничних лінійно незалежних векторів, то для побудови першого опорного плану застосовують метод штучного базису. Визначені одиничні лінійно незалежні вектори утворюють базис, і змінні, що відповідають цим векторам називаються базисними, всі решта змінних – вільні. Вільні змінні задачі прирівнюють до нуля та з кожного обмеження задачі визначають значення базисних змінних. Таким чином визначається початковий опорний план задачі лінійного програмування. Тому в системі (3.15) базисними змінними будуть , а інші змінні — вільні. Прирівняємо всі вільні змінні до нуля, тобто . Оскільки , а вектори — одиничні, то отримаємо один із розв’язків системи обмежень (3.16): (3.18) тобто опорний план. 2. Побудова симплексної таблиці Обчислювальний процес та перевірку опорного плану на оптимальність подають у симплексній таблиці. Базис Сбаз. План c1 c2 ... cn θ x1 x2 … xn x1 c1 b1 1 0 … …a1n x2 c2 b2 0 1 … …a2n 0 0 … … xm cm bm 0 0 … …amn Δj=Zj-Cj Z0 0 0 … … У першому стовбчику таблиці – ^ Базис – записуються базисні змінні опорного плану, у тій послідовності, в якій врни розміщуються в системі обмежень задачі. Наступний стовбчик - Сбаз. – коефіцієнти при базисних змінних у цільовій фукції задачі. У третьому стовбчику - План – записують значення базисних змінних опорного плану задачі і відповідне значення цільової фукції опорного плану (Z0). У решті стовбчиків, кількість яких відповідає кількості змінних задачі, записують відповідні коефіцієнти обмежень задачі лінійного програмування (вектори Aj, j=1:n). Останні рядок і стовбчик таблиці є оцінковими – в них записують розраховані оцінки. 3. ^ Перевірка опорного плану на оптимальність за допомогою оцінок Δj = Zj - Cj відбувається у відповідності до теореми: Теорема (ознака оптимальності опорного плану). Опорний план X* = (x1*;x2*;…xn*), задачі лінійного програмування є оптимальним, якщо для всіх j ( j=1:n) виконується умова Δj=Zj-Cj ≥ 0 - для задачі на max Δj=Zj-Cj ≤ - для задачі на min Якщо для побудови опорного плану було використано метод штучного базису, необхідною умовою оптимальності є вимога виведення з базису штучних змінних , або рівність їх нулеві. Значення оцінок Δj=Zj-Cj визначають заформулою Δj=Zj-Cj= ; ( j=1:n), або безпосуредньо з симплексної таблиці, як скалярний добуток векторів стовбчиків Сбаз і xj мінус відповідний коефіцієнт Сj . Розраховані оцінки записують в останній рядок таблиці, який є оцінковим. 4^ . Перехід до нового опорного плану виконується заміною базису, тобто виключенням з базису деякої змінної і введення замість неї нової з числа вільних змінних задачію. Змінна, що вводиться в базис, відповідає тій оцінці Δj=Zj-Cj, що не задавольняє умову оптимальності. Якщо таких оцінок декілька, серед них вибирають найбільшу за абсолютною величиною і відповідну їй змінну вводять в новий базис. Стовбчик в якому знаходиться нова змінна базису називається напрямним. Для визначення змінної, яка підлягає виключенню з базиса, знаходять оцінки θ = , де bі – елементи стовбчика План симплексної таблиці, aik – додатні елементи напрямного стовбчика. Серед усіх обчислених оцінок θ вибирають найменшу, змінну, що знаходиться у одному рядку із min θ в стовбчику Базис виключають з базису. Відповідний рядок (із min θ) симплексної таблиці називаєтся напрямним. Перетином напрямного рядка і напрямного стовбчика є число aрk , яке називають розв’язувальним елементом. За допомогою розв’язувального елемента і метода Жордана –Гаусса розраховують нову сиплексну таблицю. Далі ітераційний процес повторюють доти, поки не буде знайдено оптимальний план ЗЛП, або визначено, що такого не існує. Розв’язуючи ЗЛП симплексним методом можна отримати такі результати: 1). У оцінковому рядку оцінка Δj=Zj-Cj=0 відповідає вільній (небазисній) змінній, тоді ЗЛП має альтернативний оптимальний план. Отримати його можна, втбравши розв’язувальний елемент у зазначеному стовбчику таблиці і виконати ще один крок сисплекс-методу. 2). При переході від одного опорного плану до іншого в напрямному стовбчику відсутні додатні елементи, тобто неможливо визначити розв’язувальний елемент, це означає, що цільова фукція ЗЛП необмежена і оптимальних планів не існує. 3). У стовбчику θ симплексної таблиці містяться два або декілька однакових найменших значення θі (не можливо визначити напрямний рядок), тоді новий опорний план буде виродженим (одна або декілька базисних змінних будуть мати нульове значення). Вироджені плани можуть привести до циклічності алгоритму, тобто до багаторазового повторення процесу обчислення, що унеможливлює отримання оптимального плану. У такому випадку, для визначення напрямного рядка застосовують метод Креко []. Сутність методу Креко – елементи рядків що містять однакові найменші значення θі ділять на елементи напрямного стовбчика, результати ділення заносять у рядки додаткової таблиці. За напрямний обирається той рядок у якому раніше зустрінеться найменша частка при перегляді таблиці зліва направо по стовбцях. Наприклад, таблиця що містьть два однакових найменших значення θі = 2, має вигляд: Базис План x1 x2 х3 x 4 x 5 x 6 x 7 θ x1 4 2 3 6 1 0 0 2 2 x2 8 4 8 1 0 1 0 4 2 х3 15 5 12 -1 1 0 1 5 3 Припустимо, що напрямним стовбчиком буде стовбчик x 7 , тоді розв’язувальним елементом може бути 2, 4, так як min θі =2. застосувавши метод Креко отримуємо допоміжну таблицю: № стовбця 1 2 3 4 5 6 7 8 Базис План x1 x2 х3 x 4 x 5 x 6 x 7 x1 2 1 1,5 3 0,5 0 0 1 x2 2 1 2 0,25 0 0,25 0 1 Послідовно порівнюючи зліва направо отримані частки по стовбцях бачимо, що перші два стовбчика мають однакове значення часток. Третій стовбчик містить найменшу частку 1,5 у першому рядку, відповідно цей рядок і буде напрямним. Продемонструємо застосування алгебраїчного симплекс-методу на прикладі. Приклад 3.3. Продукція чотирьох видів А, В, С і D проходить послідовну обробку на двох видах виробничого обладнання. Норми часу на обробку одиниці продукції кожного виду та ціна одиниці продукції наведені в таблиці3.2.

Схожі:

	Методичні рекомендації до виконання контрольних робіт з дисципліни „економіко-математичне Методичні рекомендації до виконання контрольних робіт з дисципліни «Економіко-математичне моделювання» для студентів усіх напрямів...		Концептуальні аспекти математичного моделювання економіки Тому математичне моделювання економічних явищ та процесів, шляхом послідовного встановлення логічних причинно-наслідкових зв’язків,...
	Питання з дисципліни «Методи розпізнавання та ідентифікації автомобільних... Математичне моделювання як основа дискримінантного аналізу в теорії розпізнавання образів		Математичні методи І моделі розв’язку економічних задач Тому математичне моделювання економічних явищ та процесів, шляхом послідовного встановлення логічних причинно-наслідкових зв’язків,...
	Сутність, принципи, функції та цілі інвестиційного менеджменту Планування потреби в інвестиційних ресурсах за допомогою нормативного, розрахунково-аналітичного, оптимізаційного, економіко-статистичного...		Лекція №2 «математичне моделювання як метод наукового пізнання економічних явищ І процесів» Та апостеріорної інформації. Статистична база економетричних моделей. Змінні та рівняння в економетричних моделях. Макро- І мікроекономічні...
	IX. Економіко-правовий механізм (legal basis for economic mechanism) у галузі земельних відносин Поняття та загальна характеристика економіко-правового механізму у галузі земельних відносин		Міністерство внутрішніх справ україни національна академія внутрішніх... Безрутченко С. М. канд екон наук, професор кафедри економіко-правових дисциплін
	Група екк-42с. Моделювання		Захист елементів інформаційної системи Ресурсні (програмно-апаратні) – елементи, які реалізують функціональні можливості іс (апаратне, математичне, І програмне забезпечення,...