Методы линейного программирования

Пример

Дана система в виде:

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

, ;

запас устойчивости .

Решение:

1. ; ; ; ;
   
   ;
   ; ;
   .

1. ;
   ;
   ;
   ; ; ; ;
   ; ;
   
   Характеристический многочлен (метод Гурвица)
   ;
   ;
   ;
   ;
   ;
   ;

1. ; ;

1. 
   ;
   ; ; ; ;
   При условии если матрица динамики находится в форме Калмана, тогда
   ;
   ;

1. Если исходная система находится в форме Калмана, то матрица имеет вид
   ;
   – единичная матрица, если в форме Калмана
   ;
   .

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

(широко используется для разработки ERP-систем Enterprise Research Planning).

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

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

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

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

Качество или эффективность операции – это свойство характеризующее степень приспособленности операции к выполнению поставленной задачи (требования).

Показатель качества операции – количественная мера качества операции.

Основные этапы исследования операции:

1. Постановка задачи;
2. Построение модели операции;
3. Поиск решения;
4. Корректировка модели;
5. Реализация.

Модели операции

Модель – приближенное описание операции (один и тот же объект может иметь много различных моделей).

;

; - вектор управляемых переменных

- вектор неуправляемых переменных

Требования к модели:

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

Типы моделей:

1. Описательная модель

• сценарии;
• таблицы;
• анкеты.

1. Графические модели
• блок-схемы;
• графы состояний;
• сети;
• деревья.

1. Физические модели
• аналоговые модели;
• масштабные модели.

1. Математические модели
• аналитические;
• имитационные модели.

Этапы построение моделей:

1. Определение множества переменных, которые существенно влияют на показатели эффективности операции;
2. Выбор структуры, вида модели
   Например,
   (функционал зависит от ряда функций)
   – обобщенный критерий.
3. Оценка параметров коэффициентов ;
4. Поиск решений.

Поиск решений

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

.

Варианты задачи поиска решений

1. Известны значения переменных , , которые заданы следующим образом:
   ;
2. , линейны по , тогда методами решения этой задачи являются методы линейного программирования;
3. Если хотя бы одна из них не линейна по , то применяют методы нелинейного программирования;
4. Если хотя бы одна из переменных , где дискретна, то используют методы дискретного целочисленного программирования;
5. Если переменные случайные величины и известны законы их распределения, то модель называется вероятностной и вместо детерминированной величины используют некоторые характеристики распределения случайной величины;
6. Если полностью неизвестная величина, то тогда методом поиска решения называются методы принятия решений в условиях неопределенности;
7. Если является результатом активного действия противника, то поиск решения осуществляется на основе математического аппарата теории игр.

Корректировка модели

1. Анализ модели с точки зрения разумности и приемлемости полученных решений;
2. Анализ чувствительности моделей к малым вариациям исходных данных. (малые изменения исходных данных не должны резко менять решение).

Пример (продавец газет)

Пусть

– число газет, взятых продавцом;

– прибыль за проданную газету;
– убытки за непроданную газету;

– спрос на газеты;

– плотность распределения спроса;

с – средняя прибыль, показатель эффективности продажи газет.

Составить математическую модель.

Дано:

, ; - количество продавцов

, ; - спрос (неуправляемая переменная, случайная величина)

;

. - (мат. ожидание)

Решение:

Два случая:

1. все газеты продаются ;

2. газеты не продаются .

;

.