Линейное программирование. При решении задач планирования и управления процессами перевозок на железнодорожном транспорте на основе компьютерной технологии особое место занимают методы

При решении задач планирования и управления процессами перевозок на железнодорожном транспорте на основе компьютерной технологии особое место занимают методы оптимизации. Процесс оптимизации предполагает выбор такого варианта, при котором достигается экстремальное значение критерия оптимизации, характеризующего качество управления.

Можно выделить целый класс задач оптимизации, когда при нахождении экстремума критерий оптимизации (целевая функция) и ограничения являются линейными функциями.

В таком случае задача нахождения экстремума носит специфическое название задачи линейного программирования (ЛП).

Различные задачи оптимального управления и планирования на железнодорожном транспорте можно свести к моделям ЛП.

ЛП позволяет изучать задачи нахождения оптимального (наилучшего) значения линейной целевой функции F при линейных ограничениях на параметры управления - переменные задачи.

Общей задачей ЛП (ОЗЛП) называется задача, состоящая в определении оптимального (max или min, одним словом - extr) значения F целевой функции: F = (1.1)

при условиях (ограничениях):

(1.2)

i =

, (1.3)

где a_ij, c_j, b_i - вещественные числа, символ- один из знаков отношений .

Следовательно, в ОЗЛП отыскивается extr целевой функции (1.1) на множестве решений системы равенств и неравенств (1.2) при условии неотрицательности некоторых переменных. Отметим, что требование неотрицательности (1.3) может быть наложено на все переменные (L={1,2,...,n}) или вообще отсутствовать (L=0).

Совокупность чисел X =(x₁, x₂,..., x_n), удовлетворяющую ограничениям (1.2), (1.3) называют допустимым решением или планом.

План X^*=(), при котором целевая функция принимает

экстремальное значение, называется оптимальным.

Таким образом, при любом плане X оптимальный план X^* удовлетворяет условию: F(X^*)F(X) или F(X^*)F(X).

Не всякая задача ЛП имеет оптимальный план. Это связано с тем, что множество решений D системы ограничений (1.2), (1.3) может быть пустым или форма F на D не ограничена сверху или снизу.

Например: 1. Для ОЗЛП найти max целевой функции F = x₁+ x₂ при ограничениях:

x₁+x₂3, .

x₁1,

x₂1.

Здесь D=0, поскольку ограничения противоречивы, оптимальный план отсутствует.

2. Для ОЗЛП найти min целевой функции F = x₁+ 2x₂ при ограничениях:

x₁+x₂2,

-x₁+x₂5,

x₂0.

При пара X₁= - C, X₂= 0 является планом, однако F не ограничена снизу, поэтому оптимальный план отсутствует.

Среди множества задач ЛП выделяют класс так называемых канонических, или основных задач, в которых находится min F целевой функции (1.1) при ограничениях (1.2), (1.3) где есть =.

Иными словами, в канонической задаче ЛП (КЗЛП) находится min F на множестве решений системы уравнений при неотрицательности всех параметров (переменных) задачи.

Несложными преобразованиями нахождение основных задач ЛП (ОЗЛП) всегда может быть сведено к решению некоторой КЗЛП.

Покажем, как это делается.

1. Прежде всего нахождение max F заменяется нахождением min F,

т.е. max F= - min (-F).

2. Всякое ограничение в задаче ЛП вида

i =1,m

заменяется условием - равенством с неотрицательностью новой вспомогательной переменной x_n₊_i, которую следует интерпретировать как остаток, или неиспользованную часть данного ресурса, если исходное ограничение определяет расход некоторого продукта.

(1.4)

i =1,m;

3. Ограничение вида , i =1,m необходимо преобразовать, так как левая часть этого ограничения не может быть меньше правой. Для обращения исходного неравенства в равенство вычтем из его левой части избыточную переменную x_n₊_i > 0. В результате имеем:

(1.5)

i =1,m

Замечание. 1. Правую часть равенства всегда можно сделать неотрицательной, умножая обе части на -1. Например, равенство

2x₁+ 3x₂-7x₃= -5 эквивалентно равенству -2x₁- 3x₂+7x₃= 5.

2. Знак неравенства изменится на противоположный при умножении обеих частей на -1. Например, можно вместо 2 < 4 записать -2 > -4, неравенство 2x₁- x₂ £ -5 заменить на -2x₁+ x₂ 5.

4. Переменные X_p, на которые не наложены условия неотрицательности, представляются в (1.1) и (1.2) в виде разности неотрицательных величин:

X_k=W_k - V_k,

W_k 0; V_k 0.

Важная особенность переменных W_kи V_k состоит в том, что при любом допустимом решении только одна из переменных может принимать положительное решение, т.е. если W_k>0, то X_k = 0, и наоборот. Это позволяет рассматривать W_kкак остаточную переменную, а X_k - как избыточную, причем лишь одна из этих переменных может принимать положительное значение.

После всех этих преобразований удобно опять переобозначить W_kна X_k, а другие вспомогательные неизвестные заменить на X_n+1, X_n+2,..., X_n+t, где t есть сумма количества неравенств в (1.2) и количества переменных без ограничений. Тогда мы получим следующую КЗЛП.

Найти новую линейную форму min F₁ (1.6)

при ограничениях:

(1.6**)

(1.6*)

, i= 1, m; j= 1, n+t

Заметим, что каждому плану X^* () (1.7)

задачи (1.1), (1.2), (1.3) можно поставить в соответствие некоторый план:

X^* ()(1.8)

задачи (1.6), (1.6*), (1.6**), где числа (j= 1, n+t) получаются по той же схеме, по которой реализовывался переход от ОЗЛП к КЗЛП. Имея план (1.8) для задачи (1.4), (1.5), (1.6) можем получить план (1.7) для (1.1), (1.2), (1.3), элементы которого равны соответствующим элементам (1.8) или их некоторым разностям. Последнее имеет место при наличии в ОЗЛП переменных без ограничений.

Нетрудно убедиться, что кроме полученного взаимно однозначного соответствия между планами ОЗЛП и КЗЛП значение целевой функции F на соответствующих планах одинаковы. Таким образом, оптимальному решению задачи (1.1), (1.2), (1.3) соответствует оптимальное решение (1.6), (1.6*), (1.6**). В этом смысле указанные задачи эквивалентны.

Пример 1.1. Записать в форме КЗЛП следующую ОЗЛП:

Найти max целевой функции F= 3x₁ – 2x₂– 5x₄+ x₅ при ограничениях

2x₁+ x₃- x₄+ x₅2,

x₁- x₃+ 2x₄+ x₅3,

2x₂+ x₃- x₄+ 2x₅6,

x₁+ x₄- 5x₆8.

Решение. В данной задаче требуется найти max F, а система ограничений содержит четыре неравенства. Следовательно, чтобы записать ее в форме КЗЛП нужно:

1. Вместо нахождения max F записать F₁ = -F.

2. Перейти от ограничений-неравенств к ограничениям-равенствам.

Так как число неравенств, входящих в систему ограничений нашей задачи, равно четырем, то этот переход может быть осуществлен введением четырех дополнительных неотрицательных переменных. При этом к левым частям каждого из неравенств вида “ ” соответствующая дополнительная переменная прибавляется, а из левых частей каждого из неравенств вида “” вычитается.

Следовательно, исходная задача может быть записана в форме КЗЛП таким образом:

- минимизировать функцию F= - 3X₁ + 2X₂+ 5X₄- X₅

2X₁+ X₃- X₄+ X₅+ X₆ = 2,

X₁- X₃+ 2X₄+ X₅+ X₇ = 3,

2X₂+ X₃- X₄+ 2X₅+X₈ = 6,

X₁+ X₄- 5X₆- X₉ = 8,

Пример 1.2. записать в форме КЗЛП следующую ОЗЛП. Найти max целевой функции F = X₁+ X₂- X₃ при ограничениях

2X₁ - X₂- X₃+ X₄6,

X₁+ 2X₂+ X₃- X₄8,

3X₁ - X₂+ 2X₃+ 2X₄10,

- X₁+ 3X₂+ 5X₃- 3X₄ = 15.

Решение. В данной задаче требуется найти max F, а система ограничений содержит три неравенства. Следовательно, чтобы записать ее в форме КЗЛП, нужно составить нахождение min F при ограничениях, полученных из исходной задачи добавлением к левым частям каждого из неравенств вида “ ” дополнительной неотрицательной переменной и вычитанием дополнительных переменных из левых частей каждого из ограничений-неравенств вида “” за исключением четвертого уравнения.

Следовательно, исходная задача может быть записана в КЗЛП так:

Найти min F=-X₁+ 2X₂ - X₃ + X₄

при условиях

2X₁ - X₂ - X₃+ X₄+ X₅ = 6,