Вирішимо пряму задачу лінійного програмування симплекс-методом ..
Оскільки в правій частині присутні негативні значення, помножимо відповідні рядки на (-1).
Визначимо максимальне значення цільової функції F (X) = x 1 + x 2 при наступних умовах-обмежень.
- 3x 1 + 2x 2 ? 6
x 1 + 2x 2 ? 3
x 1 ? 3
x 2 ? 5
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної формі).
-3x 1 + 2x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 6
1x 1 + 2x 2 + 0x 3-1x 4 + 0x 5 + 0x 6 = 3
1x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 3
0x 1 + 1x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 5
Введемо штучні змінні x: в 2-м рівність вводимо змінну x 7;
-3x 1 + 2x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 + 0x 7 = 6
1x 1 + 2x 2 + 0x 3-1x 4 + 0x 5 + 0x 6 + 1x 7 = 3
1x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 + 0x 7 = 3
0x 1 + 1x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 + 0x 7 = 5
Для постановки задачі на максимум цільову функцію запишемо так:
F (X) = - Mx 7 > max
З рівнянь виражаємо штучні змінні:
x 7 = 3-x 1-2x 2 + x 4
які підставимо в цільову функцію:
F (X) = (1M) x 1 + (2M) x 2 + (-1M) x 4 + (-3M) > max
Введемо нову змінну x 0 = x 1 + 2x 2.
Висловимо базисні змінні <3, 7, 5, 6> через небазисних.
x 0 = -3 + x 1 +2 x 2-x 4
x 3 = 6 +3 x 1-2x 2
x 7 = 3-x 1-2x 2 + x 4
x 5 = 3-x 1
x 6 = 5-x 2
Переходимо до основного алгоритму симплекс-метода.
Оскільки завдання вирішується на максимум, то змінну для включення в поточний план вибирають по максимальному позитивному числу в рівнянні для x 0.
max (1,2,0, -1,0,0,0) = 2
x 0 = -3 + x 1 +2 x 2-x 4
x 3 = 6 +3 x 1-2x 2
x 7 = 3-x 1-2x 2 + x 4
x 5 = 3-x 1
x 6 = 5-x 2
В якості нової змінної вибираємо x 2.
Обчислимо значення D i по всіх рівнянь для цієї змінної: b i / a i2
і з них виберемо найменше:
Замість змінної x 7 в план увійде мінлива x 2.
Висловимо змінну x 2 через x 7
і підставимо в усі вирази.
Після приведення всіх подібних, отримуємо нову систему, еквівалентну колишньою:
x 0 = 0-x 7
x 3 = 3 +4 x 1-x 4 + x 7
x 2 = 1 1/2 -1 / 2 x 1 + 1/2 x 4 -1 / 2 x 7
x 5 = 3-x 1
x 6 = 3 1/2 + 1/2 x 1 -1 / 2 x 4 + 1/2 x 7
Вважаючи небазисних змінні x = (3, 2, 5, 6) рівними нулю, одержимо новий допустимий вектор і значення цільової функції:
x = (0, 0, 0, 0, 0, 0, 1), x 0 = 0
Вираз для x 0 не містить позитивних елементів. Знайдений оптимальний план.
x 0 = 0-x 7
x 3 = 3 +4 x 1-x 4 + x 7
x 2 = 1 1/2 -1 / 2 x 1 + 1/2 x 4 -1 / 2 x 7
x 5 = 3-x 1
x 6 = 3 1/2 + 1/2 x 1 -1 / 2 x 4 + 1/2 x 7
На цьому перший етап симплекс-метода завершений. Переходимо до другого етапу. Видаляємо змінні з штучними змінними.
x 3 = 3 +4 x 1-x 4
x 2 = 1 1/2 -1 / 2 x 1 + 1/2 x 4
x 5 = 3-x 1
x 6 = 3 1/2 + 1/2 x 1 -1 / 2 x 4
Висловимо базисні змінні:
x 2 = 1 1/2 -1 / 2 x 1 + 1/2 x 4
які підставимо в цільову функцію:
F (X) = 1 1/2 + 1/2 x 1 + 1/2 x 4
Отримуємо нову систему змінних.
x 0 = 1 1/2 + 1/2 x 1 + 1/2 x 4
x 3 = 3 +4 x 1-x 4
x 2 = 1 1/2 -1 / 2 x 1 + 1/2 x 4
x 5 = 3-x 1
x 6 = 3 1/2 + 1/2 x 1 -1 / 2 x 4
max (1/2, 0,0, 1/2, 0,0) = 1/2
x 0 = 1 1/2 + 1/2 x 1 + 1/2 x 4
x 3 = 3 +4 x 1-x 4
x 2 = 1 1/2 -1 / 2 x 1 + 1/2 x 4
x 5 = 3-x 1
x 6 = 3 1/2 + 1/2 x 1 -1 / 2 x 4
В якості нової змінної вибираємо x 4.
Обчислимо значення D i по всіх рівнянь для цієї змінної: b i / a i4
і з них виберемо найменше:
Замість змінної x 3 в план увійде мінлива x 4.
Висловимо змінну x 4 через x 3
і підставимо в усі вирази.
Після приведення всіх подібних, отримуємо нову систему, еквівалентну колишньою:
x 0 = 3 +2 +1 / 2 x 1 -1 / 2 x 3
x 4 = 3 +4 x 1-x 3
x 2 = 3 +1 +1 / 2 x 1 -1 / 2 x 3
x 5 = 3-x 1
x 6 = 2-1 1/2 x 1 + 1/2 x 3
Вважаючи небазисних змінні x = (4, 2, 5, 6) рівними нулю, одержимо новий допустимий вектор і значення цільової функції:
x = (-2 1/2, 0, 1/2, 0, 0, 0), x 0 = 3
max (2 1/2, 0, -1 / 2, 0,0,0) = 2 1/2
x 0 = 3 +2 +1 / 2 x 1 -1 / 2 x 3
x 4 = 3 +4 x 1-x 3
x 2 = 3 +1 +1 / 2 x 1 -1 / 2 x 3
x 5 = 3-x 1
x 6 = 2-1 1/2 x 1 + 1/2 x 3
В якості нової змінної вибираємо x 1.
Обчислимо значення D i по всіх рівнянь для цієї змінної: b i / a i1
і з них виберемо найменше:
Замість змінної x 6 в план увійде мі
нлива x 1.
Висловимо змінну x 1 через x 6
і підставимо в усі вирази.
Після приведення всіх подібних, отримуємо нову систему, еквівалентну колишньою:
x 0 = 6 1/3 + 1/3 x 3 -1 2/3 x 6
x 4 = 8 1/3 + 1/3 x 3 -2 2/3 x 6
x 2 = 5-x 6
x 5 = 1 2/3 -1 / 3 x 3 + 2/3 x 6
x 1 = 1 1/3 + 1/3 x 3 -2 / 3 x 6
Вважаючи небазисних змінні x = (4, 2, 5, 1) рівними нулю, одержимо новий допустимий вектор і значення цільової функції:
x = (0, 0, -1 / 3, 0, 0, 1 2/3), x 0 = 6 1/3
max (0,0, 1/3, 0,0, -1 2/3) = 1/3
x 0 = 6 1/3 + 1/3 x 3 -1 2/3 x 6
x 4 = 8 1/3 + 1/3 x 3 -2 2/3 x 6
x 2 = 5-x 6
x 5 = 1 2/3 -1 / 3 x 3 + 2/3 x 6
x 1 = 1 1/3 + 1/3 x 3 -2 / 3 x 6
В якості нової змінної вибираємо x 3.
Обчислимо значення D i по всіх рівнянь для цієї змінної: b i / a i3
і з них виберемо найменше:
Замість змінної x 5 до плану увійде мінлива x 3.
Висловимо змінну x 3 через x 5
і підставимо в усі вирази.
Після приведення всіх подібних, отримуємо нову систему, еквівалентну колишньою:
x 0 = 8-x 5-x 6
x 4 = 10-x 5-2x 6
x 2 = 5-x 6
x 3 = 5-3x 5 +2 x 6
x 1 = 3-x 5
Вважаючи небазисних змінні x = (4, 2, 3, 1) рівними нулю, одержимо новий допустимий вектор і значення цільової функції:
x = (0, 0, 0, 0, 1, 1), x 0 = 8
Вираз для x 0 не містить позитивних елементів. Знайдений оптимальний план.
Остаточний варіант системи рівнянь:
x 0 = 8-x 5-x 6
x 4 = 10-x 5-2x 6
x 2 = 5-x 6
x 3 = 5-3x 5 +2 x 6
x 1 = 3-x 5
Оптимальний план можна записати так:
x 4 = 10
x 2 = 5
x 3 = 5
x 1 = 3
F (X) = 8
Метод Гоморі.
Рішення вийшло цілочисловим. Немає необхідності застосовувати метод Гоморі.
Оптимальний цілочисельний план можна записати так:
x 4 = 10
x 2 = 5
x 3 = 5
x 1 = 3
F (X) = 8