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

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

Розглянемо задачу лінійного програмування виду:

при обмеженнях:

Дану задачу запишемо у векторній формі:

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

Означення 1: Опорний план є оптимальним, якщо усі .

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

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

Весь хід роботи за симплекс методом доцільно оформляти у вигляді таблиці наступного виду:

Симплекс таблиця

де значення дорівнює скалярному добутку вектора на вектор :

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

  1. Усі .
  2. Існує , для якого і для кожного такого  симплекс таблиці, міститься принаймні одне додатнє число  ().
  3. Існує , для якого  і всі відповідні цьому індексом величини .

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

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

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

Розв'язок задачі лінійного програмування за симплекс методом — приклад:

Для виготовлення товару A, B і C підприємство використовує три види сировини I, II, III. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару AB і C а також загальна кількість сировини наведені в наступній таблиці:

Норми витрат сировини на виробництво одного товару

Складемо такий план випуску даної продукції, щоб прибуток від її реалізації був максимальним.

Позначемо через  — кількість товару А;  — кількість товару В;  — кількість товару С. Тоді математична модель даної задачі буде наступна: знайти максимум функції при обмеженнях

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

Запишемо дану задачу у векторній формі і побудуємо першу симплекс таблицю:

Побудова першого опрного плану задачі лінійного програмування

де елементи  та  четвертого, оцінкового, рядка, обчислюються за формулами (3), (4) відповідно.

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

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

Далі, визначаємо на місце якого вектора базису вводимо . Для цього визначаємо . Таким чином розв'язуючим буде елемент , який вказує на те, що виводити з базису необхідно вектор .

Наступним кроком буде побудова другої симплекс таблиці і визначення всіх її коефіцієнтів згідно нового базису:

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

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

Побудова третього опрного плану задачі лінійного програмування

Блок-схема алгоритму знаходження розв'язку задачі лінійного програмування за симплекс методом

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар