загрузка...
Пошук по сайту

Приклад знаходження максимуму функції симплексним методом

Завантажити рішення у форматі Word
Визначимо максимальне значення цільової функції F(X) = 8 x1  +8 x2  +4 x3   за наступних умов-обмежень.
x1   +  x2   + 3 x3 <=6
2 x1   + 2 x2   +  x3 <=8
4 x1   +  x2   + 3 x3 <=12
Для побудови перших опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
1x1 + 1x2 + 3x3 + 1x4 + 0x5 + 0x6 = 6
2x1 + 2x2 + 1x3 + 0x4 + 1x5 + 0x6 = 8
4x1 + 1x2 + 3x3 + 0x4 + 0x5 + 1x6 = 12
Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:

Базисні змінні це змінні, які входять лише в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x4  , x5  , x6  
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
 X1 = (0,0,0,6,8,12)
Оскільки завдання вирішується на максимум, то ведучий стовпець вибирають по максимальному негативному кількістю та індексного рядку. Всі перетворення проводять до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Переходимо до основного алгоритму симплекс-методу.
  План   Базис   В   x 1   x 2   x 3   x 4   x 5   x 6   min
  1   x4   6   1   1   3   1   0   0   6
    x5   8   2    2   1   0   1   0    4
    x6   12   4   1   3   0   0   1   12
  Індексний рядок   F(X1)   0   -8    -8   -4   0   0   0   0

Ітерація №0
Поточний опорний план неоптімален, так як в індексному рядку знаходяться негативні коефіцієнти.
У якості ведучого виберемо стовпець, відповідний змінної x2, так як найбільший коефіцієнт за модулем.
Обчислимо значення Di по рядках як частка від ділення

і з них виберемо найменше:

Отже, 2-а рядок є провідною
Дозволяє елемент дорівнює 2 і стоїть на перетині провідного стовпця і ведучою рядка.
Формуємо наступну частину симплексного таблиці.
Замість змінної x до плану 1 увійде мінлива x2
Рядок, відповідна змінної x 2  в плані 1, отримана в результаті поділу всіх елементів рядка x5 плану 0 на дозволяє елемент РЕ=2.
На місці дозволяє елемента в плані 1 отримуємо 1.
В інших клітинах стовпця x 2  плану 1 записуємо нулі.
Таким чином, у новому плані 1 заповнені рядок x2  і стовпець x2 .
Всі інші елементи нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Для цього вибираємо зі старого плану чотири числа, які розташовані у вершинах прямокутника і завжди включають дозволяє елемент РЕ.
НЕ = СЕ - (А*В)/РЕ
СТЭ - елемент старого плану, РЕ - дозволяє елемент (2), А і В - елементи старого плану, що утворюють прямокутник з елементами СТЕ і РЕ.
Уявімо розрахунок кожного елемента у вигляді таблиці:
B x 1 x 2 x 3 x 4 x 5 x 6
8 / 2 = 4 2 / 2 = 1 2 / 2 = 1 1 / 2 = 0.5 0 / 2 = 0 1 / 2 = 0.5 0 / 2 = 0

Кінець ітерацій: знайдений оптимальний план
Остаточний варіант симплекс-таблиці:
  План   Базис   В   x 1   x 2   x 3   x 4   x 5   x 6   min
  2   x4   2   0   0   2.5   1   -0.5   0   6
    x2   4   1   1   0.5   0   0.5   0   4
    x6   8   3   0   2.5   0   -0.5   1   12
  Індексний рядок   F(X2)   32   0   0   0   0   4   0   0

Оптимальний план можна записати так:
x4 = 2
x2 = 4
x6 = 8
F(X) = 8*4 = 32