- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
9. Основные понятия лп. Свойства задач лп
Множество D={xRn| AXB, X0} называется допустимым множеством задач ЛП. Иначе говоря, это множество всех решений, удовлетворяющих всем ограничениям задачи. Поэтому форма записи модели не влияет на D.Любое решение ХD называют допустимым решением задачи ЛП.
Допустимое решение Х* является оптимальным для задачи максимизации, если выполняется неравенство
L(X*) L(X), XD. Чтобы определить свойства допустимого множества задачи ЛП, обратимся к терминам теории множеств. Множество называется замкнутым, если оно содержит и свою границу, в противном случае оно открытое. Множество может быть ограниченным, если на нем все переменные ограничены снизу и сверху, и неограниченным, если хотя бы одна переменная на нем не ограничена. Непрерывное множество выпукло, если вместе с любыми двумя точками оно содержит и весь соединяющий их отрезок, иначе множество будет невыпуклым. Пусть условия задачи записаны в стандартной форме
aijxj bi,
Так как в условия входят только непрерывные переменные, а отношения являются нестрогими, то порождаемое ими множество непрерывно и замкнуто. Возьмем одно неравенство. При двух переменных граница области, где выполняется это неравенство, представляет собой прямую, а множество значений переменных, удовлетворяющих строгому неравенству, расположено с одной стороны границы. Таким образом, неравенству соответствует полуплоскость, которая является выпуклым множесмом. При трех переменных границей будет плоскость, а соответствующее множество – выпуклым полупространством. При большем числе переменных неравенство порождает многомерное выпуклое полупространство с границей – гиперплоскостью.
Из теории множеств известно, что пересечение выпуклых множеств выпукло (если оно не пустое). В задаче ЛП число неравенств, а, значит, число полупространств, конечно. Их пересечение и дает допустимое множество D. В связи с этим дадим 2 определения.
Пересечение конечного числа выпуклых полупространств, если оно не пустое, называется выпуклым многогранным множеством. Ограниченное выпуклое многогранное множество называется выпуклым многогранником. Характерными примерами выпуклых многогранников являются различные пирамиды и призмы. Таким образом, допустимое множество задачи ЛП может быть или выпуклым многогранным множеством, или выпуклым многогранником, или пустым. Других вариантов быть не может.
Критерий L=CjXj – линейная функция и поэтому удовлетворяет условиям как выпуклости, так и и вогнутости одновременно. Из теории экстремумов известно, что максимум вогнутой функции или минимум выпуклой функции на выпуклом множестве может достигаться только на границе. Аналогичный вывод следует из рассмотрения критических точек целевой функции. Так как производная
= Const,
то точек, в которых она равна нулю или терпит разрыв, нет. Поэтому, если оптимум существует, то он может быть только на границе. Это важнейшее свойство задач ЛП.
Теперь введем понятие разрешимой задачи. Задача ЛП называется разрешимой, если она имеет хотя бы одно оптимальное решение, и неразрешимой в противном случае. Следует обратить внимание на то, что в этом определении не фигурируют допустимые решения, так как их наличие недостаточно для разрешимости задачи, что видно из нижеприводимых утверждений.
При решении задач ЛП возможны только три случая:
Условия задачи противоречивы (несовместны), допустимое множество пустое и, следовательно, задача неразрешима.
Условия задачи совместны, но допустимое множество неограниченно. Тогда возможны два исхода:
а) если критерий неограничен на этом множестве, то задача неразрешима;
б) если критерий ограничен, то задача разрешима.
Условия непротиворечивы и множество является выпуклым многогранником. В этом случае задача всегда разрешима.
Из приведенных утверждений, справедливость которых будет показана в следующем разделе, заключаем, что причиной неразрешимости задачи ЛП может быть либо неограниченность критерия, либо противоречивость ограничений.
Если модель задачи представлена в каноническом виде, то можно воспользоваться теоремой Кронекера-Капелли для системы линейных уравнений. Согласно теореме система совместна, если ранги основной и расширенной матриц равны, и несовместна в противном случае. Однако из-за трудоемкости вычисления ранга этот способ не используется, а неразрешимость задачи, если она имеет место, обнаруживается в процессе движения к оптимуму или при анализе результатов.