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

⇐ ПредыдущаяСтр 5 из 7Следующая ⇒

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

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

Задачи использования математики в планировании (программировании) – математическое программирование. Данные задачи образуют специальную науку – математическое программирование. Предмет данной науки – задачи оптимизации. При решении задач оптимизации возможен статический и динамический подход. Условно задачи, в которых используется динамический подход, можно называть задачами оптимального управления. Математический аппарат данной теории базируется на методе вариационного исчисления (XVIII в.), и динамическом программировании, принципах максимума и динамического программирования. В принципе максимума Понтрягина (Ленинская премия в 1961г.) при решении понимается выбор значений U(t), при которых достигается максимум некоторого функционала. Определение экстремума такого функционала – задача оптимального управления.

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

В оптимизации показатель эффективности W(x_1,…., х_n) extr, здесь (х_{1, ….,}x_n) – вектор инструментальных переменных.

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

W (x₁, …, x_n_,l₁, …, l_k, x₁, …, x _s) extr

Наиболее простой вариант задачи: нет неизвестных факторов x₁, …, x _s_. Нахождение инструментальных переменных х_i , обращающих W extr – вариационная задача.

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

На величины управляемых инструментальных переменных почти всегда накладываются ограничения типа , где i=1..m. Эти ограничения объясняются конечным числом ресурсов, имеемых в распоряжении лица принимающего решения. Если вектор управляемых переменных удовлетворяет ограничениям задачи, он называется допустимым. Множество допустимых векторов образует область допустимых решений задачи.

Зададим критерий эффективности в виде функции от n управляемых переменных . Критериальная функция может быть как скалярной, так и векторной величиной, а численное ее значение характеризует степень оптимальности принимаемого решения. В одних случаях оптимальным будет наибольшее, а в других – наименьшее значение критерия эффективности.

С учетом сказанного запишем оптимизационную задачу в виде модели

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

В более компактном виде модель можно записать:

Таким образом, в данной модели имеются три составляющих:

1. Целевая функция или критерий оптимизации, который показывает, в каком смысле решение должно быть оптимальным. При этом возможны три варианта назначения: максимизация, минимизация и назначение заданного значения.

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

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

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

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

Например

В соответствии с теоремой Кронекера-Капелли данная система несовместна. Система совместна (имеет хотя бы одно решение) тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы.

Решений нет.

Например

В данном случае уравнения являются линейно независимыми. Ранги основной и расширенной матриц совпадают. Следовательно, система совместна. Система имеет единственное решение, т.к. ее ранг равен числу переменных.

Например

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

Заметим, что если имеют ограничения в виде неравенств, то их можно превратить в равенства, добавив дополнительные переменные, что приводит к росту .

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

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

Функции являются непрерывными дифференцируемыми функциями – функциями-ограничениями.

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

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

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

Пусть имеется п видов товаров и услуг, количества которых (в натуральных единицах) по ценам соответственно единиц. Суммарная стоимость этих товаров и услуг составляет . Уровень потребления W может быть выражен некоторой функцией , называемой функцией полезности. Необходимо найти такой набор товаров и услуг при данной величине доходов I, чтобы обеспечить максимальный уровень потребления, т.е.

При условии

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

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

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

Проведем классификацию по классификационным признакам:

- Типу исходных данных (детерминированные, случайные);

- Типу искомых переменных (непрерывные, дискретные);

- Виду зависимостей в постановке задачи- целевой функции и ограничений- (линейные и нелинейные);

- По числу оперирующих сторон (неигровые и игровые задачи).

В таблице приведены результаты выполненной классификации.

Исходные данные	Искомые переменные	Зависимость	Класс задач
Детерминированные	Непрерывные	Линейные	ЛП
Детерминированные	Целочисленные	Линейные	ЦЛП
Детерминированные	Непрерывные, целочисленные	Нелинейные	НЛП
Случайные	Непрерывные	Линейные	СП

В линейном программировании целевая функция является линейной формой

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

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

Если в задаче математического программирования имеется переменная времени и критерий эффективности выражается в неявном виде как функция переменных, а косвенно — через уравнения, описывающие протекание операций во времени, то такая задача является задачей динамического программирования.

Если система ограничений состоит из двух типов ограничений:

, функция ограничений непрерывная и дифференцируемая. Константы ограничений - заданные действительные числа, то задача оптимизации является задачей нелинейного программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования.

Если критерий эффективности и система ограничений задаются функциями вида , то имеем задачу геометрического программирования.

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

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

Из перечисленных методов математического программирования наиболее распространенным и разработанным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций.

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

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

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

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

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

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

Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования.

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

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

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

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

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

Решение задач анализа устойчивости обычно начинается с «холодного запуска» - решения задачи с самого начала для одного из вариантов математической модели. Затем осуществляется так называемый «теплый запуск» для каждой из видоизмененных моделей. При теплом запуске расчеты обычно начинаются от решения, полученного на предыдущем шаге.

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

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

⇐ Предыдущая 1 2 3 456 7 Следующая ⇒