ИСПОЛЬЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ ЗАТРАТ
Гудович Д.В. (ЛГТУ, г. Липецк, РФ)
This article deals with some ways of finding solutions to transportation problems in classical canonical form and expediency of mathematical methods’ applications for expenditure optimization
Для решения проблем управления затратами на автомобильном транспорте широко применяются задачи линейного программирования. Одна из наиболее распространенных задач математического программирования – транспортная задача. При решении задач линейного программирования, прежде всего, формулируются цели (критерии) управляемой системы. Далее количественно формируется система ограничений по ресурсам. После определения целевой функции и описания системы ограничений находится оптимальное решение. Поскольку в транспортных задачах линейного программирования число неизвестных больше числа уравнений, аналитическое решение их практически невозможно. Часто приходится рассматривать значительное число вариантов перевозок при наличии нескольких отправителей и получателей груза (для грузовых перевозок) и нескольких пунктов отправления или назначения (для пассажирских перевозок). Для решения этих задач необходимо использовать математические методы оптимизации.
Во многих работах по математическому программированию и исследованию операций представлены вопросы решения транспортной задачи в классической постановке (ТЗ). В общей математической форме транспортная задача линейного программирования формулируется следующим образом [1]:
В 
пунктах
отправления 
сосредоточено
определенное количество единиц некоторого однородного продукта, которое
обозначим 
.
Данный продукт потребляется в 
пунктах 
; объем потребления
обозначим 
.
Известны расходы на перевозку единицы продукта из пункта 
в пункт 
, которые равны 
и приведены в
матрице транспортных расходов 
. Требуется составить такой план
перевозок, при котором весь продукт вывозится из пунктов в пункты в соответствии с
потребностью и общая величина транспортных издержек будет минимальной.
Обозначим количество продукта, перевозимого из пункта в пункт , через 
. Тогда целевая
функция задачи имеет вид:
(1)
Ограничения выглядят следующим образом:
1.Полное удовлетворение спроса каждого пункта потребления продуктами из разных пунктов производства:
(2)
2.Весь продукт, произведенный в каждом пункте производства, должен быть вывезен в пункт потребления:
(3)
3.Объемы перевозок – неотрицательные числа:
(4)
Необходимым и достаточным условием разрешимости задачи является соблюдение баланса:
(5) Транспортная задача сводится, таким образом, к минимизации суммарных
затрат (1) при условиях (2) – (4).
В транспортной задаче требуется составить план перевозок, обеспечивающий наиболее экономным путем (то есть при минимальных общих издержках) удовлетворение спроса всех пунктов потребления за счет реализации всего продукта, произведенного пунктами производства. Вместо пунктов производства и потребления соответственно могут рассматриваться пункты отправления и назначения.
В настоящее время известно несколько методов (алгоритмов) решения транспортной задачи линейного программирования. Условно их можно разбить на 2 группы. Одна из групп основана на принципе последовательного улучшения плана, когда выбранный первоначальный план при помощи расчетов улучшается до тех пор, пока он не станет оптимальным. Другая группа основана на методе последовательного сокращения невязок. Одним из методов первой группы является метод потенциалов. Другая группа основана на методе разрешаемых слагаемых [1]. Во многих транспортных организациях рассчитываются маршруты доставки грузов и пассажиров с помощью распределительного метода, дельта-метода, сетевых методов и т.п. Эти задачи часто усложняются разного рода дополнениями и условиями. В частности, такими условиями могут быть [1]:
1.Невозможность поставок некоторым потребителям продукции определенных поставщиков (или закрепления той или иной клиентуры за некоторыми автотранспортными предприятиями) по дорожным условиям, из-за договорных отношений, ввиду специальных требований к продукции или подвижному составу;
2.Наличие груза (автомобилей) и спрос на них не являются сбалансированными;
3.Возможность взаимозаменяемости автомобилей различных марок;
4.Размещение автомобилей разных марок на автотранспортном предприятии;
5.Необходимость доставить груз в минимальное время.
Недостатком транспортной задачи ТЗ является то, что модель перевозок не учитывает неоднородность грузов и транспортных средств. Неоднородность перевозимых грузов и типы автотранспортных средств можно учесть путем рассмотрения многоиндексных транспортных задач. Реализация данных задач обеспечивается решением трипланарной (Т-3Р) и триаксиальной (Т-3А) транспортных задач. Их решение позволяет получить оптимальный план транспортировки разных типов грузов разными типами автотранспортных средств. Системы ограничений транспортного типа и интеграция опорных планов многоиндексных транспортных задач в терминах теории гиперграфов представлены в работе [2].
Теория многоиндексных задач линейного программирования в общем виде наиболее полно изложена в работе Раскина Л.Г., Кириченко И.О. [2]. Авторы исследуют основные свойства многоиндексных задач линейного программирования, анализируют возможность их сведения к решению задач линейной индексности, исследуют вырожденность и совместность систем ограничений.
Таким образом, на автомобильном транспорте применимы рассмотренные выше задачи линейного программирования, позволяющие более быстро и точно находить наиболее выгодные варианты перевозок грузов и пассажиров, использования ресурсов и т.п.
Т-3Р представляет собой задачу составления плана транспортировки однородного продукта от центров производства к центрам потребления с использованием транспортных средств различных типов, реализация которого обеспечила бы минимальные транспортные издержки.
Решение задач данного типа освещается в литературе и включает исследование на разрешимость задачи Т-3Р, обоснование критериев оптимальности и вырожденности, использование метода потенциалов для решения такого рода задач. В качестве основного метода решения задачи Т-3Р предлагается метод потенциалов.
При разработке алгоритма решения трипланарной транспортной задачи основную трудность составляет проблема разрешимости задачи и связанная с ней проблема построения начального опорного плана. Для выявления неразрешимых задач Хели К. предложена рекуррентная процедура для отсева некорректно сформулированных задач и построения начального плана. Классический прием для ее решения предложен Хели К. и Верховским Б.С.
Второй важной проблемой в многоиндексных транспортных
задачах является проблема вырожденности. Применение классического приема для
исключения вырожденности, предложенного Верховским Б.С., не может быть
использовано для решения задач большой размерности. Более целесообразным
следует считать способ, основанный на обобщении оригинального 
-приема,
предложенного Юдиным Д.Б. и Гольштейном Е.Г. [3] применительно к двухиндексной
транспортной задаче.
В ряде работ исследуется проблема целочисленности в многоиндексных транспортных задачах. Излагаются алгоритмы решения трипланарной и триаксиальной транспортных задач, основанные на методах: эффективного перебора вариантов; теории транспортных сетей. Ставится проблема вычислительной сложности целочисленных транспортных моделей, в связи с чем известные алгоритмы точного решения целочисленных многоиндексных задач применимы лишь для решения задач относительно малой размерности.
При транспортировке грузов или пассажиров возникает множество проблем. Основная проблема автотранспортных организаций кроется в нерациональном использовании имеющегося в наличии подвижного состава с целью транспортировки пассажиров и грузов. Все это ведет к увеличению затрат на перевозку. Проведенные нами исследования показывают, что при осуществлении перевозок затраты возрастают с увеличением расстояния. Это обусловлено тем, что переменные затраты, зависящие от пробега автомобилей (затраты на топливо, амортизация подвижного состава, затраты на восстановление износа и ремонт автомобильных шин и т.п.), составляют значительную долю в общей сумме затрат. Следовательно, обоснована постановка задачи определения оптимального плана перевозок с минимальными затратами с учетом имеющихся в наличии видов автотранспортных средств.
Проведенный анализ теоретических подходов и эволюции научных взглядов на содержание и инструменты управления затратами показал, что многие вопросы не характеризуются однозначностью их решения. Особенно то относится к разработке комплекса моделей и методов управления затратами автотранспортных предприятий, ориентированных на решение важных прикладных задач анализа, моделирования, оптимизации и механизмов принятия управленческих решений.
Учитывая специфику работы автомобильного транспорта были проанализированы возможности использования различных моделей для принятия управленческих решений и произведена их классификация в системе управления затратами по следующим признакам: по содержанию, по фактору времени, по форме представления, по характеру использования информации.
Проведено исследование традиционных методов линейного программирования, вопросов решения транспортной задачи в классической постановке, проблем трехиндексных транспортных задач, на основании которого аргументирована целесообразность их решения для оптимизации затрат.
Литература
1. Геронимус Б.Л. Экономико-математические методы в планировании на автомобильном транспорте / Б.Л.Геронимус. – М.: Транспорт. 1988. – 160 с.
2.Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования (теория, методы, приложения) / Л.Г.Раскин, И.О.Кириченко. – М.: Радио и связь, 1982. – 240 с.
3.Юдин Д.Б., Гольштейн Е.Г. Задачи линейного программирования транспортного типа / Д.Б.Юдин, Е.Г.Гольштейн. – М.: Наука, 1969. – 535 с.