На станции необходимо выгрузить маршрут однородного груза из 150 вагонов

Сформулируем математически поставленную задачу. Обозначим число вагонов, предназначенных для выгрузки на грузовом фронте 1 – X1 , на грузовом фронте 2– X2 , на грузовом фронте 3 – X3 и на грузовом фронте 4 – X4. Тогда целевую функцию, выражающую общий доход станции от выгрузки вагонов, можно записать так:
C=13x1+115x2+145x3+89x4.(1.1)
Составим ограничения, которые накладываются на аргументы этой функции. Прежде всего, необходимо учесть, что сумма подданных вагонов не должна превышать их наличия:
x1+x2+x3+x4≤150(1.2)
Далее общее время на обработку грузовых фронтов не должно превышать ресурсов локомотиво-часов:
0,2x1+0,4x2+0,5x3+0,4x4≤22 (1.3)
Вместимость грузовых фронтов:
x1≤22;x2≤43; x3≤37; x4≤33(1.4)
По условию задачи необходимо определить неотрицательные значения аргументов, обращающих в максимум линейную функцию:
C=13x1+115x2+145x3+89x4→max,(1.5)
И связанных системой линейных ограничений:
150≥x1+x2+x3+x4 22≥0,2x1+0,4x2+0,5x3+0,4x4; 22≥x1; 43≥x2; 37≥x3; 33≥x4. (1.6)
Т.е. необходимо из всех возможных решений системы неравенств (1.6) выбрать такое, которое соответствует максимальному значению целевой функции (1.5). Неравенства можно привести к уравнению, введя дополнительные неизвестные. Обозначим через y1 – число не поданных под выгрузку вагонов, y2 – количество неиспользованных локомотиво-часов, y3, y4, y5, y6 – недоиспользование вместимости грузовых фронтов. Систему линейных неравенств (1.6) можно записать в виде системы линейных уравнений:
150=y1+x1+x2+x3+x4 22=y2+0,2x1+0,4x2+0,5x3+0,4x4; 22=y3+x1; 43=y4+x2; 37=y5+x3; 33=y6+x4. (1.7)
Так как число неизвестных (десять) больше числа уравнений (шесть), то данная система неопределенная с бесчисленным множеством решений. Все неизвестные произвольно подразделяют в базисные и свободные. Им придают произвольные значения и подставляют в систему, которая при этом из неопределенной превращается в определенную с единственным решением. Любому набору свободных значений, которые дадут бесчисленное множество решений системы (1.7). Если все свободные неизвестные приравнять нулю, то решение будет состоять только из значений базисных неизвестных. Такое решение называется базисным. Рассматривая в качестве свободных те или иные неизвестные, можно получить различные базисные решения, число которых определится числом сочетаний из n по m элементов Cnm, где n – общее число неизвестных, m – число базисных неизвестных.
Согласно теореме линейного программирования – среди базисных решений системы всегда можно найти оптимальное, а в некоторых случаях и несколько оптимальных решений, но все они обеспечат экстремум целевой функции.
Таким образом, если найти какой-либо базисный план, а затем улучшать его, то получится оптимальное решение. На этом принципе и построен симплекс-метод. В нашем случае удобно найти базисный план, приняв в качестве базисных пять неизвестных (по числу уравнений) – y1, y2, y3, y4, y5, y6. Тогда свободными неизвестными будут x1, x2, x3, x4. Используя систему 1.7, выразим все базисные неизвестные через свободные:
y1=150-(x1+x2+x3+x4); y2=22-(0,2x1+0,4x2+0,5x3+0,4x4);y3=22-x1; y4=43-x2; y5=37-x3; y6=33-x4; (1.8)
Выразим целевую функцию в аналогичной форме:
C=0--13x1-115x2-145x3-89x4;(1.9)
Приравняв свободные неравенства к нулю, получим следующий базисный план: y1=150 (количество неподанных вагонов), y2=22 (неиспользованные ресурсы локомотиво-часов), y3=22, y4=43, y5=37, y6=33 (неиспользованная вместимость грузовых фронтов) . Назовем его начальным. Он соответствует ситуации, когда вагоны вообще не подают под выгрузку, а общий доход станции (значение целевой функции С) равен нулю. Поэтому начальный план необходимо улучшить, т.е. перейти к другому базисному плану. Базисные планы отличаются, друг от друга набором свободных и базисных неизвестных. Значит, если исключить какую-либо неизвестную из числа базисных и ввести ее в число свободных, а из числа свободных одну неизвестную ввести в число базисных, можно получить новый базисный план. Надо лишь найти такие неизвестные, при которых следующий базисный план будет лучше, чем предыдущий, т.е. увеличить значение целевой функции С.
В первую симплекс-таблицу (табл.1) вносят данные начального плана, т.е. записывают коэффициенты при свободных неизвестных в соответствующих столбцах и свободные члены системы (1.8) в последнем столбце, который обозначен единицей. Первая строка соответствует выражению y1, вторая – y2 и т.д. В последней строке С записывают коэффициенты при неизвестных целевой функции. Последняя клетка этой строки предназначена для записи значения целевой функции (ее свободного члена), которое в данном случае (при x1=x2=x3=x4=0) равно нулю.
Таблица 1
Начальный план
-x1
-x2
5391153873500
-x3
-x4
1
y1 1 449977143399881 1 -397510111898001 150
y2 0,2 0,4 0,5 0,4 22
y3 1 0 0 0 22
y4 0 1 0 0 43
4744713120900y5 0 0 31037711430001 0 37
y6 0 0 0 1 33
C -13 -115 -145 -89 0
Таким образом, каждая строка таблицы (такие таблицы носят название матриц) обозначается соответствующей базисной неизвестной и знаком целевой функции С, каждый столбец – свободной неизвестной со знаком минус и единицей (для свободных членов). Знак минус перед свободной неизвестной соответствует минусу, стоящему перед круглыми скобками в выражениях (1.8) и (1.9). Поскольку в базисном плане значения свободных неизвестных равны нулю, то все значения базисных неизвестных равны соответствующим членам. Так, в рассмотренном базисном плане (см.табл.1)
y1=150; y2=22; y3=22; y4=43; y5=37; y6=33.
Чтобы заменить переменные, надо сначала их выбрать, а затем поменять местами. В результате будет получена новая матрица с новым планом.
Алгоритм решения задачи:
I. Выбор разрешающего элемента
1. Столбец, содержащий наибольший по абсолютной величине отрицательный элемент С-строки, принимается в качестве разрешающего.
2. Рассматривают все положительные элементы разрешающего столбца (кроме элемента С-строки) и на них делят соответствующие свободные члены. На пересечении разрешающих строки и столбца находится разрешающий элемент. Если окажется два или более одинаковых наибольших по абсолютной величине отрицательных элемента С-строки, то в качестве разрешающего столбца выбирают тот, которому соответствует максимальное из двух минимальных отношений