Для того щоб показати, що я освоїв даний матеріал зміню напрям цільової функції на min. Оскільки в даній лабораторній роботі розглядається і сиплекс метод двійної задачі то в наступному методі буде показано значення цільової функції при max.
З попередньої лабораторної роботи відомо що
F(0,8)=48->max
F (0,3)=18-> min
Приведемо систему обмежень до системи нерівностей сенсу ≤, помноживши відповідні рядки на (-1).
Визначимо мінімальне значення цільової функції F (X) = 3x1 + 6x2 при наступних умовах-обмеженнях.
x 1 + x 2 
8,
3x 1 + 7 x 2 
21,
x 1 + 2 x 2 6,
Для побудови першого опорного плану систему нерівностей приведемо систему рівнянь до рівностей шляхом введення додаткових змінних (перехід до канонічної форми).
В 1-й нерівності типу ()вводимо базисну змінну x3. В 2-й нерівності типу
() вводимо базисну змінну x4. У 3-й нерівності типу () вводимо базисну змінну x5.
1x1 + 1x2 + 1x3 + 0x4 + 0x5 = 8
-3x1-7x2 + 0x3 + 1x4 + 0x5 = -21
-1x1-2x2 + 0x3 + 0x4 + 1x5 = -6
Матриця коефіцієнтів A=a(ij) цієї системи рівнянь має вигляд:
Базисні змінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь щодо базисних змінних:
x3, x4, x5,
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,8,-21,-6)
Базисне рішення називається допустимим, якщо воно невід’ємне.
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | ||||||
| x4 | -21 | -3 | -7 | |||
| x5 | -6 | -1 | -2 | |||
| F(X0) | -3 | -6 |
1. Перевірка критерію оптимальності.
План 0 в симплексного таблиці є псевдопланом, тому визначаємо провідний рядок і стовпець.
2. Визначення нової вільної змінної.
Серед негативних значень базисних змінних вибираємо найбільший по модулю.
Провідним буде 2-ий рядок, а змінну x4 слід вивести із базису.
3. Визначення нової базисної змінної.
Мінімальне значення θ відповідає 2-му стовпцю, тобто змінну x2 необхідно ввести в базис.
На перетині провідного рядка і стовпця знаходиться дозволяючий елемент (ДЕ), який дорівнює (-7).
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | ||||||
| x4 | -21 | -3 | -7 | |||
| x5 | -6 | -1 | -2 | |||
| F(X) | -3 | -6 | ||||
| Θ(дельта) | -3: (-3) = 1 | -6: (-7) = 6/7 | - | - | - |
4. Перерахунок симплекс таблиці
Виконуємо перетворення симплексного таблиці методом Жордана-Гаусса.
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 4/7 | 1/7 | ||||
| x2 | 3/7 | -1/7 | ||||
| x5 | -1/7 | -2/7 | ||||
| F(X0) | -3/7 | -6/7 |
Показую розрахунок кожного елемента у вигляді таблиці:
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| 8-(-21 • 1):-7 | 1-(-3 • 1):-7 | 1-(-7 • 1):-7 | 1-(0 • 1):-7 | 0-(1 • 1):-7 | 0-(0 • 1):-7 |
| -21: -7 | -3: -7 | -7: -7 | 0: -7 | 1: -7 | 0: -7 |
| -6-(-21 • -2):-7 | -1-(-3 • -2):-7 | -2-(-7 • -2):-7 | 0-(0 • -2):-7 | 0-(1 • -2):-7 | 1-(0 • -2):-7 |
| 0-(-21 • -6):-7 | -3-(-3 • -6):-7 | -6-(-7 • -6):-7 | 0-(0 • -6):-7 | 0-(1 • -6):-7 | 0-(0 • -6):-7 |
У базисному стовпці всі елементи позитивні.
Переходимо до основного алгоритму симплекс-методу.
1. Перевірка критерію оптимальності.
Серед значень індексного рядка немає позитивних елементів(тих що задовольняють умову). Тому ця таблиця визначає оптимальний план задачі.
Остаточний варіант симплекс-таблиці:
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 4/7 | 1/7 | ||||
| x2 | 3/7 | -1/7 | ||||
| x5 | -1/7 | -2/7 | ||||
| F(X1) | -3/7 | -6/7 |
Оптимальний план при F=3X1+6X2->min
x3 = 5
x2 = 3
x5 = 0
F(X) = 6•3 = 18
Отже значення з лабораторною роботою №1 співпали.
Перевірка даного методу в Exel подана нижче у розділі №3 (малюнок 1-2)
Дата добавления: 2015-11-14; просмотров: 39 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Алгоритм симплекс методу | | | З додаванням додаткових змінних . |