Статические модели задачи размещения

где

(1)

при словиях

а , (2)

а (3)

а (4)

Если все , то задача становится обычной транспортной задачей линейного программирования. В рассматриваемой задаче предполагается, что не все . В этом случае функционал (1) представляет собой разрывную функцию, обладающую, вообще говоря, большим числом точек минимума над областью (2) - (4).

Предполагается также, что либо адля всех , либо ане для всех , так как в случае адля всех получаем задачу размещения с неограниченными объемами производства. Однако необходимо, чтобы суммарный объем потребления <- не превышал сумму верхних

(5)

так как в противном случае никакие значения ане довлетворяют словиям (2) -(4).

Обозначим через аминимальные суммарные затраты при фиксировании некоторого варианта размещения

(6)

при словиях

а , (7)

а (8)

а (9)

Фиксирование некоторого варианта размещения апроизводится тем, что для всех асчитается Для фиксированного со предполагается выполнение словия

(10)

налогичное словию (5).

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

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

Функция ане определена на множестве всех подмножеств , не довлетворяющих словию (10). Для определения функции ана множестве всех поступим следующим образом. Соотнесем пустому подмножеству аусловный пункт производства (). Так как пустое множество содержится в любом , то это означает, что словный пункт производства бундет содержаться в любом подмножестве (варианте размещения) апунктов производства. Поэтому в дальнейшем (чтобы не сложнять записи) под выражением все отличные от нуля значения элементов подмножества , но и само значение 0, соответствующее словному пункту производства. В частности, .

После такого введения словного пункта производства словие (4.10) будет выполняться для любого , так как величина аи поэтому значение атеперь может быть определено для всех . Здесь необходимо отметить, что в силу выбора величин адля тех , для которых условие (10) выполняется лишь с четом , будут сколь годно большими, для тех , для которых это словие выполняется и без чета , наличие словного пункта производства не влияет на величину , т.е. . Отсюда, в частности, следует, что искомое подмножество , для которых

(11)

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

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

где аиа<- произвольные подмножества

Для доказательств рассмотрим вспомогательную функциюа адля всех Можно записать

Таким образом, для каждого

при словиях (7)<-(10).
2. Задача размещения с фиксированными минимальными объемами производства.

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

(12)

при словиях

а , (13)

а (14)

а (15)

где а<- возможный объем производства предприятия .

Предполагается, что

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

аили

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

(16)

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

(17)

при словиях

а , (18)

а (19)

адля (20)

для а

Так как с четом пустого множества для любого авыполняется неравенство

(22)

то методами линейного программирования определяется значение адля любого ва I определяется однозначная функция . Следовательно, задача 2 сводится к определению такого подмножествафункция апринимает свое наименьшее значение, т.е. по всем при словиях (18) - (21). Возможны два случая:

1) , т.е. ааи в этом случае получаем задачу 1;

2) аможно записать агде Ч элементы , расположенные в порядке возрастания
индексов <

В случае 2) рассмотрим задачу отыскания наименьшего значения функционала

(23)

при условиях

а , (24)

а (25)

а (26)

где

а

Значения аопределяются следующим образом.

Для всех

тельное число, но в то же время

Для всех апри любых

Условие этой задачи полностью совпадает с словием задачи 1, и поэтому решение ее сводится к отысканию такого подмножества

3. Задача размещения со ступенчатой функцией стоимости производства.

Постановка этой задачи отличается от постановки задачи 1 другим заданием функций стоимости производства предприятий. В данном случае эта функция задается некоторой ступенчатой разрывной функцией аименно:

(27)

где адля всех а(приадля всех аследует, что апри адля всех

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

(28)

где <- ступенчатая разрывная функция (27) при словиях

а , (29)

а (30)

а (31)

При аполучаем задачу 1.

4. Задачи размещения с ограничениями на суммарную продукцию.

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

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

(32)

при словиях

а , (33)

а (34)

а (35)

(36)

Будем считать, что

,

Рассмотрим вначале задачу (32) -(36). Наиболее интересен случай,

когда

Все остальные предположения о расположении величины d относительно интервала алибо делают задачу несовместной, либо позволяют освободиться от словия (4.53).

Действительно, если

, то ;

при аусловия (33), (34), (36) несовместны; при условие (36)а можно исключить, заменив словия (34) на а

при аусловия (33), (34), (36) несовместны; апри словие (36) можно исключить, заменив словия (35) на а

Для любого аопределение асводится к решению задачи (32)-(36), где везде вместо I пишется d для какого-либо авыйдет из интервала , то, как показано выше, либо условия (33)-(36)а становятся несовместными (в этом случае полагаем ), либо освобождаемся от словия (4.53) и определение асводится к решению транспортной задачи типа 1.

Производственно-распределительные задачи оптимального размещения предприятий и применимость метода последовательных расчетов.

5. Производственно-распределительная задача размещения предприятий с ограниченными объемами производства и пропускными спонсобностями коммуникаций.

Рассматривается задача нахождения наименьшего значения функционала

(37)

при словиях

а (38)

а (39)

(40)

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

агде

при словиях (38)-(40), в которых I заменено на .

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

Для решения сформулированной задачи также применим метод последовательных расчетов.

6. Производствснно-распределительная задача размещения предприятий с ограничениями на суммарную продукцию.

Рассматривается задача нахождения наименьшего значения функционала

(41)

при словиях

а (42)

а (43)

(44)

(45)

Комбинаторная постановка задачи заключается в определении подмножества атакого, что

агде

здесь .

при словиях (41) -(45), в которых I заменено на

Для решения этой задачи также применим метод последовательных расчетов.