- •Экзаменационные вопросы
- •1 Постановка задачи. Локальные и глобальные экстремумы
- •2 Задача максимизации функции
- •3 Необходимые и достаточные условия локального экстремума. Классический метод нахождения экстремумов функций
- •3.1 Классический метод
- •4 Метод деления отрезка пополам
- •5 Метод золотого сечения
- •5.1 Модификация метода золотого сечения
- •6 Симметричные методы
- •6.1 Постановка задачи об оптимальных методах
- •6.2 Оптимальный пассивный метод для задачи А (метод равномерного перебора)
- •6.3 Оптимальный последовательный метод для задачи А (метод Фибоначчи)
- •7 Метод ломаных
- •7.1 Описание метода ломаных
- •7.2 Сходимость метода ломаных
- •7.3 Определение константы L
- •7.4 Достоинства и недостатки метода ломаных
- •9 Линейные пространства
- •10 Постановка задачи минимизации
- •12 Численные методы безусловной минимизации
- •13 Общая схема градиентого спуска
- •13.1 Градиентые методы с дроблением шага
- •13.2 Метод наискорейшего спуска
- •13.3.1 О сходимости градиентого метода
- •13.4 Методы покоординатного спуска (для отыскания безусловного экстремума)
- •13.4.1 Метод покоординатного спуска без вычисления производных
- •13.4.2 Рекомендации по применению этого метода
- •14 Относительный (условный) экстремум
- •15.1 Метод исключения
- •15.3 Метод Лагранжа
- •17 Обобщенная функция Лагранжа
- •17.1 Обобщеный метод множителей Лагранжа
- •17.2 Единственность вектора Лагранжа для нормального оптимального плана
- •18 Общая задача математического программирования
- •19 Выпуклые множества
- •19.1 Выпуклые функции
- •20 Дифференциальные условия оптимальности в задаче математического программирования
- •21.2 Метод проекции градиента
- •21.3 Проекция точки на гиперплоскость
- •21.4 Проекция точки на аффинное множество
- •21.5 Проекция точки на шар
- •21.6 Проекция точки на замкнутое полупространство
- •21.8 Метод покоординатного спуска для отыскания условного экстремума
- •22 Метод штрафных ф-ий
- •22.1 Метод внешних штрафных функций
- •22.2 Метод барьерных функций
- •22.2.1 Описание метода барьерных функций (для решения задачи 6.1)
- •23 Общая задача ЛП и ее канонические формы
- •23.1.3 Переход к эквивалентой системе неравенств
- •23.1.4 Переход от задачи минимизации к задаче максимизации
- •24 Различные формы записи задачи ЛП
- •24.1 Развернутая форма задачи ЛП
- •24.2 Векторная форма
- •24.3 Матричная форма
- •24.4 План. Опорный план. Оптимальный план
- •25 Выпуклые многогранники
- •26 Геометрическая интерпретация задачи ЛП
- •26.1 Свойства решения задачи ЛП
- •26.2 Графический метод решения задачи ЛП
- •27 Симплексный метод решения задач ЛП
- •27.1 Построение опорных планов
- •27.2 Отыскание оптимального плана. Условия оптимальности
- •27.3 Алгоритм симплексного метода. Симплексная таблица
- •27.3.1 Правила заполнения таблицы
- •27.3.2 Анализ симплексной таблицыx
- •27.3.3 Переход к новому опорному плану
- •27.3.4 Замечание к решению задачи на максимум
- •28 Методы искусcтвенного базиса
- •28.1 Метод больших штрафов
- •28.2 Двухэтапный метод
- •29 Вариация и ее свойства
- •30 Уравнение Эйлера
- •31 Простейшие случаи интегрируемости уравнения Эйлера
Часть V
Линейное программирование
23 Общая задача ЛП и ее канонические формы
Общая задача ЛП на минимум формулируется так: найти минимум ф-и
|
n |
|
jP |
f(x1; x2; :::; xn) = |
=1cjxj ! min (7:1) |
при условиях
n
P
aijxj > bi i = 1; 2; :::; m1 (7:2)
j=1
n
P
aijxj = bi i = m1 + 1; :::; m (7:3)
j=1
xj > 0 j = 1; 2; :::; n1 6 n (7:4)
В выражениях (7:1) (7:4) cj bi aij - постоянные величины
Существуют следующие частные случаи общей задачи линейного программирования, называемые каноническими формами
1.При m1 = 0 и n1 = n получаем первую каноническую формулу задачи линейного программирования. Найти минимим
|
n |
|
jP |
f(x1; x2; :::; xn) = |
=1cjxj ! min (7:5) |
при условиях
n
P
aijxj = bi i = 1; 2; :::; m (7:6)
j=1
xj > 0 j = 1; 2; :::; n (7:7)
Называется так же стандартной формой задачи ЛП.
2.При m1 = m и n1 = 0 получаем вторую каноническую форму. Найти минимим
|
n |
|
jP |
f(x1; x2; :::; xn) = |
=1cjxj ! min (7:8) |
при условии
n
P
aijxj > bi i = 1; 2; :::; m (7:9)
j=1
3.При m1 = m и n1 = n получаем cимметричную каноническую форму Найти минимим
|
n |
|
jP |
f(x1; x2; :::; xn) = |
=1cjxj ! min (7:10) |
при условиях
n
P
aijxj > bi i = 1; 2; :::; m (7:11)
j=1
47
xj > 0 j = 1; 2; :::; n (7:12)
Общая задача ЛП на максимум формулируется так
|
n |
|
jP |
f(x1; x2; :::; xn) = |
=1cjxj ! max (7:13) |
при условиях
n
P
aijxj 6 bi i = 1; 2; :::; m1 (7:14)
j=1
n
P
aijxj = bi i = m1 + 1; :::; m (7:15)
j=1
xj > 0 j = 1; 2; :::; n1 6 n (7:16)
У задачи на максимум возможны аналогичные частные случаи, так же называемые каноническими формами.
23.1Переход от ограничений-неравенств к равенствам и другие варианты преобразования ограничений
23.1.1Переход от ограничения-неравенства к равенству
Пусть дано условие
ai1x1 + ai2x2 + ::: + ainxn 6 bi
Это условие эквиваленто двум ограничениям
ai1x1 + ai2x2 + ::: + ainxn + xn+1 = bi
xn+1 > 0
Переменные типа xn+1называют фиктивными или дополнительными
23.1.2Представление ограничения-равенства парой неравенств
Ограничение
ai1x1 + ai2x2 + ::: + ainxn = bi
можно представить парой ограничений
ai1x1 + ai2x2 + ::: + ainxn 6 bi
( ai1)x1 + ( ai2)x2 + ::: + ( ain)xn 6 bi
23.1.3Переход к эквивалентой системе неравенств
Меняя знаки правой части и коэффициентов в ограничении-неравенстве можно поменять знак этого неравенства на обратный.
Пусть дано ограничение
ai1x1 + ai2x2 + ::: + ainxn > bi
Его можно заменить следующим эквивалентным ограничением
( ai1)x1 + ( ai2)x2 + ::: + ( ain)xn 6 bi
48