Симплекс метод

- Пропустить и перейти к материалам
- Пропустить и перейти к главной навигации
- Пропустить и перейти к первому столбцу
- Пропустить и перейти ко второму столбцу

# Библиотека учебных материалов

для студентов

Home Примеры решения задач Линейное программирование Симплекс метод

## Симплекс метод

Симплекс метод

Умова задачі: Знайти мінімум функції

1. Графічним способом

2. Симплекс методом.

3. Розв'язавши двоїсту задачу

Розв'язок

1.

Розв’язок

Побудуємо множину допустимих розв'язків системи нерівностей

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

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

Будуємо симплекс таблицю. Як бачимо, розв’язок не допустимий, тому вводимо вільну змінну в базисні

| Св | Х1 | Х2
Х3 | -10 10 | -1 1 | -1 -1
Х4 | -26 24 | -1 4 | -5 -5
Х5 | 80 50 | 5 2 | 3 3
Х6 | 40 10 | 1 -2 | 3 3
Х7 | 4 -6 | -2 -3 | 1 1
Х8 | 8 18 | 1 2 | -1 -1
-F | 0 -360 | 45 9 | 36 36

Розв’язок знову не допустимий. Вводимо змінну у базисні

| Св | Х1 | Х3
Х2 | 10 8 | 1 | -1
Х3 | 24 16 | 4 | -5
Х5 | 50 46 | 2 | 3
Х6 | 10 14 | -2 | 3
Х7 | -6 2 | -3 | 1
Х8 | 18 14 | 2 | -1
-F | -36 -378 | 9 3 | 36 39

Розв’язок допустимий, але не оптимальний, тому робимо ще один крок.

| Св. | Х7 | Х3
Х2 | 8 12 |  |
Х4 | 16 38 |  |
Х5 | 46 24 |  |
Х6 | 14 6 |  |
Х1 | 2 4 |  |
Х8 | 14 16 |  |
-F | -378 -612 | 3 | 39

Розв’язок знову не оптимальний, тому робимо ще один крок

| Св | Х7 | Х6
Х2 | 12 10 |  |
Х4 | 38 34 |  |
Х5 | 24 14 |  |
Х3 | 6 10 |  |
Х1 | 4 10 |  |
Х8 | 16 8 |  |
-F | -612 -810 |  |

Тепер розв’язок є оптимальним. Розв’язок прямої задачі ,

Сформулюємо двоїсту задачу. Для цього приведемо всі нерівності до вигляду

Тепер можемо сформулювати двоїсту задачу

Відповідність між змінними прямої та двоїстою задачі:

Складаємо симплекс таблицю

| Св | a1 | a2 | a3 | a4 | a5 | a6
a7 | -45 9 | 1 | 1 | -5 | -1 | 2 | -1
a8 | -36 -9 | 1 | 5 | -3 | -2 | -1 | 1
- | 0 720 | 10 -6 | 26 10 | -80 -16 | -40 -24 | -4 -36 | -8 8

Бачимо, що розв’язок не допустимий, тому робимо ще один крок

| Св | a1 | a2 | a7 | a4 | a5 | a6
a3 | 9 |  |  |  |  |  |
a8 | -9 |  |  |  |  |  |
- | 720 810 | -6 -10 | 10 -34 | -16 -10 | -24 -10 | -36 -14 | -8 -8

Розв’язок двоїстою задачі . Оптимальне значення цільової функції

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