Распределительная задача

Многие задачи линейного программирования, встречающиеся при решении вопросов планирования, могут быть сведены к задаче, одна из многочисленных экономических интерпретаций которой такова. Имеется т видов сырья в количествах единиц. Существуют п пунктов производства, в которых любой вид этого сырья может перерабатываться в готовый продукт, причем на изготовление единицы готового продукта в 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')

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

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

 
< Пред   СОДЕРЖАНИЕ     След >