ТРАНСПОРТНАЯ ЗАДАЧА И МЕТОДЫ ЕЕ РЕШЕНИЯ

Транспортная задача является одной из важнейших частных задач линейного программирования. Ее сущность стоит в следующем. В пунк­тах А₁, А₂, ¼ А_n имеется однородный груз в объемах а_i единиц. Этот груз необходимо доставить в пункты потребления В₁, В₂, ¼ В_m в количестве b_j единиц. Известны расстояния (стоимость) перевозок с_ij между всеми пунктами отправления и получения груза. Задача заключается в построении такого плана перевозок, при котором потребность в грузе всех пунктов потребления будет удовлетворена, весь груз из пунктов отправления будет вывезен и при этом будет обеспечен минимум транспортной работы (стоимости перевозок), что соответствует достижению наименьшего среднего расстояния перевозок груза.

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

;                        (4.1)

,

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

Решение транспортной задачи методом Хичкока рассмотрим на типовой задаче, исходные данные которой представлены в табл. 4.1, которая называется матрицей распределительного метода.

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

Решение транспортной задачи условно сводится к выполнению четырех этапов.

1. Составление первого допустимого плана перевозок.

Существует несколько способов составления первого допустимого плана перевозок одним из которых является ²метод северо-западного угла².

Согласно данного метода, распределение груза по потребителям производится начиная с грузоотправителя А₁ и грузополучателя В₁, то есть начиная с клетки А₁В₁. Потребность в грузе потребителя В₁ удовлетворяется полностью грузоотправителем А₁. В клетку А₁В₁ записывается весь объем потребления грузополучателя В₁ – 200 т. Оставшийся в точке А₁ груз в количестве 200 т. будет вывозиться потребителю В₂. Но потребителю В₂ нужно завести не 200 т., а 400 т. груза. Недостающие 200 т. груза ввозятся от грузоотправителя А₂. Оставшиеся у грузоотправителя А₂ 400 т. груза вывозятся в пункт В₃. Рассуждая таким образом, распределяется весь груз по потребителям (закрепление потребителей за грузополучателями), что выразится в заполнении клеток А₁В₁, А₁В₂, А₂В₂, А₂В₃, А₃В₃, А₃В₄, которые называются загруженными. Количество загруженных клеток всегда должно равняться величине i+j-1 (i – количество поставщиков; j – количество потребителей).

Если количество загруженных клеток менее чем i+j-1 (вырождение в задачах линейного программирования), то недостающее количество клеток получается путем загрузки соответствующего количества свободных клеток нулями (нулевые загрузки). Клетка, в которой проставлена нулевая загрузка, считается загруженной.

Таблица 4.1

2. Нахождение специальных цифровых индексов (потенциалов).

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

3. Проверка оптимальности.

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

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

В рассматриваемой задаче на минимум первый допустимый план не является оптимальным, поскольку в клетках А₁В₄, А₂В₁, А₁В₃, А₃В₁ име­ются отрицательные потенциалы (табл. 2.2), что требует перераспределе­ния загрузки клеток таблицы.

Таблица 2.2

Грузообразующие пункты

Грузопоглощающие пункты

Итого по вывозу, т

Потенциалы Дата добавления: 2018-06-27; просмотров: 1056; Мы поможем в написании вашей работы! Поделиться с друзьями: ⇐ Предыдущая123 Мы поможем в написании ваших работ! . . © 2014-2024 — Студопедия.Нет — Информационный студенческий ресурс. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав (0.097)