Статические модели задачи размещения
Информация - Математика и статистика
Другие материалы по предмету Математика и статистика
РЕФЕРАТ
Статические модели задачи размещения.
Самара, 2006
Производственно-транспортные задачи оптимального размещения предприятий и применимость метода последовательных расчетов
- Задача размещения предприятий с ограниченными объемами производства.
Имеется п пунктов потребления с заданными объемами потребления и 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 тем, что некоторые предприятия являются уже действующими с мощностями , закрытие их запрещено и возможно лишь увеличение их мощностей до некоторой величины (), что влечет дополнительные затраты . Таким образом, ставится следующая задача: определить совокупност