Линейное программирование (ЛП)

раздел теории экстремальных задач, в котором изучаются задач и минимизации (или максимизации) линейных функций на множествах, задаваемых системами линейных равенств и неравенств.

Формулировка задачи ЛП (общий случай): найти вектор х* (x* ₁ ,..., х*_n), определяющий максимум (минимум) линейной форме f(x) с₁x₁ + с₂x₂+...+с_nx_nпри ряде ограничений.

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

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

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

2 Транспортная задача линейного программирования (частный тип задачи ЛП) широко распространены в практике. К ним сводятся многие другие задачи ЛП - задачи о назначениях, сетевые, календарного планирования.

Замкнутая транспортная модель: требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок.

Открытая транспортная модель: не требуется, чтобы весь произведенный продукт в каждом пункте производства был реализован.

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

Открытая транспортная модель может быть приведена к замкнутой модели добавлением фиктивного пункта отправления (потребления), от которого поступает весь недостающий продукт или в который свозится весь избыточный запас. Стоимость перевозок между реальными пунктами и фиктивным принимается равной нулю.

Венгерский метод: строится начальный план перевозок, не удовлетворяющий в общем случае всем условиям задачи (из некоторых пунктов производства не весь продукт вывозится, потребность части пунктов потребления не полностью удовлетворена). Далее осуществляется переход к новому плану, более близкому к оптимальному. Последовательное применение этого приема за конечное число итераций приводит к решению задачи.

Наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины /2 ( - суммарная невязка подготовительного этапа).

Достоинство: возможность оценивать близость результата каждой из итераций к оптимальному плану перевозок.

Метод потенциалов

- модификация симплекс-метода решения задачи ЛП применительно к транспортной задаче. Позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций.