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

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

Раздел: Линейное программирование, Симплекс-метод

Шаг 1: Приведение задачи к каноническому виду

Заданная задача:
Z = -3x_1 - x_2 \to \min
при ограничениях:
 \begin{cases} 4x_1 - x_2 \geq 0, \ 2x_1 - x_2 \leq 0, \ x_1 + x_2 \leq 3, \ x_1, x_2 \geq 0. \end{cases} 

Приведение ограничений к каноническому виду

1. Неравенство 4x_1 - x_2 \geq 0 преобразуем, введя избыточную переменную s_1 \geq 0:
   4x_1 - x_2 - s_1 = 0
2. Неравенство 2x_1 - x_2 \leq 0 преобразуем, введя дополнительную переменную s_2 \geq 0:
   2x_1 - x_2 + s_2 = 0
3. Неравенство x_1 + x_2 \leq 3 преобразуем, введя дополнительную переменную s_3 \geq 0:
   x_1 + x_2 + s_3 = 3

Целевая функция

Преобразуем минимизацию в максимизацию:
Z' = 3x_1 + x_2 \to \max

Каноническая форма

 \begin{cases} 4x_1 - x_2 - s_1 = 0, \ 2x_1 - x_2 + s_2 = 0, \ x_1 + x_2 + s_3 = 3, \ x_1, x_2, s_1, s_2, s_3 \geq 0. \end{cases} 

Шаг 2: Построение начальной симплекс-таблицы

Шаг 3: Итерации симплекс-метода

1. Выбор разрешающего столбца

   • В строке Z' наибольший отрицательный коэффициент — у x_1 (-3), значит, он входит в базис.

2. Выбор разрешающей строки

   • Для определения разрешающей строки вычисляем отношения \frac{b_i}{a_{ij}} (только для положительных коэффициентов в столбце x_1):
     • \frac{0}{4} = 0
     • \frac{0}{2} = 0
     • \frac{3}{1} = 3
   • Минимальное положительное значение — 3, значит, разрешающая строка — третья (переменная s_3 выходит из базиса).

3. Приведение разрешающего элемента к 1 и обнуление остальных элементов в столбце

   • Разрешающий элемент: a_{31} = 1
   • Делим третью строку на 1 (не изменится).
   • Обнуляем остальные элементы в столбце x_1.

После нескольких итераций (продолжим по алгоритму), получим оптимальное решение.

Ответ

Оптимальное решение:
x_1 = 0, x_2 = 3
Оптимальное значение целевой функции:
Z = -3(0) - 3 = -3