Практическое занятие 2 «Оптимизационные модели»
Задачи: научить студентов строить оптимизационные модели. Используемое программное обеспечение: операционная система Windows, Ms Excel, надстройка Поиск решения. Время выполнения работы: 6 часов аудиторных занятий.
Формулировка любой оптимизационной задачи требует использования некоторой базовой системы понятий. Любая переменная (изменяемая ячейка в электронной таблице) обычно интерпретируется как некоторый ресурс (например, ресурс времени, материала, продукта, валюты), выраженный в количественном измерении (минуты, тонны, штуки, рубли). Задача оптимизации состоит в том, чтобы подобрать такие значения переменных, при которых целевая функция (целевая ячейка таблицы) принимает максимальное, минимальное или заданное значение (оптимальное значение), при этом найденные значения переменных в совокупности составляют оптимальное решение задачи. В классическом исследовании операций задачи математического программирования делятся на несколько различных типов в зависимости от вида целевой функции и ограничений. К основным типам относятся задачи линейного и нелинейного программирования. Для первого типа характерна целевая функция, линейно зависящая от переменных (ресурсов) исследуемой системы, и такие же линейные ограничения. Если же целевая функция или хотя бы одно из ограничений нелинейно зависит от переменной (хотя бы одной), задача относится к типу нелинейного программирования. В качестве примеров нелинейностей можно привести зависимости видов Если оптимизационная задача должна решаться в целых числах, когда хотя бы одна из переменных модели должна измеряться в штуках, говорят о целочисленном программировании. Наконец, если хотя бы одна из переменных может принимать только одно из двух значений (0 или 1), говорят о булевском программировании.
Ниже мы рассмотрим задачи линейного программирования. Общая задача линейной оптимизации заключается в нахождении максимума (минимума) линейной целевой функции f(x):
(1)
при ограничениях
(5)
Набор чисел Первым этапом формализации модели линейного программирования (ЛП) должно стать выявление ограничений на переменные решения. Ограничения сужают множество допустимых значений. Примерами ограничений могут быть: – инвестиции в проект ограничены суммой капитала, имеющегося в распоряжении; – решения директора завода ограничены производственной мощностью завода и имеющимися ресурсами; – план выпуска изделий ограничен имеющимися ресурсами материалов и спросом на данный вид продукции. Целевая функция или показатель эффективности, который можно минимизировать (затраты или время) или максимизировать (прибыль, эффективность, производительность), существует в каждой модели линейного программирования. При реализации задачи ЛП средствами Excel можно использовать следующие рекомендации: – каждая переменная решения располагается в отдельной ячейке, ячейки группируются по строкам или столбцам; каждому ограничению отводится отдельная строка или столбец (чаще всего переменные решения располагаются в столбцах, а ограничения – в строках); – коэффициенты целевой функции хранятся в отдельной строке, а формула для вычислений целевой функции находится в соседней ячейке. Надстройка Excel Поиск решения позволяет оптимизировать как линейные, так и нелинейные модели, но необходимо помнить, что при линейных моделях все формулы, содержащие переменные, должны быть линейными. Рассмотрим несколько примеров задач ЛП.
Задача составления скользящих графиков Такие графики обычно связаны с расписаниями многосменной работы предприятия в условиях нестационарного спроса на товары или услуги, связанные с деятельностью этого предприятия. Задача состоит в том, чтобы организовать расписание обслуживания клиентов таким образом, чтобы издержки от неравномерности спроса были бы минимальны. В таблице 2 приведено число продавцов, необходимое для удовлетворения покупательского спроса в зале магазина. Требуется так организовать расписание работы продавцов, чтобы их общее количество (то есть расходы на оплату их труда) было минимальным. Пусть продавцы в магазине работают по 8 часов. В соответствии с данными задачи, число продавцов меняется через 4 часа. Если предположить, что в первую смену работает x1 продавцов, во вторую — x2 и т. д., то график работы продавцов представим на рисунке 3. Таблица 2 Требуемое количество продавцов
Рис. 3. График работы продавцов Жирные линии – это смены, они начинаются через 4 часа и продолжаются 8 часов. Смены перекрываются, т. е., с 4 до 8 часов в зале присутствуют (x1 + x2) продавцов, с 8 до 12 часов — (x2 + xЗ) продавцов, а с 0 часов до 4 работают (x1 + x6) продавцов. Этот «скользящий» график и образует расписание смен. В качестве ограничений при этом будут выступать условия: x1+x6 >= 2; x1+x2 >= 2; x2+x3 >= 5; x3+x4 >= 7; x4+x5 >= 7; x5+x6 >= 4. Кроме того,
Рис. 4. Модель задачи составления скользящих графиков Задача оптимизации инвестиций Основная цель решения этого класса задач — найти оптимальное распределение финансовых средств, доставляющее максимальную прибыль по истечении срока действия инвестиционного проекта.
Денежные средства могут быть использованы для финансирования двух проектов. Проект А гарантирует получение прибыли в размере 70 центов на вложенный доллар через год. Проект В гарантирует получение прибыли в размере 2 долларов на каждый инвестированный доллар, но через два года. При финансировании проекта В период инвестиций должен быть кратным двум годам. Как следует распорядиться капиталом в 100 000 долларов, чтобы максимизировать суммарную величину прибыли, которую можно получить через три года после начала инвестиций? Содержимое изменяемых ячеек: xа, Ya — вложения в проект A; Xb, Yb — вложения в проект В. Возможные инвестиции могут быть проиллюстрированы схемой, приведенной на рисунке 5. Из схемы следует, что в исследуемой системе существуют только два возможных срока вложений — начало первого года и начало второго года. Суммы вложений в эти сроки определяют содержимое изменяемых ячеек. «Точка вложений» в начале третьего года одна, в нее вкладываются все доходы от предыдущих вложений.
Рис. 5. Схема инвестиций в проекты А и В Ограничения: xа + xЬ = 100 000; ya + yb = (1 + 0,7)*xа. Целевая функция: z= ya*(l + 0,7)*2 + yb*(l + 2) + xb*(l + 2)*(1 + 0,7)® max.
Решение задачи представлено на рисунке 6.
Рис. 6. Модель задачи об инвестициях Задача логического выбора Этот класс задач связан с выбором конкретных вариантов организации системы с учетом ресурсных ограничений. Как правило, в них используются изменяемые ячейки, которые могут хранить одно из двух значений: 1 или 0. Выбор одного из двух вариантов организации исследуемой системы (1, 2) может определяться двумя булевскими переменными (хI, х2). Условие выбора только одного из двух вариантов эквивалентно логическому ограничению: хI+х2= 1. Такое ограничение моделирует условие взаимоисключения. Условие выбора хотя бы одного из двух вариантов эквивалентно логическому ограничению хI+х2 >= 1. Если вариант 2 может быть принят только при принятии
Рассматриваются пять проектов, которые могут быть осуществлены в течение трех лет. Ожидаемые величины прибыли от реализации проектов и распределение необходимых капиталовложений по годам (в тыс. долл.) приведены в таблице 3. Требуется выбрать совокупность проектов, которой соответствует максимум общей прибыли. Таблица 3 Исходные данные задачи выбора проектов
Добавим к таблице исходных данных столбец изменяемых ячеек. Обозначим содержимое этих ячеек как х i, где i определяет номер проекта, a хi – решение: вкладывать (хi =1) или нет (хi = 0) средства в i-ый проект (рис. 7). Ограничениями задачи будут: – По объему капиталовложений в первый год: 5* xI + 4*x2 +3*xЗ + 7*x4 + 8*x5 <= 25; во второй год: 1* xI + 7*x2 +9*xЗ + 4*x4 + 6*x5 <= 25; в третий год: 8* xI + 10*x2 +2*xЗ + 10*x4 + 1*x5 <= 25. – «Естественные» ограничения: – Целевая функция: Z= 20*x 1 + 40*x 2 + 20*x З + 15*x 4 + 30*x 5 ® max.
Рис. 7. Модель задачи логического выбора Задачи для самостоятельной работы
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|