Решение транспортной задачи графическим способом

Графический метод решения транспортной задачи

Анализ вычисления транспортной задачи путем итерационного улучшения плана перевозок от опорного решения. Особенность использования наименее затратной программы транспортирования. Сложность постройки графика при большом количестве условий ограничения.

Рубрика	Экономико-математическое моделирование
Вид	контрольная работа
Язык	русский
Дата добавления	04.04.2016
Размер файла	91,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Графический метод решения транспортной задачи

Многие из нас знакомы с транспортной задачей и основным методом ее решения, путем «Итерационного улучшения плана перевозок от опорного решения».

Этот метод позволяет путём последовательных операций найти оптимальное решение от опорного плана.

Недостатком же этого метода является его не наглядность — непонятность для неподготовленного персонала, которому будет представлен этот план оптимизации расходов.

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

Более полно и красочно описать оптимизацию производства поможет графический метод решения транспортной задачи.

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

Рассмотрим некоторую задачу:

На предприятии работают 2 пекарни(П) и 2 магазина(М). Магазины имеют склады с вместительностью 16 и 14 (что составляет их суточную реализацию), следовательно, им необходимо ежесуточно поставлять это количество продукции. Пекарни же в свою очередь могут выпекать продукцию со скоростями 20 и 10 У.Е. изделий за смену и хранить их на складе до перевозки. Судя по графу расстояний между П и М можно составить следующую транспортную матрицу, и занести ее в таблицу.

Источник

Решение транспортной задачи

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

• вычеркивания (метод двойного предпочтения);
• северо-западного угла;
• минимального элемента;
• аппроксимации Фогеля.

Опорное решение транспортной задачи

Приближенные методы решения транспортной задачи.
Метод вычеркивания (метод двойного предпочтения). Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждом столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным.
Метод «северо-западного угла» состоит в последовательном переборе строк и столбцов транспортной таблицы, начиная с левого столбца и верхней строки, и выписывании максимально возможных отгрузок в соответствующие ячейки таблицы так, чтобы не были превышены заявленные в задаче возможности поставщика или потребности потребителя. На цены доставки в этом методе не обращают внимание, поскольку предполагается дальнейшая оптимизация отгрузок.
Метод «минимального элемента». Отличаясь простотой данный метод все же эффективнее чем, к примеру, метод Северо-западного угла. Кроме того, метод минимального элемента понятен и логичен. Его суть в том, что в транспортной таблице сначала заполняются ячейки с наименьшими тарифами, а потом уже ячейки с большими тарифами. То есть мы выбираем перевозки с минимальной стоимостью доставки груза. Это очевидный и логичный ход. Правда он не всегда приводит к оптимальному плану.
Метод «аппроксимации Фогеля». При методе аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

Источник

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

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

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

I. Основные параметры, термины и обозначения

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

Все суда на одной карте в режиме онлайн

Зеленый цвет — пассажирские суда, желтые — грузовые, розовый — частные яхты, оранжевый — танкеры и др. Аналогичная картина наблюдается и для авиационных перевозок, перевозок по железной дороге или автотранспортом. Изображения получены в начальном периоде Пандемии короновируса, что привело к огромным пробкам в узостях мирового Океана (Панамский, Суэцкий и др. каналы). Танкеры отправили отстаиваться на рейде, экипажам судов на берег сойти не разрешалось. Это форс-мажорные обстоятельства, которые в теории должны рассматриваться и учитываться специальным образом, что пока к сожалению перевозчиков не сделано.

Все самолеты мира в режиме онлайн

В теории в тексте задачи Хичкока ничего не говорится о равенстве имеющегося общего запаса судов в портах отправления и общей потребности в судах в портах прибытия (назначения). Если такого равенства нет, то система ограничений несовместна. В случае равенства

транспортная задача называется «сбалансированной». Задачи, в которых условие баланса не задано, должны быть приведены к «сбалансированному» виду. Это можно выполнить использованием «фиктивных» перевозок. Рассматриваем два случая:

Поэтому ранг системы равен не n+m, а n+m – 1, т.е с mn неизвестными. Общее число опорных планов равно числу сочетаний из mn по n+m – 1.. Применение симплекс метода для решения задачи возможно, но требует большого объема вычислений уже при n и m ≈ 10 -15. Заметим также, что каждая неизвестная входит лишь в два уравнения системы (матрица коэффициентов системы ограничений имеет в каждой строке и каждом столбце только два ненулевых элемента). Более того, транспортная задача всегда имеет допустимое решение. Все сказанное вызвало потребность попытаться учесть специфику задачи и создать метод ее решения более простой, чем симплекс метод. Такие методы были найдены и получили названия метода потенциалов и распределительного метода. Это разновидности симплексного метода. Они удобно реализуются, если условие задачи представлено в виде таблиц.

ТАБЛИЦА 1 — Вид данных транспортной задачи линейного программирования

Метод содержит три последовательных этапа:

Формирование опорного плана;

Проверка опорного плана на оптимальность;

Переход к новому опорному плану, если предыдущий не оптимален.

Рисунок 1 — Структурно-логическая схема алгоритма метода потенциалов

II. Формирование опорного плана перевозок

Рассмотрим способ получения начального опорного плана транспортной задачи, названный способом северо-западного (С-З) угла. Способ заключается в заполнении ячеек таблицы m×n значениями переменной x_ij, таким образом, чтобы удовлетворялись условия задачи. При этом план решения Х[m, n] может быть и не оптимальным, но обязательно должен быть допустимым.

В этом способе формируют опорный план, двигаясь по таблице: сверху вниз по строкам и слева направо вдоль строки. Начинают с левого верхнего угла (ячейки), куда вписывают значение x₁₁ =min<a₁, b₁>.Первые строка и столбец из рассмотрения далее исключаются.

Затем, если a₁ > b₁, то определяется остаток (a₁ – b₁) продукта на первом пункте отправления и его запас реализуется на 2-м пункте назначения. Остаток потребностей 2-го пункта назначения удовлетворяется за счет 2-го пункта отправления, остатки которого направляются в 3-й пункт назначения и т.д. Ниже метод будет иллюстрирован числовым примером.

Пример 1. Построение опорного плана методом Северо-Западного угла

Заданы значения: m = 3, n = 4; a₁ = 60, a₂ = 80, a₃ =100, b₁ = 40,b₂ = 60, b₃ = 80, b₄ = 60. Слева в таблице приведены d_ij удельные стоимости перевозок; справа — В_ij стоимости совместно с предложениями a_i и потребностями b_{j .}

Требуется найти план Х [m,n] перевозок, удовлетворяющий условиям на целевую функцию Q и переменные х_ij задачи Q.

РЕШЕНИЕ Построить исходный опорный план способом северо-западного угла. Строим симплексную таблицу: Таблица 3. Опорный план задачи

В таблице способом северо-западного угла получен опорный план. Базисные переменные (их число = 6): x₁₁ = 40, x₁₂= 20, x₂₂= 40, x₂₃= 40, x₃₃= 40, x₃₄= 60. Свободные переменные: x₁₃= x₁₄= x₂₁= x₂₄= x₃₁= x₃₂= 0 (их число равно 6).

Ячейки таблицы, соответствующие базисным переменным, называют базисными, остальные – свободными. Далее в алгоритме будем следовать идее симплекс метода. Суммарная стоимость перевозок Q, соответствующая плану Х[m,n], получает представление

Q = d₁₁∙x₁₁ + d₁₂∙x₁₂ + d₂₂∙x₂₂ + d₂₃ ∙x₂₃+ d₃₃ ∙x₃₃+ d₃₄ ∙x₃₄ = = 5∙40 + 2∙20 + 10∙40 + 2∙40 + 8∙40 + 5∙60 = 200+40+400 + 80 + 320+ 300 = 1340 ед

Коэффициенты d_ij называются фиктивными или косвенными стоимостями; их выражают через косвенные величины α и β, d’_ij = α_i +β_j . Здесь параметры α_i и ( — β_j ), по аналогии с механикой называют потенциалами i-го пункта отправления и j-го пункта прибытия. Значения потенциалов определяется из системы линейных уравнений: α_i + β_j = d_ij

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

Решая далее систему уравнений для потенциалов, находим значения потенциалов строк и столбцов, все фиктивные стоимости d_ij и коэффициенты γ_ij. Если для всех свободных клеток γ_rs ≤ 0, то перевод в базис любой свободной переменной не уменьшит значения целевой функции и, следовательно, выбранный опорный план не является оптимальным. Если же некоторые γ_rs >0, то данный план можно улучшить путем перевода в базис свободной переменной, соответствующей max γ_rs, а также путем исключения из базиса, принадлежащей ему переменной, первой обращающейся в нуль. Переход к новому опорному плану и поиск оптимального плана рассмотрим на примере. Другой способ формирования опорного плана предложен Фогелем. Этот способ при первом чтении можно пропустить, так как дальше он в тексте не используется.

Пример 2. Способ аппроксимации Фогеля

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

Этапы алгоритма: 1. Вычисление разностей в каждой строке и в каждом столбце между наименьшей стоимостью и ближайшей к ней по величине. Разности по строкам записываются справа в столбце разностей, разности по столбцам – внизу в строке разностей. Например, для строк А₁ разность равна А₁В₂ – А₁В₃ = 38 – 24 = 14 и т. д.

ТАБЛИЦА 2 — Метод Фогеля для получения опорного плана транспортной задачи

2. Поиск из всех разностей, как по строкам, так и по столбцам максимальный. В нашем примере максимальная разность равна 38 и находится в строке А₂. Обведем максимальную разность рамкой.

3. Размещение в клетку, где находится наименьшая стоимость (А₂В₂ = 18) (строка с наибольшей разностью), максимально возможного количества ресурсов. Оно равно 20, т.е. всему ресурсу отправителя А₂. Поскольку все ресурсы отправителя А₂ исчерпаны, строку А₂ исключаем из дальнейших расчетов, для чего отметим все клетки этой строки точками.

4. Вычисление разностей столбцам и строкам, не принимая во внимание стоимость в клетках, имеющих ресурсы и клетках с точкой (исключенную строку или столбец) и определение максимальной разности в строке или столбце (В₃ = 76).

5. Поиск минимального элемента в строке или в столбце с максимальной разностью (А₁В₃ = 24) и размещения в данную клетку максимально возможного количества ресурса, возвращение к этапу №4 и т.д. Окончательно

ЦФ Q=23∙19 + 7∙3 + 20∙18 + 2∙10 + 14∙24 + 1∙100 +3∙48 = = 437 + 21 + 360 + 20 +3 36 + 100 + 272 =1546 ед. Это значение соответствует опорному плану Фогеля.

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

Как основной метод решения транспортной задачи – используется метод потенциалов. Ни симплексный метод, ни распределительный метод здесь не рассматриваются. У них имеются свои плюсы и минусы, но объем изложения достаточно велик. Возможно этому позднее я уделю внимание и время, но пока отвечаю на пожелание читателя Хабра.

Пример 3 — Транспортная задача. Метод потенциалов

Исходные данные задачи удобно представить двумя матрицами.

ТАБЛИЦА — Исходные данные

Требуется найти план Х [m,n] перевозок, удовлетворяющий условиям на целевую функцию Q и переменные х_ij задачи

Решение задачи:

1. Формирование начального опорного плана способом Северо-Западного угла.

Базисные n + m – 1 = 3 + 4 – 1 = 6 переменные:
x₁₁ =70, x₁₂ = 20, x₂₂ = 10, x₂₃ = 20, x₂₄ = 0, x₃₄ = 40.
Остальные переменные nm – n + m – 1 = 12 – 6 = 6 свободные:
x₁₃ = x₁₄ = x₂₁ = x₂₄ = x₃₁= x₃₂ = 0 .
Суммарная стоимость перевозок для опорного плана получает представление:
Q = d₁₁ ∙x₁₁ + d₁₂∙x₁₂ + d₂₂∙x₂₂ + d₂₃∙x₂₃+ d₂₄∙x₂₄+ d₃₄∙x₃₄ =
=2∙70 + 3∙20 + 3∙10 + 1∙20 + 2∙0 + 2∙40 = 140 + 60 + 30 + 20 + 0 +80 = 330 ед.

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

Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов. Определим систему уравнений для потенциалов и вычислим их значения:

α₁ + β₁ = d₁₁ = 2;
α₁ + β₂ = d₁₂ = 3;
α₂ + β₂ = d₂₂ = 3;
α₂ + β₃ = d₂₃ = 1;
α₂ + β₄ = d₂₄ = 2;
α₃ + β₄ = d₃₄ = 2.

Каждое из этих значений соответствует одной базисной ячейке. Одну из неизвестных в системе можно задавать произвольно. Пусть β₁ = 0. Тогда после решения системы получены значения потенциалов: α₁= 2, α₂= 2, α₃= 2, β₁ =0, β₂=1, β₃ =–1, β₄ =0,

Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].

Выделяем в Г [m, n] свободные ячейки, содержащие γ_rs. Проверяем наличие положительных переменных γ_i,j > 0. Так как в матрице (в свободных ячейках) имеем γ₃₂ = 2 > 0, то исходный опорный план может быть улучшен, он не является оптимальным.

3. Переход к новому (улучшенному) опорному плану

Переменную x₃₂ =x следует ввести в базис. Обозначим ее предварительно через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся начальным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок

Модификация начального опорного плана

Обозначим ее предварительно через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся начальным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок Очевидно, что наибольшее x определяется теми x_ij в базисных клетках, из которых этот х вычитается. Следовательно, x₁₁ = min<х₂₂, х₃₄> = <10, 40>= 10. При x >10 перевозка х₂₂ становится отрицательной. Переменную х₂₂ исключаем из базиса и переводим ее в разряд свободных переменных. Далее повторяются рекурсивно три пункта алгоритма.

Получаем из модифицированного плана новый опорный план

В нем объемы перевозок распределены иначе чем в начальном опорном плане.

Новый опорный план

Суммарная стоимость перевозок для этого опорного плана получает представление:
Q = d₁₁ ∙x₁₁ + d₁₂∙x₁₂ + d₂₃∙x₂₃ + d₃₂∙x₃₂ + d₂₄∙x₂₄+ d₃₄∙x₃₄ =
=2∙70 + 3∙20 + 2∙10 + 1∙20 + 1∙10 + 2∙30 = 140 + 60 + 20 + 20 + 10 + 60 = 310 ед. Затраты на перевозки при этом плане уменьшились на 330 – 310 = 20 ед.

Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов.

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

Определим систему уравнений для потенциалов и вычислим их значения:
α₁ + β₁ = d₁₁ = 2;
α₁ + β₂ = d₁₂ = 3;
α₂ + β₃ = d₂₃ = 1;
α₂ + β₄ = d₂₄ = 2;
α₃ + β₂ = d₃₂ = 1;
α₃ + β₄ = d₃₄ = 2.

Каждое из этих значений соответствует одной базисной ячейке. Одну из неизвестных в системе можно задавать произвольно. Пустьα₁ = 0. Тогда после решения системы получены значения потенциалов: α₁= 0, α₂= – 2, α₃= –2, β₁ =2, β₂=3, β₃ = 3, β₄ =4.

Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].

Свободные ячейки матрицы Г [m, n] содержат γ_i,j > 0 (γ₁₄ = 1>0). План не оптимален.

3. Переход к новому (улучшенному) опорному плану

Из свободных переменных с x_ij > 0, выбираем одну x₁₄ для введения ее в базис. Обозначим ее как и ранее через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся очередным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок

модифицированный план

Очевидно, что наибольшее x определяется теми x_ij в базисных клетках, из которых этот х вычитается. Следовательно, x₁₁ = min<х₁₂, х₃₄> = <20, 30>= 20. При х₁₂ >20 перевозка х₁₂ становится отрицательной. Переменную х₁₂ исключаем из базиса и переводим ее в разряд свободных переменных. Переходим к новой итерации

1. Получаем из модифицированного плана новый опорный план.

В нем объемы перевозок распределены иначе чем в предшествующем опорном плане.

Суммарная стоимость перевозок для этого опорного плана получает представление:
Q = d₁₁ ∙x₁₁ + d₁₄∙x₁₄ + d₂₃∙x₂₃ + d₃₂∙x₃₂ + d₂₄∙x₂₄+ d₃₄∙x₃₄ =
=2∙70 + 3∙20 + 1∙20 + 2∙10 + 1∙30 + 2∙10 = 140 + 60 + 20 + 20 + 30 + 20 = 290 ед. Затраты на перевозки при этом плане уменьшились на 310 – 290 = 20 ед. Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов.

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

Определим систему уравнений для потенциалов и вычислим их значения:
α₁ + β₁ = d₁₁ = 2;
α₁ + β₄ = d₁₄ = 3;
α₂ + β₃ = d₂₃ = 1;
α₂ + β₄ = d₂₄ = 2;
α₃ + β₂ = d₃₂ = 1;
α₃ + β₄ = d₃₄ = 2. Каждое из этих значений соответствует одной базисной ячейке. Одну из неизвестных в системе можно задавать произвольно. Пусть β₁ = 0. Тогда после решения системы получены значения потенциалов: α₁= 2, α₂= 2, α₃= 2, β₁ =0, β₂=1, β₃ =–1, β₄ =0.

Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].

При переходе к новому опорному плану проверяем наличие положительных свободных переменных γ_i,j >0. Но таких переменных не оказалось. Отсюда следует вывод, что полученный последним модифицированный план является оптимальным и ему соответствует значение линейной формы
Q’= 2∙70 + 3∙20 + 1∙20 + 2∙10 + 1∙30 + 2∙10 = 290.

Заключение

Вся теория исследования операций с позиций математики решает неклассические задачи оптимизации целевых функций. Отличие от классики в том, что те ограничения на переменные, которые исследователи вынуждены накладывать в рамках моделей, созданы и вызваны реальностью. Отыскивать требуется экстремумы функций при многих ограничениях, так называемые условные экстремумы. Классика не позволяет этого делать. Взятие производных и приравнивание их нулю «не видит» ограничений. Лучшее, что там имеется это функция Лагранжа, но ее использование также весьма ограничено. Транспортные задачи – частный, но важный случай в исследовании операций. Надеюсь, что читатель разобравшись в приведенных примерах, лучше стал понимать логику задачи и сумеет самостоятельно постигать интересующие его вопросы по другим публикациям в учебниках и журнальных статьях.

Ваулин А. Е. Методы цифровой обработки данных.– СПб.: ВИККИ им. А. Ф. Можайского, 1993.– 106 с.

Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.

Корбут А.А., Финкельштейн Ю. Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.

Макаров И. М. и др. Теория выбора и принятия решений.– М.: Наука, 1982.– 328 с.

Пфанцагль И. Теория измерений. – М.: Наука, 1988.–384 с.

Таха Х. А. Введение в исследование операций. 7-е изд. М.: Изд. дом «Вильямс», 2005.

Фишберн П. С. Теория полезности для принятия решений. – М.: Наука,1978. –352 с.

Источник