Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці. Оскільки в правій частині присутні негативні значення, помножимо відповідні рядки на (-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 + 2 x 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) = x 1 + x 2 - Mx 7 > max З рівнянь виражаємо штучні змінні: x 7 = 3-x 1-2x 2 + x 4 які підставимо в цільову функцію: F (X) = (1 +1 M) x 1 + (1 +2 M) x 2 + (-1M) x 4 + (-3M) > max Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд: -3 2 1 0 0 0 0
1 2 0 -1 0 0 1
1 0 0 0 1 0 0
0 1 0 0 0 1 0
Вирішимо систему рівнянь щодо базисних змінних: x 3, x 7, x 5, x 6, Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план: X1 = (0,0,6,0,3,5,3) Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7
x 3 6 -3 2 1 0 0 0 0
x 7 3 1 2 0 -1 0 0 1
x 5 3 1 0 0 0 1 0 0
x 6 5 0 1 0 0 0 1 0
F (X0) -3M -1-1M -1-2M 0 1M 0 0 0
Переходимо до основного алгоритму симплекс-метода. Ітерація № 0. Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти. В якості ведучого виберемо стовпець, відповідний змінної x 2, так як це найбільший коефіцієнт за модулем. Обчислимо значення D i по рядках як частка від ділення: b i / a i2 і з них виберемо найменше: Отже, 2-ий рядок є провідною. Дозволяє елемент дорівнює (2) і стоїть на перетині провідного стовпця і ведучою рядка. Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7 min
x 3 6 -3 2 1 0 0 0 0 3
x 7 3 1 2 0 -1 0 0 1 1 1/2
x 5 3 1 0 0 0 1 0 0 -
x 6 5 0 1 0 0 0 1 0 5
F (X1) -3M -1-1M -1-2M 0 1M 0 0 0 0
Отримуємо нову симплекс-таблицю: Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7
x 3 3 -4 0 1 1 0 0 -1
x 2 1 1/2 1/2 1 0 -1 / 2 0 0 1/2
x 5 3 1 0 0 0 1 0 0
x 6 3 1/2 -1 / 2 0 0 1/2 0 1 -1 / 2
F (X1) 1 1/2 -1 / 2 0 0 -1 / 2 0 0 1/2 +1 M
Ітерація № 1. Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти. В якості ведучого виберемо стовпець, відповідний змінної x 4, так як це найбільший коефіцієнт за модулем. Обчислимо значення D i по рядках як частка від ділення: b i / a i4 і з них виберемо найменше: Отже, 1-а рядок є провідною. Дозволяє елемент дорівнює (1) і стоїть на перетині провідного стовпця і ведучою рядка. Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7 min
x 3 3 -4 0 1 1 0 0 -1 3
x 2 1 1/2 1/2 1 0 -1 / 2 0 0 1/2 -
x 5 3 1 0 0 0 1 0 0 -
x 6 3 1/2 -1 / 2 0 0 1/2 0 1 -1 / 2 7
F (X2) 1 1/2 -1 / 2 0 0 -1 / 2 0 0 1/2 +1 M 0
Отримуємо нову симплекс-таблицю: Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7
x 4 3 -4 0 1 1 0 0 -1
x 2 3 -1 1/2 1 1/2 0 0 0 0
x 5 3 1 0 0 0 1 0 0
x 6 2 1 1/2 0 -1 / 2 0 0 1 0
F (X2) 3 -2 1/2 0 1/2 0 0 0 1M
Ітерація № 2. Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти. В якості ведучого виберемо стовпець, відповідний змінної x 1, так як це найбільший коефіцієнт за модулем. Обчислимо значення D i по рядках як частка від ділення: b i / a i1 і з них виберемо найменше: Отже, 4-й рядок є провідною. Дозволяє елемент дорівнює (1 1/2) і стоїть на перетині провідного стовпця і ведучою рядка. Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7 min
x 4 3 -4 0 1 1 0 0 -1 -
x 2 3 -1 1/2 1 1/2 0 0 0 0 -
x 5 3 1 0 0 0 1 0 0 3
x 6 2 1 1/2 0 -1 / 2 0 0 1 0 1 1/3
F (X3) 3 -2 1/2 0 1/2 0 0 0 1M 0
Отримуємо нову симплекс-таблицю: Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7
x 4 8 1/3 0 0 -1 / 3 1 0 2 2/3 -1
x 2 5 0 1 0 0 0 1 0
x 5 1 2/3 0 0 1/3 0 1 -2 / 3 0
x 1 1 1/3 1 0 -1 / 3 0 0 2/3 0
F (X3) 6 1/3 0 0 -1 / 3 0 0 1 2/3 1M
Ітерація № 3. Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти. В якості ведучого виберемо стовпець, відповідний змінної x 3, так як це найбільший коефіцієнт за модулем. Обчислимо значення D i по рядках як частка від ділення: b i / a i3 і з них виберемо найменше: Отже, 3-а рядок є провідною. Дозволяє елемент дорівнює (1/3) і стоїть на перетині провідного стовпця і ведучою рядка. Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7 min
x 4 8 1/3 0 0 -1 / 3 1 0 2 2/3 -1 -
x 2 5 0 1 0 0 0 1 0 -
x 5 1 2/3 0 0 1/3 0 1 -2 / 3 0 5
x 1 1 1/3 1 0 -1 / 3 0 0 2/3 0 -
F (X4) 6 1/3 0 0 -1 / 3 0 0 1 2/3 1M 0
Отримуємо нову симплекс-таблицю: Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7
x 4 10 0 0 0 1 1 2 -1
x 2 5 0 1 0 0 0 1 0
x 3 5 0 0 1 0 3 -2 0
x 1 3 1 0 0 0 1 0 0
F (X4) 8 0 0 0 0 1 1 1M
Кінець ітерацій: індексна рядок не містить негативних елементів - знайдений оптимальний план Остаточний варіант симплекс-таблиці: Базис B x 1 x 2 x 3 x 4 x 5 x 6 x 7
x 4 10 0 0 0 1 1 2 -1
x 2 5 0 1 0 0 0 1 0
x 3 5 0 0 1 0 3 -2 0
x 1 3 1 0 0 0 1 0 0
F (X5) 8 0 0 0 0 1 1 1M
Оптимальний план можна записати так: x 4 = 10 x 2 = 5 x 3 = 5 x 1 = 3 F (X) = 1 5 + 1 3 = 8