Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,087

INEQUALITIES METHOD IN THE LINEAR PROGRAMMING PROBLEM WITH A PARAMETER

Kravchuk S.P. 1 Kravchuk I.S. 2 Tatarnikov O.V. 1 Shved E.V. 1
1 Plekhanov Russian University of Economics. Moscow
2 Moscow State University of Railway Transport
При анализе инженерных и экономических проблем, которые сводятся к задачам линейного программирования, зачастую необходимо проводить исследование математической модели на чувствительность к изменению в определенном интервале коэффициентов задачи. Такое изменение коэффициентов может быть представлено в виде их зависимости от некоторого параметра. При использовании симплекс-метода подобный анализ является трудоемким процессом, поскольку требует нахождения оптимальных решений для каждого набора значений изменяемых коэффициентов. В данной работе предлагается метод решения задачи линейного программирования с зависящими от параметра коэффициентами, сводимой к решению системы неравенств одного знака, которая в свою очередь сводится к одному неравенству. Этот метод позволяет получить оптимальное решение в виде функции от параметра, определяющего возможные изменения коэффициентов задачи.
In the analysis of engineering and economic problems which can be transformed to problems of linear programming often it is necessary to carry out research of mathematical model sensitivity to variation in a certain interval of coefficients of a task. The coefficients variation can be presented in the form of their dependence on some parameter. When using a simplex method this analysis is being a labor-intensive process as demands receiving of optimal solutions for each set of variable coefficients. In this paper the method of the solution of a problem of linear programming with the variable coefficients which is reduced to the problem of system of the same sign inequalities which is in turn reduced to one inequality is proposed. This method allows receiving the optimal solution in the form of function of the parameter defining variation of task coefficients.
inequality
linear programming
the simplex method
Gauss-Jordan method
the objective function
extremum
matrix
1. Holstein E.G., Yudin D.B. New directions in linear programming. Moscow: Soviet Radio, 1966.
2. Kravchuk S.P., Kravchuk I.S., Swed E.V. Extremum in the system of linear inequalities with two variables. St. Petersburg.: Modern aspects of the economy, no. 6 (154), 2010.
3. Kravchuk S.P., Kravchuk I.S., Tatarnikov O.V., Swed E.V. Inequalities method in the linear programming problem. M.: Fundamental research, no. 3, pp. 1, 2014.
4. General course of higher mathematics for economists. Textbook ed. prof. V.I. Ermakov. Moscow: INFRA-M, 2000.
5. Yudin D.B., Goldstein E.G. Linear programming. Moscow: Fizmatgiz, 1963.

В работах [2, 3] предложен простой метод решения задач линейного программирования, основанный на последовательном исключении переменных в системе линейных неравенств. Важным преимуществом этого метода перед симплексным является возможность решения задач с параметрами, т.е. получение окончательного результата в виде функции от этих параметров. В данной работе рассматривается однопараметрическая задача линейного программирования с двумя неотрицательными переменными, в которой часть коэффициентов (или все) зависят от одного общего параметра. Экстремум целевой функции и опорное решение станут аналитически зависеть от этого параметра.

Найдём методом неравенств [2] решение следующей задачи:

Z = x1 + 3x2 → min;

kravzuk01.wmf (1)

Её легко решить графоаналитическим способом [4, 5]:

pic_48.wmf

Рис. 1

Как видно из рис. 1, Zmin = 1 при x1 = 1, x2 = 0.

Это решение является частным для более общей задачи с переменными коэффициентами:

Z = (1 + C1)x1 + (3 + C2)x2 → min;

kravzuk02.wmf (2)

Здесь буквенные величины задают отклонения от значений коэффициентов задачи (1). Условиям (2) соответствует система неравенств

kravzuk03.wmf (3)

Начало таблицы решений выглядит так:

Таблица 1

x1

x2

         
 

         

kravzuk06.wmf

kravzuk06.wmf

kravzuk07.wmf

 

           

kravzuk09.wmf

kravzuk10.wmf

Для дальнейшего решения требуется задать конкретный вид отклонений коэффициентов (3). Пусть параметр t меняется в пределах от 0 до 1:t ∈[0; 1].

Чтобы отклонения коэффициентов по абсолютной величине были невелики, будем отсчитывать их от среднего значения параметра t = 1/2. Все отклонения предполагаются линейными функциями, пропорциональными t – 1/2. Коэффициенты пропорциональности выберем, например, такими, чтобы максимальные отклонения не превышали 10 % от значений коэффициентов (2).

Отметим, что допущение малой изменчивости коэффициентов рассматриваемой задачи делается только с целью сохранения их знака при этих t, что сокращает трудоёмкость решения задачи. При произвольных законах изменения коэффициентов aik(t) и Cj(t) следует весь промежуток изменения параметра t разбить на ряд интервалов, в пределах которых знак этих коэффициентов остаётся неизменным. Это позволит правильно выбирать складываемые неравенства. В итоге процесс решения по сути не изменится, а только удлинится, т.к. придётся искать Zmax(t) на каждом из данных интервалов.

Случай переменных свободных членов

Проще всего задача (2) решается, когда C1 = C2 = 0; a11 = a12 = a21 = a22 = 0. Тогда табл. 1 принимает вид табл. 2.

Если предположить, что |b1| ≤ 0,4 и |b2| ≤ 0,2, то решением полученной системы неравенств будет Zmin = 1 + 0,5b2. При этом x1 = 1 + 0,5b2; x2 = 0. Если, например, положить

kravzuk18.wmf (4)

то

Zmin(t) = 0,2t + 0,9;

x1 = 0,2t + 0,9; x2 = 0. (5)

Таблица 2

x1

     

     

kravzuk12.wmf

kravzuk13.wmf

2.wmf

kravzuk15.wmf

kravzuk16.wmf

kravzuk17.wmf

При этом

Zmin ∈[0,9; 1,1]; Zcp = Zmin(1/2) = 1;

x1 ∈[0,9; 1,1];

kravzuk19.wmf

Случай переменных коэффициентов целевой функции и свободных членов

Пусть a11 = a12 = a21 = a22 = 0; |C1| ≤ 0,1; |C2| ≤ 0,3; |b1| ≤ 0,4; |b2| ≤ 0,2. Тогда табл. 1 станет выглядеть так:

Таблица 3

x1

   

   

kravzuk21.wmf

kravzuk22.wmf

 

kravzuk24.wmf

kravzuk25.wmf

При рассматриваемой малости отклонений решение последней системы таково:

kravzuk26.wmf

x1 = 1 + 0,5b2; x2 = 0.

Если принять

kravzuk27.wmf (6)

а b1 и b2 взять из (4), то

Zmin(t) = (0,2t + 0,9)2;

x1 = 0,2t + 0,9; x2 = 0. (7)

При этом

Zmin ∈[0,81; 1,21]; Zcp = Zmin(1/2) = 1;

x1 ∈[0,9; 1,1];

kravzuk28.wmf

Случай всех переменных коэффициентов

Теперь в дополнение к (4), (6) примем

kravzuk29.wmf

kravzuk30.wmf (8)

так, что |a11| ≤ 0,1; |a12| ≤ 0,1; |a21| ≤ 0,2; |a22| ≤ 0,1.

Тогда из табл. 1, как и из табл. 2 и 3, можно найти

kravzuk31.wmf (9)

kravzuk32.wmf

При этом

Zmin ∈[0,74; 1,34]; Zmin(1/2) = 1;

x1 ∈[0,82; 1,22]; x1(1/2) = 1.

Результаты (5), (6), (9) показывают, что не все переменные коэффициенты влияют на Zmin(t), x1(t), x2(t).

Для наглядности изобразим графики функций Zmin(t).

Из рис. 2 видно, что даже при небольших отклонениях коэффициентов задачи от их средних значений отклонение Zmin от среднего значения Zcp = 1 может быть немалым.

pic_51.wmf

Рис. 2

Существует способ решения параметрических задач линейного программирования на основе симплекс-метода [1]. Однако этот способ непрост и довольно трудоёмок. В результате есть риск получить ошибочное решение. В качестве примера рассмотрим следующую задачу из [1].

Z = –x1 + 2x2 – 3x3 – x4 > MAX;

kravzuk33.wmf (10)

Согласно [1],

kravzuk34.wmf (11)

При остальных ? Zmax не существует.

Решим (10) методом неравенств. Составляя таблицу, подобную табл. 1, и исключая все переменные, в итоге получим систему из 23-х неравенств вида

kravzuk35.wmf (12)

Для нахождения Zmax(μ) построим графики всех прямых, отвечающих правым частям неравенств для Z. Затем выберем среди них прямые с наименьшими ординатами. Они и составят график Zmax(μ) на рис. 3.

Этому графику соответствуют первые 5 неравенств (12):

kravzuk36.wmf (13)

pic_52.wmf

Рис. 3

На рис. 3 штрих-пунктиром нанесено и решение (11). Как видно, (11) и (13) отличаются при μ < 0, что свидетельствует о том, что решение, приведенное в [1], ошибочно.

Сравнение представленных методов решения задачи (10) позволяет сделать вывод, что метод неравенств является более простым и надежным по сравнению с симплекс-методом.

Рецензенты:

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

Туганбаев А.А., д.ф.-м.н., профессор кафедры высшей математики, ФГБОУ ВПО «Национальный исследовательский университет «МЭИ», г. Москва.

Работа поступила в редакцию 23.09.2014.