- •1. Загальні відомості
- •2. Зміст дисципліни
- •3. Запитання для підготовки до іспиту
- •4. Варіанти лабораторних робіт та порядок їх виконання
- •4.1. Лабораторна робота 1 Графічне розв’язання задачі лінійного програмування
- •4.2. Лабораторна робота 2 Симплекс-метод
- •4.3. Лабораторна робота 3 Розв’язання задачі лінійного програмування з використанням методу штучного базису
- •4.4. Лабораторна робота 4 Розв’язання задачі двоїстим симплекс-методом
- •4.5. Лабораторна робота 5
- •Варіанти задач
- •4.6. Лабораторна робота 6
- •Варіанти задач
- •4.7. Варіанти завдань контрольної роботи для студентів заочної форми навчання
- •5. Вказівки до виконання лабораторних та контрольної робіт
- •5.1. Алгоритм симплекс-методу
- •5.2. Приклад
- •5.3. Алгоритм методу штучного базису
- •5.4. Приклад
- •5.5. Алгоритм двоїстого симплекс-методу
- •5.6. Приклад
- •5.7. Алгоритм методу Гоморі
- •5.8. Приклад
- •Рекомендована література
- •6.1. Основна
- •6.2. Додаткова
5.3. Алгоритм методу штучного базису
Складаємо розширену задачу.
Знаходимо початковий опорний план розширеної задачі.
Використовуючи симплекс-метод, виводимо штучні вектори з базису. В результаті знаходимо початковий опорний план вихідної задачі або встановлюємо, що задача не має розв’язку.
Перевіряємо знайдений опорний план на оптимальність і встановлюємо, що цей план оптимальний, або доказуємо, що задача немає розв’язку.
5.4. Приклад
Розв’язати задачу лінійного програмування з використанням методу штучного базису:
Зведемо задачу до канонічної форми:
Запишемо систему обмежень у векторній формі:
де
Кількість обмежень . Оскільки серед векторів не має двох одиничних векторів, то складаємо розширену задачу і вводимо штучні змінні .
де ─ деяке досить велике додатне число, конкретне значення якого не задається.
Вектори і одиничні, вони утворюють базис. Змінні і ─ базисні, змінні ─ вільні і прирівнюються до нуля. Опорний план розширеної задачі буде мати вигляд:
Використовуючи симплекс-метод для розширеної задачі, поступово вводимо в базис основні змінні замість штучних.
Після обмеженого числа ітерацій всі штучні змінні повинні бути виведені з базису.
Побудуємо симплекс-табл. 4.
Таблиця 4
i |
Базис |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
1 |
|
─М |
27 |
1 |
─1 |
4 |
|
─1 |
0 |
1 |
0 |
2 |
|
─М |
24 |
2 |
3 |
─1 |
4 |
0 |
─1 |
0 |
1 |
m+1 |
|
|
0 |
1 |
3 |
4 |
2 |
0 |
0 |
0 |
0 |
m+2 |
|
|
─51 |
─3 |
-2 |
─3 |
─9 |
1 |
1 |
0 |
0 |
Обчислимо і :
У рядок записуємо 0, оскільки немає чисел без , а в рядок записуємо ─ 51. Аналогічно обчислюємо і заносимо їх у таблицю:
Оскільки в рядку серед величин є від’ємні, то початковий опорний план розширеної задачі не є оптимальним. Треба перейти до наступного опорного плану. Обчислення виконуємо за допомогою симплекс-методу, однак розв’язуваний стовпець обираємо серед елементів рядка. Розв’язуваний стовпець відповідає найбільшому за абсолютною величиною від’ємному елементу рядка – це 9. Вектор, який вводиться, – . Знаходимо величину Розв’язуваний рядок – перший. Розв’язуваний елемент дорівнює 5.
Отже, з базису виведемо штучний вектор , коефіцієнти якого далі перераховувати не потрібно, а в базис вводимо вектор .
Використовуючи жорданові виключення перерахуємо елементи (табл.5).
Таблиця 5
i |
Базис |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
1 |
|
─2 |
|
|
|
|
1 |
|
0 |
|
0 |
2 |
|
─М |
|
|
|
|
0 |
|
─1 |
|
1 |
m+1 |
|
|
|
|
|
|
0 |
|
0 |
|
0 |
m+2 |
|
|
|
|
|
|
0 |
|
0 |
|
0 |
|
|||||||||||
1 |
|
─2 |
|
|
0 |
|
1 |
|
|
|
|
2 |
|
─М |
|
|
1 |
|
0 |
|
|
|
|
m+1 |
|
|
|
|
0 |
|
0 |
|
0 |
|
|
Після другого кроку з базису вийшли всі штучні змінні, і всі елементи рядка стали нулями. У стовпцях і рядка стоять від’ємні елементи. Це свідчить про те, що опорний план
не є оптимальним. Вектор буде розв’язуваним, оскільки ( ) – найбільший за абсолютною величиною від’ємний елемент рядка. Для знаходження розв’язуваного рядка обчислимо розв’язуваний рядок – другий, розв’язуваний елемент ─ .
У базис вводимо вектор , а з базису виводимо вектор і перераховуємо елементи таблиці. В результаті отримуємо табл. 6.
Таблиця 6
i |
Базис |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
1 |
|
─2 |
5 |
0 |
|
|
1 |
|
|
2 |
|
─1 |
2 |
1 |
|
|
0 |
|
|
m+1 |
|
|
─12 |
0 |
|
|
0 |
0 |
|
У табл. 6 всі . Опорний план 0, 0, 5, 0, 0) є оптимальним планом задачі і . Оскільки початкова задача була на мінімум цільової функції, то .