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

 

 

 

 

РЕФЕРАТ

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Самара, 2006

Производственно-транспортные задачи оптимального размещения предприятий и применимость метода последовательных расчетов

1. Задача размещения предприятий с ограниченными объемами производства.

 

Имеется п пунктов потребления с заданными объемами потребления  и m пунктов производства (предприятий) с неизвестными, ограниченными сверху объемами производства . Для каждого  заданы величины  — постоянные затраты (капиталовложения), не пропор­циональные объему производства  необходимые, например, для строи­тельства предприятий . Задана матрица транспортных расходов , где  — стоимость перевозки единицы продукции из пункта производства i в пункт потребления j.

Необходимо определить такие объемы перевозок, чтобы суммарные затраты были минимальными, т.е. требуется найти наименьшее значение функционала

где

                                                      ₍₁₎

_{при условиях}

,    ,  ,                                                     (2)

                                                              ₍₃₎

                                                             ₍₄₎

Если все , то задача становится обычной транспортной задачей линей­ного программирования. В рассматриваемой задаче предполагается, что не все . В этом случае функционал (1) представляет собой разрывную функцию, обладающую, вообще говоря, большим числом точек минимума над областью (2) - (4).

Предполагается также, что либо  для всех , либо  не для всех , так как в случае  для всех получаем задачу размещения с неограниченными объемами производства. Однако необходимо, чтобы суммарный объем потребления - не превышал сумму верхних/ границ объемов производств, т.е.

                  

                                                            (5)

так как в противном случае никакие значения  не   удовлетворяют усло­виям (2) -(4).

Обозначим через  минимальные суммарные затраты при фиксиро­вании некоторого варианта размещения , т.е.

                                                       (6)

при условиях

,    ,  ,                                                     (7)

                                                              ₍₈₎

                                                             ₍₉₎

Фиксирование некоторого варианта размещения  производится тем, что для всех  считается .). Для фиксированного со пред­полагается выполнение условия

                                                                    (10)

аналогичное условию (5).

Значение  для каждого определяется решением обычной транспортной задачи линейного программирования. Таким образом, можно говорить об однозначной функции , заданной на множестве всех , для которых выполняются условия (10).

Задача, собственно, состоит в отыскании среди всех возможных подмно­жеств (вариантов размещения)  пунктов производства  такого подмножества (варианта) , при котором обеспечи­ваются с учетом условий (7) — (10) наименьшие суммарные затраты. Другими словами, требуется определить такое подмножество , для которого  по всем , удовлетворяющим условию (10).

Функция  не определена на множестве всех подмножеств , не удовлетворяющих условию (10). Для определения функции  на множестве всех поступим следующим образом. Соотнесем пус­тому подмножеству  условный пункт производства и со cколь угодно большими постоянными транспортными расходами (сколь угодно больше ). Так как пустое множество содержится в любом , то это означает, что условный пункт производства бу­дет содержаться в любом подмножестве (варианте размещения)  пунктов производства. Поэтому в дальнейшем (чтобы не усложнять за­писи) под выражением будем понимать, что принимает не только все отличные от нуля значения элементов подмножества , но и само значение 0, соответствующее условному пункту производства. В част­ности, будет означать .

После такого введения условного пункта производства условие (4.10) будет выполняться для любого , так как величина  и поэтому значение  теперь может быть определено для всех . Здесь необхо­димо отметить, что в силу выбора величин значения  для тех , для которых условие (10) выполняется лишь с учетом , бу­дут сколь угодно большими, а для тех , для которых это условие выполняется и без учета , наличие условного пункта производства не влияет на величину , т.е. . Отсюда, в частности, следует, что искомое подмножество будет находиться среди тех , для которых

                                                          ₍₁₁₎

Таким образом, на множестве всех подмножеств  множества/опреде­ляется однозначная функция  и исходная задача сводится к отыска­нию такого подмножества , на котором  достигает своего наи­меньшего значения , т.епо всем .

Покажем, что к решению этой задачи применим метод последовательных расчетов. Для этого достаточно установить, что функция  удовлет­воряет условию

где  и - произвольные подмножества .

Для   доказательства   рассмотрим   вспомогательную   функцию   для всех . Можно записать

Таким образом, для каждого

при условиях (7)-(10).
2. Задача размещения с фиксированными минимальными объе­мами производства.

 

 Эта задача отличается от задачи 1 тем, что неко­торые предприятия являются уже действующими с мощностями , закрытие их запрещено и возможно лишь увеличение их мощностей до некоторой величины (), что влечет дополнительные затраты . Таким образом, ставится следующая задача: определить сово­купность значений , при  которых достигается  минимум функционала

                                                 (12)

при условиях

,    ,  ,                                                     (13)

                                                            ₍₁₄₎

                                                        ₍₁₅₎

где  - возможный объем производства предприятия .

Предполагается, что

так как в противном случае задача не имеет решения. Задача чрезвычайно упрощается, когда

 или

в обоих случаях ее решение сводится к решению одной транспортной за­дачи. Поэтому будем в общем случае считать

.                                                 (16)

Обозначим через  множество тех , для которых . Определим функцию  на множестве всех подмножеств  (считаем для , как и прежде, ). Если для каждого  полагать, что для всех  (это означает, что для всех предприятий возможно расширение мощности до ), то минималь­ное значение функционала (12) для этого может быть определено так:

                                      (17)

при условиях

,    ,  ,                                                     (18)

                                                            ₍₁₉₎

 _{для                                                       (20)}

   _для  

Так как с учетом пустого множества для любого  выполняется не­равенство

,                                                               (22)

то методами линейного программирования определяется значение  для любого . Таким образом, на множестве всех подмножеств со множест­ва I определяется однозначная функция . Следовательно, задача 2 сводится к определению такого подмножества, на котором функция  принимает свое наименьшее значение, т.е. по всем при условиях (18) — (21). Возможны два случая:

1) , т.е.   и в этом случае получаем задачу 1;

2)  можно записать  где     — элементы , расположенные в порядке возрастания
индексовi, т.е. если

В случае 2) рассмотрим задачу отыскания наименьшего значения функционала

                                                      (23)

при условиях

,    ,  ,                                                     (24)

                                                            ₍₂₅₎

                                                                 ₍₂₆₎

где

 

Значения ,,  определяются следующим образом.

Для всех - сколь угодно большое положи

тельное число, но в то же время  т.е. сколь угодно меньше числа

Для всех  при любых

Условие этой задачи полностью совпадает с условием задачи 1, и поэтому решение ее сводится к отысканию такого подмножества на котором функция достигает своего наименьшего значения

3. Задача размещения со ступенчатой функцией стоимости произ­водства.

Постановка этой задачи отличается от постановки задачи 1 другим заданием функций стоимости производства предприятий. В данном случае эта функция задается некоторой ступенчатой разрывной функцией  именно:

                         (27)

где  для всех  (при). Из для всех  следует, что  при  для всех

Таким образом, задача состоит в следующем: определить совокупность значений  при которых достигается минимум функционала

                                                          (28)

где   - ступенчатая разрывная функция (27) при условиях

,    ,  ,                                                     (29)

                                                              ₍₃₀₎

                                                             ₍₃₁₎

При  получаем задачу 1.

4. Задачи размещения с ограничениями на суммарную продукцию.

 

 В этой задаче предполагается, что суммарный объем продукции, выпус­каемой всеми предприятиями, задан и равен , объемы перевозок от предприятий до потребителей ограничены сверху величинами , каждый потребитель должен получить продукцию в объеме, не меньшем . Осталь­ные условия задачи 1 сохраняются.

Тогда рассматриваемая задача принимает следующий вид: определить совокупность значений , при которых достигается минимум функционала

                                                 (32)

при условиях

,    ,  ,                                                     (33)

                                                            ₍₃₄₎

                                                        ₍₃₅₎

                                                        (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)

при условиях

                                                            ₍₃₈₎

                                                        ₍₃₉₎

                                                        (40)

 

 

В отличие от задач оптимального размещения предприятий и применимость метода последовательных расчетов, здесь имеются коэффициенты , назы­ваемые коэффициентами переработки. Комбинаторная постановка за­дачи (37) - (40) состоит в определении подмножества  тако­го, что

 где ,

при  условиях   (38)-(40), в которых I заменено на .

В случае отсутствия верхних ограничений на переменные  в работе показывалось, что функция  удовлетворяет условию .

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

6. Производствснно-распределительная задача размещения пред­приятий с ограничениями на суммарную продукцию.

 

 Рассматривается за­дача нахождения наименьшего значения функционала

                                                 (41)

при условиях

                                                            ₍₄₂₎

                                                        ₍₄₃₎

                                                               (44)

                                                          (45)

Комбинаторная постановка задачи заключается в определении под­множества  такого, что

 где ,

здесь .

при условиях (41) -(45), в которых I заменено на .

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

 

      РЕФЕРАТ     Статические модели задачи размещения.            

Больше работ по теме: