Задача линейного программирования без учета целочисленности

Первый алгоритм Гомори. Алгоритм Гомори для полностью целочисленных задач включает в себя следующие этапы: Решается задача линейного программирования без учета целочисленности. Среди дробных чисел выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной. Полученная задача решается двойственным симплекс-методом.

Классификация задач математического программирования Задачи математического программирования классифицируются в зависимости от вида целевой функции и свойств допустимой области ограничений G. К ним относятся задачи: нелинейного программирования, линейного программирования, целочисленного программирования, дробно-линейного программирования, параметрического программирования, сепарабельного программирования, квадратичного программирования, динамического программирования, стохастического программирования, геометрического программирования и другие.

Первая и вторая теоремы двойственности ЛП. Первая теорема двойственности. Если одна задача из пары двойственных обладает оптимальным решением, то и другая имеет оптимальное решение, причем экстремальные значения соответствующих целевых функций равны Если же у одной из этих задач целевая функция не ограничена, то двойственная ей задача не имеет допустимых решений. Наконец, если одна из этих задач не имеет допустимых решений, то двойственная ей задача либо также не имеет допустимых решений, либо имеет неограниченную целевую функцию.