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

↑

⇐ ПредыдущаяСтр 15 из 17Следующая ⇒

Лекція 13

План:

1. Суть симплекс-методу.

2. Симплекс-метод в загальному вигляді.

3. Симплекс-таблиці.

Короткий зміст лекції:

Розглянемо задачу лінійного програмування з обмеженням в формі рівнянь.

Дана система:

(1)

m лінійних рівнянь з n невідомими та лінійна форма:

.

(2)

Серед невід’ємних розв’язків системи (1) необхідно знайти такий, який мінімізує форму f (2).

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

Припустимо, для визначеності, що невідомі, які виражені через інші – це .

Отже, система зведена до виду:

(3)

Невідомі  називаються базисними, а весь набір , який позначимо буквою Б – базисом, інші невідомі називаються небазисними або вільними.

Підставляючи в форму f замість базисних невідомих їх вирази (3), записуємо f у вигляді:

.

Надаємо вільним невідомим нульових значень: . Тоді . Одержуємо допустимий розв’язок системи: . Він називається базисним розв’язком, який відповідає базису .

Для базисного розв’язку значення форми f дорівнює .

Розв’язування задачі за симплекс-методом розпадається на ряд кроків. Кожний з кроків полягає в тому, що від даного базису Б переходимо до іншого базису  так, щоб значення  зменшилося або, в крайньому випадку, не збільшилося: .

Новий базис  одержується із старого Б вилученням одного з невідомих і введенням замість нього іншого (з числа попередніх небазисниx). Заміна базису веде до перебудови системи (3). Після декількох кроків одержуємо базис , для якого  є шуканий мінімум форми f, а відповідний базисний розв’язок є оптимальним, або з’ясовуємо, що задача розв’язку не має.

Порядок роботи за симплекс-методом полягає в наступному.

1. Зводимо систему обмежень до виду, розв’язаному відносно будь-якого базису.

2. Виражаємо форму f через небазисні невідомі. Якщо в одержаному виразі всі коефіцієнти при небазисних невідомих невід’ємні, то базисний розв’язок є оптимальним – задача розв’язана.

3. Нехай серед коефіцієнтів, заданих в попередньому пункті, є від’ємні. Беремо будь-який з них – нехай, наприклад, це буде коефіцієнт при . Продивляємося стовпчик з коефіцієнтів при  в правих частинах системи обмежень. Якщо всі числа цього стовпчика невід’ємні, то min f = –∞ – задача розв’язків не має.

4. Нехай в стовпці коефіцієнтів, згаданих в пункті 3, є від’ємні числа. Для кожного з таких чисел –  (так позначаємо коефіцієнт при  у виразі для базисного невідомого ) знаходимо відношення  ( – вільний член у виразі для ). Серед цих відношень вибираємо найменше; припустимо, що воно відповідає значенню k = i. Елемент  називається розв’язувальним.

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

Далі повертаємося до виконання пункту 2.

Всі труднощі описаної процедури зосереджені в пунктах 1, 2, 5.

Примітка. В основі одного кроку процесу обчислень за симплекс-методом лежить вибір від’ємного коефіцієнту при . Якщо таких коефіцієнтів не один, а декілька, то можна вибирати будь-який з них. Ця обставина вносить деякий елемент свавілля в розрахунки, оскільки одержується декілька можливостей для вибору розв’язувального елементу . Якщо обидва вибори зроблені, то далі процес обчислень продовжується однозначно – до закінчення даного кроку.

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

Нехай канонічна задача максимізації функції f зведена до виду:

(1)

та системи обмежень:

(2)

Даним (1) і (2) відповідає наступна таблиця, в яку внесені коефіцієнти при невідомих і вільні члени з (1) і (2).

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности