Основы исследования систем

Министерство образования и науки Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего образования «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРОМЫШЛЕННЫХ ТЕХНОЛОГИЙ И ДИЗАЙНА» Кафедра информационных технологий Моделирование и методы оптимизации Методические указания к выполнению контрольных работ для всех направлений Составитель Е. В. Кулеева Санкт-Петербург 2018 СОДЕРЖАНИЕ Лекционный материал ............................................................................................ 3 Лекция 1. Основы исследования систем ............................................................... 3 1.1. Определение системы и задач, решаемых для ее исследования ........... 3 1.2. Этапы исследования систем ...................................................................... 4 1.2.1. Словесная постановка задачи ............................................................. 4 1.2.2. Выбор показателя эффективности, математическая постановка задачи 5 1.2.3. Модели и их роль при исследовании систем .................................... 6 1.2.4. Моделирование функционирования систем ...................................... 8 Лекция 2. Модели и их виды .................................................................................. 9 2.1. Представление о геометрической модели................................................ 9 2.2. Представление о словесной модели ....................................................... 10 2.3. Представление о физической модели ..................................................... 10 2.4. Представление о математической модели ............................................. 11 Лекция 3. Задачи оптимизации ............................................................................ 12 Лекция 4. Методы линейного программирования ............................................. 12 4.1. Задача об оптимальном использовании ресурсов при производственном планировании. ................................................................... 13 4.2. Задача о смесях (планирование состава продукции) ............................ 16 4.3. Транспортная задача ................................................................................ 19 Методические указания к контрольной работе. Варианты решения. .............. 24 Работа № 1. Оптимизация работы станции технического обслуживания автомобилей ........................................................................................................... 24 Работа № 2. Задачи об оптимальном использовании ресурсов ........................ 28 Работа № 3. Задачи о смесях ................................................................................ 30 Работа № 4. Транспортная задача ........................................................................ 32 Лекционный материал Лекция 1. Основы исследования систем 1.1. Определение системы и задач, решаемых для ее исследования Система – это некоторое целостное образование, состоящее из отдельных элементов, которые связаны между собой материальными, энергетическими и информационными связями, и имеют специфические свойства, не присущие в полной мере всему этому образованию. Различают простые и сложные системы. Простые – это те, которые не меняют свои свойства и структуру во времени. Т.е. время рассмотрения этой системы так мало, что никакие изменения в ней не успевают произойти. Поэтому их еще называют с та тис тич ес ким и . Сложные – наоборот меняют состояние во времени. Их также могут называть дин ами че ски ми . Разделение на простые и сложные системы условно. В большинстве случаев удобнее рассматривать и изучать именно сложные системы. Им присущи следующие признаки: 1. Много взаимодействующих между собой элементов; 2. Возможность разбиения системы на подсистемы; 3. Наличие управления (обработка потоков информации); 4. Наличие взаимодействия с окружающей средой. Для того чтобы понимать системы необходимо их исследование, которое заключается в решении прямой и обратной задачи. Прямая задача решается при исследовании существующей системы: известен состав системы; необходимо совершенствовать еѐ структуру, чтобы повысить, например, эффективность функционирования. Прямую задачу исследования систем можно также назвать реинжинирингом. Обратная задача решается при создании новых до сих пор не существующих систем, т.е. здесь уже необходимо определить: неделимые операции и их задачи; элементы системы, имеющие заданные свойства, но при этом будут известны: цель функционирования системы; задачи элементов; функция системы. Обратную задачу исследования систем можно назвать инжинирингом. Однако в чистом виде прямую и обратную задачу практически не используют. Например, при модернизации существующей системы, когда заданный состав системы по свойствам и количеству не позволяет найти эффективный вариант структуры системы, то решается дополнительная задача нахождения нужных элементов. В то же время при решении создать новую систему часто используют в качестве ее составных элементов ранее модернизированные и когда-то успешные системы. Для того чтобы решить ту или иную задачи исследования систем, необходимо пройти определенные этапы. 1.2. Этапы исследования систем Основными этапами исследования систем являются: - словесная постановка задачи; - выбор показателя эффективности (целевой функции); - математическая постановка задачи; - разработка модели функционирования системы; - моделирование функционирования системы – сравнение альтернативных вариантов функционирования системы по выбранной целевой функции (показателю эффективности); - принятие решения. Последний этап очень важен. Все остальные этапы существуют ради того, чтобы было принято решение о назначении, составе и структуре системы. 1.2.1. Словесная постановка задачи На этом этапе делается описание объекта и более подробно описание предмета исследования. Выделяются проблемы, связанные со структурой и составом системы. Формулируются актуальность, цель и задачи исследования. Определяются границы исследования, т. е. предельные значения входных и выходных характеристик системы. Описание предмета исследования делается вначале словесным (вербальным), а затем графическим (блок-схемами). Структура описания зависит от того, какую задачу исследования системы необходимо решить. Если это задача прямая, то вначале описываются элементы системы, их свойства и задачи. Затем описываются элементарные и составные или системные операции и их цели. Далее определяется совокупность и последовательность операций, которые могут привести к главной цели функционирования системы. Если это обратная задача исследования системы, то вначале описывается совокупность и последовательность операций, которые могут привести к главной цели, а затем свойства элементов, которые они должны иметь для участия в этих операциях. При этом используется накопленный опыт и результаты наблюдений за процессами функционирования аналогичных реальных систем с учетом особенностей проектируемой системы. 1.2.2. Выбор показателя эффективности, математическая постановка задачи Когда определены проблемы, границы исследования, цель и задачи функционирования системы, то можно приступить к выбору показателя эффективности функционирования, который покажет достигает система цели или нет, и если достигает, то насколько. Под показателем эффективности функционирования сложной системы понимается такая ее числовая характеристика, которая оценивает степень приспособленности системы к достижению поставленной перед ней цели. Для оценки ожидаемой эффективности деятельности некоторого предприятия могут быть приняты следующие два типа показателей эффективности. Первый – вероятность события, например, выполнение заказа в заданное время. Второй – математическое ожидание (среднее значение), если целью является достижение максимальной производительности. Для оценки больших по объему, сложных по физической сущности процессов возникает необходимость привлечения нескольких показателей эффективности. Один из них будет основным, остальные дополнительными. Основной должен соответствовать главной цели функционирования, а дополнительные – характеризовать состояние элементов. Например, если предприятие имеет цель выполнить заказ, то основным показателем эффективности может быть вероятность его выполнения в заданное время. Дополнительными показателями могут стать расход материальных средств, энергии и т. п. Если при этом решается прямая задача исследования систем, то основной показатель максимизируется, а дополнительные показатели выступают в виде ограничений. При решении обратной задачи основной показатель фиксируется на заданном уровне и становится одним из ограничений, а один из бывших дополнительных показателей, например, материальные ресурсы, минимизируется. В связи с этим, при решении обратной задачи исследования систем показатель эффективности называют целевой функцией. В общем случае основные или дополнительные показатели эффективности (целевые функции) должны быть критичными (чувствительными) к структуре системы, свойствам и количеству ее элементов. Только тогда их можно использовать для оценки степени достижения цели и получения правильных для принятия решений рекомендаций. После выбора показателя эффективности (целевой функции), являющегося фактически математической мерой цели исследования системы, записанной в виде функционала от характеристик системы, формулируется математическая постановка задачи. Математическая постановка задачи соответствует словесной постановке и представляет собой совокупность математических выражений показателя эффективности (целевой функции), а также ограничений области исследований (значений выходных характеристик системы) начальных и предельных значений входных характеристик системы. Математическая постановка задачи предшествует разработке моделей функционирования исследуемой системы. 1.2.3. Модели и их роль при исследовании систем Исследования систем можно выполнить двумя способами: - путем обработки данных натурного эксперимента, проводимого над системой; - путем обработки данных эксперимента, проводимого над моделью системы. Изучение существующих систем первым способом в большинстве случаев нецелесообразно из-за огромных расходов. Поэтому метод исследования систем с помощью проведения эксперимента на их моделях стал основным, хотя возможно и сочетание – эксперимент с элементом системы и моделью системы в целом. Вообще говоря, вся история развития естественных наук – это история создания и совершенствования тех или иных моделей. Здесь можно назвать геоцентрическую и гелиоцентрическую модели солнечной системы, предложенные Птолемеем и Коперником, модели строения вещества, последовательно сменявшие друг друга в химии, различные модели атома и его ядра (планетарная, капельная и квантовая), математические модели, описывающие взаимодействия тел, Ньютона и Эйнштейна и многие другие. Что касается настоящего времени, то можно привести огромное количество примеров использования моделей различных природных явлений и систем с целью изучить их. Накоплен большой опыт по созданию разнообразных видов моделей различной степени сложности. Определение модели коротко можно сформулировать следующим образом. Модель – это естественный или искусственный объект, находящийся в соответствии с изучаемым явлением или какой-либо его стороной. Другими словами, модель (лат. modulus) – это объект, заменяющий оригинал и обеспечивающий воспроизведение некоторых его свойств [1]. Разнообразие моделей, применяемых в различных областях науки и техники, чрезвычайно велико. С точки зрения сложности и степени детализации можно предложить следующую иерархию моделей. На первом уровне иерархии находятся простые модели – вербальные. Второй уровень иерархии предполагает задание моделей с помощью структурных, функциональных и принципиальных схем. К этому уровню относятся, например, информационные модели, отражающие состав и структуру информационных систем. Модели этих двух уровней могут входить в состав первого этапа исследования систем – этапа постановки задачи. Третий уровень иерархии – это геометрические, физические и математические модели, которые обеспечивают наибольший уровень детализации. Геометрические модели отражают внешние, наглядные стороны системы и используются в основном для демонстрационных целей (макеты архитектурных сооружений, кораблей и т.п.). Эти модели могут выступать как экспонаты выставок. Физические модели наиболее полно отражают свойства системы. Они имеют внешнее сходство и одинаковую физическую природу с системой. Например, действующие макеты электростанций, железных дорог и т.п. Физические модели находят применение в тех случаях, когда производится многократное в течение длительного времени исследование систем. Математические модели реальных систем представляют собой совокупность соотношений (например, формул, уравнений, неравенств, логических условий и т. д.), определяющих характеристики функционирования системы, входных переменных, начальных условий и времени. Математические модели лишены внешнего сходства с системой, но отражают глубокие ее свойства, касающиеся реакции на внешние воздействия. Математические модели можно разделить: - на аналитические, в том числе вероятностные; - статистические; - имитационные, которые включают аналитические и статистические элементы (блоки). При построении аналитических моделей для описания исследуемых процессов используются методы математического анализа, теории вероятностей, математического программирования, теории массового обслуживания и т.д. Для разработки статистических моделей могут применяться методы прикладной статистики. Имитационные модели получили широкое распространение с развитием вычислительной техники и информационных технологий. Любая модель представляет собой упрощение реальной ситуации. Хорошая модель учитывает существенные черты изучаемого процесса и, что не менее важно, игнорирует несущественные. В связи с этим возникает вопрос об оценке адекватности модели, ее близости к оригиналу. Имеются два подхода к решению этой проблемы – сравнение поведения объекта и модели и сравнение их структуры. Согласно первому подходу объект и модель считаются близкими, если с достаточной степенью точности совпадает их поведение, т.е. близки реакции на одинаковые входные воздействия. Такой подход обычно применяют для систем с неизвестной внутренней структурой. Согласно второму подходу объект и модель считаются близкими, если совпадают их структуры. Обычно это совпадение реализуется при построении имитационных моделей. Как правило, первый подход оценки адекватности может использоваться при решении прямой задачи, а второй – при решении обратной задачи исследования систем. 1.2.4. Моделирование функционирования систем Моделирование – это замещение объекта моделью для получения информации о нем путем проведения экспериментов с его моделью. Остановимся кратко на следующих методах использования математических моделей или моделирования: - аналитические исследования процессов; - исследование процессов при помощи численных методов (с применением ЭВМ); - исследование процессов на ЭВМ непрерывного действия – аналоговых или моделирующих машинах; - моделирование процессов на цифровых ЭВМ. Как правило, математическая модель в своем первоначальном виде не может быть использована для аналитического исследования процесса (искомые величины находятся в неявном виде). Необходимо преобразовать математическую модель в такую систему отношений относительно искомых величин, которая допускает получение результата аналитическими методами, например в системе явных формул для искомых величин, либо приведение уравнений к виду, для которого методы решения известны. Аналитическое исследование является наиболее полным решением задачи моделирования, однако воспользоваться им не всегда удается, так как преобразование математической модели в систему уравнений, допускающую эффективное решение, является очень трудной задачей, а для сложных систем эти трудности часто оказываются непреодолимыми, несмотря на упрощение модели для получения хотя бы приближенного решения. В тех случаях, когда не удается преобразовать математическую модель в подходящую систему уравнений, а упрощение модели приводит к недопустимо грубым результатам, от аналитического исследования или моделирования отказываются. Более широкую сферу применения математической модели имеет исследование процессов с помощью численных методов и ЭВМ. Содержание работ при численном исследовании процессов остается в основном такими же, как и при использовании аналитических методов. Разница состоит в том, что после преобразования математической модели в систему уравнений последние решаются численными методами. Класс уравнений, которые могут быть решены приближенно численными методами, значительно шире, чем класс уравнений, доступных аналитическому исследованию. Однако математические модели сложных процессов, очень трудно преобразовать в соответствующую систему уравнений, которую можно решать численными методами. При моделировании процессов с помощью аналоговых ЭВМ математическую модель необязательно преобразовывать в специальную систему уравнений относительно искомых величин. Для оценки искомых величин в аналоговых машинах используется информация, циркулирующая в модели. Математическая модель дает возможность выбрать процесс-аналог подходящей природы и установить значения соответствующие коэффициентам подобия. Недостатком аналогового моделирования является то обстоятельство, что аналоговые вычислительные машины не могут быть универсальными. Они строятся для решения только определенного класса задач (например, решение линейных дифференциальных уравнений). К сожалению, во многих случаях аналитическое, численное или аналоговое моделирование вообще невозможно использовать для исследования случайных процессов. Наиболее универсальным методом моделирования является моделирование с помощью цифровых ЭВМ. Для этого необходимо преобразовать математическую модель в специальный моделирующий алгоритм или расчетный алгоритм, который затем описывается алгоритмическим языком. Особо следует отметить реализуемое цифровыми ЭВМ имитационное моделирование, при котором математическая модель имитирует почти полностью реальный процесс. Оно применяется в основном для исследования сложных систем, для которых, как правило, неизвестны закономерности взаимодействия различных операций составляющих функционирование системы, и воздействия на нее различных случайных факторов. Лекция 2. Модели и их виды Моделирование - это замещение одного объекта (оригинала) другим (моделью) для дальнейшей фиксации и изучения свойств модели. Замещение производится с целью упрощения, удешевления, ускорения изучения свойств оригинала. Модель - это система со своими множествами параметров и характеристик. Оригинал и модель сходны по одним параметрам и различны по другим. Замещение одного объекта другим правомерны, если интересующие исследователя характеристики оригинала и модели определяются однотипными параметрами и связаны одинаковыми зависимостями с этими параметрами. 2.1. Представление о геометрической модели Простейшим видом моделей являются геометрические модели. Они передают внешние признаки объекта, размеры, форму, цвет. Геометрические модели подобны своему прототипу (оригиналу). Они служат в основном для учебных и наглядных целей, при проектировании сооружений, конструировании различных устройств и изделий. Макет здания, корабля, рельефная карта местности, иногда с изменением мерности пространства (плоский рисунок или фотография трехмерных объектов и т.д.) — все это геометрические модели. Геометрическая модель — представление о внешних признаках реального объекта. Геометрическая компьютерная модель — представление информационной модели с помощью средств графики. Приступая к геометрическому моделированию, следует выделить его объект, определить цели моделирования, сформировать информационную модель в соответствии с задачей и выбрать инструмент моделирования. 2.2. Представление о словесной модели Словесные модели – это такие модели создаются с помощью слов на обычном языке. Важно следующее: то, что описано словами, уже является моделью, так как словесное описание – это более или менее точное отражение оригинала. Словесная модель – это письменное или устное представление информационной модели средствами разговорного языка. Словесные модели могут описывать ситуации, события, происходящие в жизни, с целью их осмысления и использования опыта. С помощью словесных моделей описывают также и процессы. Часто словесная модель какого-либо процесса составлена в виде алгоритма, где четко выделены действия и объекты, над которыми они совершаются. Однако важна польза и наглядность графической информации. Поэтому в книгах, учебниках словесные модели дополняются рисунками, диаграммами, таблицами. 2.3. Представление о физической модели Физической моделью называют систему, эквивалентную или подобную оригиналу, но возможно имеющую другую физическую природу. Виды физических моделей:  натуральные;  квазинатуральные;  масштабные;  аналоговые. Натуральные модели - это реальные исследуемые системы (макеты, опытные образцы). Имеют полную адекватность (соответствия) с оригиналом, но очень дорогие. Квазинатуральные модели совокупность натуральных и математических моделей. Этот вид используется, когда модель части системы не может быть математической из-за сложности еѐ описания (модель человека оператора) или когда часть системы должна быть исследована во взаимодействии с другими частями, но их ещѐ не существует или их включение очень дорого, например (вычислительные полигоны, АСУ) Масштабная модель - это система той же физической природы, что и оригинал, но отличается от него масштабами. Методологической основой масштабного моделирования является теория подобия. Аналоговыми моделями называют системы, имеющие физическую природу, отличающуюся от оригинала, но сходные с оригиналом процессы функционирования. Для создания аналоговой модели требуется наличие математического описания изучаемой системы. В качестве аналоговых моделей используются механические, гидравлические, пневматические и электрические системы. 2.4. Представление о математической модели Математическая модель – описание объекта или процесса математическими формулами, связывающими их количественные параметры. При описании математических моделей используются различные системы обозначений, принятые в той или иной науке. В учебниках формулы дополняют описательную модель, делают ее более наглядной, запоминающейся. Математические модели, как и словесные, — это продукт творческой деятельности человека. Компьютер позволяет на качественно новом уровне перевести мысленную модель в знаковую форму. Математические модели можно классифицировать на детерминированные и вероятностные, аналитические, численные и имитационные. Аналитической моделью называется такое формализованное описание объекта, которое позволяет получить решение уравнений, описывающих ее работу в явном виде, используя известный математический аппарат. Численная модель характеризуется такими уравнениями, которые допускают только частные решения для конкретных начальных условий и количественных параметров моделей. Имитационная модель - это совокупность описания системы и внешних воздействий, алгоритмов функционирования системы или правил изменения состояния системы под влиянием внешних и внутренних возмущений. Они позволяют имитировать процесс функционирования системы и производить вычисления интересующих характеристик. Имитационные модели могут быть созданы для более широкого класса объектов и процессов, чем аналитические и численные. Лекция 3. Задачи оптимизации Оптимизацией в общем случае называют поиск наилучшего в некотором смысле решения, а методы оптимизации являются соответствующим математическим инструментом. Задача оптимизации появляется, когда желаемый эффект какого-либо процесса сложным образом зависит от некоторой переменной, например, при ее изменении эффект вначале увеличивается, а затем уменьшается. Поэтому оптимизация всегда связана с поиском экстремума (максимума или минимума) некоторой функции, отражающей зависимость эффекта от искомой переменной. При поиске оптимального решения анализируемый процесс обычно представляют с помощью некоторой математической модели в виде системы уравнений и неравенств. Для ее решения необходимы специальные математические методы, которые и называются методами оптимизации. Они базируются на сочетании методов математического анализа (понятие функции, производной, системы уравнений и неравенств) и вычислительной математики (поиск решения систем уравнений и неравенств численным методом). В методических указаниях к контрольной работе приведен пример решения задачи оптимизации. Лекция 4. Методы линейного программирования Задачи линейного программирования (ЗЛП) – это поиск оптимального решения (max, min нахождение), когда целевая функция линейная. Линейная функция – это такая зависимость, когда функция прямо пропорциональна аргументу. Графиком такой функции является прямая линия. Вид функции , где a и b любые числа (коэффициенты). Здесь программирование – это планирование, формирование планов, разработка программы действий. ЗЛП – это задачи об оптимальном использовании ограниченных ресурсов. Например:  Задача о ресурсах;  Задача о смесях;  Транспортная задача. Модель любой ЗЛП включает:  Целевую функцию, значение которой надо найти (max, min)  Ограничения в виде системы линейных уравнений или неравенств.  Требование неотрицательности переменных. В общем виде модель ЗЛП записывается в виде:  Целевая функция: ( ) ( )  Ограничения: ( ) ( ) …………………………………………… ( )  Требование неотрицательности: ̅̅̅̅̅ - заданные постоянные величины. Надо найти оптимальное значение функции ( ) при заданных ограничениях. Систему ограничений называют функциональными ограничениями задачи. – называют допустимым решением (планом) задачи линейного программирования. План, при котором функция достигает своего максимального (минимального) значения, называется оптимальным. Далее приведем примеры некоторых типовых задач, решаемых при помощи методов линейного программирования. Такие задачи имеют реальное экономическое содержание. 4.1. Задача об оптимальном использовании ресурсов при производственном планировании. Общий смысл задач этого класса сводится к следующему. Для изготовления n видов продукции P1,…,Pn используется m видов сырья S1,…,Sm, запасы которого ограничены и составляют соответственно b1,…,bm единиц. Известно, что на производство единицы продукции Pj ̅̅̅̅̅) расходуется аij (аij – технологические коэффициенты) единиц ( ̅̅̅̅̅), а прибыль от реализации единицы продукции Pj ( ресурса Si ( ̅̅̅̅̅) составляет сj ( ̅̅̅̅̅) . Требуется определить план производства, при реализации которого прибыль предприятия была бы наибольшей. Прежде всего запишем условия задачи компактно в виде таблицы 1. Таблица 1 – Условие задачи о ресурсах Составим математическую модель задачи. ̅̅̅̅̅) планируемое к выпуску количество Обозначим через xj ( ̅̅̅̅̅) , а через (х1,…, xn) – прибыль предприятия от продукции Рj ( реализации всей продукции. Тогда планом производства будет вектор Х = (х1,…,хn), показывающий, какое количество продукции каждого вида будет произведено. Переменные х1,…,хn – управляемые переменные. Цель решения задачи (критерий оптимальности) – максимизировать прибыль: ( ) ̅̅̅̅̅) составляют: Суммарные затраты ресурса Si ( В силу ограниченности ресурса Si величиной bi получим систему ограничений: ̅̅̅̅̅) ( На переменные хj должно быть наложено условие неотрицательности ̅̅̅̅̅) , т.е. продукция Рj может либо выпускаться (xj > 0), либо не xj ≥ 0 ( выпускаться (xj = 0). Итак, математическая модель примет вид: ( ) , Далее приведем простой пример задачи такого класса. Пример решения задачи о ресурсах Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере €2, а каждый шахматный набор – в размере €4. На изготовление одной клюшки требуется 4 часа работы на участке А и 2 часа работы на участке В. Шахматный набор изготавливается за 6 часов на участке А, 6 часов на участке В и 1 часа на участке С. Доступная производственная мощность участка А составляет 120 нормочасов в день, участка В – 72 нормо-часа и участка С – 10 нормо-часов. Сколько клюшек и шахматных наборов должна выпускать компания, чтобы получать максимальную прибыль? Условие задач указанного класса часто представляют в табличной форме: Таблица 2 – Исходные данные задачи об использовании производственных ресурсов Производственные участки Затраты времени на единицу продукции, н-час Общий фонд рабочего времени клюшки наборы шахмат А 4 6 120 В 2 6 72 С - 1 10 Прибыль на единицу продукции, € 2 4 - По данному условию сформулируем задачу линейного программирования. Обозначим: – количество выпускаемых ежедневно хоккейных клюшек; – количество выпускаемых ежедневно шахматных наборов. Формулировка ЗЛП: ( ) Given otv := maximize ( ) otv = (-) ( )= Подчеркнем, что каждое равенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое – участку А, второе – участку В, третье – участку – С. Решаем задачу в Mathcad 14. Для этого нужно сопоставить задачу с таблицей 1 с данными из таблицы 2 и записать все исходные данные на листе Mathcad. 4.2. Задача о смесях (планирование состава продукции) Задача определения оптимального состава смеси возникает тогда, когда из имеющихся видов сырья путем их смешивания необходимо получить конечный продукт с заданными свойствами. При этом требуется, чтобы стоимость такой смеси была минимальной. К этой группе задач относятся, например, задачи получения смесей для разных марок бензина в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве, задача о выборе диеты, составление кормового рациона в животноводстве и др. Пусть имеется m видов сырья, запасы которого составляют соответственно d1,…, dm. Из этого сырья необходимо составить смесь, содержащую n веществ, определяющих технические характеристики смеси. ̅̅̅̅̅ ̅̅̅̅̅), определяющие количество j-го Известны величины aij ( ̅̅̅̅̅), а также вещества в единице i-го вида сырья, цена которого равна сi ( ̅̅̅̅̅) − наименьшее допустимое количество j-го вещества в смеси. bj ( Требуется получить смесь с заданными свойствами при наименьших затратах на исходные сырьевые материалы. Для составления математической модели запишем условия задачи в виде таблицы 3. Таблица 3 – Условие задачи о смесях ̅̅̅̅̅) количество сырья i-го вида, входящего в Обозначим через хi ( состав смеси. Цель задачи (целевая функция) – минимизировать суммарные затраты на сырье: ( ) Система ограничений включает в себя ограничения по техническим характеристикам: а также ограничения по объему неотрицательности переменных примут вид: сырья, которые с учетом ̅̅̅̅̅̅ Пример решения задачи о смесях На птицеферме употребляются два вида кормов – I и II. В единице массы корма I содержатся единица вещества А, единица вещества В и единица вещества С. В единице массы корма II содержатся 4 единицы вещества А, 2 единицы вещества В и не содержится вещество С. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее 4 единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II – 2 рубля. Составьте ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион. Представим условие задачи в таблице 4. Таблица 4 – Исходные данные задачи о смесях Вид смеси Вид вещества, ед. А В С корм I 1 1 1 корм II 4 2 Мин. кол-во вещ-в в смеси, ед. 1 4 Цена единицы массы корма, руб. 3 2 1 Сформулируем задачу линейного программирования. Обозначим: – количество корма I в дневном рационе птицы; – количество корма II в дневном рационе птицы. Формулировка ЗЛП: ( ) Given otv := minimize ( ) otv = ( ) ( )= Решаем задачу в Mathcad 14. Для этого нужно сопоставить задачу с таблицей 3 с данными из таблицы 4 и записать все исходные данные на листе Mathcad. 4.3. Транспортная задача Рассмотрим транспортную задачу, т. е. задачу, в которой речь идет о рациональной перевозке некоторого однородного продукта от производителей к потребителям. Пусть имеется m пунктов производства однородного продукта (добыча руды в карьерах, производство автобусов, кондитерских изделий, компьютеров и т.д.) и n пунктов потребления этого продукта. Мощности ̅̅̅̅̅) единиц однородного продукта, пунктов производства составляют аi ( ̅̅̅̅̅) единиц. а потребности каждого j-го пункта потребления равны bj ( Известны затраты cij на перевозку единицы продукта от i-го поставщика j-му потребителю. Составить такой план перевозок, при котором суммарные затраты на все перевозки были бы наименьшими. Пусть спрос и предложение совпадают, т.е. ∑ – суммарный запас грузов ∑ – суммарная потребность в грузах Такую транспортную задачу называют сбалансированной (закрытой). При этом предполагается, что вся продукция от поставщиков будет вывезена и спрос каждого из потребителей будет удовлетворен. В случае весь груз будет вывезен, но будет недопоставка груза, что экономически невыгодно потребителям. При , наоборот, будут удовлетворены все потребители, но часть груза остается на складах – экономически невыгодно поставщикам. Составим математическую модель задачи. Обозначим через xij − количество продукта, перевозимого из i-го пункта производства в j-й пункт потребления. Тогда матрица: … Заказы bj Запасы ai С11 x11 Сi1 С1j Сij Xij … … Сmj xm1 x1n Сin Xi1 Сm1 С1n x1j Xin … … Сmn xmj xmn Предположим, что транспортные затраты прямо пропорциональны количеству перевозимого продукта. Тогда суммарные затраты выразятся функцией цели: ( ) ̅̅̅̅̅ ̅̅̅̅̅), когда Надо найти план перевозок { } ( удовлетворяет система ограничений:  Груз, отправленный всем потребителям, каждым поставщиком, равен запасу груза поставщика где i=1, 2,…m  Количество груза, поставщиков, равно заказу. полученное каждым потребителем от где j=1,2,…n План перевозок, реализующий min F, называется оптимальным. Если задача является открытой, то:  при добавляем фиктивного поставщика с запасом  при добавляем фиктивного потребителя с заказом груза Тарифы полагаем равными 0. Из условия задачи следует, что все Математическая модель сбалансированной транспортной задачи имеет вид: ( ) ∑∑ при ограничениях: Пример решения транспортной задачи Дано: На складах А1, А2, А3 хранится =100, =200, = 120 единиц одного и того же запаса груза, соответственно. Требуется: Доставить его трем потребителям B1, B2, B3, заказы которых составляют =200, =110, = 80 единиц груза. Стоимость перевозки единицы груза с склада потребителю равны =4, =2, = 6, =7, =5, = 3, =1, =7, = 6 и указаны в транспортной таблице 5. Таблица 5 – Исходные данные для транспортной задачи Поставщики / Потребители B1 B2 B3 Запасы товаров на складе, А1 =4 =2 =6 100 А2 =7 =5 =3 200 А3 =1 =7 =6 120 Объем заказа, 200 110 ∑ ∑ 80 Требуется найти минимальную стоимость перевозки. Для этого вводим фиктивный пункт назначения B4, которому приписываем фиктивную заявку, равную избытку запасам над заявками ∑ ∑ . Стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения составляет . Введением фиктивного пункта назначения B4 с его заявкой мы сравняли баланс транспортной задачи и теперь ее можно решать как обычную транспортную задачу с правильным балансом (количество перевезенного груза обозначим символами ). Таблица 6 – Добавление фиктивного пункта назначения B1 B2 B3 B4 Запасы товаров на складе, А1 4* 2* 6* 0* 100 А2 7* 5* 3* 0* 200 А3 1* 7* 6* 0* 120 Объем заказа, 200 110 Решаем задачу в Mathcad 14. 80 30 Таблица 7 – Нахождение остатка B1 B2 B3 B4 А1 4*51,425 2*48,575 6*0 0*0 А2 7*28,575 5*61,425 3*80 0*30 А3 1*120 7*0 6*0 0*0 Объем заказа, ∑ ∑ При реализации оптимального нереализованный товар в размере 30 ед. ∑ Запасы товаров на складе, ∑ ∑ ( ) ∑ ∑ плана у поставщика останется Методические указания к контрольной работе. Варианты решения. Контрольная работа выполняется cредствами MS Word и Mathcad 14. Для каждой работы приведены 3 варианта. Студенту необходимо выбрать один из вариантов согласно последнему номеру зачетной книжки. 1 – номера зачетной книжки, закачиваются на 1, 3, 5, 0; 2 – номера зачетной книжки, закачиваются на 2, 6, 8; 3 – номера зачетной книжки, закачиваются на 4, 7, 9; Работы должны быть размещены в папку с названием Фамилия_группа и в заархивированном виде высланы на сайт заочного обучения. В качестве допуска к экзамену по дисциплине выступает выполнение всех 4-х работ. Экзамен будет проходить в виде тестирования по лекционному материалу. Работа № 1. Оптимизация работы станции технического обслуживания автомобилей Вариант 1. Задача Планируется модернизировать работу станции технического обслуживания автомобилей, имеющую n рабочих мест. Известно, что машины приходят с интенсивностью =2 авт./ч., интенсивность обслуживания составляет μ=1,4 авт./ч. Содержание каждого рабочего места обходится С2 = 1 усл.ед/ч. Каждый обслуженный автомобиль приносит доход С1 = 2 усл.ед/ч. Найти оптимальное число рабочих мест (n), при котором прибыль предприятия является максимальной. Расчеты проводить для n=1,2,3,4,5,6. Вариант 2. Задача Планируется модернизировать работу станции технического обслуживания автомобилей, имеющую n рабочих мест. Известно, что машины приходят с интенсивностью =3 авт./ч., интенсивность обслуживания составляет μ=2,1 авт./ч. Содержание каждого рабочего места обходится С2 = 2 усл.ед/ч. Каждый обслуженный автомобиль приносит доход С1 = 3 усл.ед/ч. Найти оптимальное число рабочих мест (n), при котором прибыль предприятия является максимальной. Расчеты проводить для n=1,2,3,4,5,6. Вариант 3. Задача Планируется модернизировать работу станции технического обслуживания автомобилей, имеющую n рабочих мест. Известно, что машины приходят с интенсивностью =2 авт./ч., интенсивность обслуживания составляет μ=1,8 авт./ч. Содержание каждого рабочего места обходится С2 = 5 усл.ед/ч. Каждый обслуженный автомобиль приносит доход С1 = 8 усл.ед/ч. Найти оптимальное число рабочих мест (n), при котором прибыль предприятия является максимальной. Расчеты проводить для n=1,2,3,4,5,6. Найти дополнительно: Расчеты необходимо проводить, начиная с количества рабочих мест равным шести (n=6). Далее, изменяя n, определить количество рабочих мест, которое позволяет получить максимальную прибыль. Ниже приведен пример решения задачи, который поможет решить задачу из выбранного варианта. Ход выполнения: 1. Открыть Mathcad 14. 2. Введите в рабочую область исходные данные (здесь и далее указывается пример выполнения задачи) 3. Введите в блок Given систему уравнений для моделирования технического обслуживания автомобилей с n=6 рабочими местами. 4. В блоке Find найдите вероятности P0, P1, P2, P3, P4, P5, P6 и, передав их в переменную otv, получите искомые значения. Здесь Pn = P6 – вероятность обслуживания при 6 рабочих мест. 5. Ниже найдите значения дополнительных переменных (выше указаны их названия): В итоге данных вычислений найдено, что при 6-ти рабочих местах (n=6) прибыль станции составила -0,786 усл.ед. (Пр= -0,786). 6. Далее проведите расчеты, уменьшая количество рабочих мест от n=5 до n=1, повторив пункты 2-5. Обратите внимание, что в исходных значениях записывать значения , μ, С1 и С2 не требуется, а количество вероятностей также должно уменьшаться согласно количеству n (Pn-1). Записывая пункт 3, будьте внимательны с системой уравнений. Прежде сверьтесь с теоретическими формулами. Построение зависимости прибыли от количества рабочих мест станции техобслуживания 1. Откройте новый лист в Mathcad 14 и сохраните как Зависимость.xmcd. 2. Задайте исходные данные и начальные значения коэффициентов многочлена. 3. В блоке Given запишите систему уравнений 4. В блоке Find найдите значения коэффициентов, передав их переменной otv 5. Рядом с otv перепишите полученные значения коэффициентов с соответствующие переменные для дальнейшего расчета: 6. Постройте зависимость прибыли от количества рабочих мест. 7. Сделайте вывод по полученному графику. 8. Сохраните работу в свою папку под именем Р1_Оптимизация. Работа № 2. Задачи об оптимальном использовании ресурсов Работа состоит из двух частей. В первой части необходимо составить таблицу согласно теоретическому материалу к данной задачи (таблица 1). Данная таблица может быть выполнена в MS Word и сохранена как Ресурсы.doc, либо можно заполнить ее на бумаге от руки и сохранить в формате рисунка Ресурсы.jpg. Во второй части работы решается задача в Mathcad 14. Файл должен иметь название Ресурсы.xmcd. Вариант 1 Задача о коврах Фабрика имеет в своем распоряжении определенное количество ресурсов: рабочую силу, деньги, сырье, оборудование, производственные площади и т. п. Допустим, например, ресурсы трех видов рабочая сила, сырье и оборудование имеются в количестве соответственно 80 чел/дней, 480 кг, 130 станко-часов. Фабрика может выпускать ковры четырех видов. На производство Ковра «Русская краса» требуется 7 чел/дней, 5 кг пряжи, 2 станко-часа. На Ковер «Утренняя роса» - 2 чел/дней, 8 кг пряжи, 4 станко-часов. На Ковер «Горный» - 2 чел/дней, 4 кг пряжи, 1 станко-час. На Ковер «Медальон» - 6 чел/дней, 3 кг пряжи, 8 станко-часов. Прибыль от реализации 1-го ковра составляет 3 т.р., 2-го ковра – 4 т.р., 3-го ковра – 3 т.р. и 4-го ковра – 1 т.р. Требуется определить, сколько ковров каждого вида необходимо произвести, чтобы обеспечить фабрике максимальную прибыль. Исходные данные занесите в таблицу и сделайте расчет в Mathcad. Вариант 2 Задача о планировании выпуска продукции пошивочному предприятию (Задача о костюмах). Намечается выпуск трех видов костюмов – мужских, женских и детских. Предприятие располагает следующими видами сырья: шерсть, лавсан, рабочая сила. На женский костюм требуется 1 м шерсти, 2 м лавсана и 2 человеко-день трудозатрат. На мужской костюм - 3,5 м шерсти, 1,5 м лавсана и 2 человеко-день трудозатрат. На детский костюм – 0,5 м шерсти, 1 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 20 денежных единиц, от мужского - 18 денежных единиц, от детского – 10 денежных единиц При этом следует иметь в виду, что необходимо сшить всего не менее 60 мужских костюмов. Исходные данные занесите в таблицу и сделайте расчет в Mathcad. Вариант 3 Задача о кабелях При производстве четырех видов кабеля выполняется пять групп технологических операций. Для данных операций доступная производственная мощность составит соответственно 7200 ч, 5600 ч, 11176 ч, 3600 ч и 4200 ч. На изготовление первого вида кабеля требуется 1,2 часа работы на операции «Волочение», 1 час работы на операции «Наложение изоляций», 6,4 часа на операции «Скручивание элементов в кабель», 3 часа работы на операции «Освинцовывание» и 2,1 часа на операции «Испытание и контроль». На изготовление второго вида кабеля требуется 1,8 часа работы на операции «Волочение», 0,4 часа работы на операции «Наложение изоляций», 5,6 часов на операции «Скручивание элементов в кабель» и 1,5 часа на операции «Испытание и контроль». На изготовление третьего вида кабеля требуется 1,6 часов работы на операции «Волочение», 0,8 часов работы на операции «Наложение изоляций», 6 часов на операции «Скручивание элементов в кабель» и 1,8 часов работы на операции «Освинцовывание» и 0,8 часа на операции «Испытание и контроль». На изготовление четвертого вида кабеля требуется 2,4 часа работы на операции «Волочение», 0,7 часов работы на операции «Наложение изоляций», 8 часов на операции «Скручивание элементов в кабель» и 2,4 часа работы на операции «Освинцовывание» и 3 часа на операции «Испытание и контроль». Прибыль от реализации 1 км каждого вида кабеля составит соответственно 1,2 руб., 0,8 руб., 0,95 руб., 1,3 руб. Определить такой план выпуска кабеля, при котором общая прибыль от реализации изготавливаемой продукции является максимальной. Исходные данные занесите в таблицу и сделайте расчет в Mathcad 14. Работа № 3. Задачи о смесях Работа состоит из двух частей. В первой части необходимо составить таблицу согласно теоретическому материалу к данной задачи (таблица 3). Данная таблица может быть выполнена в MS Word и сохранена как Смеси.doc, либо можно заполнить ее на бумаге от руки и сохранить в формате рисунка Смеси.jpg. Во второй части работы решается задача в Mathcad 14. Файл должен иметь название Смеси.xmcd. Вариант 1 Бройлерное хозяйство птицеводческой фермы насчитывает 20 000 цыплят, которые выращиваются до 8-недельного возраста и после соответствующей обработки поступают в продажу. Недельный расход корма в среднем (за 8 недель) составляет 500г = 0.5 кг. Для того чтобы цыплята достигли к 8-й неделе необходимого веса, кормовой рацион должен удовлетворять определѐнным требованиям по питательности. Этим требованиям могут соответствовать смеси различных видов кормов, или ингредиентов. В таблице приведены данные, характеризующие содержание (по весу) питательных веществ в каждом из ингредиентов и удельную стоимость каждого ингредиента. Смесь должна содержать:  не менее 0.8% кальция (от общего веса смеси)  не менее 22% белка (от общего веса смеси)  не более 5% клетчатки (от общего веса смеси) Требуется определить количество (в кг) каждого из трѐх ингредиентов, образующих смесь минимальной стоимости, при соблюдении требований к общему расходу кормовой смеси и еѐ питательности. Содержание питательных веществ (кг/ингредиента) Ингредиент Известняк Зерно Соевые бобы Кальций 0.38 0.001 0.002 Белок - 0.09 0.5 Клетчатка - 0.02 0.08 Стоимость (руб./кг) 0.04 0.15 0.40 До начала решения задачи определите дополнительно общий вес смеси (кг), еженедельно расходуемый на кормление всех цыплят. Исходные данные занесите в таблицу и сделайте расчет в Mathcad 14. Вариант 2 Для поддержания нормальной жизнедеятельности человеку ежедневно необходимо потреблять не менее 118 г белков, 56 г жиров, 500 г углеводов, 8 г минеральных солей. Количество питательных веществ, содержащихся в 1 кг каждого вида потребляемых продуктов, а также цена 1 кг каждого из этих продуктов приведена в таблице. Составить дневной рацион, содержащий не менее минимальной суточной нормы потребности человека в необходимых питательных веществах при минимальной общей стоимости потребляемых продуктов. Исходные данные занесите в таблицу и сделайте расчет в Mathcad 14. Вариант 3 Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее 26 ед. химического вещества А, 30 ед. – вещества В и 24 ед. – вещества С. Количество единиц химического вещества, содержащегося в 1 кг сырья каждого вида, цена 1 кг сырья каждого вида. Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость. Исходные данные занесите в таблицу MS Word и сделайте расчет в Mathcad 14. Работа № 4. Транспортная задача Вариант 1 У поставщика пластиковых окон на складах А1, А2, А3 хранится =150, =130, = 200 единиц запаса груза, соответственно. Требуется доставить его трем потребителям B1, B2, B3, заказы которых составляют =300, =100, = 50 штук пластиковых окон. Стоимость перевозки единицы груза с склада потребителю указаны в транспортной таблице: Поставщики / Потребители А1 А2 А3 B1 B2 B3 3 6 1 1 4 6 5 2 6 Решите транспортную задачу, следуя указаниям лекционного материала. Вариант 2 У поставщика шкафов на складах А1, А2, А3 хранится =180, =320, = 90 единиц запаса груза, соответственно. Требуется доставить его трем потребителям B1, B2, B3, заказы которых составляют =250, =190, = 120 штук шкафов. Стоимость перевозки единицы груза с склада потребителю указаны в транспортной таблице: Поставщики / Потребители А1 А2 А3 B1 B2 B3 5 7 2 4 5 3 7 3 8 Решите транспортную задачу, следуя указаниям лекционного материала. Вариант 3 У поставщика пиломатериалов на складах А1, А2, А3 хранится =190, =270, = 100 единиц запаса обрезных досок, соответственно. Требуется доставить их трем потребителям B1, B2, B3, заказы которых составляют =180, =170, = 140 единиц обрезных досок. Стоимость перевозки единицы груза с склада потребителю указаны в транспортной таблице: Поставщики B1 / Потребители А1 =4 А2 =7 А3 =1 Решите материала. транспортную B2 B3 =2 =5 =7 задачу, следуя =6 =3 =6 указаниям лекционного Приложение А Титульный лист контрольной работы Министерство образования и науки Российской Федерации ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРОМЫШЛЕННЫХ ТЕХНОЛОГИЙ И ДИЗАЙНА Институт информационных технологий и автоматизации Направление подготовки Профиль подготовки Выпускающая кафедра КОНТРОЛЬНАЯ РАБОТА № по дисциплине Моделирование и методы оптимизации Исполнитель - студент учебной группы (группа) (фамилия, имя, отчество, подпись) Преподаватель (ученая степень, звание, фамилия, имя, отчество, подпись) Санкт-Петербург 20___