- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
13. Алгоритм симплекс-метода
Резюмируя изложенное в предыдущих разделах, опишем алгоритм симплекс-метода. По модели в каноническом виде определяется начальное базисное решение. Последующие действия проводятся в специальных таблицах, называемых симплекс-таблицами. В них представляются результаты итераций, которые завершаются при выполнении признака оптимальности или обнаружении неразрешимости задачи.
Полная симплекс-таблица имеет следующую структуру.
Таблица l |
C0 |
C1 |
C2 |
… |
Cr |
… |
C |
|
|||
i |
Csi |
базис Asi |
B=A0 |
A1 |
A2 |
… |
Ar |
… |
A |
||
1 |
Cs1 |
As1 |
10=xS1 |
11 |
12 |
… |
1r |
… |
1 |
|
|
2 |
Cs2 |
As2 |
20=xS2 |
21 |
22 |
… |
2r |
… |
2 |
|
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
k |
Csk |
Ask |
k0=xSk |
k1 |
k2 |
… |
kr |
… |
k |
0 |
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
m |
Csm |
Asm |
m0=xSm |
m1 |
m2 |
… |
mr |
… |
m |
|
|
m+1 |
-m+1,j |
L |
Δ1 |
Δ2 |
… |
Δr |
… |
Δ |
|
||
m+2 |
zj |
z0 |
z1 |
z2 |
… |
zr |
… |
z |
Здесь Cj – коэффициенты линейной формы L, Csi – коэффициенты в L при базисных переменных (подмножество Cj), Asi – базисные векторы, si – индекс базисного компонента на позиции i. Жирной линией выделена главная часть таблицы, все ее элементы подчиняются соотношениям (4.22). Первая и последняя строки и второй столбец таблицы являются вспомогательными, они обязательны только в начальной таблице.
Примечание. В линейной алгебре во второй строке и третьем столбце таблицы используют обозначения переменных xj и xi вместо векторов Aj и Asi соответственно. Поскольку элементы главной части таблицы являются коэффициентами разложения векторов, принятые здесь обозначения, на наш взгляд, более корректны.
Алгоритм состоит из предварительного и основного этапов.
На предварительном этапе сначала определяется начальное базисное решение одним из методов, рассмотренных выше. Исходя из него заполняется начальная симплекс-таблица. В третий столбец заносятся m базисных векторов, а во второй – соответствующие коэффициеты из L (или из верхней строки) в порядке следования условий в модели (на первую позицию ставится вектор при базисной переменной из первого условия и т.д.).
Так как начальный базис единичный, элементы главной части таблицы кроме последней строки не вычисляются, а берутся прямо из модели (в столбец A0 заносятся правые части условий, в Aj – коэффициеты при ).
Для получения относительных оценок используются формулы (4.11) и (4.12). Значения zj находятся как скалярное произведение векторов Cb=[Csi] и Aj (суммируются произведения одноименных компонент). Вычитая из нижней строки верхнюю, получаем L и оценки Δj.
Основной этап является итерационным.
Очередная итерация заканчивается заполнением симплекс-таблицы за исключением столбца . Пусть завершилась l-я итерация. Цикл начинается с анализа оценок Δj в таблице l. Если нет отрицательных оценок, значит, выполнился признак оптимальности. В этом случае возможны два вывода:
если не вводились искусственные переменные или они равны нулю, получено оптимальное решение;
если хотя бы одна искусственная переменная не равна нулю, задача неразрешима из-за противоречивости условий.
При невыполнении признака оптимальности анализируются столбцы с отрицательными оценками. Если среди них обнаружится столбец, в котором все коэффициенты разложения неположительны, то есть ij0, i, то задача неразрешима по причине неограниченности критерия на допустимом множестве. В противном случае выбирается минимальная (отрицательная) оценка
Она определяет столбец Ar, называемый направляющим или разрешающим, или ведущим столбцом. Мы будем придерживаться первого термина.
Заполняется столбец . Значения вычисляются делением элементов столбца A0 на положительные элементы направляющего столбца
По минимальному значению определяется направляющая строка k:
На пересечении направляющей строки и направляющего столбца находится направляющий элемент kr. Тем самым определена переменная которая становися базисной, и переменная выводимая из числа базисных (она становится равной нулю).
Заполняется таблица l+1. В ней отражается смена базиса: вектор Ask заменяется вектором Ar, соответственно вместо Csk ставится Cr, остальные базисные элементы остаются на месте. Элементы главной части таблицы вычисляются согласно (4.22):
Э ти формулы применяются следующим образом. Элементы строки, которая была направляющей, находятся делением строки на направляющий элемент. Для вычисления остальных элементов можно использовать правило прямоугольника: в таблице l элемент ij проектируется на направляющий столбец и направляющую строку (рис.4.7). В вершинах образовавшегося прямоугольника находятся все элементы, входящие в рекуррентную формулу. Теперь, вычитая из проектируемого элемента произведение элементов в двух других противолежащих вершинах прямоугольника, деленное на направляющий элемент, получаем новое значение элемента. При этом так вычисляются элементы только небазисных столбцов, так как в базисных столбцах всегда имеем единичные векторы.
После заполнения главной части таблицы возвращаемся на начало основного этапа.
Для контроля вычислений можно проводить повторный счет оценок, используя вспомогательные строки z и C.
Наглядное представление алгоритма дает блок-схема, приведенная на рис. 4.8.
Замечание. При выборе направляющего столбца и направляющей строки может иметь место неоднозначность из-за достижения минимума более чем на одном индексе. При этом можно выбирать любой из них либо для однозначного выбора добавить правило, например, при нескольких индексах брать наименьший.
Из неоднозначности выбора строки следует, что новое базисное решение будет вырожденным. При степени вырожденности больше единицы теоретически возможно зацикливание. Для его устранения в теории предложена -задача, соответствующая малому деформированию вектора ограничений, которое приводит к замене вырожденной вершины невыржденными. Из решения этой задачи выведено более сложное правило выбора направляющей строки:
В строках с минимальным находятся отношения 1 элементов 1-го столбца к элементам направляющего и выбирается строка с минимальным 1. Если же этот выбор снова неоднозначен, то вычисляются отношения 11 элементов 2-го и направляющего столбца в строках с минимальным 1, и т.д. до достижения однозначного выбора. Это правило гарантирует от зацикливания. Однако на реальных задачах сталкиваться с зацикливанием не приходилось, и поэтому изложенное правило представляет больше теоретический интерес.