Решение задачи линейного программирования искусственным симплексным методом

Предмет: Математика

Раздел: Линейное программирование

Задача линейного программирования требует поиска наибольшего значения целевой функции с учетом заданных ограничений. В данном случае, целевая функция: \( Z = x_1 - x_2 \) и ограничения: \[ \begin{cases} x_1 + x_2 \leq 2, \\ -2x_1 + x_2 \leq 1, \\ 3x_1 - x_2 \leq 3, \\ x_i \geq 0, \, i = 1, 2. \end{cases} \]

Для решения задачи искусственным симплексным методом введем дополнительные переменные, чтобы удовлетворить ограничения:

1. Введем дополнительные переменные (искусственные переменные) \( s_1, s_2, s_3 \) для преобразования неравенств в равенства: \[ \begin{cases} x_1 + x_2 + s_1 = 2, \\ -2x_1 + x_2 + s_2 = 1, \\ 3x_1 - x_2 + s_3 = 3, \\ x_i, s_j \geq 0, \, i = 1, 2, \, j = 1, 2, 3. \end{cases} \]
2. Запишем начальную задачу искусственным симплексным методом. Поскольку дополнительные переменные искусственные, они добавляются в целевую функцию с большими коэффициентами \( M \): \[ Z = x_1 - x_2 - M(s_1 + s_2 + s_3) \to \max. \]
3. Преобразуем систему ограничений в каноническую форму: \[ \begin{cases} x_1 + x_2 + s_1 = 2, \\ -2x_1 + x_2 + s_2 = 1, \\ 3x_1 - x_2 + s_3 = 3. \end{cases} \]
4. Начальная таблица симплекс-метода будет выглядеть следующим образом: \[ \begin{array}{c|ccccc|c} & x_1 & x_2 & s_1 & s_2 & s_3 & B \\ \hline s_1 & 1 & 1 & 1 & 0 & 0 & 2 \\ s_2 & -2 & 1 & 0 & 1 & 0 & 1 \\ s_3 & 3 & -1 & 0 & 0 & 1 & 3 \\ \hline Z & -1 & -1 & -M & -M & -M & 0 \\ \end{array} \]
5. Находим элемент наибольшего уменьшения в строке целевой функции \( Z \). В данном случае это элемент при \( x_1 \) с коэффициентом -1. Столбец \( x_1 \) будет базисным.
6. Рассчитываем отношения для выбора ведущей строки: \[ \begin{cases} \frac{2}{1} = 2, \\ \frac{1}{-2} \, \text{не применимо (отрицательное)}, \\ \frac{3}{3} = 1. \end{cases} \] Минимальное положительное значение отношения равно 1. Выбираем строку \( s_3 \),
7. Применяем элементарные преобразования для получения новой таблицы, заменив \( s_3 \) на \( x_1 \). Нормализуем строку \( s_3 \): \[ \frac{\{3, -1, 0, 0, 1, 3\}}{3} = \{1, -\frac{1}{3}, 0, 0, \frac{1}{3}, 1\} \]

Обновляем другие строки в таблице с учетом проведенной нормализации:

Таким образом, новая таблица симплекс-метода:

Продолжаем итерации, пока не получим оптимальное значение. Важно следить за улучшением значения целевой функции на каждом шагу. Таким образом, данная задача решается с помощью искусственного симплексного метода, требуется продолжить итерации, отбросив искусственные переменные, чтобы получить окончательную оптимальную таблицу и максимально возможное значение \( Z \).