Распределительная задача. 
Проектирование логистических систем

Многие задачи линейного программирования, встречающиеся при решении вопросов планирования, могут быть сведены к задаче, одна из многочисленных экономических интерпретаций которой такова. Имеется т видов сырья в количествах единиц. Существуют п пунктов производства, в которых любой вид этого сырья может перерабатываться в готовый продукт, причем на изготовление единицы готового продукта в j-м пункте производства идет aij единиц сырья i-го вида. Заданы количества единиц продукта, которые должны быть изготовлены на каждом из пунктов производства. Пусть - количество продукта, изготавливаемое в j-м пункте производства из сырья i-го вида, а - стоимость изготовления единицы продукта этим способом.

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

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

(4.13).

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

(4.14).

а все неизвестные должны быть неотрицательными:

(4.15).

Стоимость производства, определяемая планом , выражается формулой.

(4.16).

Таким образом, приходим к следующей математической формулировке задачи: найти минимум линейной функции (4.16) при ограничениях (4.13)-(4.15), накладываемых на неизвестные.

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

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

(4.17).

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

(4.18).

При этом следует считать перевозки неотрицательными:

(4.19).

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

(4.20).

Итак, требуется найти минимум линейной функции (4.20) при условиях (4.17)-(4.19). Эта постановка несколько отлична от ранее приведенной. Однако если ввести замену переменных и обозначить , то задача сведется к отысканию минимума линейной функции.

(4.16').

при условиях.

(4.13').

(4.14').

(4.15').

что с точностью до обозначений совпадает с ранее сформулированной распределительной задачей.

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