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

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