§ 2. Задачи размещения и специализации

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

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

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

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

Введем переменные

Тогда наша задача сведется к минимизации

при условиях

и

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

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

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

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

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

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

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

и минимизирующий суммарные затраты

Эта задача отличается от классической транспортной задачи лишь тем, что вместо обычного баланса производства и потребления мы имеем неравенство (2.5). В силу этого в условии (2.6) вместо равенств фигурируют неравенства.

Решение задачи (2.6) — (2.7) никаких затруднений не вызывает, ибо при помощи общеизвестного приема (введение фиктивного потребителя) она сводится к транспортной. Оптимальный план этой задачи дает следующую информацию:

1) список реальных поставщиков (множество всех тех для которых величины

отличны от нуля);

2) плановые мощности этих поставщиков (отличные от нуля

3) схему прикрепления поставщиков к потребителям (сами числа

В ряде случаев к условиям (2.6) — (2.7) могут присоединяться дополнительные ограничения, не меняющие

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

(объем производства в данном пункте не должен быть ниже заданного) и т. п.

Задача (2.6) — (2.7) включена в наш перечень дискретных моделей по чисто формальным причинам, которые были подробно объяснены в § 1 гл. 2 (целочислен-ность оптимальных планов транспортной задачи). Однако некоторые дальнейшие обобщения этой схемы уже приводят к дискретным задачам в собственном смысле слова. Одним из наиболее непосредственных обобщений такого рода является описывавшаяся ранее транспортная задача с фиксированными доплатами (см. § 5 гл. 2). Напомним, что она заключается в минимизации функции

где

при условиях (2.6). Экономически модель (2.9), (2.10), (2.6) естественно интерпретировать, например, как «размещение в условиях бездорожья»; под в этих условиях можно понимать стоимости перевозок, а под стоимости строительства дорог между производителями и потребителями Сведение этой задачи к целочисленной демонстрировалось в § 5 гл. 2.

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

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

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

Тогда наша цель будет заключаться в минимизации целевой функции вида (2.7) при условиях

Здесь из (2.11) и (2.14) сразу следует, что для каждого только одно равно единице, а остальные равны нулю. Номер А, соответствующий этому у указывает проектный вариант мощности, принимаемый для данного пункта производства условие (2.13) здесь является прямым аналогом обычного условия 2 в открытой транспортной задаче.

Отметим, что эта задача сходна с задачей реконструкции, описанной в п. 2.1; в частности, условие (2.14) здесь играет роль условия (2.4) задачи реконструкции.

Как и там, в этой модели условия (2.14) могут быть (для некоторых или для всех заменены неравенствами

экономический смысл последних ясен непосредственно.

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

где функции описывают затраты на строительство пункта производства при объеме производства и. Сначала рассмотрим случай неоднородных зависимостей вида

Экономический смысл (2.16) довольно прозрачен. Будем предполагать, что структура затрат (2.15) имеет место в условиях обычной открытой транспортной модели размещения, описанной в п. 2.2. Применим уже известный нам прием, использованный при рассмотрении транспортной задачи с фиксированными доплатами (§ 5 гл. 2). Легко убедиться, что минимизация целевой функции (2.15), где имеет вид (2.16), при условиях (2.6) эквивалентна минимизации

при условиях

и

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

2.5. Можно еще усложнить последнюю модель, предположив (как и в п. 2.3), что для каждого имеется вариантов строительства с производительностями Пусть теперь затраты на строительство поставщика описываются функциями зависящими также от номера проектного варианта причем эта зависимость имеет вид

(иначе говоря, здесь от номера зависят только фиксированные доплаты на строительство, а пропорциональная часть одна и та же для всех вариантов). Тогда, вводя, согласно (2.11), дополнительные переменные мы будем иметь ограничения (2.12), (2 13) и (2.14), а целевая функция примет вид

что в силу (2.14) равно

2.6. Перенесем теперь описанную в п. 2.3 модель на случай нелинейной целевой функции общего вида. Пусть суммарные затраты имеют следующую структуру:

Речь идет о минимизации (2.22) при условиях (2.12) - (2.14). В практических задачах функция вида (2.22) обычно оказывается вогнутой. С экономической точки зрения это означает, что с ростом объема производства удельные затраты на его дальнейшее увеличение сокращаются. Поэтому задача (2.22), (2.12) — (2.14) выпадает из рамок выпуклого целочисленного программирования и становится многоэкстремальной задачей. В данном случае ввиду того, что объемы производства в каждом пункте могут принимать лишь конечное число значений ее рассмотрение оказывается весьма простым. Именно, для каждого пункта производства найдем значение затрат при объеме производства:

после чего целевую функцию (2.22) можно будет выразить в виде

Окончательно задача сводится к минимизации (2.22) при условиях (2.12) -(2.14).

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

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

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

Введем обозначения

Тогда целевую функцию (2.22) можно приближенно представить формулой

При этом в силу невыпуклости исходной целевой функции переменные должны быть подчинены еще некоторым дополнительным условиям, смысл которых был подробно объяснен в § 6 гл. 2. Именно, следует ввести еще один набор дополнительных переменных

и наложить дополнительные ограничения

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