Решение задачи выпуклого программирования

Рассмотрим один из методов выпуклого программирования - метод Эрроу-Гурвица.

Прежде всего найдем минимум целевой функции, пока не учитывая ограничения:

X₁ = 3,26;

X₂ = 4,53.

Проверка соответствия полученных X₁ и X₂ ограничениями:

x₁5,

x₂8,

2x₁ + 2.5x₂ 16,

x₁2,

x₂4

показывает, что третье из них нарушено:

2x₁ + 2.5x₂ = 2×3.26 + 2.5×4.53 = 17.84 > 16,

т.е. наличного парка составов не хватает, поэтому X₁ = 3,26 и X₂ = 4,53 не будет решением задачи.

Положим, что запрещение использовать более 16 составов не является безусловным, но за использование каждого сверх 16 состава, назначается штраф, т.е. за нарушение на единицу третьего неравенства уплачивается условный «штраф» - l₃ .

Положим далее, что можно нарушить первое неравенство (x₁5) и пропустить по первому участку больше пяти поездов в час. Однако за каждую лишнюю нитку графика сверх пяти наложен штраф l₁ (индексы равны номерам нарушаемых неравенств).

Далее, полагаем, что если использование лишних ресурсов (составов, ниток графика) связано с уплатой штрафа, то экономия ресурсов в пределах рабочего парка (например, отказ от одного из 16 составов) награждается условной «премией» той же величины: l₃ - за отказ от одного состава; l₁ - от одной нитки графика. Для удобства эту премию можно представить как отрицательный штраф. Численные значения штрафов l_i пока не известны.

Далее решаем задачу заново, не рассматривая ограничения как безусловные запреты, а сводим к минимуму сумму реальных расходов F(x) с уплатой условных штрафов за перерасход ресурсов и вычетом условных премий за экономию. Обозначим сумму штрафов - R(x), тогда

R(x) = l₁(X₁ - 5) + l₃ (2X₁ + 2.5X₂ - 16) =

= (l₁+ 2l₃ )X₁ + 2.5l₃X₂ - 5l₁ +16l₃.