Общая характеристика распределительной задачи

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

Большинство распределительных задач можно представить в виде матриц, приведенных в таблице 5.1.

Элементы Cij, стоящие в клетках матрицы, соответствуют затратам или доходу, отвечающим выделению, одной единицы ресурса Ri на работу Jj. Величины Cij могут быть зависимыми и независимыми.

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

Если затраты (или доход), определяемые объемом Хij ресурса I, выделенного на выполнение работы Ji, равны ХijCij, то имеем линейную распределительную задачу.

Основные методы решения распределительных задач, в частности линейного программирования, построены на допущении, что объемы, имеющихся в наличии ресурсов (bi), требуемые объемы (aj) и затраты (Ci,j) точно известны.

Если общий объем наличных ресурсов Σb_i (i = 1…m) равен общей потребности в них Σa_j (i =1…n), то имеет место сбалансированная (закрытая) распределительная задача. Если же Σa_j ≠ Σb_i, то задача называется несбалансированной (открытой). Если ресурсы можно разделить между работами, то некоторые работы можно выполнять с помощью различных комбинаций ресурсов. Если работы и ресурсы измеряются в единицах одной и той же шкалы, то такие задачи обычно называют транспортными или задачами разложения. Если же работы и ресурсы выражаются в различных единицах измерения, то задача называется общей разделительной задачей. Таким образом, транспортная задача является частным случаем общей распределительной задачи.

Таблица 5.1.

 

Методика выполнения работы

Транспортная задача

Имеется М поставщиков некоторого товара. Количество товара, имеющееся у поставщиков, составляет А₁, А₂,…, А_М единиц. Имеются N потребителей этого товара; их спрос составляет B₁, B₂, …, B_N единиц. Сумма запасов товара, имеющихся у поставщиков, равна сумме величин спроса всех потребителей:

Известны затраты на перевозку единицы товара от каждого поставщика каждому потребителю (стоимости перевозок): C_ij, i =1, …, M, j =1, …, N.

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

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

Пояснить его проще всего будет на конкретном примере:

Пример 5.1. С четырех складов (СК1, СК2, СК3, СК4) доставляется товар в три магазина (МГ1, МГ2, МГ3). На складе СК1 имеется 40 тонн товара, на складе СК2 – 50 тонн, на складе СК3 – 60 тонн, на складе СК4 – 30 тонн. Магазину МГ1 требуется 60 тонн товара, магазину МГ2 – 80 тонн, магазину МГ3 – 40 тонн. Затраты (в ден. ед.), связанные с перевозкой одной тонны товара с каждого склада в каждый магазин, приведены в табл. 5.2.

Таблица 5.2

Склады	Магазины
МГ1	МГ2	МГ3
СК1
СК2
СК3
СК4

 

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

Данную задачу можно представить как задачу линейного программирования. Для построения математической модели этой задачи введем переменные X_ij, i =1,…,4, j=1,…,3, обозначающие количество товара, перевозимого с i-го склада в j-й магазин.

На складах имеется 180 единиц товара; магазинам требуется также 180 единиц товара. Поэтому для удовлетворения спроса всех магазинов потребуется вывезти со складов весь товар. Ограничения, выражающие это требование, имеют следующий вид:

 

x₁₁ + x₁₂ + x₁₃ = 40

x₂₁ + x₂₂ + x₂₃ = 50

x₃₁ + x₃₂+ x₃₃ = 60

x₄₁ + x₄₂ + x₄₃= 30.

 

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

 

x₁₁ + x₂₁ + x₃₁+ x₄₁= 60

x₁₂ + x₂₂+ x₃₂ + x₄₂= 80

x₁₃ + x₂₃ + x₃₃ + x₄₃= 40.

 

Так как переменные обозначают количество перевозимого товара, на них накладывается требование неотрицательности:

x _ij³0, i =1,…,4, j=1,…,3.

Целевая функция представляет собой затраты на выполнение всех перевозок:

Е = 4x₁₁ + 3x₁₂+ 5x₁₃ + 6x₂₁ + 2x₂₂ + 1x₂₃ + 10x₃₁ + 4x₃₂+ 7x₃₃ + 8x₄₁ + 6x₄₂ + +3x₄₃ ® min.

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

При решении транспортной задачи удобно пользоваться расчетной таблицей, содержащей стоимости перевозок, запасы товара у поставщиков и величины спроса потребителей. По ходу решения задачи в нее заносятся величины перевозок (значения переменных x_ij), а также вспомогательные величины, используемые для решения задачи. Расчетная таблица для примера 5.1 показана в табл 5.3.

 

Таблица 5.3

Склады	Магазины
МГ1	МГ2	МГ3
СК1
СК2
СК3
СК4

 

Решение транспортной задачи включает два этапа:

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

· поиск оптимального решения, т.е. плана перевозок и минимальными затратами.

 

 

 

 

 

 

Порядок выполнения работы

1. Изучить теоретическую часть.

2. Решить транспортную задачу.