Прикладных задач в транспортных системах

Использование методов линейного программирования для решения

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

Эти методы позволяют описать с достаточной точностью широкий круг задач коммерческой деятельности, таких, как:

· планирование товарооборота,

· размещение розничной торговой сети города,

· планирование товароснабжения города,

· прикрепление торговых предприятий к поставщикам,

· организация рациональных перевозок товаров (транспортная задача),

· распределение работников торговли по должностям (задача о назначении).

· организация рациональных закупок продуктов питания (задача о диете).

· распределение ресурсов,

· планирование капиталовложений,

· оптимизация межотраслевых связей,

· замена торгового оборудования,

· определение оптимального ассортимента товаров в условиях ограниченной площади,

· установление рационального режима работы.

В задачах ЛП критерий эффективности и функции в системе ограничений линейны.

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

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

Общая задача линейного программирования.

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

В целом экономико-математическая формулировка и модель общей задачи ЛП имеют следующий вид:

найти максимальное (минимальное) значение линейной ЦФ

(1)

при условиях-ограничениях:

(2)

(3)

(4)

где - заданные постоянные величины.

Стандартной задачей ЛП называется задача, которая состоит в определении максимального (минимального) значения ЦФ (1) при выполнении условий (2) и (4). (не строгое)

Канонической (или основной) задачей ЛП называется задача, которая состоит в определении максимального (минимального) значения ЦФ (1) при выполнении условий (3) и (4). (строгое)

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

План , при котором ЦФ задачи принимает максимальное (минимальное) значение, называется оптимальным.

Запишем в основной задаче ЛП ограничения (3) в векторной форме:

(5)

где - m-мерные векторы-столбцы, составленные из коэффициентов при

неизвестных и свободных членах системы уравнений задачи.

План называется опорным планом основной задачи ЛП, если система векторов , входящих в разложение (5) с положительными коэффициентами X_j, линейно независима. (см. фото в группе)

Так как векторы являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать m.

Опорный план называется невырожденным, если он содержит ровно m положительных компонент. Если в опорном плане число положительных компонент меньше m, то план является вырожденным.