Читайте данную работу прямо на сайте или скачайте

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

РЕФЕРАТ

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

Самара, 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) состоит в определении подмножества атаконго, что