- •Математические методы системного анализа и теория принятия решений Методическое пособие
- •1. Теория принятия решений 4
- •2. Линейное программирование 9
- •3. Нелинейное программирование 42
- •4. Игровые методы обоснования решений 51
- •5. Задачи распознавания образов 62
- •Предисловие
- •1. Теория принятия решений
- •1.1. Задачи, связанные с принятием решений Проблема оптимальности.
- •Основные понятия и принципы исследования операций.
- •Примеры задач исследования операций.
- •1.2. Математические модели операций Искусство моделирования.
- •1.3. Разновидности задач исследования операций и подходов к их решению Прямые и обратные задачи исследования операций.
- •Пример выбора решения при определенности: линейное программирование.
- •Проблема выбора решений в условиях неопределенности.
- •Выбор решения по многим критериям.
- •«Системный подход».
- •2. Линейное программирование
- •2.1. Краткое представление о математическом программировании Предмет математического программирования.
- •Краткая классификация методов математического программирования.
- •2.2. Примеры экономических задач линейного программирования Понятие линейного программирования.
- •Задача о наилучшем использовании ресурсов.
- •Задача о выборе оптимальных технологий.
- •Задача о смесях.
- •Задача о раскрое материалов.
- •Транспортная задача.
- •2.3. Линейные векторные пространства Основные понятия линейного векторного пространства.
- •Решение систем линейных уравнений методом Гаусса.
- •Реализация метода исключения неизвестных в среде Excel.
- •Различные схемы реализации метода Гаусса.
- •Опорные решения системы линейных уравнений.
- •2.4. Формы записи задачи линейного программирования Основные виды записи злп.
- •Каноническая форма представления задачи линейного программирования.
- •Переход к канонической форме.
- •2.5. Геометрическая интерпретация задачи линейного программирования Определение выпуклой области.
- •Геометрическая интерпретация.
- •2.6. Свойства решений задачи линейного программирования Свойства основной задачи линейного программирования.
- •Графический метод решения задачи линейного программирования.
- •2.7. Симплексный метод Идея симплекс-метода.
- •Теоретические обоснования симплекс-метода.
- •Переход к нехудшему опорному плану.
- •Зацикливание.
- •Алгоритм симплекс-метода.
- •2.8. Двойственность в линейном программировании Прямая и двойственная задача.
- •Связь между решениями прямой и двойственной задач.
- •Геометрическая интерпретация двойственных задач.
- •2.9. Метод искусственного базиса Идея и реализация метода искусственного базиса.
- •3. Нелинейное программирование
- •3.1. Общая задача нелинейного программирования Постановка задачи.
- •Примеры задач нелинейного программирования (экономические).
- •Геометрическая интерпретация задачи нелинейного программирования.
- •3.2. Выпуклое программирование Постановка задачи выпуклого программирования.
- •3.3. Классические методы оптимизации Метод прямого перебора.
- •Классический метод дифференциальных исчислений.
- •3.4. Метод множителей лагранжа
- •3.5. Градиентные методы решения задач нелинейного программирования Общая идея методов.
- •Метод Франка-Вулфа.
- •Метод штрафных функций.
- •4. Игровые методы обоснования решений
- •4.1. Предмет и задачи теории игр Основные понятия.
- •Классификация выборов решений.
- •Антагонистические матричные игры.
- •Чистые и смешанные стратегии и их свойства.
- •4.2. Методы решения конечных игр Упрощение матричной игры.
- •Решение матричной игры размерностью 22.
- •Графическое решение матричной игры.
- •Сведение задач теории игр к задачам линейного программирования.
- •4.3. Задачи теории статистических решений Игры с природой.
- •Критерии принятия решений.
- •5. Задачи распознавания образов
- •5.1. Общая постановка задачи распознавания образов и их классификация Проблема распознавания.
- •Обсуждение задачи опознавания.
- •Язык распознавания образов.
- •Априорные предположения — это записанные специальным образом, накопленные знания специалистов.
- •Общая постановка задачи.
- •Геометрическая интерпретация задачи распознавания.
- •Классификация задач распознавания.
- •5.2. Подготовка и анализ исходных данных Общая схема решения задачи.
- •Общая схема постановки и решения задачи Анализ данных с целью выбора постановки и метода решения
- •5.3. Методы опознавания образов Основные этапы процесса опознавания образов.
- •Методы создания системы признаков.
- •Признаковое пространство.
- •Сокращение размерности исходного описания.
- •Методы построения решающего правила.
- •5.4. Меры и метрики Понятие о сходстве.
- •Меры сходства и метрики.
- •Примеры функций мер сходства.
- •5.5. Детерминированно-статистический подход к познаванию образов Основные этапы детерминированно-статистического подхода.
- •Получение исходного описания.
- •Создание системы признаков.
- •Сокращение размерности исходного описания.
- •Нахождение решающего правила (метод эталонов).
- •Коррекция решающего правила.
- •5.6. Детерминированный метод построения решающего правила (метод эталонов) Идея метода эталонов.
- •Минимизация числа эталонов.
- •Габаритные эталоны.
- •Применение метода эталонов к частично пересекающимся образам.
- •Дополнительная минимизация числа признаков.
- •Квадратичный дискриминантный анализ.
- •Распознавание с отказами.
- •5.8. Алгоритм голотип-1 Назначение
- •Постановка задачи
- •Метод решения задачи.
- •Условия применимости.
- •Условия применимости.
- •5.10. Алгоритм направление опробования Назначение
- •Постановка задачи.
- •Метод решения задачи.
- •Условия применимости.
- •Транспортная задача Математическая постановка.
- •Постановка задачи.
- •Теоретическое введение.
- •Методы нахождения опорного плана транспортной задачи.
- •Определение оптимального плана транспортной задачи.
- •Заключение.
- •Целочисленное программирование Постановки задач, приводящие к требованию целочисленности.
- •Постановка задачи.
- •Методы отсечения.
- •Алгоритм Гомори.
- •Первый алгоритм р. Гомори решения полностью целочисленных задач.
- •Приближенные методы.
- •Заключение.
- •Параметрическое программирование Введение.
- •Формулировка задачи.
- •Теоретическая часть.
- •Общая постановка задачи.
- •Решение задачи.
- •Геометрическая интерпретация задачи.
- •Общая постановка задачи.
- •Решение задачи.
- •Геометрическая интерпретация задачи
- •Постановка задачи.
- •Решение.
- •Геометрическое решение.
- •Решение задачи симплекс-методом.
- •Результат.
- •Некооперативные игры n лиц с ненулевой суммой Введение.
- •Теоретическая часть.
- •Постановка и решение задачи.
- •Заключение.
- •Cписок литературы
Алгоритм Гомори.
В 1954 г. Дж. Данциг высказал идею о том, что построение выпуклой оболочки целочисленной области для задачи (Gц, Z) можно осуществлять поэтапно и решать получаемые при этом задачи. Однако при этом возникли вопросы как строить ограничения новой задачи и как обеспечить конечность процесса.
Ответ на эти вопросы был впервые получен Р. Гомори, который предложил алгоритмы решения целочисленных и частично целочисленных задач.
Алгоритм Р. Гомори состоит из следующих процедур:
-
Решается (G, Z)-задача, соответствующая исходной (Gц, Z)-задаче.
-
Полученное оптимальное решение задачи, если оно существует, проверяется на целочисленность. Если условие целочисленности выполняется по всем переменным, то оптимальное решение (G, Z)-задачи есть оптимальное решение (Gц, Z)-задачи. Если условие целочисленности не выполняется хотя бы по одной координате, то переходят к третьему этапу. Если (G, Z)-задача оказывается неразрешимой, то (Gц, Z)-задача тоже решения не имеет.
-
Строится дополнительное ограничение, обладающее тем свойством, что с его помощью отсекается часть области, в которой содержится оптимальное решение (G, Z)-задачи и не содержится ни одного допустимого решения (Gц, Z)-задачи. Процесс построения дополнительных ограничений и решения получаемых при этом (G, Z)-задач продолжается до тех пор, пока не получим целочисленного решения или не убедимся в неразрешимости задачи.
При этом свойства, которыми должно обладать каждое из дополнительных ограничений при переходе от одной задачи к другой следующие:
-
дополнительное ограничение должно быть линейным, чтобы оставаться в области применимости аппарата линейного программирования;
-
дополнительное ограничение должно отсекать часть области, в которой не содержится допустимых решений целочисленной (Gц, Z)-задачи, но есть найденное оптимальное решение нецелочисленной (G, Z)-задачи, т. е. ограничение должно обладать свойством правильности, которое не позволяет потерять оптимальное решение исходной (Gц, Z)-задачи.
Пусть x(G, Z) — оптимальное решение (G, Z)-задачи, которое является недопустимым решением для (Gц, Z)-задачи. Неравенство
(18)
определяет правильное отсечение, если удовлетворяет
-
условию отсечения: x(G, Z) не удовлетворяет неравенству (18),
-
условию правильности: любое допустимое решение (Gц, Z), удовлетворяет неравенству (18).
Методы, основанные на использовании процедуры построения правильных отсечений, получили название методов отсечения.
Первый алгоритм р. Гомори решения полностью целочисленных задач.
Следуя общей схеме методов отсечения, решим (G, Z)-задачу (14,15,17), соответствующую (Gц, Z)-задаче (14—17). Пусть x(G, Z) — ее оптимальное решение. Проанализируем координаты x(G, Z) на целочисленность. Если все координаты вектора x(G, Z) целые, то x(G, Z)= x(Gц, Z). Если хотя бы одна координата, пусть xi, будет нецелой, поступим следующим образом.
Обозначим через N совокупность небазисных переменных и на основании последней симплексной таблицы запишем разложение xi по небазисным переменным xj, jN.
(19)
Так как xi — нецелая величина, обозначим ближайшее целое число, не превосходящее xi, через [xi] и определим дробную часть: {xi}=xi—[xi]. Очевидно, xi >0.
Покажем, что по i-ой строке симплексной таблицы (G, Z)-задачи (в которой стоит нецелая координата решения) можно определить дополнительное линейное ограничение, обладающее свойствами правильности.
Т е о р е м а 2. Пусть x=(x1,…, xn),— допустимое решение (Gц, F)-задачи, тогда соотношения
определяют правильное отсечение.
Следствие. Любое оптимальоне решение x(G, Z) (G, Z)-задачи, не являющееся допустимым решением(Gц, Z)-задачи, не удовлетворяет условию правильного отсечения (20).
Очевидно, что количество дополнительных ограничений будет нарастать по мере решения вспомогательных (G, Z)-задач, оптимальные планы которых будут содержать нецелые координаты, т. е. возникает проблема размерности.
Р. Гомори предложил прием, позволяющий ограничить размеры рассматриваемых симплексных таблиц вспомогательных задач величиной (n+2) (k+1), где n — количество переменных (G, Z)-задачи, k — число небазисных переменных ее. Этот прием основывается на том, что нас интересует дополнительное ограничение лишь как способ отсечения нецелочисленного оптимального решения вспомогательной задачи, полученной на данном шаге, и перехода к следующей задаче.
Последовательность (G, Z)-задач пометим индексом k=0,1,… , соответствующим номеру итерации в последовательном приближении к решению исходной (Gц, Z)-задачи, и обозначим (Gk, Z). При этом (G0, Z)-задача соответствует (G, Z)-задаче (задаче без требования целочисленности).
Переменную zi, которая определяется дополнительным линейным ограничением (9.20) и строится по некоторой целочисленной координате оптимального решения (Gk, Z)-задачи (k=0, 1, 2, …) обозначим xn+k+1.
Чтобы размерность последовательности (Gk, Z)-задач не возрастала, вычеркнем из симплекс-таблицы переменную, по которой построено дополнительное линейное ограничение.
Перейдем к вычислительной схеме.
-
Решим (Gk, Z)-задачу (вначале k=0) методом последовательного улучшения плана.
Пусть в базис оптимального решения вошли векторы As1, … , Asm. Параметры последней симплекс-таблицы обозначим через xij;
j= x0j, i=1,2,…,m; j=1,2,…,n.
Если все базисные составляющие xi0 оптимального решения x(Gk, Z) (Gk, Z)-задачи целые, то x(Gk, Z)= x(Gц, Z). Если некоторая координата xi0 оптимального решения x(Gk,F) нецелая, то перейдем к п. 2.
-
Если среди совокупности координат оптимального решения x(Gk, Z) имеется единственная нецелая координата, то дополнительное линейное ограничение (9.20) строится по этой координате. Если нецелых координат в x(Gk, Z) более одной, то выберем координату с наименьшим номером. Пусть ею оказалась xl0. Составим дополнительное линейное ограничение
-
Добавим условия (21, 22) к условиям (Gk, Z)-задачи. Получим новую (Gk+1, Z)-задачу. Так как оптимальное решение x(Gk, Z) (Gk, Z)-задачи определяло одну из вершин многогранника условий, то оно может быть выбрано в качестве первоначального опорного решения для вновь полученной задачи. А это означает, что последнюю симплексную таблицу (Gk, Z)-задачи можно взять в качестве исходной для (Gk+1, Z)-задачи, дополнив ее условием (21).
Итак, симплексная таблица для (Gk+1, Z)-задачи получается из последней симплексной таблицы для (Gk, Z)-задачи путем окаймления (i+1)-строки с элементами:
xi+1 0= – { xl 0},
xi+1 j= – { xl j},
где j Nk, где Nk — небазисные переменные (Gk, Z)-задачи.
xi+1 n+1= 1,
xi+1 j= 0, j Nk.
Получим новую задачу, переменными которой являются x1, x2, x3, … , xn, xn+k+1. Условия этой задачи разрешены относительно xs1, … , xsm переменных и новой переменной xn+k+1, а линейная форма выражена через небазисные переменные (Gk, Z)-задачи. Так как мы занимаемся максимизацией Z(x) и решение x* для (Gk, Z)-задачи оптимально, то все j 0. Поэтому процесс перехода к новому решению (Gk+1, Z)-задачи не может быть осуществлен по методу уточнения плана. В то же время xi+1 0= – { xl0} и поэтому вектор A0 симплексной таблицы не является опорным решением для (Gk+1, Z)-задачи, так как решением называется вектор, все координаты которого неотрицательны и удовлетворяют условию принадлжности области Gk+1. Поэтому назовем полученный вектор x=(x1*, … , xi*, xi+1, 0) псевдорешением задачи (Gk+1, Z) и перейдем к дальнейшему преобразованию симплекс- таблицы.
Обозначим через k номер псевдорешения (Gk, Z)-задачи; тогда направляющей строкой является i+k+1-я строка, k = 0, 1, 2, … . Поэтому на каждом этапе преобразования таблицы вектор Ai+k+1 будет выводиться из таблицы. Через конечное число шагов либо будет найдено целочисленное решение, либо будет обнаружена ее неразрешимость, а тем самым неразрешимость (Gц, Z)-задачи.
Если решение (Gk, Z)-задачи завершается построением оптимального целочисленного решения x*, то m, первых его компонент определяют решение целочисленной задачи; если среди координат x* есть дробные, то одна из дробных компонент порождает дополнительное ограничение и процесс решения должен быть продолжен с новой окаймляющей строкой. Строка, используемая ранее для окаймления, вычеркивается и больше для построения расширенных задач не восстанавливается.
Процедуру решения (Gk, Z)-задачи (k = 0, 1, …) и анализа полученного решения назовем большой итерацией. Номер большой итерации совпадает с номером решаемой (Gk, Z)-задачи.
Результатом большой итерации является переход к новой (Gk+1, Z)-задаче либо окончание решения задачи.
П р и м е р 2. Найти максимальное значение функции с помощью первого алгоритма Р. Гомори:
Z=3x1+2x2+x3+x4+x5
при условиях
x1+ x2+ x3 =13,
x1 - x2 + x4 =6,
-3x1+ x2 + x5=9,
xj0 (j=1,2,…,5),
xj — целые (j=1,2,…,5).
Р е ш е н и е. Для определения оптимального плана целочисленной задачи сначала найдем оптимальный план задачи без условия целочисленности.
Найденный оптимальный план X=(19/2, 7/2, 0, 0, 34) не является оптимальным планом целочисленной задачи, поскольку две компоненты x1 и x2 имеют нецелочисленные значения. Составим дополнительное ограничение для переменной x2. Из последеней симплекс-таблицы имеем:
x2 +1/2 x3 -1/2 x4 =7/2.
Таким образом, к системе ограничений задачи добавляется неравенство:
x3 + x4 1.
Из последней симплекс-таблицы видно, что исходная задача целочисленного программирования имеет оптимальный план X*=(9; 4; 0; 1; 32). При этом плане значение целевой функции равно Zmax =35.