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

Сдавался/использовался2006г., Самара
Примечаниерассматриваются задачи оптимального размещения предприятий
Загрузить архив:
Файл: ref-23638.zip (139kb [zip], Скачиваний: 160) скачать

РЕФЕРАТ

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

Самара, 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 заменено на

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