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

Покупательский спрос математический программирование

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

Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи -- это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д.

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

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

Метод потенциалов относится к группе методов последовательного приближения. Вначале отыскивается исходный допустимый план перевозок, который, как плавило, не является оптимальным, а затем по определенной итеративной процедуре этот план доводится до оптимального варианта.

Решение транспортной задачи методом потенциалов

Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены.

Пусть имеется транспортная задача с балансовыми условиями

Стоимость перевозки единицы груза из Ai в Bj равна C ij; таблица стоимостей задана. Требуется найти план перевозок xij, который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок бала минимальна.

Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления Ai вносит за перевозку единицы груза (все равно куда) какую-то сумму бi ; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму вj. Эти платежи передаются некоторому третьему лицу ("перевозчику"). Обозначим ai + bj = иij ( i=1..m; j=1..n) и будем называть величину иij "псевдостоимостью" перевозки единицы груза из Ai в Bj. Заметим, что платежи бi и вj не обязательно должны быть положительными; не исключено, что "перевозчик" сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (бi и вj) одна и та же и от плана к плану не меняется.

До сих пор мы никак не связывали платежи (бi и вj) и псевдостоимости иij с истинными стоимостями перевозок Cij. Теперь мы установим между ними связь. Предположим, что план xij невырожденный (число базисных клеток в таблице перевозок ровно m + n -1). Для всех этих клеток xij>0. Определим платежи (бi и вj) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:

Иij=бi+вj=сij, при xij>0.

Что касается свободных клеток (где xij=0), то в них соотношение между псевдостоимостями и стоимостями может быть, какое угодно.

Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана xij>0,

Бi+вj=иij=сij,

А для всех свободных клеток xij=0,

Бi+вj=иij?сij,

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

Иij= сij (для всех базисных клеток) (2.36)

Иij ? сij (для всех свободных клеток) (2.37)

Называется потенциальным планом, а соответствующие ему платежи (бiи вj) -- потенциалами пунктов Ai и Bj (i=1,...,m; j=1,..., n). Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так:

Всякий потенциальный план является оптимальным.

Похожие статьи




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

Предыдущая | Следующая