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

Условие:

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

Решение:

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