На базе линейной алгебры.

В предыдущей лекции нами приведена таблица 6.2, мы приведём её снова для того, чтобы выполнить анализ задачи с точки зрения её решения методами линейной алгебры, которые мы специальным образом дополним.

Предметом интересов линейной алгебры является исследование и решение систем линейных уравнений. Представления о линейной алгебре полезны для понимания методов линейного программирования.

Для удобства работы повторим приведенную ранее табличную матрицу 6.3.

под номером 7.1,

Таблица 7.1.

Распределительная таблица

На основе распределительной таблицы можно составить 10 уравнений:

Система относится к классу неопределённых, поскольку число неизвестных больше, чем число уравнений.

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

Решением системы называется совокупность значений неизвестных, при подстановке которых все уравнения системы обращаются в тождества.

Система, имеющая хотя бы одно решение, называется совместной, система, не имеющая ни одного решения, - несовместной. Система, имеющая единственное решение, называется определённой; система, имеющая более одного решения, - неопределённой. Чтобы определить тип системы надо провести исследование системы уравнений.

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

Универсальным методом исследования и одновременно решения системы линейных уравнений является метод Жордана-Гаусса, алгоритм которого построен на преобразовании системы с последовательным исключением переменных (неизвестных.) из каждого, входящего в систему, уравнения, вплоть до такого её вида, когда в каждом уравнении остаётся только одна неизвестная, а это и означает решение системы.

В изложенной постановке задачи субъект управления транспортом должен, во-первых, выполнить задание по перевозкам. Во-вторых, он заинтересован в снижении своих издержек в целом. При невыполнении первого условия задача просто не будет считаться решённой. Второй вопрос - это выбор критерия эффективности для искомого плана (стратегии). В качестве такого критерия можно принять минимум издержек при реализации плана перевозок. Численное значение такого критерия названо целевой функцией Z

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

Таблица 7.3

(Нулевая версия) Z₀ = 1332

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

Рассматриваемая задача линейного программирования относится к категории закрытых транспортных задач, в которых количество предоставляемых ресурсов всегда равно количеству потребностей. Нулевая версия решения получена путём подбора данных и носит чисто иллюстративный характер.

Для упорядочения порядка решения методами линейной алгебры введём систему приоритетов, и рассмотрим две версии алгоритмов решения.

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

Версия 2. Предоставим такую последовательность клиентов для выбора корреспонденций, при которой, очередь клиентов идёт в порядке возрастания количественной меры потребности. Такой вариант может иметь место при желании сохранить клиентуру, которая испытывает временные трудности.

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

Версия 1 Z₁ = 1000

Версия 2 Z₂ = 1040

Представленные два варианта решения на получены на базе линейной алгебры. И для оценки решения была использована целевая функция, которая оценивает затраты на перевозки. Предложенный алгоритм построен на основе введения принципа поочерёдного удовлетворения потребностей в перевозках за счет последовательного предложения ресурсов. Сама последовательность выбрана на основе принципов, которые однозначно приводят к решению поставленной задачи. Возможность введения тех или иных принципов расчёта в исследовании операций определяется характером задачи.

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

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

С другой стороны это позволяет нам перейти к рассмотрению известного алгоритма распределения обозначенного как «транспортная задача» линейного программирования

Дата добавления: 2014-01-05