- •Моделирование
- •2. Точность вычислительного эксперимента
- •1. Линейное программирование
- •1.2. Графический метод решения задач лп
- •1.3 Проверка задач лп на чувствительность
- •1.4 Симплекс - метод решения задач лп
- •1.4. Симплекс-метод решения задач лп
- •1.5. Модифицированный симплекс-метод
- •Исходная таблица имеет вид
- •1.6. Транспортная задача
- •1.7. Метод потенциалов для решения тз
- •1.7.1. Нахождение предварительного плана перевозок
- •Учитывая условия баланса наличия и потребления
- •1.7.2. Проверка опорного плана на оптимальность
- •1.7.3. Корректировка плана перевозок
- •1.8. Алгоритм метода потенциалов
- •Проверим необходимое условие в опорном плане:
- •0 3 0 Таблица 1.14
- •Преобразованная матрица показана в табл. 1.25
- •Преобразованная матрица стоимостей приведена в табл. 1.28.
- •1.9. Транспортная задача в сетевой форме
- •1.10. Двойственные задачи линейного программирования
- •Легко видеть, что
- •Запишем целевую функцию для прямой задачи
- •Прямая задача:
- •Из этой таблицы находим решение двойственной пары:
- •Окончательно прямая задача имеет следующее решение:
- •2. Обработка результатов эксперимента
- •Аппроксимация гиперболической функцией
- •Аппроксимация функциональной зависимостью вида
- •Аппроксимация функциональной зависимостью вида
- •Интерполяционный многочлен Ньютона
- •Экстраполяция
- •3. Некоторые простейшие задачи нелинейной оптимизации
- •3.1. Оптимизация числа ниток в графике движения поездов
- •3.2. Управление запасами
- •Понятие о выпуклом программировании
- •В нашем примере целевая функция имеет вид
- •Проверим:
- •Решение задачи выпуклого программирования
- •Сумма реальных расходов со штрафом составит
- •Филоненков Александр Иванович
- •Математические модели и меттоды Учебное пособие
Понятие о выпуклом программировании
Напомним понятия выпуклой функции на примере функции одной переменной, изображенной на плоскости (рис. 3.6).
Функция выпукла, если прямолинейный отрезок, соединяющий любые две точки кривой, полностью лежит выше самой кривой. Если любой такой отрезок лежит ниже кривой, то функция вогнута.
Рис. 3.6
Аналогично можно представить выпуклые и вогнутые функции в пространстве: так, сферический купол здания изображает вогнутую функцию, а сферическое дно резервуара - выпуклую. Для функций более двух переменных геометрическая наглядность теряется, но сохраняется аналитическое определение свойства выпуклости. Функция F(X) выпукла, если для двух любых точек X1 и X2 при любом
0
1
справедливо неравенство
F(X1
+ (1- )X2)
F(X1)
+ (1- )F(X2)
где X - совокупность значений ряда переменных, определяющих функцию (например, конкретное число поездов на первом, втором, третьем участке).
На рис. 3.5 функции 1, 2, 3 - выпуклые, а 4, 5, 6, 7 - вогнутые, функция 8 не относится ни к одному из этих видов. Функция 9 имеет разрыв, поэтому так же не относится ни к одному из видов. Из сравнения 3 и 7 видно, что если F(X) выпукла, то -F(X) вогнута, и наоборот. Выпуклые функции имеют не более одного минимума, вогнутые - не более одного максимума. Функция 8 может иметь много минимумов и много максимумов (так, кривая 8 имеет минимумы при X=A и X= B). В этом случае минимум с наименьшим значением F(X) называют глобальным (общим), а остальные - локальные (местные). Та же терминология применяется и к максимумам, если их несколько.
Задачи оптимизации с нелинейными целевыми функциями могут быть точно решены при двух условиях:
Допустимое значение переменных Xi образуют выпуклую область. На нашем рисунке затемненная область возможных решений выпукла.
Целевая функция, сводимая к минимуму, должна быть выпуклой (1-3), а к максимуму - вогнутой.
Этими методами решаются задачи на минимум расходов, если расходы - выпуклая функция, и на максимум продукции или прибыли, если это вогнутые функции.
При анализе конкретной задачи необходимо определить характер целевой функции. Задача упрощается, если целевая функция - это сумма слагаемых, каждое из которых зависит лишь от одной переменной:
F(x1,…,xn) = F(x1) + … + Fn(xn).
В нашем примере целевая функция имеет вид
F(X) = 75X1 + 800/X1 + 78X2 + 1600/X2 .
Функция выпукла, если F"(x)>0 для любого x.
Проверим:
;
;
;
.
Значит, функция выпукла, поскольку x>0.
Следовательно, выбор оптимального числа поездов на двух участках оказывается задачей выпуклого программирования, которая может быть решена двумя группами методов:
1). выпуклого программирования;
2). кусочно-линейного программирования.
Решение задачи выпуклого программирования
Рассмотрим один из методов выпуклого программирования - метод Эрроу-Гурвица.
Прежде всего найдем минимум целевой функции, пока не учитывая ограничения:
X1
= 3,26;
X2
= 4,53.
Проверка соответствия полученных X1 и X2 ограничениями:
x
1
5,
x2 8,
2x1 + 2.5x2 16,
x1 2,
x2
4
показывает, что третье из них нарушено:
2x1 + 2.5x2 = 23.26 + 2.54.53 = 17.84 > 16,
т.е. наличного парка составов не хватает, поэтому X1 = 3,26 и X2 = 4,53 не будет решением задачи.
Положим, что запрещение использовать более 16 составов не является безусловным, но за использование каждого сверх 16 состава, назначается штраф, т.е. за нарушение на единицу третьего неравенства уплачивается условный «штраф» - 3 .
Положим далее, что можно нарушить первое неравенство (x1 5) и пропустить по первому участку больше пяти поездов в час. Однако за каждую лишнюю нитку графика сверх пяти наложен штраф 1 (индексы равны номерам нарушаемых неравенств).
Далее, полагаем, что если использование лишних ресурсов (составов, ниток графика) связано с уплатой штрафа, то экономия ресурсов в пределах рабочего парка (например, отказ от одного из 16 составов) награждается условной «премией» той же величины: 3 - за отказ от одного состава; 1 - от одной нитки графика. Для удобства эту премию можно представить как отрицательный штраф. Численные значения штрафов i пока не известны.
Далее решаем задачу заново, не рассматривая ограничения как безусловные запреты, а сводим к минимуму сумму реальных расходов F(x) с уплатой условных штрафов за перерасход ресурсов и вычетом условных премий за экономию. Обозначим сумму штрафов - R(x), тогда
R(x) = 1(X1 - 5) + 3 (2X1 + 2.5X2 - 16) =
= (1+ 23 )X1 + 2.53X2 - 51 +163 .
