- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Теорема
Пусть f, i и k – дифференцируемые функции и справедливо свойство Слейтера (то есть найдутся такие ХD, что неравенства i будут строгими). F(X, ) – соответствующая функция Лагранжа. Тогда для того чтобы вектор Х* являлся решением общей задачи максимизации (8.2) необходимо выполнение условий
1) по X:
Xj* 0;
2) по :
Приведенные условия оптимальности называются условиями Куна-Таккера. Опуская строгое доказательство, приведем логическое обоснование выражений (8.5)-(8.9).
П о существу они являются обобщением классических условий экстремума, определяющих стационарные точки. Условие (8.5) содержит неравенство, так как неотрицательность вектора X означает, что максимум может быть либо при положительном X и тогда производная F по X обязательно равна нулю (случай 1 на рис. 8.3), либо при X=0 и тогда эта производная может быть как равной нулю, так и отрицательной (случаи 2 и 3 на рис. 8.3). Этим же объясняются условия дополняющей нежесткости (8.6): в точке максимума равны нулю либо X, либо производная, либо вместе.
Выражения (8.7)-(8.9) можно обосно–вать аналогично, если учесть, что по рассматривается минимум F и
.
Применив условия Куна-Таккера к задаче ЛП, получим равенства второй основной теоремы двойственности как частный случай условий дополняющей нежесткости, а двойственные переменные – как частный случай .
Особую роль условия Куна-Таккера играют в решении задач выпуклого программирования, так как для них они являются не только необходимыми, но и достаточными. В следующем разделе это свойство будет использовано для построения точного метода.
37. Квадратичное программирование
Задачи квадратичного программирования (КП) имеют место, если целевая функция – сумма линейной и квадратичной форм, а все условия линейные.
Например, в задаче с двумя переменными целевая квадратичная функция записывается следующим образом:
f(x1, x2) = d1x1 + d2x2 + ½(C11x12 + C12x1x2 + C21x1x2 + C22x22) .
линейная форма квадратичная форма
В векторной форме она принимает вид
.
Обобщая на случай многих переменных, получаем:
Матрица С – квадратная, диагонально-симметричная (Cij=Cji).
В целом задача квадратичного программирования ставится в виде:
(8.10)
; (8.11)
. (8.12)
Чтобы она являлась задачей выпуклого программирования, целевая функция (8.10) должна быть вогнутой.
Свойства функции определяются матрицей С. Для вогнутости функции необходимо, чтобы матрица С была отрицательно определенной (строгая вогнутость) или отрицательно полуопределенной. Матрица С отрицательно определенная, если для всех ненулевых X справедливо ХTСХ< 0, и отрицательно полуопределенная, если ХTСХ 0. В случае минимизации целевая функция должна быть выпуклой, что имеет место при положительно определенной или положительно полуопределенной матрице С. Практически определить свойство квадратичной функции можно с помощью достаточных условий экстремума: если функция в стационарной точке имеет максимум, она вогнутая, а если минимум, то выпуклая.
Далее будем полагать, что условия вогнутости функции выполняются. Тогда решение задачи КП можно найти на основе следующей теоремы.
Теорема
Для того чтобы вектор Х* являлся решением задачи (8.10)-(8.12), необходимо и достаточно существования таких неотрицательных m-мерных векторов W и и неотрицательного n-мерного вектора V, которые удовлетворяют следующей системе уравнений:
D + CX*-AT + V = 0, (8.13)
B - AX* - W = 0, (8.14)
VTX* = 0, (8.15)
WT = 0. (8.16)
Покажем, что теорема выводится из условий Куна-Таккера. Функция Лагранжа для рассматриваемой задачи имеет вид
.
Записываем условия (8.5):
.
Введя в это неравенство неотрицательный вектор дополнительных переменных V, получаем (8.13). (8.14) – это исходное условие задачи после приведения его к равенству вводом неотрицательного вектора дополнительных переменных W. Очевидно. что производная , когда дополнительная переменная V>0 и , когда V=0. Таким образом, V играет роль индикатора производной. Поэтому условие дополняющей нежесткости (8.6) принимает вид (8.15). Аналогична взаимосвязь вектора W с производной F по , и отсюда имеем второе условие дополняющей нежесткости (8.16).
Система уравнений (8.13)-(8.16) – нелинейная, так как нелинейны (8.15) и (8.16). Она содержит (m + n + 2) уравнений и 2(m + n) неизвестных X*, , V и W.
Так как и векторы V и X неотрицательны, из (8.15) следует, что по крайней мере n переменных из vj и xj равны 0. Аналогично из (8.16) вытекает, что равны нулю не менее m переменных из wi и i. Таким образом, в решении системы (8.13)-(8.14) положительными могут быть не более (m + n) переменных. Это свойство системы дает ключ к решению.
Действительно, линейная система (8.13), (8.14) содержит n+m уравнений и 2(n + m) неизвестных. Но известно, что в искомом решении число положительных переменных не превышает (m + n). Следовательно, это допустимое базисное решение (опорный план) системы (8.13), (8.14). Поэтому искать решение задачи КП нужно только среди опорных планов этой системы. Такие решения находятся методами линейного программирования. Опорный план системы (8.13), (8.14), удовлетворяющий условиям (8.15), (8.16), будет оптимальным решением задачи КП.
Перепишем уравнения (8.13), (8.14) в обычном виде:
(8.17)
Если вектор D – неположительный, а вектор B – неотрицательный, то начальное базисное решение V=-D, W=B удовлетворяет условиям (8.15), (8.16) и, значит, является оптимальным решением задачи КП. Однако, как правило, вектор D имеет положительные компоненты и такое начальное решение оказывается недопустимым. В этом случае, ориентируясь на использование прямого симплекс-метода, строится искусственное начальное решение: в уравнения (8.17) с отрицательной правой частью вводятся искусственные переменные yk и они вместе с неотрицательными vj и wi образуют базисное решение. В качестве критерия линейной задачи принимается сумма искусственных переменных:
Lиск = yk min.
Для выполнения условий дополняющей нежесткости (8.15)-(8.16) алгоритм симплекс-метода дополняется правилом ограниченного ввода:
если в базисном решении имеется vj, то не может вводиться xj (с тем же индексом) и наоборот;
если в базисном решении имеется wi, то не может вводиться i (с тем же индексом) и наоборот.
Иначе говоря, в базисном решении не могут находиться одновременно переменные v, x (w, ) с одинаковыми индексами. Если по оценкам претендентом на ввод является переменная, которую согласно правилу нельзя вводить, в базисное решение вводится другая переменная с положительной оценкой.
Признаком выполнения условий теоремы (8.13)-(8.16) и, следовательно, оптимальности решения задачи КП является равенство нулю всех искусственных переменных или Lиск=0.
Очевидно, что рассмотренный метод находит за конечное число шагов глобальное решение задачи КП с вогнутой функцией цели. При строгой вогнутости задача имеет одно решение, при нестрогой вогнутости возможно множество решений. Если функция не является вогнутой, метод находит некоторый локальный максимум.
Пример 8.2. Найти решение следующей задачи КП:
f = 10x1 + 20 x2 + x1x2 – 2x12 – 2x22 max,
8 – x2 0,
9 – x1 – x2 0,
x1, x2 0.
Перепише целевую функцию в векторной форме:
По матрице С (гессиану) проверяем достаточные условия: 1=-4<0, 1=16-2>0. Значит, f имеет максимум и строго вогнутая.
Записываем первую систему уравнений (8.17):
или
Добавляем вторую:
Для образования начального базисного решения вводим в первую систему искусственные переменные y1 и y2:
Критерий линейной задачи:
Lиск = у1 + у2 min.
Базисные переменные в начальном решении: y1, y2, w1 и w2.
Заполняем начальную симплекс-таблицу.
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
|
Баз. |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
10 |
4 |
-1 |
0 |
1 |
-1 |
0 |
0 |
0 |
1 |
0 |
5/2 |
1 |
|
20 |
-1 |
4 |
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
1 |
- |
0 |
|
8 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
- |
0 |
|
9 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
9 |
|
|
30 |
3 |
3 |
1 |
2 |
-1 |
-1 |
0 |
0 |
0 |
0 |
|
|
30 |
3 |
3 |
1 |
2 |
-1 |
-1 |
0 |
0 |
0 |
0 |
Выполнив симплекс-преобразования с учетом правила ограниченного ввода, находим оптимальное решение задачи КП. На рис. 8.4 показано допустимое множество задачи и линии уровня критерия. Оптимум достигается на границе допустимого множества в точке касания с линией уровня.
Этот пример показывает, что в задачах КП в отличие от линейного программирования оптимальное решение может находиться как в любой точке границы (не только в вершине), так и внутри допустимого множества в случае совпадения с безусловным максимумом.
В заключение отметим, что задача КП может использоваться в качестве аппроксимации при нелинейности критерия, отличной от квадратичной, так как в небольшой области гладкие функции с высокой точностью могут быть представлены квадратичной функцией. Ряд последовательных аппроксимаций с решением задачи КП позволяют найти решение исходной нелинейной задачи с необходимой точностью