Постановка транспортной задачи

Транспортная задача

Постановка транспортной задачи

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

Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным.

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

Пример.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через количество единиц сырья, перевозимого из i–го пункта его получения на j–е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(6)

При данном плане перевозок общая стоимость перевозок составит

(7)

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

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

Основные шаги при решении транспортной задачи:

1. Найти начальный допустимый план.

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

3. Выбрать выводимую из базиса переменную, найти новое базисное решение. Вернуться к шагу 2.

 

Всякое неотрицательное решение систем линейных уравнений (2) и (3), определяемое матрицей , называется планом транспортной задачи. Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение.

Обычно исходные данные транспортной задачи записывают в виде таблицы.

Матрицу С называют матрицей транспортных затрат, матрицу X, удовлетворяющую условиям Т-задачи (2) и (3) называют планом перевозок, а переменные - перевозками. План , при котором целевая функция минимальна, называется оптимальным.

Число переменных в транспортной задаче с m пунктами отправления и n пунктами назначения равно m*n, а число уравнений в системах (2) и (3) равно m+n. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно m+n–1. Следовательно, опорный план транспортной задачи может иметь не более m+n–1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности m+n–1, то план является невырожденным, а если меньше – то вырожденным.

Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

Построение допустимого (опорного) плана в транспортной задаче

По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Существует несколько методов построения начальных опорных планов Т-задачи. Из них самый распространенный метод северо-западного угла и метод минимального элемента.

Наиболее простой способ его нахождения основывается на так называемом мето­де северо-западного угла. Суть метода состоит в последова­тельном распределении всех запасов, имеющихся в первом, вто­ром и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте про­изводства или к попытке полного удовлетворения потребно­стей в очередном пункте потребления. На каждом шаге q вели­чины текущих нераспределенных запасов обозначаются а_i^(q), а текущих неудовлетворенных потребностей — b_j^{(q )}. Построение допустимого начального плана, согласно методу северо-запад­ного угла, начинается с левого верхнего угла транспортной таб­лицы, при этом полагаем а_i⁽⁰⁾= а_i, b_j⁽⁰⁾= b_j. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются зна­чения нераспределенного запаса в i -ом пункте производства и неудовлетворенной потребности j -ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: х_i,j=min{а_i^(q), b_j^(q)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на дан­ную величину:

а_i^(q+1)= а_i^(q) - x_i,j, b_j^(q+1)= b_j^(q) - x_i,j

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: а_i^(q+1)= 0 или b_j^(q+1)= 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте произ­водства i+1, т. е. переместиться к следующей клетке вниз по столбцу. Если же b_j^(q+1) = 0, то значит, полностью удовлетворе­на потребность для j -го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все пере­численные операции.

Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы полу­чим допустимый план. В силу того же условия число шагов ал­горитма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не ис­ключено, что на некотором промежуточном шаге текущий не­распределенный запас оказывается равным текущей неудовлет­воренной потребности (а_i^(q)=b_j^(q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и по­требления), а это означает «потерю» одной ненулевой компо­ненты в плане или, другими словами, вырожденность построен­ного плана.

Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимально­го. Это происходит потому, что при его построении никак не учитываются значения c_i,j. В связи с этим на практике для по­лучения исходного плана используется другой способ — ме­тод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наи­меньшими ценами.

 

Пример нахождения опорного плана

Поставщики	Потребители и их спрос	Мощность поставщиков

 

F=14 x₁₁ + 28 x₁₂ + 21 x₁₃ + 28 x₁₄ + 10 x₂₁ + 17 x ₂₂ + 15 x₂₃ + 24 x₂₄ + 14 x₃₁ + 30 x₃₂ +25 x₃₃ + 21 x₃₄

 

Первоначальный план получен по методу северо-западного угла. Задача сбалансированная (закрытая).

Таблица 1

 

Стоимость перевозок по данному плану составляет: 1681:

F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 =1681

Решение задачи в Excel

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

Если такой команды в меню нет, то необходимо выполнить команду Сервис/Надстройки и установить Поиск решения.

После выполнения команды появится окно:

 

 

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

Задать параметры «Линейная модель» и «Неотрицательные значения» (См. лекцию по ЛП).

Для нахождения решения нажать кнопку «Выполнить» в окне Поиска решения.

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

 

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

В окне "Результаты поиска решения" представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы". Для выбора нужных отчетов необходимо выделить их названия. Отчет будет представлен на отдельном листе рабочей книги Excel.

 

Для получения более полной информации в отчете по устойчивости нужно в окне задания параметров установить флажок "Линейная модель ".

 

Для получения же ответа (значений переменных и ЦФ) прямо в экранной форме можно сразу нажать кнопку "OK". После этого в экранной форме появляется оптимальное решение задачи.

 

Замечания по решению ТЗ:

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

· Если задача не сбалансированная и при этом объемы предложения больше спроса, то ограничения не меняются.

· Если задача не сбалансированная и при этом объемы предложения меньше спроса, то в ограничениях на количество отправляемых грузов надо знак «<=» поменять на знак «=», а в ограничениях на количество доставляемых грузов поменять знак «>=» на знак «<=» (т.е. не все потребности будут удовлетворены).

· Если по каким-либо маршрутам нельзя перевозить продукцию, то стоимости перевозок по этим маршрутам задаются так, чтобы они превышали самые высокие стоимости возможных перевозок (для того, чтобы было невыгодно везти по недоступным маршрутам) – при решении задачи на минимум. На максимум – наоборот.

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

§ из запаса соответствующего пункта отправки;

§ из потребности соответствующего пункта назначения.

Отчет по результатам

Отчет по результатам состоит из трех таблиц:

· таблица 1 содержит информацию о ЦФ;

· таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи;

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

Отчет по устойчивости

Отчет по устойчивости состоит из двух таблиц.

 

Таблица 1 содержит информацию, относящуюся к переменным:

· Результ. значение показывает результат решения задачи.

· Нормированная стоимость показывает, на сколько изменится значение ЦФ в случае принудительного включения единицы соответствующей перевозки в оптимальное решение.

· Коэффициенты ЦФ отображают исходные данные.

· Допустимое увеличение и уменьшение показывают предельные значения приращения целевых коэффициентов, при которых сохраняется первоначальное оптимальное решение. Другими словами: на сколько нужно снизить затраты на перевозку по неиспользуемым направлениям, чтобы по ним было выгодно везти продукцию. Например, если затраты на перевозку из А1 в В2 снизить более, чем на 5 единиц, т.е. они станут < 28-5, то везти груз по этому маршруту станет выгодно.

Таблица 2 содержит информацию, относящуюся к ограничениям.

· Результ. значение показывает сколько всего груза заберут у производителей и привезут потребителям.

· Теневая цена показывает, на сколько будет изменяться значение ЦФ (т.е. общие затраты на перевозки), если будут уменьшаться потребности в пунктах назначения или увеличиваться запасы в пунктах отправления (в другую сторону невозможно, т.к. данная задача будет неразрешима из-за превышения спроса над предложением).

· Ограничение правая часть показывает исходные данные из правых частей ограничений.

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

Транспортная задача

Постановка транспортной задачи

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

Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным.

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