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

    Дисциплина: Разное
    Тип работы: Реферат
    Тема: Статические модели задачи размещения

    РЕФЕРАТ

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

    Самара, 2006

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

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

    производства.

    Имеется п пунктов потребления с заданными объемами

    потребления

    пунктов производства

    (предприятий) с неизвестными, ограниченными сверху объемами произ

    водства

    Для каждого

    заданы

    величины

    — постоянные затраты (капиталовложения), не пропор­циональные объему производства

    необходимые, например, для строи­

    тельства предприятий

    , где

    — стоимость перевозки единицы продукции из

    пункта производства

    в пункт потребления

    Необходимо определить такие объемы перевозок

    затраты были минимальными, т.е. требуется найти наименьшее значение

    функционала

    где

    при условиях

    Если все

    , то задача становится обычной транспортной задачей линей­

    ного программирования. В рассматриваемой задаче предполагается, что не

    все

    . В этом случае функционал (1) представляет собой разрывную

    функцию, обладающую, вообще говоря, большим числом точек минимума

    над областью (2) - (4).

    Предполагается также, что либо

    для всех

    , либо

    не для всех

    , так как в случае

    для всех

    получаем задачу размещения с неограниченными объемами производства

    Однако необходимо, чтобы

    суммарный объем потребления

    не превышал сумму верхних

    границ объемов производств, т.е.

    так как в противном случае никакие значения

    не

    удовлетворяют усло­

    виям (2) -(4).

    Обозначим через

    минимальные суммарные затраты при фиксиро­

    вании некоторого варианта размещения

    при условиях

    Фиксирование некоторого варианта размещения

    производится тем,

    что для всех

    считается

    Для фиксированного со пред­

    полагается выполнение условия

    (10)

    аналогичное условию

    (5).

    Значение

    для каждого

    определяется решением обычной транспортной задачи линейного программирования. Таким образом, можно

    говорить об однозначной функции

    заданной на множестве всех

    , для которых выполняются условия

    (10)

    Задача, собственно, состоит в отыскании среди всех возможных подмно­

    жеств (вариантов размещения)

    пунктов производства

    такого подмножества (варианта)

    , при котором обеспечи­ваются с учетом условий (7) — (10) наименьшие суммарные затраты

    Другими словами, требуется определить такое подмножество

    для которого

    по всем

    , удовлетворяющим условию

    (10).

    Функция

    не определена на множестве всех подмножеств

    , не удовлетворяющих условию

    (10).

    Для определения функции

    на множестве всех

    поступим следующим образом. Соотнесем пус­

    тому подмножеству

    условный пункт производства

    коль угодно большими постоянными транспортными расходами

    ). Так как пустое множество

    содержится в любом

    , то это означает, что условный пункт производства бу­дет содержаться в любом подмножестве (варианте размещения)

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

    писи) под выражением

    все отличные от нуля значения элементов подмножества

    , но и само

    значение 0, соответствующее условному пункту производства. В част­

    ности,

    После такого введения условного пункта производства условие (4.10)

    будет выполняться для любого

    , так как величина

    и поэтому

    значение

    теперь может быть определено для всех

    . Здесь необхо­

    димо отметить, что в силу выбора величин

    для тех

    , для которых условие (10) выполняется лишь с учетом

    , бу­дут сколь угодно большими, а для тех

    , для которых это условие

    выполняется и без учета

    наличие условного пункта производства не

    влияет на величину

    т.е.

    . Отсюда, в частности,

    следует, что искомое подмножество

    , для которых

    (11)

    Таким образом, на множестве всех подмножеств

    множества/опреде­

    ляется однозначная функция

    и исходная задача сводится к отыска­нию такого подмножества

    достигает своего наи­

    меньшего значения

    т.е

    по всем

    Покажем, что к решению этой задачи применим метод последовательных

    расчетов. Для этого достаточно установить, что функция

    удовлет­

    воряет условию

    где

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

    Для

    доказательства

    рассмотрим

    вспомогательную

    функцию

    для всех

    Можно записать

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

    при условиях (7)

    -(10).

    Задача размещения с фиксированными минимальными объе­

    мами производства.

    Эта задача отличается от задачи 1 тем, что неко­

    торые предприятия

    являются уже действующими с мощностями

    , закрытие их запрещено и возможно лишь увеличение их мощностей

    до некоторой величины

    , что влечет дополнительные затраты

    Таким образом, ставится следующая задача: определить сово­

    купность значений

    при

    которых достигается

    минимум функционала

    (12)

    при условиях

    где

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

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

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

    упрощается, когда

    или

    в обоих случаях ее решение сводится к решению одной транспортной за­

    дачи. Поэтому будем в общем случае считать

    (16)

    Обозначим через

    множество тех

    , для которых

    . Определим

    функцию

    на множестве всех подмножеств

    (считаем для

    , как и прежде,

    полагать, что

    для всех

    (это означает, что для всех

    предприятий

    возможно расширение мощности до

    ), то минималь­

    ное значение функционала (12) для этого

    (17)

    при условиях

    (18)

    (19)

    для

    (20)

    для

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

    выполняется не­

    равенство

    (22)

    то методами линейного программирования определяется значение

    для любого

    ва

    определяется однозначная функция

    Следовательно, задача

    2 сводится к определению такого подмножества

    функция

    принимает свое наименьшее значение

    т.е.

    по всем

    при условиях (18) — (21). Возможны два

    случая:

    , т.е.

    и в этом случае получаем задачу

    можно записать

    где

    — элементы

    , расположенные в порядке возрастания

    индексов

    т.е.

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

    (23)

    при условиях

    (24)

    (25)

    (26)

    где

    Значения

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

    Для всех

    тельное число, но в то же время

    Для всех

    при любых

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

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

    водства.

    Постановка этой задачи отличается от постановки задачи

    другим заданием функций стоимости производства предприятий.

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

    функцией

    именно:

    где

    для всех

    (при

    для всех

    следует, что

    при

    для всех

    Таким образом, задача состоит в следующем: определить совокупность

    значений

    при которых достигается минимум функционала

    (28)

    где

    - ступенчатая

    разрывная функция (27) при

    условиях

    При

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

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

    В этой задаче предполагается, что суммарный объем продукции, выпус­

    каемой всеми предприятиями, задан и равен

    , объемы перевозок от

    предприятий до потребителей ограничены сверху величинами

    каждый потребитель должен получить продукцию в объеме, не меньшем

    Осталь­

    ные условия задачи 1 сохраняются.

    Тогда рассматриваемая задача принимает с...

    Забрать файл

    Похожие материалы:


    Добавить комментарий
    Старайтесь излагать свои мысли грамотно и лаконично

    Введите код:
    Включите эту картинку для отображения кода безопасности
    обновить, если не виден код



ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены