- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Условия оптимальности
Здесь рассмотрим наиболее важные с точки зрения приложений необходимые и достаточные условия оптимальности. Они позволяют строить методы отыскания эффективных решений и способы проверки эффективности найденных решений.
Наиболее общий случай необходимых условий содержит следующая теорема.
Теорема 1. Пусть Y* G и все . Вектор Y* слабо эффективен тогда и только тогда, когда найдутся такие числа , что
(10.1)
Условие не ограничивает применимость теоремы, так как его всегда можно обеспечить добавлением к положительной константы .
При оговариваемых свойствах D и f(X) справедливы теоремы 2 и 3.
Теорема 2. Пусть D выпукло, а , вогнуты и положительны на D. Тогда решение X* слабо эффективно в том и только в том случае, если существуют такие числа , что
. (10.2)
Теорема 3. Пусть D выпукло, а f вогнуто. Для слабой эффективности точки X*D необходимо и достаточно, чтобы существовали числа , при которых
. (10.3)
Т ребование вогнутости f существенно, так как его невыполнение может привести к тому, что не для всех слабо эффективных решений найдутся , удовлетворяющие (10.3). Например, для критериев и ( выпукла) на D=[0,1] множество S(X)=D. Максимум функции достигается только на одном из концов интервала [0,1] и поэтому ни при каких неотрицательных и максимизация этой функции не даст слабо оптимальную точку, лежащую внутри D.
Терема 4.Вектор Y*G эффективен тогда и только тогда, когда для каждого
, (10.4)
где
¦ > , }. (10.5)
Если Y*G эффективна, то она является единственной в G точкой, удовлетворяющей (10.4) при каждом .
Достаточные условия, приведенные ниже, основаны на свойствах возрастающей функции многих переменных. Поэтому сначала дадим определение такой функции. Числовая функция F(Y), определённая на множестве G, является возрастающей по отношению , если из выполнения неравенства YY для векторов Y,YG всегда следует справедливость неравенства F(Y)>F(Y). Аналогично, F(Y) – функция, возрастающая по отношению >, если из Y>Y всегда следует F(Y)>F(Y).
Теорема 5. Пусть функция F(Y) определена на множестве G. Для того чтобы точка Y*G была эффективной (слабо эффективной), достаточно, чтобы она являлась точкой максимума на множестве G функции F(Y), возрастающей по отношению (по отношению >).
Теорема легко доказывается от противного. Пусть Y*G и
F(Y*)F(Y) для всех YG. (10.6)
Предположим противное, т.е. что существует YG, для которого верно неравенство Y Y*. Так как функция F возрастающая по отношению , то противоречит (10.6). Аналогично доказываются достаточные условия слабой эффективности.
Теорема 5 играет важную роль в решении многокритериальных задач. Её применение основано на максимизации возрастающих функций многих переменных. Поэтому целесообразно рассмотреть примеры таких функций.
1). Функция F(Y)= , где , является возрастающей по каждой переменной на числовой оси и потому возрастает по на Em. Поэтому любая точка максимума F(Y) на G эффективна. Эта же функция при и хотя бы одном из них положительном является возрастающей по отношению > и, значит, максимизация такой функции на G дает слабо эффективную точку.
2
m
m
m
3).Функция F(Y) , где s>0, >0, а >= , , возрастает по ≥ на G. Поэтому любая её точка максимума на G эффективна. Отсюда, в частности, следует, что минимизация широко применяемой функции дает эффективную точку.
4
m
m
5). Возьмём функцию F(Y) при , . Если для всех i, то и для всех i. Поэтому справедливо неравенство
m