- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
11. Понятие базиса. Переход от одного базисного решения к другому
Здесь нам понадобятся некоторые понятия линейной алгебры..
Векторы А1, А2, …, АS являются линейно-независимыми, если равенство k1A1+k2A2+…+kSAS=0 выполняется только при k1=k2=…=kS=0. Признаком линейной независимости векторов является ненулевое значение определителя, составленного из этих векторов, так как однородная система имеет единственное (нулевое) решение только при таком определителе.
Если есть система линейно-независимых векторов, то любой другой вектор может быть выражен в виде их линейной комбинации и притом единственным образом:
Ap=1A1+2A2+…+SAS, p[1, S].
В канонической форме условия записываются в виде
(4.4)
Пусть система (4.4) имеет базисное решение:
(4.5)
Тогда из (4.4) следует
(4.6)
Так как система (4.6) совместна, то ее определитель не равен нулю и, значит, векторы, входящие в (4.6), являются линейно-независимыми. Для их обозначения введем следующее понятие: система m линейно-независимых векторов, соответствующих базисным переменным, называется базисом. Таким образом, каждой экстремальной точке соответствует своё базисное решение и свой базис.
Теперь, имея исходные базисное решение (4.5) и базис , построим новое базисное решение. Как следует из геометрических представлений, смежные вершины отличаются по составу базисных переменных только одной. Поэтому новое решение можно получить вводом в исходное небазисной переменной с одновременным переводом одной базисной переменной в небазисные.
Пусть вводимой будет переменная с индексом r[1,m], принимающая в новом решении некоторое положительное значение
В новом решении, как в любом допустимом, условия (4.4) также должны выполняться, поэтому имеем:
(4.7)
Задача состоит в том, чтобы определить X(1) по X(0). С этой целью сделаем несложные преобразования. Выразим вектор Ar через исходный базис:
Ar=A11r+A22r+…+Ammr. (4.8)
Так как известен базис, то известны (или находятся решением этой ситстемы) коэффициенты разложения ir. Умножим левую и правую части равенства (4.8) на :
Ar=A11r+A22r+…+Ammr . (4.9)
Вычитая (4.9) из (4.6), получим:
или окончательно:
( 4.10)
Сравнивая равенства (4.7) и (4.10), видим, что правые части равны, а левые содержат одну и ту же ситстему векторов. Поэтому коэффициенты при одноименных векторах должны совпадать. Приравнивая их, получаем искомые соотношения:
(4.11)
Однако решение (4.11) может быть недопустимым, если не оговорить возможные значения . Предположим, что среди коэффициентов ir есть положительные. Тогда с увеличением значения соответствующие переменные могут стать отрицательными. Поэтому для допустимости решения X(1) необходимо, чтобы было ограничено сверху:
(4.12)
С учетом (4.12) решение (4.11) всегда будет допустимым, но число ненулевых переменных в нем может превышать m, так как добавлена xr, а значит, оно может быть небазисным. Если же в качестве значения выбрать 0, то одна из переменных станет равной нулю, а решение (4.11) базисным.
Пусть минимум в (4.12) достигается на переменной xk. Тогда базисные переменные в новом опорном решении будут вычисляться по формулам:
(4.13)
Этому решению соответствует новый базис {Ai}(1)={A1,…,Ak-1,Ar, Ak+1,…,Am}. Таким образом, переход к новому базисному решению произошел путем замены переменной Xk на Xr, соответсвенно в базисе Ak на Ar.
Р ассмотрим возможные ситуации при переходе от одного решения к другому. Как было показано выше, при существовании положительных коэффициентов ir достигается новое базисное решение (смежная вершина), что иллюстрируется рис. 4.6-а. Если же все ir неположительны, величина , а это значение вводимой переменной, не ограничена сверху. Следовательно, введение такой переменной не приведет к получению базисного решения (достижению новой вершины). Это признак того, что соответствующее ребро допустимого множества, а значит, и само множество оказываются неогранниченными (рис. 4.6-б).
При вычислении 0 минимум может достигаться более чем на одном индексе. При этом обнуляется более одной переменной из входящих в исходное решение. Следовательно, в новом решении будут базисные переменные с нулевым значением, что означает попадание в вырожденное базисное решение.
Если исходное решение вырожденное и нулевой переменной соответствует коэффициет kr>0, то согласно (4.12) 0=0 и значения переменных не изменяются. Однако состав базиса и базисных переменных изменится произойдет замена на При высокой степени вырожденности теоретически возможно зацикливание, то есть возврат к старому базису, но на практике такие случаи не встречались.