Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

МЕТОД ВОЗМУЩЕНИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПАРАМЕТРОМ

Кравчук С.П. 1 Кравчук И.С. 2 Татарников О.В. 1 Швед Е.В. 1
1 ФГБОУ ВПО «Российский экономический университет им. Г.В. Плеханова»
2 ФГБОУ ВПО «Московский государственный университет путей сообщения»
Предложенный ранее авторами метод последовательного исключения переменных в системе линейных неравенств, ставящих задачу линейного программирования, позволяет также находить точное аналитическое решение задач с переменными коэффициентами, зависящими от параметра. Однако при изменчивых знаках коэффициентов задачи требуется кропотливое рассмотрение отдельных промежутков параметра, где коэффициенты сохраняют свой знак. Для случая слабого относительного изменения всех коэффициентов в данной работе предлагается эффективный приближённый способ нахождения аналитического решения задачи линейного программирования с переменными коэффициентами. Суть его составляет широко используемый в прикладной математике метод возмущений, или метод малого параметра, позволяющий строить простую итерационную схему. При этом точность решения порядка 1 % достигается за несколько итераций. Рассмотренная методика легко обобщается и на многопараметрические задачи.
неравенства
линейное программирование
симплекс-метод
метод Жордана – Гаусса
целевая функция
экстремум
матрица
метод возмущений
1. Кравчук С.П., Кравчук И.С., Татарников О.В., Швед Е.В. Метод неравенств в задаче линейного программирования с параметром. – М.: Фундаментальные исследования, 2014. – № 9, часть 12.
2. Кравчук С.П., Кравчук И.С., Швед Е.В. Экстремумы в системе линейных неравенств с двумя переменными. – СПб.: Современные аспекты экономики, 2010. – № 6 (154).
3. Кравчук С.П., Кравчук И.С., Татарников О.В., Швед Е.В. Метод неравенств в задачах линейного программирования. – М.: Фундаментальные исследования, 2014. – № 3, часть 1.
4. Найфе А.Х. Введение в методы возмущений. – М.: Мир, 1984.
5. Олвер Ф. Введение в асимптотические методы и специальные функции. – М.: Мир, 1986.

В работе [1] показано, как на основе метода последовательного исключения переменных в системе линейных неравенств [2, 3] можно находить точное аналитическое решение задачи линейного программирования, коэффициенты которой зависят от параметра. Однако даже в случае однопараметрической задачи с двумя переменными [1] решение может оказаться громоздким. В практических же задачах линейного программирования коэффициенты обычно незначительно изменяются относительно своих средних значений, как, например, стоимость товара в зависимости от курса валют или инфляции. В подобных случаях, когда относительные изменения коэффициентов порядка 10 % и меньше, удобно использовать широко применяемый в различных исследованиях асимптотический метод возмущений [4, 5]. Суть его сводится к поиску разложения искомых функций в функциональные ряды, быстрота сходимости которых зависит от «параметра малости» – относительного изменения функций, влияющих на задачу.

Итерационная схема решения

Рассмотрим в общем случае задачу на минимум, преобразованную к системе линейных неравенств [3]:

kravchuk01.wmf (1)

В задаче на максимум в первом неравенстве (1) следует поменять знак «≤» на «≥» [3].

Обозначим через kravchuk02.wmf kravchuk03.wmf kravchuk04.wmf средние значения всех коэффициентов:

kravchuk05.wmf kravchuk06.wmf kravchuk07.wmf

где, например, для непрерывных коэффициентов, зависящих от параметра t ∈ [0;1],

kravchuk08.wmf (2)

Пусть kravchuk09.wmf kravchuk10.wmf kravchuk11.wmf означают отклонения этих коэффициентов от их средних значений:

kravchuk12.wmf kravchuk13.wmf kravchuk14.wmf

Тогда средние значения отклонений равны нулю:

kravchuk15.wmf (3)

Далее предполагается, что все относительные отклонения, например, kravchuk16.wmf, достаточно малы (менее 10 %).

Будем искать Z и xi для системы (1) в виде рядов, состоящих из поправок соответствующего порядка:

kravchuk17.wmf kravchuk18.wmf (4)

Здесь kravchuk19.wmf и Z0 – решения (1), когда все коэффициенты равны своим средним значениям:

kravchuk20.wmf (5)

Для нахождения поправок первого порядка kravchuk21.wmf и Z1 подставляем в (1):

kravchuk22.wmf kravchuk23.wmf kravchuk24.wmf

kravchuk25.wmf kravchuk26.wmf

kravchuk27.wmf

После раскрытия скобок получим

kravchuk28.wmf

Относительные изменения первых поправок порядка относительного изменения коэффициентов. Зачёркнутые же слагаемые имеют второй порядок малости и поэтому должны быть отброшены [4]. Обозначим

kravchuk29.wmf

kravchuk30.wmf

– решение в первом приближении теории возмущений. Тогда последняя система неравенств перепишется в виде

kravchuk31.wmf (6)

У систем (5) и (6) одинаковые и постоянные коэффициенты при неизвестных. Отличаются только свободные члены. Поэтому обе системы решаются одинаково просто методом исключения [2, 3].

Для нахождения решения во втором приближении

kravchuk32.wmf

kravchuk33.wmf

подставляем эти суммы вместо xi и Z в (1). После отбрасывания слагаемых третьего порядка малости получим

kravchuk34.wmf (7)

Результаты (6), (7) нетрудно обобщить на любой порядок приближения р = 1, 2, …:

kravchuk35.wmf (8)

Следует только иметь в виду, что при достаточно больших р асимптотические ряды начинают расходиться [5]. Критерием возможности увеличения р может, например, служить среднее отклонение kravchuk36.wmf от kravchuk37.wmf:

kravchuk38.wmf (9)

Если ∆p начинает увеличиваться, итерационный процесс следует закончить. Тогда максимальная достигнутая точность оценивается относительной погрешностью

kravchuk39.wmf (10)

для последнего р.

В векторной форме система (8) кратко выглядит так:

kravchuk40.wmf

Средние значения kravchuk41.wmf и kravchuk42.wmf можно также найти путём усреднения системы (8) с учётом (2) и (3):

kravchuk43.wmf

В частности, при р = 1

kravchuk44.wmf

Эта система в точности совпадает с (5). Поэтому

kravchuk45.wmf

kravchuk46.wmf

т.е. средние значения первого приближения совпадают с нулевым приближением.

При рассмотрении задачи на максимум Z следует во всех вышеприведённых неравенствах, содержащих Z, поменять знак неравенства с «≤» на «≥».

Пример

В работе [1] было найдено точное решение задачи:

kravchuk47.wmf

с коэффициентами:

kravchuk48.wmf (11)

Решение таково:

kravchuk49.wmf kravchuk50.wmf x2 = 0. (12)

Усредняя (11) по формуле (2), находим

kravchuk51.wmf kravchuk52.wmf kravchuk53.wmf kravchuk54.wmf kravchuk55.wmf kravchuk56.wmf kravchuk57.wmf kravchuk58.wmf (13)

kravchuk63.wmf kravchuk64.wmf

1.wmf

kravchuk65.wmf

kravchuk66.wmf

pic_99.wmf

1.wmf

kravchuk68.wmf

kravchuk69.wmf

pic_100.wmf

kravchuk71.wmf

kravchuk72.wmf

Решение в нулевом приближении [1]:

kravchuk59.wmf kravchuk60.wmf kravchuk61.wmf (14)

Найдём решение в первом приближении. Для этого подставим в (6) значения (11), (13) и (14). Получаем систему неравенств:

kravchuk62.wmf

где обозначено τ = t – 0,5, τ ∈ [–0,5; 0,5].

Решаем её табличным способом [1]:

Таким образом,

kravchuk73.wmf

kravchuk74.wmf kravchuk75.wmf (15)

Подставляя затем (11), (13), (15) в (7), находим решение во втором приближении:

kravchuk76.wmf

kravchuk77.wmf

kravchuk78.wmf (16)

Сравним значения Zmin, рассчитанные по (12), (15), (16):

kravchuk79.wmf kravchuk80.wmf

kravchuk81.wmf kravchuk82.wmf

kravchuk83.wmf kravchuk84.wmf

Их средние значения находим, усредняя (12), (15), (16) по формуле (2):

kravchuk85.wmf

kravchuk86.wmf kravchuk87.wmf

Оценим погрешности приближений (9), (10):

kravchuk88.wmf

kravchuk89.wmf

kravchuk90.wmf

kravchuk91.wmf

Отсюда видно, что если коэффициенты (11) при t ∈ [0;1] изменяются в пределах ±10 % по отношению к их средним значениям (13), то относительная погрешность конечного результата в первом приближении имеет тот же порядок малости. Во втором же приближении относительная погрешность результата порядка квадрата погрешности первого приближения, т.е. существенно меньше. Это согласуется с многочисленными другими задачами [4, 5].

Рецензенты:

Петров Л.Ф., д.т.н., профессор кафед_ры «Математические методы в экономике», ФГБОУ ВПО «РЭУ имени Г.В. Плеханова», г. Москва;

Титов В.А., д.э.н., профессор кафедры информационных технологий, ФГБОУ ВПО «РЭУ имени Г.В. Плеханова», г. Москва.


Библиографическая ссылка

Кравчук С.П., Кравчук И.С., Татарников О.В., Швед Е.В. МЕТОД ВОЗМУЩЕНИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПАРАМЕТРОМ // Фундаментальные исследования. – 2015. – № 5-2. – С. 299-303;
URL: http://www.fundamental-research.ru/ru/article/view?id=38211 (дата обращения: 18.11.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074