Статические модели задачи размещения
РЕФЕРАТ
Статические модели задачи размещения.
Самара, 2006
Производственно-транспортные задачи оптимального размещения предприятий и применимость метода последовательных расчетов
1. Задача размещения предприятий с ограниченными объемами производства.
Имеется п пунктов потребления с заданными объемами потребления и m пунктов производства (предприятий) с неизвестными, ограниченными сверху объемами производства . Для каждого заданы величины — постоянные затраты (капиталовложения), не пропорциональные объему производства необходимые, например, для строительства предприятий , где — стоимость перевозки единицы продукции из пункта производства i в пункт потребления j.
Необходимо определить такие объемы перевозокзатраты были минимальными, т.е. требуется найти наименьшее значение функционала
где
(1)
при условиях
, (2)
(3)
(4)
Если все , то задача становится обычной транспортной задачей линейного программирования. В рассматриваемой задаче предполагается, что не все . В этом случае функционал (1) представляет собой разрывную функцию, обладающую, вообще говоря, большим числом точек минимума над областью (2) - (4).
Предполагается также, что либо для всех , либо не для всех , так как в случае для всех получаем задачу размещения с неограниченными объемами производства. Однако необходимо, чтобы суммарный объем потребления - не превышал сумму верхних/ границ объемов производств, т.е.
(5)
так как в противном случае никакие значения не удовлетворяют условиям (2) -(4).
Обозначим через минимальные суммарные затраты при фиксировании некоторого варианта размещения
(6)
при условиях
, (7)
(8)
(9)
Фиксирование некоторого варианта размещения производится тем, что для всех считается Для фиксированного со предполагается выполнение условия
(10)
аналогичное условию (5).
Значение для каждого определяется решением обычной транспортной задачи линейного программирования. Таким образом, можно говорить об однозначной функции заданной на множестве всех , для которых выполняются условия (10).
Задача, собственно, состоит в отыскании среди всех возможных подмножеств (вариантов размещения) пунктов производства такого подмножества (варианта) , при котором обеспечиваются с учетом условий (7) — (10) наименьшие суммарные затраты. Другими словами, требуется определить такое подмножество , для которого по всем , удовлетворяющим условию (10).
Функция не определена на множестве всех подмножеств , не удовлетворяющих условию (10). Для определения функции на множестве всех поступим следующим образом. Соотнесем пустому подмножеству условный пункт производства cколь угодно большими постоянными транспортными расходами (). Так как пустое множество содержится в любом , то это означает, что условный пункт производства будет содержаться в любом подмножестве (варианте размещения) пунктов производства. Поэтому в дальнейшем (чтобы не усложнять записи) под выражением все отличные от нуля значения элементов подмножества , но и само значение 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) можно записать где — элементы , расположенные в порядке возрастания индексовi, т.е.
В случае 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 заменено на
Для решения этой задачи также применим метод последовательных расчетов.