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

РЕФЕРАТ
Статические модели задачи размещения.
Самара, 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заменено на
Длярешения этой задачи также применим метод последова­тельных расчетов.