Математические методы оптимизации ресурсов

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

и для  их получения не требуется никаких  дополнительных

измерений. Однако на практике достаточно часто  между параметрами

модели  нет известной функциональной зависимости.

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

общественного транспорта города в течение суток, то нам необходимо

знать, как пассажиропоток распределен  во времени. Естественно,

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

потребуется осуществить сбор и обработку  статистических

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

которая и будет тем офаничением, которое  следует

включить  в задачу оптимизации.

Значения  переменных, удовлетворяющие заданным фанич-

ным условиям и офаничениям, называют допустимым решением

задачи. Иногда случается, что в задачу включаются противоречивые

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

Такая ситуация приводит к несовместным задачам, которые в

планировании  называют несбалансированными планами (когда нет

и не может  быть допустимых решений). Обычно же, если задача

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

решений. Чтобы из данного набора допустимых решений

лицо, принимающее  решение (ЛПР), могло выбрать одно

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

его найти. В дальнейшем не будет речи о правильных решениях,

потому  что мы просто не з н а е м , что это такое. Мы будем говорить только об оптимальных решениях (от лат. optimus —

наилучший). Заметим, что наилучшего решения  во всех смыслах

быть  не может, оно может быть наилучшим (оптимальным)

только  в одном, строго установленном смысле. ЛПР должно абсолютно

точно представлять, в чем заключается  оптимальность

принимаемого  решения, т. е. по какому критерию (от ф.

kriterion —  мерило, оценка, средство для суждения) принимаемое

решение должно быть оптимально.

Критерий  часто называют целевой функцией, функцией цели,

а в  математических работах — функционалом. Критерий в

общем случае может оценивать качественные свойства объекта,

причем  как желательные пдя субъекта (обычно с максимальным

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

надежность), так и нежелательные для него (или минимальные

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

простои оборудования и др.). Если при принятии решения требуется

максимизировать какое-то свойство (к примеру, прибыль,

производительность  или надежность), то в результате решения

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

решений. Если же требуется минимизировать критерий

(стоимость,  расход материала, время простоев  оборудования),

то в  результате решения критерий будет  иметь наименьшее

значение  из всех допустимых.

Множество различных по смыслу задач оптимизации, окружающих

нас, например, из табл. 2.1, нельзя эффективно решить

без привлечения  ЭВМ, без знаний экономико-математических

моделей, практических навыков составления  математических

моделей решения задач и применения их в среде существующего

профаммного обеспечения 

Таблица  2.1. Классификация задач оптимизации  процессов и принятия решений.

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

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

Любой объект в процессе управления, проектирования или эксплуатации

характеризуется своим устройством и действием,

причем  устройство определяется его структурой и параметрами,

а действие — процессом функционирования. Например, технологический

процесс можно определить как последовательность

работ, которые обусловливают превращение  сырья в готовую

продукцию; такую последовательность работ  называют маршрутом;

каждую  операцию, входящую в марщрут, можно  охарактеризовать

определенными режимами обработки, управления,

контроля, функционирования. Заметим, что и  процессы функционирования

объекта проектирования, и технологические  процессы

характеризуются изменением некоторых параметров во

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

(непрерывные  процессы протекают в металлургии,  энергетике,

химии и др., а дискретные — в машиностроении, экономике,

образовании и т. п.).

В любых  математических моделях можно вьщелить следующие

элементы  (рис. 2.1): исходные данные, зависимости, описывающие

целевую функцию, и ограничения.

Зависимости между переменными, как целевые  функции, так

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

входят  в первой степени и нет их произведения; если

переменные  входят не в первой степени или  есть произведение

переменных, то зависимости являются нелинейными. Сочетание

разнообразных элементов модели приводит к различным  классам

задач оптимизации, требуюшим разных методов  решения и

разных  программных средств (табл. 2.2).

Для экономических  систем наиболее характерны задачи оптимизации

и распределения  ресурсов, решаемые методом линейного

профаммирования, для которого разработаны надежные

алгоритмы, реализованные в поставляемом с  ЭВМ про-

фаммном обеспечении; более сложные задачи (целочисленные,

нелинейные) оптимизации можно свести к задачам  линейного

профаммирования. Большинство задач оптимизации, присущих

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

программирования. В целом методы математического

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

исследованием операций

 
 

 

2.2Методы  оптимизации и распределения  ресурсов

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

Подобные  методы широко применимы в производстве,

транспорте, организации процессов, в об^'чении, руководстве

персоналом  и др. К числу наиболее известных  задач, решаемых этим методом, относятся  задача о назначениях, транспортная

задача  и др. [78, 82, 128—130].

Задача  о назначениях и распределении  работ является частным

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

допущения: число поставщиков т равно числу потребителей

л; запасы каждого поставщика о, = 1; заявки каждого  потребителя

bj= 1; каждый поставщик может поставлять фузы только

одному  потребителю; каждый потребитель может  получать фузы

только  от одного поставщика.

Если  не учитывать направление оптимизации  целевой функции

(шах  или min), что не влияет на  аналитические зависимости,

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

получает  вид модели задачи о назначениях. Если сумма

всех  запасов А у поставщика равняется сумме всех заявок

В потребителей, то такую транспортную задачу называют сбалансированной;

если  А 4t В, то задача является несбалансированной, и

ее математическая модель может иметь вид:

Знак  неравенства в офаничениях для  запасов а, означает,

что объем  фуза, вывозимый от любого /-го поставщика по заявкам

всех  потребителей, не может превышать  имеющегося у

него  запаса, при этом часть запаса фуза может остаться невы-

везенной. Аналогично знак неравенства в Офаничениях  для

заявок  bj означает, что фуз, получаемый ./-м поставщиком,

должен  быть не меньше заявки, но превышение заявки при

этом  допускается.

Модель  сбалансированной задачи является частным  случаем

модели  несбалансированной задачи. Несбалансированная модель

транспортной  задачи является достаточно универсальной  моделью,

описывающей множество задач распределения  однородных

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

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

знать ответы на вопросы:

• В  каком смысле распределение средств  должно быть наилучшим?

• Какой  вклад дает каждый объект (субъект) в целевую

функцию?

Любая правильно составленная задача планирования имеет

бесчисленное  множество допустимых решений. Какое  же из них

выбрать? Мы уже знаем, чтобы ответить на этот вопрос, необходимо

прежде  всего сформулировать задачу оптимизации, при