3. Математическое моделирование

Поскольку задача имеет вид таблицы, будем использовать два индекса для переменных:

j – вид ремонта;

i – тип базы.

Для данной задачи управляемыми переменными являются x_ij – количество ремонтов j-го вида, производящихся на i-й базе. При изменении значений управляемых переменных мы получаем новые планы размещения различных видов ремонтов локомотивов по ремонтным базам.

В задаче также присутствуют неуправляемые переменные:

C_ij – стоимость проведения j-го ремонта на i-й базе;

K_ij - до­пустимая загрузка базы в течение месяца по каждому из видов ремонта;

B_j - cредняя месячная потребность в выполнении ремонтов j-го вида.

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

Таким образом, построим математическую модель задачи с учетом вышеизложенного:

(1)

(2)

(3)

Кроме того, добавим ограничения на тип переменных. Управляемые переменные x_ij являются целыми величинами:

x_ij N .

В конечном итоге имеем целочисленные управляемые переменные, линейные ограничения. Значит, данная задача относится к задачам линейного целочисленного программирования.

4. Обоснование и выбор метода решения

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

Для задач дискретного программирования существую специальные методы решения. Самыми распространенными из них являются метод отсечений Гомори и метод «ветвей и границ», которые используют в качестве подалгоритма симплекс-метод решения задач ЛП.

Метод отсечений на начальном этапе отбрасывает требование целочисленности, и решается задача ЛП. Если решение получается целым, то оно является оптимальным. Иначе применяют условие правильного отсечения. Для этого формируют новое ограничение, которое отсекает только что полученное оптимальное «непрерывное» решение, оставляя допустимыми все целочисленные решения.

Метод «ветвей и границ»  наиболее широко применяемый метод дискретного программирования. Он относится к комбинаторным методам, т.е. заключается в последовательном анализе вариантов.

МВГ состоит из двух процедур:

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

2. установление границ возможного для каждого анализируемого подмножества решений. На этом этапе выбирается оценка для заданного подмножества, т.е. такое значение ЦФ, которое не может быть улучшено ни на одном из вариантов оцениваемого подмножества. Оценка должна быть как можно более точной (близкой к истинным значениям).

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

Задача ЛЦП имеет следующую математическую модель:

На начальном этапе, согласно МВГ, отбрасывается ограничение (3). Если полученное решение автоматически удовлетворяет условию целочисленности, то оно является оптимальным. Иначе рассматривают нецелочисленную переменную x_l=d_l полученного решения и по ней производят ветвление, все множество разбивают на два и кроме ограничений (2) добавляются:

Снова решаем задачу на каждом подмножестве. Если оба решения не удовлетворяют условию (3), выбираем среди них перспективное. Оценки сравнивают со всеми еще не разбитыми подмножествами. Как только на каком-нибудь подмножестве получено целочисленное решение, проверяем условие оптимальности. Если оно выполняется, получено оптимальное решение. В противном случае алгоритм повторяется.