Применение метода последовательных расчетов к задаче размещения с искомыми объемами производства

УДК 519.8

М.А. Асанкулова, С.Т. Муканова, К.И. Алымбаев

г. Каракол, ИГУ им. К. Тыныстанова
ПРИМЕНЕНИЕ МЕТОДА ПОСЛЕДОВАТЕЛЬНЫХ РАСЧЕТОВ К ЗАДАЧЕ РАЗМЕЩЕНИЯ С ИСКОМЫМИ ОБЪЕМАМИ ПРОИЗВОДСТВА
В данной работе предлагается метод последовательных расчетов для нахождения оптимального решения задачи размещения.
В данной статье рассмотрено применение метода последовательных расчетов к задаче размещения с искомыми объемами производства и составлена программа решения данной задачи с использованием метода последовательных расчетов на Delphi.

Дадим основные положения метода последовательных расчетов.

Дано некоторое подмножество , которое можно представлять, например, как множество номеров некоторых параметров оптимизации, способных (для определенности) принимать лишь два значения: 0 или 1. Каждое подмножество естественно интерпретировать как множество тех параметров, которые приняли одно из этих значений (например 1), в то время как параметр из принимают другое возможное значение (т.е. 0).

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

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

(*)

При нахождении минимума знак неравенства в (*) меняется на обратный.

Теоретические основы метода последовательных расчетов даются следующей теоремой.

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

Использование этой теоремы позволяет отбраковывать множество вариантов. Действительно, пусть для некоторой и таких, что найденные значения и . Тогда при из рассмотрения можно отбросить все вариантов . Если же , то можно исключить все вариантов . Пусть, например, взяты некоторые, для которых Тогда отбрасывается сразу вариантов, т.е. половина их общего числа. Это варианты, отвечающие нулевому значению параметра оптимизации с номером из .

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

Рассмотрим следующую задачу и найдем оптимальное решение с помощью метода последовательных расчетов.

Задача: имеется пунктов добычи сырья , с заданными объемами добычи . Однако вследствие малой производительности пункты добычи не удовлетворяет требуемого спроса Q в этом сырье. В связи с этим возникает задача о строительстве дополнительных пунктов добычи сырья, которое возможно в пунктах. При этом известен максимально возможный объем добычи сырья . Сырье, добытое в этих пунктах, должно быть доставлено на перерабатывающих предприятий . Объем перерабатываемого сырья на каждом перерабатывающем предприятии предполагается заданным величиной . Для каждого возможного пункта , задана разрывная функция , отражающая зависимость себестоимости сырья (с учетом капитальных вложений) от объема добычи ,



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

Кроме того, задана матрица транспортных расходов .

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

(1)

при ограничениях

(2)

(3)

(4)



(6)

где



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



Далее, из постановки задачи видно, что функция разрывные. Следовательно, рассматриваемая задача (1)-(6) многоэкстремальная. В связи с этим для ее решения в общем случае нельзя применить те методы поиска минимума, которые разработаны для линейного и выпуклого программирования. Поэтому для решения задачи (2)-(7) используем метод последовательных расчетов, позволяющий отыскать глобальный рассматриваемого функционала при ограничениях (2)-(6). Преобразуем задачу (1)-(6) к следующему виду:

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

(7)

при ограничениях

(8)

(9)

(10)
(11)

(12)

где для всех .

Обозначим через множество, состоящее из пунктов добычи сырья т.е. и через множество пунктов

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

(13)

при ограничениях

(14)

(15)

(16)

(17)

(18)

Обозначим через минимальное значение при ограничениях (14)-(18). Следовательно, исходная задача может быть сформулирована следующим образом.

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

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

(19)

Подсчет производится лишь для вариантов, удовлетворяющих условию (19), а для вариантов , не удовлетворяющих условию (19), подсчет не производится и исключается из дальнейшего рассмотрения все где .

На основе данного метода последовательных расчетов была составлена программа на Delphi для отыскания оптимального решения задачи размещения (1)-(6) и рассмотрена экспериментальная задача.

Задача. Имеется один пункт производства сырья с заданным объемом производства . Однако, производство этого пункта не удовлетворяет требуемого спроса Q=35 этом сырье, в связи с чем возникает задача о строительстве дополнительных пунктов. Строительство возможно четырех пунктах причем известен максимальный объем производства сырья т.е.



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



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

Тогда экономическая модель задачи записывается в таком виде:

Найти минимум



при ограничениях



где объем производства сырья фиктивного пункта .

Для определения оптимального решения задачи воспользовались методом последовательных расчетов с дополнительным условием отбраковки (19). Таким образом, исходная задача имеет решение:

.

Для нахождения глобального минимума пришлось перебрать 12 вариантов из 16 возможных.

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

ЛИТЕРАТУРА

1. 
   Ланге Э.Г., Жусупбаев А.Ж. О методах решения задачи размещения. –Ф.:Илим, 1976.
   
2. 
   Черенин В.П., Хачатуров В.Р. Решение методом последовательных расчетов одного класса задач о размещении производства //Экономико-математические методы. –М.:Наука, 1965.