«В.П. Белокуров С.В. Белокуров Г.А. Денисов Н.И. Злобина Э.Н. Бусарин ПРИНЯТИЕ ОПТИМАЛЬНЫХ РЕШЕНИЙ В ТЕХНОЛОГИИ ТРАНСПОРТНЫХ ПРОЦЕССОВ Учебное пособие Воронеж 2013 1 Министерство образования и науки Российской Федерации ...»

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Воронежская государственная лесотехническая академия»

В.П. Белокуров С.В. Белокуров Г.А. Денисов Н.И. Злобина Э.Н. Бусарин

ПРИНЯТИЕ ОПТИМАЛЬНЫХ РЕШЕНИЙ

В ТЕХНОЛОГИИ ТРАНСПОРТНЫХ ПРОЦЕССОВ

Учебное пособие Воронеж 2013 1 Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Воронежская государственная лесотехническая академия»

В.П. Белокуров С.В. Белокуров Г.А. Денисов Н.И. Злобина Э.Н. Бусарин

ПРИНЯТИЕ ОПТИМАЛЬНЫХ РЕШЕНИЙ

В ТЕХНОЛОГИИ ТРАНСПОРТНЫХ ПРОЦЕССОВ

Учебное пособие Воронеж УДК 656.13: П Печатается по решению учебно-методического совета ФГБОУ ВПО «ВГЛТА» (протокол № 2 от 1 ноября 2013 г.) Рецензенты: кафедра электротехники и автоматики ФГБОУ ВПО Воронежский ГАУ;

д-р техн. наук, проф. Е.В. Кондрашова П76 Принятие оптимальных решений в технологии транспортных процессов [Текст] : учебное пособие / В. П. Белокуров, С. В. Белокуров, Г. А. Денисов, Н. И. Злобина, Э. Н. Бусарин ; М-во образования и науки РФ, ФГБОУ ВПО «ВГЛТА». – Воронеж, 2013. – 187 с.

ISBN 978-5-7994-0599-1 (в обл.) Учебное пособие посвящено прикладным аспектам теории принятия оптимальных решений в технологии транспортных процессов. Рассматриваются методы и алгоритмы линейного, нелинейного, целочисленного, стохастического программирования, а также принятия решений в условиях неопределенности, многокритериальности, которые используются для решения задач оптимизации в технологии транспортных процессов.

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

Учебное пособие предназначено для студентов, обучающихся по направлению подготовки 190700 – Технология транспортных процессов, а также для аспирантов и магистров.

УДК 656.13: © Белокуров В.П., Белокуров С.В., Денисов Г.А., Злобина Н.И., Бусарин Э.Н, ISBN 978-5-7994-0599-1 © ФГБОУ ВПО «Воронежская государственная лесотехническая академия», Оглавление Введение……………………………………………………………... 1. ПРИНЯТИЕ РЕШЕНИЯ

2. МОДЕЛИРОВАНИЕ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ

2.1. Принципы составления простейших моделей…………….. 2.2. Форма записи математической модели……………………. 2.3. Классификация оптимизационных задач…………………..

3. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ О РАСПРЕДЕЛЕНИИ

РЕСУРСОВ В ТЕХНОЛОГИИ ГРУЗОВЫХ

АВТОМОБИЛЬНЫХ ПЕРЕВОЗОК

4. ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ

4.1. Основные понятия в геометрических решениях 4.2. Графическое решение задач линейного 4.3. Различные варианты оптимальных решений в задачах 5. ПРИНЯТИЕ РЕШЕНИЙ 5.5. Решение оптимизационных задач в относительных

6. ТЕОРИЯ ВЕРОЯТНОСТЕЙ ДЛЯ ПРИНЯТИЯ

ОПТИМАЛЬНЫХ РЕШЕНИЙ В УСЛОВИЯХ

6.2. Теория вероятностей в оптимизационных задачах

7. АНАЛИЗ В ЗАДАЧАХ ОПЕРАТИВНОГО

7.1. Анализ в случае использования математических моделей. 7.2. Симплекс – метод в решении оптимизационных задач….. 7.3. Принятие решений в случае отклонения ресурсов от первоначально запланированных…………………………….

8. ЦЕЛОЧИСЛЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО

8.1. Общие понятия о задачах целочисленного 8.2. Особенности решения задач. Метод целочисленного 8.3. Задачи раскроя в целочисленном программировании……. 8.4. Булевы переменные в задачах целочисленного 8.5. Решение задач оптимизации с использованием булевых

9. ТЕОРИЯ ГРАФОВ В ЗАДАЧАХ ЛИНЕЙНОГО

9.1. Основные понятия теории графов…………………………. 9.2. Задачи оптимизации на сетях………………………………. 9.3. Критический путь в сетевых графиках……………………. 10.1. Основные понятия нелинейного программирования…… 10.2. Аналитические методы определения экстремума в задачах безусловной оптимизации…………………………… 10.3. Вычислительные методы в задачах условной 10.4. Задачи условной оптимизации, учитывающие начальные и граничные условия………………………………... 11. ОПТИМАЛЬНОЕ ПРОЕКТИРОВАНИЕ…………………... 11.1. Основные понятия о системе автоматизированного 11.2. Инженерные и экономические расчеты в САПР………… 11.3. Структура и параметры объекта проектирования………. 11.4. Исходные данные для использования методов оптимального проектирования…………………………………. 11.5. Задачи оптимизации технологических процессов………. 11.6. Методы перебора возможных вариантов и методы решения задач оптимизации в САПР…………………………...

ВВЕДЕНИЕ

Решения человечество принимало всегда и во всех сферах своей деятельности. Раньше хотели, чтобы принимаемые решения были правильными. Теперь принято говорить, что решения должны быть оптимальными. Важная область принятия решения связана с производством. Чем больше объем производства, тем труднее, принять решение и, следовательно, легче допустить ошибку. Возникает естественный вопрос: нельзя ли во избежание таких ошибок использовать ЭВМ? В настоящее время применение ЭВМ в управлении производством достигло очень больших масштабов.

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

Вопросам принятия решений на основе применения ЭВМ и математических моделей посвящена многочисленная литература, в том числе фундаментальные работы отечественных учёных А. Г. Аганбегяна, Е. С. Вентцель, Л. В. Канторовича, Н. Н. Моисеева, Г. С. Поспелова, Н. П. Федоренко, Д. Б. Юдина и др.

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

Глава 1. ПРИНЯТИЕ РЕШЕНИЯ Основными этапами задач принятия оптимальных решений являются этапы, представленные на рис. 1.

Рис. 1. Основные этапы задач принятия оптимальных решений Выбор задачи. Выбор задачи – важнейший вопрос. Решение задачи, особенно достаточно сложной, – это очень трудное дело, требующее много времени. И если задача выбрана неудачно, то это может привести к сожалению о потерянном времени. Каким же основным требованиям должна удовлетворять задача? Таких требований два:

1) должно существовать, как минимум, два варианта ее решения; ведь если вариантов решения нет, значит, и выбирать не из чего;

2) надо четко знать, в каком смысле искомое решение должно быть наилучшим.

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

Составление модели. Модели, бесконечные в своем разнообразии, можно классифицировать по самым различным признакам. В первую очередь все модели можно подразделить на физические и описательные.

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

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

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

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

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

Как же оценить адекватность моделей? Любая оценка – это сравнение с некоторым эталоном. Применительно к принятию решений таких эталонов, как правило, нет. Единственным мерилом правильности решения, принятого на модели, можно считать только эксперимент, практику. Модель же, проверенная на практике, способна стать надежным средством принятия решений.

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

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

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

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

Для обеспечения успеха моделирования надо выполнить три правила:

учесть главные свойства моделируемого объекта; пренебрегать его второстепенными свойствами; уметь отделить главные свойства от второстепенных.

Но в жизни, к сожалению, не всегда так легко отделить главное от второстепенного и составить приемлемую математическую модель.

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

Алгоритмы могут быть записаны в различной форме: словесным описанием необходимых действий, указанием последовательности выполняемых работ по пунктам с помощью формул и т. д. Удобной формой записи алгоритма является блок-схема. Она не только достаточно наглядно описывает алгоритм, но и является основной для составления программы.

Составление программы. Алгоритм записывают с помощью обычных математических символов. Для того чтобы этот алгоритм мог быть ЭВМ прочитан, надо составить программу, т. е. записать последовательность вычислений, которые должна произвести ЭВМ, на языке, который ЭВМ понимает. Алгоритмы и программы объединяются понятием «математическое обеспечение».

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

Глава 2. МОДЕЛИРОВАНИЕ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ

2.1. Принципы составления простейших моделей Прежде чем приступить к составлению модели, введем некоторые понятия. То, что мы хотим спроектировать, будем называть объектом проектирования (ОП). Каждый ОП обладает определенными свойствами. Эти свойства могут быть как количественными, так и качественными. Примерами количественных свойств могут быть масса, производительность, стоимость и т. д. Примерами качественных свойств – надежность, удобство эксплуатации и, наконец, само понятие «качество», например, качество автоперевозок.

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

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

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

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

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

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

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

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

2.2. Форма записи математической модели Чтобы решать самые разнообразные задачи оптимизации необходимо иметь математическую модель решаемой задачи. Зачастую самые различные по содержанию задачи оказываются частными случаями одной задачи оптимизации.

Для записи задачи оптимизации в общем виде принимаем, что число искомых переменных равно n. При этом каждую переменную обозначим xj, где j=1, 2,…, n, что сокращенно обозначается j = 1, n. При этом j – порядковый номер искомой переменной; i – порядковый номер ограничения i = 1, m ; m – число всех ограничений.

В этом случае в общем виде для n переменных и m ограничений математическая модель может быть записана в виде:

где aj и bj – нижнее и верхнее предельно допустимые значения xj.

Данную задачу (2.1) представим более компактно:

Зависимость (2.2) является математической постановкой задачи оптимизации в общем виде и включает три составляющие: целевую функцию (ЦФ);

ограничения (ОГР); граничные условия (ГРУ). Рассмотрим эти составляющие.

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

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

В этом случае в задаче (2.2) принимается a j = 0, b j = и накладывается только требование неотрицательности x j 0.

2. В ряде случаев значение величины x j задается.

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

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

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

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

Если задача составлена правильно, то вобщем случае она имеет набор допустимых решений. Чтобы из этого набора допустимых решений выбрать одно, необходимо договориться, по какому признаку мы это будем делать. Естественно, хочется, чтобы выбранное решение оказалось правильным. Но что такое правильное решение? Оказывается, на этот вопрос ответить не так-то просто. Любая оценка – это сравнение. А сравнивать не с чем. Эталонов правильных решений, к сожалению, нет. Сказать, что решение правильное или неправильное, – это значит дать оценку, которая может оказаться весьма субъективной. Поэтому в дальнейшем не будем говорить о правильных решениях, потому что мы просто не знаем, что это такое. Наш разговор будет об оптимальных решениях. Что же касается оптимального решения, название которого происходит от лат. optimus – наилучший, то здесь все четко и определенно.

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

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

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

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

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

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

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

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

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

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

Методы математического программирования – это существенная часть науки, которую традиционно называют исследованием операций.

Глава 3. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ О РАСПРЕДЕЛЕНИИ

РЕСУРСОВ В ТЕХНОЛОГИИ ГРУЗОВЫХ АВТОМОБИЛЬНЫХ

ПЕРЕВОЗОК

3.1. Задачи о распределении одинаковых грузов Математическая модель рассматриваемой задачи в общем случае, когда количество исполнителей и работ равно n, будет иметь вид:

где i – номер исполнителя; j – номер работы.

Величина cij принимается из матрицы 3.1 условий задачи; условие (а) означает, что на каждую i-ю работу может быть назначен только один j-й исполнитель; условие (б) означает, что каждый j-й исполнитель может быть назначен только на одну i-ю работу.

Рассмотрим конкретную задачу о распределении одинаковых грузов, но с разным количеством поставщиков i и потребителей j грузов.

Допустим, требуется транспортировать груз одного вида (песок, руду, молоко), находящийся у двух поставщиков A1 и А2, к трем потребителям В1, B2, В3. Возможные варианты транспортировки показаны на рис. 3.1, на котором над каждой стрелкой, соединяющей поставщика с потребителем, указана стоимость перевозки единицы груза. У каждого поставщика есть некоторый запас товаров.

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

Рис. 3.1. Схема поставки грузов Условие задачи сведено в табл. 3.2. Требуется определить, какое количество груза следует отправить от каждого поставщика каждому потребителю, чтобы суммарные транспортные расходы были минимальными. То, что мы записали, называется содержательной постановкой задачи. На основании содержательной постановки надо сформулировать математическую модель. Для составления модели введем следующие обозначения: x11, х12, х13 – число единиц груза, который 1-й поставщик должен отправить 1-, 2- и 3-му потребителям; х21, x22, x23 – то же применительно ко 2-му поставщику.

Суммируя переменные по строкам табл. 3.2, запишем:

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

Суммируя по столбцам, получим для потребителей:

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

Объединяя условия для поставщиков и потребителей, мы получим систему, содержащую 2 + 3 = 5 уравнений и 2x3 = 6 неизвестных. Для того чтобы получить единственное решение, число неизвестных должно быть равно числу уравнений. Если же неизвестных больше, чем уравнений, то система имеет бесчисленное множество решений.

Действительно, пусть задано одно уравнение где имеется два неизвестных. Если записать x1 = 2 + x2, то, придавая х2 бесчисленное множество значений 1, 2, 3 и т. д., будем соответственно получать х1 =3, 4, 5 и т. д.

Рассмотрим для примера три варианта решения транспортной задачи, которые приведены в табл. 3.3 – 3.5. В этих таблицах на пересечении строк-поставщиков и столбцов-потребителей приведено количество транспортируемого груза, удовлетворяющее системе уравнений. Так, в табл. 3.3 от поставщика A 1 потребителю В1 будет доставлено 0 единиц груза, т. е. х11 = 0. Далее x12 = 10; x13 = 90.

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

Нетрудно определить суммарную стоимость перевозок грузов для рассмотренных вариантов:

для варианта 1 (табл. 3.3) для варианта 2 (табл. 3.4) для варианта 3 (табл. 3.5) В транспортной же задаче решений бесчисленное множество, и все они удовлетворяют системе ограничений, т. е. являются допустимыми.

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

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

В результате решения системы 3.2 были найдены следующие значения:

х11 = 80; x12 = 20; x13 = 0; x21 = 0; x22 = 110; x23 = 90. Если эти значения подставить в табл. 3.2 или в систему (3.2), то нетрудно убедиться в соблюдении всех ограничений, что, впрочем, справедливо и для каждого допустимого решения. Однако в полученном решении при таком распределении поставок суммарные транспортные расходы F будут минимально возможными и равными 3830.

Сравним полученное решение с ранее принятыми допустимыми вариантами, как это сделано в табл. 3.6. Из табл. 3.6 видно, что увеличение транспортных расходов в наших примерах для допустимых планов перевозок по сравнению с оптимальным планом перевозок составляет от 15 до 40 %. Пусть наши допустимые планы не самые удачные. Но все равно трудно себе представить, что без решения задачи оптимизации можно с помощью здравого смысла найти оптимальный план перевозок. И если это кому-нибудь удастся на данном примере, то это вовсе не означает что этого можно достигнуть в реальных транспортных задачах, включающих сотни поставщиков и потребителей.

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

Вернемся к ее составлению.

Систему (3.2) можно записать более компактно:

где i – номер поставщика; j – номер потребителя; cij – стоимость перевозки единицы груза от i-го поставщика j-му потребителю; ai – запасы i-го поставщика; bj – заявки j-го потребителя.

Целевая функция F1 = Если от рассмотренного частного случая перейти к общему, в котором число поставщиков равно т, а потребителей n, то матрица исходных данных (табл. 3.2) получит вид табл. З.7, а математическую модель (3.3) можно будет представить следующим образом:

Если сравнить исходные данные, записанные в табл. 3.7 и математическую модель 3.4 с исходными данными табл. 3.1 и математической моделью 3.1, то нетрудно заметить, что задача о назначениях является частным случаем транспортной задачи, в которой приняты следующие допущения: число поставщиков m равно числу потребителей п; запасы каждого поставщика аi = 1;

заявки каждого потребителя bj = 1; каждый поставщик может поставлять грузы только одному потребителю; каждый потребитель может получать грузы только от одного поставщика.

Если не учитывать направление оптимизации целевой функции (max или min), что не влияет на аналитические зависимости, то модель транспортной задачи (3.4) при этих допущениях получит вид модели задачи о назначениях (3.1).

Рассмотрим еще один вопрос. В системе 3.4 сумма всех запасов равна сумме всех заявок Транспортную задачу, в которой А = В, т. е. сумма всех запасов равна сумме всех заявок, называют сбалансированной. Если же А # В, то задача является несбалансированной и ее математическая модель будет иметь вид:

Системы (3.4) и (3.5) различаются тем, что в ограничениях (3.5) вместо знаков равенства стоят знаки неравенства. Знак неравенства в ограничениях для запасов ai соответствует требованию, согласно которому вывозимый груз не может превышать имеющийся запас, но допускается, что часть груза может остаться невывезенной. Аналогично знак неравенства в ограничениях для заявок bj отвечает требованию, в соответствии с которым получаемый груз должен быть не меньше заявки, но превышение заявки при этом допускается.

Таким образом, модель сбалансированной задачи (3.4) представляет собой частный случай несбалансированной задачи (3.5).

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

Так, если от поставщиков перейти к объектам финансирования, а от потребителей – к периодам финансирования, то табл. 3.7 будет иметь вид табл.

3.8, в которой ai – финансирование каждого объекта в течение всего времени; bj – финансирование всех объектов в данный период времени; хij – выделяемое финансирование i-го объекта в j-м периоде; cij – результат финансирования i -го объекта в j-м периоде; A = ai – финансирование всех объектов; B = b j – фиj = нансирование на протяжении всех периодов.

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

3.2. Задача о распределении разных ресурсов Все, что необходимо для производства (автотранспорт, оборудование, финансы, рабочая сила и др.), можно объединить понятием «ресурсы», которые в свою очередь, могут быть трех основных видов: трудовые, материальные и финансовые. Большое число задач, возникающих в производстве, можно рассматривать как преобразование ресурсов в результат. Поэтому значительную часть задач, возникающих при управлении производством, можно отнести к классу задач распределения ресурсов. В том случае, когда ресурс относится к одному типу, например, однородный груз или финансы, то задача распределения сводится к транспортной задаче. Но использование ресурса одного типа – это частный случай. В общем случае ресурсы могут быть самыми разнообразными. Как же решать эту часто встречающуюся задачу распределения неоднородных ресурсов?

Начнем с примера. Требуется определить план выпуска четырех видов продукции П1, П2, ПЗ, П4 (например, различные агрегаты для автотранспорта:

П1 – КПП; П2 – муфта сцепления; П3 – двигатель; П4 – задний мост), для изготовления которых необходимы ресурсы трех типов: трудовые, материальные, финансовые. Количество каждого типа i-го ресурса для изготовления каждого j-го вида продукции будем называть нормой расхода и обозначать a i j. Количество каждого вида ресурса, которым мы располагаем, обозначим b i. Конкретные значения а i j и b i применительно к рассматриваемой задаче приведены в табл. 3.9, из которой видно, что для выпуска единицы продукции, например, вида П2, требуется две единицы трудовых ресурсов, для выпуска единицы продукции вида ПЗ – четыре единицы материальных ресурсов и т. д. Кроме того, в табл. 3.9 показано наличие каждого вида ресурса, а также, исходя из требований спроса, заданы нижние и верхние предельные границы выпуска каждого вида продукции. На основании приведенных исходных данных составим математическую модель для определения плана выпуска продукции. Составление модели начнем с введения обозначений. Плановое количество выпускаемой продукции каждого вида, которое нам надо найти, обозначим соответственно x 1, x 2, x 3, x 4 (см. табл. 3.9). Перейдем далее к составлению ограничений. Из табл. 3.9 видно, что для выпуска единицы продукции вида П1 требуется одна единица трудовых ресурсов, для выпуска единицы видов продукции П2, ПЗ, П4 соответственно – две, три и четыре единицы трудовых ресурсов. Тогда потребный трудовой ресурс для выпуска всех видов продукции будет равен Очевидно, что потребный ресурс не может превышать располагаемый.

Значит, для трудового ресурса справедливо неравенство где 40 – располагаемый трудовой ресурс (см. табл. 3.9).

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

В этой системе неравенства, устанавливающие зависимости для ресурсов, являются ограничениями, а предельно допустимые значения переменных – граничными условиями. В ограничениях левые части неравенства представляют собой потребные ресурсы, а правые – располагаемые. Если в неравенства ввести дополнительные переменные y1 0; y 2 0; y 3 0, то можно записать:

В этой системе дополнительные переменные представляют собой разность между располагаемым ресурсом и потребным и, следовательно, равны неиспользуемому ресурсу. Иными словами, дополнительные переменные – это резервы каждого вида ресурсов.

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

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

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

ЛИБО ПРИ ЗАДАННЫХ РЕСУРСАХ МАКСИМИЗИРОВАТЬ ПОЛУЧАЕМЫЙ РЕЗУЛЬТАТ;

ЛИБО ПРИ ЗАДАННОМ РЕЗУЛЬТАТЕ МИНИМИЗИРОВАТЬ ИСПОЛЬЗУЕМЫЕ РЕСУРСЫ.

Если обозначить Q – ресурсы, R – результат их применения, то при заданных зависимостях результата и потребных ресурсов от количества выпускаемой продукции R = f ( x j ); Q = f ( x j ) две постановки задачи распределения ресурсов можно записать следующим образом:

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

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

Возвращаясь к нашей задаче, рассмотрим ее при двух следующих постановках: максимизация прибыли при данных ресурсах; минимизация ресурсов при заданной прибыли. Для составления математической модели нам потребуются дополнительные данные. Для первой постановки задачи необходимо знать прибыль, получаемую с единицы продукции. Для продукции видов П1, П2, П3, П4 принимаем прибыль соответственно равной 60, 70, 120, 130. Тогда для первой постановки задачи к системе (3.6) добавим целевую функцию и получим математическую модель:

Для второй постановки задачи необходимо задаться значением требуемой прибыли. Принимаем ее равной 1000. Тогда будем иметь:

Поскольку y 1, y 2,y 3 представляют собой резервы по ресурсам, то максимизация их суммы обеспечивает минимизацию используемых ресурсов F min. Оптимальное решение задач (3.10) и (З.11) приведено в табл. 10, в которой R – прибыль, Q – суммарный используемый ресурс.

Поста- Целевая Граничные нов- функция условия Из рассмотрения данных табл. 3.10 видно, что для двух различных постановок задачи получены совершенно разные решения. В первой постановке максимальная прибыль R1 = 1350, общее число использованных ресурсов Q1 = 219. При этом ресурсы оказались подразделенными на две группы: лимитирующие, для которых y i = 0, и нелимитирующие, для которых y i > 0. К первой группе относят финансы, ко второй – трудовые и материальные ресурсы.

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

Но вернемся к анализу решения для второй постановки, в которой общее число использованного ресурса Q2 = 137, для всех ресурсов имеются резервы y1, y2, y3, значение которых больше нуля. Следовательно, все ресурсы нелимитирующие. Дальнейшее уменьшение используемых ресурсов ограничивается требованием, согласно которому прибыль должна быть не менее 1000.

Нашу задачу составления плана при заданных значениях ресурса и прибыли мы решили в двух постановках. Оба решения являются оптимальными. Право выбора из них предпочтительного варианта предоставляется лицу, принимающему решение (ЛПР). В помощь ему можем сказать, что возможным подходом при выборе из ряда оптимальных решений может служить оценка эффективности = R / Q, показывающая отношение полученного результата к затраченным ресурсам. Для наших постановок, как это видно из табл. 3.10, 1 = 6.16; 2 = 7.3. Следовательно, в смысле эффективности предпочтительнее второй вариант. Но напомним, что только в смысле эффективности, так как прибыль в этом варианте существенно меньше.

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

После этого небольшого отступления вернемся к нашей задаче. Систему (3.10) более компактно можно представить в виде:

Если от рассматриваемого случая (3.12) перейти к общему с числом переменных n и ограничений m, то можно записать:

где cj – коэффициент в целевой функции; a i j – норма расхода i-го ресурса для выпуска единицы j-й продукции; b j – располагаемый ресурс; d j и D j – минимальное и максимальное допустимые значения xj.

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

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

3.3. Решение задачи оптимизации в случае неопределенности Допустим, что необходимо дополнительно изготовить 20 КПП, но сырьевых ресурсов для этого нет, что, к сожалению, имеет место быть на заводахизготовителях. Это происходит в том случае, когда планы не сбалансированы по номенклатуре, нормам расходов материалов и сырью. Не вызывает сомнения, что работать по несбалансированным планам невозможно. Именно несбалансированный план порождает нарушения производственной дисциплины:

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

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

Вернемся к нашей задаче распределения ресурсов, условия которой приведены в табл. З.9, а математическая модель имеет вид (3.6). В условия этой задачи внесем два изменения. Раньше мы говорили, что выпуск продукции П1 должен быть в интервале 1 x1 12, а выпуск продукции П2 не является обязательным, т. е. x 2 0.

Теперь в связи с изменившимся спросом необходимо выпускать продукцию П1 в количестве не менее 12, а П2 – не менее 5 ед. Условия задачи с учетом данных, приведенных в табл. 3.9, и дополнительными требованиями приведены в табл. 3.11.

Характеристика Граница:

Из этой таблицы не видно, вызывает ли такое дополнительное условие несбалансированность плана. Для ответа на этот вопрос составим математическую модель задачи:

В результате решения этой задачи оказывается, что задача не имеет решения, так как она не сбалансирована по ресурсам. Покажем это только на примере второй строки, в которой записано условие для материальных ресурсов. Для проверки сбалансированности подставим вместо хj значения, равные нижним границам этих переменных, т. е. проверим, хватит ли материальных ресурсов для выполнения плана на нижнем пределе допустимых значений. При этом потребный ресурс 6 12 + 5 5 + 4 2 + 3 3 = 114, что больше располагаемого ресурса, который равен 100. Не будем проверять несбалансированность по другим ресурсам. Решая задачу распределения ресурсов до получения решения, мы не знаем, естественно, сбалансирована она или нет. Поэтому в том случае, когда есть подозрение, что задача может оказаться несбалансированной, имеет смысл сразу же составить математическую модель с учетом возможной недостачи ресурсов. В такой модели отличия будут в ограничениях по ресурсам, которые представим так:

где у1, у2, у3 – количество необходимого дополнительного ресурса. Если в результате решения окажется, что yi = 0, значит, дополнительных ресурсов не требуется.

В том случае, если мы хотим минимизировать дополнительные ресурсы, целевая функция F1 = y1 + y 2 + y 3 min Так как целевая функция может быть только одна, а нас интересует размер получаемой прибыли, включим ее значение в систему. Тогда окончательно наша система будет иметь вид:

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

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

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

Следовательно, одним из методов преодоления несбалансированного плана является увеличение ресурсов. А если ресурсы добавить нельзя, можно ли получить сбалансированный план?

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

Глава 4. ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

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

Итак, рассмотрим неравенство:

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

В модель задачи (3.13), приведенной в гл. 3, входят неравенства вида где n – число неизвестных; m – число неравенств.

Если в каждое неравенство добавить неотрицательное неизвестное y i 0, i = 1, m, то от системы неравенств можно перейти к системе уравнений В этой системе общее число неизвестных где n – число основных неизвестных x j ; m – число дополнительных неизвестных у i, которое равно числу уравнений.

Возможны три варианта соотношений величин N и m.

1. Число неизвестных меньше, чем число уравнений: N m. Например, Очевидно, что все значения x1 и x2 лежащие на прямой, изображенной на рис. 4.1, являются решением уравнения (4.3). Значит, уравнение (4.3) имеет бесчисленное множество решений.

Рис. 4.1. Графическое представление уравнения Итак, если в системе число неизвестных N больше, чем число уравнений m, то такая система имеет бесчисленное множество решений.

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

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

Чтобы построить это уравнение, найдем его точки пересечения с осями координат. При x1 = 0 получим а2x2 = b, откуда x2 = b/a2. При x2 = 0 будем иметь вид a1x1 = b и x1 = b/a1.

На рис. 4.2 построено это линейное уравнение и показаны отрезки, которые отсекает прямая на осях координат.

Рис. 4.2. Графическое представление уравнения Разделим теперь левую и правую части уравнения на b и запишем уравнение (4.3) следующим образом:

Введем обозначения 1 = b / a1 ; 2 = b / a 2 ;

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

Поясним это на примере.

Пусть нам надо построить уравнение Представим это уравнение в форме уравнения в отрезках Значит, отрезки равны 1 = 1; 2 = 2. Уравнение (4.5) построено на рис. 4.1.

Рассмотрим еще одну форму представления уравнения (4.3). Запишем это уравнение так:

Введем обозначения:

Тогда уравнение (4.3) будет иметь вид Из уравнения (4.6) видно, что при x1 = 0 x2 = F. Следовательно, свободный член F – это отрезок, который отсекает прямая на оси ординат, что показано на рис. 4.3. Напомним, что k = tq называют угловым коэффициентом и форму записи (4.6) – уравнением прямой с угловым коэффициентом. Анализируя рис. 4.3, сделаем важный вывод, который нам потребуется в дальнейшем:

при увеличении F прямая перемещается параллельно самой себе в направлении, показанном стрелками.

Рис. 4.3. Графическое представление уравнения Вспомним неравенства. Если линейное уравнение с двумя переменными (4.3) может быть представлено в виде прямой на плоскости, то неравенство изображается как полуплоскость.

Так неравенство представляет собой полуплоскость, показанную на рис. 4.4. На этом рисунке часть плоскости, не удовлетворяющая неравенству, заштрихована. Координаты всех точек, принадлежащих незаштрихованной полуплоскости, имеют такие значения x 1 и x 2, которые удовлетворяют заданному неравенству. Значит, эти значения составляют область допустимых решений (ОДР).

Рис. 4.4. Графическое представление уравнения Рассмотрим построение системы линейных неравенств. Такое построение сделаем для системы:

Для удобства построения неравенства можно записать в форме, аналогичной уравнениям в отрезках:

Система (4.9) построена на рис. 4.5. Решением этой системы неравенств являются координаты всех точек, принадлежащих ОДР, т. е. многоугольнику ABCDO. Поскольку в ОДР бесчисленное множество точек, Рис. 4.5. Графическое представление системы уравнений значит, рассматриваемая задача имеет бесчисленное множество допустимых решений. Следует подчеркнуть, что не любая система линейных неравенств имеет ОДР, т. е. допустимые решения. Поясним это на примере. Построим систему Система (4.10) построена на рис. 4.6, из которого видно, что нет таких точек, которые удовлетворяли бы всем неравенствам, входящим в простую систему (4.10).

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

С увеличением числа переменных выше трех, геометрическая интерпретация невозможна, но система линейных неравенств также будет представлять собой ОДР в k - мерном пространстве. При этом мерность пространства k определяется следующим образом: если ограничения заданы в виде неравенств, то k = n, где n – число переменных; если ограничения заданы в виде уравнений, то k = n - m, где m – число уравнений.

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

4.2. Графическое решение задач линейного программирования Задачу линейного программирования можно решать аналитическими и графическими методами. Аналитические методы, которые представляют собой последовательность вычислений по некоторым правилам, являются основой для решения задачи. Их единственный недостаток заключается в том, что в отличие от графических методов они недостаточно наглядны. Графические методы достаточно наглядны, но они пригодны лишь для решения задач на плоскости, т. е. когда мерность пространства k = 2. Однако, учитывая большую наглядность графических методов, мы с их помощью рассмотрим идею решения задачи линейного программирования на примере задачи распределения ресурсов.

Пусть для двух видов продукции П1 и П2 требуются трудовые, материальные, финансовые ресурсы. Наличие ресурсов каждого вида и их нормы расхода, необходимые для выпуска единицы продукции, приведены в табл. 4.1.

Характеристика Резервы:

Составим математическую модель задачи. Аналогично моделям, рассмотренным в гл. 3, ограничения и граничные условия, входящие в модель этой задачи, будут иметь вид:

Модель (4.11) представляет собой систему линейных неравенств (4.9), которую мы уже рассматривали в качестве примера при построении системы линейных неравенств. Значит, ОДР нашей задачи – это многоугольник, показанный на рис. 4.5. Координаты каждой точки ОДР представляют собой допустимое решение этой задачи.

Рис. 4.7. Графическое представление уравнения Если мы хотим найти оптимальное решение, то должны принять целевую функцию. Допустим, мы хотим, чтобы решение было оптимальным в смысле максимизации суммарного выпуска. Тогда целевая функция Эту зависимость представим в форме уравнения прямой с угловым коэффициентом (4.6) Из графика данного уравнения (рис. 4.7) следует, что tga = -1. При этом yгoл = 135°, а величина F равна отрезку, отсекаемому прямой на оси ординат. Если прямую перемещать параллельно самой себе в направлении, указанном стрелками, то эта величина будет возрастать. Совместим теперь ОДР, изображенную на рис. 4.5, с линией целевой функции (4.12), построенной на рис. 4.7, как это показано на рис. 4.8, а. Поскольку нам требуется найти оптимальное решение, при котором целевая функция т. е. стремится к максимуму, будем перемещать линию целевой функции в направлении увеличения F. Очевидно, что оптимальным решением будут координаты точки С, равные x1* и x 2. При этом F = F *.

Рис. 4.8. Графическое представление решения задачи На основании рассмотренного, можно сделать исключительно важный вывод: оптимальным решением являются координаты вершины ОДР. А из этого вывода следует метод решения задачи линейного программирования. Этот метод заключается в следующем.

1. Найти вершины ОДР как точки пересечения ограничений.

2. Определить последовательно значения целевой функции в вершинах.

3. Вершина, в которой целевая функция приобретает оптимальное (максимальное или минимальное) значение, является оптимальной вершиной.

4. Координаты оптимальной вершины являются оптимальными значениями искомых переменных.

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

Мы должны выпускать продукцию двух видов П1 и П2. На выпуск каждого вида продукции требуется один вид ресурсов, который имеется в количестве 6 единиц. Количества ресурсов, необходимые для выпуска единиц продукции П1 и П2, одинаковые и равны 2 ед. Требуется определить, сколько продукции каждого вида следует изготавливать, чтобы суммарный выпуск ее был максимальным.

Мы уже знаем, что математическая модель такой задачи может быть записана так:

Ограничения в форме уравнения в отрезках имеют вид что на рис. 4.8, б соответствует прямой АВ. При этом ОДР является равносторонним прямоугольным треугольником ОАВ. Значит, угол АВО равен 45°.

Целевая функция в форме уравнения с угловым коэффициентом имеет следующий вид:

где tg = -1 и, следовательно, угол наклона линии целевой функции = 135°.

Таким образом, в данном случае линия целевой функции совпадает со стороной ОДР, равной АВ. При этом координаты каждой точки, лежащей на прямой АВ, являются оптимальным решением задачи. Но мы уже говорили, что в общем случае решением являются координаты вершин. Следовательно, в данном случае задача имеет два решения. В первом случае это координаты вершины А, равные x1* = 0; x 2 = 3 ; при этом выпуск Во втором случае это координаты вершины В, равные x1* = 3; x 2 = 0 при этом выпуск т. е. для разных значений переменных мы получили одно и то же значение целевой функции.

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

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

А теперь вернемся к общему случаю.

Определение координат вершин ОДР в практических задачах со многими переменными и ограничениями требует очень больших объемов вычислений. В связи с этим для аналитического решения задач линейного программирования разработан специальный алгоритм направленного перебора вершин. Этот алгоритм обеспечивает переход от одной вершины к другой в таком направлении, при котором значение целевой функции от вершины к вершине улучшается. В геометрии есть такое понятие «симплекс». Симплексом тела в k - мерном пространстве называют совокупность k+1 его вершин. Так, для плоскости при k = симплексом будут три вершины треугольника, при k = 3 – четыре вершины четырехгранника, например, тетраэдра, и т. д. С учетом этого понятия аналитический метод решения задачи линейного программирования называют симплексметодом. Определение значения целевой функции и переменных в одной вершине считается итерацией. Число итераций зависит от числа переменных и в реальных задачах может измеряться сотнями. Вручную с помощью симплексметода могут быть решены задачи, содержащие не более десяти переменных.

Поэтому в реальных задачах поиска оптимального решения необходимо применять ЭВМ и прикладное программное обеспечение.

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

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

Поясним это на рассмотренном ранее примере (4.11). В нем было задано пять ограничений (включая требования x 0 x2 0 ). Выше мы находили оптимальное решение по максимизации суммарного выпуска Найдем оптимальные решения еще для четырех целевых функций:

максимизации выпуска продукции П максимизации выпуска продукции П максимизации прибыли где коэффициенты перед x1 и x2 взяты из таблицы исходных данных (см. табл. 4.1);

минимизации используемых ресурсов F3 = (1 + 3 + 6) x1 + (4 + 4 + 2) x 2 min, т.е. F5 = 10 x1 + 10 x 2 min.

Для каждой приведенной целевой функции аналогично тому, как это делалось для F1, можно построить линию целевой функции и определить вершину, в которой целевая функция будет иметь оптимальное значение. Результаты решения задачи по пяти целевым функциям сведены в табл. 4.2, из анализа которой можно сделать следующий вывод: координаты каждой вершины могут быть оптимальным решением задачи в некотором принятом смысле. Так, вершина С дает максимальный суммарный выпуск, вершина А – максимальный выпуск продукции П2 и т. д.

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

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

В МНОГОПАРАМЕТРИЧЕСКОЙ ОПТИМИЗАЦИИ

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

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

Как же в таком случае принимать оптимальное решение, которое согласно определению является наилучшим только в одном – единственном смысле? Задачи, в которых оптимизацию следует производить по нескольким параметрам, называют задачами многопараметрической, или векторной оптимизации. Предложен ряд методов многопараметрической оптимизации. Поскольку математическая модель задачи оптимизации включает три основные части: целевую функцию, ограничения и граничные условия, то любой метод многопараметрической оптимизации должен быть сведен к использованию этих основных частей. Некоторые методы многопараметрической оптимизации приведены в п. 5.2 и 5.4.

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

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

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

Пусть для выпуска трех видов продукции требуются три типа ресурсов.

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

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

Характеристика Продукция:

Задачу будем решать методом последовательных уступок. Суть этого метода заключается в том, что один из оптимизируемых параметров принимают в качестве целевой функции, а для других задают некоторые предельные значения граничных условий. Задачу решают в нескольких вариантах, которые отличаются друг от друга предельно задаваемыми значениями. Для задачи, условия которой приведены в табл. 5.1, в качестве целевой функции принимаем максимизацию объема выпуска продукции при условии, что показатель ее качества должен быть не меньше заданного значения. Тогда эту задачу можно записать в виде математической модели:

Результаты решения этой задачи для различных значений Кзад приведены в табл. 5.2. Анализ результатов дает основание сделать следующие выводы.

1. Повышение требований к качеству продукции приводит к уменьшению объема ее выпуска.

Характеристика Резерв ресурсов:

Действительно, в варианте 1, когда на уровень качества не накладывались какие-либо требования, был достигнут максимальный объем выпуска продукции Об, равный 1340. При этом качество К = 830. По мере увеличения требований к качеству Об уменьшается, и при заданном значении Кзад составляет 1198.

2. В зависимости от требований к качеству продукции меняется структура плана. Так, в варианте 1 продукция П1 вообще не выпускается, так как она дает наименьший объем, что видно из исходных данных, приведенных в табл. 5.1.

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

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

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

Характеристика Резерв ресурсов:

1. При реализации требований по увеличению объема выпуска ухудшается качество продукции.

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

Заметим, что полное использование всех видов ресурсов может быть только в задачах очень малой размерности, как в нашем примере. В реальных задачах распределения ресурсов всегда есть ресурсы, которые используются не полностью. Объединив результаты, приведенные в табл. 5.2 и 5.3, можно построить зависимость объемов выпуска продукции от ее качества. Для этого выпишем значения Об в рассмотренных вариантах и расставим их по мере возрастания качества К продукции:

На основании этих данных на рис. 5.1 построена зависимость Об = f (K).

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

Рис. 5.1. Зависимость Об = f (K) 1) по заданному качеству продукции К выявлять возможный объем ее выпуска Об; 2) по заданному объему Об определять возможное качество К. Таким образом, за качество продукции надо платить уменьшением объема ее выпуска. В связи с этим задача максимизации объемов Об при максимизации качества К не может быть выполнена. Применительно к данной задаче, как и в задачах распределения ресурсов, возможны две реальные ее постановки: 1) максимизация объемов Об при обеспечении качества К не ниже заданного значения; 2) максимизация качества К при обеспечении объемов Об не меньше заданного значения.

Для случая максимизации объемов Об при ограничении по качеству К модель (5.1) в общем виде можно записать следующим образом:

Для общего случая максимизации качества K при ограничениях по объему Об модель (5.2) примет вид:

В результате решения должны быть получены зависимости: в первом случае Об = f (Kзад), во втором – К = f (Обзад).

Таким образом, применяя метод последовательных уступок, можно установить зависимость объема выпуска продукции от качества и на основании этой зависимости выбирать связанные между собой оптимальные значения Об и К. Зависимость между этими параметрами получена в результате применения метода последовательных уступок представленной графиком функции Об = f (K).

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

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

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

Рассмотрим из них три.

Непосредственное назначение коэффициентов веса. Согласно этому методу, каждый i-й эксперт для каждого k-го параметра должен назначить коэффициент веса ik таким образом, чтобы сумма всех коэффициентов веса, назначенных одним экспертом для различных параметров, равнялась единице.

Это требование можно записать так:

где n – число экспертов.

По результатам экспертизы составляют табл. 5.4. В качестве коэффициента веса k-го параметра ik принимают среднее значение по результатам экспертизы всех экспертов Поясним этот метод на примере. Допустим, нас интересует сравнительная важность двух параметров: объема выпуска продукции и ее качества. Для экспертизы пригласили восемь человек. Результат экспертизы приведен в табл. 5.5, которая составлена по форме табл. 5.4.

На основании данных проведенной экспертизы по зависимости (5.4) находим значения экспертных оценок: 1 = 0.75; 2 = 0.25. Как показывает опыт, удовлетворение экспертами требования Если К > 3, вызывает затруднение. Для того чтобы избежать выполнения этого требования, можно определять коэффициенты веса другими методами, рассмотренными ниже.

Оценка важности параметров в баллах. В этом случае i-й эксперт назначает каждому k-му параметру оценку по десятибалльной системе. Наиболее важный параметр оценивают более высоким баллом. Заметим, что различным параметрам может быть назначен одинаковый балл. В результате экспертизы заполняется табл. 5.6. Далее определяется сумма для каждого эксперта И находится значение коэффициента веса.

Эксперт Эксперт Величины ik представляют собой исходные данные, полученные в ходе экспертизы по предыдущему методу и сведенные в табл. 5.4. После получения этих данных, как и в предыдущем методе, значение коэффициентов веса находят по зависимости (5.4). Поясним это на примере.

Допустим, в результате экспертизы получены данные, представленные в табл. 5.7. Просуммированные по строкам значения i проставлены в последнем столбце таблицы. С помощью зависимости (5.5) найдем значения ik, которые запишем в табл. 5.8, составленную по форме табл. 5.4. Затем по зависимости (5.4) определим значения коэффициентов веса, которые приведены в нижней строке табл. 5.8. Из рассмотрения нижней строки табл. 5.8 видно, что, несмотря на, казалось бы, отсутствие какой-либо закономерности в оценках, данных экспертами и приведенных в табл. 5.7, все параметры имеют примерно одинаковую относительную важность.

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

Пусть задано пять параметров: x1, x2, x3, x4, x5. Каждый i-й эксперт назначает парные соотношения Пусть для i-го эксперта получена табл. 5.9. Переход от данных табл. 5. к коэффициентам веса производится следующим образом: просуммируем значения для каждой строки, которые равны и запишем их в последнем столбце табл. 5.9; просуммируем величины для всех строк и найдем определим экспертную оценку i-го эксперта для k-го параметра по зависимости Для i-го эксперта, который составил табл. 5.9, получим значения:

1 = 0,3; 2 = 0,2; 3 = 0; 4 = 0,3; 5 = 0,2; Эти данные представляют собой строку для i-го эксперта в табл. 5.4. Получив аналогично значения по форме табл. 5. для остальных экспертов и выполнив приведенные вычисления, определим значения коэффициентов веса для всех экспертов ik, которые являются исходными данными для составления табл. 5.4. На основании табл. 5.4 по зависимости (5.4) можно найти коэффициенты веса для каждого параметра.

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

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

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

Приведем пример целевой функции, удовлетворяющей этим требованиям:

В этой целевой функции оптимизацию производят по К параметрам.

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

Таким образом, для оптимизации по такой целевой функции необходимо иметь дополнительные величины xkn и k. Посмотрим, каким образом назначаются эти величины. Значение нормирующей величины xkn можно назначать различными способами. Наиболее распространены два способа. В первом случае xkn = xk, где xk принимается из утвержденного документа, например, техзад зад нического задания. Если такой утвержденной величины нет, то можно решить задачу оптимизации при максимизации этой величины, т. е. F = xk max, и полученное в результате оптимизации значение x*k принять за нормирующее.

Следовательно, в этом случае xkn = x*k пертных оценок.

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

В качестве нормирующих значений Обn и Кn принимаем их максимальные значения, полученные в результате оптимизации отдельно по каждому параметру: Обn = 1340; Кn = 1028.

Если к целевой функции (5.7) добавить ограничения, составленные на основе данных, приведенных в табл. 5.1, то получим математическую модель:

Результаты решения этой задачи при различных значениях коэффициентов веса 1 и 2 приведены в табл. 5.10. Анализ табличных данных дает основание сделать следующие выводы.

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

Характеристика Резерв ресурсов:

2. Наиболее выгодной с позиции качества является продукция П1, наиболее невыгодной – продукция П2, которая при 2 =1 не выпускается.

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

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

Многоцелевое программирование. Идею этого метода продемонстрируем на нашем примере. Решая задачу последовательно по двум целевым функциям: максимизации объема и максимизации качества, мы получили результаты, согласно которым при располагаемых ресурсах максимально возможные значения объема выпуска и качества продукции соответственно равны 1340 и 1028. Следует отметить, что одновременно такие значения получены быть не могут.

Для иллюстрации возможностей рассматриваемого метода принимаем, что необходимо обеспечить одновременно выполнение экономических показателей Об = 1500, К = 1100. Очевидно, что при имеющихся ресурсах такие показатели не могут быть достигнуты. Значит, данная задача является несбалансированной между заданными экономическими показателями и располагаемыми ресурсами. Как же решить такую задачу? Прежде всего, составим математическую модель:

Поскольку данная задача является несбалансированной, то решения у нее нет или она имеет несовместное решение. Кроме того, в данной системе нет целевой функции. Для получения совместного решения, а также назначения целевой функции введем дополнительные переменные y1 y8 и запишем систему (5.9) в виде:

Дополнительные переменные у1, у2 показывают, насколько полученные значения объема выпуска и качества продукции отличаются от заданных;

y3 y5 определяют неиспользованный ресурс; y6 y8 равны значениям дополнительного ресурса, который необходимо иметь для решения поставленной задачи. Эти переменные являются тем средством, которое дает возможность избежать получения несовместного решения.

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

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

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

Результаты решения по обеим целевым функциям приведены в табл.

5.11. На основании анализа этих результатов можно сделать следующие выводы. При решении по первой целевой функции F1 заданные экономические показатели Об = 1500 и К = 1100 выполняются, при этом y1 = y2 = 0 ;

Характеристика Целевая функция Характеристика Целевая функция располагаемые ресурсы используются полностью, т. е. резервы ресурсов отсутствуют, так как y3 = y4 = y5 = 0; для достижения заданных экономических показателей требуются дополнительные ресурсы, которые определяются значениями y6 = 3,6; y7 = 20,2; y8 = 6,1. При решении задачи по второй целевой функции F2 заданные ресурсы используются полностью, резервов нет (y3 = y4 = y5 = 0);

дополнительные ресурсы не требуются, так как y6 = y7 = y8 = 0; величины Об и К не достигают заданных значений и равны соответственно 1260 и 930; отклонения от заданных значений определяются дополнительными переменными y = 240; y2 = 170.

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

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

При решении задачи оптимизации целью принятия оптимального решения является определение таких значений параметров, которые придают принятой целевой функции оптимальное, т. е. самое лучшее, значение из всех возможных. При этом в случае максимизации целевая функция приобретает максимально возможное значение, равное max F. Когда же мы решаем задачу выбора варианта, то после принятия некоторого критерия К выбираем такой вариант, для которого значение К является максимальным лишь из всех сравниваемых, где i – номер варианта. И нет никаких оснований утверждать, что лучший из выбранных вариантов является действительно оптимальным, т. е. лучшим из всех возможных. Более того, как правило, Метод выбора лучшего варианта рассмотрим на таком примере. Допустим, есть четыре варианта системы, которая характеризуется двумя параметрами: Q – производительность, шт./мин; С – стоимость, р. Значения этих параметров для всех вариантов приведены ниже.

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

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

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

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

где 1, 2 – коэффициенты веса; Qn, Сн – нормирующие значения Q и С. Знак минус перед вторым членом показывает, что возрастание стоимости снижает значение критерия. Таким образом, эта зависимость обеспечивает увеличение критерия при повышении производительности и уменьшении стоимости сравниваемых вариантов. Следовательно, лучшим является вариант, для которого значение К будет наибольшим, Для определения критерия типа (5.6) в качестве нормирующих значений принимаем QH = Qmax = 60; CH = Cmax= 500. При этом зависимость (5.6) имеет вид Относительную важность параметров будем оценивать коэффициентами веса.

Определим значения критерия для трех случаев: важна только производительность; при этом, следовательно, 1 = 1, 2 = 0 ; производительность и стоимость одинаково важны; значит, 1 = 0,5, 2 = 0,5 ; важна только стоимость, в этом случае 1 = 0, 2 = 1. Значения критериев применительно к этим трем случаям для четырех сравниваемых вариантов приведены в табл. 5.12, из рассмотрения которой видно, что наибольшее значение критерия зависит не только от параметров вариантов, но и от принятых коэффициентов веса.

Так, для случая 1 лучшим оказывается вариант 3, для случая 2 – вариант 4, для случая 3 – вариант 1. При этом вариант 2 ни в одном из рассмотренных случаев не будет лучшим.

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

Глава 6. ТЕОРИЯ ВЕРОЯТНОСТЕЙ ДЛЯ ПРИНЯТИЯ ОПТИМАЛЬНЫХ

РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТЕЙ

6.1. Основные понятия теории вероятностей Мы уже знаем, что значительную часть управленческих решений можно рассматривать как решение задач распределения ресурсов, математической моделью которых служит задача линейного программирования (3.13). До сих пор мы принимали, что в этой модели величины aij, bi, cj являются строго определенными, или детерминированными, и их точные значения нам известны. Однако на практике, к сожалению, такая определенность наблюдается далеко не всегда.

Например, величина bi обозначает имеющийся в наличии i-й ресурс. Не вызывает сомнения, что достаточно часто мы не можем точно сказать, сколько будет поставлено ресурса в течение планируемого периода, так как эта величина, в свою очередь, зависит от выделенных фондов, соответствия качества ресурса предъявляемым требованиям, своевременности поставки и т. д. Следовательно, величина bi зависит от множества различных факторов, которые заранее определить физически невозможно. При этом чем больше период планирования, тем больше неопределенность в оценке возможного значения bi. То же самое в полной мере относится к нормам расхода aij и коэффициентам в целевой функции сj.

Таким образом, есть все основания считать, что в реальных задачах распределения ресурсов входящие в модель величины aij, bi, cj, зависящие от ряда случайных факторов, являются случайными величинами и не могут быть определены однозначно. Значит, с одной стороны, объективно существует неопределенность. При этом чем больше период планирования, тем эта неопределенность больше. А с другой стороны, необходимо принимать четкие решения и в том числе составлять детерминированные планы.

Как измерить случай? Или, точнее, как оценивать случайность? Эта проблема является предметом специальной науки – теории вероятностей.

Для того чтобы пользоваться отдельными положениями теории вероятностей, введем некоторые понятия. Событием будем называть всякий факт, который в результате опыта может произойти или не произойти. Признак того, что данный факт является событием, состоит в том, что ответом на вопрос «произошло ли событие?» может быть либо «да», либо «нет». Примерами событий может служить своевременная поставка сырья и др. События могут быть достоверными, невозможными и возможными. Достоверным называют такое событие, которое непременно должно произойти. Достоверными событиями являются, например, расход ресурсов при выпуске продукции. Невозможным считают такое событие, которое не может произойти. В качестве примера невозможного события можно привести выпуск сверхплановой продукции без использования дополнительных ресурсов и др. Возможным называют такое событие, которое может либо произойти, либо не произойти. Примерами возможного события являются падение монеты гербом вверх, выполнение плана на 100 % и др.

Для выражения возможности события используют численную меру. Такую численную меру возможности события называют вероятностью. Вероятность события А, т. е. Р(А), можно вычислить по формуле где m – число случаев, когда событие А может произойти; n – общее число случаев.

Очевидно, что вероятность невозможного события равна нулю, достоверного – единице, возможного – от нуля до единицы.

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

Для оценки того, как часто события уже происходили, используют понятие частоты. Частота события А обозначается где m* – показывает, сколько раз событие произошло; n – общее число произведенных испытаний.

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

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

Такие числа называют случайными величинами. Случайная величина может принять то или иное значение, заранее неизвестное. Например, случайными величинами являются объем поставленного сырья, трудоемкость выполнения некоторой работы и др. Конкретное измеренное значение случайной величины называют ее реализацией. Различные реализации случайной величины относят к несовместным событиям. Действительно, если трудоемкость изготовления детали составила 100 чел.-ч, то она не может быть равна 105 чел.-ч или любому другому значению.

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

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

Математическое ожидание характеризует среднее значение случайной величины, обозначается Мx М [х] или x и определяется по зависимости где n – число реализаций; xi – значение случайной величины в i-й реализации.

Дисперсия Dx характеризует разброс значений случайной величины:

Поскольку размерность дисперсии равна квадрату размерности самой случайной величины, использовать дисперсию для относительной оценки, разброса значений случайной величины не представляется возможным. В связи с этим разброс оценивают среднеквадратическим отклонением x. Между дисперсией и среднеквадратическим отклонением существует зависимость Следовательно, Удобной характеристикой случайной величины, которая показывает относительное значение разброса случайной величины, является коэффициент вариабельности Определение характеристик случайной величины покажем на таком примере. Пусть случайной величиной является некоторый ресурс bi, имеющийся в наличии в каждом квартале. Реализацией этой случайной величины будет фактический объем этого ресурса для различных кварталов. Допустим, мы готовим материалы для составления плана будущего года в IV квартале. В нашем распоряжении есть отчетные данные за прошлый год и три квартала текущего года, которые приведены ниже.

Определим характеристики этой случайной величины.

Математическое ожидание Среднеквадратическое отклонение Коэффициент вариабельности Наиболее полной характеристикой случайной величины является закон ее распределения. Что же он характеризует? Ранее было отмечено, что сумма вероятностей всех несовместных событий равна единице и что различные реализации случайной величины являются несовместными событиями. Объединив эти два положения, можно, следовательно, сказать, что сумма вероятностей всех реализаций случайной величины также равна единице. Теперь перейдем к закону распределения.

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

Рис. 6.1. Зависимость f(x) от x Нормальный закон распределения имеет две формы представления:

плотность распределения и функцию распределения. График плотности распределения случайной величины х, находящейся в интервале А x B, показан на рис. 6.1, а. С помощью этого графика можно решать различные задачи. Например, можно определить; чему равна вероятность того, что случайная величина х будет не больше величины а, т. е. P( x a). Оказывается, эта вероятность равна заштрихованной площади. Зная P( x a), нетрудно установить вероятность того, что случайная величина х будет не меньше величины а, т. е.

P ( x a ). Очевидно, что Следовательно, что соответствует не заштрихованной площади, на рис. 6.1, а.

Однако площадь криволинейной фигуры вычислять достаточно сложно.

В связи с этим для решения практических задач широко применяют другую форму закона распределения – функцию распределения F(x), график которой приведен на рис, 6.1, б. Вероятность P( x a), определяемая на рис. 6.1, а как площадь криволинейной фигуры, на рис. 6.1, б равна ординате кривой F(x).

Следовательно, откуда Для облегчения расчетов при работе с нормальным законом распределения от реальной случайной величины х переходят к центрированной нормированной случайной величине Для; определения F(t) имеются специальные таблицы. Ниже приведены значения F(t) для некоторых t, на основании которых построен рис. 6.2.

Рис. 6.2. Зависимость F(t) от t По графику F(t) легко определить интересующие нас величины. Поясним это на примере. Предположим, надо определить, какова вероятность того, что наличный ресурс будет не менее 98. Очевидно, что Перейдем к значению t, которое для данного случая равно Ранее мы установили, что b = 100, b = 9. Следовательно, t = (98 - 100) / = - 0, Согласно представленным выше данным, F(- 0,25) = 0,4. Тогда окончательно получим Значит, вероятность того, что требуемый ресурс будет не меньше 98, равна 0,6.

С помощью функции распределения F(t) можно решать и обратную задачу, которая формулируется так: при каком значении ta вероятность появления случайной величины удовлетворяла бы условию где a – заданный уровень вероятности.

Так, из рассмотренного примера, также из приведенных выше данных и рис. 6.2 видно следующее. Если задаться уровнем вероятности a = 0,6, то соответствующее значение ta = 0,25.

6.2. Теория вероятностей в оптимизационных задачах в случае их неопределенности Известно, что значительная часть задач принятия решений сводится по форме к задачам составления планов, а по содержанию – к задачам распределения ресурсов. Математической моделью задачи распределения ресурсов является хорошо знакомая нам задача линейного программирования, в которой величины aij, bi, cj строго определены и, следовательно, являются детерминированными.

Однако в реальных условиях величины aij, bi, cj достаточно часто оказываются случайными. Такие задачи линейного программирования, в которых эти величины являются не детерминированными, а случайными, относятся к задачам стохастического программирования (СТП).