В работах [2, 3] предложен простой метод решения задач линейного программирования, основанный на последовательном исключении переменных в системе линейных неравенств. Важным преимуществом этого метода перед симплексным является возможность решения задач с параметрами, т.е. получение окончательного результата в виде функции от этих параметров. В данной работе рассматривается однопараметрическая задача линейного программирования с двумя неотрицательными переменными, в которой часть коэффициентов (или все) зависят от одного общего параметра. Экстремум целевой функции и опорное решение станут аналитически зависеть от этого параметра.
Найдём методом неравенств [2] решение следующей задачи:
Z = x1 + 3x2 → min;
(1)
Её легко решить графоаналитическим способом [4, 5]:
Рис. 1
Как видно из рис. 1, Zmin = 1 при x1 = 1, x2 = 0.
Это решение является частным для более общей задачи с переменными коэффициентами:
Z = (1 + C1)x1 + (3 + C2)x2 → min;
(2)
Здесь буквенные величины задают отклонения от значений коэффициентов задачи (1). Условиям (2) соответствует система неравенств
(3)
Начало таблицы решений выглядит так:
Таблица 1
|
x1 |
x2 |
|||||
|
∇ |
||||||
|
|
|
|
|
|||
|
∇ |
||||||
|
|
|
|||||
Для дальнейшего решения требуется задать конкретный вид отклонений коэффициентов (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. Если, например, положить
(4)
то
Zmin(t) = 0,2t + 0,9;
x1 = 0,2t + 0,9; x2 = 0. (5)
Таблица 2
|
x1 |
|||
|
∇ |
|||
|
|
|
|
|
|
|
|
|
|
При этом
Zmin ∈[0,9; 1,1]; Zcp = Zmin(1/2) = 1;
x1 ∈[0,9; 1,1];
Случай переменных коэффициентов целевой функции и свободных членов
Пусть a11 = a12 = a21 = a22 = 0; |C1| ≤ 0,1; |C2| ≤ 0,3; |b1| ≤ 0,4; |b2| ≤ 0,2. Тогда табл. 1 станет выглядеть так:
Таблица 3
|
x1 |
||
|
∇ |
||
|
|
|
|
|
|
|
|
При рассматриваемой малости отклонений решение последней системы таково:
x1 = 1 + 0,5b2; x2 = 0.
Если принять
(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];
Случай всех переменных коэффициентов
Теперь в дополнение к (4), (6) примем
(8)
так, что |a11| ≤ 0,1; |a12| ≤ 0,1; |a21| ≤ 0,2; |a22| ≤ 0,1.
Тогда из табл. 1, как и из табл. 2 и 3, можно найти
(9)
При этом
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 может быть немалым.
Рис. 2
Существует способ решения параметрических задач линейного программирования на основе симплекс-метода [1]. Однако этот способ непрост и довольно трудоёмок. В результате есть риск получить ошибочное решение. В качестве примера рассмотрим следующую задачу из [1].
Z = –x1 + 2x2 – 3x3 – x4 > MAX;
(10)
Согласно [1],
(11)
При остальных ? Zmax не существует.
Решим (10) методом неравенств. Составляя таблицу, подобную табл. 1, и исключая все переменные, в итоге получим систему из 23-х неравенств вида
(12)
Для нахождения Zmax(μ) построим графики всех прямых, отвечающих правым частям неравенств для Z. Затем выберем среди них прямые с наименьшими ординатами. Они и составят график Zmax(μ) на рис. 3.
Этому графику соответствуют первые 5 неравенств (12):
(13)
Рис. 3
На рис. 3 штрих-пунктиром нанесено и решение (11). Как видно, (11) и (13) отличаются при μ < 0, что свидетельствует о том, что решение, приведенное в [1], ошибочно.
Сравнение представленных методов решения задачи (10) позволяет сделать вывод, что метод неравенств является более простым и надежным по сравнению с симплекс-методом.
Рецензенты:
Титов В.А., д.э.н., профессор кафедры информационных технологий, ФГБОУ ВПО «Российский экономический университет имени Г.В. Плеханова», г. Москва;
Туганбаев А.А., д.ф.-м.н., профессор кафедры высшей математики, ФГБОУ ВПО «Национальный исследовательский университет «МЭИ», г. Москва.
Работа поступила в редакцию 23.09.2014.