Решение Задачи Линейного Программирования (ЗЛП)

Мищенко Максим Юрьевич, МетОпт 1.2 K3339

Краткое описание алгоритма решения ЗЛП

Данная программа реализует двухфазный симплекс-метод для решения задач линейного программирования (ЗЛП) с использованием библиотеки numpy для матричных операций.

Общая схема алгоритма (псевдокод)

Функция РешитьЗЛП(целевая_функция, ограничения, тип_оптимизации):

1. Стандартизация_Задачи(): a. Преобразовать все ограничения к виду равенств:

• LHS <= RHS -> LHS + s_i = RHS (добавить переменную ослабления s_i >= 0).
• LHS >= RHS -> LHS - e_i = RHS (вычесть переменную избытка e_i >= 0).
• LHS = RHS (без изменений). b. Все переменные должны быть неотрицательными (x_i >= 0). c. Ввести искусственные переменные (a_j >= 0) в каждое ограничение, где нет очевидной базисной переменной (т.е., для всех ограничений типа = и >= после приведения к равенствам). d. Сформировать начальную симплекс-таблицу, содержащую:
• Матрицу коэффициентов ограничений (с оригинальными, ослабления, избытка, искусственными переменными).
• Вектор правых частей (RHS).
• Строку целевой функции Фазы 1 (Z_p1).
• Строку целевой функции Фазы 2 (Z_p2 - исходная целевая функция).

2. Фаза 1: Поиск допустимого базисного решения a. Целевая функция Фазы 1 (Z_p1) формулируется как минимизация суммы искусственных переменных. b. Повторять (Итерации Симплекс-метода): i. Найти входящую переменную (ведущий столбец): Выбрать столбец с самым отрицательным коэффициентом в строке Z_p1. Если все коэффициенты неотрицательны, перейти к шагу c. ii. Найти выходящую переменную (ведущая строка): Используя тест минимальных отношений (RHS / коэффициент входящей переменной) для всех строк с положительным коэффициентом входящей переменной. iii. Выполнить операцию поворота (Pivot): Преобразовать таблицу так, чтобы ведущий элемент стал 1, а остальные элементы в ведущем столбце стали 0. c. Проверить результат Фазы 1: - Если оптимальное значение Z_p1 больше нуля (т.е., сумма искусственных переменных не стала нулем), то исходная ЗЛП не имеет допустимых решений. Завершить. - Если оптимальное значение Z_p1 равно нулю, то найдено допустимое базисное решение. Перейти к Фазе 2.

3. Переход к Фазе 2: Решение основной задачи a. Удалить строку Z_p1 из таблицы. b. Удалить столбцы, соответствующие искусственным переменным (если они не находятся в базисе с нулевым значением). c. Перестроить симплекс-таблицу, обновив индексы базисных переменных. d. Убедиться, что коэффициенты базисных переменных в строке Z_p2 обнулены (путем вычитания соответствующих строк ограничений).

4. Фаза 2: Решение основной задачи a. Использовать исходную целевую функцию (Z_p2). b. Повторять (Итерации Симплекс-метода): i. Найти входящую переменную (ведущий столбец): Выбрать столбец с самым отрицательным коэффициентом в строке Z_p2. Если все коэффициенты неотрицательны, перейти к шагу c. ii. Найти выходящую переменную (ведущая строка): Используя тест минимальных отношений. Если все отношения бесконечны (или отрицательны), целевая функция неограничена. Завершить. iii. Выполнить операцию поворота (Pivot). c. Если все коэффициенты в строке Z_p2 неотрицательны, найдено оптимальное решение.

5. Извлечение решения: a. Считать значения оригинальных переменных (x_i) из столбца RHS для соответствующих базисных строк. b. Вычислить значение целевой функции в оптимальной точке. c. Записать результат.

Демонстрация работы программы

запуск

python lp_solve.py

Вариант задания:

Максимизировать $Z = 2x_1 + 3x_2 + x_3 + 4x_4$ при условиях: $x_1 + x_2 + x_3 + x_4 \le 10$ $2x_1 + x_2 - x_3 + x_4 = 8$ $x_2 + 2x_3 + x_4 \ge 5$ и $x_i \ge 0$ для всех $i=1,2,3,4$.

Содержимое файла lp_problem.txt:

MAX
2 3 1 4
<= 10
1 1 1 1
= 8
2 1 -1 1

--- Starting Phase 1 ---
Phase 1 - Iteration 1: Objective (sum of artificials) is zero. Moving to Phase 2.
--- Starting Phase 2 ---
Phase 2 - Iteration 1
Phase 2 - Iteration 2
Phase 2 - Iteration 3
--- Phase 2 complete. Extracting solution ---
Задача успешно решена!
Оптимальная точка x: [0. 6. 1.5 0.5]
Значение целевой функции в оптимальной точке: 24.5

Рефлективный вывод

Работа над этой задачей была очень познавательной. Основной полезный вывод – глубокое понимание внутренней механики симплекс-метода, особенно двухфазной его реализации, которая требуется для обработки ограничений равенства и "больше или равно". Обычно при использовании готовых библиотек эти детали скрыты. Было интересно увидеть, как абстрактные математические концепции (базисные переменные, операция поворота, тест минимальных отношений) преобразуются в конкретные матричные операции с помощью numpy.

1. Сложность стандартизации задачи: Первоначальное преобразование ЗЛП в каноническую форму, добавление переменных ослабления, избытка и искусственных, а также корректное формирование начальной симплекс-таблицы (особенно Z-строк для Фазы 1 и Фазы 2) оказалось наиболее трудоемким этапом. Это требовало очень внимательного отслживания индексов и логики.
   • Преодоление: Многократное ручное прохождение примера на бумаге, тщательная проверка размерностей массивов numpy и пошаговая отладка с выводом self.tableau на каждой стадии.
2. Переход между Фазами 1 и 2: Корректное удаление столбцов искусственных переменных и соответствующее ремаппирование индексов базисных переменных для новой, уменьшенной таблицы Фазы 2 было значительным вызовом. Ошибки индексации были частыми.
   • Преодоление: Разделение задачи на более мелкие функции, постоянная проверка состояния таблицы и индексов после каждого преобразования. Использование явных списков non_artificial_cols и basis_variable_indices для отслеживания изменений.
3. Численная стабильность: Проблемы с числами с плавающей запятой (сравнение с нулем, деление на очень малые числа) приводили к непредсказуемым результатам или ошибкам.
   • Преодоление: Активное использование допусков (1e-9) при сравнениях с нулем, особенно в _find_entering_variable, _find_leaving_variable и _pivot.
4. Обработка краевых случаев: Определение неограниченности или недопустимости решения требовало внимания к деталям условий выхода из циклов симплекс-метода.
   • Преодоление: Использование явных флагов статуса и соответствующих сообщений, возвращаемых методом solve.

Рабта продемонстрировала, насколько сложна ручная реализация даже относительно "простого" алгоритма, когда нужно учитывать все его аспекты, и насколько ценными являются готовые и протестированные библиотеки для реальных задач.