Транспортная задача линейного программирования

Ряд задач оперативного управления сводятся к решению задачи оптимального закрепления потребителей за поставщиками, состоящей в определении наилучшего плана поставок однородных (взаимозаменяемых) ресурсов (грузов, автомобилей и т.п.) от m поставщиков A_i () к n потребителям B_j (). Такой план должен обеспечивать соблюдение ограничений по наличию и потребностям ресурсов, а также минимальные транспортные издержки. Вместо стоимости при поиске оптимальных решений могут приниматься за основу расстояния поставки, время на движение, условные расстояния и другие показатели. Наиболее часто применяются расстояния перевозки.

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

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

Если обозначить размер ресурса (вывоза) от поставщика A_i через X_Ai, требуемый размер поставки потребителю B_j через X_Bj, размер корреспонденции от i-го поставщика j-му получателю (потребителю) через X_ij и стоимость поставки единицы ресурса между ними через l_ij, то поставленная задача в математической форме примет вид:

; (3.1)

(3.2)

; (3.3)

X_ij ³ 0. (3.4)

В случае, если запасы у поставщиков равны общим потребностям получателей, то

. (3.5)

Поставленная таким образом задача (ограничения 3.1, 3.2, 3.4 и целевая функция 3.3) является сбалансированной моделью (условие 3.5) классической транспортной задачи линейного программирования, в результате решения которой по известным значениям X_Ai, X_Bj, l_ij находятся оптимальные значения корреспонденций X_ij.

Задача может быть поставлена с дополнительными условиями:

1) имеются ограничения на размер поставок от каждого i-го поставщика каждому j-му потребителю в объемах X_оij, ; ;

2) запрещена поставка ресурса от i-го поставщика j-му потребителю, т.е. должно быть обеспечено условие X_ij=0;

3) должна быть обеспечена поставка от i-го поставщика j-му потребителю в гарантированном объеме X_гij (X_гij ≤ X_Аi и X_гij ≤ X_Вj );

4) при несбалансированной задаче необходимо назначить по какому-то из пунктов корреспонденцию реального или фиктивного ресурса.

Для решения транспортная задача может быть представлена в виде распределительной таблицы (таблица 3.23).

Общий алгоритм решения несбалансированной задачи с учетом ограничений на размер корреспонденций представлен на рисунке 3.23.

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

1) рассчитываются суммарный объем наличия ресурса X_сА и суммарный объем потребности в ресурсе X_сВ

;

;

2) сравниваются объемы X_сА и X_сВ. Если они равны, то задача сбалансирована, иначе на пункт 3;

3) если X_сА > X_сВ, то вводится фиктивный потребитель (n=n+1) и если X_сА<X_сВ –фиктивный поставщик (m=m+1);

4) по фиктивному потребителю или поставщику назначается объем ресурса в размере abs(X_сА - X_сВ);

5) назначаются стоимости по фиктивному пункту равными постоянной величине, например l_ф= (для фиктивного потребителя l_in = l_ф , или для фиктивного поcтавщика l_mj =l_ф , ;

6) назначаются ограничения по фиктивному пункту, равными постоянной величине, например X_{oф ³}abs(XсА-XсВ) (для фиктивного потребителя X_oij = X_oф, j=n, или для поставщика X_oij = X_oф , i=m, ).

Для отыскания оптимального закрепления потребителей за поставщиками необходимо сделать в распределительной таблице первоначальное закрепление, т.е. получить произвольный план закрепления (опорный), удовлетворяющий ограничениям (3.1), (3.2), (3.4) и (3.5) при числе загруженных связей m+n-1 и отсутствии циклов (контуров). План, содержащий ровно m+n-1 загруженных связей без циклов, называется базисным.

1

Ввод исходных данных: число и

название пунктов, объемы запасов

и потребностей ресурса, стоимос-

ти возможных поставок на едини-

цу ресурса, ограничения на

размер корреспонденций 3

Введение фиктивного поставщика

(потребителя), объема ресурса по

2 Нет нему, условных стоимостей пос-

Наличие баланса? тавок и ограничений

Да

Составление первоначального ба-

зисного плана поставок ресурса

(с учетом стоимостей)

5 Да Нет 6 Имеются

План оптимален? ли ограничения на размер

корреспонденций?

Нет Да

7 8

Улучшение плана поcтавок Ввод в окончательное решение

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

по определенному правилу (где превышены), корректировка

ограничений и стоимостей

9 Размер поставок Да

превышает

ограничения?

Нет

11 10

Вывод результата решения: Формирование окончательного

название корреспондирующих решения: последнее

пунктов, размер и стоимость распределение и ранее

поставок ресурса включенные в него поставки

Рисунок 3.23 – Укрупненный алгоритм решения транспортной задачи линейного программирования

Цикл (контур) в распределительной таблице – это условная замкнутая ломаная линия, образованная прямыми отрезками, углы между которыми равны 90^о, а вершины углов лежат в загруженных связях. Контур может быть четырехугольным, шестиугольным, восьмиугольным и т.д. Если число загруженных связей более m+n-1, то среди них есть цикл. Примеры циклов приведены ниже (точками показаны загруженные связи):

Существует несколько методов получения опорного плана – метод северо-западного угла (диагональный) и ряд эффективных, дающих решение более близкое к оптимальному,– метод минимального элемента, метод абсолютного двойного предпочтения, метод Фогеля (наиболее эффективный) и др.

Таблица 3.3 – Распределительная таблица (общий вид)

Для получения первоначального базисного решения рассмотрим применение метода минимального элемента. В соответствии с этим методом распределение составляется по следующему алгоритму:

1) формируются дополнительные массивы стоимостей l'_ij (l'_ij = l _ij), объемов ресурса X'_Ai (X'_Ai=X_Ai) и X'_Bj (X'_Bj =X_Bj), ; ;

2) находится минимальная стоимость из всех связей

.

Если l_rw = ¥, то первоначальное базисное решение получено. Иначе на 3);

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

X_rw = min (X'_Ar,X'_Bw),

где X'_Ar – количество ресурса r-го поставщика с учетом ранее назначенных корреспонденций другим, кроме w-го, потребителям; X'_Bw – количество ресурса, требуемого w-му потребителю с учетом ранее назначенных корреспонденций от других, кроме r-го поставщика;

4) из сравниваемых величин X'_Ar и X'_Bw вычитается значение X_rw , в результате чего получаются измененные ограничения X'_Ar =X'_Ar - X_rw и X'_Bw =X'_Bw - X_rw ;

5) изменяется массив l'_ij по следующему правилу:

если X'_Bw=0, то l'_iw = ¥ (),

иначе (X'_Ar=0) l'_rj = ¥ ();

6) переход на пункт 2).

Пункт 5 алгоритма обеспечивает исключение из дальнейшего рассмотрения поставщика (если X'_Ar =0), либо получателя (если X'_Bw=0). Остаток объема ресурса X'_Ar или X'_Bw к дальнейшему распределению может иметь значение, равное нулю.

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

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

Наиболее широкое применение получил модифицированный метод (МОДИ). В распределительную таблицу вводят вспомогательные строку и столбец; в них вносят специальные показатели, называемые потенциалами. Распределительные методы основаны на следующем: если к стоимостям любой строки (столбца) распределительной таблицы прибавить (или отнять) одно и то же произвольное число, то оценка оптимальности относительно не изменится. Если, например, от стоимостей каждого i-го поставщика отнять число u_Ai , а от стоимостей каждого j-го потребителя – u_Bj, то относительной оценкой любой связи ij может служить оценочный параметр s_ij (вместо l _ij):

s_ij = l_ij - u_Ai- u_Bj. (3.6)

Принимая для загруженных связей s_ij = 0 и используя выражение (3.6), определяются потенциалы u_Ai и u_Bj по следующему правилу:

потенциал для одного пункта, например первого поставщика принимается равным нулю;

по расстояниям загруженных связей подбираются потенциалы для других поставщиков и потребителей таким образом, чтобы соблюдалось принятое условие l_ij - u_Ai- u_Bj = 0, т.е. стоимость для каждой загруженной связи должна быть равна сумме потенциалов по поставщику и потребителю.

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

Если значение оценочного параметра свободной связи будет меньше нуля (s_ij <0), то это значит, что перераспределение корреспонденций с загрузкой такой связи, называемой потенциальной, уменьшит значение целевой функции на величину abs(s_ijX_ij), X_ij – размер корреспонденции, которой будет загружена связь ij. Отсутствие связей со значением параметра s_ij <0 означает, что проверяемый план закрепления потребителей за поставщиками является оптимальным. Если для какой-то свободной связи значение s_ij равно нулю, то это означает, что можно получить другой план с тем же минимальным значением целевой функции.

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

При перераспределении загрузок по связям в распределительной таблице для наиболее потенциальной связи, как для загруженной, строится контур. Введение к m+n-1 загруженным связям еще одной образует ровно один определенный контур, присущий вводимой связи. После чего связи, соответствующие вершинам контура, нумеруются: номер 1 присваивается выбранной потенциальной связи, а дальнейшая нумерация ведется в порядке следования вершин по контуру (могут присваиваться связям контура положительные и отрицательные знаки).

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

1) выявляется связь с четным номером, которой соответствует наименьшее значение корреспонденции X_м ;

2) значение объема ресурса X_м вычитается от значений объемов корреспонденций всех связей с четными номерами вершин. Если среди связей с четными номерами вершин окажутся две (или более) с одинаковой минимальной корреспонденцией, то из плана исключается только одна из них, для связи с большим расстоянием поставки, а вместо остальных оставляют условную корреспонденцию с нулевым значением, чтобы не допустить вырождения;

3) для всех связей с нечетными номерами вершин (включая и потенциальную) к значениям объемов корреспонденций прибавляется величина X_м.

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

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

При решении транспортной задачи линейного программирования на основе существующего базисного решения возможны варианты, когда число загруженных связей в таблице меньше m+n-1 (случай вырождения) или больше m+n-1 (случай наличия циклов). В первом случае нельзя оценить оптимальность решения, так как невозможно определить потенциалы для некоторых поставщиков и (или) потребителей, во втором – потенциалы определяются неоднозначно.

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

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

1) строится один из возможных контуров;

2) нумеруются углы контура;

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

4) среди связей (с четными или нечетными номерами), для которых сумма стоимостей перевозок больше, выявляется связь с наименьшим значением размера корреспонденции X_м;

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

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

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

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

1) проверяется выполнение условия X_ij £X_oij для связей ij. Если условие выполняется для всех связей, то решение закончено (переход на блок 10 общего алгоритма), иначе переход на пункт 2;

2) для каждой связи ij, по которой имеет место условие X_ij > X_oij , последовательно должен быть реализован алгоритм:

2.1) в окончательное решение вводится корреспонденция X_ij = X_oij ;

2.2) корректируются соответствующие размеры наличия и потребности в ресурсе

X_{А j} =X_{А j} - X_ij ;

X_{Bj =} X_Bj - X_ij ;

2.3) корректируется соответствующая стоимость поставки l_ij путем замены на большое число, например ;

3) переход на блок 4 укрупненного алгоритма решения задачи.

Решение задачи с запрещением поставки ресурса от i-го поставщика j-му потребителю решается по общей схеме с предварительной заменой реальной стоимости l_ij на большое число, например . Тем самым обеспечивается X_ij =0.

Решение задачи с необходимостью обеспечения поставки от i-го поставщика j-му потребителю в гарантированном объеме X_гij производится следующим образом:

1) предварительно для каждой такой связи ij, по которой имеет место условие X_ij³X_гij:

1.1) в окончательное решение вводится корреспонденция X_ij=X_гij;

1.2) корректируются соответствующие размеры наличия и потребности в ресурсе

X_Аj=X_Аj-X_ij; X_Bj=X_Bj-X_ij;

2) решается задача с новыми условиями по общей схеме.

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

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

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

Пример. На предприятиях A_i пассажирского транспорта имеется следующее число X_Ai транспортных средств для работы на маршрутах: A₁ – X_A1 =10; A₂ – X_A2 =30; A₃ – X_A3 =40. Для работы на маршрутах B_j требуется следующее число транспортных средств: B₁ – X_B1 =10; B₂ – X_B2 =10; B₃ – X_B3 =20; B₄ – X_B4 =30. Имеются дополнительные условия:

1) заданы ограничения на размер корреспонденций для всех связей (кроме А₁В₃) – в размере 30 ед, для А₁В₃ – в размере 5 ед.;

2) транспортные средства 2-го предприятия необходимо использовать в полном объеме;

3) поставка транспортных средств 2-го предприятия на 2-й маршрут должна быть не менее 5 единиц;

4) поставка транспортных средств 1-го предприятия на 4-й маршрут запрещена.

Требуется оптимальным образом распределить транспортные средства по маршрутам перевозок. Расстояния между предприятиями и маршрутами (нулевые пробеги транспортных средств) приведены ниже в таблице 3.4.

Таблица 3.4 – Данные по нулевым пробегам транспортных средств

Поиск по сайту: