Модели линейного программирования в решениях задач управления транспортными процессами

3.1. Общая задача линейного программирования

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

Линейное программирование включает в себя целый ряд эвристических (приближенных) методов решения, позволяющих при заданных условиях из всех возможных вариантов решений производственных задач выбрать наилучший, оптимальный. К этим методам относятся следующие – графический, симплексный, метод потенциалов (модифицированный распределительный метод – МОДИ), Хичкова, Креко, метод аппроксимации Фогеля и другие.

Часть этих методов объединяют общим названием - распределительный, или транспортный, метод.

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

На автомобильном транспорте методы линейного программирования используются с 1960-х годов для решения большого числа важнейших производственных задач, а именно: сокращение дальности перевозок грузов; составление оптимальной схемы перевозок; выбор кратчайших маршрутов движения; задачи перевозки разных, но взаимозаменяемых грузов; сменно-суточное планирование; планирование перевозок мелкопартионных грузов; распределение автобусов по маршрутам и другие.

Особенности модели линейного программирования заключаются в следующем:

- целевая функция и ограничения выражены линейными зависимостями (равенствами или неравенствами);

- число зависимостей всегда меньше числа неизвестных (условие неопределенности);

-неотрицательность искомых переменных. Общая форма записи модели линейного программирования в сокращенном виде выглядит следующим образом:

- найти х _ij ≥ 0 (j = 1, 2…n) при ограничениях следующего типа:

.

Эти ограничения минимизируют (или максимизируют) целевую функцию

min (max).

Стандартной формой записи модели линейного программирования является система линейных уравнений, записанная в канонической форме, т. е. в форме линейных равенств, в неотрицательных числах:

а₁₁х₁ + а₁₂х₂ + …+ а_1nх_n = b₁;

а₂₁х₁ + а₂₂х₂ + … + а_2nх_n = b₂; (3.1)

……………………………..

a_mх₁ + а_m2х₂ + …+ а_mnх_n = b_m..

Если модель записана в форме неравенств в неотрицательных числах, т. е. имеет вид

а₁₁х₁ + а₁₂х₂ + …+ а_1nх_n ≤ b₁;

а₂₁х₁ + а₂₂х₂ + … + а_2nх_n ≤ b₂; (3.2)

……………………………..

a_mх₁ + а_m2х₂ + …+ а_mnх_n ≤ b_m,..

то эта запись приводится к канонической форме (3.1) путем введения дополнительных переменных х_n+1 > 0 (i =1,2… m) в левую часть неравенства (или сокращения числа переменных, если знак неравенства направлен в другую сторону). Дополнительные переменные составляют базис.

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

L = с₁ х₁ + с₂ х₂…с_n х_n → min, (3.3)

где с₁, с₂… с_n – коэффициенты целевой функции L при переменных х _j.

В целевую функцию дополнительные переменные входят с нулевыми коэффициентами.

В случае максимизации целевой функции L следует знаки при переменных целевой функции изменить на противоположные, и мы вновь придем к задаче минимизации, т.е. одна задача сводится к другой заменой L на – L или max L = min (– L).

Базисным решением системы линейных уравнений (3.1) называется решение, в котором небазисным переменным даны нулевые значения.

Допустимым называется такое базисное решение, в котором вошедшие в базис переменные являются неотрицательными.

Оптимальным называется допустимое решение, максимизирующее (или минимизирующее) целевую функцию (3.3).

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

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

Понятие двойственности широко используется в анализе задач линейного программирования. Свойство двойственности детально рассматривается в каждом конкретном случае.

3.2. Графоаналитический метод

Графоаналитический метод – это один из простейших методов линейного программирования. Он наглядно раскрывает сущность линейного программирования, его геометрическую интерпретацию. Его недостаток в том, что он позволяет решать задачи с 2 или 3 неизвестными, т. е. применим для узкого круга задач. Метод основан на правилах аналитической геометрии.

Решение задачи с двумя переменными х₁ и х₂, которые по смыслу задачи не должны быть отрицательными, выполняется в системе декартовых координат. Уравнения х₁ =0 и х₂ = 0 являются осями системы координат первого квадранта

(рис. 3.1).

Метод решения рассмотрим на конкретном примере.

Пример 3.1. На складе имеются 300 т изделий из пенобетона и 200 т из стали. Автопредприятию необходимо доставить эти изделия на строящийся объект. На автопредприятии имеются грузовые автомобили КамАЗ - 5320 и

ЗИЛ-4314. За одну поездку КамАЗ-5320 может доставить 6 т пенобетона и 2 т стали, а прибыль от ездки составит 4 тыс. руб. ЗИЛ-4314 за одну поездку доставляет 2 т пенобетона и 4 т стали, прибыль от ездки составляет 6 тыс. руб. Необходимо организовать перевозку так, чтобы обеспечить автопредприятию наибольшую прибыль.

Построим математическую модель задачи. Обозначим через х₁ искомое количество ездок КамАЗ-5320 и через х ₂ искомое количество ездок ЗИЛ-4314.

Общая перевозка в т изделий из пенобетона составляет 6 х₁ + 2 х₂, а из стали 2 х₁ + 4 х₂. Ограничения по перевозке, исходя из имеющегося количества изделий, составляют 6 х₁ + 2 х₂ ≤ 300т по пенобетону и 2 х₁ + 4 х₂ ≤ 200т по стали.

Суммарная прибыль в тыс. руб. выражается величиной 4 х ₁ + 6 х ₂, которую нужно максимизировать и которая является критерием оптимальности в рассматриваемой задаче. Математическая модель задачи, таким образом, выглядит следующей. Необходимо максимизировать целевую функцию

L = 4 х₁ + 6 х₂ → mах при условиях: 6 х₁ + 2 х₂ ≤ 300; 2 х₁ + 4 х₂ ≤ 200; х₁≥ 0; х₂≥ 0.

Рассмотрим уравнение 6 х₁ + 2 х₂ = 300. Чтобы построить прямую, описываемую этим уравнением, найдем две точки, лежащие на этой прямой. При х₁ = 0 из уравнения прямой найдем 2 х₂ = 300, откуда х₂ = 150. Следовательно, точка А с координатами (0,150) лежит на искомой прямой. При х₂ = 0 имеем 6 х₁ = 300, откуда х₁ = 50, а точка D с координатами (50,0) также находится на искомой прямой. Через эти две точки проводим прямую AD (рис. 3.1).

Линейное неравенство 6 х₁ + 2 х₂ ≤ 300 представляет собой полуплоскость, расположенную с одной из сторон от построенной прямой 6 х₁ + 2 х₂ = 300. Чтобы выяснить, с какой стороны от этой прямой расположены точки искомой полуплоскости, подставим в неравенство 6 х₁ + 2 х₂ ≤ 300 координаты какой-либо точки, не лежащей на граничной прямой. Например, начало координат 0-(0,0). Для него справедливо неравенство 6∙0 + 2∙0 = 0 < 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD и на рис. 3.1 заштрихована.

Уравнение 2 х₁ + 4 х₂ = 200 построим по двум точкам. При х₁= 0 4 х₂ = 200, откуда х₂ = 50. Тогда точка Е имеет координаты (0,50) и принадлежит искомой прямой. При х₂ = 0, 2 х₂ = 200, точка с находится на данной прямой с координатами (100,0). Подставив в неравенство координаты точки с (0,0), получим 2∙0 + 4∙0 = 0 < 200. Значит, начало координат находится в области допустимых значений от прямой 2 х₁ + 4 х₂ = 200.

Система ограничений задачи требует, чтобы планы (х₁; х₂) удовлетворяли всем четырем неравенствам, т. е. допустимые планы – точки (х₁; х₂) должны одновременно находиться во всех четырех полуплоскостях. Этому требованию отвечают только точки, расположенные внутри и на границе многоугольника OEKD, который и является многоугольником допустимых решений.

Вершинами многоугольника допустимых решений являются точки O, E, K, D, отрезки прямых OE, EK, KD, OD – его ребра. Любая точка многоугольника OEKD является планом задачи, удовлетворяя все ее условия. Вершины многоугольника образованы пересечением двух прямых и соответствуют опорным планам задачи, среди которых находится и наилучший (оптимальный) план. Таким образом, опорных планов будет столько, сколько вершин у многоугольника допустимых решений.

Наглядное геометрическое представление можно получить и для целевой функции L = 4 х₁ + 6 х₂. Зафиксируем какое-либо значение целевой функции, например L = 120. уравнение 4 х₁ + 6 х₂ = 120 определяет прямую, проходящую через точку В с координатами (х₁ = 0; х₂ = 20) и точку L с координатами ((х ₁ = 30; х ₂ = 0). Отрезок ВL лежит внутри многоугольника OEKD. Следовательно, для всех планов (точек) этого отрезка значение целевой функции одинаково и равно 120. Придавая другие значения целевой функции, получим параллельные прямые, которые называют линиями уровня целевой функции.

Перемещая прямую L параллельно самой себе в одном направлении, получим возрастание целевой функции, а в противоположном направлении – ее убывание. В рассматриваемом примере передвижение прямой ВL вправо определяет возрастание целевой функции, которую мы максимизируем. Так поступаем до тех пор, пока прямая ВL будет иметь хотя бы одну общую точку с многоугольником допустимых решений OEKD. Из рис. 3.1 следует, что последней точкой, которую пересечет прямая уровня целевой функции, будет точка К. Это значит, что точка К определяет оптимальный план задачи.

Направление возрастания, перпендикулярное к линии уровня, называется направлением наибольшего возрастания целевой функции и определяет ее максимальный прирост. Это направление можно установить без построения линий уровня. Для этого необходимо на осях х₁ и х₂ отложить отрезки, равные коэффициентам целевой функции, и по ним, как по координатам, построить вектор наибольшего возрастания целевой функции. В математике его называют градиентом и обозначают знаком grad. Градиентом для функции L = 4х₁ + 6х₂ будет вектор n | 4; 6 |. Для удобства его построения увеличим координаты, например, в 10 раз, т.е. n | 40; 60 |. Построим градиент целевой функции L, для чего соединим точку с координатами (40; 60) с началом координат. Линии уровня целевой функции строят перпендикулярно к направлению градиента.

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

6 х₁ + 2 х₂ = 300;

2 х₁ + 4 х₂ = 200.

Уравняем коэффициенты при х₁, умножив второе уравнение на 3, и вычтем из второго уравнения первое. Получим 10 х₂ = 300, х₂ = 30. Подставив значение х₂ = 30 в любое из уравнений, например в первое, определим значение х ₁:

6 х₁ + 2 х · 30 = 300,

откуда 6 х₁ = 300 – 60 = 240, следовательно, х₁ = 40.

Таким образом, чтобы получить наибольшую прибыль автопредприятию, необходимо выполнить 40 ездок на КамАЗ-5320 и 30 ездок на ЗИЛ-4314. Максимальная прибыль при этом составит

L = 4 х₁ + 6 х₂ = 4 · 40 + 6 · 30 = 340 тыс. руб.

На основе рассмотренного примера и геометрической интерпретации задачи оптимизации с двумя переменными можно сделать следующие выводы:

1) в двухмерном пространстве область допустимых решений представляет собой многоугольник;

2) каждой стороне многоугольника соответствует значение одной переменной, равной нулю;

3) каждой вершине многоугольника допустимых решений соответствуют значения двух переменных, равных нулю;

4) каждому значению целевой функции соответствует прямая;

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

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

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

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

На рис. 3.2,б изображены невыпуклые множества. В невыпуклых множествах можно указать хотя бы две точки отрезка АВ, не принадлежащие рассматриваемому множеству.

3.3. Симплексный метод

Симплексный метод – это распространенный метод решения задач линейного программирования. Свое название метод получил от слова «симплекс», обозначающего простейший выпуклый многоугольник, число вершин которого всегда на единицу больше, чем размерность пространства. Симплексный метод разработан в США математиком Дж. Данцигом в конце 1940-х годов.

Симплексный метод включает получение неотрицательного базисного решения системы канонических линейных уравнений типа (3.1), последующую минимизацию (максимизацию) целевой функции (3.3) и нахождение таким способом оптимальных значений искомых переменных х₁, х_2… х_n.

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

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

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

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

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

Пусть необходимо минимизировать линейную форму

L = с₁ х₁+ с₂ х₂ + … с_n х_n.

При условиях (для наглядности нулевые и единичные коэффициенты в уравнениях сохранены):

1 х₁ + 0 х₂ + … 0 х_m + a_1m+1x_m+1…+a_1n^x_n = b₁;

0 х₁+ 1 х₂ + … 0 х_m + a_2m+1x_m+1…+a_2n^x_n = b₂;

……………………………………………

0 х₁ + 0 х₂ + … 1х_m + a_mm+1x_m+1…+a_mnx_n = b_m.

В данной системе уравнений уже имеется готовый базис, поскольку каждое уравнение ограничений содержит неизвестную с коэффициентом, равным единице, которой нет в других уравнениях, т. е. из коэффициентов при переменных х ₁, х ₂…, х_m можно составить единичную матрицу.

Решим уравнения относительно базисных переменных:

х₁ = b₁ – (a_1m+1·х_m+1…+ a_1nx_n);

х₂ = b₂ – (a_2m+1·х_m+1…+ a_2nx_n);

………………………………

х_m = b_m – (a_mm+1x_m+1…+ a_mnx_n),

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

L=c₁b₁+c₂b₂+c_mb_m–(c₁a_1m+c₂a_2m+1+…+c_ma_mn+1)x_m+1-…-(c₁a_1n+c₂a_2n+…+c_ma_mn)x_n…+c_nx_n..

Переменные х₁, х₂…, х_m, с помощью которых найден первый базисный план, являются базисными, а остальные x_m+1, x_m+2,…x_n – свободными. Базисных переменных должно быть всегда столько, сколько уравнений в системе. Исходя из условия неотрицательности, наименьшее значение свободных переменных равно нулю. Полученное базисное решение системы уравнений и является ее первоначальным допустимым решением, т.е. x₁= b₁, x₂=b₂, … x_m=b_m, x_m+1= 0, …, x_n= 0.

Этому решению соответствует значение целевой функции

L = с₁ b₁+ с₂ b₂ + … с_m b_m.

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

Симплексные таблицы составляют следующим образом (см. табл. 3.1). Вверху таблицы помещают все переменные х ₁, х ₂…, х_n и коэффициенты c_{j ,} с которыми соответствующие переменные входят в целевую функцию. Первый столбец c_i состоит из коэффициента целевой функции при переменных, вошедших в базис. Затем следует столбец базисных переменных и свободных членов уравнений. Элементы остальных столбцов таблицы представляют собой коэффициенты при переменных, с которыми последние входят в систему уравнений. Таким образом, каждой строке таблицы соответствует уравнение системы, решенное относительно базисной переменной. В таблице показан и вариант плана, который соответствует целевой функции при данном базисе.

Нижняя строка таблицы называется индексной. Каждый ее элемент (оценка) ∆ _j определяют

∆ _j = z_j – c_j,

где c_j – коэффициенты при соответствующих переменных в целевой функции; z_j – сумма произведений коэффициентов целевой функции при базисных переменных на соответствующие переменные – элементы j –го столбца таблицы.

Таблица 3.1

Симплексная таблица с первоначальным допустимым