Особистий сайт алексея григорьева - симплекс метод
Розглянемо алгоритм сімлекс-методу більш неформально на завданні на максимізацію функції
і наступними обмеженнями:
Перед читанням краще ознайомитися з деякою літературою по темі, так як то наші люди терміни, використовувані в статті, і кроки алгоритму можуть бути незрозумілі.
Рішення задач з початковим базисом
Дане завдання - завдання з початковим базисом, так як всі обмеження в ній - менше або дорівнює. Такі завдання вирішуються простіше, ніж завдання з довільними знаками, тому для початку розглянемо їх рішення. Першою дією переідем від неравентства до рівності і запишемо завдання в канонічній формі. Для цього до кожного нерівності системи додамо змінну, яка буде базовою.
Базисом в системі є змінні, і, вони називаються базисними змінними.
Складемо симплекс-таблицю для цього завдання
Симплекс-таблиця, ітерація 0
У першому стовпці записані змінні, що утворюють базис. Далі записана матриця системи, де передостанній стовпець - вільні члени системи. Останній рядок - це цільова функція.
Тепер отримана таблиця буде поліпшуватися на кожній ітерації алгоритму, поки оптимальне рішення не буде досягнуто.
Для поліпшення вибирається дозволяє стовпець - стовпець, який відповідає найменшому негативному коефіцієнту в z-рядку (для завдання на максимум). Змінна, відповідна дозволяючим стовпцю увійде в базис системи при наступній ітерації. Далі вибирається графічна рядок - для цього серед усіх ненегативний елементів дозволяє стовпця вибирається той, результат ділення на відповідний вільний член якого найменший. Всі ці відносини записані в останньому стовпці симплекс-таблиці. Елемент, відповідний роздільною рядку вийде з базису на наступній ітерації. Дозволяє елемент - елемент, що знаходиться на перетині роздільною рядки і стовпці. Якщо ж в дозвільному стовпці немає невід'ємних елементів, то рішення системи розходиться.
У цьому завданню на першому етапі що дозволяє стовпцем є стовпець зі змінною x2. а роздільної рядком - рядок зі змінною s3.
Далі потрібно заповнити симплекс-таблицю для наступної ітерації. Новий елемент входить в базис, тому коефіцієнт перед відповідною змінною (там, де знаходиться дозволяє елемент) має дорівнювати одиниці, а всі інші коефіцієнти - нулю. Для цього нормалізуємо рядок - розділимо всі її елементи на значення дозволяє елемента. Для отримання нуля у всіх інших рядках (включаючи z-рядок) потрібно значення коефіцієнта при новій базисної змінної помножити на роздільну рядок і поелементно відняти цей результат з поточного рядка.
Симплекс-таблиця, ітерація 1
Для цієї ітерації що дозволяє стовпцем буде стовпець зі змінною x1. а роздільної рядком - рядок зі змінною s2.
Симплекс-таблиця, ітерація 2
Симплекс-таблиця, ітерація 3
Ітерації завершуються, коли в z-рядку всі коефіцієнти стають невід'ємними. На даній ітерації ця умова задовольняється, значить, отримано рішення: x1 = 24, x2 = 16, zmax = 192.
Реалізація на python алгоритму для вирішення завдань з початковим базисом. Показати.
Рішення задач з штучним базисом
Однак на практиці частіше зустрічаються завдання, в обмеженнях яких в нерівностях зустрічаються не тільки знаки менше або дорівнює, а й так само і більше або дорівнює.
Розберемо таку задачу
Запишемо задачу в канонічній формі. Якщо знак нерівності менше або дорівнює, то вводиться змінна буде мати знак «+» в цьому нерівності. Якщо знак «дорівнює», то змінна вводитися не буде. І якщо знак «більше», то змінна буде зі знаком «-».
Для вирішення цього завдання симплекс-методом потрібно ввести змінні, які повинні базувати базис. Одна базисна змінна вже є - це змінна s2. Введемо тимчасові змінні:
У разі, якщо тимчасові змінні присутсвуют в базисі, то вибір роздільної рядка повинен проводиться дещо іншим способом. А саме, потрібно отримати ще один рядок «оцінка», в якій буде зберігатися сума зі знаком мінус всіх коефіцієнтів при тимчасових змінних в даному стовпці. Розглянемо на прикладі.
Симплекс-таблиця, ітерація 0
Рядок «оцінка» буде присутній в таблиці тільки в тому випадку, якщо в базисі присутсвуют тимчасові змінні. На першій ітерації вони присутсвуют, тому дозволяє стовпець вибирається за мінімальним значенням в рядку «оцінка». Дозволяє стовпця буде стовпець змінної x2.
Якщо тимчасові змінні в базисі не беруть участь, то дозволяє стовпець вибирається за найменшим значенням в z-рядку. Робота алгоритму завершиться, коли всі коефіцієнти в z-рядку, крім коефіцієнтів, відповідних тимчасовим змінним, будуть позитивні.