МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
БУКОВИНСЬКИЙ ДЕРЖАВНИЙ ФІНАНСОВО-ЕКОНОМІЧНИЙ УНІЕРСИТЕТ
ІНДЗ з навчальної дисципліни «ОПТИМІЗАЦІЙНІ МЕТОДИ ТА МОДЕЛІ»
Виконала
Студентка групи ОА-21
Чипчирук А.Р.
Викладач
Веренич І.І.
Чернівці 2012
Задача до розділу V
Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.
Визначимо максимальне значення цільової функції F (X) = 3x1 + 2x2 за таких умов-обмежень.
7x1 + 3x2≤10
2x1 + x2≤5
Для побудови першого опорного плану систему нерівностей наведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).
В 1-м нерівності сенсу (≤) вводимо базисну змінну x3. В 2-м нерівності сенсу (≤) вводимо базисну змінну x4.
7x1 + 3x2 + 1x3 + 0x4 = 10
2x1 + 1x2 + 0x3 + 1x4 = 5
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x3, x4,
Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план:
X1 = (0,0,10,5)
Базисне рішення називається допустимим, якщо воно невід'ємне.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x3 |
10 |
7 |
3 |
1 |
0 |
x4 |
5 |
2 |
1 |
0 |
1 |
F(X0) |
0 |
-3 |
-2 |
0 |
0 |
Переходимо до основного алгоритму симплекс-методу.
Ітерація №0.
1. Перевірка критерію оптимальності.
Поточний опорний план неоптімален, так що в індексному рядку знаходяться негативні коефіцієнти.
2. Визначення нової базисної змінної.
В якості ведучого виберемо стовпець, відповідний змінної x1, так як це найбільший коефіцієнт по модулю.
3. Визначення нової вільної змінної.
Обчислимо значення Di по рядках як частка від ділення: bi / ai1
і з них виберемо найменше:
min (10 : 7 , 5 : 2 ) = 13/7
Отже, 1-ий рядок є провідною.
Дозволяючий елемент дорівнює (7) і стоїть на перетині ведучого шпальти і головною рядка.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
min |
x3 |
10 |
7 |
3 |
1 |
0 |
13/7 |
x4 |
5 |
2 |
1 |
0 |
1 |
21/2 |
F(X1) |
0 |
-3 |
-2 |
0 |
0 |
0 |
4. Перерахунок симплекс-таблиці.
Формуємо наступну частину симплексного таблиці.
Замість змінної x в план 1 увійде мінлива x1 .
Рядок, відповідна змінної x1 в плані 1, отримана в результаті поділу всіх елементів рядка x3 плану 0 на дозволяє елемент РЕ=7.
На місці дозволяє елемента в плані 1 отримуємо 1.
В інших клітинах стовпц x1 плану 1 записуємо нулі.
Таким чином, у новому плані 1 заповнені рядок x1 і стовпець x1.
Всі інші елементи нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Для цього вибираємо зі старого плану чотири числа, які розташовані в вершинах прямокутника і завжди включають дозволяє елемент РЕ.
НЕ = СЕ - (А * В) / РЕ
СТЕ - елемент старого плану, РЕ - дозволяє елемент (7), А і В - елементи старого плану, що утворюють прямокутник з елементами СТЕ і РЕ.
Уявімо розрахунок кожного елемента у вигляді таблиці:
B |
x 1 |
x 2 |
x 3 |
x 4 |
10 : 7 |
7 : 7 |
3 : 7 |
1 : 7 |
0 : 7 |
5-(10 • 2):7 |
2-(7 • 2):7 |
1-(3 • 2):7 |
0-(1 • 2):7 |
1-(0 • 2):7 |
0-(10 • -3):7 |
-3-(7 • -3):7 |
-2-(3 • -3):7 |
0-(1 • -3):7 |
0-(0 • -3):7 |
Отримуємо нову симплекс-таблицю:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x1 |
13/7 |
1 |
3/7 |
1/7 |
0 |
x4 |
21/7 |
0 |
1/7 |
-2/7 |
1 |
F(X1) |
42/7 |
0 |
-5/7 |
3/7 |
0 |
Ітерація №1.
1. Перевірка критерію оптимальності.
Поточний опорний план неоптімален, так що в індексному рядку знаходяться негативні коефіцієнти.
2. Визначення нової базисної змінної.
В якості ведучого виберемо стовпець, відповідний змінної x2, так як це найбільший коефіцієнт по модулю.
3. Визначення нової вільної змінної.
Обчислимо значення Di по рядках як частка від ділення: bi / ai2
і з них виберемо найменше:
min (13/7 : 3/7 , 21/7 : 1/7 ) = 31/3
Отже, 1-ий рядок є провідною.
Дозволяючий елемент дорівнює (3/7) і стоїть на перетині ведучого шпальти і головною рядка.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
min |
x1 |
13/7 |
1 |
3/7 |
1/7 |
0 |
31/3 |
x4 |
21/7 |
0 |
1/7 |
-2/7 |
1 |
15 |
F(X2) |
42/7 |
0 |
-5/7 |
3/7 |
0 |
0 |
4. Перерахунок симплекс-таблиці.
Формуємо наступну частину симплексного таблиці.
Замість змінної x в план 2 увійде мінлива x2 .
Рядок, відповідна змінної x2 в плані 2, отримана в результаті поділу всіх елементів рядка x1 плану 1 на дозволяє елемент РЕ=3/7.
На місці дозволяє елемента в плані 2 отримуємо 1.
В інших клітинах стовпц x2 плану 2 записуємо нулі.
Таким чином, у новому плані 2 заповнені рядок x2 і стовпець x2.
Всі інші елементи нового плану 2, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Уявімо розрахунок кожного елемента у вигляді таблиці:
B |
x 1 |
x 2 |
x 3 |
x 4 |
13/7 : 3/7 |
1 : 3/7 |
3/7 : 3/7 |
1/7 : 3/7 |
0 : 3/7 |
21/7-(13/7 • 1/7):3/7 |
0-(1 • 1/7):3/7 |
1/7-(3/7 • 1/7):3/7 |
-2/7-(1/7 • 1/7):3/7 |
1-(0 • 1/7):3/7 |
42/7-(13/7 • -5/7):3/7 |
0-(1 • -5/7):3/7 |
-5/7-(3/7 • -5/7):3/7 |
3/7-(1/7 • -5/7):3/7 |
0-(0 • -5/7):3/7 |
Отримуємо нову симплекс-таблицю:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x2 |
31/3 |
21/3 |
1 |
1/3 |
0 |
x4 |
12/3 |
-1/3 |
0 |
-1/3 |
1 |
F(X2) |
62/3 |
12/3 |
0 |
2/3 |
0 |