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

РЕФЕРАТ

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

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

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