Markets-Web.ru

Перейдем к рассмотрению конкретных прикладных задач маркетинга, решаемых на основе оптимизационных моделей.

Статическая модель оптимизации прикрепления потребителей к поставщикам.

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

В т пунктах отправления (А1, А2 . Ат), которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим ai (i = 1, 2 . m).

Данный продукт потребляется в n пунктах (В1, B2 . Вn), которые будем называть потребителями; объем потребления обозначим через bj (j = 1, 2 . n).

Известны расходы на перевозку единицы продукта из пункта Аi в пункт Вj, которые равны cij и приведены в матрице транспортных расходов С = (сij).

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

Обозначим количество продукта, перевозимого из пункта Ai в пункт Bj, через Хij. Совокупность всех переменных хij для краткости обозначим символом , тогда целевая функция задачи приобретет вид:

А ограничения выглядят следующим образом:

Условия (25.31) означают полное удовлетворение спроса во всех пунктах потребления; условия (25.30) определяют больший вывоз продукции от всех поставщиков.

Необходимым и достаточным условием разрешимости задачи (25.29) – (25.31) является условие баланса:

Транспортная задача, в которой имеет место равенство (25.32), называется закрытой и в качестве ЗЛП может быть решена с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения.

Чаще всего применяется метод потенциалов, при котором каждой i-й строке (i-му поставщику) устанавливается потенциал Ui, который можно интерпретировать как цену продукта в пункте поставщика, а каждому столбцу j (j-му потребителю) устанавливается потенциал Vj, принимаемый условно за цену продукта в пункте потребителя. В простейшем случае цена продукта в пункте потребителя равна его цене в пункте поставщика плюс транспортные расходы на его доставку, т.е.:

Vj = Ui + cij. (25.33)

Алгоритм метода потенциалов для закрытой транспортной задачи детально описан в ряде учебных пособий*.

* См.: Экономико-математические методы и прикладные модели. Учебное пособие для вузов/Под ред. В.В. Федосеева. – М.: ЮНИТИ, 1999.

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

Если баланс (25.32) не выполняется, то ограничения (25.30) или (25.31) имеют вид неравенств типа «меньше или равно»; транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода или фиктивного потребителя, если в неравенства превращаются условия (25.30), или фиктивного поставщика в случае превращения в неравенства ограничений (25.31).