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

Предмет: Математическое программирование

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

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

1. Приведение задачи к стандартной форме.
2. Введение искусственных переменных.
3. Формирование начального симплексного таблицы.
4. Применение симплексного метода для достижения оптимального решения.

Приведение задачи к стандартной форме

Запишем все ограничения с неравенствами в виде равенств, введя дополнительные переменные \( u_i \):

1. \( x_1 + x_2 + u_1 = 3 \)
2. \( -2x_1 + 3x_2 + u_2 = 8 \)
3. \( -x_1 - x_2 - u_3 = -2 \) (переписываем как \( - x_1 - x_2 + u_3 = 2 \), так как \(u_3 \geq 0\))

Итак, введём дополнительные переменные:

\[ u_1, u_2, u_3 \geq 0 \]

Введение искусственных переменных

Добавляем искусственные переменные \( R_i \) к ограничениям, чтобы начальная база была допустимой. Новая система выглядит следующим образом:

\[ \begin{cases} x_1 + x_2 + u_1 + R_1 = 3 \\ -2x_1 + 3x_2 + u_2 + R_2 = 8 \\ -x_1 - x_2 + u_3 + R_3 = 2 \\ x_1, x_2, u_1, u_2, u_3, R_1, R_2, R_3 \geq 0 \end{cases} \]

Целевая функция примет вид: \( Z = 4x_1 - x_2 \). Для искусственного строителя функции примем: W = R_1 + R_2 + R_3

Начальная симплексная таблица

Начальная базисная переменная будет ( \( R_1, R_2, R_3 \) ) со значениями:

\[ \begin{array}{c|c|c|c|c|c|c|c|c} & x_1 & x_2 & u_1 & u_2 & u_3 & R_1 & R_2 & R_3 & & \\ \hline R_1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 3 \\ R_2 & -2 & 3 & 0 & 1 & 0 & 0 & 1 & 0 & 8 \\ R_3 & -1 & -1 & 0 & 0 & 1 & 0 & 0 & 1 & 2 \\ \hline W & 0 & 0 & & & & & & & 13 \end{array} \]

Применение симплексного метода

Шаг 1: Определяем ведущий столбец (где наибольший отрицательный значения).

Шаг 2: Определяем ведущую строку (по минимальному отношению свободного члена на коэффициент ведущего столбца).

Рассчитаем и продолжим так, пока не получим оптимальное решение.

Продолжение работы с таблицей

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

\[ \begin{array}{c|c|c|c|c|c|c|c|c} & x_1 & x_2 & u_1 & u_2 & u_3 & R_1 & R_2 & R_3 & & \\ \hline u_1 & 1 & 1 & 1 & 0 & 0 & 0 & -1 & 0 & 3 \\ x_2 & -\frac{2}{3} & 1 & 0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 & 8 \\ x_1 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 2 \\ \hline W & 0 & 0 & & & & & & & 13 \end{array} \]

Таким образом, получаем оптимальное значение функции \(Z = 4x_1 - x_2\) и значения переменных \(x_1\) и \(x_2\) при которых оно достигается.

Ответ

Оптимальное значение переменных:

\[ x_1 = 2, x_2 = 0 \]

Оптимальное значение функции:

\[ Z = 4*2 - 0 = 8 \]