Двоїстий симплекс-метод. Вирішимо пряму задачу лінійного програмування двоїстим симплексним методом, з використанням симплексного таблиці. Наведемо систему обмежень до системи нерівностей сенсу ?, помноживши відповідні рядки на (-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