кандидат технических наук, доцент Грекул Владимир Иванович Учебный курс Теория информационных систем Лекция 6

Примеры оптимизационных задач Выбор поставщиков товара Из множества поставщиков, товар каждого из которых: может принести прибыль Р1, Р2… характеризуется индексом риска R1, R2… выбрать таких, товары которых обеспечат максимальную прибыль при ограниченном суммарном риске.

Оптимизация плана выпуска продукции Определить оптимальные количества Х 1, Х 2,… выпуска различных изделий, каждое из которых: может принести прибыль P1, P2… требует разного количества ресурсов (финансовых, материальных и пр.) С1-1, С1-2…, С2-1, С2-2… План должен обеспечить максимальную прибыль при условии использования ограниченных объемов ресурсов R1, R2… Требуемое количество 1-го ресурса для второго изделия

Оптимизация транспортных расходов Из множества доступных маршрутов доставки М1-1, М1-2, М1-3, М2-1, М2-2 …, каждый из которых характеризуется определенной стоимостью перевозки единицы груза C1-1, C1-2, … C2-1, C2-2… выбрать такие, которые обеспечат: Минимальные суммарные затраты. Доставку нужного количества груза на каждый объект. Вывоз всех запасов со всех складов. Маршрут доставки груза с первого склада на второй объект

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

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

Математическое программирование - область исследования операций, которая занимается оптимизацией (нахождением минимума или максимума) целевой функции при заданных ограничениях. Линейное программирование используется для решения задач, в которых целевая функция и ограничения представляют собой линейные уравнения или неравенства относительно переменных решения т.е. выражения типа С 1 *Х 1 + С 2 *Х 2 +…+ С n *X n Постоянные коэффициенты Переменные решения

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

Условия задачи Для организации выпуска двух видов продукции (А и В) выделены следующие ресурсы: Фонд заработной платы – р. Фонд закупки материалов – р. Имеющиеся на складе запасы стекла – 240 м 2. Затраты ресурсов на выпуск единицы продукции: Сколько следует выпустить изделий типа А и В? Какова возможная максимальная прибыль? Прибыль от одного изделия Материалы 21 Стекло 100 Зарплата Изделие ВИзделие А Ресурсы

Таблица элементов модели 100 * Х * Х 2 =< по фонду заработной платы 350 * Х * Х 2 =< по фонду закупки материалов 1 * Х * Х 2 =< 240 по запасу стекла на складе Х 1, Х 2 >= 0 количество изделий не может быть отрицательным Ограничения Р=200* Х 1+100* Х 2 Суммарная прибыль от выпуска продукции должна быть максимальной Х 1 – количество изделий А Х 2 – количество изделий В Целевая функцияПеременные решения

Х2 Х Свойства линейных функций 4 * Х * Х 2 = 20 Х2=0 4*Х1=20 Х1=5 Х1=0 5*Х2=20 Х2=4 4*2+5*1=9 20 При любых значениях Х 1 и Х 2 из этой области выполняется неравенство 4*Х 1 +5*Х 2 > * Х * Х2 =< Ограничение по фонду расходов на материалы

Анализ решения Цель анализа – оценить влияние изменения условий деятельности (параметров модели) на функционирование системы: - колебаний цен на продукцию; - изменения располагаемых запасов ресурсов и т.п. Ограничения по фондам Материалов Стекла Зарплаты 350*Х1+100*Х2= *Х1+100*Х2= *Х1+2*Х2=240 Область допустимых планов – множество точек (Х1,Х2), для которых одновременно выполняются все ограничения

Исследование решения Р=МАКС Р= Р= Суммарная прибыль Р=200*Х1+100*Х2 Существует множество планов производства, которые принесут одинаковую прибыль Р. Они отображаются прямой. Семейство параллельных прямых отражает изменения планов при разных значениях Р. Чем больше Р, тем дальше прямая смещена вправо. Максимальную прибыль обеспечит план, соответствующий прямой, которая проходит через правую граничную точку области допустимых планов.

Область устойчивости решения С А =250 С А =200 С А =150 Р=250*Х1+100*Х2 = Р=200*Х1+100*Х2 = Р=150*Х1+100*Х2 = При изменении весовых коэффициентов целевой функции в некоторых пределах оптимальный план остается неизменным. Максимальная прибыль изменяется относительно плавно. Оптимальный план Х1=80 Х2=70

Смена оптимального плана Х1 С А =90 Р=90*Х1+100*Х2 = (старые значения ) При выходе за пределы устойчивости происходит смена оптимального плана и резкое изменение максимальной прибыли. Оптимальный план Х1=60 Х2=90 (старые значения Х1=80, Х2=70)

Разработка и внедрение ИС – Классификация информационных систем – Методология проектирования ИС – Основные подходы к разработке моделей – Методология внедрения ИС

ПО ДАННЫМ Standish Group Таким образом, более 70% проектов завершаются с отклонением от первоначального бюджета, сроков, функциональности или не реализуются вообще. Только в США стоимость нереализованных проектов составляет около 75 млрд. долларов. Бюджет 214% Сроки 202% Функциональность 74% Отклонения от планов Зарубежная статистика по IT проектам Данные 1998 года

1. Классификация информационных систем Информационные системы Фактографические Автоматизиро ванные Автоматичес кие По степени автоматизации Интегрирован- ные Организационного управления САПР Управления ТП По сфере применения Информационно- поисковые По характеру обработки данных Информационно- решающие Управляющие Советующие По уровню управления Стратегически е Функциональ ные Операционные Документальные Ручные По типу данных

2. Методология проектирования ИС Цель - регламентировать процесс проектирования ИС и обеспечить: отвечающих целям и задачам организации создание корпоративных ИС, отвечающих целям и задачам организации, а также предъявляемым требованиям по автоматизации деловых процессов заказчика; срокибюджета гарантировать создание системы с заданным качеством в заданные сроки и в рамках установленного бюджета проекта; сопровождения, модификации и наращивания поддерживать удобную дисциплину сопровождения, модификации и наращивания системы; преемственность обеспечивать преемственность разработки, т.е. использование в разрабатываемой ИС существующей информационной инфраструктуры организации (задела в области информационных технологий).