- •Задача линейного программирования, формулировка, математическая модель, алгоритм решения симплексным методом и в Excel. Постоптимизационный анализ решения задачи.
- •Двойственность в линейном программировании. Симметричная пара двойственных задач, правила составления, их экономическое содержание.
- •Двойственные оценки ресурсов и технологий. Математическая модель задачи определения двойственных оценок, их экономическое содержание.
- •Несимметричная пара двойственных задач, правила составления, её особенности.
- •Первая основная теорема двойственности и её экономическая интерпретация.
- •Вторая основная теорема двойственности и её экономическая интерпретация.
- •Третья основная теорема двойственности и её экономическая интерпретация.
- •Задача оптимального пополнения недостающих ресурсов на предприятии.
- •Применение метода динамического программирования при принятии решений об оптимальном распределений инвестиций.
- •Оптимизация плана распределения ресурсов между производственными подразделениями с помощью двойственных оценок при двухуровневой системе управления.
- •Задача целочисленного программирования. Решение методом Гомори, методом ветвей и границ, а также в Excel.
- •Многокритериальные задачи линейного программирования, решение методом последовательных уступок.
- •Векторы, действия над ними, линейная зависимость и независимость векторов, их линейная комбинация, базис.
- •Матрицы, их классификация, алгебра матриц.
- •Определители матриц их свойства и методы вычисления.
- •Метод динамического программирования, принцип оптимальности, параметр состояния, функция состояния, рекуррентные динамические соотношения.
- •Принятие решений в условиях полной неопределённости, матрицы последствий и рисков.
- •Принятие решений в условиях полной неопределённости, правило Вальда.
- •Принятие решений в условиях полной неопределённости, правило Сэвиджа.
- •Принятие решений в условиях полной неопределённости, правило Гурвица.
- •Принятие решений в условиях частичной неопределённости, матрицы последствий и рисков.
- •Принятие решений с помощью дерева решений.
- •Риск как среднее квадратическое отклонение. Бейесовский подход к принятию решений, методы снижения рисков.
- •Матричные игры, основные понятия и определения, решение игры в чистых стратегиях.
- •Теорема об активных стратегиях, решение матричных игр в смешанных стратегиях.
- •Упрощение и геометрическая интерпретация решения матричных игр.
- •Сведение решения игры к решению пары взаимно двойственных задач линейного программирования.
- •Некооперативные биматричные игры, основные понятия и определения. Анализ биматричной игры в некооперативном варианте.
- •Кооперативные биматричные игры, оптимальность по Парето, переговорное множество, арбитражные схемы Нэша, функция Нэша.
- •Экспертные методы принятия решений.
Вопросы для подготовки к экзамену
по дисциплине “Системный анализ и принятие решений”
для студентов 3 курса, д/о, 2011/2012уч. год
Задача линейного программирования, формулировка, математическая модель, алгоритм решения симплексным методом и в Excel. Постоптимизационный анализ решения задачи.
Исходные данные:
Количество видов изделия n;
Количество видов ресурсов m;
Нормы потребления ресурсов на каждый вид изделия:
Объем ресурсов каждого вида:
Удельная прибыль при возможном выпуске четырех видов изделий с использованием трех видов продукции: вектор С:
Формулировка задачи:
На предприятии предполагается организовать выпуск четырех видов изделий в количествах соответственно:
Фабрика располагает тремя видами ресурсов, количество которых определяется вектором В. Известны также нормы расходов ресурсов (матрица А) и прибыль от реализации одного изделия (матрица С).
Требуется составить такой план выпуска изделий, при котором предприятие уложится в имеющиеся ресурсы, а суммарная прибыль будет максимальной.
Математическая модель задачи
Основные элементы модели оптимизационной задачи:
Критерий оптимальности (целевая функция);
Система ограничений;
Неотрицательность переменных.
Примем следующие обозначения:
i - номер отдельного вида ресурса: i = (1, 2, … , m);
j – номер вида изделия: j = (1, 2, … , n);
– норма ресурсов на изготовление j-го изделия с использованием i-го ресурса;
– объем i-го ресурса;
– объем прибыли при производстве j-го изделия;
- количество планируемых единиц j-го изделия;
( - искомый план производства.
Найти производственную программу максимизирующую целевую функцию прибыли:
(1.1.)
при ограничениях по ресурсам:
(1.2.)
и при условии неотрицательности переменных:
(1.3.)
Решение
Для решения задачи линейного программирования используется симплексный метод, для которого учитываются следующие условия:
Задача должна быть классической, т.е. на минимум (максимум);
Система ограничений должна быть в виде равенств;
В каждом уравнении должна быть базисная переменная.
=
Алгоритм (на примере):
Для решения систему ограничений (1.1.), состоящую из неравенств, следует преобразовать в равенства при помощи дополнительных неотрицательных неизвестных , т.е. заменить ее системой алгебраических уравнений. В целевую функцию также добавляются дополнительные переменные с коэффициентами 0:
(1.3.)
(1.4.)
где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Для них также существует условие неотрицательности:
(1.5.)
Дополнительные переменные с коэффициентом +1 являются базисными.
Заполняется начальная симплексная таблица
Таблица 1.1. Исходная симплексная таблица
|
Б |
Н |
|
|
|
|
|
|
|
|
|
0 |
|
168,00 |
3,00 |
2,00 |
0,00 |
3,00 |
1,00 |
0,00 |
0,00 |
84,00 |
0,67 |
0 |
|
60,00 |
0,00 |
1,00 |
4,00 |
2,00 |
0,00 |
1,00 |
0,00 |
60,00 |
0,33 |
0 |
|
112,00 |
1,00 |
3,00 |
5,00 |
0,00 |
0,00 |
0,00 |
1,00 |
37,33 |
--- |
|
|
0,00 |
-18,00 |
-19,00 |
-8,00 |
-5,00 |
0,00 |
0,00 |
0,00 |
--- |
-6,33 |
– коэффициент целевой функции при базисных переменных;
Б – базисные переменные;
Н – значение базисных переменных;
Двойственные оценки рассчитываются по формуле
Выбирается разрешающий столбец по максимальной по величине двойственной оценке (второй столбец)
Выбирается разрешающая строка с помощью коэффициента – отношения элементов столбца Н и соответствующих элементов ключевого столбца.
Производится перерасчет таблицы по методу Жордано-Гаусса: вычисляется столбец β делением ключевого разрешающего на ключевой элемент, затем из каждой строки вычитается разрешающая строка, умноженная на соответствующий коэффициент β. Сама разрешающая строка делится на ключевой элемент.
Заполняется новая симплексная таблица (п.2)
Признак окончания расчетов – значения всех двойственных оценок больше или равны 0 (в задаче на максимум).
Критерий оптимальности в задаче на максимизацию прибыли – отсутствие отрицательных двойственных оценок.
Двойственные оценки фактических переменных ( ) показывают, насколько уменьшится значение целевой функции (прибыль), если ввести в план одно изделие соответствующего вида.
Двойственные оценки дополнительных переменных ( ) показывает, насколько уменьшится целевая функция (прибыль) при уменьшении величины соответствующего ресурса на единицу (или увеличится при его увеличении).
Решение задачи с помощью программы Excel (на примере)
Предприятие выпускает четыре вида изделий ( ) . Для их изготовления используется три вида ресурсов ( ). Известны нормы расходов ресурсов на единицу продукции каждого вида, цена за единицу продукции и запасы ресурсов.
Для расчета следует организовать данные следующим образом: в первой таблице указать виды изделия, цены за единицу, план выпуска, в отдельной ячейке ввести формулу расчета значения целевой функции; во второй таблице указать ресурсы, нормы расходов, формулы с указанием фактических расходов ресурсов и их запасов.
.
С помощью функции «Поиск решения» производится решение задачи симплекс-методом. Для этого в окне поиска указать: целевую ячейку (целевая функция), условие максимизации целевой функции, изменяемые ячейки (план выпуска).
Ввести ограничения, указанные в условии задачи: суммарные расходы ресурсов не должны превышать заданного объема. Также следует указать условие неотрицательности переменных.
Выполнить!
Получен оптимальный план производства
Постиптимизационный анализ:
Из отчетов по пределам и устойчивости можно сделать следующие выводы:
Какие ресурсы использованы полностью, а для каких имеется резерв;
При каких изменениях цен оптимальный план выпуска будет оставаться неизменным;
При каких изменениях объемов ресурсов структура оптимального плана будет неизменной;
Теневые цены показывают, на сколько изменится прибыль при увеличении объема ресурса.