Двоїстий симплекс-метод.
Вирішимо пряму задачу лінійного програмування двоїстим симплексним методом, з використанням симплексного таблиці.
Наведемо систему обмежень до системи нерівностей сенсу ?, помноживши відповідні рядки на (-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
Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:
Вирішимо систему рівнянь щодо базисних змінних:
x 3, x 4, x 5, x 6,
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,6, -3,3,5)
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6

x 3
6
-3
2
1
0
0
0

x 4
-3
-1
-2
0
1
0
0

x 5
3
1
0
0
0
1
0

x 6
5
0
1
0
0
0
1

F (X0)
0
-1
-1
0
0
0
0

 
План 0 в симплексного таблиці є псевдопланом, тому визначаємо провідні рядок і стовпець.
На перетині провідних рядка і стовпця знаходиться дозволяє елемент (РЕ), рівний (-2).
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6

x 3
6
-3
2
1
0
0
0

x 4
-3
-1
-2
0
1
0
0

x 5
3
1
0
0
0
1
0

x 6
5
0
1
0
0
0
1

F (X)
0
-1
-1
0
0
0
0

?
0
-1: (-1) = 1
-1: (-2) = 1/2
-
-
-
-

 
Виконуємо перетворення симплексного таблиці методом Жордана-Гаусса.
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6

x 3
3
-4
0
1
1
0
0

x 2
1 1/2
1/2
1
0
-1 / 2
0
0

x 5
3
1
0
0
0
1
0

x 6
3 1/2
-1 / 2
0
0
1/2
0
1

F (X0)
1 1/2
-1 / 2
0
0
-1 / 2
0
0

 
У базисному стовпці всі елементи позитивні.
Переходимо до основного алгоритму симплекс-метода.
Кінець ітерацій: індексна рядок не містить позитивних елементів - знайдений оптимальний план
Остаточний варіант симплекс-таблиці:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6

x 3
3
-4
0
1
1
0
0

x 2
1 1/2
1/2
1
0
-1 / 2
0
0

x 5
3
1
0
0
0
1
0

x 6
3 1/2
-1 / 2
0
0
1/2
0
1

F (X1)
1 1/2
-1 / 2
0
0
-1 / 2
0
0

 
Оптимальний план можна записати так:
x 3 = 3
x 2 = 1 1/2
x 5 = 3
x 6 = 3 1/2
F (X) = 1 • 1 1/2 = 1 1/2