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

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

Завантажити рішення у форматі Word
Визначимо мінімальне значення цільової функції F(X) = 5 x1  +6 x2  +3 x3   за наступних умов-обмежень.
3.4 x1   + 5.6 x2   + 4.4 x3 >=0.2
0.6 x1   + 0.7 x2   + 0.2 x3 >=0.98
0.7 x1   + 0.5 x2   + 0.7 x3 >=079
0.3 x1   + 1.3 x2   + 0.79 x3 >=0.1
Для побудови перших опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
3.4x1 + 5.6x2 + 4.4x3-1x4 + 0x5 + 0x6 + 0x7 = 0.2
 0.6x1 + 0.7x2 + 0.2x3 + 0x4-1x5 + 0x6 + 0x7 = 0.98
 0.7x1 + 0.5x2 + 0.7x3 + 0x4 + 0x5-1x6 + 0x7 = 079
 0.3x1 + 1.3x2 + 0.79x3 + 0x4 + 0x5 + 0x6-1x7 = 0.1
Оскільки завдання вирішується на мінімум і елементи одиничної матриці негативні, зведемо задачу до знаходження максимуму.
Для цього помножимо всі рядки на (-1) і будемо шукати початковий опорний план.
Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:
  -3.4   -5.6   -4.4   1   0   0   0
  -0.6   -0.7   -0.2   0   1   0   0
  -0.7   -0.5   -0.7   0   0   1   0
  -0.3   -1.3   -0.79   0   0   0   1

Базисні змінні це змінні, які входять лише в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x4, x5 ,x6 , x 7  
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,0,-0.2,-0.98,-79,-0.1)
У стовпці вільних членів є негативні елементи. Виберемо з них найбільший за модулем, а в його рядку - будь-який негативний. Взявши Цей елемент може бути дозволяє перерахуємо таблицю.
У якості ведучого виберемо стовпець, відповідний змінної x1.
3-а рядок є провідною.
 План   Базис   В   x 1   x 2   x 3   x 4   x 5   x 6   x 7   min
  0   x4   383.51   0   -3.17   -1   1   0   -4.86   0   0
    x5   66.73   0   -0.27   0.4   0   1   -0.86   0   0
    x1   112.86   1   0.71   1   0   0   -1.43   0   0
    x7   33.76   0   -1.09   -0.49   0   0   -0.43   1   0
  Індексний рядок   F(X)   -564.29   0   2.43   -2   0   0   7.14   0   0

НЕ = СЕ - (А*В)/РЕ
Уявімо розрахунок кожного елемента у вигляді таблиці:
  B   x 1   x 2   x 3   x 4   x 5   x 6   x 7
  112.86 / 1 = 112.86   1 / 1 = 1   0.71 / 1 = 0.71   1 / 1 = 1   0 / 1 = 0   0 / 1 = 0   -1.43 / 1 = -1.43   0 / 1 = 0

У базисному стовпчику всі елементи позитивні.
Переходимо до основного алгоритму симплекс-методу.
  План   Базис   В   x 1   x 2   x 3   x 4   x 5   x 6   x 7   min
  1   x4   383.51   0   -3.17   -1   1   0   -4.86   0   0
    x5   66.73   0   -0.27   0.4   0   1   -0.86   0   0
    x1   112.86   1    0.71   1   0   0   -1.43   0    158
    x7   33.76   0   -1.09   -0.49   0   0   -0.43   1   0
  Індексний рядок   F(X1)   -564.29   0    2.43   -2   0   0   7.14   0   0

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

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

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

У базисному стовпчику всі елементи позитивні. Тому переходимо до основного алгоритму симплекс-методу.
  План   Базис   В   x 1   x 2   x 3   x 4   x 5   x 6   x 7   min
  2   x4   884.6   4.44   -0   3.44   1   0   -11.2   0   257.15
    x5   109.62   0.38   -0   0.78   0   1   -1.4   0   140.54
    x2   158   1.4   1    1.4   0   0   -2   0    112.86
    x7   205.3   1.52   -0   1.03   0   0   -2.6   1   199.32
  Індексний рядок   F(X2)   -948   -3.4   0    -5.4   0   0   12   0   0

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

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

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

Остаточний варіант симплекс-таблиці:
 План   Базис   В   x 1   x 2   x 3   x 4   x 5   x 6   x 7   min
  3   x4   496.37   1   -2.46   0   1   0   -6.29   0   257.15
    x5   21.59   -0.4   -0.56   0   0   1   -0.29   0   140.54
    x3   112.86   1   0.71   1   0   0   -1.43   0   112.86
    x7   89.06   0.49   -0.74   0   0   0   -1.13   1   199.32
  Індексний рядок   F(X3)   -338.57   2   3.86   -0   0   0   4.29   0   0

Оптимальний план можна записати так:
x4 = 496.37
x5 = 21.59
x3 = 112.86
x7 = 89.06
F(X) = 3*112.86 = 338.57