2.1. Введение

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

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

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

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

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