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

Постановка задачи

• Целевая функция: Что необходимо максимизировать или минимизировать? Запишите ее в виде линейной комбинации переменных. Например: max Z = 3x + 2y
• Ограничения: Какие ограничения накладываются на переменные? Запишите их в виде системы линейных неравенств или равенств. Например:x + y ≤ 5
  2x - y ≥ 3
  x ≥ 0, y ≥ 0 (неотрицательность переменных)
  

Пример задачи

Задача:Максимизировать функцию Z = 3x + 2y при ограничениях:

• x + y ≤ 5
• 2x - y ≥ 3
• x ≥ 0, y ≥ 0

Решение:

1. Приведение к стандартному виду:Вводим искусственные переменные для преобразования неравенств в равенства.
   
   Получаем систему уравнений:x + y + s₁ = 5
   2x - y - s₂ + a₁ = 3
   Z - 3x - 2y = 0 (целевая функция в виде уравнения)
   s₁, s₂ - искусственные переменные, a₁ - искусственная базисная переменная.
   
2. Составление начальной симплексной таблицы:| Базис | x | y | s₁ | s₂ | a₁ | Z | |---|---|---|---|---|---|---| | s₁ | 1 | 1 | 1 | 0 | 0 | 0 | 5 | | a₁ | 2 | -1 | 0 | -1 | 1 | 0 | 3 | | Z | -3 | -2 | 0 | 0 | 0 | 1 | 0 |
3. Итерации симплекс-метода:Выбираем разрешающий столбец (с наибольшим по модулю отрицательным числом в строке Z).
   Вычисляем отношения свободных членов к положительным элементам разрешающего столбца и выбираем минимальное положительное отношение. Это будет разрешающая строка.
   Выполняем элементарные преобразования строк таблицы, чтобы на пересечении разрешающего столбца и разрешающей строки получить единицу, а остальные элементы в разрешающем столбце сделать нулями.
   Повторяем шаги 3-4 до тех пор, пока в строке Z не останется отрицательных чисел.
   
4. Оптимальное решение:Коэффициенты при базисных переменных в строке Z дают значения этих переменных в оптимальном решении.
   Свободный член в строке Z дает значение целевой функции в оптимуме.